數(shù)據(jù)結(jié)構(gòu)各章作業(yè)題目

1、第一章作業(yè)一、 選擇題1. 被計(jì)算機(jī)加工的數(shù)據(jù)元素不是孤立的，它們彼此之間一般存在某種關(guān)系，通常把數(shù)據(jù)元素之間的這種關(guān)系稱為( )。A. 規(guī)則B. 結(jié)構(gòu)C. 集合D. 運(yùn)算2. 在Data_Structure=(D,S)中，D是( )的有限集合。A. 數(shù)據(jù)元素B. 算法C. 數(shù)據(jù)操作D.數(shù)據(jù)對(duì)象3. 計(jì)算機(jī)所處理的數(shù)據(jù)一般具有某種關(guān)系，這是指( )之間存在的某種關(guān)系。A. 數(shù)據(jù)與數(shù)據(jù)B. 數(shù)據(jù)元素與數(shù)據(jù)元素C. 元素內(nèi)數(shù)據(jù)項(xiàng)與數(shù)據(jù)項(xiàng)D. 數(shù)據(jù)文件內(nèi)記錄與記錄4. 順序存儲(chǔ)表示中數(shù)據(jù)元素之間的邏輯關(guān)系是由( )表示的。A. 指針B. 邏輯順序C. 存儲(chǔ)位置D. 問題上下文5. 鏈接存儲(chǔ)表示中數(shù)據(jù)

2、元素之間的邏輯關(guān)系是由( )表示的。A. 指針B. 邏輯順序C. 存儲(chǔ)位置D. 問題上下文6. 從邏輯上可將數(shù)據(jù)結(jié)構(gòu)分為( )。A. 動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B. 緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C. 內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)D. 線性結(jié)構(gòu)和非線性結(jié)構(gòu)7. 以下選項(xiàng)屬于線性結(jié)構(gòu)的是( )。A. 廣義表B. 二叉樹C. 串D. 稀疏數(shù)組8. 以下選項(xiàng)屬于非線性結(jié)構(gòu)的是( )。A. 廣義表B. 隊(duì)列C. 優(yōu)先隊(duì)列D. 棧9. 以下屬于邏輯結(jié)構(gòu)的是( )A. 順序表B. 散列表C. 有序表D. 單鏈表10. 一個(gè)完整的算法應(yīng)該具有( )等特性。A. 可執(zhí)行性、可修改性和可維護(hù)性B. 可行性、確定性和有窮性C. 確定性、有窮

3、性和可靠性D. 正確性、可讀性和有效性11. 若一個(gè)問題既可以用迭代方法也可以用遞歸方法求解，則( )的方法具有更高的時(shí)空效率。A. 迭代B. 遞歸C. 先遞歸后迭代D. 先迭代后遞歸12. 一個(gè)遞歸算法必須包括( )A. 遞歸部分B. 終止條件和遞歸部分C. 迭代部分D. 終止條件和迭代部分13. 算法的時(shí)間復(fù)雜度與( )有關(guān)。A. 問題規(guī)模B. 源程序長(zhǎng)度C. 計(jì)算機(jī)硬件運(yùn)行速度D. 編譯后執(zhí)行程序的質(zhì)量二、指出下列各算法的功能并求出其時(shí)間復(fù)雜度。(1)int Prime(int n)int i=2,x=(int)sqrt(n); /sqrt(n)為求n的平方根while(i<=x)

4、if(n%i=0)break;i+;if(i>x) return 1;else return 0;(2)int sum1(int n)int p=1,s=0;for(int i=1;i<=n;i+)p*=i;s+=p;return s;(3)int sum2(int n)int s=0;for(int i=1;i<=n;i+)int p=1;for(int j=1;i<=i;j+) p*=j;s+=p;return s;(4)int fun(int n)int i=1,s=1;while(s<n) s+=+i;return i;(5)void mtable(int

5、 n)for(int i=1;i<=n;i+)for(int j=i;j<=n;j+)cout<<i<<"*"<<j<<"="<<setw(2)<<i*j<<" "cout<<endl;第二章作業(yè)一、選擇題1. 在線性表中的每一個(gè)表元素都是不可再分的( )A. 數(shù)據(jù)項(xiàng)B. 數(shù)據(jù)記錄C. 數(shù)據(jù)元素D. 數(shù)據(jù)字段2. 順序表是線性表的( )存儲(chǔ)表示。A. 有序B. 連續(xù)C. 數(shù)組D. 順序存取3. 若長(zhǎng)度為n的非空線性表采用順序存儲(chǔ)

