數(shù)據(jù)結(jié)構(gòu)含答案

1、數(shù)據(jù)結(jié)構(gòu)綜合練習一、選擇題1 .數(shù)據(jù)的存儲結(jié)構(gòu)包括順序、鏈接、散列和()4種基本類型。A索引B數(shù)組C集合D向量2 .下面程序的時間復雜性的量級為()。inti=0,s1=0,s2=0;while(i+<n)if(i%2)s1+=i;elses2+=i;A.O(1)B.O(1bn)C.O(n)D.O(2n)3 .下面程序段的時間復雜度為()。for(inti=0;i<m;i+)for(intj=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個元素(1WiWn+1)位置插入一個元素

2、時，需要從后向前依次后移()個元素。A.n-iB.n-i+lC.n-i-lD.i5 .在一個長度為n的順序存儲結(jié)構(gòu)的線性表中，刪除第i個元素(1WiWn+1)時，需要從前向后依次后移()個元素。A.n-iB.n-i+lC.n-i-lD.i6 .在一個長度為n的線性表中，刪除值為x的元素時需要比較元素和移動元素的總次數(shù)為()。A.(n+1)/2B.n/2C.nD.n+17 .在一個順序表中的任何位置插入一個元素的時間復雜度為()。A.O(n)B.O(n/2)C.O(1)D.O(n2)8 .線性表的鏈式存儲比順序存儲更有利于進行()操作。A.查找B.表尾插入和刪除C按值插入和刪除D.表頭的插入和刪

3、除9 .線性表的順序存儲比鏈式存儲更有利于進行（）操作。A.查找B.表尾插入和刪除C.按值插入和刪除D.表頭的插入和刪除10 .在一個表頭指針為ph的單鏈表中，若要向表頭插入一個由指針p指向的結(jié)點，則應(yīng)執(zhí)行（）操作。A.ph=p;p->next=ph;B.p->next=ph;ph=p;C.p->next=ph;p=ph;D.p->next=ph->next;ph->next=p;11 .在一個表頭指針為ph的單鏈表中，若要在指針q所指結(jié)點的后面插入一個由指針p所指向的結(jié)點，則執(zhí)行（）操作。A. q->next=p->next;p->nex

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

5、t;next=q;13 .棧的插入和刪除操作在（）進行。A.棧頂B.棧底C.任意位置D.指定位置14 .若讓元素1,2,3,4依次進棧，則出棧次序不可能出現(xiàn)（）的情況。A.3,2,1,4B.2,1,4,3C.4,3,2,1D.1,4,2,3.15 .假定一個順序循環(huán)隊列的隊首和隊尾指針分別用f和r表示，則判斷隊空的條件為（）。A.f+1=rB.r+1=fC.f=0D.f=r16 .假定一個順序循環(huán)隊列存儲于數(shù)組aN,其隊首和隊尾指針分別用f和r表示，則判斷隊滿的條件為（）。A.（r-1）%N=fB.（r+1）%N=fC.（f-1）%N=rD.（f+1）%N=r17 .二維數(shù)組A12,10采用行

6、優(yōu)先存儲，每個數(shù)據(jù)元素占用4個存儲單元，該數(shù)組的首地址（A0,0的地址）為1200,則A6,5的地址為（）。A.1400B.1404C.1372D.146018 .在一棵具有n個結(jié)點的二叉樹中，所有結(jié)點的空子樹個數(shù)等于（）。A.nB.n-1C.n+1D.2n19 .有如圖1所示的一棵二叉樹，則該二叉樹的中序遍歷序列為（）。A.ABCDEFGB.CDBGFEAC.CBDAEGFD.ABECDFG20 .有如圖1所示的一棵二叉樹，則該二叉樹的先序遍歷序列為（）。A.ABCDEFGB.CDBGFEAC.CBDAEGFD.ABECDFG21 .有如圖1所示的一棵二叉樹，則該二叉樹的后序便利序列為（）。

7、A.ABCDEFGB.CDBGFEAC.CBDAEGFD.ABECDFG22 .利用n個值生成的哈夫曼樹中共有（）個結(jié)-、點。A.nB.n+1C.2nD.2n-1:，三23 .利用3,6,8,12這4個值作為葉子結(jié)尸（點的權(quán)，生成一棵哈夫曼樹，該樹的帶一權(quán)路徑長度為（）。A.55B.29C.58D.38圖j-24 .在一個具有n個頂點的無向圖中，若具有e條邊，則所有頂點的度數(shù)為（）。A.nB.eC.n+eD.2e25 .在一個具有n個頂點和e條邊的無向圖的鄰接矩陣中，表示邊存在的元素（又稱為有效元素）的個數(shù)為（）。A.nB.neC.eD.2e26 .若一個圖的邊集為（A,B）（A,C）（B,D

8、）（C,F）（D,E）（D,F）,則從頂點A開始對該圖進行深度優(yōu)先搜索，得到的頂點序列可能為()A.ABCFDEB.ACFDEBC.ABDCFED.ABDFEC27 .若一個圖的邊集為(A,B)(A,C)(B,D)(C,F)(D,E)(D,F),則從頂點A開始對該圖進行廣度優(yōu)先搜索，得到的頂點序列可能為()。A.ABCDEFB.ABCFDEC.ABDCEFD.ACBFDE28 .對于順序存儲的有序表(5,12,20,26,37,42,46,50,64),若采用二分查找，則查找元素26的查找長度為()。A.2B.3C.4D.529 .若根據(jù)查找表(23,44,36,48,52,73,64,58)

9、建立線性哈希表，采用H(K)=K%13計算哈希地址，則元素64的哈希地址為()。A.4B.8C.12D.1330 .若根據(jù)查找表(23,44,36,48,52,73,64,58)建立線形哈希表，采用H(K)=K%13計算哈希地址，則哈希地址為3的元素個數(shù)為()。A.1B.2C.3D.4答案為031 .若一個元素序列基本有序，則選用()方法較快。A.直接插入排序B.簡單選擇排序C.堆排序D.快速排序二、填空題1 .數(shù)據(jù)的邏輯結(jié)構(gòu)可分為和兩大類。線性；非線性2 .數(shù)據(jù)的存儲結(jié)構(gòu)被分為，,和4種。順序；鏈式；索引；散列存儲結(jié)構(gòu)3 .一種數(shù)據(jù)結(jié)構(gòu)的元素集合K和它的二元關(guān)系R為：K=a,b,c,d,e,

10、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)。線性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>貝U該數(shù)據(jù)結(jié)構(gòu)具有結(jié)構(gòu)。非線性5 .線性表的兩種存儲結(jié)構(gòu)分別為和。順序；鏈式6 .在一個單鏈表中刪除指針p所指向結(jié)點的后繼結(jié)點時，需要把的值賦

