違法信息舉報(bào) 客服熱線:400-118-7898
廣告
?
專接本欄目測(cè)試廣告

?數(shù)據(jù)結(jié)構(gòu)導(dǎo)論2014年4月真題(02142)

自考 責(zé)任編輯:彭雅倩 2019-06-26

摘要:數(shù)據(jù)結(jié)構(gòu)導(dǎo)論2014年4月真題及答案解析(02142),該試卷為數(shù)據(jù)結(jié)構(gòu)導(dǎo)論自考?xì)v年真題試卷,包含答案及詳細(xì)解析。

數(shù)據(jù)結(jié)構(gòu)導(dǎo)論2014年4月真題及答案解析(02142)

數(shù)據(jù)結(jié)構(gòu)導(dǎo)論2014年4月真題及答案解析(02142),該試卷為數(shù)據(jù)結(jié)構(gòu)導(dǎo)論自考?xì)v年真題試卷,包含答案及詳細(xì)解析。

一、單項(xiàng)選擇題(本大題共15小題,每小題2分,共30分)在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的,請(qǐng)將其選出并將“答題紙”的相應(yīng)代碼涂黑。錯(cuò)涂、多涂或未涂均無(wú)分。

1.下列幾種算法時(shí)間復(fù)雜度中,最小的是(  )

A.O(log2n)
B.O(n)
C.O(n2)
D.O(1)

2.數(shù)據(jù)的存儲(chǔ)方式中除了順序存儲(chǔ)方式和鏈?zhǔn)酱鎯?chǔ)方式之外,還有(  )

A.索引存儲(chǔ)方式和樹(shù)形存儲(chǔ)方式
B.線性存儲(chǔ)方式和散列存儲(chǔ)方式
C.線性存儲(chǔ)方式和索引存儲(chǔ)方式
D.索引存儲(chǔ)方式和散列存儲(chǔ)方式

3.表長(zhǎng)為n的順序表中做刪除運(yùn)算的平均時(shí)間復(fù)雜度為(  )

A.O(1)
B.O(log2n)
C.O(n)
D.O(n2)

4.順序表中定位算法(查找值為x的結(jié)點(diǎn)序號(hào)最小值)的平均時(shí)間復(fù)雜度為(  )

A.O(1)
B.O(log2n)
C.O(n)
D.O(n2)

5.元素的進(jìn)棧次序?yàn)锳,B,C,D,E,出棧的第一個(gè)元素為E,則第四個(gè)出棧的元素為(  )

A.D
B.C
C.B
D.A

6.帶頭結(jié)點(diǎn)的鏈隊(duì)列中,隊(duì)列頭和隊(duì)列尾指針?lè)謩e為front和rear,則判斷隊(duì)列空的條件為(  )

A.front==rear
B.front!=NULL
C.rear!==NULL
D.front==NULL

7.深度為5的二叉樹(shù),結(jié)點(diǎn)個(gè)數(shù)最多為(  )

A.31個(gè)
B.32個(gè)
C.63個(gè)
D.64個(gè)

8.如果結(jié)點(diǎn)A有2個(gè)兄弟結(jié)點(diǎn),結(jié)點(diǎn)B為A的雙親,則B的度為(  )

A.1
B.3
C.4
D.5

9.將題9圖所示的一棵樹(shù)轉(zhuǎn)換為二叉樹(shù),結(jié)點(diǎn)C是(  )

A.A的左孩子
B.A的右孩子
C.B的右孩子
D.E的右孩子

10.n為圖的頂點(diǎn)個(gè)數(shù),e為圖中弧的數(shù)目,則圖的拓?fù)渑判蛩惴ǖ臅r(shí)間復(fù)雜度為(  )

A.O(n)
B.O(e)
C.O(n-e)
D.O(n+e)

11.無(wú)向圖的鄰接矩陣是(  )

A.對(duì)角矩陣
B.稀疏矩陣
C.上三角矩陣
D.對(duì)稱矩陣

12.在具有101個(gè)元素的順序表中查找值為x的元素結(jié)點(diǎn)時(shí),平均比較元素的次數(shù)為(  )

A.50
B.51
C.100
D.101

13.構(gòu)造散列函數(shù)的方法很多,常用的構(gòu)造方法有(  )

A.數(shù)字分析法、除留余數(shù)法、平方取中法
B.線性探測(cè)法、二次探測(cè)法、除留余數(shù)法
C.線性探測(cè)法、除留余數(shù)法、鏈地址法
D.線性探測(cè)法、二次探測(cè)法、鏈地址法

14.就平均時(shí)間性能而言,快速排序方法最佳,其時(shí)間復(fù)雜度為(  )

A.O(n)
B.O(nlog2n)
C.O(n2)
D.O(1og2n)

15.下述算法中,不穩(wěn)定的排序算法是(  )

A.直接插入排序
B.冒泡排序
C.堆排序
D.歸并排序

二、填空題(本大題共13小題,每小題2分,共26分)

11.數(shù)據(jù)的基本單位是_________。