6、結(jié)構(gòu)，在表中的第i個(gè)位置插入一個(gè)數(shù)據(jù)元素，i的合法值應(yīng)該是( )A. B. C. D. 4. 若設(shè)一個(gè)順序表的長(zhǎng)度為n，那么，在表中順序查找一個(gè)值為x的元素時(shí)，在等概率的情況下，查找成功的數(shù)據(jù)平均比較次數(shù)為( )A. B. C. D. 5. 在長(zhǎng)度為n的順序表的表尾插入一個(gè)新的元素的時(shí)間復(fù)雜度為( )A. B. C. D. 6. 數(shù)據(jù)結(jié)構(gòu)反映了數(shù)據(jù)元素之間的結(jié)構(gòu)關(guān)系。單鏈表是一種( )。A. 順序存儲(chǔ)線性表B. 非順序存儲(chǔ)非線性表C. 順序存儲(chǔ)非線性表D. 非順序存儲(chǔ)線性表7. 單鏈表又稱為線性鏈表，在單鏈表上實(shí)施插入和刪除操作( )A. 不需移動(dòng)結(jié)點(diǎn)，不需改變結(jié)點(diǎn)指針B. 不需移動(dòng)結(jié)點(diǎn)，只需

7、改變結(jié)點(diǎn)指針C. 只需移動(dòng)結(jié)點(diǎn)，不需改變結(jié)點(diǎn)指針D. 既需移動(dòng)結(jié)點(diǎn)，又需改變結(jié)點(diǎn)指針8. 已知L是帶頭結(jié)點(diǎn)的單鏈表，則刪除首元素結(jié)點(diǎn)的語句是( )A. L=L->next;B. L->next=L->next->next;C. L=L->next->next;D. L->next=L;9. 已知單鏈表A長(zhǎng)度為m，單鏈表B長(zhǎng)度為n，若將B鏈接在A的末尾，在沒有鏈尾指針的情況下，算法的時(shí)間復(fù)雜度應(yīng)為( )。A. B. C. D. 10. 給定有n個(gè)元素的一維數(shù)組，建立一個(gè)有序單鏈表的時(shí)間復(fù)雜度是( )A. B. C. D. 二、算法設(shè)計(jì)1. 設(shè)計(jì)一個(gè)算法，

8、從順序表L中(SqList L)刪除具有給定值x(ElemType x)的所有元素。2. 設(shè)計(jì)一個(gè)算法，從有序順序表中刪除所有其值重復(fù)的元素，使表中所有元素的值均不相同。3. 設(shè)計(jì)一個(gè)算法，在非遞減有序的帶頭結(jié)點(diǎn)的單鏈表中刪除值相同的多余結(jié)點(diǎn)。第三章作業(yè)一、選擇題1. 用S表示進(jìn)棧操作，用X表示出棧操作，若元素的進(jìn)棧順序是1234，為了得到1342的出棧順序，相應(yīng)的S和X的操作序列為( )A. SXSXSSXXB. SSSXXSXXC. SXSSXXSXD. SXSSXSXX2. 假設(shè)一個(gè)棧的輸入序列是1，2，3，4，則不可能得到的輸出序列是( )A. 1,2,3,4B. 4,1,2,3C.

9、4,3,2,1D. 1,3,4,23. 已知一個(gè)棧的進(jìn)棧序列為1,2,3,n，其輸出序列的第一個(gè)元素是i，則第j個(gè)出棧元素是( )。A. B. C. D. 不確定4. 已知一個(gè)棧的進(jìn)棧序列為，其輸出序列是。若，則的值是( )A. B. C. D. 不確定5. 已知一個(gè)棧的進(jìn)棧序列為，其輸出序列是。若，則的值是( )A.一定是2B. 一定是1C.可能是1D. 可能是26. 已知一個(gè)棧的進(jìn)棧序列為，其輸出序列是。若，則的值是( )A.一定是2B. 可能是2C.不可能是2D. 一定是37. 已知一個(gè)棧的進(jìn)棧序列為，其輸出序列是。若，則的值是( )A.一定是2B. 可能是2C.不可能是1D. 一定是1

