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

1、數(shù)據(jù)結(jié)構(gòu)綜合練習(xí)一、選擇題 1數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)包括順序、鏈接、散列和（ ）4種基本類型。 A索引 B數(shù)組 C集合 D向量 2下面程序的時(shí)間復(fù)雜性的量級為（）。 int i=0，s1=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下面程序段的時(shí)間復(fù)雜度為（ ）。 for(int i=0;im;i+) for(int j=0;jnext=ph; B. p-next=ph; ph=p; C. p-next=ph; p=ph; D. p-next=ph-next; ph-next=p; 11.

2、 在一個(gè)表頭指針為ph的單鏈表中，若要在指針q所指結(jié)點(diǎn)的后面插入一個(gè)由指針p所指向的結(jié)點(diǎn)，則執(zhí)行（）操作。 A. q-next=p-next; 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=

3、q-next-next; q-next=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，3 C.4，3，2，1 D.1，4，2，3. 15. 假定一個(gè)順序循環(huán)隊(duì)列的隊(duì)首和隊(duì)尾指針分別用f和r表示，則 判斷隊(duì)空的條件為（）。 A.f+1=r B.r+1=f C.f=0 D.f=r 16. 假定一個(gè)順序循環(huán)隊(duì)列存儲(chǔ)于數(shù)組aN，其隊(duì)首和隊(duì)尾指針分別 用f和r表示，則判斷隊(duì)滿的條件為（）。 A.（r-1）%N=f B.（r+1）%N=f C.

4、（f-1）%N=r D.（f+1）%N=r 17. 二維數(shù)組A12,10采用行優(yōu)先存儲(chǔ)，每個(gè)數(shù)據(jù)元素占用4個(gè)存儲(chǔ) 單元，該數(shù)組的首地址（A0，0的地址）為1200，則A6，5的 地址為（）。 A.1400 B.1404 C.1372 D.1460 18.在一棵具有n個(gè)結(jié)點(diǎn)的二叉樹中，所有結(jié)點(diǎn)的空子樹個(gè)數(shù)等于（）。 A.n B.n-1 C.n+1 D.2n 19.有如圖1所示的一棵二叉樹，則該二叉樹的中序遍歷序列為（）。 A. ABCDEFG B. CDBGFEA C. CBDAEGF D. ABECDFG 20.有如圖1所示的一棵二叉樹，則該二叉樹的先序遍歷序列為（）。 A.ABCDEFG B

5、.CDBGFEA C.CBDAEGF D.ABECDFG 21.有如圖1所示的一棵二叉樹，則該二叉樹的后序便利序列為（）。 A.ABCDEFG B.CDBGFEA C.CBDAEGF D.ABECDFG 22.利用n個(gè)值生成的哈夫曼樹中共有（）個(gè)結(jié)點(diǎn)。 A.n B.n+1 C.2n D.2n-1 23.利用3，6，8，12這4個(gè)值作為葉子結(jié)點(diǎn)的權(quán)，生成一棵哈夫曼樹，該樹的帶權(quán)路徑長度為（）。 A.55 B.29 C.58 D.38 24.在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中，若具有e條邊，則所有頂點(diǎn)的度數(shù)為（）。 A.n B.e C.n+e D.2e 25.在一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖的鄰接矩陣

6、中，表示邊存在的元素（又稱為有效元素）的個(gè)數(shù)為（）。 A.n B.ne C.e D.2e 26.若一個(gè)圖的邊集為（A，B）（A，C）（B，D）（C，F(xiàn)）（D，E）（D，F(xiàn)），則從頂點(diǎn)A開始對該圖進(jìn)行深度優(yōu)先搜索，得到的頂點(diǎn)序列可能為（）。 A. ABCFDE B. ACFDEB C. ABDCFE D. ABDFEC 27.若一個(gè)圖的邊集為（A，B）（A，C）（B，D）（C，F(xiàn)）（D，E）（D，F(xiàn)），則從頂點(diǎn)A開始對該圖進(jìn)行廣度優(yōu)先搜索，得到的頂點(diǎn)序列可能為（）。 A.ABCDEF B.ABCFDE C.ABDCEF D.ACBFDE 28.對于順序存儲(chǔ)的有序表（5，12，20，26，37，4

7、2，46，50，64）， 若采用二分查找，則查找元素26的查找長度為（）。 A.2 B.3 C.4 D.5 29.若根據(jù)查找表（23，44，36，48，52，73，64，58）建立線性哈希表，采用H（K）=K%13計(jì)算哈希地址，則元素64的哈希地址為（）。 A.4 B.8 C.12 D.13 30.若根據(jù)查找表（23，44，36，48，52，73，64，58）建立線形哈希表，采用H（K）=K%13計(jì)算哈希地址，則哈希地址為3的元素個(gè)數(shù)為（）。A.1 B.2 C.3 D.4 答案為031.若一個(gè)元素序列基本有序，則選用（）方法較快。 A.直接插入排序 B.簡單選擇排序 C.堆排序 D.快速排序二

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

9、先進(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ì)尾；對頭10.在一棵二叉樹中，假定雙分支結(jié)點(diǎn)數(shù)為5個(gè)， 單分支結(jié)點(diǎn)數(shù)為6個(gè)，則葉子結(jié)點(diǎn)數(shù)為_。 611.對于一棵二叉樹，若一個(gè)結(jié)點(diǎn)的編號(hào)i，若它的左孩子結(jié)點(diǎn)存在， 則其編號(hào)為_，若右孩子結(jié)點(diǎn)存在，則其編號(hào)為_，若雙親結(jié)點(diǎn)存在，則其編號(hào)為_。 2i；2i+1；i/212.一個(gè)森林轉(zhuǎn)換成二叉樹后如圖1.9所示，則該森林中包含_棵樹。313.若由3，6

10、，8，12，10作為葉子結(jié)點(diǎn)的值生成一棵哈夫曼樹，則該樹的深度為_，帶權(quán)路徑長度為_。 4；8714.一種數(shù)據(jù)結(jié)構(gòu)的元素集合K和它的二元關(guān)系R為： K=1，2，3，4，5，6 R=（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)行散列存儲(chǔ)，采用H（K）=K%7作為哈希函數(shù)，采用線性探測再散列法處理沖突，則在建立哈希表過程中，將會(huì)碰到_次沖突，平均查找長度為_。 5；216.若對一組記錄（46，79，56，38，40，80，35，50，74）進(jìn)行直接插入排序，當(dāng)把第8個(gè)記錄插

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

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

13、。 初始關(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次后成為： （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，39，45，56，58，63，74，6），試畫出對應(yīng)的二分查找判定樹，求出其平均查找長度。 折半查找判定樹如圖131所示。 平均查找長度：ASL=（1+223443）/10=2.97. 設(shè)有一組關(guān)鍵字（17，13，14，153，29，35）需插入到表長為12的散列表中，請回答下列問題： （1）設(shè)