1、數(shù) 據(jù) 結(jié) 構(gòu) 習(xí) 題 集 一、選擇題 .在一個(gè)長(zhǎng)度為n的順序表中，向第i個(gè)元素(1in+1)之前插入一個(gè)新元素時(shí)，需向后移動(dòng) B 個(gè)元素。 A. n-1 B. n-i+1 C. n-i-1 D. i .在一個(gè)具有n個(gè)單元的順序棧中，假定以地址低端作為棧底，以top作為棧頂指針， 則當(dāng)做退棧處理時(shí)，top變化為 C 。 A. top不變 . top -n C. toptop-1 D. top=top+1 .向順序棧中壓入元素時(shí)，是 A 。 A. 先存入元素，后移動(dòng)棧頂指針 B.先移動(dòng)棧頂指針，后存入元素 .在一個(gè)順序存儲(chǔ)的循環(huán)隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的 A 。 A. 前一個(gè)位置 B. 后一

2、個(gè)位置 C. 隊(duì)首元素位置 D. 隊(duì)尾元素位置 .若進(jìn)棧序列為1,2,3,4,進(jìn)棧過(guò)程中可以出棧，則 C 不可能是一個(gè)出棧序列。 A. 3,4,2,1 B. 2,4,3,1 C. 1,4,2,3 D. 3,2,1,4 .在具有n個(gè)單元的順序存儲(chǔ)的循環(huán)隊(duì)列中，假定front和rear分別為隊(duì)首指針和隊(duì)尾指針，則判斷隊(duì)空的條件是 C 。 A. front= =rear+1 B. front+1= =rear C. front= =rear D. front= =0 .在具有n個(gè)單元的順序存儲(chǔ)的循環(huán)隊(duì)列中，假定front和rear分別為隊(duì)首指針和隊(duì)尾指針，則判斷隊(duì)滿的條件是 D 。 A. rear

3、% n= =front B. (rear-1) % n= =front C. (rear-1) % n= =rear D. (rear+1) % n= =front .從一個(gè)具有n個(gè)節(jié)點(diǎn)的單鏈表中查找其值等于x結(jié)點(diǎn)時(shí)，在查找成功的情況下，需 平均比較 D 個(gè)結(jié)點(diǎn)。 A. n B. n/2 C. (n-1)/2 D. (n+1)/2 .在一個(gè)單鏈表中，已知*q結(jié)點(diǎn)是*p結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在*q和*p之間插入*s結(jié)點(diǎn)， 則執(zhí)行 C 。 A. s->next=p->next; p->next=s; B. p->next=s->next; s->next=p; C.

4、 q->next=s; s->next=p; D. p->next=s; s->next=q; 10.向一個(gè)棧項(xiàng)指針為hs的鏈棧中插入一個(gè)*s結(jié)點(diǎn)時(shí)，則執(zhí)行 C 。 A. hs->next=s; B. s->next=hs->next; hs->next=s; C. s->next=hs；hs=s; D. s->next=hs; hs=hs->next; 11.在一個(gè)鏈隊(duì)列中，假定front和rear分別為隊(duì)首指針和隊(duì)尾指針，則進(jìn)行插入*s結(jié)點(diǎn)的操作時(shí)應(yīng)執(zhí)行 B 。 A. front->next=s; front=s; B

5、. rear->next=s; rear=s; C. front=front->next; D. front=rear->next; 12.線性表是 A 。 A. 一個(gè)有限序列，可以為空 B. 一個(gè)有限序列，不能為空 C. 一個(gè)無(wú)限序列，可以為空 D. 一個(gè)無(wú)限序列，不能為空 13.對(duì)順序存儲(chǔ)的線性表，設(shè)其長(zhǎng)度為n，在任何位置上插入或刪除操作都是等概率的， 刪除一個(gè)元素時(shí)大約要移動(dòng)表中的 C 個(gè)元素。 A. n+1 B. n-1 C. (n-1)/2 D. n 14.線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其地址 D 。 A. 必須是連續(xù)的 B. 部分地址必須是連續(xù)的 C. 一定是不連續(xù)的 D

6、. 連續(xù)與否均可以 15.設(shè)單鏈表中指針p指著結(jié)點(diǎn)(數(shù)據(jù)域?yàn)閙)，指針f指著將要插入的新結(jié)點(diǎn)(數(shù)據(jù)域?yàn)閤)，當(dāng)x插在結(jié)點(diǎn)m之后時(shí)，只要先修改 B 后修改p->link=f即可。 A. f->link=p; B. f->link=p->link; C. p->link=f->link; D. f=nil; 16.在雙向鏈表存儲(chǔ)結(jié)構(gòu)中，刪除p所指的結(jié)點(diǎn)時(shí)需修改指針 B 。 A. (p->rlink) ->rlink) ->link=p; p->rlink=(p->rlink) ->rlink; B. (p->llink)

7、 ->rlink=p->rlink; (p->rlink) ->llink=p->llink; C. p->llink=(p->llink) ->llink; (p->llink) ->llink) ->rlink=p; D. (p->llink) ->llink) ->rlink=p; p->llink=(p->llink) ->llink; 17.在雙向鏈表存儲(chǔ)結(jié)構(gòu)中，刪除p所指的結(jié)點(diǎn)的前趨結(jié)點(diǎn)（若存在）時(shí)需修改指針 A 。 A. (p->llink) ->llink) -&g

8、t;rlink=p; p->llink=(p->llink) ->llink; B. (p->rlink) ->rlink) ->llink=p; p->rlink=(p->rlink) ->rlink; C. (p->llink) ->rlink=p->rlink; (p->rlink) ->llink=p->llink; D. p->llink=(p->llink) ->llink; (p->llink) ->llink) ->rlink=p; 18.根據(jù)線性表的鏈