10、8. 已知一個(gè)棧的進(jìn)棧序列為，其輸出序列是。若，則的值是( )A. B. C. D. 不確定9. 設(shè)棧S和隊(duì)列Q的初始狀態(tài)均為空，元素1,2,3,4,5,6,7，依次進(jìn)入S。如果每個(gè)元素出棧后立即進(jìn)入隊(duì)列Q，且7個(gè)元素的出隊(duì)順序?yàn)?,4,3,6,5,1,7，則棧S的容量至少是( )A. 1B. 2C. 3D. 410. 對(duì)中綴表達(dá)式求值，在求值過程中掃描到6時(shí)，操作數(shù)棧和操作符棧的內(nèi)容分別是( )A. 3,2,4,2,2和+,*,(,+,*B. 3,2,4,4和+,*,(,+C. 3,2,8和+,*,(D. 3,2,8,6和+,*,(,-二、算法設(shè)計(jì)題1. 詳見數(shù)據(jù)結(jié)構(gòu)題集(C語言版)第25頁

11、3.24。2. 詳見數(shù)據(jù)結(jié)構(gòu)題集(C語言版)第25頁3.25。第四章作業(yè)11. 串是一種特殊的線性表，其特殊性體現(xiàn)在( )A. 可以順序存儲(chǔ)B. 數(shù)據(jù)元素是一個(gè)字符C. 可以鏈?zhǔn)酱鎯?chǔ)D. 數(shù)據(jù)元素可以是多個(gè)字符12. 設(shè)有兩個(gè)串T和P，求P在T中首次出現(xiàn)的位置的運(yùn)算叫做( )。A. 求子串B. 模式匹配C. 串替換D. 串連接13. 下面關(guān)于串的敘述中，哪一個(gè)是不正確的？（ ）A串是字符的有限序列 B空串是由空格構(gòu)成的串C模式匹配是串的一種重要運(yùn)算 D串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)14. 串的長(zhǎng)度是指（ ）A串中所含不同字母的個(gè)數(shù) B串中所含字符的個(gè)數(shù)C串中所含不同字符的個(gè)數(shù) D串中

12、所含非空格字符的個(gè)數(shù)15. 兩個(gè)串相等的充分必要條件是（）A串中所含的字符相同 B串中所含字符的個(gè)數(shù)相同，且對(duì)應(yīng)位置上的字符也相同C串中所含的字符個(gè)數(shù)相同 D串中對(duì)應(yīng)位置上的字符相同6. 已知p=”abcaabbabcabaacbacb”，求出next函數(shù)值。第五章作業(yè)一、選擇題16. 數(shù)組通常具有的操作是( )A. 順序存取B. 直接存取C. 散列存取D. 索引存取17. 多維數(shù)組實(shí)際上是由( )實(shí)現(xiàn)的。A. 一維數(shù)組B. 多項(xiàng)式C. 三元組表D. 簡(jiǎn)單變量18. 在二維數(shù)組A810中，每一個(gè)數(shù)組元素Aij占用3個(gè)存儲(chǔ)空間，所有數(shù)組元素相繼存放于一個(gè)連續(xù)的存儲(chǔ)空間中，則存放該數(shù)組至少需要的存

13、儲(chǔ)空間是( )。A. 80B. 100C. 240D. 27019. 一個(gè)二維數(shù)組A1020按行存放于一個(gè)連續(xù)的存儲(chǔ)空間中，A00的存儲(chǔ)地址是200，每個(gè)數(shù)組元素占1個(gè)存儲(chǔ)字，則A62的地址為( )A. 226B. 322C. 341D. 34220. 一個(gè)二維數(shù)組A1020按列存放于一個(gè)連續(xù)的存儲(chǔ)空間中，A00的存儲(chǔ)地址是200，每個(gè)數(shù)組元素占1個(gè)存儲(chǔ)字，則A62的地址為( )A. 226B. 322C. 341D. 34221. 在二維數(shù)組A910中，每個(gè)數(shù)組元素占用3個(gè)存儲(chǔ)單元，從首地址SA開始按行連續(xù)存放，在這種情況下，元素A85的起始地址為( )A. SA+141B. SA+144C

14、. SA+222D. SA+25522. 將一個(gè)的對(duì)稱矩陣A的下三角部分按存放在一個(gè)一維數(shù)組B中，A00存放在B0中，那么第i行的對(duì)角元素Aii在B中的存放位置是( )A. B. C. D. 23. 將一個(gè)的對(duì)稱矩陣A的上三角部分按存放在一個(gè)一維數(shù)組B中，A00存放在B0中，那么第i行的對(duì)角元素Aii在B中的存放位置是( )A. B. C. D. 24. 設(shè)A是一個(gè)的對(duì)稱矩陣，將A的對(duì)角線及對(duì)角線上方的元素以列優(yōu)先(以列為主序)的方式存放在一維數(shù)組中，則矩陣中任一元素在B中的存放位置是( )A. B. C. D. 25. 設(shè)n階三對(duì)角矩陣A的三條對(duì)角線上的元素被按行壓縮存儲(chǔ)到一維數(shù)組B中，A0

15、0存放于B0。若某矩陣元素在B中存放的位置在k，那么該元素在原始矩陣中的行號(hào)i是( )A. B. C. D. 二、簡(jiǎn)答題26. 設(shè)有一個(gè)3維數(shù)組，按行優(yōu)先存放于一個(gè)連續(xù)的存儲(chǔ)空間中，每個(gè)數(shù)組元素占4個(gè)存儲(chǔ)字，首元素的存儲(chǔ)地址是1000，則存放于什么地方。27. 設(shè)有一個(gè)二維數(shù)組，假設(shè)存放位置在，存放在，每個(gè)元素占1個(gè)存儲(chǔ)單元，問存放在什么位置？腳注(10)表示用十進(jìn)制表示。28. 對(duì)于一個(gè)矩陣A的任一元素，按行存儲(chǔ)和按列存儲(chǔ)時(shí)的地址之差是多少？(假設(shè)兩種存儲(chǔ)的開始存儲(chǔ)地址以及元素所占存儲(chǔ)單元數(shù)d相同)29. 設(shè)有n階三對(duì)角矩陣A，將其3條對(duì)角線上的元素逐行存儲(chǔ)到數(shù)組中，使得，且，求(1) 用i

16、，j表示k的下標(biāo)變換公式。(2) 用k表示i，j的下表變換公式。30. 設(shè)有一個(gè)的對(duì)稱矩陣A，將其下三角部分按行壓縮存放于一個(gè)一維數(shù)組B中，存放于B0，試問：(1) 一維數(shù)組B有多少個(gè)元素？(2) A中的任意一個(gè)元素應(yīng)存于一維數(shù)組B的什么下標(biāo)位置？31. 設(shè)有一個(gè)的對(duì)稱矩陣A，將其上三角部分按列壓縮存放于一個(gè)一維數(shù)組B中，存放于B0，試問：(1) 一維數(shù)組B有多少個(gè)元素？(2) A中的任意一個(gè)元素應(yīng)存于一維數(shù)組B的什么下標(biāo)位置？第六章作業(yè)一、選擇題 32. 一顆有n個(gè)結(jié)點(diǎn)的樹的所有結(jié)點(diǎn)的度數(shù)之和為( )。A. B. C. D. 33. 設(shè)一顆高度為h的滿二叉樹有n個(gè)結(jié)點(diǎn)，其中有m個(gè)葉結(jié)點(diǎn)，則(

17、 )A. B. C. D. 34. 一顆有124個(gè)葉結(jié)點(diǎn)的完全二叉樹最多有( )個(gè)結(jié)點(diǎn)。A. 247B. 248C. 249D. 25035. 一顆有129個(gè)葉結(jié)點(diǎn)的完全二叉樹最少有( )個(gè)結(jié)點(diǎn)。A. 254B. 255C. 257D. 25836. 設(shè)完全二叉樹的第6層有24個(gè)葉結(jié)點(diǎn)，則此樹最多有( )個(gè)結(jié)點(diǎn)。A. 55B. 79C. 81D. 12737. 具有1000個(gè)結(jié)點(diǎn)的完全二叉樹的次底層的葉結(jié)點(diǎn)個(gè)數(shù)為( )。A. 11B. 12C. 24D. 3638. 用順序存儲(chǔ)的方法將n個(gè)結(jié)點(diǎn)的完全二叉樹中所有結(jié)點(diǎn)按層逐個(gè)順序存放在一維數(shù)組中，當(dāng)編號(hào)為0的根結(jié)點(diǎn)存放于時(shí)，若結(jié)點(diǎn)有左孩子，則左孩

18、子是( )。A. B. C. D. 39. 用順序存儲(chǔ)的方法將n個(gè)結(jié)點(diǎn)的完全二叉樹中所有結(jié)點(diǎn)按層逐個(gè)順序存放在一維數(shù)組中，當(dāng)編號(hào)為0的根結(jié)點(diǎn)存放于時(shí)，若結(jié)點(diǎn)有右孩子，則右孩子是( )。A. B. C. D. 40. 二叉樹的葉結(jié)點(diǎn)在前序、中序和后序遍歷過程中的相對(duì)順序( )。A. 發(fā)生改變B. 不發(fā)生變化C. 無法確定D. 以上均不對(duì)41. 設(shè)n，m為一顆二叉樹上的兩個(gè)結(jié)點(diǎn)，在該二叉樹的中序遍歷序列中n在m前的條件是( )。A. n在m右方B. n是m的祖先C. n在m左方D. n是m的子孫42. 設(shè)一顆二叉樹的前序序列為abdec，中序序列為dbeac，則該二叉樹的后序遍歷順序是( )。A.

19、 abdecB. debacC. debcaD. abedc43. 設(shè)一顆二叉樹的中序序列為badce，后序序列為bdeca，則該二叉樹的前序遍歷順序是( )。A. adbecB. decabC. debacD. abcde44. 對(duì)二叉樹的結(jié)點(diǎn)從1開始連續(xù)編號(hào)，要求每個(gè)結(jié)點(diǎn)的編號(hào)大于其左、右孩子的編號(hào)，同一結(jié)點(diǎn)的左、右孩子中，其左孩子編號(hào)小于其右孩子編號(hào)，則可采用( )遍歷實(shí)現(xiàn)二叉樹的結(jié)點(diǎn)編號(hào)。A. 先序B. 中序C. 后序D. 層次序45. 如果T2是由有序樹T轉(zhuǎn)換成的二叉樹，那么T中結(jié)點(diǎn)的先根遍歷順序?qū)?yīng)T2中結(jié)點(diǎn)的( )遍歷順序。A. 前序B. 中序C. 后序D. 層次序46. 如果T

