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