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