20、2是由有序樹T轉(zhuǎn)換成的二叉樹，那么T中結(jié)點(diǎn)的后根遍歷順序?qū)?yīng)T2中結(jié)點(diǎn)的( )遍歷順序。A. 前序B. 中序C. 后序D. 層次序47. 用n個(gè)權(quán)值構(gòu)造出來的Huffman樹共有( )個(gè)結(jié)點(diǎn)。A. B. C. D. 48. 由權(quán)值為8,4,5,7的4個(gè)葉結(jié)點(diǎn)構(gòu)造一顆Huffman樹，該樹的帶權(quán)路徑長(zhǎng)度為( )。A. 24B. 36C. 48D. 72二、簡(jiǎn)答題49. 設(shè)二叉樹根結(jié)點(diǎn)所在層次為1，樹的深度d為距離根最遠(yuǎn)的葉結(jié)點(diǎn)所在的層次，試回答以下問題：(1) 試精確給出深度為d的完全二叉樹的不同二叉樹的棵數(shù)；(2) 試精確給出深度為d的滿二叉樹的不同二叉樹棵數(shù)。50. 如果一棵樹有個(gè)度為1的結(jié)

21、點(diǎn)，有個(gè)度為2的結(jié)點(diǎn)，有個(gè)度為m的結(jié)點(diǎn)，試問有多少個(gè)度為0的結(jié)點(diǎn)？51. 已知一棵二叉樹的前序遍歷序列為ABECDFGHIJ，中序遍歷序列為EBCDAFHIGJ。(1)畫出這棵二叉樹；(2)給出這棵二叉樹后序遍歷序列；(3)畫出這棵二叉樹轉(zhuǎn)換成對(duì)應(yīng)的樹(或森林)。52. 假定用于通信的電文僅有8個(gè)字母A,B,C,D,E,F,G,H組成，各字母在電文中出現(xiàn)的頻率分別為5,25,3,6,10,11,36,4。試為這8 個(gè)字母設(shè)計(jì)不等長(zhǎng)Huffman編碼，并給出該電文的總碼數(shù)。三、算法設(shè)計(jì)53. 設(shè)二叉樹的存儲(chǔ)結(jié)構(gòu)為二叉鏈表，編寫一個(gè)遞歸算法，統(tǒng)計(jì)二叉樹中度為1的結(jié)點(diǎn)個(gè)數(shù)。54. 設(shè)二叉樹的存儲(chǔ)結(jié)構(gòu)

