一、選擇題
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. 在下面的程序段中,對x的賦值語句的頻度爲 _ _(表示爲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分)
五、算法設計題
考查棧、樹和二叉樹、查找和排序的算法設計與填空。