第三套數據結構與算法自測題

1、第三套 數 據結 構自測題一、單項選擇題 (本大題共有 15小題，每小題 2分，共 30 分) (在每小題列出的四個選項中只有一個選項符合題目要求，請將正確選項前的 字母填在題后的括號內。 )1. 數據在計算機存儲器內表示時，根據結點的關鍵字直接計算出該結點的存儲地址，這 種方法稱為A. 索引存儲方法 B. 順序存儲方法 C. 鏈式存儲方法 D. 散列存儲方法2. 在單鏈表中，存儲每個結點需要有兩個域，一個是數據域，另一個是指針域，它指向該 結點的A. 直接前趨 B. 直接后繼 C. 開始結點 D. 終端結點3.4.其算法所需要的時間復雜度為2)需判斷別隊是否滿在已知頭指針的單鏈表中，要在其尾

2、部插入一新結點，A.O(1) B.(lgn) C.(n) D.O(n 在鏈接隊列執(zhí)行入隊操作，A. 需判斷別隊是否空 B.C. 限制在鏈表頭 p 進行5. 串函數 strcmp( “ bcde” , ” Bcde”A. 小于 0B. 等于 0D. 限制在鏈表尾 p 進行 )的返回值是C. 大于 0 D. - 16.7.廣義表( )的長度為A. 0B. 1 C. 2 D.某二叉樹的后序遍歷序列為 dabec, 中序遍歷序列為不確定debac, 則前序序列遍歷為A.acbed B.decab C.deabc D.cedba8. 含有 n 個結點的二叉樹用二叉鏈表表示時，空鏈域個數為A.n-1B.n

3、C.n+1D.n+29. 在一個圖中，所有頂點的度數之和與圖的邊數的比是A.1:2B.1:1C.2:1D.4:110. n 個頂點的無向圖若采用鄰接矩陣存儲，則該矩陣的大小是22A.nB.(n-1)2C.n+1 D.n211. 下述幾種排序方法中，要求內存量最大的是A. 插入排序 B. 快速排序 C. 歸并排序 D. 選擇排序12. 對 n 個不同的排序碼進行冒泡排序，在元素無序的情況下比較的次數為A.n+1 B.nC.n-1D.n(n-1)/213. 對線性表示進行二分查找時，要求線性表必須A. 以順序方式存儲B. 以鏈接方式存儲C. 以順序方式存儲，且結點按關鍵字有序排列D. 以鏈接方式存

4、儲，且結點按關鍵字有序排列14. 下列方法中，不穩(wěn)定的排序是A. 直接插入排序 B. 冒泡排序 C. 堆排序 D. 歸并排序15. 在索引非順序文件中，建立的索引表是A. 稠密索引 B. 稀疏索引 C. 多級索引 D. 鏈接索引二、填空題(本大題共 10小題，每小題 2分，共 20 分)16. 順序表的存儲密度為 ，而鏈表的存儲密度為 。17. 在有 n 個元素的鏈隊列中，入隊和出隊操作的時間復雜度為 和 。18. 在串運 算中 ， strcmp( “abc”,”abef”) 的值; 順 序串上的串定 位運 算NaiveStr- Match( “acaabc” , ” aab”)的值為 。19

5、. 在上三角矩陣中，它的 中的元素均為常數 C。 上三角矩陣中的重復元素 C可共享一個存儲空間，其余的元素正好有 個(設上三角矩陣的階數為 n)。20. 高度為n的完全二叉數最多有 個結點；最少有 個結點。21. 對于一棵有n個結點的4度數，每個結點中有 4個指針，指向子結點，則樹中指向子結點的指針有 個，空指針有 個。22. 某二叉樹的前序遍歷序列為IJKIMN0,中序遍歷序列為 JLKNM0則后序遍歷序列為。由一棵二叉樹的后序序列和 可惟一確定這棵二叉樹。23. 堆排序的時間復雜度為 ;輔助存儲空間為 。24. 希爾排序屬于排序方法；堆排序屬于排序方法。25. 在插入和選擇排序中，若初始數

6、據基本正序，則選用 ;若初始數據基本反序，則選用。三簡答題(本大題共5小題，每小題4分，共20分)26. 順序隊列中的假上溢用什么方法解決？請作簡短的解釋。27. 試寫出下列廣義表運算的結果：tail(a,b),(c,d)。28. 分別畫出滿足下列條件的所有二叉樹：(1) 前序序列和中序序列均為ABCDE;(2) 前序序列為ABCDE,并且與其對應的二叉樹高度為5。29. 什么是堆？請寫出對應于序列10，20，7，75，41，67，3，9，30，45的初始堆(堆頂元素取最小值)。30. 從一個空的二叉排序樹開始，將以下關鍵字25，13，15，34，7，20，37依次插入，請畫出全部插入后的二叉

7、排序樹。四、讀程序填空題(本大題共 4小題，每小題5分，共20分)31. 設串的堆存儲可用C描述為typedef structchar* ch;int legth;試填寫以它為基礎的求子串程序。#defi ne error #defi ng ok 1int substingHstring&sub,Hstring S, int pos,int lengthif(poss.legth|lenptr.tp)dep=_(4);if(depmax)_(5);return max+1;33. 完成下列中序列遍歷二叉的算法。注意，在遍歷中只用一個棧，而不用任何其他變量。 #define max 100 ty

8、pedef struct tnode elemtype data;struct tnode * lchild,* rchild; tnode;typedef struct stack tnode * elemmax;int top;stack;void inorder(tnode * bt) stack s; s.top=0;_(1);dowhile(_(_2)s.elems.top+=s.elems.top 1 1child if(s.top1)_(3);printf(s.elems.top 1=_(4);while(!(s.top 1&s.elems.top 1= =null); (5)_;34. 下列算法的功能是求出指定結點在給定的二叉排序樹中所在的層次。請完善該算法。 Void leve1(BSTree root,p)int leve = o;if (!root)(1)；elselevel +;while(root-key!=p- key) if (root- keyp key) _J2);else(3)_;leve1 +;(4)_;五、程序設計題(本大題有 3小題，可任選1題做，共10分。35. 編寫算法判斷以下二叉鏈表是否為二叉排序樹。36. 設計一個折半查找算法，在一組字符串中找出給定的字符串，假設