9、式存儲(chǔ)結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)所含指針的個(gè)數(shù)，鏈表分為單鏈表和 B 。 A. 循環(huán)鏈表 B. 多重鏈表 C. 普通鏈表 D. 無(wú)頭結(jié)點(diǎn)鏈表 19.在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的數(shù)據(jù)叫 C 結(jié)構(gòu)。 A. 存儲(chǔ) B. 物理 C. 邏輯 D. 物理和存儲(chǔ) 20.二分法查找 A 存儲(chǔ)結(jié)構(gòu)。 A. 只適用于順序 B. 只適用于鏈?zhǔn)?C. 既適用于順序也適用于鏈?zhǔn)?D. 既不適合于順序也不適合于鏈?zhǔn)?21.在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，邏輯上相鄰的元素在物理位置上 B 。 A. 一定相鄰 B. 不一定相鄰 C. 有時(shí)相鄰 22.設(shè)字符串s1='abcdefg',s2='pqrst'

10、，則運(yùn)算 s=concat(sub(s1,2,len(s2),sub(s1,len(s2),2)后串值為 D 。 A. 'bcdef' B. 'bcdefg' C. 'bcpqrst' D. 'bcdefef' 23.假定在一棵二叉樹(shù)中，雙分支結(jié)點(diǎn)數(shù)為15個(gè)，單分支結(jié)點(diǎn)數(shù)為32個(gè)，則葉子結(jié)點(diǎn) 數(shù)為 B 。 A. 15 B. 16 C. 17 D. 47 24.假定一棵二叉樹(shù)的結(jié)點(diǎn)數(shù)為18個(gè)，則它的最小高度 B 。 A. 4 B. 5 C. 6 D. 18 25.在一棵二叉樹(shù)中第五層上的結(jié)點(diǎn)數(shù)最多為 C 。 A. 8 B. 15 C

11、. 16 D. 32 26.在一棵具有五層的滿二叉樹(shù)中，結(jié)點(diǎn)總數(shù)為 A 。 A. 31 B. 32 C. 33 D. 16 27.已知8個(gè)數(shù)據(jù)元素為(34、76、45、18、26、54、92、65)，按照依次插入結(jié)點(diǎn)的方法生成一棵二叉排序樹(shù)后，最后兩層上的結(jié)點(diǎn)總數(shù)為 B 。 A. 1 B. 2 C. 3 D. 4 28.由分別帶權(quán)為9、2、5、7的四個(gè)葉子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹(shù)，該樹(shù)的帶權(quán)路徑長(zhǎng)度為 C 。 A. 23 B. 37 C. 44 D. 46 29.在樹(shù)中除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)分成m (m0)個(gè) A 的集合T1,T2,T3.Tm,每個(gè)集合又都是樹(shù)，此時(shí)結(jié)點(diǎn)T稱為T(mén)i的父結(jié)點(diǎn)，Ti稱為T(mén)

12、的子結(jié)點(diǎn)(1im)。 A. 互不相交 B. 可以相交 C. 葉結(jié)點(diǎn)可以相交 D. 樹(shù)枝結(jié)點(diǎn)可以相交 30.下面答案 D 是查找二叉樹(shù)（又稱二叉排序樹(shù)）。 A. 二叉樹(shù)中的每個(gè)結(jié)點(diǎn)的兩棵子樹(shù)的高度差的絕對(duì)值不大于 B. 二叉樹(shù)中的每個(gè)結(jié)點(diǎn)的兩棵子樹(shù)的高度差等于 C. 二叉樹(shù)中的每個(gè)結(jié)點(diǎn)的兩棵子樹(shù)是有序的 D. 二叉樹(shù)中的每個(gè)結(jié)點(diǎn)的關(guān)鍵字大于其左子樹(shù)（如果存在）所有結(jié)點(diǎn)的關(guān)鍵字值， 且小于其右子樹(shù)（如果存在）所有結(jié)點(diǎn)的關(guān)鍵字值。 31.如果結(jié)點(diǎn)A有三個(gè)兄弟，而且B是A的雙親，則B的出度是 B 。 A. 3 B. 4 C. 5 D. 1 32.一個(gè)深度為L(zhǎng)的滿K叉樹(shù)有如下性質(zhì)：第L層上的結(jié)點(diǎn)都是葉子

13、結(jié)點(diǎn)，其余各層上每個(gè)結(jié)點(diǎn)都有K棵非空子樹(shù)。如果按層次順序從開(kāi)始對(duì)全部結(jié)點(diǎn)編號(hào)，編號(hào)為n的有右兄弟的條件是 B 。 A. (n-1) % k= =0 B. (n-1) % k!=0 C. n % k= =0 D. n % k!=0 33.在完全二叉樹(shù)中，當(dāng)i為奇數(shù)且不等于時(shí)，結(jié)點(diǎn)i的左兄弟是結(jié)點(diǎn) D ，否則沒(méi)有左兄弟。 A. 2i-1 B. i+1 C. 2i+1 D. i-1 34.某二叉樹(shù)T有n個(gè)結(jié)點(diǎn)，設(shè)按某種遍歷順序?qū)中的每個(gè)結(jié)點(diǎn)進(jìn)行編號(hào)，編號(hào)值為1,2,n且有如下性質(zhì)：T中任一結(jié)點(diǎn)V，其編號(hào)等于左子樹(shù)上的最小編號(hào)減1，而V的右子樹(shù) 的結(jié)點(diǎn)中，其最小編號(hào)等于V左子樹(shù)上結(jié)點(diǎn)的最大編號(hào)加1。

