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

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

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

一、單項選擇題：本大題共15小題，每小題2分，共30分。在每小題列出的備選項中只有一項是最符合題目要求的，請將其選出。

1.與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置、個數(shù)無關(guān)的是數(shù)據(jù)的(　　)

A.存儲結(jié)構(gòu)
B.邏輯結(jié)構(gòu)
C.類型
D.運算實現(xiàn)

2.時間復(fù)雜度的階數(shù)中，O(n)表示(　　)

A.常數(shù)階
B.線性階
C.多項式階
D.指數(shù)階

3.假設(shè)順序表的長度為n，則在第i(1≤i≤n+1)個元素之前插入一個新元素x所需移動元素的個數(shù)為(　　)

A.i
B.n-i
C.n-i+1
D.n

4.在雙向循環(huán)鏈表中，設(shè)p指向待刪結(jié)點，刪除*p的正確語句為(　　)

A.p->prior->next=p->next; p->next->prior=p->prior; free(p);
B.p->next= p->prior->next; p->prior= p->next->prior; free(p);
C.p->prior->next=p->next; p->next->prior=-p->prior;
D.p->next=p->prior->next; p->prior= p->next->prior;

5.關(guān)于棧和隊列，下面敘述正確的是(　　)

A.函數(shù)的嵌套調(diào)用用隊列來實現(xiàn)
B.操作系統(tǒng)中進(jìn)程調(diào)用用棧來實現(xiàn)
C.程序遞歸的處理用隊列來實現(xiàn)
D.棧和隊列是運算受限的線性表

6.設(shè)兩個數(shù)據(jù)元素類型一致的棧共享一維數(shù)組空間data[max]成為雙棧，兩個棧的棧底分別設(shè)在數(shù)組兩端，這兩個棧的棧頂變量分別為top1和top2，且top2≥top1，則下列會發(fā)生“上溢”情況的是(　　)

A.top1+1=top2
B.top1=top2
C.top2+1-=top1
D.top1+top2=max

7.設(shè)有一循環(huán)隊列SQ，現(xiàn)將數(shù)據(jù)x進(jìn)行入隊操作，語句為(　　)

A.SQ. front=(SQ. front+1)%maxsize;
B.SQ. rear=(SQ. rear+1)%maxsize;
C.SQ. front=(SQ. front +1)%maxsize; SQ. data[SQ. front]=x;
D.SQ. rear=(SQ. rear+1)%maxsize; SQ. data[SQ.rear]=x;

8.關(guān)于樹的概念，下面敘述正確的是(　　)

A.樹可以沒有根結(jié)點
B.樹中結(jié)點個數(shù)不為0
C.樹中可以存在多個根節(jié)點
D.若樹中存在多個子樹，則子樹之間可以相交

9.關(guān)于滿二叉樹和完全二叉樹，下面敘述正確的是(　　)

A.完全二叉樹結(jié)點個數(shù)>滿二叉樹結(jié)點個數(shù)
B.滿二叉樹一定是完全二叉樹
C.完全二叉樹一定是滿二叉樹
D.含有n個結(jié)點的完全二叉樹的深度為log₂n

10.與二叉鏈表結(jié)構(gòu)形式完全相同的是(　　)

A.孩子鏈表
B.孩子兄弟鏈表
C.帶雙親的孩子鏈表
D.雙親鏈表

11.一個具有n個頂點的無向完全圖的邊數(shù)為(　　)

A.n²/2
B.n²
C.n(n-1)/2
D.n(n-1)

12.鄰接表的存儲方法結(jié)合了(　　)

A.順序存儲與散列存儲
B.順序存儲與鏈?zhǔn)酱鎯?br/>C.鏈?zhǔn)酱鎯εc索引存儲
D.鏈?zhǔn)酱鎯εc散列存儲

13.假設(shè)順序表為(b1，b2，b3)，查找b1，b2，b3的概率分別為0.2，0.2，0.6，則順序查找法的平均查找長度為(　　)

A.1
B.1.2
C.1.4
D.1.6

14.已知一個有序表為(13，18，24，35，47，50，62，83，90，115，134)，當(dāng)用二分查找方法查找值為90的元素時，查找成功時，鍵值比較的次數(shù)為(　　)

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

15.在插入排序方法中，類似圖書館中整理圖書的過程的是(　　)

A.希爾排序
B.表插入排序
C.折半插入排序
D.直接插入排序

二、填空題：本大題共13空，每空2分，共26分。

11.在估算算法空間復(fù)雜度時，一般只需要分析_________所占用的空間。

12.對于按位置查找運算，順序表是隨機(jī)存取，其時間復(fù)雜度為_________。

13.設(shè)順序表A長度為100，若下標(biāo)從1開始計數(shù)，則刪除元素A[10]需要移動_________個元素。

14.循環(huán)隊列的隊頭指針為front，隊尾指針為rear，當(dāng)_________時表明隊列為空。

15.對于一棵包含n個結(jié)點的二叉樹，用二叉鏈表存儲時，其指針總數(shù)為_________個。

16.若對一棵有n(n>0)個結(jié)點的完全二叉樹從1開始進(jìn)行結(jié)點的編號，并按此編號把它順序存儲到一維數(shù)組A中，即編號為1的結(jié)點存儲到A[1]中，其余類推。若i>2，則A[i]的雙親結(jié)點為_________。

17.用于描述分類過程的二叉樹稱為_________。

18.在樹形結(jié)構(gòu)中，每一層結(jié)點只能和上一層中的至多一個結(jié)點相關(guān)，而在_________中，任意兩個結(jié)點之間都可能相關(guān)。

19.Dijkstra算法的思想是按照最短路徑長度_________的方法產(chǎn)生從一點到其他頂點的最短路徑。

110.遍歷圖的基本方法有深度優(yōu)先搜索和_________優(yōu)先搜索兩種。

111.作為一種數(shù)據(jù)結(jié)構(gòu)，查找表的邏輯結(jié)構(gòu)是_________。

112.對于具有n個元素的數(shù)據(jù)序列，采用二叉排序樹查找，平均查找長度介于_________之間。

113.直接插入排序的空間復(fù)雜度為_________。

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

21.已知一個7×6的稀疏矩陣如題29圖所示，試寫出該稀疏矩陣的三元組表示。

22.已知一棵二叉樹如題30圖所示，試求該二叉樹的先序遍歷序列、后序遍歷序列和層次遍歷序列。

23.設(shè)有向圖的鄰接表表示如題31圖所示，請給出每個頂點的入度和出度。

24.已知散列表的地址空間為0~10，散列函數(shù)為H(key)= key mod11(mod表示求余運算)，采用二次探測法解決沖突，試用鍵值序列20，38，16，27，5，23，56，29建立散列表，并計算出等概率情況下查找成功的平均查找長度。

25.給出一組關(guān)鍵字(20，29，11，74，35，3，8，56)，寫出冒泡排序前兩趟的排序結(jié)果，并說明冒泡排序算法的穩(wěn)定性如何?

四、算法設(shè)計題：本大題共2小題，每小題7分，共14分。

31.設(shè)有一n階方陣A，設(shè)計算法實現(xiàn)對該矩陣的轉(zhuǎn)置。

32.已知二叉鏈表的類型定義如下：typedef struct btnode{  DataType data;   struct btnode *lchild, *rchild;}*BinTree;假定vsit(bt)是一個已定義的過程，其功能是訪問指針bt所指結(jié)點。設(shè)計遞歸算法preorder( BinTree bt)實現(xiàn)在二叉鏈表上的先序遍歷。