數(shù)據(jù)結(jié)構(gòu)試題答案

1、數(shù)據(jù)結(jié)構(gòu)試題答案一、單項選擇題（每題2分，共30分）1.若某線性表中最常用的操作是取第i個元素和找第i個元素的前趨元素，則采用（ ）存儲方式最節(jié)省時間。A) 單鏈表 B) 雙鏈表 C) 單向循環(huán)鏈表 D) 順序表2.串是任意有限個（ ）。A) 符號構(gòu)成的序列 B) 符號構(gòu)成的集合C) 字符構(gòu)成的序列 D) 字符構(gòu)成的集合3.設(shè)矩陣A的任一元素aij(1i,j10)滿足：aij0；(ij,1i,j10)aij=0； (inext=NULL。2.在單鏈表中，指針p所指結(jié)點為最后一個結(jié)點的條件是_。3.設(shè)一個鏈棧的棧頂指針是ls，棧中結(jié)點格式為 ，棧空的條件為_。如果棧不為空，則出棧操作為p=ls;

2、_;free(p)。4.已知一棵度為3的樹有2個度為1的結(jié)點，3個度為2的結(jié)點，4個度為3的結(jié)點，則該樹有_個葉子結(jié)點。5.樹有三種常用的存儲結(jié)構(gòu)，即孩子鏈表法，孩子兄弟鏈表法和_。6.n個頂點的連通圖的生成樹有_條邊。7.一個有向圖G中若有弧 、 和 ，則在圖G的拓撲序列中，頂點 的相對位置為_。8.設(shè)表中元素的初始狀態(tài)是按鍵值遞增的，分別用堆排序、快速排序、冒泡排序和歸并排序方法對其進行排序(按遞增順序)，_最省時間，_最費時間。9.下面是將鍵值為x的結(jié)點插入到二叉排序樹中的算法，請在劃線處填上適當?shù)膬?nèi)容。Typedef struct pnode int key;struct node *

3、 left, * right;Void search (int x; pnode t ) if (_)p = malloc (size);p-key=x;p-left=NULL;p-right=NULL;t=p;elseif (xkey) search (x,t-left)else _10.線性表的_的主要優(yōu)點是從表中任意結(jié)點出發(fā)都能訪問到所有結(jié)點。而使用_，可根據(jù)需要在前后兩個方向上方便地進行查找。三、應(yīng)用題（每題10分，共30分）1.在雙鏈表中，要在指針變量P所指結(jié)點之后插入一個新結(jié)點，請按順序?qū)懗霰匾乃惴ú襟E。(設(shè)：P所指結(jié)點不是鏈表的首尾結(jié)點，q是與p同類型的指針變量)2.已知待排序

4、文件各記錄的排序碼順序如下：72 73 71 23 94 16 05 68請列出快速排序過程中每一趟的排序結(jié)果。四、算法題(共12分)編寫算法，實現(xiàn)單鏈表上的逆置運算(說明：即將單鏈表中的元素次序反轉(zhuǎn))參考答案：一、單項選擇題（每題2分，共30分）1.D 2.C 3.D 4.C 5.D 6.D 7.A 8.B 9.D 10.C 11.D 12.C 13.A 14.B 15.C二、填空題（每空2分，共28分）1. r-next=s; 2. p-next=NULL;3. ls = = NULL; ls=ls-link。 4. 125. 雙親表示法 6. n-17. i,j,k 8. 冒泡排序，快速

5、排序9. t= =NULL，search（x,t-right）； 10.循環(huán)鏈表，雙向鏈表三、應(yīng)用題（每題10分，共30分）1new(q)；q.llink p；q.rlink p.rlink；p.rlink.llink q；p.rlink q。評分細則：按順序每對一個給2分，全對計10分。2各趟結(jié)果如下：68 05 71 23 16 72 94 7316 05 23 68 71 72 94 7305 16 23 68 71 72 94 7305 16 23 68 71 72 94 7305 16 23 68 71 72 94 7305 16 23 68 71 72 73 9405 16 23 68 71 72 73 94四算法題(共12分)void invert（ pointer h