14、這時(shí)按 B 編號(hào)。 A. 中序遍歷序列 B. 前序遍歷序列 C. 后序遍歷序列 D. 層次遍歷序列 35.在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的 B 倍。 A. 1/2 B. 1 C. 2 D. 4 36.對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖，若采用鄰接表表示，則表頭向量的大小 為 A 。 A. n B. n+1 C. n-1 D. n+e 37.具有n個(gè)頂點(diǎn)的無(wú)向完全圖，邊的總數(shù)為 D 條。 A. n-1 B. n C. n+1 D. n*(n-1)/2 38.設(shè)圖G有n個(gè)頂點(diǎn)和e條邊，當(dāng)G是非孤立頂點(diǎn)的連通圖時(shí)有2e>=n,故可推得深度優(yōu)先搜索的時(shí)間復(fù)雜度為 A

15、。 A. O(e) B. O(n) C. O(ne) D. O(n+e) 39.最小代價(jià)生成樹(shù) D 。 A.是唯一的 B.不是唯一的 C.唯一性不確定 D.唯一性與原因的邊的權(quán)數(shù)有關(guān) 40.在無(wú)向圖G的鄰接矩陣A中，若Ai,j等于1，則Aj,i等于 C 。 A. i+j B. i-j C. 1 D. 0 41.圖的深度優(yōu)先或廣度優(yōu)先遍歷的空間復(fù)雜性均為 A 。(訪問(wèn)標(biāo)志位數(shù)組空間) A. O(n) B. O(e) C. O(n-e) D. O(n+e) 42.已知一個(gè)有序表為(12、18、24、35、47、50、62、83、90、115、134)，當(dāng)二分查找值為90的元素時(shí)， B 次比較后查找

16、成功；當(dāng)二分查找值為47的元素時(shí)， D 次比較后查找成功。 A. 1 B. 2 C. 3 D. 4 43.散列函數(shù)有一個(gè)共同性質(zhì)，即函數(shù)值應(yīng)當(dāng)以 D 取其值域的每個(gè)值。 A. 最大概率 B. 最小概率 C. 平均概率 D. 同等概率 44.設(shè)散列地址空間為0m1,k為關(guān)鍵字，用p去除k，將所得的余數(shù)作為k的散列地址，即H(k)k % p。為了減少發(fā)生沖突的頻率，一般取p為 D 。 A. 小于m的最大奇數(shù) B. 小于m的最大偶數(shù) C. m D. 小于m的最大素?cái)?shù) 45.目前以比較為基礎(chǔ)的內(nèi)部排序時(shí)間復(fù)雜度T(n)的范圍是 A ；其比較次數(shù)與待排序的記錄的初始排列狀態(tài)無(wú)關(guān)的是 B 。 A. O(l

17、og2 n)O(n) O(lon2 n)O(n2 ) O(nlog2 n)O(n2 ) O(n)O(n2 ) O(n)O(nlog2 n) B. 插入排序 先用二分法查找，找到后插入排序 快速排序 冒泡排序 46.設(shè)關(guān)鍵字序列為：3,7,6,9,8,1,4,5,2。進(jìn)行排序的最小交換次數(shù)是 A 。 A. 6 B. 7 C. 8 D. 20 47.在歸并排序過(guò)程中，需歸并的趟數(shù)為 C 。 A. n B. n C. log2 n向上取整 D. log2 n向下取整 48.一組記錄排序碼為(46、79、56、38、40、84)，則利用堆排序的方法建立的初始堆為 B 。 A. (79、46、56、38

18、、40、80) B. (84、79、56、38、40、46) C. (84、79、56、46、40、38) D. (84、56、79、40、46、38) 49.一組記錄的關(guān)鍵碼為(46、79、56、38、40、84)，則利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為 C 。 A. (38、40、46、56、79、84) B. (40、38、46、79、56、84) C. (40、38、46、56、79、84) D. (40、38、46、84、56、79) 50.在平均情況下快速排序的時(shí)間復(fù)雜性為 C ，空間復(fù)雜性為 B ；在最壞情況下（如初始記錄已有序），快速排序的時(shí)間復(fù)雜性為 D

19、 ，空間復(fù)雜性為 A 。 A. O(n) B. O(log2 n) C. O(nlog2 n) D. O(n2 ) 二、填空題 1.在線性結(jié)構(gòu)中第一結(jié)點(diǎn) 1 無(wú) 前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有 2 一 個(gè)前驅(qū)結(jié)點(diǎn)；最后一個(gè)結(jié)點(diǎn) 3 無(wú) 后繼結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有 4 一 個(gè)后繼結(jié)點(diǎn)。 2.在樹(shù)型結(jié)構(gòu)中，樹(shù)根結(jié)點(diǎn)沒(méi)有 1 前趨 結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且僅有 2 一 個(gè)前驅(qū)結(jié)點(diǎn)；樹(shù)葉結(jié)點(diǎn)沒(méi)有 3 后繼 結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的 4 后繼 結(jié)點(diǎn)數(shù)不受限制。 3.一個(gè)數(shù)據(jù)結(jié)構(gòu)用二元組表示時(shí)，它包括 1 數(shù)據(jù)元素 的集合K和K上 2二元關(guān)系 的集合R。 * 4.對(duì)于一個(gè)二維數(shù)組A1.m,1.n，若按行序?yàn)?/p>

20、主序存儲(chǔ)，則任一元素Ai,j的相對(duì)地址（即偏移地址）為 1 (i-1)*n+j-1 。 5.對(duì)于順序存儲(chǔ)的線性表，當(dāng)隨機(jī)插入或刪除一個(gè)元素時(shí)，約需平均移動(dòng)表長(zhǎng) 1 一半 的元素。 6.對(duì)于長(zhǎng)度為n的順序表，插入或刪除元素的時(shí)間復(fù)雜性為 1 O(n) ；對(duì)于順序棧或隊(duì)列，插入或刪除元素的時(shí)間復(fù)雜性為 2 O(1) 。 7.在具有n個(gè)單元、順序存儲(chǔ)的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有 1 n-1 個(gè)元素。 8.從順序表中刪除第i個(gè)元素時(shí)，首先把第i個(gè)元素賦給 1 變參或函數(shù)名 帶回，接著從 2 鏈接指針 開(kāi)始向后的所有元素均 3 前移 一個(gè)位置，最后使線性表的長(zhǎng)度 4 減1 。 9.在線性表的順序存儲(chǔ)中，元素

