數(shù)據(jù)結(jié)構(gòu)練習(xí)附答案

1、一、單項(xiàng)選擇題1. 邏輯關(guān)系是指數(shù)據(jù)元素間的（ ）A 類型 B 存儲方式 C結(jié)構(gòu) D 數(shù)據(jù)項(xiàng)2. 對于只在表的首、尾兩端進(jìn)行插入操作的線性表，宜采用的存儲結(jié)構(gòu)為( ) A順序表 B.用頭指針表示的單循環(huán)鏈表 C. 用尾指針表示的單循環(huán)鏈表 D. 單鏈表 3. 設(shè)數(shù)組datam作為循環(huán)隊(duì)列SQ的存儲空間，front為隊(duì)頭指針，rear為隊(duì)尾指針，則執(zhí)行出隊(duì)操作后其頭指針front值為（ ） Afront=front+1 Bfront=(front+1)%(m-1) Cfront=(front-1)%m Dfront=(front+1)%m4. 在具有n個(gè)單元的順序存儲的循環(huán)隊(duì)列中，假定front

2、和rear分別為隊(duì)頭指針和隊(duì)尾指針，則判斷隊(duì)滿的條件為( )。Arearn=front B(front+l)n=rearCrearn-1=front D(rear+l)n=front5. 在具有n個(gè)單元的順序存儲的循環(huán)隊(duì)列中，假定front和rear分別為隊(duì)頭指針和隊(duì)尾指針，則判斷隊(duì)空的條件為( )。A rearn=front Bfront+l=rearCrear=front D(rear+l)n=front6. 已知一顆二叉樹上有92個(gè)葉子結(jié)點(diǎn)，則它有_個(gè)度為2的結(jié)點(diǎn)。( )A. 90 B. 91 C. 92 D. 93 7. 在一棵非空二叉樹的中序遍歷序列中，根結(jié)點(diǎn)的右邊_。A.只有右子樹

3、上的所有結(jié)點(diǎn) B. 只有右子樹上的部分結(jié)點(diǎn) C.只有左子樹上的所有結(jié)點(diǎn) D. 只有左子樹上的部分結(jié)點(diǎn)8. 有n條邊的無向圖的鄰接表存儲法中，鏈表中結(jié)點(diǎn)的個(gè)數(shù)是( )個(gè)。 A.n B. 2n C. n/2 D.n*n9. 判斷有向圖是否存在回路，除了可利用拓?fù)渑判蚍椒ㄍ?，還可以利用（ ）。A. 求關(guān)鍵路徑的方法 B.求最短路徑的方法C. 深度優(yōu)先遍歷算法 D.廣度優(yōu)先遍歷算法10. 對線性表進(jìn)行二分查找時(shí)，要求線性表必須( )。 A.鍵值有序的順序表 B.鍵值有序的鏈接表 C.鏈接表但鍵值不一定有序 D.順序表但鍵值不一定有序11. 下列時(shí)間復(fù)雜度中最好的是（ ）。 AO(1) BO(n) CO

4、(log2n) DO(n2)12. 若某線性表的常用操作是取第i個(gè)元素及其前趨元素，則采用( )存儲方式最節(jié)省時(shí)間？A順序表B單鏈表C雙鏈表D單向循環(huán)13. 在一個(gè)單鏈表HL中，若要向q所指結(jié)點(diǎn)之后插入一個(gè)由指針p指向的結(jié)點(diǎn)，則執(zhí)行（ ）AHL=p;p-next=HL Bp-next=HL;HL=pCp-next=q-next;q-next=p Dp-next=q-next;q=pnext14. 棧和隊(duì)列是兩種特殊的線性表，只能在它們的（ ）處添加或刪除結(jié)點(diǎn)。A中間點(diǎn) B端點(diǎn) C隨機(jī)存取點(diǎn) D結(jié)點(diǎn)15. 一個(gè)棧的輸入序列為1，2，3，4，5，則下列序列中不可能是站的輸出序列的是_ A. 2,3