22、為二叉鏈表，編寫一個(gè)遞歸算法，統(tǒng)計(jì)二叉樹中度為2的結(jié)點(diǎn)個(gè)數(shù)。55. 設(shè)樹T以孩子-兄弟鏈表作為其存儲(chǔ)表示，編寫一個(gè)算法統(tǒng)計(jì)樹T的葉結(jié)點(diǎn)個(gè)數(shù)。56. 設(shè)樹T以孩子-兄弟鏈表作為其存儲(chǔ)表示，編寫一個(gè)算法計(jì)算樹T的高度。第七章作業(yè)一、選擇題 1. 具有n個(gè)頂點(diǎn)且每一對(duì)不同頂點(diǎn)間都有一條邊的無向圖被稱為( )。A. 完全無向圖B. 無向連通圖C. 無向強(qiáng)連通圖D. 無向樹圖2. 一個(gè)有n個(gè)頂點(diǎn)的無向圖中邊數(shù)最多有( )條。A. B. C. D. 3. 對(duì)于具有個(gè)頂點(diǎn)的強(qiáng)連通圖，其有向邊條數(shù)至少是( )A. B. C. D. 4. 設(shè)G是一個(gè)非連通無向圖，有15條邊，則該圖的頂點(diǎn)數(shù)至少有( )個(gè)。A.

