數據結構導論2017年10月真題及答案解析（02142）

數據結構導論2017年10月真題及答案解析（02142），該試卷為數據結構導論自考歷年真題試卷，包含答案及詳細解析。

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

1.與數據元素本身的形式、內容、相對位置、個數無關的是數據的(　　)

A.存儲結構
B.邏輯結構
C.類型
D.運算實現

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

A.常數階
B.線性階
C.多項式階
D.指數階

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

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

4.在雙向循環鏈表中，設p指向待刪結點，刪除*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.關于棧和隊列，下面敘述正確的是(　　)

A.函數的嵌套調用用隊列來實現
B.操作系統中進程調用用棧來實現
C.程序遞歸的處理用隊列來實現
D.棧和隊列是運算受限的線性表

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

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

7.設有一循環隊列SQ，現將數據x進行入隊操作，語句為(　　)

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.關于樹的概念，下面敘述正確的是(　　)

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

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

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

10.與二叉鏈表結構形式完全相同的是(　　)

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

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

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

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

A.順序存儲與散列存儲
B.順序存儲與鏈式存儲
C.鏈式存儲與索引存儲
D.鏈式存儲與散列存儲

13.假設順序表為(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)，當用二分查找方法查找值為90的元素時，查找成功時，鍵值比較的次數為(　　)

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

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

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

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

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

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

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

14.循環隊列的隊頭指針為front，隊尾指針為rear，當_________時表明隊列為空。

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

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

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

18.在樹形結構中，每一層結點只能和上一層中的至多一個結點相關，而在_________中，任意兩個結點之間都可能相關。

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

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

111.作為一種數據結構，查找表的邏輯結構是_________。

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

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

三、應用題：本大題共5小題，每小題6分，共30分。

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

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

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

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

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

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

31.設有一n階方陣A，設計算法實現對該矩陣的轉置。

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