武大數據結構試題

⑴ 數據結構本科試題

6 、A （至多有2^(k-1)個節點。k為深度）
7、A（簡單排一下，就發現父節點就是編號/2）
8、B（隊列先進先出）
9、B（
結點的權：在一些應用中，賦予樹中結點的一個 有某種意義的實數。
結點的帶權路徑長度：結點到樹根之間的路徑長度與該結點上權的乘積。
樹的帶權路徑長度：為樹中所有葉結點的帶權路徑長度之和）
10、B（先訪問根節點、再訪問左子樹，最後右子樹）
11、C（首先肯定是線性結構，排除D，其次，隊列和棧，順序存儲、鏈式存儲皆可。A、B顯然不對）

⑵ 求下面數據結構試題的答案...

一．

1,復雜性2.線性結構非線性結構

3．可以按序號隨機存取4.數據元素

5.後進先出6.n7.只能在隊頭進行

9.長度1深度1

10-+A*BC/DE

11

12頂點Vp到頂點Vq之間的路徑是指定的序列Vp，Vi1，Vi2•••Vim，Vq。

13n（n-2）/214n—1152n—1

17一種存儲結構

19可以從表中任意結點開始遍歷整個鏈表；只用一個指向尾結點的指針對鏈表頭、尾進行操作，提高了效率。

20棧是僅限制在表的一端進行插入和刪除的運算的線性表，是一種操作受限的線性表。

二．

1演算法的時間復雜度和空間復雜度

2.隊列

3.

4嵌套集合表示法，廣義表表示法，凹入表示法

5.456.S(1)X(1)S(2)S(3)X(3)S(4)X(4)X(2)

7（1）O（nˆ2）

（2）O（nˆ2）

8.

哈夫曼樹：

WPL=2*5+4*5+5*4+16*3+8*3+7*3+30=173

9.鄰接矩陣：

鄰接表：

10.二叉樹：

前序：ABCEFD

中序：BEFCDA

後序：FEDCBA

⑶ 數據結構 試題 求答案

首先，定義一個數組存放上表所有數據（共46個數據）。設這個數組為A(46)
然後按下列步驟進行排序計算
1）A(1)≤A(2)？是轉第2步，否則

A(1)<-->A(2)（即A(1)、A(2)值互換，實現A(1)≤A(2)）
2）A(2)≤A(3)？是（說明A(1)≤A(2)≤A(3)）轉第3步，否則

A(2)<-->A(3)（實現A(2)≤A(3)）

A(1)≤A(2)？是（說明A(1)≤A(2)≤A(3)）轉第3步，否則

A(1)<-->A(2)（實現A(1)≤A(2)≤A(3)）
3）A(3)≤A(4)？是（說明A(1)≤A(2)≤A(3)≤A(4)）轉第4步，否則

A(3)<-->A(4)（實現A(3)≤A(4)）

A(3)≥A(2)？是（說明A(1)≤A(2)≤A(3)≤A(4)）轉第4步，否則

A(2)<-->A(3)（實現A(2)≤A(3)）

A(2)≥A(1)？是（說明A(1)≤A(2)≤A(3)≤A(4)）轉第4步，否則

A(1)<-->A(2)（實現A(1)≤A(2)≤A(3)≤A(4)）
4）A(4)≤A(5)？是（說明A(1)≤A(2)≤A(3)≤A(4)≤A(5)）轉第5步，否則

A(4)<-->A(5)（實現A(4)≤A(5)）

A(4)≥A(3)？是（說明A(1)≤A(2)≤A(3)≤A(4)≤A(5)）轉第5步，否則

A(3)<-->A(4)（實現A(3)≤A(4)）

A(3)≥A(4)？是（說明A(1)≤A(2)≤A(3)≤A(4)≤A(5)）轉第5步，否則

A(2)<-->A(3)（實現A(2)≤A(3)）

A(2)≥A(1)？是（說明A(1)≤A(2)≤A(3)≤A(4)≤A(5)）轉第5步，否則

A(1)<-->A(2)（實現A(1)≤A(2)≤A(3)≤A(4)≤A(5)）
5）A(5)≤A(6)？是轉第6步，否則

A(5)<-->A(6)

A(5)≥A(4)？是轉第6步，否則

A(4)<-->A(5)

A(4)≥A(3)？是轉第6步，否則

A(3)<-->A(4)

A(3)≥A(2)？是轉第6步，否則

A(2)<-->A(3)

A(2)≥A(1)？是轉第6步，否則

A(1)<-->A(2)
6）......

按如上思路進行下去，即可實現A(46)數組按升序重排。

由上述1）~5）步的比較過程可以看出，每執行一步，就完成一次若干組數據從小到大的排序，且執行比較時，總是從已排好序的最大那個數開始，從大到小進行邊比較邊調整次序。另一個特點是，越到後面，每一步中需要比較與調整的數據越多。