23、5B. 6C. 7D. 85. 在一個(gè)具有n個(gè)頂點(diǎn)的有向圖中，若所有頂點(diǎn)的岀度之和為s，則所有頂點(diǎn)的入度之和為( )。A. sB.s-1C. s+1D. n6. 一個(gè)有n個(gè)頂點(diǎn)和n條邊的無向圖一定是( )。A. 重連通圖B. 不連通圖C. 無環(huán)的D. 有環(huán)的7. 無向圖的鄰接矩陣是一個(gè)( )。A. 對(duì)稱矩陣B. 零矩陣C. 上三角矩陣D. 對(duì)角矩陣8. 有n個(gè)頂點(diǎn)和e條邊的無向圖采用鄰接矩陣存儲(chǔ)，零元素的個(gè)數(shù)為( )。A. B. C. D. 9. 帶權(quán)有向圖G用鄰接矩陣A存儲(chǔ)，則頂點(diǎn)i的入度等于A中( )。A. 第i行非的元素之和B. 第i列非的元素之和C. 第i行非且非0的元素個(gè)數(shù)D. 第i

24、列非且非0的元素個(gè)數(shù)10. 設(shè)圖有n個(gè)頂點(diǎn)和e條邊，采用鄰接矩陣時(shí)，遍歷圖的頂點(diǎn)所需時(shí)間為( )。A. B. C. D. 11. 設(shè)圖有n個(gè)頂點(diǎn)和e條邊，采用鄰接表時(shí)，遍歷圖的頂點(diǎn)所需時(shí)間為( )。A. B. C. D. 12. 圖的深度優(yōu)先搜索類似于樹的( )次序遍歷。A. 先根B. 中根C. 后根D. 層13. 圖的廣度優(yōu)先搜索類似于樹的( )次序遍歷。A. 先根B. 中根C. 后根D. 層14. 采用鄰接表存儲(chǔ)的圖的深度優(yōu)先搜索算法類似于二叉樹的( )。A. 中序遍歷B. 前序遍歷C. 后序遍歷D. 層次遍歷15. 采用鄰接表存儲(chǔ)的圖的廣度優(yōu)先搜索算法類似于二叉樹的( )。A. 中序遍歷

25、B. 前序遍歷C. 后序遍歷D. 層次遍歷16. 如果從無向圖的任一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜索即可訪問所有頂點(diǎn)，則該圖一定是( )。A. 強(qiáng)連通圖B. 連通圖C. 有回路D. 一棵樹17. 如果一個(gè)連通網(wǎng)絡(luò)G中各邊權(quán)值互不相同，權(quán)重最小的邊一定包含在G的( )生成樹中。A. 最小B. 任何C. 廣度優(yōu)先D. 深度優(yōu)先18. 任何一個(gè)連通圖的最小生成樹( )。A. 只有一棵B. 有一棵或多棵C. 一定有多棵D. 可能不存在19. 一個(gè)有n個(gè)頂點(diǎn)和e條邊的連通圖的生成樹有( )條邊。A. B. C. D. 20. 設(shè)一個(gè)n個(gè)頂點(diǎn)的帶權(quán)連通圖有條邊，則應(yīng)該選通( )算法來求這個(gè)圖的最小生成樹，從而

26、使計(jì)算時(shí)間較少。A. PrimB. KruskalC. DFSD. BFS21. 求最短路徑的Dijkstra算法的時(shí)間復(fù)雜度為( )。A. B. C. D. 22. 求最短路徑的Floyd算法的時(shí)間復(fù)雜度為( )。A. B. C. D. 23. 設(shè)有向圖具有n個(gè)頂點(diǎn)和e條邊，如果用鄰接表作為它的存儲(chǔ)結(jié)構(gòu)，則拓?fù)渑判虻臅r(shí)間復(fù)雜度為( )。A. B. C. D. 24. 設(shè)有向圖具有n個(gè)頂點(diǎn)和e條邊，如果用鄰接矩陣作為它的存儲(chǔ)結(jié)構(gòu)，則拓?fù)渑判虻臅r(shí)間復(fù)雜度為( )。A. B. C. D. 二、應(yīng)用題25. 針對(duì)圖1所示的有向圖，畫出該圖的鄰接矩陣、鄰接表和逆鄰接表。 圖1圖226. 對(duì)圖2所示的無