5、,4,1,5 B.5,4,1,3,2 C. 2,3,1,4,5 D.1,5,4,3,216. 廣義表(a),a)的表尾是。（ ）Aa B C(a) D (a)17. 將含100個(gè)結(jié)點(diǎn)的完全二叉樹從根這一層開始，每層從左至右依次對結(jié)點(diǎn)編號，根結(jié)點(diǎn)的編號為1。編號為47的結(jié)點(diǎn)X的雙親的編號為( )A24 B25 C23 D無法確定18. 有n個(gè)頂點(diǎn)的無向圖的鄰接矩陣是用_數(shù)組存儲。A. n行n列 B.一維 C.任意行n列 D.n行任意列19. 如圖所示有向圖的一個(gè)拓?fù)湫蛄惺牵ǎ〢ABCDEF BFCBEAD CFEDCBA DDAEBCF20. 有一個(gè)有序表1，4，6，10，18，35，42，53

6、，67，71，78，84，92，99，當(dāng)用二分查找法查找鍵值為84的結(jié)點(diǎn)時(shí)，經(jīng)_比較后查找成功。 A.2 B.3C.4 D.1221. 在一個(gè)帶有附加表頭結(jié)點(diǎn)的單鏈表HL中，若要向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn)，則執(zhí)行（ ）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)該選用（ ）A. 帶尾指針的非循環(huán)鏈表 B. 帶尾指針的循環(huán)鏈表C. 帶頭指針的非循環(huán)鏈表 D. 帶頭指針的循環(huán)鏈表23. 棧和隊(duì)列是兩種特殊的線性表，只能在它

7、們的 處添加或刪除結(jié)點(diǎn)。（ ）A. 中間點(diǎn) B. 端點(diǎn) C. 隨機(jī)存取點(diǎn) D. 結(jié)點(diǎn)24. 首先訪問結(jié)點(diǎn)的左子樹，然后訪問該結(jié)點(diǎn)，最后訪問結(jié)點(diǎn)的右子樹，這種遍歷稱為 ( )A.前序遍歷 B.后序遍歷 C.中序遍歷D.層次遍歷25. 樹最適合用來表示（ ）A.有序數(shù)據(jù)元素 B.無序數(shù)據(jù)元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù) D.元素之間無聯(lián)系的數(shù)據(jù)26. 已知一顆二叉樹上有92個(gè)葉子結(jié)點(diǎn)，則它有_個(gè)度為2的結(jié)點(diǎn)。（ ）A. 90 B. 91 C. 92 D. 9327. 對一棵查找樹根結(jié)點(diǎn)而言，左子樹中所有結(jié)點(diǎn)與右子樹中所有結(jié)點(diǎn)的關(guān)鍵字大小關(guān)系是 ( )A、小于 B、大于 C、等于D、不小于28

8、. 對關(guān)鍵字序列19，11，27，18，33進(jìn)行快速排序，則要進(jìn)行多少次關(guān)鍵字比較？（ ）A. 5次 B. 6次 C. 7次 D. 8次1. 設(shè)有一個(gè)二維數(shù)組Amn，假設(shè)A00存放位置在644(10)，A22存放位置在676(10)，每個(gè)元素占一個(gè)空間，問A33(10)存放在什么位置？腳注(10)表示用10進(jìn)制表示。( C )A.688 B.678 C.692 D.6962. 設(shè)有6個(gè)結(jié)點(diǎn)的無向圖，該圖至少應(yīng)該有( A )條邊才能確保是一個(gè)連通圖。A.5 B. 6 C. 7 D. 83. 根據(jù)二叉樹的定義可知二叉樹共有( B )種不同的形態(tài)。A.4 B.5 C.6 D.74. 假設(shè)在一棵二叉樹

9、中，雙分支結(jié)點(diǎn)數(shù)為15，單分 支結(jié)點(diǎn)數(shù)為30個(gè)，則葉子結(jié)點(diǎn)數(shù)為( B )個(gè)。A15 B16 C17 D475. 任何一棵二叉樹的葉子結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對次序( A )。A不發(fā)生改變 B發(fā)生改變 C不能確定 D以上都不對6. 在一個(gè)具有n個(gè)頂點(diǎn)的無向完全圖中，所含的邊數(shù)為( C )。An Bn(n-1) Cn(n-1)/2 Dn(n+1)/27. 若一個(gè)圖的邊集為(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

10、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ù)類型可分為兩類：_和_。2. 線性表有兩種存儲結(jié)構(gòu)：_和_。3. 在以HL為表頭指針的循環(huán)單鏈表中，鏈表為空的條件為_。4. 設(shè)棧S和隊(duì)列Q的初始狀態(tài)皆為空，元素a1,a2,a3,a4,a5和a6一次通過一個(gè)棧后即進(jìn)入隊(duì)列Q，若6個(gè)元素出對的順序是a3,a5,a4,a6,a2,a1，則棧S至少可以容納_

