計算機技能測試題答案
一、選擇題(30分)
1. 設一組權值集合W={2，3，4，5，6}，則由該權值集合構造的哈夫曼樹中帶權路徑長度之和為( )。
(A) 20 (B) 30 (C) 40 (D) 45
2.執行一趟快速排序能夠得到的序列是( )。
(A) [41，12，34，45，27] 55 [72，63]
(B) [45，34，12，41] 55 [72，63，27]
(C) [63，12，34，45，27] 55 [41，72]
(D) [12，27，45，41] 55 [34，63，72]
3.設一條單鏈表的頭指標變數為head且該連結串列沒有頭結點，則其判空條件是( )。
(A) head==0 (B) head->next==0
(C) head->next==head (D) head!=0
4.時間複雜度不受資料初始狀態影響而恆為O(nlog2n)的是( )。
(A) 堆排序 (B) 氣泡排序 (C) 希爾排序 (D) 快速排序
5.設二元樹的先序遍歷序列和後序遍歷序列正好相反，則該二元樹滿足的條件是( )。
(A) 空或只有一個結點 (B) 高度等於其結點數
(C) 任一結點無左孩子 (D) 任一結點無右孩子
6.一趟排序結束後不一定能夠選出一個元素放在其最終位置上的是( )。
(A) 堆排序 (B) 氣泡排序 (C) 快速排序 (D) 希爾排序
7.設某棵三叉樹中有40個結點，則該三叉樹的最小高度為( )。
(A) 3 (B) 4 (C) 5 (D) 6
8.順序查詢不論在順序線性表中還是在鏈式線性表中的時間複雜度為( )。
(A) O(n) (B) O(n2) (C) O(n1/2) (D) O(1og2n)
9.二路歸併排序的時間複雜度為( )。
(A) O(n) (B) O(n2) (C) O(nlog2n) (D) O(1og2n)
10. 深度為k的完全二元樹中最少有( )個結點。
(A) 2k-1-1 (B) 2k-1 (C) 2k-1+1 (D) 2k-1
11.設指標變數front表示鏈式佇列的隊頭指標，指標變數rear表示鏈式佇列的.隊尾指標，指標變數s指向將要入佇列的結點X，則入佇列的操作序列為( )。
(A) front->next=s;front=s; (B) s->next=rear;rear=s;
(C) rear->next=s;rear=s; (D) s->next=front;front=s;
12.設某無向圖中有n個頂點e條邊，則建立該圖鄰接表的時間複雜度為( )。
(A) O(n+e) (B) O(n2) (C) O(ne) (D) O(n3)
13.設某哈夫曼樹中有199個結點，則該哈夫曼樹中有( )個葉子結點。
(A) 99 (B) 100 (C) 101 (D) 102
14.設二叉排序樹上有n個結點，則在二叉排序樹上查詢結點的平均時間複雜度為( )。
(A) O(n) (B) O(n2) (C) O(nlog2n) (D) O(1og2n)
15.設用鄰接矩陣A表示有向圖G的儲存結構，則有向圖G中頂點i的入度為( )。
(A) 第i行非0元素的個數之和 (B) 第i列非0元素的個數之和
(C) 第i行0元素的個數之和 (D) 第i列0元素的個數之和
二、判斷題(20分)
1.呼叫一次深度優先遍歷可以訪問到圖中的所有頂點。( )
2.分塊查詢的平均查詢長度不僅與索引表的長度有關，而且與塊的長度有關。( )
3.氣泡排序在初始關鍵字序列為逆序的情況下執行的交換次數最多。( )
4.滿二元樹一定是完全二元樹，完全二元樹不一定是滿二元樹。( )
5.設一棵二元樹的先序序列和後序序列，則能夠唯一確定出該二元樹的形狀。( )
6.層次遍歷初始堆可以得到一個有序的序列。( )
7.設一棵樹T可以轉化成二元樹BT，則二元樹BT中一定沒有右子樹。( )
8.線性表的順序儲存結構比鏈式儲存結構更好。( )
9.中序遍歷二叉排序樹可以得到一個有序的序列。( )
10.快速排序是排序演算法中平均效能最好的一種排序。( )
三、填空題(30分)
(i=1，t=1，s=0;i<=n;i++) {t=t*i;s=s+t;}的時間複雜度為_________。
2.設指標變數p指向單鏈表中結點A，指標變數s指向被cha入的新結點X，則進行插入操作的語句序列為__________________________(設結點的指標域為next)。
3.設有向圖G的二元組形式表示為G =(D，R)，D={1，2，3，4，5}，R={r}，r={<1,2>，<2,4>，<4,5>，<1,3>，<3,2>，<3,5>}，則給出該圖的一種拓撲排序序列__________。
4.設無向圖G中有n個頂點，則該無向圖中每個頂點的度數最多是_________。
5.設二元樹中度數為0的結點數為50，度數為1的結點數為30，則該二元樹中總共有_______個結點數。
6.設F和R分別表示順序迴圈佇列的頭指標和尾指標，則判斷該迴圈佇列為空的條件為_____________________。
7.設二元樹中結點的兩個指標域分別為lchild和rchild，則判斷指標變數p所指向的結點為葉子結點的條件是_____________________________________________。
8.簡單選擇排序和直接插入排序演算法的平均時間複雜度為___________。
9.快速排序演算法的空間複雜度平均情況下為__________，最壞的情況下為__________。
10.散列表中解決衝突的兩種方法是_____________和_____________。
四、演算法設計題(20分)
1.1. 設計在順序有序表中實現二分查詢的演算法。
2.2. 設計判斷二元樹是否為二叉排序樹的演算法。
3.3. 在鏈式儲存結構上設計直接插入排序演算法