27、向圖，從頂點(diǎn)a開始進(jìn)行深度優(yōu)先遍歷，給出2個(gè)可得到的頂點(diǎn)訪問序列；從頂點(diǎn)a開始進(jìn)行廣度優(yōu)先遍歷，給出2個(gè)可得到的頂點(diǎn)訪問序列。27. 已知一個(gè)帶權(quán)連通圖如圖3所示，分別使用Prim算法和Kruskal算法求其最小生成樹。圖3圖428. 已知一個(gè)帶權(quán)有向圖如圖4所示，用Dijkstra算法求從頂點(diǎn)a到其余各頂點(diǎn)的最短路徑及路徑長(zhǎng)度。29. 如圖所示的AOE網(wǎng)，求(1) 完成此工程最少要多少天(設(shè)弧上的權(quán)值為天數(shù))；(2) 每項(xiàng)活動(dòng)的最早開始時(shí)間和最遲開始時(shí)間；(3) 哪些是關(guān)鍵活動(dòng)；(4) 是否存在某些活動(dòng)，當(dāng)其提高速度后能使整個(gè)工程縮短工期?圖5第九章作業(yè)一、選擇題 30. 順序查找算法適用于

28、( )。A. 線性表B. 查找樹C. 查找網(wǎng)D. 連通圖31. 順序查找法適用于線性表的( )。A.散列存儲(chǔ)B.壓縮存儲(chǔ)C. 索引存儲(chǔ)D. 順序或鏈接存儲(chǔ)32. 采用順序查找方式查找長(zhǎng)度為n的順序表時(shí)，平均查找長(zhǎng)度為( )A. B. C. D. 33. 如果有5個(gè)關(guān)鍵嗎a,b,c,d,e放在順序表中，他們的查找概率分別為0.35,0.25,0.20,.015,0.05，可使平均查找長(zhǎng)度達(dá)到最小的存放方式是( )。A. d,a,b,c,eB. e,d,c,b,aC. a,b,c,d,eD. a,c,e,d,b34. 對(duì)于長(zhǎng)度為n的有序單鏈表，若查找每個(gè)元素的概率相等，則順序查找表中任一元素的查找

29、成功的平均查找長(zhǎng)度為( )A. B. C. D. 35. 對(duì)線性表進(jìn)行折半查找時(shí)，要求線性表必須( )A. 以順序方式存儲(chǔ)B. 以鏈接方式存儲(chǔ)C. 以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵嗎有序排列D. 以鏈接方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵嗎有序排列36. 采用折半查找法查找長(zhǎng)度為n的有序順序表時(shí)，平均查找長(zhǎng)度為( )A. B. C. D. 37. 對(duì)于長(zhǎng)度為18的有序順序表，若采用折半查找，則查找第15個(gè)元素的查找次數(shù)為( )。A. 3B. 4C. 5D. 638. 已知有序順序表(13,18,24,35,47,50,62,83,90,115,134)，若采用折半查找法查找值為18的元素時(shí)，查找成功的數(shù)據(jù)比較次

30、數(shù)為( )。A. 1B. 2C. 3D. 439. 使用散列法時(shí)確定元素存儲(chǔ)地址的依據(jù)是( )。A. 元素的序號(hào)B. 元素個(gè)數(shù)C. 關(guān)鍵嗎D. 非碼屬性40. 設(shè)一個(gè)散列表中有n個(gè)元素，用散列法進(jìn)行查找的平均查找長(zhǎng)度是( )。A. B. C. D. 41. 使用散列函數(shù)將元素的關(guān)鍵嗎映射為散列地址時(shí)，常會(huì)發(fā)生沖突。此時(shí)的沖突是指( )。A. 兩個(gè)元素具有相同的序號(hào)B. 兩個(gè)元素的關(guān)鍵碼不同，而非關(guān)鍵碼相同C. 不同關(guān)鍵碼對(duì)應(yīng)到相同的存儲(chǔ)地址D. 裝載因子過大，數(shù)據(jù)元素過多42. 計(jì)算出的地址分布最均勻的散列函數(shù)是( )。A. 數(shù)值分析法B. 除留余數(shù)法C. 平方取中法D. 折疊法43. 將10

31、個(gè)元素散列到大小為100000個(gè)元素的散列表中，( )產(chǎn)生沖突。A. 一定會(huì)B. 一定不會(huì)C. 仍可能會(huì)D. 以上都不對(duì)44. 采用線性探測(cè)法解決沖突時(shí)計(jì)算出的一系列“下一個(gè)空位”( )。A. 必須大于等于原散列地址B. 必須小于等于原散列地址C. 可以大于或小于但不等于原散列地址D. 對(duì)地址在何處沒有限制45. 包含有4個(gè)結(jié)點(diǎn)的元素值互不相同的二叉查找樹有( )棵。A. 4B. 6C. 10D. 1446. 利用逐個(gè)數(shù)據(jù)插入的方法建立序列35,45,25,55,50,10,15,30,40,20對(duì)應(yīng)的二叉查找樹后，查找元素20需要進(jìn)行( )次元素之間的比較。A. 4B. 5C. 7D. 10

