1、數(shù)據(jù)結(jié)構(gòu)綜合練習(xí)一、選擇題1 數(shù)據(jù)的存儲結(jié)構(gòu)包括順序、鏈接、散列和()4種基本類型。A索引B數(shù)組C集合D向量2 .下面程序的時間復(fù)雜性的量級為()。inti=0 , s仁0, s2=0;while (i+<n)if (i%2)s1+=i;else s2+=i;A. O(1) B.O(1bn) C.O ( n)D.O(2n)3 .下面程序段的時間復(fù)雜度為()。for(i nti=0;i<m;i+)for(i nt j=0;j <n ;j+)aij=i*j；A. O(m2) B.O( n2) C.O(m+n) D.O(m* n)4 .在一個長度為n的順序存儲結(jié)構(gòu)的線性表中，向第i

2、個元素(K i < n+1)位置插入一個元素時，需要從后向前依次后移()個元素。A.n-iB. n-i+IC. n-i-l D.i5在一個長度為n的順序存儲結(jié)構(gòu)的線性表中，刪除第i個元素(K iw n+1)時，需要從前向后依次后移()個元素。A.n-iB. n-i+IC. n-i-l D.i6 在一個長度為n的線性表中，刪除值為x的元素時需要比較元素和移動元素的總次數(shù)為()。A.(n+1)/2 B.n/2 C.n D.n+17 在一個順序表中的任何位置插入一個元素的時間復(fù)雜度為()。A. 0(n) B. O(n/2) C. O(1) D. 0(n2)8. 線性表的鏈?zhǔn)酱鎯Ρ软樞虼鎯Ω欣?/p>

3、于進(jìn)行()操作。A.查找B.表尾插入和刪除C按值插入和刪除D.表頭的插入和刪除9. 線性表的順序存儲比鏈?zhǔn)酱鎯Ω欣谶M(jìn)行（）操作。A.查找B.表尾插入和刪除C按值插入和刪除D.表頭的插入和刪除10. 在一個表頭指針為 ph的單鏈表中，若要向表頭插入一個由指針p指向的結(jié)點，則應(yīng)執(zhí)行（）操作。A. ph=p; p_>n ext=ph; B. p_>n ext=ph; ph=p;C. p_>n ext=ph; p=ph; D. p_>n ext=ph->n ext; ph->n ext=p;11. 在一個表頭指針為 ph的單鏈表中，若要在指針q所指結(jié)點的后面插入

4、一個由指針p所指向的結(jié)點，則執(zhí)行（）操作。A. q->n ext=p->n ext; p->n ext=q;B. p_>n ext=q _>n ext; q=p;C. q_>n ext=p->n ext; p_>n ext=q;D. p_>n ext=q _>n ext; q_>n ext=p;12. 在一個單鏈表HL中，若要刪除由指針 q所指向結(jié)點的后繼結(jié)點（若存在的話），則執(zhí)行（）操作。A. p=q _>n ext; p_>n ext=q _>n ext;B. p=q _>n ext; q_>n

5、 ext=p;C. p=q _>n ext; q_>n ext=p->n ext;D. q->n ext=q->n ext->n ext; q->n ext=q;13. 棧的插入和刪除操作在（）進(jìn)行。A.棧頂B.棧底C.任意位置D.指定位置14. 若讓元素1，2，3，4依次進(jìn)棧，則出棧次序不可能出現(xiàn)（）的情況。A.3，2，1，4 B.2，1，4，3C.4，3，2，1 D.1，4，2，3.f和r表示，則15. 假定一個順序循環(huán)隊列的隊首和隊尾指針分別用 判斷隊空的條件為（）。A.f+ 仁=B.r+ 仁=彳 C.f=0 D.f=r16.假定一個順序循環(huán)隊列

6、存儲于數(shù)組aN,其隊首和隊尾指針分別用f和r表示，則判斷隊滿的條件為()A. (r-1) %N=f B. (r+1) %N=fC. (f-1) %N=r D. (f+1) %N=r17. 二維數(shù)組A12,10采用行優(yōu)先存儲，每個數(shù)據(jù)元素占用4個存儲單元，該數(shù)組的首地址（A0，0的地址）為1200，則A6，5的 地址為()。A.1400 B.1404 C.1372 D.146018. 在一棵具有n個結(jié)點的二叉樹中，所有結(jié)點的空子樹個數(shù)等于（）A.n B.n-1 C.n+1 D.2 n19. 有如圖1所示的一棵二叉樹，則該二叉樹的中序遍歷序列為（）A. ABCDEFG B. CDBGFEA C.

