大數(shù)據(jù)結(jié)構(gòu)含問(wèn)題詳解

1、實(shí)用標(biāo)準(zhǔn)數(shù)據(jù)結(jié)構(gòu)綜合練習(xí)一、選擇題1 .數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)包括順序、鏈接、散列和()4種基本類型。A索引B數(shù)組C集合D向量2 .下面程序的時(shí)間復(fù)雜性的量級(jí)為()。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 .下面程序段的時(shí)間復(fù)雜度為()。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 .在一個(gè)長(zhǎng)度為n的順序存儲(chǔ)結(jié)構(gòu)的線性表中，向第i個(gè)元素(KiWn+1)位置插入一

2、個(gè)元素時(shí)，需要從后向前依次后移()個(gè)元素。A.n-iB.n-i+lC.n-i-lD.i5 .在一個(gè)長(zhǎng)度為n的順序存儲(chǔ)結(jié)構(gòu)的線性表中，刪除第i個(gè)元素(1WiWn+1)時(shí)，需要從前向后依次后移()個(gè)元素。A.n-iB.n-i+lC.n-i-lD.i6 .在一個(gè)長(zhǎng)度為n的線性表中，刪除值為x的元素時(shí)需要比較元素和移動(dòng)元素的總次數(shù)為()。A.(n+1)/2B.n/2C.nD.n+17 .在一個(gè)順序表中的任何位置插入一個(gè)元素的時(shí)間復(fù)雜度為()。A.O(n)B.O(n/2)C.O(1)D.O(n2)8 .線性表的鏈?zhǔn)酱鎯?chǔ)比順序存儲(chǔ)更有利于進(jìn)行()操作。文檔大全實(shí)用標(biāo)準(zhǔn)A.查找B.表尾插入和刪除C按值插入和

3、刪除D.表頭的插入和刪除9 .線性表的順序存儲(chǔ)比鏈?zhǔn)酱鎯?chǔ)更有利于進(jìn)行（）操作。A.查找B.表尾插入和刪除C.按值插入和刪除D.表頭的插入和刪除10 .在一個(gè)表頭指針為ph的單鏈表中，若要向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn)，則應(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 .在一個(gè)表頭指針為ph的單鏈表中，若要在指針q所指結(jié)點(diǎn)的后面插入一個(gè)由指針p所指向的結(jié)點(diǎn)，則執(zhí)行（）操作。A. q->next=p->nex

4、t;p->next=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 .在一個(gè)單鏈表HL中，若要?jiǎng)h除由指針q所指向結(jié)點(diǎn)的后繼結(jié)點(diǎn)（若存在的話），則執(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-&g

5、t;next;q->next=q;13 .棧的插入和刪除操作在（）進(jìn)行。A.棧頂B.棧底C.任意位置D.指定位置14 .若讓元素1,2,3,4依次進(jìn)棧，則出棧次序不可能出現(xiàn)（）的情況。A.3,2,1,4B.2,1,4,3C.4,3,2,1D.1,4,2,3.15 .假定一個(gè)順序循環(huán)隊(duì)列的隊(duì)首和隊(duì)尾指針?lè)謩e用f和r表示，則判斷隊(duì)空的條件為（）。A.f+1=rB.r+1=fC.f=0D.f=r16 .假定一個(gè)順序循環(huán)隊(duì)列存儲(chǔ)于數(shù)組aN,其隊(duì)首和隊(duì)尾指針?lè)謩e文檔大全實(shí)用標(biāo)準(zhǔn)用f和r表示，則判斷隊(duì)滿的條件為（）。A.（r-1）%N=fB.（r+1）%N=fC.（f-1）%N=rD.（f+1）%N

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

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

8、(A,B)(A,C)(B,D)(C,F)(D,E)(D,F),則從頂點(diǎn)A開(kāi)始文檔大全實(shí)用標(biāo)準(zhǔn)對(duì)該圖進(jìn)行深度優(yōu)先搜索，得到的頂點(diǎn)序列可能為()。A.ABCFDEB.ACFDEBC.ABDCFED.ABDFEC27 .若一個(gè)圖的邊集為(A,B)(A,C)(B,D)(C,F)(D,E)(D,F),則從頂點(diǎn)A開(kāi)始對(duì)該圖進(jìn)行廣度優(yōu)先搜索，得到的頂點(diǎn)序列可能為()。A.ABCDEFB.ABCFDEC.ABDCEFD.ACBFDE28 .對(duì)于順序存儲(chǔ)的有序表(5,12,20,26,37,42,46,50,64),若采用二分查找，則查找元素26的查找長(zhǎng)度為()。A.2B.3C.4D.529 .若根據(jù)查找表(2

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

10、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)。線性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 .線性表的兩種存儲(chǔ)結(jié)構(gòu)分別為和。順序；鏈?zhǔn)? .在一個(gè)單鏈表中

