數(shù)據結構(含規(guī)范標準答案)

1、!-數(shù)據結構綜合練習、選擇題1 .數(shù)據的存儲結構包括順序、鏈接、散列和（）4種基本類型。A索引B數(shù)組C集合D向量2 .下面程序的時間復雜性的量級為（）。int i=0，s1=0, s2=0;while ( i+<n)if (i%2)s1+=i;else s2+=i;A. 0(1) B.0(1bn) C.O ( n)D.O(2n) 3 .下面程序段的時間復雜度為（for(i nt i=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的順序存儲結構的線性表中,向第

2、i個元素（1 < i< n+1）位置插入一個元素時，需要從后向前依次后移（）個元素。A.n-i B.n-i+l C. n-i-l D.i5 .在一個長度為n的順序存儲結構的線性表中,刪除第 i個元素（1W iw n+1）時，需要從前向后依次后移（）個元素。A.n-i B.n-i+l C.n-i-l D.i 6 .在一個長度為n的線性表中，刪除值為 x的元素時需要比較元素和移動元素的總次數(shù)為（）。A.( n+1)/2 B. n/2 C.n D.n+1 7 .在一個順序表中的任何位置插入一個元素的時間復雜度為（）A. O(n) B. O( n/2) C. O(1) D. O(n2)8.

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

4、h的單鏈表中，若要在指針q所指結點的后面插入一個由指針P所 指向的結點，則執(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所指向結點的后繼結點（若存在的話），則執(zhí)行（）操作。A. p=q->n ext; p->n ext=q->n ext;B. p=q

5、->n ext; q->n 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依次進棧，則出棧次序不可能出現(xiàn)（ ）的 情況。A.3，2，1，4 B.2，1，4，3C.4，3，2，1 D.1，4，2，3.15.假定一個順序循環(huán)隊列的隊首和隊尾指針分別用f和r表示，則判斷隊空的條件為（）。A.f+1=r B.r+1=f C.f=0

6、 D.f=r16.假定一個順序循環(huán)隊列存儲于數(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ù)據元素占用4個存儲單元，該數(shù)組的首地址（A0, 0的地址）為1200，則A6 , 5的地址為（）。A.1400 B.1404 C.1372 D.146018.在一棵具有n個結點的二叉樹中，所有結點的空子樹個數(shù)等于（）。A.n B.n-1 C.n+1 D.2n19.有如圖1所示的一棵二叉樹，則該二叉樹的中序遍歷序列為()A. ABC

7、DEFG B. CDBGFEA C. CBDAEGF D. ABECDFG20.有如圖1所示的一棵二叉樹，則該二叉樹的先序遍歷序列為()A.ABCDEFG B.CDBGFEA C.CBDAEGF D.ABECDFG21.有如圖1所示的一棵二叉樹，則該二叉樹的后序便利序列為()A.ABCDEFG B.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.在一個具有

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

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

10、哈希地址為3的元素個數(shù)為()OA.1 B.2 C.3 D.4 答案為 031.若一個兀素序列基本有序,則選用（）方法較快。A.直接插入排序B.簡單選擇排序C.堆排序D.快速排序二、填空題1.數(shù)據的邏輯結構可分為和兩大類。線性；非線性2.數(shù)據的存儲結構被分為和4種。順序；鏈式；索引；散列存儲結構3.一種數(shù)據結構的元素集合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>則該數(shù)據結構具有結構。線性4.一種數(shù)據結構

11、的元素集合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>則該數(shù)據結構具有 結構。非線性5.線性表的兩種存儲結構分別為和O順序；鏈式6.在一個單鏈表中刪除指針 P所指向結點的后繼結點時，需要把的值賦給P->next指針域O .p->n ext->next7.棧又稱為.表，隊列又稱為表。先進后出； 先進先出8.假定一個鏈棧的棧頂指針為top ,每個結點包含值域data和指針域next，當p

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

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

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

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

16、26, 92, 87, 11, 43, 87,第一遍排序比較8次，交換6次后成為:(01, 19, 26,87, 11, 43, 87, 21,第二遍排序比較7次，交換3次后成為:(01, 19, 26,11 , 43, 87, 21, 87,第三遍排序比較6次，交換2次后成為:21)92)92)(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次。排序完畢。6.已知一個順序存儲的有序表為(15, 26, 34,39 , 45 , 56 , 58 , 63 , 74 , 6),試畫出對應的二分查找判定樹,求出其平均查找長度。折半查找判定樹如圖 1. 31所示。/10=2.9平均查找長度： ASL= (1+2 X 2 + 3X 4+ 4X 3)CD©、寢® © ©圖 317.設有一組關鍵字(17 , 13 , 14 , 153 , 29 , 35)需插入到表長為12的散列表中，請回答 下列問題:!-(1