21、之間的邏輯關(guān)系是通過(guò) 1 相鄰位置 決定的；在線性表的鏈接存儲(chǔ)中，元素之間的邏輯關(guān)系是通過(guò) 2 鏈接指針 決定的。 10.一個(gè)單鏈表中刪除*p結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行如下操作: (1)q=p->next; (2)p->data=p->next->data; (3)p->next= 1 q->next或p->next->next ; (4)free(q); 11.若要在一個(gè)單鏈表中的*p結(jié)點(diǎn)之前插入一個(gè)*s結(jié)點(diǎn)時(shí)，可執(zhí)行如下操作: (1)s->next= 1 p->next ; (2)p->next=s; (3)t=p->data;

22、(4)p->data= 2 s->data ; (5)s->data= 3 t ; 12.對(duì)于線性表的順序存儲(chǔ)，需要預(yù)先分配好存儲(chǔ)空間，若分配太多則容易造成存儲(chǔ)空間的 1 浪費(fèi) ，若分配太少又容易在算法中造成 2 溢出 ，因此適應(yīng)于數(shù)據(jù)量變化不大的情況；對(duì)于線性表的鏈接存儲(chǔ)(假定采用動(dòng)態(tài)結(jié)點(diǎn))，不需要 3 預(yù)先分配 存儲(chǔ)空間，存儲(chǔ)器中的整個(gè) 4 動(dòng)態(tài)存儲(chǔ)區(qū) 都可供使用，分配和回收結(jié)點(diǎn)都非常方便，能夠有效地利用存儲(chǔ)空間，在算法中不必考慮 5 溢出 的發(fā)生，因此適應(yīng)數(shù)據(jù)量變化較大的情況。 13.無(wú)論對(duì)于順序存儲(chǔ)還是鏈接存儲(chǔ)的棧和隊(duì)列來(lái)說(shuō)，進(jìn)行插入或刪除運(yùn)算的時(shí)間復(fù) 雜性均相同，則

23、為 1 O(1) 。 0 0 2 0 *14.一個(gè)稀疏矩陣為 3 0 0 0，則對(duì)應(yīng)的三元組線性表為 0 0 -1 5 (1,3,2),(2,1,3),(3,3,-1),(3,4,5)。 0 0 0 0 15.對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的樹(shù)，則該樹(shù)中所有結(jié)點(diǎn)的度之和為 n-1 。 16.在一棵二叉樹(shù)中，度為0的結(jié)點(diǎn)的個(gè)數(shù)為n0 ，度為2的結(jié)點(diǎn)的個(gè)數(shù)為n2 ，則：n0 = n2 +1 。 17.在二叉樹(shù)的順序存儲(chǔ)中，對(duì)于下標(biāo)為5的結(jié)點(diǎn)，它的雙親結(jié)點(diǎn)的下標(biāo)為 1 2 ， 若它存在左孩子，則左孩子結(jié)點(diǎn)的下標(biāo)為 2 10 ，若它存在右孩子，則右孩子結(jié)點(diǎn)的下標(biāo)為 3 11 。 18.假定一棵二叉樹(shù)的廣義表表示

24、為A(B(，D)，C(E(G)，F(xiàn))，則該樹(shù)的深度為 14 ， 度為0的結(jié)點(diǎn)數(shù)為 23 ，度為1的結(jié)點(diǎn)數(shù)為 3 2 ，度為2的結(jié)點(diǎn)數(shù)為 42 ；C結(jié)點(diǎn)是A 結(jié)點(diǎn)的 5 右 孩子，E結(jié)點(diǎn)是C結(jié)點(diǎn)的 6 左 孩子。 19.在一棵二叉排序樹(shù)中，按 中序 遍歷得到的結(jié)點(diǎn)序列是一個(gè)有序序列。 20.由分別帶權(quán)為3,9,6,2,5的共五個(gè)葉子結(jié)點(diǎn)構(gòu)成一棵哈夫曼樹(shù)，則帶權(quán)路徑長(zhǎng)度為 55 。 21.假定在二叉樹(shù)的鏈接存儲(chǔ)中，每個(gè)結(jié)點(diǎn)的結(jié)構(gòu)為leftdataright ，其中 data為值域，left和right分別為鏈接左、右孩子結(jié)點(diǎn)的指針域，請(qǐng)?jiān)谙旅嬷行虮闅v算法 中畫(huà)有橫線的地方填寫(xiě)合適的語(yǔ)句。 void

25、 inorder(bt); if bt!=nil (1) 1 inorder(bt->left) ； (2) 2 printf(bt->data) ； (3) 3 inorder(bt->right) ； 22.在圖G的鄰接表表示中，每個(gè)頂點(diǎn)鄰接表中所含的結(jié)點(diǎn)數(shù)，對(duì)于無(wú)向圖來(lái)說(shuō)等于該 頂點(diǎn)的 1 度數(shù) ，對(duì)于有向圖來(lái)說(shuō)等于該頂點(diǎn)的 2 出度數(shù) 。 23.假定一個(gè)圖具有n個(gè)頂點(diǎn)和e條邊，則采用鄰接矩陣表示的空間復(fù)雜性為 1 O(n2 ) ， 采用鄰接表表示的空間復(fù)雜性為 2 O(n+e) 。 24.已知一個(gè)無(wú)向圖的鄰接矩陣如下所示，則從頂點(diǎn)A出發(fā)按深度優(yōu)先搜索遍歷得到的 頂點(diǎn)序

