大學數據結構測試卷

一、選擇題

1. 下面關於算法説法錯誤的是（ ） A．算法最終必須由計算機程序實現

B.為解決某問題的算法同為該問題編寫的程序含義是相同的

C. 算法的可行性是指指令不能有二義性 D. 以上幾個都是錯誤的

2. 下述哪一條是順序存儲結構的優點？（ A．插入運算方便 B．存儲密度大 C．刪除運算方便

D．可方便地用於各種邏輯結構的存儲表示

3. 線性表是具有n個（ ）的有限序列（n>0）。

A．表元素 B．字符 C．數據項 D. 數據元素

4. 若某線性表最常用的操作是存取任一指定序號的`元素和在最後進行插入和刪除運算，則利用（ ）存儲方式最節省時間。

A．順序表 B．雙鏈表 C．帶頭結點的雙循環鏈表 D．單循環鏈表 5. 下列排序算法中，在每一趟都能選出一個元素放到其最終位置上，並且其時間性能受數據初始特性影響的是：（ ）

A. 直接插入排序 B. 快速排序 C. 直接選擇排序 D. 堆排序 6. 輸入序列為ABC，可以變為CBA時，經過的棧操作為（ ）

A. push,pop,push,pop,push,pop B. push,push,push,pop,pop,pop C. push,push,pop,pop,push,pop D. push,pop,push,push,pop,pop 7. 設有兩個串p和q，其中q是p的子串，求q在p中首次出現的位置的算法稱為（ ）

A．求子串 B．聯接 C．匹配 D．求串長

8. 二叉樹的先序遍歷和中序遍歷如下： 先序遍歷：EFHIGJK；中序遍歷: HFIEJKG 。該二叉樹根的右子樹的根是： （ ）

A、 E B、 F C、 G D、 H

9. 對於順序存儲的線性表，訪問結點和增加、刪除結點的時間複雜度為（ ） A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1) 10. 已知一算術表達式的中綴形式為 A+B*C-D/E，後綴形式為ABC*+DE/-，其前綴形式為( )

A．-A+B*C/DE B. -A+B*CD/E C．-+*ABC/DE D. -+A*BC/DE

A,並已0右孩子的平衡因子為1,則應作（ ）型調整以使4，其中度為1，2，3和4的結點個數分別為4，2，1，1 則T中 ）

．6 C．7 D．8 D ） ．3 C．4 D．

14. 設如左圖所示，在下面的5個序列中，符合深度優先遍歷的序列有多少？（ ）

a e b d f c a c f d e b

a e d f c b a e f d c b a e f d b c

A．5個 B．4個 C．3個 D．2個

二、填空題

1. 在下面的程序段中，對ｘ的賦值語句的頻度為 _ _（表示為n的函數） For(i=1;i<=n;i++)

For(j=1;j<=i;j++) X+=3;

2. 循環隊列的引入，目的是為了克服 ____________ ____ 3. 一個棧的輸入序列是：1，2，3則不可能的棧輸出序列是_______________ 4. 如果結點A有 3個兄弟，而且B是A的雙親，則B的度是_______________。 5. 當使用監視哨順序查找n個元素的順序表時，若查找失敗，則比較關鍵字的次數為________________

6. 設一棵完全二叉樹具有1000個結點，則它有________個葉子結點，有________個度為2的結點。

7. N個頂點的連通圖的生成樹含有 _條邊

8. 已知一無向圖G=（V，E），其中V={a,b,c,d,e } E={(a,b),(a,d),(a,c),(d,c),(b,e)}現用某一種圖遍歷方法從頂點a開始遍歷圖，得到的序列為abecd，則採用的是_______________遍歷方法

9.分別採用堆排序，快速排序，冒泡排序和歸併排序，對初態為有序的表，則最省時間的是 ___算法，最費時間的是 ____算法。 10.若不考慮基數排序，則在排序過程中，主要進行的兩種基本操作是關鍵字的 _______和記錄的 ____ 。

三、應用題

1.考查樹和二叉樹的應用（本題8分）

2.考查圖的方面的應用（本題8分）

3.考查查找方面的應用（本題8分）

四、計算題

1.考查排序方面的應用

2.考查哈希表的應用（本題8分）

五、算法設計題

考查棧、樹和二叉樹、查找和排序的算法設計與填空。