⑷ 數據結構概論 試題求解

二、判斷對錯題：（每題2分，共40分，正確的選A，錯誤的選B）
1. 數據的邏輯結構是指數據的各數據項之間的邏輯關系。B
2. 順序存儲方式插入和刪除時效率太低，因此它不如鏈式存儲方式好。B
3. 取線性表的第i個元素的時間同i的大小有關。B
4. 兩個棧共用靜態存儲空間，對頭使用也存在空間溢出問題。A
5. 二叉樹是一般樹的特殊情形。B
6. 無向圖的鄰接矩陣一定是對稱矩陣，有向圖的鄰接矩陣一定是非對稱矩陣。B
7. 在n個結點的無向圖中，若邊數大於n-1,則該圖必是連通圖。B
8. 就平均查找長度而言，分塊查找最小，折半查找次之，順序查找最大。B(折半最小）
9. Hash表的平均查找長度與處理沖突的方法無關。B
10. 用鄰接矩陣表示圖時，矩陣元素的個數與邊的條數有關.A
11. 樹最適合用來表示元素之間具有分支層次關系的數據。A
12. 圖型結構中元素之間存在1對多關系。A
13. 哈夫曼樹度為1的結點數等於度為2和0的結點數之差。
14. 兩個串相等的充分必要條件是分配的存儲空間一樣。B
15. 已知指針P指向鍵表L的某結點，執行語句P=P->next不會刪除該鏈表中的結點。A
16. 在鏈隊列中，即使不設置尾指針也能進行入隊操作。A
17. 若圖G的最小生成樹不唯一，則G的邊數一定多於n-1，並且權值最小的邊有多條（其中n為G的頂點數）。A
18. 直接選擇排序演算法在最好情況下的時間復雜度為O（N），N是數據元素的個數。B
19. 排序演算法中的比較次數與初始元素序列的排列無關。B
20. 記錄是數據處理的最小單位。B
21. 程序一定是演算法。B
22. 在順序存儲結構中，有時也存儲數據結構中元素之間的關系。A
23. 數據的邏輯結構說明數據元素之間的順序關系,它依賴於計算機的儲存結構.B
24. 循環鏈表不是線性表.B
25. 順序存儲結構通過數據元素存儲的位置表示元素之間的關系。A
26. 隊列是一種插入與刪除操作分別在表的兩端進行的線性表，是一種先進後出型結構。B
27. 循環隊列的引入，目的是為了克服假溢出。A
28. 完全二叉樹一定存在度為1的結點B。
29. 對一棵二叉樹進行層次遍歷時，應藉助於一個棧。B
30. 二叉樹只能用二叉鏈表表示。B
31. 樹中的結點和圖中的頂點就是指數據結構中的數據元素。A
32. 有向圖中頂點V的度等於其鄰接矩陣中第V行中的1的個數。B
33. 帶權的有向圖和無向圖，只能使用鄰接表存儲形式來存儲它。B
34. 適用於折半查找的表的存儲方式及元素排列要求是：鏈接方式存儲，元素無序 。B
35. 當採用分快查找時，數據的組織方式為數據分成若干塊，每塊內數據有序。B
36. 散列函數越復雜越好，因為這樣隨機性好，沖突概率小。B
37. 冒泡排序和快速排序都是基於交換兩個逆序元素的排序方法。A
38. 在排序過程中，主要進行的兩種基本操作是關鍵字的比較和記錄的移動。A
39. 鏈表中的頭結點僅起到標識的作用。B
40. 對順序表上的插入、刪除演算法的時間復雜性分析來說，通常以結點移動量為標准分析。A
41. 為了很方便的插入和刪除數據，可以使用雙向鏈表存放數據。A
42. 棧是實現過程和函數等子程序所必需的結構。A
43. 在執行簡單的串匹配演算法時，最壞的情況為每次匹配比較不等的字元出現的位置均為模式串的最末字元。A
44. 在單鏈表中，指針p指向元素為x的結點，實現"刪除x的後繼"的語句是p->next=p->next->next;B
45. 完全二叉樹一定存在度為1的結點。B
46. 連通圖上各邊權值均不相同，則該圖的最小生成樹是唯一的。A
47. 通常將鏈串的結點大小設置為大於1是為了提高存儲密度。
48. 排序的穩定性是指排序演算法中的比較次數保持不變，且演算法能夠終止。B
49. 快速排序的速度在所有排序方法中為最快,而且所需附加空間也最少。B
50. 鄰接多重表是無向圖和有向圖的鏈式存儲結構。B
51. 強連通圖的各頂點間均可達。A
52. 度為二的樹就是二叉樹。B
大概都對吧，個別沒確定答案，自己判斷了下