11、個(gè)元素。5. 對于一棵具有30個(gè)結(jié)點(diǎn)的二叉樹，若一個(gè)結(jié)點(diǎn)的編號為5，則它的左孩子結(jié)點(diǎn)的編號為_，右孩子結(jié)點(diǎn)的編號為_，雙親結(jié)點(diǎn)的編號為_。6. 對于一個(gè)具有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)它存儲在二叉鏈表中時(shí)，其指針字段的總數(shù)為_個(gè)，其中_個(gè)用于鏈接孩子結(jié)點(diǎn)，_個(gè)空閑。7. 設(shè)圖中有n 個(gè)頂點(diǎn)，e條邊，則含有e=_ _條邊的無向圖稱作完全圖，含有e=_條弧的有向圖稱作有向完全圖。8. 對于線性表（78，4，56，30，65）進(jìn)行哈希存儲時(shí)，若選用H（K）=K %5作為哈希函數(shù)，則哈希地址為0的元素有_個(gè)。9. 在單鏈表上難以實(shí)現(xiàn)的排序方法有_和_。10. 根據(jù)值的不同特性，高級程序語言中的數(shù)據(jù)類型可分為兩

12、類：_和_。11. 在單鏈表中，刪除指針P所指節(jié)點(diǎn)的后繼結(jié)點(diǎn)的語句是_。12. 棧又稱為_的線性表，隊(duì)列又稱為_的線性表。13. N個(gè)結(jié)點(diǎn)的二叉樹采用二叉鏈表存放，共有空鏈域個(gè)數(shù)為_。14. 一棵深度為k的滿二叉樹的結(jié)點(diǎn)總數(shù)為_，一棵深度為k的完全二叉樹的結(jié)點(diǎn)總數(shù)的最小值為_，最大值為_。15. 具有80個(gè)結(jié)點(diǎn)的完全二叉樹，若按層次從上到下、從左到右對其編號(根結(jié)點(diǎn)為1號)，則編號最大的分支結(jié)點(diǎn)序號為_，編號最小的分支結(jié)點(diǎn)序號為_，編號最大的葉子結(jié)點(diǎn)序號為_，編號最小的葉子結(jié)點(diǎn)序號為_。16. 采用二分法進(jìn)行查找的查找表，應(yīng)選擇_的存儲結(jié)構(gòu)。17. 假設(shè)在有序表A 019中進(jìn)行二分查找，比較二

13、次查找成功的結(jié)點(diǎn)數(shù)為_，比較三次查找成功的結(jié)點(diǎn)數(shù)為_。18. 一個(gè)有向圖G中若有弧、和，則在圖G的拓樸序列中，頂點(diǎn)Vi,Vj和Vk的相對位置為_。19. 對于一個(gè)長度為n的順序存儲的線性表，在表頭插入元素的時(shí)間復(fù)雜度為_，在表尾插入元素的時(shí)間復(fù)雜度為_。20. 棧又稱為_的線性表，隊(duì)列又稱為_的線性表。21. 對于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，用二叉鏈表存儲時(shí)，其指針總數(shù)為_個(gè)，其中_個(gè)指針是空閑的。22. 在稀疏矩陣所對應(yīng)的三元組線性表中，每個(gè)三元組元素按_為主序、_為輔序的次序排列。23. 一顆深度為K且有_個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹。24. 若對一棵完全二叉樹從0開始進(jìn)行結(jié)點(diǎn)的編號，并按此編