7、CBDAEGF D. ABECDFG20. 有如圖1所示的一棵二叉樹，則該二叉樹的先序遍歷序列為（）A.ABCDEFG B.CDBGFEA C.CBDAEGF D.ABECDFG21. 有如圖1所示的一棵二叉樹，則該二叉樹的后序便利序列為（）A.ABCDEFGB.CDBGFEA C.CBDAEGF D.ABECDFG22. 利用n個值生成的哈夫曼樹中共有（）個結(jié) 點。A.n B. n+1 C.2 n D.2 n-123. 利用3，6，8，12這4個值作為葉子結(jié) 點的權(quán)，生成一棵哈夫曼樹，該樹的帶 權(quán)路徑長度為（）。A.55 B.29 C.58 D.3824. 在一個具有n個頂點的無向圖中，若具

8、有 e 條邊，則所有頂點的 度數(shù)為()。A. nB.eC. n+eD.2e25. 在一個具有n個頂點和e條邊的無向圖的鄰接矩陣中，表示邊存 在的元素（又稱為有效元素）的個數(shù)為（）。A.n B. ne C.eD.2e26. 若一個圖的邊集為（ A，B）（ A，C）（B，D）（ C,F）（ D，E）（ D,F），則從頂點A開始 對該圖進(jìn)行深度優(yōu)先搜索，得到的頂點序列可能為（）A. ABCFDEB. ACFDEB C. ABDCFE D. ABDFEC27. 若一個圖的邊集為（ A，B）（ A，C）（B, D）（ C, F）（ D，E）（ D, F），則從頂點A開始對該圖進(jìn)行廣度優(yōu)先搜索，得到的頂點

9、序列可能為（）。A.ABCDEF B.ABCFDE C.ABDCEF D.ACBFDE28. 對于順序存儲的有序表（5，12, 20，26，37，42，46，50，64），若采用二分查找，則 查找元素26的查找長度為（）。A.2 B.3 C.4 D.529. 若根據(jù)查找表（23, 44, 36，48，52，73, 64，58）建立線性哈希表，采用H （K）=K%13計算哈希地址，則元素 64的哈希地址為（）。A.4 B.8 C.12 D.1330. 若根據(jù)查找表（23, 44, 36, 48, 52, 73, 64, 58）建立線形哈希表，采用H （K）=K%13計算哈希地址，則哈希地址為3的

10、元素個數(shù)為（）。A.1 B.2 C.3 D.4 答案為 031. 若一個元素序列基本有序，則選用（）方法較快。A.直接插入排序 B.簡單選擇排序 C.堆排序D.快速排序二、填空題1. 數(shù)據(jù)的邏輯結(jié)構(gòu)可分為和_兩大類。線性；非線性2. 數(shù)據(jù)的存儲結(jié)構(gòu)被分為 _, , 和_4種。順序；鏈?zhǔn)剑凰鞴瓅；散列存儲結(jié)構(gòu)3. 一種數(shù)據(jù)結(jié)構(gòu)的元素集合K和它的二元關(guān)系R為：K=a,b,c,d,e,f,g,hR=<a,b>, <b,c>, <c,d>, <d,e>, <e,f>, <f,g>, <g,h>則該數(shù)據(jù)結(jié)構(gòu)具有結(jié)構(gòu)。線性

11、4. 一種數(shù)據(jù)結(jié)構(gòu)的元素集合K和它的二元關(guān)系R為：K=a,b,c,d,e,f,g,hR=<d,b>, <d,g>, <b,a>, <b,c>, <g,e>, <g,h>, <e,f>則該數(shù)據(jù)結(jié)構(gòu)具有結(jié)構(gòu)。非線性5. 線性表的兩種存儲結(jié)構(gòu)分別為 和。順序；鏈?zhǔn)?. 在一個單鏈表中刪除指針p所指向結(jié)點的后繼結(jié)點時，需要把 的值賦給p->next指針域。.p->next->next7棧又稱為 表，隊列又稱為 表。先進(jìn)后出；先進(jìn)先出8假定一個鏈棧的棧頂指針為top，每個結(jié)點包含值域 data和指針域n

12、ext，當(dāng)p所指向的結(jié)點入棧時，則首先執(zhí)行 操作，然后執(zhí)行 操作。.p->next二top;top二pABCE圖 2DGIHF9隊列的插入操作在 進(jìn)行，刪除操作在 進(jìn)行。隊尾；對頭10. 在一棵二叉樹中，假定雙分支結(jié)點數(shù)為 5個，單分支結(jié)點數(shù)為6個，則葉子結(jié)點數(shù)為 。611. 對于一棵二叉樹，若一個結(jié)點的編號i，若它的左孩子結(jié)點存在,則其編號為 ，若右孩子結(jié)點存在，則其編號為 ，若雙親結(jié)點存在，則其編號為。2i; 2i+1; i/212. 一個森林轉(zhuǎn)換成二叉樹后如圖1.9所示，則該森林中包含棵樹。313. 若由3, 6 , 8, 12, 10作為葉子結(jié)點的值生成一棵哈夫曼樹，則該樹的深度