11、給p->next指針域。.p->next->next7 .棧又稱為表，隊列又稱為表。先進后出；先進先出8 .假定一個鏈棧的棧頂指針為top,每個結(jié)點包含值域data和指針域next,當p所指向的結(jié)點入棧時，則首先執(zhí)行操作，然后執(zhí)行操作。.p->next=top;top=pABCE圖2DGIHF9 .隊列的插入操作在進行，刪除操作在進行。隊尾；對頭10 .在一棵二叉樹中，假定雙分支結(jié)點數(shù)為5個，單分支結(jié)點數(shù)為6個，則葉子結(jié)點數(shù)為。611 .對于一棵二叉樹，若一個結(jié)點的編號i,若它的左孩子結(jié)點存在，則其編號為，若右孩子結(jié)點存在，則其編號為，若雙親結(jié)點存在，則其編號為。2i;

12、2i+1;i/212 .一個森林轉(zhuǎn)換成二叉樹后如圖1.9所示，則該森林/7k中包含棵樹。313 .若由3,6,8,12,10作為葉子結(jié)點的值生成一棵哈夫曼樹，則該樹的深度為，帶權(quán)路徑長度為。''<'、二4;8714 .一種數(shù)據(jù)結(jié)構(gòu)的元素集合K和它的二元關(guān)系R為：圖L9K=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),進行散列存儲，采用H(K)=K%7作為哈希函數(shù)，采用線性探測再散列法處理沖突，則在建立哈希表過程中，將會碰

13、到次沖突，平均查找長度為。5；216 .若對一組記錄(46,79,56,38,40,80,35,50,74)進行直接插入排序，當把第8個記錄插入到前面已排序的有序表時，為尋找插入位置需比較次。4三、簡答題1.已知一棵二叉樹的中序遍歷序列為CDBAEGF先序遍歷序列為ABCDEFG試問能不能唯一確定一棵二叉樹？若能，畫出該二叉樹。若給定先序遍歷序列和后序遍歷序列，能否唯一確定？18.(1)由中序遍歷序列和先序遍歷序列，或中序遍歷序列和后序遍歷序列，可以唯一確定一顆二叉樹。由先序序列知，根結(jié)點最先被訪問，就可確定根結(jié)點為A,而又由中序序列得知一棵樹的根結(jié)點是其左，右子樹的分隔點，從而可確定以A為根

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

15、列出每一遍排序后關(guān)鍵字的排列次序，并統(tǒng)計每遍排序進行的關(guān)鍵字比較次數(shù)。初始關(guān)鍵字序列為：(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次后成為：1(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),試畫出對應(yīng)平均查找長度：ASL=(1+2X2+3X4+4X3)/10=2.9折半查找判定樹如圖1.31所示。7 .設(shè)有一組關(guān)鍵字(17,13,14,153,29,35)需插入到表長為1