練習(xí)附答案(更新).doc

一、單項(xiàng)選擇題1. 邏輯關(guān)系是指數(shù)據(jù)元素間的（ C ）A 類型 B 存儲方式 C結(jié)構(gòu) D 數(shù)據(jù)項(xiàng)2. 對于只在表的首、尾兩端進(jìn)行插入操作的線性表，宜采用的存儲結(jié)構(gòu)為( C ) A順序表 B.用頭指針表示的單循環(huán)鏈表 C. 用尾指針表示的單循環(huán)鏈表 D. 單鏈表 3. 設(shè)數(shù)組datam作為循環(huán)隊(duì)列SQ的存儲空間，front為隊(duì)頭指針，rear為隊(duì)尾指針，則執(zhí)行出隊(duì)操作后其頭指針front值為（D ） Afront=front+1Bfront=(front+1)%(m-1) Cfront=(front-1)%mDfront=(front+1)%m4. 在具有n個單元的順序存儲的循環(huán)隊(duì)列中，假定front和rear分別為隊(duì)頭指針和隊(duì)尾指針，則判斷隊(duì)滿的條件為( D )。Arearn=front B(front+l)n=rearCrearn-1=front D(rear+l)n=front5. 在具有n個單元的順序存儲的循環(huán)隊(duì)列中，假定front和rear分別為隊(duì)頭指針和隊(duì)尾指針，則判斷隊(duì)空的條件為( C )。A rearn=front Bfront+l=rearCrear=front D(rear+l)n=front6. 已知一顆二叉樹上有92個葉子結(jié)點(diǎn)，則它有_個度為2的結(jié)點(diǎn)。( B )A. 90 B. 91 C. 92 D. 93 7. 在一棵非空二叉樹的中序遍歷序列中，根結(jié)點(diǎn)的右邊( C )。A.只有右子樹上的所有結(jié)點(diǎn) B. 只有右子樹上的部分結(jié)點(diǎn) C.只有左子樹上的所有結(jié)點(diǎn) D. 只有左子樹上的部分結(jié)點(diǎn)8. 有n條邊的無向圖的鄰接表存儲法中，鏈表中結(jié)點(diǎn)的個數(shù)是( B )個。 A.n B. 2n C. n/2 D.n*n9. 判斷有向圖是否存在回路，除了可利用拓?fù)渑判蚍椒ㄍ?，還可以利用（ C ）。A. 求關(guān)鍵路徑的方法 B.求最短路徑的方法C. 深度優(yōu)先遍歷算法 D.廣度優(yōu)先遍歷算法10. 對線性表進(jìn)行二分查找時，要求線性表必須( A )。 A.鍵值有序的順序表 B.鍵值有序的鏈接表 C.鏈接表但鍵值不一定有序 D.順序表但鍵值不一定有序11. 下列時間復(fù)雜度中最好的是（ A ）。 AO(1) BO(n) CO(log2n) DO(n2)12. 若某線性表的常用操作是取第i個元素及其前趨元素，則采用( A )存儲方式最節(jié)省時間？A順序表B單鏈表C雙鏈表D單向循環(huán)13. 在一個單鏈表HL中，若要向q所指結(jié)點(diǎn)之后插入一個由指針p指向的結(jié)點(diǎn)，則執(zhí)行（ C ）AHL=p;p-next=HL Bp-next=HL;HL=pCp-next=q-next;q-next=p Dp-next=q-next;q=pnext14. 棧和隊(duì)列是兩種特殊的線性表，只能在它們的（ B ）處添加或刪除結(jié)點(diǎn)。A中間點(diǎn) B端點(diǎn) C隨機(jī)存取點(diǎn) D結(jié)點(diǎn)15. 一個棧的輸入序列為1，2，3，4，5，則下列序列中不可能是站的輸出序列的是( B) A. 2,3,4,1,5 B.5,4,1,3,2 C. 2,3,1,4,5 D.1,5,4,3,216. 廣義表(a),a)的表尾是。（ C ）Aa B C(a) D (a)17. 將含100個結(jié)點(diǎn)的完全二叉樹從根這一層開始，每層從左至右依次對結(jié)點(diǎn)編號，根結(jié)點(diǎn)的編號為1。編號為47的結(jié)點(diǎn)X的雙親的編號為( C )A24 B25 C23 D無法確定18. 有n個頂點(diǎn)的無向圖的鄰接矩陣是用_A_數(shù)組存儲。A. n行n列 B.一維 C.任意行n列 D.n行任意列19. 如圖所示有向圖的一個拓?fù)湫蛄惺牵˙）AABCDEF BFCBEAD CFEDCBA DDAEBCF20. 有一個有序表1，4，6，10，18，35，42，53，67，71，78，84，92，99，當(dāng)用二分查找法查找鍵值為84的結(jié)點(diǎn)時，經(jīng)_C_比較后查找成功。 A.2 B.3C.4 D.1221. 在一個帶有附加表頭結(jié)點(diǎn)的單鏈表HL中，若要向表頭插入一個由指針p指向的結(jié)點(diǎn)，則執(zhí)行（ B ）A. HL=p; p-next=HL; B. p-next=HL-next; HL-next=p;C. p-next=HL; p=HL; D. p-next=HL; HL=p; 22. 若采用單鏈表表示循環(huán)隊(duì)列，則應(yīng)該選用（ B ）A. 帶尾指針的非循環(huán)鏈表 B. 帶尾指針的循環(huán)鏈表C. 帶頭指針的非循環(huán)鏈表 D. 帶頭指針的循環(huán)鏈表23. 棧和隊(duì)列是兩種特殊的線性表，只能在它們的 處添加或刪除結(jié)點(diǎn)。（ B ）A. 中間點(diǎn) B. 端點(diǎn) C. 隨機(jī)存取點(diǎn) D. 結(jié)點(diǎn)24. 首先訪問結(jié)點(diǎn)的左子樹，然后訪問該結(jié)點(diǎn)，最后訪問結(jié)點(diǎn)的右子樹，這種遍歷稱為 (C )A.前序遍歷 B.后序遍歷 C.中序遍歷D.層次遍歷25. 樹最適合用來表示（ C ）A.有序數(shù)據(jù)元素 B.無序數(shù)據(jù)元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù) D.元素之間無聯(lián)系的數(shù)據(jù)26. 已知一顆二叉樹上有92個葉子結(jié)點(diǎn)，則它有_個度為2的結(jié)點(diǎn)。（ B ）A. 90 B. 91 C. 92 D. 9327. 對一棵查找樹根結(jié)點(diǎn)而言，左子樹中所有結(jié)點(diǎn)與右子樹中所有結(jié)點(diǎn)的關(guān)鍵字大小關(guān)系是 ( A)A、小于 B、大于 C、等于D、不小于1. 設(shè)有一個二維數(shù)組Amn，假設(shè)A00存放位置在644(10)，A22存放位置在676(10)，每個元素占一個空間，問A33(10)存放在什么位置？腳注(10)表示用10進(jìn)制表示。( C )A.688 B.678 C.692 D.6962. 設(shè)有6個結(jié)點(diǎn)的無向圖，該圖至少應(yīng)該有( A )條邊才能確保是一個連通圖。A.5 B. 6 C. 7 D. 83. 根據(jù)二叉樹的定義可知二叉樹共有( B )種不同的形態(tài)。A.4 B.5 C.6 D.74. 假設(shè)在一棵二叉樹中，雙分支結(jié)點(diǎn)數(shù)為15，單分 支結(jié)點(diǎn)數(shù)為30個，則葉子結(jié)點(diǎn)數(shù)為( B )個。A15 B16 C17 D475. 任何一棵二叉樹的葉子結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對次序( A )。A不發(fā)生改變 B發(fā)生改變 C不能確定 D以上都不對6. 在一個具有n個頂點(diǎn)的無向完全圖中，所含的邊數(shù)為( C )。An Bn(n-1) Cn(n-1)/2 Dn(n+1)/27. 若一個圖的邊集為(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)，則從頂點(diǎn)A開始對該圖進(jìn)行深度優(yōu)先搜索，得到的頂點(diǎn)序列可能為( B )。AA,B,C,F,D,E BA,C,F,D,E,BCA,B,D,C,F,E DA,B,D,F,E,C8. 假定對元素序列(7,3,5,9,1,12)進(jìn)行堆排序，采用小頂堆，則初始數(shù)據(jù)構(gòu)成的初始堆為( B )。A1,3,5,7,9,12 B1,3,5,9,7,12C1,7,3,5,9,12 D1,3,5,7,9,12 二、填空題1. 根據(jù)值的不同特性，高級程序語言中的數(shù)據(jù)類型可分為兩類：_原子類型_和 結(jié)構(gòu)類型。2. 線性表有兩種存儲結(jié)構(gòu)： 順序結(jié)構(gòu) 和 鏈?zhǔn)浇Y(jié)構(gòu) 。3. 在以HL為表頭指針的循環(huán)單鏈表中，鏈表為空的條件為 HL-next=HL 。4. 設(shè)棧S和隊(duì)列Q的初始狀態(tài)皆為空，元素a1,a2,a3,a4,a5和a6一次通過一個棧后即進(jìn)入隊(duì)列Q，若6個元素出對的順序是a3,a5,a4,a6,a2,a1，則棧S至少可以容納 4 個元素。5. 對于一棵具有30個結(jié)點(diǎn)的二叉樹，若一個結(jié)點(diǎn)的編號為5，則它的左孩子結(jié)點(diǎn)的編號為 10 ，右孩子結(jié)點(diǎn)的編號為 11 ，雙親結(jié)點(diǎn)的編號為 2 。6. 對于一個具有n個結(jié)點(diǎn)的二叉樹，當(dāng)它存儲在二叉鏈表中時，其指針字段的總數(shù)為 2n 個，其中 n-1 個用于鏈接孩子結(jié)點(diǎn)， n+1 個空閑。7. 設(shè)圖中有n 個頂點(diǎn)，e條邊，則含有e= n(n-1)/2 條邊的無向圖稱作完全圖，含有e= n(n-1) 條弧的有向圖稱作有向完全圖。8. 對于線性表（78，4，56，30，65）進(jìn)行哈希存儲時，若選用H（K）=K %5作為哈希函數(shù)，則哈希地址為0的元素有 2 個。9. 在單鏈表上難以實(shí)現(xiàn)的排序方法有 堆排序 和 希爾排序 。10. 根據(jù)值的不同特性，高級程序語言中的數(shù)據(jù)類型可分為兩類：原子類型 和 結(jié)構(gòu)類型 。11. 在單鏈表中，刪除指針P所指節(jié)點(diǎn)的后繼結(jié)點(diǎn)的語句是 p-next=p-next-next 。12. 棧又稱為 后進(jìn)先出 的線性表，隊(duì)列又稱為 先進(jìn)先出 的線性表。13. N個結(jié)點(diǎn)的二叉樹采用二叉鏈表存放，共有空鏈域個數(shù)為 N+1 。14. 一棵深度為k的滿二叉樹的結(jié)點(diǎn)總數(shù)為2k-1 ，一棵深度為k的完全二叉樹的結(jié)點(diǎn)總數(shù)的最小值為 2k-1 ，最大值為 2k-1 。15. 具有80個結(jié)點(diǎn)的完全二叉樹，若按層次從上到下、從左到右對其編號(根結(jié)點(diǎn)為1號)，則編號最大的分支結(jié)點(diǎn)序號為 40 ，編號最小的分支結(jié)點(diǎn)序號為 1 _，編號最大的葉子結(jié)點(diǎn)序號為 80 ，編號最小的葉子結(jié)點(diǎn)序號為 41 。16. 采用二分法進(jìn)行查找的查找表，應(yīng)選擇_鍵值有序的順序_的存儲結(jié)構(gòu)。17. 假設(shè)在有序表A 019中進(jìn)行二分查找，比較二次查找成功的結(jié)點(diǎn)數(shù)為 2 ，比較三次查找成功的結(jié)點(diǎn)數(shù)為 4 。18. 一個有向圖G中若有弧、和，則在圖G的拓樸序列中，頂點(diǎn)Vi,Vj和Vk的相對位置為_VjViVk_。19. 對于一個長度為n的順序存儲的線性表，在表頭插入元素的時間復(fù)雜度為_O(n) ，在表尾插入元素的時間復(fù)雜度為 O(1) 。20. 棧又稱為 后進(jìn)先出 的線性表，隊(duì)列又稱為 先進(jìn)先出 的線性表。21. 對于一棵具有n個結(jié)點(diǎn)的二叉樹，用二叉鏈表存儲時，其指針總數(shù)為 2n 個，其中 n+1 個指針是空閑的。22. 在稀疏矩陣所對應(yīng)的三元組線性表中，每個三元組元素按_ 行序 為主序、 列序 為輔序的次序排列。23. 一顆深度為K且有 2k-1個結(jié)點(diǎn)的二叉樹稱為滿二叉樹。24. 若對一棵完全二叉樹從0開始進(jìn)行結(jié)點(diǎn)的編號，并按此編號把它順序存儲到一維數(shù)組A中，即編號為0的結(jié)點(diǎn)存儲到A0中。其余類推，則Ai元素的左孩子元素為 2i+1 ，雙親元素為 (i-1)/2 。25. 對于線性表（78，4，56，30，65）進(jìn)行哈希存儲時，若選用H（K）=K %5作為哈希函數(shù)，則哈希地址為0的元素有 2 個，哈希地址為4的有 1 個。26. 以折半查找方法從長度為8的有序表中查找一個元素時，平均查找長度為 2.625 。27. 假定一個有向圖的頂點(diǎn)集為a,b,c,d,e,f，邊集,，則出度為0的頂點(diǎn)個數(shù)為 1 ，入度為1的頂點(diǎn)個數(shù)為 4 。28. 設(shè)有向圖G中有向邊的集合E=，則該圖的一種拓?fù)湫蛄袨?1423 。29. 對于一棵具有n個結(jié)點(diǎn)的二叉樹，當(dāng)進(jìn)行鏈接存儲時，其二叉鏈表中的指針域的總數(shù)為2n個，其中 n-1 個用于鏈接孩子結(jié)點(diǎn)， n+1 個空閑著。30. 設(shè)有向圖中不存在有向邊，則其對應(yīng)的鄰接矩陣A中的數(shù)組元素Aij的值等于_ 0 _。31. 根據(jù)初始關(guān)鍵字序列(19，22，01，38，10)建立的二叉排序樹的高度為 3 。32.三應(yīng)用題1. 順序隊(duì)的“假溢出”是怎樣產(chǎn)生的？如何知道循環(huán)隊(duì)列是空還是滿？2. 回文。假設(shè)一字符序列已存入計(jì)算機(jī)，請分析用線性表、堆棧和隊(duì)列等方式正確輸出其回文的可能性？假設(shè)正讀和反讀都相同的字符序列為“回文”，例如，abba和abcba是回文，abcde 和ababab則不是。3. 設(shè)有編號為1，2，3，4的四輛列車，順序進(jìn)入一個棧式結(jié)構(gòu)的車站，具體寫出這四輛列車開出車站的所有可能的順序。至少有14種。 全進(jìn)之后再出情況，只有1種：4，3，2，1 進(jìn)3個之后再出的情況，有3種，3,4,2,1 3,2,4,1 3,2,1,4 進(jìn)2個之后再出的情況，有5種，2,4,3,1 2,3,4,1 2,1, 3,4 2,1,4,3 2,1,3,4 進(jìn)1個之后再出的情況，有5種，1,4,3,2 1,3,2,4 1,3,4,2 1, 2,3,4 1,2,4,34. 對給定的權(quán)值2,3,4,7,8,9，構(gòu)造出相應(yīng)的赫夫曼樹，并求出帶權(quán)路徑的長度WPL。WPL=2*4+3*4+4*3+9*2+7*2+8*2=805. 對于下圖的無向圖，繪出從a出發(fā)，用普利姆算法構(gòu)造的最小生成樹的過程。（過程略）6. 請畫出右圖的鄰接矩陣和鄰接表。7. 試比較順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)缺點(diǎn)。在什么情況下用順序表比鏈表好？在什么情況下用鏈表比順序表好？ 順序存儲時，相鄰數(shù)據(jù)元素的存放地址也相鄰（邏輯與物理統(tǒng)一）；要求內(nèi)存中可用存儲單元的地址必須是連續(xù)的。優(yōu)點(diǎn)：存儲密度大（1？），存儲空間利用率高。缺點(diǎn)：插入或刪除元素時不方便。鏈?zhǔn)酱鎯r，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲空間分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針優(yōu)點(diǎn)：插入或刪除元素時很方便，使用靈活。缺點(diǎn)：存儲密度小，存儲空間利用率低。順序表適宜于做查找這樣的靜態(tài)操作；鏈表宜于做插入、刪除這樣的動態(tài)操作。若線性表的長度變化不大，且其主要操作是查找，則采用順序表；若線性表的長度變化較大，且其主要操作是插入、刪除操作，則采用鏈表。8. 按照下列給定二叉樹的先序遍歷序列、中序遍歷序列和后序遍歷序列，分別構(gòu)造出二叉樹。 先序遍歷序列：EBADCFHGIKJ中序遍歷序列：ABCDEFGHIJK 中序遍歷序列：ACBGEDF后序遍歷序列：ABCDEFG (1) (2) 9. 如下列所示的連通圖，請畫出：（1）以頂點(diǎn)a為根的深度優(yōu)先生成樹；（2）如果有關(guān)節(jié)點(diǎn)，請找出所有的關(guān)節(jié)點(diǎn)。頂點(diǎn)