第三套數(shù)據(jù)結(jié)構(gòu)與算法自測(cè)題

1、第三套 數(shù) 據(jù)結(jié) 構(gòu)自測(cè)題一、單項(xiàng)選擇題 (本大題共有 15小題，每小題 2分，共 30 分) (在每小題列出的四個(gè)選項(xiàng)中只有一個(gè)選項(xiàng)符合題目要求，請(qǐng)將正確選項(xiàng)前的 字母填在題后的括號(hào)內(nèi)。 )1. 數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，根據(jù)結(jié)點(diǎn)的關(guān)鍵字直接計(jì)算出該結(jié)點(diǎn)的存儲(chǔ)地址，這 種方法稱為A. 索引存儲(chǔ)方法 B. 順序存儲(chǔ)方法 C. 鏈?zhǔn)酱鎯?chǔ)方法 D. 散列存儲(chǔ)方法2. 在單鏈表中，存儲(chǔ)每個(gè)結(jié)點(diǎn)需要有兩個(gè)域，一個(gè)是數(shù)據(jù)域，另一個(gè)是指針域，它指向該 結(jié)點(diǎn)的A. 直接前趨 B. 直接后繼 C. 開始結(jié)點(diǎn) D. 終端結(jié)點(diǎn)3.4.其算法所需要的時(shí)間復(fù)雜度為2)需判斷別隊(duì)是否滿在已知頭指針的單鏈表中，要在其尾

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

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

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

5、. 在上三角矩陣中，它的 中的元素均為常數(shù) C。 上三角矩陣中的重復(fù)元素 C可共享一個(gè)存儲(chǔ)空間，其余的元素正好有 個(gè)(設(shè)上三角矩陣的階數(shù)為 n)。20. 高度為n的完全二叉數(shù)最多有 個(gè)結(jié)點(diǎn)；最少有 個(gè)結(jié)點(diǎn)。21. 對(duì)于一棵有n個(gè)結(jié)點(diǎn)的4度數(shù)，每個(gè)結(jié)點(diǎn)中有 4個(gè)指針，指向子結(jié)點(diǎn)，則樹中指向子結(jié)點(diǎn)的指針有 個(gè)，空指針有 個(gè)。22. 某二叉樹的前序遍歷序列為IJKIMN0,中序遍歷序列為 JLKNM0則后序遍歷序列為。由一棵二叉樹的后序序列和 可惟一確定這棵二叉樹。23. 堆排序的時(shí)間復(fù)雜度為 ;輔助存儲(chǔ)空間為 。24. 希爾排序?qū)儆谂判蚍椒?；堆排序?qū)儆谂判蚍椒ā?5. 在插入和選擇排序中，若初始數(shù)

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

7、排序樹。四、讀程序填空題(本大題共 4小題，每小題5分，共20分)31. 設(shè)串的堆存儲(chǔ)可用C描述為typedef structchar* ch;int legth;試填寫以它為基礎(chǔ)的求子串程序。#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. 完成下列中序列遍歷二叉的算法。注意，在遍歷中只用一個(gè)棧，而不用任何其他變量。 #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. 下列算法的功能是求出指定結(jié)點(diǎn)在給定的二叉排序樹中所在的層次。請(qǐng)完善該算法。 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)_;五、程序設(shè)計(jì)題(本大題有 3小題，可任選1題做，共10分。35. 編寫算法判斷以下二叉鏈表是否為二叉排序樹。36. 設(shè)計(jì)一個(gè)折半查找算法，在一組字符串中找出給定的字符串，假設(shè)