11、刪除指針p所指向結(jié)點(diǎn)的后繼結(jié)點(diǎn)時(shí)，需要把的值賦給p->next指針域。.p->next->next7 .棧又稱為表，隊(duì)列又稱為表。文檔大全實(shí)用標(biāo)準(zhǔn)先進(jìn)后出；先進(jìn)先出8 .假定一個(gè)鏈棧的棧頂指針為top,每個(gè)結(jié)點(diǎn)包含值域data和指針域next,當(dāng)p所指向的結(jié)點(diǎn)入棧時(shí)，則首先執(zhí)行操作，然后執(zhí)行操作。.p->next=top;top=pABCE圖2DGIHF9 .隊(duì)列的插入操作在進(jìn)行，刪除操作在進(jìn)行。隊(duì)尾；對(duì)頭10 .在一棵二叉樹(shù)中，假定雙分支結(jié)點(diǎn)數(shù)為5個(gè)，單分支結(jié)點(diǎn)數(shù)為6個(gè)，則葉子結(jié)點(diǎn)數(shù)為。611 .對(duì)于一棵二叉樹(shù)，若一個(gè)結(jié)點(diǎn)的編號(hào)i,若它的左孩子結(jié)點(diǎn)存在，則其編號(hào)為，若

12、右孩子結(jié)點(diǎn)存在，則其編號(hào)為，若雙親結(jié)點(diǎn)存在，則其編號(hào)為。2i;2i+1;i/212 .一個(gè)森林轉(zhuǎn)換成二叉樹(shù)后如圖1.9所示，則該森林/7k中包含棵樹(shù)。313 .若由3,6,8,12,10作為葉子結(jié)點(diǎn)的值生成一棵哈夫曼樹(shù)，則該樹(shù)的深度為，帶權(quán)路徑長(zhǎng)度為。''<'、二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 .假定對(duì)線性表(38,25,74,52,48),進(jìn)行散列存儲(chǔ)，采用H(K)=K%7作為哈希函

13、數(shù)，采用線性探測(cè)再散列法處理沖突，則在建立哈希表過(guò)程中，將會(huì)碰到次沖突，平均查找長(zhǎng)度為。5;216 .若對(duì)一組記錄(46,79,56,38,40,80,35,50,74)進(jìn)行直接插入排序，當(dāng)把第8個(gè)記錄插入到前面已排序的有序表時(shí)，為尋找插入位置需比較次。4三、簡(jiǎn)答題1.已知一棵二叉樹(shù)的中序遍歷序列為CDBAEGF先序遍歷序列為ABCDEFG試問(wèn)能不能唯一確定一棵二叉樹(shù)？若能，畫(huà)出該二叉樹(shù)。若給定先序遍歷序列和后序遍歷序列，能否唯一確定？18.(1)由中序遍歷序列和先序遍歷序列，或中序遍歷序列和后序遍歷序列，可以唯一確定一文檔大全實(shí)用標(biāo)準(zhǔn)顆二叉樹(shù)。由先序序列知，根結(jié)點(diǎn)最先被訪問(wèn)，就可確定根結(jié)點(diǎn)為

14、A,而又由中序序列得知一棵樹(shù)的根結(jié)點(diǎn)是其左，右子樹(shù)的分隔點(diǎn)，從而可確定以A為根的左子樹(shù)的結(jié)點(diǎn)為B,C,D,右子樹(shù)的結(jié)點(diǎn)為E,F,G。重復(fù)進(jìn)行就可得到二叉樹(shù)。(2)由先序遍歷序列和后序遍歷序列不能唯一確定一棵二叉樹(shù)。因?yàn)閮煞N遍歷方法只能確定根結(jié)點(diǎn)，而分不清左右子樹(shù)。2.將圖1.12所示的樹(shù)轉(zhuǎn)換成二叉樹(shù)。3.試分別畫(huà)出具有3個(gè)結(jié)點(diǎn)的樹(shù)和3個(gè)結(jié)點(diǎn)的二叉樹(shù)的所有不同形態(tài)。樹(shù)的狀態(tài)如圖1.21所示.3個(gè)結(jié)點(diǎn)的二叉樹(shù)的狀態(tài)如圖1.22所示d圖1.21看I.；4.假定用于通信的電文由8個(gè)字母組成，分別是A,B,C,D,E,F,G,和H,各字母在電文中出現(xiàn)的概率為：5%,25%,4%,7%,9%,12%,30

15、%,8%,試為8個(gè)字母設(shè)計(jì)哈夫文檔大全實(shí)用標(biāo)準(zhǔn)曼編碼。5.給出一組關(guān)鍵字(19,01,26,92,87,11,43,87,21),進(jìn)行冒泡排序，列出每一遍排序后關(guān)鍵字的排列次序，并統(tǒng)計(jì)每遍排序進(jìn)行的關(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.已知一個(gè)順序存儲(chǔ)的有序表為(15,26,34,的二分查找判定樹(shù)，求出其平均查找長(zhǎng)度。39,45,56,58,63,74,6),試畫(huà)出對(duì)應(yīng)折半查找判定樹(shù)如圖1.31所示。平均查找長(zhǎng)度：ASL=(1+2X2+3X4+4X3)/10=2.97.設(shè)有一組關(guān)鍵字(17,13,14,153,29,35)需插入到表長(zhǎng)為12的散列表中，請(qǐng)回答卜列問(wèn)題:文