1、數據結構綜合練習一、選擇題1 數據的存儲結構包括順序、鏈接、散列和()4種基本類型。A索引B數組C集合D向量2 .下面程序的時間復雜性的量級為()。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 .下面程序段的時間復雜度為()。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的順序存儲結構的線性表中，向第i

2、個元素(K i < n+1)位置插入一個元素時，需要從后向前依次后移()個元素。A.n-iB. n-i+IC. n-i-l D.i5在一個長度為n的順序存儲結構的線性表中，刪除第i個元素(K iw n+1)時，需要從前向后依次后移()個元素。A.n-iB. n-i+IC. n-i-l D.i6 在一個長度為n的線性表中，刪除值為x的元素時需要比較元素和移動元素的總次數為()。A.(n+1)/2 B.n/2 C.n D.n+17 在一個順序表中的任何位置插入一個元素的時間復雜度為()。A. 0(n) B. O(n/2) C. O(1) D. 0(n2)8. 線性表的鏈式存儲比順序存儲更有利

3、于進行()操作。A.查找B.表尾插入和刪除C按值插入和刪除D.表頭的插入和刪除9. 線性表的順序存儲比鏈式存儲更有利于進行（）操作。A.查找B.表尾插入和刪除C按值插入和刪除D.表頭的插入和刪除10. 在一個表頭指針為 ph的單鏈表中，若要向表頭插入一個由指針p指向的結點，則應執行（）操作。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所指結點的后面插入

4、一個由指針p所指向的結點，則執行（）操作。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所指向結點的后繼結點（若存在的話），則執行（）操作。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. 棧的插入和刪除操作在（）進行。A.棧頂B.棧底C.任意位置D.指定位置14. 若讓元素1，2，3，4依次進棧，則出棧次序不可能出現（）的情況。A.3，2，1，4 B.2，1，4，3C.4，3，2，1 D.1，4，2，3.f和r表示，則15. 假定一個順序循環隊列的隊首和隊尾指針分別用 判斷隊空的條件為（）。A.f+ 仁=B.r+ 仁=彳 C.f=0 D.f=r16.假定一個順序循環隊列

6、存儲于數組aN,其隊首和隊尾指針分別用f和r表示，則判斷隊滿的條件為()A. (r-1) %N=f B. (r+1) %N=fC. (f-1) %N=r D. (f+1) %N=r17. 二維數組A12,10采用行優先存儲，每個數據元素占用4個存儲單元，該數組的首地址（A0，0的地址）為1200，則A6，5的 地址為()。A.1400 B.1404 C.1372 D.146018. 在一棵具有n個結點的二叉樹中，所有結點的空子樹個數等于（）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個值生成的哈夫曼樹中共有（）個結 點。A.n B. n+1 C.2 n D.2 n-123. 利用3，6，8，12這4個值作為葉子結 點的權，生成一棵哈夫曼樹，該樹的帶 權路徑長度為（）。A.55 B.29 C.58 D.3824. 在一個具有n個頂點的無向圖中，若具

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

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. 若根據查找表（23, 44, 36，48，52，73, 64，58）建立線性哈希表，采用H （K）=K%13計算哈希地址，則元素 64的哈希地址為（）。A.4 B.8 C.12 D.1330. 若根據查找表（23, 44, 36, 48, 52, 73, 64, 58）建立線形哈希表，采用H （K）=K%13計算哈希地址，則哈希地址為3的

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

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

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

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

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

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

16、列次序，并統計每遍排序進行的關鍵字比較次數。(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次。排序完畢。初始關鍵字序列為:1729圖1 . 2$6已知一個順序存儲的有序表為(15, 26 , 34, 39, 45, 56, 58, 63, 74 , 6),試畫出對應的二分查找判定樹，求出其平均查找長度。折半查找判定樹如圖1. 31所示。平均查找長度： ASL= (1+2 X 2 + 3X 4+ 4X 3) /10=2.9Hk 317. 設有一組關鍵字(17, 13, 14, 153, 29, 35)需插入到表