32、47. 一顆高度為h的AVL樹，若其每個(gè)非葉子結(jié)點(diǎn)的平衡因子都是0，則該樹共有( )個(gè)結(jié)點(diǎn)。A. B. C. D. 48. 高度為7的AVL樹最少有( )個(gè)結(jié)點(diǎn)。A. 12B. 21C. 33D. 5449. 高度為7的AVL樹最多有( )個(gè)結(jié)點(diǎn)。A. 63B. 64C. 65D. 127二、應(yīng)用題50. 設(shè)有一個(gè)關(guān)鍵碼的輸入序列55,31,11,37,46,73,63，從空樹開始構(gòu)造AVL樹，畫出每加入一個(gè)新結(jié)點(diǎn)時(shí)二叉樹的形態(tài)。若發(fā)生不平衡，指明需做的平衡旋轉(zhuǎn)的類型及平衡旋轉(zhuǎn)的結(jié)果。51. 分別畫出在圖1所示的AVL樹中插入15、36后樹的變化。如果有平衡化旋轉(zhuǎn)，注明相關(guān)結(jié)點(diǎn)平衡因子的變化(

33、注意，15和36是各自獨(dú)立插入到圖1所示的AVL樹中)。圖152. 已知含12個(gè)關(guān)鍵字的有序表及其相應(yīng)的權(quán)值如下表，試按次優(yōu)查找樹的構(gòu)造算法，畫出由這12個(gè)關(guān)鍵字構(gòu)造所得的次優(yōu)查找樹，并計(jì)算它的PH值。關(guān)鍵字ABCDEFGHIJKL權(quán)值82349326711453. 對(duì)于23題有序表及其相應(yīng)的權(quán)值，試按次優(yōu)查找樹的構(gòu)造算法并加適當(dāng)調(diào)整，畫出由這12個(gè)關(guān)鍵字構(gòu)造所得的次優(yōu)查找樹，并計(jì)算它的PH值。通過適當(dāng)調(diào)整后得到的次優(yōu)查找樹是否更優(yōu)？54. 設(shè)哈希表HT15，哈希函數(shù)為。用開放地址法解決沖突，對(duì)下列關(guān)鍵碼序列12,23,45,57,20,03,78,31,15,36造表。采用線性探測(cè)法尋找下一

34、個(gè)空位，畫出相應(yīng)的哈希表，并計(jì)算等概率下查找成功的平均查找長(zhǎng)度和查找不成功的平均查找長(zhǎng)度。55. 設(shè)哈希表HT15，哈希函數(shù)為。用開放地址法解決沖突，對(duì)下列關(guān)鍵碼序列12,23,45,57,20,03,78,31,15,36造表。采用再哈希法尋找下一個(gè)空位，再哈希函數(shù)為，尋找下一個(gè)空位置的公式為，。畫出相應(yīng)的哈希表，并計(jì)算等概率下查找成功的平均查找長(zhǎng)度。第十章作業(yè)一、選擇題 56. 排序算法的穩(wěn)定性是指( )。A. 經(jīng)過排序后，能使值相同的數(shù)據(jù)保持原順序中的相對(duì)位置不變B. 經(jīng)過排序后，能使值相同的數(shù)據(jù)保持原順序中的絕對(duì)位置不變C. 經(jīng)過排序后，數(shù)據(jù)序列的存放數(shù)組的結(jié)構(gòu)保持不變D. 經(jīng)過排序后，數(shù)據(jù)序列的存放數(shù)組的結(jié)構(gòu)隨之變化57. 若要求在最壞情況下也能盡快地對(duì)序列進(jìn)行穩(wěn)定的排序，則應(yīng)選( )。A.起泡排序B.快速排序C. 歸并排序D. 堆排序58. 每次從未排序的序列中取出一個(gè)元素與已排序的序列中的元素依次進(jìn)行比較，然后把它插入到已排序序列中的適當(dāng)位置，此種排序方法叫做( )A. 起泡排序B. 直接插入排序C. 簡(jiǎn)單選擇排序D. 二路歸并排序59. 對(duì)5個(gè)不同數(shù)據(jù)元素做直接插入排序，其數(shù)據(jù)比較次數(shù)最多是( )。A. 8B. 10C. 15D. 2560. 直接插入排序在最好情