數(shù)據(jù)結(jié)構(gòu)自考2013年10月真題及答案解析

本試卷為單選題型，填空題，算法閱讀，算法設(shè)計(jì)等題型。

一、單項(xiàng)選擇題(本大題共15小題，每小題2分，共30分) 在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫(xiě)在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無(wú)分。

1.算法的時(shí)間復(fù)雜度表征的是(　　)

A.算法的可讀性
B.算法的難易程度
C.執(zhí)行算法所耗費(fèi)的時(shí)間
D.執(zhí)行算法所耗費(fèi)的存儲(chǔ)空間

2.對(duì)需要頻繁插入和刪除結(jié)點(diǎn)的線性表，適合的存儲(chǔ)方式是(　　)

A.順序儲(chǔ)存
B.鏈?zhǔn)酱鎯?chǔ)
C.索引存儲(chǔ)
D.散列存儲(chǔ)

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

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

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

A.求圖中某頂點(diǎn)到其他頂點(diǎn)的最短路徑
B.求圖中所有頂點(diǎn)之間的最短路徑
C.求圖的最小生成樹(shù)
D.求圖的拓?fù)渑判蛐蛄?/p>

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

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的二維數(shù)組，按行優(yōu)先方式順序存儲(chǔ)，元素A[0][0]的存儲(chǔ)地址為1 000，若每個(gè)元素占2個(gè)字節(jié)，則元素A[3][3]的存儲(chǔ)地址為(　　)

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

7.深度為4的完全二叉樹(shù)的結(jié)點(diǎn)數(shù)至少為(　　)

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

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

A.結(jié)點(diǎn)k對(duì)應(yīng)行元素之和
B.結(jié)點(diǎn)k對(duì)應(yīng)列元素之和
C.結(jié)點(diǎn)k對(duì)應(yīng)行和列元素之和
D.非零元素之和

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

A.對(duì)稱(chēng)矩陣
B.對(duì)角矩陣
C.三角矩陣
D.單位矩陣

10.下列關(guān)于有向帶權(quán)圖G的敘述中，錯(cuò)誤的是(　　)

A.圖G的任何一棵生成樹(shù)都不含有回路
B.圖G生成樹(shù)所含的邊數(shù)等于頂點(diǎn)數(shù)減1
C.圖G含有回路時(shí)無(wú)法得到拓?fù)湫蛄?br/>D.圖G的最小生成樹(shù)總是唯一的

11.在下列排序算法中，關(guān)鍵字比較次數(shù)與初始排列次序無(wú)關(guān)的是(　　)

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

12.對(duì)下圖進(jìn)行拓?fù)渑判?，可以得到的拓?fù)湫蛄惺?　　)

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.順序存儲(chǔ)(2,12,5,6,9,3,89,34,25)
B.鏈?zhǔn)酱鎯?chǔ)(2,12,5,6,9,3,89,34,25)
C.順序存儲(chǔ)(2,3,5,6,9,12,25,34,89)
D.鏈?zhǔn)酱鎯?chǔ)(2,3,5,6,9,12,25,34,89)

14.在下列查找方法中，平均查找長(zhǎng)度與結(jié)點(diǎn)數(shù)量無(wú)直接關(guān)系的是(　　)

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

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

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

二、填空題(本大題共10小題，每小題2分，共20分) 請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無(wú)分。

11.數(shù)據(jù)的同一種邏輯結(jié)構(gòu)，可以對(duì)應(yīng)多種不同的__________。

12.若在長(zhǎng)度為n的順序表第i個(gè)元素之前插入一個(gè)元素，則需要向后移動(dòng)的元素個(gè)數(shù)是__________。

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

14.隊(duì)列只能在隊(duì)尾進(jìn)行插入操作，在隊(duì)首進(jìn)行__________操作。

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

16.以權(quán)值分別為4，3，2，1的四個(gè)葉子結(jié)點(diǎn)構(gòu)成的哈夫曼樹(shù)，其帶權(quán)路徑長(zhǎng)度WPL是_______。

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

18.如果排序算法是穩(wěn)定的，則關(guān)鍵字相同的兩個(gè)記錄排序前后相對(duì)次序__________。

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

110.己知圖G的鄰接表如題25圖所示。 從頂點(diǎn)v1出發(fā)進(jìn)行深度優(yōu)先搜索，得到的深度優(yōu)先搜索序列是__________.

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

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

22.己知帶權(quán)圖G=(VE)，其中V=(A，B，C，D，E)，鄰接矩陣如下(1)畫(huà)出對(duì)應(yīng)的圖G(2)畫(huà)出圖G的最小生成樹(shù)

23.已知一組待排記錄的關(guān)鍵字序列為(15，11，17，59，14，35，13，17，24，84)，請(qǐng)給出對(duì)應(yīng)的小根堆序列。

24.已知二叉樹(shù)如題29圖，請(qǐng)畫(huà)出該二叉樹(shù)的前序線索。

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

31.閱讀下列函數(shù)并回答問(wèn)題(1)執(zhí)行該函數(shù)后，單鏈表head中data值為x的結(jié)點(diǎn)數(shù)是多少?(2)該函數(shù)的功能是什么?

32.閱讀下列函數(shù)并回答問(wèn)題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)給出對(duì)如題3 1圖所示的二叉樹(shù)執(zhí)行函數(shù)Inorder后得到的輸出序列。(2)該函數(shù)的功能是什么?

33.下列函數(shù)實(shí)現(xiàn)直接插入排序，請(qǐng)?zhí)顚?xiě)適當(dāng)內(nèi)容，使其功能完整。

34.函數(shù)BinSearch實(shí)現(xiàn)二分查找，請(qǐng)回答下列問(wèn)題。(1)在空白處填寫(xiě)適當(dāng)內(nèi)容，使函數(shù)功能完整。(2)查找成功時(shí)函數(shù)的返回值是什么?(3)查找失敗時(shí)函數(shù)的返回值是什么?

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

41.已知：typedef struct node{       int data;       struct node *next;} LinkNode;typedef LinkNode *LinkList;請(qǐng)編寫(xiě)原型為int Listisequal(LinkList A，LinkList B)的函數(shù)，指針A、B分別指向兩個(gè)帶頭結(jié)點(diǎn)的單鏈表。函數(shù)功能是：若單鏈表A、B中全部對(duì)應(yīng)結(jié)點(diǎn)的data值相等，則返回1，否則返回0。