?數據結構自考2013年10月真題

數據結構自考2013年10月真題及答案解析

本試卷為單選題型，填空題，算法閱讀，算法設計等題型。

一、單項選擇題(本大題共15小題，每小題2分，共30分) 在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內。錯選、多選或未選均無分。

1.算法的時間復雜度表征的是(　　)

A.算法的可讀性
B.算法的難易程度
C.執行算法所耗費的時間
D.執行算法所耗費的存儲空間

2.對需要頻繁插入和刪除結點的線性表，適合的存儲方式是(　　)

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

3.在頭指針為head的循環鏈表中，判斷指針變量P指向尾結點的條件是(　　)

A.p->next->next==head
B.p->next==head
C.p->next->next==NULL
D.p->next==NULL

4.迪杰斯特拉(Dijkstra)算法的功能是(　　)

A.求圖中某頂點到其他頂點的最短路徑
B.求圖中所有頂點之間的最短路徑
C.求圖的最小生成樹
D.求圖的拓撲排序序列

5.若棧的進棧序列為1，2，3，4，5，則經過出入棧操作不可能獲得的出棧序列是(　　)

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

6.A是7×4的二維數組，按行優先方式順序存儲，元素A[0][0]的存儲地址為1 000，若每個元素占2個字節，則元素A[3][3]的存儲地址為(　　)

A.1015
B.1016
C.1028
D.1030

7.深度為4的完全二叉樹的結點數至少為(　　)

A.4
B.8
C.13
D.15

8.若采用鄰接矩陣A存儲有向圖G，則結點k的入度等于A中(　　)

A.結點k對應行元素之和
B.結點k對應列元素之和
C.結點k對應行和列元素之和
D.非零元素之和

9.無向圖G的鄰接矩陣一定是(　　)

A.對稱矩陣
B.對角矩陣
C.三角矩陣
D.單位矩陣

10.下列關于有向帶權圖G的敘述中，錯誤的是(　　)

A.圖G的任何一棵生成樹都不含有回路
B.圖G生成樹所含的邊數等于頂點數減1
C.圖G含有回路時無法得到拓撲序列
D.圖G的最小生成樹總是唯一的

11.在下列排序算法中，關鍵字比較次數與初始排列次序無關的是(　　)

A.冒泡排序
B.希爾排序
C.直接插入排序
D.直接選擇排序

12.對下圖進行拓撲排序，可以得到的拓撲序列是(　　)

A.a b c d e
B.b a c d e
C.b c a d e
D.a b d c e

13.下列線性表中，能使用二分查找的是(　　)

A.順序存儲(2,12,5,6,9,3,89,34,25)
B.鏈式存儲(2,12,5,6,9,3,89,34,25)
C.順序存儲(2,3,5,6,9,12,25,34,89)
D.鏈式存儲(2,3,5,6,9,12,25,34,89)

14.在下列查找方法中，平均查找長度與結點數量無直接關系的是(　　)

A.順序查找
B.分塊查找
C.散列查找
D.基于B樹的查找

15.下列排序算法中，時間復雜度為的算法是(　　)

A.快速排序
B.冒泡排序
C.直接選擇排序
D.直接插入排序

二、填空題(本大題共10小題，每小題2分，共20分) 請在每小題的空格中填上正確答案。錯填、不填均無分。

11.數據的同一種邏輯結構，可以對應多種不同的__________。

12.若在長度為n的順序表第i個元素之前插入一個元素，則需要向后移動的元素個數是__________。

13.順序棧存放在S[m]中，S[0]為棧底，棧頂指針top初始值為-1，則棧滿的條件是top= __________。

14.隊列只能在隊尾進行插入操作，在隊首進行__________操作。

15.廣義表A=(x，((y，z)，a，b))，則函數head(head(tail(A)))的值是__________。

16.以權值分別為4，3，2，1的四個葉子結點構成的哈夫曼樹，其帶權路徑長度WPL是_______。

17.圖的遍歷方法有兩種，一種是深度優先遍歷，另一種是__________。

18.如果排序算法是穩定的，則關鍵字相同的兩個記錄排序前后相對次序__________。

19.己知散列表表長m=11，散列函數h(key)=key%11，表中存有三個關鍵字15，27，39，其余地址為空，若采用線性探查法處理沖突，則關鍵字為60的結點保存的地址是_________。

110.己知圖G的鄰接表如題25圖所示。 從頂點v1出發進行深度優先搜索，得到的深度優先搜索序列是__________.

三、解答題(本大題共4小題，每小題5分，共20分)

21.設Q[M]是有M個元素存儲空間的循環隊列，若front指向隊首元素，rear指向隊尾 元素的下一位置，請分別用C語言描述下列操作：(1)將元素x入隊;(2)將隊首元素出隊，并保存到變量y中;(3)計算當前隊列中元素個數。

22.己知帶權圖G=(VE)，其中V=(A，B，C，D，E)，鄰接矩陣如下(1)畫出對應的圖G(2)畫出圖G的最小生成樹

23.已知一組待排記錄的關鍵字序列為(15，11，17，59，14，35，13，17，24，84)，請給出對應的小根堆序列。

24.已知二叉樹如題29圖，請畫出該二叉樹的前序線索。

四、算法閱讀題(本大題共4小題，每小題5分，共20分)

31.閱讀下列函數并回答問題(1)執行該函數后，單鏈表head中data值為x的結點數是多少?(2)該函數的功能是什么?

32.閱讀下列函數并回答問題typedef struct node{          DataType data;          struct node *lchild， *rchild;}BinTNode;typedef B inTNode *BinTree;void Inorder(BinTree bt){           if(bt!=NULL){              Inorder(bt->lchild);              printf(〃%c〃，bt->data);              Inorder(bt->rchild);        }}(1)給出對如題3 1圖所示的二叉樹執行函數Inorder后得到的輸出序列。(2)該函數的功能是什么?

33.下列函數實現直接插入排序，請填寫適當內容，使其功能完整。

34.函數BinSearch實現二分查找，請回答下列問題。(1)在空白處填寫適當內容，使函數功能完整。(2)查找成功時函數的返回值是什么?(3)查找失敗時函數的返回值是什么?

五、算法設計題(本大題共1小題，共10分)

41.已知：typedef struct node{       int data;       struct node *next;} LinkNode;typedef LinkNode *LinkList;請編寫原型為int Listisequal(LinkList A，LinkList B)的函數，指針A、B分別指向兩個帶頭結點的單鏈表。函數功能是：若單鏈表A、B中全部對應結點的data值相等，則返回1，否則返回0。