26、列為 1 ABCDFE ，按廣度優(yōu)先搜索遍歷得到的頂點(diǎn)序列為 2 ABCEFD 。 A B C D E F 0 1 1 0 1 0A 1 0 1 0 1 1B 1 1 0 1 0 0C 0 0 1 0 0 1D 1 1 0 0 0 1E 0 1 0 1 1 0F 25.已知一個(gè)圖如下所示，在該圖的最小生成樹(shù)中，各邊的權(quán)值之和為 20 。 10 15 5 2 8 12 3 26.假定在有序表A1.20上進(jìn)行二分查找，則比較一次查找成功的結(jié)點(diǎn)數(shù)為 11 ， 比較兩次查找成功的結(jié)點(diǎn)數(shù)為 22 ，比較三次查找成功的結(jié)點(diǎn)數(shù)為 34 ，比較四次查找成功結(jié)點(diǎn)數(shù)為 48 ，比較五次查找成功的結(jié)點(diǎn)數(shù)為 55 ，

27、平均查找長(zhǎng)度為 63.7 。 27.在索引查找或分塊查找中，首先查找 1 索引表 ，然后再查找相應(yīng)的 2 子表或塊 ，整個(gè)索引查找的平均查找長(zhǎng)度等于查找索引表的平均查找長(zhǎng)度與查找相應(yīng)子表的平均查找長(zhǎng)度之 3 和 。 28.在散列存儲(chǔ)中，裝填因子的值越大，存取元素時(shí)發(fā)生沖突的可能性就 1 越大，當(dāng)?shù)闹翟叫?，存取元素時(shí)發(fā)生沖突的可能性就 2 越小 。 29.給定線性表(18,25,63,50,42,32,90)，用散列方式存儲(chǔ)，若選用h(K)=K % 9作為散列函數(shù)，則元素18的同義詞元素共有 12 個(gè)，元素25的同義詞元素共有 20 個(gè)，元素50的同義詞元素共有 31 個(gè)。 30.在對(duì)一組記錄(

28、54,38,96,23,15,72,60,45,83)進(jìn)行直接選擇排序時(shí)，第四次選擇和交換后，未排序記錄(即無(wú)序表)為 (54,72,60,96,83) 。 31.在對(duì)一組記錄(54,38,96,23,15,72,60,45,38)進(jìn)行冒泡排序時(shí)，第一趟需進(jìn)行相鄰記錄交換的次數(shù)為 17 ，在整個(gè)冒泡排序過(guò)程中共需進(jìn)行 25 趟后才能完成。 32.在歸并排序中，若待排序記錄的個(gè)數(shù)為20，則共需要進(jìn)行 15 趟歸并，在第三趟歸并中，是把長(zhǎng)度為 24 的有序表歸并為長(zhǎng)度為 38 的有序表。 33.在直接插入和直接選擇排序中，若初始數(shù)據(jù)基本正序，則選用 1 直接插入排序 ，若初始數(shù)據(jù)基本反序，則選用

29、2 直接選擇排序 。 34.在堆排序、快速排序和歸并排序中，若只從節(jié)省空間考慮，則應(yīng)首先選取 1 堆排序 方法，其次選取 2 快速排序 方法，最后選取 3 歸并排序 方法；若只從排序結(jié)果的穩(wěn)定性考慮，則應(yīng)選取 4 歸并排序 ；若只從平均情況下排序最快考慮，則應(yīng)選取 5 快速排序 方法；若只從最壞情況下排序最快并且要節(jié)省內(nèi)存考慮，則應(yīng)選取 6 堆排序 方法。 三、判斷題 1數(shù)據(jù)元素是數(shù)據(jù)的最小單位（× ）。 2數(shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位（ × ）。 3順序存儲(chǔ)的線性表可以隨機(jī)存?。?）。 4線性表中的元素可以是各種各樣的，但同一線性表中的數(shù)據(jù)元素具有相同的特性， 因此，是屬于同一

30、數(shù)據(jù)對(duì)象（ ）。 5在單鏈表中，任何兩個(gè)元素的存儲(chǔ)位置之間都有固定的聯(lián)系，因?yàn)榭梢詮念^結(jié)點(diǎn)查找任何一個(gè)元素（× ）。 6在單鏈表中，要取得某個(gè)元素，只要知道該元素的指針即可，因此，單鏈表是隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)（ × ）。 7鏈表的每個(gè)結(jié)點(diǎn)中，都恰好包含一個(gè)指針（× ）。 *8數(shù)組是同類型值的集合（× ）。 /不是集合/ *9使用三元組表示稀疏矩陣的元素，有時(shí)并不能節(jié)省存儲(chǔ)時(shí)間（ ）。 *10.線性表可以看成是廣義表的特例，如果廣義表中的每個(gè)元素都是原子，則廣義表便成為線性表（ ）。 11.由樹(shù)轉(zhuǎn)換成二叉樹(shù)，其根結(jié)點(diǎn)的右子樹(shù)總是空的（ ）。 12.后序遍歷樹(shù)

31、和中序遍歷與該樹(shù)對(duì)應(yīng)的二叉樹(shù)，其結(jié)果不同（ × ）。 13.若有一個(gè)結(jié)點(diǎn)是某二叉樹(shù)子樹(shù)的中序遍歷序列中的最后一個(gè)結(jié)點(diǎn)，則它必是該子 樹(shù)的前序遍歷序列中的最后一個(gè)結(jié)點(diǎn)（× ）。 14.若一個(gè)樹(shù)葉是某子樹(shù)的中序遍歷序列中的最后一個(gè)結(jié)點(diǎn)，則它必是該子樹(shù)的前序 遍歷序列中的最后一個(gè)結(jié)點(diǎn)（ ）。 15.已知二叉樹(shù)的前序遍歷和后序遍歷序列并不能唯一地確定這棵樹(shù)，因?yàn)椴恢罉?shù) 的根結(jié)點(diǎn)是哪一個(gè)（× ）。 16.在哈夫曼編碼中，當(dāng)兩個(gè)字符出現(xiàn)的頻率相同時(shí)，其編碼也相同，對(duì)于這種情況應(yīng)作特殊處理（× ）。 17.有回路的圖不能進(jìn)行拓?fù)渑判颍?）。 18.連通分量是無(wú)向圖中

