大學數據結構測試卷
一、選擇題
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中 ）
?。? 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分）
五、算法設計題
考查棧、樹和二叉樹、查找和排序的算法設計與填空。
【大學數據結構測試卷】相關文章：
1.小學畢業的測試卷
2.小學科學測試卷
3.期中測試卷參考
4.復習與提高測試卷
7.第八單元的測試卷
本文來源：http://www.nvnqwx.com/zuowen/dongtian/3452350.htm