14、號把它順序存儲到一維數(shù)組A中，即編號為0的結(jié)點(diǎn)存儲到A0中。其余類推，則Ai元素的左孩子元素為_，雙親元素為_。25. 對于線性表（78，4，56，30，65）進(jìn)行哈希存儲時(shí)，若選用H（K）=K %5作為哈希函數(shù)，則哈希地址為0的元素有_個(gè)，哈希地址為4的有_個(gè)。26. 以折半查找方法從長度為8的有序表中查找一個(gè)元素時(shí)，平均查找長度為_。27. 假定一個(gè)有向圖的頂點(diǎn)集為a,b,c,d,e,f，邊集,，則出度為0的頂點(diǎn)個(gè)數(shù)為_，入度為1的頂點(diǎn)個(gè)數(shù)為_。28. 設(shè)有向圖G中有向邊的集合E=，則該圖的一種拓?fù)湫蛄袨開。29. 對于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)進(jìn)行鏈接存儲時(shí)，其二叉鏈表中的指針域的總數(shù)

15、為2n個(gè)，其中_個(gè)用于鏈接孩子結(jié)點(diǎn)，_個(gè)空閑著。30. 設(shè)有向圖中不存在有向邊，則其對應(yīng)的鄰接矩陣A中的數(shù)組元素Aij的值等于_。31. 根據(jù)初始關(guān)鍵字序列(19，22，01，38，10)建立的二叉排序樹的高度為_。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)入一個(gè)棧式結(jié)構(gòu)的車站，具體寫出這四輛列車開出車站的

16、所有可能的順序。至少有14種。 全進(jìn)之后再出情況，只有1種：4，3，2，1 進(jìn)3個(gè)之后再出的情況，有3種，3,4,2,1 3,2,4,1 3,2,1,4 進(jìn)2個(gè)之后再出的情況，有5種，2,4,3,1 2,3,4,1 2,1, 3,4 2,1,4,3 2,1,3,4 進(jìn)1個(gè)之后再出的情況，有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)造的最小生成樹的過程

17、。（過程略）6. 請畫出右圖的鄰接矩陣和鄰接表。7. 試比較順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)缺點(diǎn)。在什么情況下用順序表比鏈表好？在什么情況下用鏈表比順序表好？ 順序存儲時(shí)，相鄰數(shù)據(jù)元素的存放地址也相鄰（邏輯與物理統(tǒng)一）；要求內(nèi)存中可用存儲單元的地址必須是連續(xù)的。優(yōu)點(diǎn)：存儲密度大（1？），存儲空間利用率高。缺點(diǎn)：插入或刪除元素時(shí)不方便。鏈?zhǔn)酱鎯r(shí)，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲空間分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針優(yōu)點(diǎn)：插入或刪除元素時(shí)很方便，使用靈活。缺點(diǎn)：存儲密度小，存儲空間利用率低。順序表適宜于做查找這樣的靜態(tài)操作；鏈表宜于做插入、刪除這樣的動態(tài)操作。若線性表的

18、長度變化不大，且其主要操作是查找，則采用順序表；若線性表的長度變化較大，且其主要操作是插入、刪除操作，則采用鏈表。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) a 和頂點(diǎn) c 是關(guān)節(jié)點(diǎn)10. 給定表19，14，22，01，66，21，83，27，56，13，10 試按元素在表中的順序構(gòu)造一棵二叉排序樹； 判斷該二叉排序樹是否平衡，若不平衡，調(diào)整其為平衡二叉樹。、請說明樹型結(jié)構(gòu)和線性結(jié)構(gòu)的相同和不同之處。二叉排序樹為： 二叉平衡樹： 四算法設(shè)計(jì)題1 假設(shè)某個(gè)單項(xiàng)循環(huán)鏈表的長度大于1，且表中既無頭結(jié)點(diǎn)也無頭指針。已知S為指向鏈表中某個(gè)結(jié)點(diǎn)的指針，試編寫算法在鏈表中刪除指針S所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。 Status DelPrior(LinkList &S,ElemType &e)/S指向鏈表中某個(gè)節(jié)點(diǎn)，前驅(qū)結(jié)點(diǎn)賦值給參數(shù)e2 編寫遞歸算法，計(jì)算一棵以二叉鏈表表示的樹的所有結(jié)點(diǎn)中度為1的結(jié)點(diǎn)個(gè)數(shù)。void