32、的極小連通子圖（× ）。 /極大/ 19.散列法存儲(chǔ)的基本思想是由關(guān)鍵碼的值決定數(shù)據(jù)的存儲(chǔ)地址（ ）。 20.散列表的查找效率取決于散列表造表時(shí)選取的散列函數(shù)和處理沖突的方法（ ）。 21.m階B-樹(shù)每一個(gè)結(jié)點(diǎn)的子樹(shù)個(gè)數(shù)都小于或等于m（ ）。 22.中序遍歷二叉排序樹(shù)的結(jié)點(diǎn)就可以得到排好序的結(jié)點(diǎn)序列（ ）。 23.在二叉排序樹(shù)上插入新的結(jié)點(diǎn)時(shí)，不必移動(dòng)其它結(jié)點(diǎn)，僅需改動(dòng)某個(gè)結(jié)點(diǎn)的指針， 由空變?yōu)榉强占纯桑?）。 24.當(dāng)待排序的元素很多時(shí)，為了交換元素的位置，移動(dòng)元素要占用較多的時(shí)間，這是影響時(shí)間復(fù)雜性的主要因素（ ）。 25.對(duì)于n個(gè)記錄的集合進(jìn)行快速排序，所需要的平均時(shí)間是O(n

33、log2 n)（ ）。 26.對(duì)于n個(gè)記錄的集合進(jìn)行歸并排序，所需要的平均時(shí)間是O(nlog2 n)（ ）。 27.堆中所有非終端結(jié)點(diǎn)的值均小于或等于（大于或等于）左右子樹(shù)的值（ ）。 *28.磁盤(pán)上的順序文件中插入新的記錄時(shí)，必須復(fù)制整個(gè)文件（ × ）。 *29.在索引順序文件中插入新的記錄時(shí)，必須復(fù)制整個(gè)文件（× ）。 *30.索引順序文件是一種特殊的順序文件，因此通常存放在磁帶上（× ）。 四、綜合題 1. 線性表有兩種存儲(chǔ)結(jié)構(gòu)：一是順序表，二是鏈表。試問(wèn)： (1)兩種存儲(chǔ)表示各有哪些主要優(yōu)缺點(diǎn)? (2)如果有n個(gè)線性表同時(shí)并存，并且在處理過(guò)程中各表的長(zhǎng)度會(huì)

34、動(dòng)態(tài)發(fā)生變化，線性 表的總數(shù)也會(huì)自動(dòng)地改變。在此情況下，應(yīng)選用哪種存儲(chǔ)結(jié)構(gòu)?為什么? (3)若線性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，但要求以最快的速度存取線性表中的元素，那么，應(yīng)采用哪種存儲(chǔ)結(jié)構(gòu)?為什么? 1. 解答: (1)順序存儲(chǔ)是按索引（隱含的）直接存取數(shù)據(jù)元素，方便靈活，效率高，但插入、刪除操作時(shí)將引起元素移動(dòng)，因而降低效率；鏈接存儲(chǔ)內(nèi)存采用動(dòng)態(tài)分配，利用率高，但需增設(shè)指示結(jié)點(diǎn)之間有序關(guān)系的指針域，存取數(shù)據(jù)元素不如順序存儲(chǔ)方便，但結(jié)點(diǎn)的插入、刪除操作十分簡(jiǎn)單。 (2)應(yīng)選用鏈接表存儲(chǔ)結(jié)構(gòu)。其理由是，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)用一組任意的存儲(chǔ)單元依次存儲(chǔ)線性表里各元素，這里存儲(chǔ)單元可以是連續(xù)的，

35、也可以是不連續(xù)的。這種存儲(chǔ)結(jié)構(gòu)，在對(duì)元素作插入或刪除運(yùn)算時(shí)，不需要移動(dòng)元素，僅修改指針即可。所以很容易實(shí)現(xiàn)表的容量擴(kuò)充。 (3)應(yīng)選用順序存儲(chǔ)結(jié)構(gòu)。其理由是，每個(gè)數(shù)據(jù)元素的存儲(chǔ)位置和線性表的起始位置相差一個(gè)和數(shù)據(jù)元素在線性表中的序號(hào)成正比的常數(shù)。由此，只要確定了起始位置，線性表中任一數(shù)據(jù)元素都可隨機(jī)存取，所以線性表的順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。而鏈表則是一種順序存取的存儲(chǔ)結(jié)構(gòu)。2. 用線性表的順序結(jié)構(gòu)來(lái)描述一個(gè)城市的設(shè)計(jì)和規(guī)劃合適嗎?為什么? 2.解答: 不合適。因?yàn)橐粋€(gè)城市的設(shè)計(jì)和規(guī)劃涉及非常多的項(xiàng)目，很復(fù)雜，經(jīng)常需要修改、 擴(kuò)充和刪除各種信息，才能適應(yīng)不斷發(fā)展的需要。有鑒于此，順

36、序線性表不能很好適應(yīng)其需要，故是不合適的。3. 在單鏈表和雙向表中，能否從當(dāng)前結(jié)點(diǎn)出發(fā)訪問(wèn)到任一結(jié)點(diǎn)? 3. 解答: 在單鏈表中只能由當(dāng)前結(jié)點(diǎn)訪問(wèn)其后的任一結(jié)點(diǎn)，因?yàn)闆](méi)有指向其前驅(qū)結(jié)點(diǎn)的指 針。而在雙向鏈表中，既有指向后繼結(jié)點(diǎn)的指針又有指向前驅(qū)結(jié)點(diǎn)的指針，故可由當(dāng)前結(jié)點(diǎn)出發(fā)訪問(wèn)鏈表中任一結(jié)點(diǎn)。4. 試述棧的基本性質(zhì)? 4. 解答: 由棧的定義可知，這種結(jié)構(gòu)的基本性質(zhì)綜述如下： (1)集合性。棧是由若干個(gè)元素集合而成，當(dāng)沒(méi)有元素的空集合稱為空棧； (2)線性結(jié)構(gòu)。除棧底元素和棧頂元素外，棧中任一元素均有唯一的前驅(qū)元素和后繼元素； (3)受限制的運(yùn)算。只允許在棧頂實(shí)施壓入或彈出操作，且棧頂位置由棧