12.雙向循環(huán)鏈表中,在p所指結(jié)點(diǎn)的后面插入一個(gè)新結(jié)點(diǎn)*t,需要修改四個(gè)指針,分別為t->prior=P; t->next=p->next; _________; p->next=t; 。

13.在帶有頭結(jié)點(diǎn)的循環(huán)鏈表中,尾指針為rear,判斷指針P所指結(jié)點(diǎn)為首結(jié)點(diǎn)的條件是_________。

14.若線性表中最常用的操作是求表長(zhǎng)和讀表元素,則順序表和鏈表這兩種存儲(chǔ)方式中,較節(jié)省時(shí)間的是_________。

15.不含任何數(shù)據(jù)元素的棧稱為_(kāi)________。

16.稀疏矩陣一般采用的壓縮存儲(chǔ)方法是_________。

17.100個(gè)結(jié)點(diǎn)的二叉樹(shù)采用二叉鏈表存儲(chǔ)時(shí),用來(lái)指向左、右孩子結(jié)點(diǎn)的指針域有_________個(gè)。

18.已知完全二叉樹(shù)的第5層有5個(gè)結(jié)點(diǎn),則整個(gè)完全二叉樹(shù)有_________個(gè)結(jié)點(diǎn)。

19.n個(gè)頂點(diǎn)的有向圖G用鄰接矩陣A[1..n,1..n]存儲(chǔ),其第i列的所有元素之和等于頂點(diǎn)Vi的_________。

110.具有10個(gè)頂點(diǎn)的有向完全圖的弧數(shù)為_(kāi)________。

111.要完全避免散列所產(chǎn)生的“堆積”現(xiàn)象,通常采用_________解決沖突。

112.在長(zhǎng)度為n的帶有崗哨的順序表中進(jìn)行順序查找,查找不成功時(shí),與關(guān)鍵字的比較次數(shù)為_(kāi)________。

113.歸并排序算法的時(shí)間復(fù)雜度是_________。

三、應(yīng)用題(本大題共5小題,每小題6分,共30分)

21.稀疏矩陣A如題29圖所示,寫出該稀疏矩陣A的三元組表示法。

22.設(shè)二叉樹(shù)的中序遍歷序列為BDCEAFHG,后序遍歷序列為DECBHGFA,試畫出該二叉樹(shù)。

23.寫出題31圖所示無(wú)向圖的鄰接矩陣,并寫出每個(gè)頂點(diǎn)的度。                      題31圖

24.已知散列表的地址空間為0至13,散列函數(shù)H(k)=k mod 11,(mod為求余運(yùn)算),待散列序列為(26,61,38,84,49),用二次探測(cè)法解決沖突,構(gòu)造該序列的散列表,要求寫出處理沖突的過(guò)程。

25.將一組鍵值(80,50,65,13,86,35,96,57,39,79,59,15)應(yīng)用二路歸并排序算法從小到大排序,試寫出各趟的結(jié)果。

四、算法設(shè)計(jì)題(本大題共2小題,每小題7分,共14分)

31.設(shè)單鏈表及鏈棧S的結(jié)構(gòu)定義如下:typedef struct node{  Data Type data;   struct node *next;}linkstack;編寫一個(gè)算法void ReverseList(1inkstack *head),借助于棧S將帶頭結(jié)點(diǎn)單鏈表head中序號(hào)為奇數(shù)的結(jié)點(diǎn)逆置,序號(hào)為偶數(shù)的結(jié)點(diǎn)保持不變。(例如:?jiǎn)捂湵淼倪壿嫿Y(jié)構(gòu)為(a1,a2,a3,a4,a5,a6),逆置后變?yōu)?a5,a2,a3,a4,a1,a6))。說(shuō)明:棧的初始化運(yùn)算用InitStack(S);進(jìn)棧運(yùn)算用Push(S, x);判??者\(yùn)算用EmptyStack(S);出棧運(yùn)算用Pop(S);取棧頂元素運(yùn)算用Gettop(S)。

32.以二叉鏈表作為存儲(chǔ)結(jié)構(gòu),試編寫遞歸算法實(shí)現(xiàn)求二叉樹(shù)中葉子結(jié)點(diǎn)個(gè)數(shù)。

更多資料

00149《國(guó)際貿(mào)易理論與實(shí)務(wù)》【知識(shí)集錦】

00159《高級(jí)財(cái)務(wù)會(huì)計(jì)》【知識(shí)集錦】

00184《市場(chǎng)營(yíng)銷策劃》【知識(shí)集錦】

溫馨提示:因考試政策、內(nèi)容不斷變化與調(diào)整,本網(wǎng)站提供的以上信息僅供參考,如有異議,請(qǐng)考生以權(quán)威部門公布的內(nèi)容為準(zhǔn)!

自考備考資料免費(fèi)領(lǐng)取

去領(lǐng)取

資料下載
  • 00152《組織行為學(xué)》【知識(shí)集錦】

    下載
  • 00158《資產(chǎn)評(píng)估》【知識(shí)集錦】

    下載
  • 00148《國(guó)際企業(yè)管理》【知識(shí)集錦】

    下載
  • 00160《審計(jì)學(xué)》【知識(shí)集錦】

    下載