13-14-1《資料結構》複習題
2013.12.
一、判斷題
1. 邊數很少的稀疏圖，適宜用鄰接矩陣表示。（ ×）
2. 對於同一組記錄，生成二叉搜尋樹的形態與插入記錄的次序無關。(×)
3. 有迴路的有向圖不能完成拓撲排序。( √ )
4. 對乙個連通圖進行一次深度優先搜尋可以遍訪圖中的所有頂點。( √ )
5. 乙個無向連通圖的生成樹是圖的極小的連通子圖。（√）
6. 雜湊查詢法中解決衝突問題的常用方法是除留餘數法。（ × ）
7. 在樹的儲存中，若使每個結點帶有指向雙親結點的指標，這為在演算法中尋找雙親結點帶來方便。(√)
8. 對判定樹進行中根遍歷，可得到結點的有序序列。（√ ）
9. 鏈式棧與順序棧相比, 乙個明顯的優點是通常不會出現棧滿的情況。（ √ ）
10. 用字元陣列儲存長度為n的字串，陣列長度至少為n+1。（√）
11. 在一棵具有n個結點的線索二叉樹中，每個結點的指標域可能指向子女結點，也可能作為線索，使之指向某一種遍歷次序的前驅或後繼結點，所有結點中作為線索使用的指標域共有n個。( × )
12. 對乙個連通圖進行一次深度優先搜尋可以遍訪圖中的所有頂點。( √ )
13. 邊數很少的稀疏圖，適宜用鄰接表表示。（ √ ）
14. 使用三元組表示稀疏矩陣中的非零元素能節省儲存空間。（ √ ）
15. 在一棵二叉樹中，假定每個結點只有左子女，沒有右子女，對它分別進行中序遍歷和後序遍歷，則具有相同的結果。( √ )
16. 演算法和程式都應具有下面一些特徵：有輸入，有輸出，確定性，有窮性，有效性。（×）
17. 對於一棵具有n個結點的任何二叉樹，進行前序、中序或後序的任一種次序遍歷的空間複雜度為o(log2n)。( × )
18. 如果有向圖中各個頂點的度都大於2，則該圖中必有迴路。( × )
19. 對乙個有向圖進行拓撲排序，一定可以將圖的所有頂點按其關鍵碼大小排列到乙個拓撲有序的序列中。(×)
20. 裝載因子是雜湊表的乙個重要引數，它反映了雜湊表的裝滿程度。( √ )
21. 演算法和程式原則上沒有區別，在討論資料結構時二者是通用的。( × )
22. 內部排序是指排序過程在記憶體中進行的排序。（ √ ）
23. 折半查詢所對應的判定樹，既是一棵二叉查詢樹，又是一棵理想平衡二叉樹。(√)
24. 迴圈鍊錶的結點與單鏈表的結點結構完全相同，只是結點間的連線方式不同。（ √ ）
25．理想情況下雜湊查詢的等概率查詢成功的平均查詢長度是o（1）。（ √ ）
二、單項選擇題
1. 向乙個棧頂指標為hs的鏈棧中插入乙個s所指結點時，則執行（ b ）。
>next=>next=hs->next;hs->next=s;
>next=hs;hs=>next=hs;hs=hs->next;
2. 已知8個資料元素為（34，76，45，18，26，54，92，65），按照依次插入結點的方法生成
一棵二叉排序樹後，最後兩層上的結點總數為（ b ） 。
a. 1 b.2c.3d.4
3. 在乙個鏈隊中，假設f和r分別為隊首和隊尾指標，則插入s所指結點的運算時（ b ）。
>next=s;f=s; >next=s;r=s;
>next=r;r=s; >next=f;f=s;
4. 某二叉樹的先序序列和後序序列正好相反，則該二叉樹一定是（ b ）的二叉樹。
a.空或只有乙個結點 b.高度等於其結點數
c.任一結點無左孩子 d.任一結點無右孩子
5. 在乙個順序表中，若表的第乙個元素的儲存位址是210，每乙個元素的長度為3，則第5個元素的儲存位址是（b ）。
a．219 b．222 c．225 d．228
6. 對關鍵字集合k=,從一棵空二叉樹開始逐個插入關鍵字，建立二叉排序樹，若希望得到的二叉排序樹的高度最小，應選用下列輸入序列（ b）。
a. 45，24，53，12，37，96，30b.37，24，12，30，53，45，96
c. 12，24，30，37，45，53，96d.30，24，12，37，45，96，53
7. 在迴圈雙鏈表的p所指接點之前插入s所指接點的操作是（ d ）。
> prior =s;s-> next=p;p-> prior->neft=s;s-> prior =p-> prior;
b. p-> prior =s;p-> prior -> next =s;s-> next =p;s-> prior =p-> prior;
> next =p;s-> prior =p-> prior;p-> prior =s;p-> prior -> next =s;
> next =p;s-> prior =p-> prior;p-> prior -> next =s;p-> prior =s;
8. 假設乙個有n個頂點和e條弧的有向圖用鄰接表表示,則刪除與某個頂點vi相關的所有弧的時間複雜度是（c）。
a．o(n) b．o(ec．o(n+e) d．o(n*e)
9. 已知含6個頂點(v0，v1，v2，v3，v4，v5)的無向圖的鄰接矩陣如圖所示，則從頂點v0出發進行深度優先遍歷可能得到的頂點訪問序列為（ a ）。
a.(v0，v1，v2，v5，v4，v3) b.(v0，v1，v2，v3，v4，v5)
c.(v0，v1，v5，v2，v3，v4) d.(v0，v1，v4，v5，v2，v3)
10. 非空的迴圈單鏈表head的尾結點（由p指向）滿足( c )。
a. p->next=null b. p=null
c. p->next=head
11. 在乙個鏈隊中，假設f和r分別為隊首和隊尾指標，則插入s所指結點的運算時（b）。
>next=s;f=s; >next=s;r=s;
>next=r;r=s; >next=f;f=s;
12. 查詢雜湊表，不會產生衝突的雜湊函式是（ b ）。
a．鏈位址法 b．直接位址法 c．除留餘數法 d．隨機探測法
13. 從乙個棧頂指標為hs的鏈棧中刪除乙個結點時，用x儲存被刪結點的值，則執行（ d ）。
>next;
>data;
>next;x=hs->data;
>data;hs=hs->next;
14. 高度為5的完全二叉樹中含有的結點數至少為（a ）。
a.16 b.17 c.31 d.32
15. 設有乙個10階的對稱矩陣a，採用壓縮儲存方式，以行序為主儲存，a1,1為第乙個元素，其儲存位址為1，每個元素佔1個位址空間，則a8,4的位址為（ b ）。
a.15 b.32 c.34 d.33
16. 假設以三元組表表示稀疏矩陣，則和下列三元組對應的稀疏矩陣是（ a ）。
17. 在乙個鏈隊中，假設f和r分別為隊首和隊尾指標，則刪除乙個結點的運算時（ c ）。
>next; >next;
>next; >next;
18. 用某種排序方法對關鍵字序列（25，84，21，47，15，27，68，35，20）進行排序時，序列的變化情況如下：
20，15，21，25，47，27，68，35，84
15，20，21，25，35，27，47，68，84
15，20，21，25，27，35，47，68，84
則所採用的排序方法是（d）。
a．選擇排序 b．希爾排序 c．歸併排序 d．快速排序
19. 已知在一棵度為3的樹中，度為2的結點數為4，度為3的結點數為3，則該樹中的葉子結點數為（ c ）。
a.5 b.8 c.11 d.18
20. 如果最常用的操作是提取第i個結點及其前驅，則採用（b ）儲存方式最節省時間。
a．單鏈表 b.順序表 c.迴圈鍊錶 d.雙鏈表
21. 若已知乙個棧的入棧序列是1，2，3，……..n，其輸出序列為p1,p2,p3,…….,pn,若p1=n,則pi為（ c ）。
d.不確定
22. 已知乙個順序儲存線性表，若第1個結點的位址d，第3個的位址是5d，則第n個結點的位址為（ a ）。
a．[2*(n-1)+1]*d b.2*(n-1)*d c.[2*(n-1)-1]*d d.(n+1)*d
23. 乙個n階對稱矩陣，如果以行或列為主序放入記憶體，則容量為（ d）。
c. (n+1)*(n+1)/2
24．查詢雜湊表，不會產生衝突的雜湊函式是（b ）。
a．鏈位址法 b．直接位址法 c．除留餘數法 d．隨機探測法
25. 有40個結點的完全二叉樹儲存在陣列ｔ[1..40]中，陣列ｔ中第乙個葉子結點是（ c ）。
a．ｔ[19] b．ｔ[20] c．ｔ[21] d．ｔ[22]
三、填空題
1. 由關鍵字序列（57,24,76,63,18,31,15）生成的一棵二叉排序樹，其等查詢概率情況下查詢成功的平均查詢長度為（ 18/7）。
資料結構複習題
1.資料結構可用三元式表示 d，s，p 其中 d是資料物件，s是d上的關係，p是對d的基本操作集。f 2 簡單地說,資料結構是帶有結構的資料元素的集合。t 3 判斷帶頭結點的非空迴圈單鏈表 頭指標為l 中指標p所指結點是最後乙個元素結點的條件是 p next l。t 4 線性表的鏈式儲存結構具有可直...
資料結構複習題
資料結構複習題 2004年6月 一 單項選擇題 1 鏈棧和順序棧相比，有乙個較明顯的優點是 a.通常不會出現棧滿的情況 b.通常不會出現棧空的情況 c.插入操作更加方便c.刪除操作更加方便 2 若待排序物件序列在排序前已按其排序碼遞增順序排序，則採用 方法比較次數最少。a 直接插入排序b 分劃交換排...
資料結構複習題
1 如果以鍊錶作為棧的儲存結構，則退棧操作時 a.必須判別棧是否滿 b.對棧不作任何判別 c.必須判別棧是否空 d.判別棧元素的型別 2 設陣列data 0.m 作為迴圈佇列sq的儲存空間，front為隊頭指標，rear為隊尾指標，則執行出隊操作的語句為 a.front front 1 b.fron...