37、指針?biāo)甘荆?4)數(shù)學(xué)性質(zhì)。當(dāng)多個(gè)編號(hào)元素依某種順序壓入，且可任意時(shí)刻彈出時(shí)，所獲得的編號(hào)元素排列的數(shù)目，恰好滿足卡塔南數(shù)列的計(jì)算，即： n n 2n /(n1) 其中，n為編號(hào)元素的個(gè)數(shù)，Cn 是可能的排列數(shù)目。 5. 何謂隊(duì)列的上溢現(xiàn)象?解決它有哪些方法，且分別簡(jiǎn)述其工作原理。 5. 解答: 在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)中，設(shè)隊(duì)頭指針為front,隊(duì)尾指針為rear,隊(duì)的容量（存儲(chǔ)空間的大?。閙。當(dāng)有元素要加入隊(duì)列時(shí)，若rearm（初始時(shí)reat0），則發(fā)生隊(duì)列的上溢現(xiàn)象，該元素不能加入隊(duì)列。 這里要特別注意的是：隊(duì)列的假溢出現(xiàn)象，隊(duì)列中還有空余的空間，但元素不能進(jìn)隊(duì) 列。造成這種現(xiàn)象的原因是由

38、于隊(duì)列的操作方式所致。 解決隊(duì)列的上溢有以下幾種方法： (1)建立一個(gè)足夠大的存儲(chǔ)空間，但這樣做往往會(huì)造成空間使用的效率低。 (2)當(dāng)出現(xiàn)假溢出時(shí)，可采用以下幾種方法： 采用平移元素的方法。每當(dāng)隊(duì)列中加入一個(gè)元素時(shí)，隊(duì)列中已有的元素向隊(duì)頭 移動(dòng)一個(gè)位置（當(dāng)然要有空余的空間可移）； 每當(dāng)刪去一個(gè)隊(duì)頭元素時(shí)，則依次序移隊(duì)中的元素，始終使front指針指向隊(duì)列 中的第一個(gè)位置； 采用循環(huán)隊(duì)列方式。把隊(duì)頭隊(duì)尾看成是一個(gè)首尾相鄰的循環(huán)隊(duì)列，雖然物理上 隊(duì)尾在隊(duì)首之前，但邏輯上隊(duì)首依然在前，作插入和刪除運(yùn)算時(shí)仍按“先進(jìn)先出”的原則。 6. 兩個(gè)字符串相等的充要條件是什么? 6. 解答: 兩個(gè)字符串相等的充