13、為,帶權(quán)路徑長度為_4; 8714. 一種數(shù)據(jù)結(jié)構(gòu)的元素集合K和它的二元關(guān)系 R為:K=1, 2, 3, 4, 5, 6R= (1 , 2) (2, 3) (2 , 4) ( 3 , 4) ( 3 , 5) (3 , 6) (4 , 5) (4 , 6) 則該數(shù)據(jù)結(jié)構(gòu)具有數(shù)據(jù)結(jié)構(gòu)。圖狀15. 假定對線性表(38 , 25 , 74 , 52 , 48),進(jìn)行散列存儲，采用H (K) =K%7作為哈希函數(shù),采用線性探測再散列法處理沖突，則在建立哈希表過程中，將會碰到次沖突，平均查找長度為。 5; 216. 若對一組記錄(46 , 79 , 56 , 38 , 40 , 80 , 35 , 50

14、, 74)進(jìn)行直接插入排序，當(dāng)把第 8個記錄插入到前面已排序的有序表時，為尋找插入位置需比較 次。4三、簡答題 1.已知一棵二叉樹的中序遍歷序列為 CDBAEGF先序遍歷序列為 ABCDEFG試問能不能唯 一確定一棵二叉樹？若能，畫出該二叉樹。若給定先序遍歷序列和后序遍歷序列， 能否唯一 確定？18.(1)由中序遍歷序列和先序遍歷序列，或中序遍歷序列和后序遍歷序列，可以唯一確定顆二叉樹。由先序序列知，根結(jié)點最先被訪冋，就可確定根結(jié)點為A，而又由中序序列得知一棵樹的根結(jié)點是其左，右子樹的分隔點，從而可確定以A為根的左子樹的結(jié)點為 B,C,D,右子樹的結(jié)點為E,F,G。重復(fù)進(jìn)行就可得到二叉樹。（2

15、 ）由先序遍歷序列和后序遍歷序列不能唯一確定一棵二叉樹。因為兩種遍歷方法只能確定根結(jié)點，而分不清左右子樹。2將圖1.12所示的樹轉(zhuǎn)換成二叉樹。3試分別畫出具有 3個結(jié)點的樹和3個結(jié)點的二叉樹的所有不同形態(tài)。樹的狀態(tài)如圖1.21所示3個結(jié)點的二叉樹的狀態(tài)如圖1.22 所示電文中出現(xiàn)的概率為：5%，25%，4%，7%，9%，12%，30%，8%，試為 8 個字母設(shè)計哈夫4.假定用于通信的電文由8個字母組成，分別是A, B，C,D， E，F(xiàn)，G,和H，各字母在曼編碼。5給出一組關(guān)鍵字(19, 01, 26, 92, 87, 11 , 43, 87, 21),進(jìn)行冒泡排序，列出每一遍 排序后關(guān)鍵字的排

16、列次序，并統(tǒng)計每遍排序進(jìn)行的關(guān)鍵字比較次數(shù)。(19, 01, 26, 92, 87, 11, 43, 87,21)第一遍排序比較8次，交換6次后成為：(01, 19, 26, 87, 11, 43, 87, 21 ,92)第二遍排序比較7次，交換3次后成為：(01 , 19, 26, 11 , 43, 87, 21, 87,92)第三遍排序比較6次，交換2次后成為：(01, 19, 11, 26, 43, 21, 87, 87,92)第四遍排序比較5次，交換2次后成為：(01, 11, 19, 26, 21, 43, 87 , 87,92)第五遍排序比較4次，交換1次后成為：(01, 11, 19, 21, 26, 43, 87, 87,92)第六遍排序比較3次，交換0次。排序完畢。初始關(guān)鍵字序列為:1729圖1 . 2$6已知一個順序存儲的有序表為(15, 26 , 34, 39, 45, 56, 58, 63, 74 , 6),試畫出對應(yīng)的二分查找判定樹，求出其平均查找長度。折半查找判定樹如圖1. 31所示。平均查找長度： ASL= (1+2 X 2 + 3X 4+ 4X 3) /10=2.9Hk 317. 設(shè)有一組關(guān)鍵字(17, 13, 14, 153, 29, 35)需插入到表