- 相關(guān)推薦
數據結構試題答案
一、單項選擇題（每題2分，共30分）
1.若某線(xiàn)性表中最常用的操作是取第i個(gè)元素和找第i個(gè)元素的前趨元素，則采用（ ）存儲方式最節省時(shí)間。
A) 單鏈表 B) 雙鏈表 C) 單向循環(huán)鏈表 D) 順序表
2.串是任意有限個(gè)（ ）。
A) 符號構成的序列 B) 符號構成的集合
C) 字符構成的序列 D) 字符構成的集合
3.設矩陣A的任一元素aij(1≤i,j≤10)滿(mǎn)足：
aij≠0；(i≥j,1≤i,j≤10)
aij=0； (i<j,1≤i,j≤10)
現將A的所有非0元素以行序為主序存放在首地址為2000的存儲區域中，每個(gè)元素占有4個(gè)單元，則元素A[9,5]的首地址為（ ）。
A) 2340 B) 2336 C) 2164 D) 2160
4.如果以鏈表作為棧的存儲結果，則出棧操作時(shí)（ ）。
A) 必須判別棧是否為滿(mǎn) B) 對棧不作任何判別
C) 必須判別棧是否為空 D) 判別棧元素的類(lèi)型
5.設數組Data[0..m]作為循環(huán)隊列SQ的存儲空間，front為隊頭指針，rear為隊尾指針,則執行出隊操作的語(yǔ)句為（ ）。
A) front = front+1 B) front = (front+1) % m
C) rear = (rear+1) % m D) front = (front+1) % (m+1)
6.深度為6(根的層次為1)的二叉樹(shù)至多有（ ）結點(diǎn)。
A) 64 B) 32 C) 31 D) 63
7.將含100個(gè)結點(diǎn)的完全二叉樹(shù)從根這一層開(kāi)始，每層上從左到右依次堆結點(diǎn)編號，根結點(diǎn)的編號為1。編號為49的結點(diǎn)X的雙親的編號為（ ）。
A) 24 B) 25 C) 23 D) 無(wú)法確定
8.設有一個(gè)無(wú)向圖 和 ，如果 為 的生成樹(shù)，則下面不正確的說(shuō)法是（ ）。
A) 為 的子圖 B) 為 的連通分量
C) 為 的.極小連通子圖且 D) 為 的一個(gè)無(wú)環(huán)子圖
9.用線(xiàn)性探測法查找閉散列表，可能要探測多個(gè)散列地址，這些位置上的鍵值（ ）。
A) 一定都是同義詞 B) 一定都不是同義詞
C) 多相同 D) 不一定都是同義詞
10.二分查找要求被查找的表是（ ）。
A) 鍵值有序的鏈接表 B) 鏈接表但鍵值不一定有序
C) 鍵值有序的順序表 D) 順序表但鍵值不一定有序
11.當初始序列已經(jīng)按鍵值有序，用直接插入算法對其進(jìn)行排序，需要循環(huán)的次數為（ ）。
A) B) C) D) n－1
12.堆是一個(gè)鍵值序列 ,對 ，滿(mǎn)足（ ）。
A) B)
C) 且 ( ) D) 或 ( )
13.使用雙向鏈表存儲數據，其優(yōu)點(diǎn)是可以（ ）。
A) 提高檢索速度 B) 很方便地插入和刪除數據
C) 節約存儲空間 D) 很快回收存儲空間
14.設計一個(gè)判別表達式中左右括號是否配對出現地算法，采用（ ）數據結構最佳。
A) 線(xiàn)性表地順序存儲結構 B) 棧
C) 隊列 D) 線(xiàn)性表達的鏈式存儲結構
15.設深度為k的二叉樹(shù)上只有度為0和2的結點(diǎn)，則此類(lèi)二叉樹(shù)中所含的結點(diǎn)數至少為（ ）。
A) k + 1 B) 2k C) 2k - 1 D) 2k + 1
二、填空題（每空2分，共28分）
1.設r指向單鏈表的最后一個(gè)結點(diǎn)，要在最后一個(gè)結點(diǎn)之后插入s所指的結點(diǎn)，需執行的三條語(yǔ)句是_____________________________________________r=s;r->next=NULL。
2.在單鏈表中，指針p所指結點(diǎn)為最后一個(gè)結點(diǎn)的條件是___________________。
3.設一個(gè)鏈棧的棧頂指針是ls，棧中結點(diǎn)格式為 ，�？盏臈l件為_(kāi)____________。如果棧不為空，則出棧操作為p=ls;______________;free(p)。
4.已知一棵度為3的樹(shù)有2個(gè)度為1的結點(diǎn)，3個(gè)度為2的結點(diǎn)，4個(gè)度為3的結點(diǎn)，則該樹(shù)有________個(gè)葉子結點(diǎn)。
5.樹(shù)有三種常用的存儲結構，即孩子鏈表法，孩子兄弟鏈表法和____________。
6.n個(gè)頂點(diǎn)的連通圖的生成樹(shù)有__________條邊。
7.一個(gè)有向圖G中若有弧 、 和 ，則在圖G的拓撲序列中，頂點(diǎn) 的相對位置為_(kāi)__________。
8.設表中元素的初始狀態(tài)是按鍵值遞增的，分別用堆排序、快速排序、冒泡排序和歸并排序方法對其進(jìn)行排序(按遞增順序)，________最省時(shí)間，__________最費時(shí)間。
9.下面是將鍵值為x的結點(diǎn)插入到二叉排序樹(shù)中的算法，請在劃線(xiàn)處填上適當的內容。
Typedef struct pnode
{ int key;
struct node * left, * right;
}
Void search (int x; pnode t )
{ if (_____________)
{p = malloc (size);
p->key=x;p->left=NULL;
p->right=NULL;
t=p;
}
else
if (xkey) search (x,t->left)
else _________________
}
10.線(xiàn)性表的____________的主要優(yōu)點(diǎn)是從表中任意結點(diǎn)出發(fā)都能訪(fǎng)問(wèn)到所有結點(diǎn)。而使用____________，可根據需要在前后兩個(gè)方向上方便地進(jìn)行查找。
三、應用題（每題10分，共30分）
1.在雙鏈表中，要在指針變量P所指結點(diǎn)之后插入一個(gè)新結點(diǎn)，請按順序寫(xiě)出必要的算法步驟。(設：P所指結點(diǎn)不是鏈表的首尾結點(diǎn)，q是與p同類(lèi)型的指針變量)
2.已知待排序文件各記錄的排序碼順序如下：
72 73 71 23 94 16 05 68
請列出快速排序過(guò)程中每一趟的排序結果。
四、算法題(共12分)
編寫(xiě)算法，實(shí)現單鏈表上的逆置運算(說(shuō)明：即將單鏈表中的元素次序反轉)
參考答案：
一、單項選擇題（每題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. 12
5. 雙親表示法 6. n-1
7. i,j,k 8. 冒泡排序，快速排序
9. t= =NULL，search（x,t->right）； 10.循環(huán)鏈表，雙向鏈表
三、應用題（每題10分，共30分）
1．new(q)；
q↑.llink ← p；
q↑.rlink ← p↑.rlink；
p↑.rlink↑.llink ← q；
p↑.rlink ← q。
評分細則：按順序每對一個(gè)給2分，全對計10分。
2．各趟結果如下：
[68 05 71 23 16] 72 [94 73]
[16 05 23] 68 [71] 72 [94 73]
[05] 16 [23] 68 [71] 72 [94 73]
05 16 [23] 68 [71] 72 [94 73]
05 16 23 68 71 72 [94 73]
05 16 23 68 71 72 [73] 94
05 16 23 68 71 72 73 94
四．算法題(共12分)
void invert（ pointer head）
{p=NULL;
while ( head<>NULL)
{u=head;
head=head->next;
u->next=p;
p=u;
}
head=p;
}