39、要條件是：兩個(gè)串的長(zhǎng)度相等，且對(duì)應(yīng)位置的字符相等。*7. 畫(huà)出廣義表(A(B(E，F(xiàn)(J)，C，D(G(K，L)，H，I)對(duì)應(yīng)的樹(shù)型結(jié)構(gòu)。 7. 解答: 根據(jù)廣義表的結(jié)構(gòu)可知，該樹(shù)的根結(jié)點(diǎn)為A；而B(niǎo)、C、D為A的子樹(shù)，B又有兩棵子 樹(shù)等等，該廣義表對(duì)應(yīng)的樹(shù)型結(jié)構(gòu)見(jiàn)下圖。 A B C D E F G H I J K L*8. 對(duì)于二叉排序樹(shù)，當(dāng)所有結(jié)點(diǎn)的權(quán)都相等的情況下，最佳二叉排序樹(shù)有何特點(diǎn)。 8. 解答:其特點(diǎn)是只有最下面的二層結(jié)點(diǎn)可以小于，其它結(jié)點(diǎn)的度數(shù)必須為。 9. 試證明：已知一棵二叉樹(shù)的前序序列和中序序列，則可唯一地確定一棵二叉樹(shù)。 9. 證明 利用前序遍歷的結(jié)果序列能夠得到各子樹(shù)的

40、根，即從左到右檢查前序遍歷序列，當(dāng)?shù)?到根結(jié)點(diǎn)之后，利用根結(jié)點(diǎn)在中序遍歷序列中的位置可以確定其左右子樹(shù)，這樣便可逐次確定整個(gè)二叉樹(shù)。 假設(shè)BT為二叉樹(shù)的根，P1 ，P2 ，Pn 為前序遍歷序列，I1 ，I2 ，In 為中 序遍歷序列。 由前序遍歷序列可以得到BTP1 。 在中序遍歷序列中查找等于P1 的結(jié)點(diǎn)，設(shè)該結(jié)點(diǎn)為Ii ，則有Ii P1 。 根據(jù)二叉樹(shù)中序遍歷的原理，則該二叉樹(shù)可被分成左右兩棵子樹(shù)：對(duì)于左子樹(shù)，在中序遍歷序列中有I1 ，I2 ，Ii1 ，依此序列在前序遍歷序列中可以得到其左子樹(shù)為P2 ， P3 ，Pi ； 同理，對(duì)于右子樹(shù)有 Ii1 ，Ii2 ，In Pi1 ，Pi2 ，P

41、n 對(duì)于這兩棵子樹(shù)而言，其左子樹(shù)的根為P2 ，其右子樹(shù)的根為Pi1 。 依此類推，用同樣的方法就可以確定整個(gè)二叉樹(shù)。10.證明n個(gè)頂點(diǎn)的無(wú)向完全圖的邊數(shù)的n(n1)/2。 10.證明 方法一： 用歸納法證明 當(dāng)n1時(shí)，邊數(shù)為0，結(jié)論成立。 當(dāng)n2時(shí)，邊數(shù)為1，結(jié)論成立。 當(dāng)n1,2,k時(shí)均成立，即當(dāng)nk時(shí)，邊數(shù)為k(k1)/2。現(xiàn)證明當(dāng)nk1時(shí)若仍然 成立，則結(jié)論正確。 由前面證得，對(duì)于有k個(gè)頂點(diǎn)時(shí)，其邊數(shù)總和為 k(k1)/2。 當(dāng)再增加一個(gè)新頂點(diǎn)時(shí)，由于是無(wú)向完全圖，故該頂點(diǎn)到原來(lái)各個(gè)頂點(diǎn)均有一條邊， 這樣就共有邊數(shù)為 k(k1)/2kk(k1)/2(k1)(k1)1/2 可知當(dāng)頂點(diǎn)數(shù)k1

42、時(shí)，結(jié)論仍然成立，故具有n個(gè)頂點(diǎn)的無(wú)向完全圖的這數(shù)為 n(n1)/2 方法二： 在n個(gè)頂點(diǎn)的無(wú)向完全圖中，每個(gè)頂點(diǎn)與其余各頂點(diǎn)均有一條邊。第一個(gè)頂點(diǎn)到其余 各頂點(diǎn)的邊數(shù)為n1，第二個(gè)頂點(diǎn)到其余各頂點(diǎn)的邊數(shù)為n1，但它與第一個(gè)頂點(diǎn)之間的 邊已在第一個(gè)頂點(diǎn)的邊中，故第二個(gè)頂點(diǎn)到其它n2個(gè)頂點(diǎn)的邊為n2,，第n1個(gè)到余下的第n個(gè)頂點(diǎn)為邊數(shù)為1，所以總的邊數(shù)為 (n1)(n2)(n3)21n(n1)/2 所以其結(jié)論成立。 11.證明一個(gè)有n個(gè)頂點(diǎn)，e條邊的無(wú)向圖G，必有 dj 2e 其中dj 為頂點(diǎn)j的度。 11.證明 由度的定義可知，頂點(diǎn)j所聯(lián)接的邊數(shù)必為dj 條，另一方面，圖G中的任一條邊均關(guān)聯(lián)

43、G中的兩個(gè)頂點(diǎn)，即一條邊均要分別計(jì)入兩個(gè)不同的dj 和di 中，故dj 中的邊數(shù)應(yīng)為G中邊數(shù)的兩倍，即有 n j 2e i-1 12.證明：若無(wú)向圖G的頂點(diǎn)度數(shù)的最小值大于或等于2，則G有一條回路。 12.證明 方法一： 設(shè)G(V，E)，任取一頂點(diǎn)v1 V，因V1 的度大于或等于2,在v1 的鄰接頂點(diǎn)中任取一個(gè)不同于v1 的頂點(diǎn)作為v2 。因v2 的度大于或等于2,在v2 的鄰接頂點(diǎn)中任取一個(gè)不同于v2 的頂 點(diǎn)作為v3 。若v1 、v2 、v3 不構(gòu)成回路，則在再v3 的鄰接頂點(diǎn)中任取一個(gè)不同于v3 的的頂點(diǎn) 作為v4 ，。因?yàn)閳D中頂點(diǎn)的集合V是有限的，當(dāng)取得某個(gè)頂點(diǎn)vi 后，vi1 一定為

44、v1 ， v2 ，vi-1 之一，因而構(gòu)成回路。命題得證。方法二： 設(shè)圖G有n個(gè)頂點(diǎn)，整個(gè)圖G的度數(shù)之和為N，則有 N2n 我們知道，圖中每條邊涉及二個(gè)頂點(diǎn)，也就是每條邊含有2個(gè)度，這樣一來(lái)，該圖G至少有n條邊。由于一個(gè)n個(gè)頂點(diǎn)的樹(shù)圖只有n1條邊，多于n1條邊時(shí)則樹(shù)圖就不存在，圖中會(huì)出現(xiàn)回路。由前面推得，該圖至少有n條邊，故會(huì)出現(xiàn)回路。13.若對(duì)大小均為n的有序的順序表和無(wú)序的順序表分別進(jìn)行順序查找，試問(wèn)在下面三 種情況下，分別討論兩者在等概率時(shí)，平均查找長(zhǎng)度是否相同? (1)查找不成功，即表中沒(méi)有關(guān)鍵字等于給定值k的記錄； (2)查找成功，且表中只有一個(gè)關(guān)鍵字等于給定值k的記錄； (3)查找

45、成功，且表中有若干個(gè)關(guān)鍵字等于給定值k的記錄，一次查找要求找出所有記 錄，此時(shí)的平均查找長(zhǎng)度應(yīng)考慮找到所有記錄時(shí)所用的比較次數(shù)。 13.(1) 解答:不相同。對(duì)于有序的順序表而言，當(dāng)表中無(wú)此關(guān)鍵字時(shí)，只要在查找過(guò)程中發(fā)現(xiàn)順序表中的某個(gè)關(guān)鍵字大于待查的關(guān)鍵字時(shí)，查找過(guò)程就可以結(jié)束（假定順序表是由小到大排列的，對(duì)于由大到小排列的情況類似），沒(méi)有必要查找到表中最后一個(gè)關(guān)鍵字才確定查找不成功。而對(duì)于非有序的順序表，只有對(duì)表中的每一個(gè)關(guān)鍵字比較完之后，才能說(shuō)明查找不成功。顯然在等概率時(shí)兩種順序的平均查找長(zhǎng)度是不相同的。有序順序表的平均長(zhǎng)度為(n1)/2，而無(wú)序順序表的平均查找長(zhǎng)度為n。但從數(shù)量級(jí)上兩者是相同的,即O(n)。