數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題集 習(xí)題集

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. 先存入元素，后移動(dòng)棧頂指針 B.先移動(dòng)棧頂指針，后存入元素 .在一個(gè)順序存儲(chǔ)的循環(huán)隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的。A. 前一個(gè)位置 B. 后一個(gè)位置 C. 隊(duì)首元素位置

2、D. 隊(duì)尾元素位置 .若進(jìn)棧序列為1,2,3,4,進(jìn)棧過(guò)程中可以出棧，則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 % n= =front B. (rear-1) % n= =fr

3、ontC. (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. q->next=s; s->next=p; D. p->

4、next=s; s->next=q;10.向一個(gè)棧項(xiàng)指針為hs的鏈棧中插入一個(gè)*s結(jié)點(diǎn)時(shí)，則執(zhí)行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. rear->next=s; rear=s;C. front=front->ne

5、xt; D. front=rear->next;12.線性表是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 114.線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其地址。A. 必須是連續(xù)的 B. 部分地址必須是連續(xù)的C. 一定是不連續(xù)的 D. 連續(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之

6、后時(shí)，只要先修改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í)需修改指針A. (p->rlink) ->rlink) ->link=p; p->rlink=(p->rlink) ->rlink;B. (p->llink) ->rlink=p->rlink; (p->rlink) ->llink=p->llink;C. p->llink=

7、(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. (p->llink) ->llink) ->rlink=p; p->llink=(p->llink) ->llink;B. (p->rlink) ->rlink) ->lli

8、nk=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ù)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)所含指針的個(gè)數(shù)，鏈表分為單鏈表和。A. 循環(huán)鏈表 B. 多重鏈表 C. 普通鏈表 D. 無(wú)頭結(jié)點(diǎn)鏈表19.在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的數(shù)據(jù)叫A. 存儲(chǔ)

9、 B. 物理 C. 邏輯 D. 物理和存儲(chǔ)20.二分法查找A. 只適用于順序 B. 只適用于鏈?zhǔn)?C. 既適用于順序也適用于鏈?zhǔn)紻. 既不適合于順序也不適合于鏈?zhǔn)?1.在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，邏輯上相鄰的元素在物理位置上。A. 一定相鄰 B. 不一定相鄰 C. 有時(shí)相鄰22.設(shè)字符串s1='abcdefg',s2='pqrst'，則運(yùn)算s=concat(sub(s1,2,len(s2),sub(s1,len(s2),2)后串值為。A. 'bcdef' B. 'bcdefg' C. 'bcpqrst' D. 

10、9;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. 4724.假定一棵二叉樹(shù)的結(jié)點(diǎn)數(shù)為18個(gè)，則它的最小高度。A. 4 B. 5 C. 6 D. 1825.在一棵二叉樹(shù)中第五層上的結(jié)點(diǎn)數(shù)最多為A. 8 B. 15 C. 16 D. 3226.在一棵具有五層的滿二叉樹(shù)中，結(jié)點(diǎn)總數(shù)為。A. 31 B. 32 C. 33 D. 1627.已知8個(gè)數(shù)據(jù)元素為(34、76、45、18、26、54、92、65)，按照依次插入結(jié)點(diǎn)的方法生成一棵二叉排序樹(shù)后，最后兩層上的結(jié)點(diǎn)總數(shù)為 B 。A. 1

11、 B. 2 C. 3 D. 428.由分別帶權(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. 4629.在樹(shù)中除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)分成m (m0)個(gè)T1,T2,T3.Tm,每 2個(gè)集合又都是樹(shù)，此時(shí)結(jié)點(diǎn)T稱為T(mén)i的父結(jié)點(diǎn)，Ti稱為T(mén)的子結(jié)點(diǎn)(1im)。A. 互不相交 B. 可以相交C. 葉結(jié)點(diǎn)可以相交 D. 樹(shù)枝結(jié)點(diǎn)可以相交30.下面答案。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)鍵字大于其左子

12、樹(shù)（如果存在）所有結(jié)點(diǎn)的關(guān)鍵字值， 且小于其右子樹(shù)（如果存在）所有結(jié)點(diǎn)的關(guān)鍵字值。31.如果結(jié)點(diǎn)A有三個(gè)兄弟，而且B是A的雙親，則B的出度是A. 3 B. 4 C. 5 D. 132.一個(gè)深度為L(zhǎng)的滿K叉樹(shù)有如下性質(zhì)：第L層上的結(jié)點(diǎn)都是葉子結(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!=033.在完全二叉樹(shù)中，當(dāng)i為奇數(shù)且不等于時(shí)，結(jié)點(diǎn)i的左兄弟是結(jié)點(diǎn)，否則沒(méi)有左兄弟。 A. 2i-1 B. i+1 C. 2i+1 D.

13、 i-134.某二叉樹(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。這時(shí)按 B 編號(hào)。A. 中序遍歷序列 B. 前序遍歷序列 C. 后序遍歷序列 D. 層次遍歷序列35.在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的A. 1/2 B. 1 C. 2 D. 436.對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖，若采用鄰接表表示，則表頭向量的大小 為 A 。 A. n B. n+1 C. n-1 D. n+e37.具有n個(gè)頂點(diǎn)的無(wú)向完全

14、圖，邊的總數(shù)為條。A. n-1 B. n C. n+1 D. n*(n-1)/238.設(shè)圖G有n個(gè)頂點(diǎn)和e條邊，當(dāng)G是非孤立頂點(diǎn)的連通圖時(shí)有2e>=n,故可推得深度優(yōu)先搜索的時(shí)間復(fù)雜度為 A 。A. O(e) B. O(n) C. O(ne) D. O(n+e)39.最小代價(jià)生成樹(shù)A.是唯一的 B.不是唯一的 C.唯一性不確定 D.唯一性與原因的邊的權(quán)數(shù)有關(guān)40.在無(wú)向圖G的鄰接矩陣A中，若Ai,j等于1，則Aj,i等于A. i+j B. i-j C. 1 D. 041.圖的深度優(yōu)先或廣度優(yōu)先遍歷的空間復(fù)雜性均為(訪問(wèn)標(biāo)志位數(shù)組空間)A. O(n) B. O(e) C. O(n-e) D

15、. O(n+e)42.已知一個(gè)有序表為(12、18、24、35、47、50、62、83、90、115、134)，當(dāng)二分查找值為90的元素時(shí)， B 次比較后查找成功；當(dāng)二分查找值為47的元素時(shí)， D 次比較后查找成功。 A. 1 B. 2 C. 3 D. 443.散列函數(shù)有一個(gè)共同性質(zhì)，即函數(shù)值應(yīng)當(dāng)以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.目前以

16、比較為基礎(chǔ)的內(nèi)部排序時(shí)間復(fù)雜度T(n)的范圍是待排序的記錄的初始排列狀態(tài)無(wú)關(guān)的是 B 。A. O(log2 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. 6 B. 7 C. 8 D. 2047.在歸并排序過(guò)程中，需歸并的趟數(shù)為A. n B. C. log2 n向上取整D. log2 n向下取整48.一組記錄排序碼為(46、79、56、38、40、84)，則利用堆

17、排序的方法建立的初始堆為 B 。A. (79、46、56、38、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ù)雜性為，空間復(fù)雜性為壞情況下（如初始記錄已

18、有序），快速排序的時(shí)間復(fù)雜性為 D ，空間復(fù)雜性為 A 。A. O(n) B. O(log2 n) C. O(nlog2 n) D. O(n2 )二、填空題1.在線性結(jié)構(gòu)中第一結(jié)點(diǎn)前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有驅(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)有 個(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í)，它包括的集合K和K上關(guān)系 的集合R。* 4.對(duì)于一個(gè)二維數(shù)組A1.m,1.n，若按行序?yàn)橹餍虼鎯?chǔ)，則任一元素Ai,j的相對(duì)地址（即偏移地址）為 1 (i-1)*

19、n+j-1 。5.對(duì)于順序存儲(chǔ)的線性表，當(dāng)隨機(jī)插入或刪除一個(gè)元素時(shí)，約需平均移動(dòng)表長(zhǎng)半 的元素。6.對(duì)于長(zhǎng)度為n的順序表，插入或刪除元素的時(shí)間復(fù)雜性為或隊(duì)列，插入或刪除元素的時(shí)間復(fù)雜性為 2 O(1) 。7.在具有n個(gè)單元、順序存儲(chǔ)的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有個(gè)元素。8.從順序表中刪除第i個(gè)元素時(shí)，首先把第i個(gè)元素賦給帶回，接著從 2 鏈接指針 開(kāi)始向后的所有元素均 3 前移 一個(gè)位置，最后使線性表的長(zhǎng)度 4 減1 。9.在線性表的順序存儲(chǔ)中，元素之間的邏輯關(guān)系是通過(guò)決定的；在線性表的鏈接存儲(chǔ)中，元素之間的邏輯關(guān)系是通過(guò) 2 鏈接指針 決定的。10.一個(gè)單鏈表中刪除*p結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行如下操作:(1

20、)q=p->next;(2)p->data=p->next->data;(4)free(q);11.若要在一個(gè)單鏈表中的*p結(jié)點(diǎn)之前插入一個(gè)*s結(jié)點(diǎn)時(shí)，可執(zhí)行如下操作:;(2)p->next=s;(3)t=p->data;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ǔ)空間，在算

21、法中不必考慮 5 溢出 的發(fā)生，因此適應(yīng)數(shù)據(jù)量變化較大的情況。13.無(wú)論對(duì)于順序存儲(chǔ)還是鏈接存儲(chǔ)的棧和隊(duì)列來(lái)說(shuō)，進(jìn)行插入或刪除運(yùn)算的時(shí)間復(fù) 雜性均相同，則為 1 O(1) 。0 0 2 0*14.一個(gè)稀疏矩陣為 3 0 0 0，則對(duì)應(yīng)的三元組線性表為0 0 -1 5 。 0 0 0 015.對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的樹(shù)，則該樹(shù)中所有結(jié)點(diǎn)的度之和為。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)為， 若它存在左孩子，則左孩子結(jié)點(diǎn)的下標(biāo)為 2 10 ，若它存在右孩子，則右孩子

22、結(jié)點(diǎn)的下標(biāo)為 3 11 。18.假定一棵二叉樹(shù)的廣義表表示為A(B(，D)，C(E(G)，F(xiàn))，則該樹(shù)的深度為 度為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)度為 。21.假定在二叉樹(shù)的鏈接存儲(chǔ)中，每個(gè)結(jié)點(diǎn)的結(jié)構(gòu)為leftdataright ，其中 data為值域，left和right分別為鏈接左、右孩子結(jié)點(diǎn)的指針域，請(qǐng)?jiān)谙旅嬷行虮闅v算法 中畫(huà)有橫線的地

23、方填寫(xiě)合適的語(yǔ)句。void inorder(bt); if bt!=nil ；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ù)雜性為2 ， 采用鄰接表表示的空間復(fù)雜性為。24.已知一個(gè)無(wú)向圖的鄰接矩陣如下所示，則從頂點(diǎn)A出發(fā)按深度優(yōu)先搜索遍歷得到的 頂點(diǎn)序列為 1 ABCDFE ，按廣度優(yōu)先搜索遍歷得到的頂點(diǎn)序列為 2 ABCEFD 。A B C D E F0 1 1 0 1 0A1 0 1 0 1 1B1 1 0 1 0 0C0 0 1

24、 0 0 1D1 1 0 0 0 1E0 1 0 1 1 0F25.已知一個(gè)圖如下所示，在該圖的最小生成樹(shù)中，各邊的權(quán)值之和為 10226.假定在有序表A1.20上進(jìn)行二分查找，則比較一次查找成功的結(jié)點(diǎn)數(shù)為， 比較兩次查找成功的結(jié)點(diǎn)數(shù)為 22 ，比較三次查找成功的結(jié)點(diǎn)數(shù)為 34 ，比較四次查找成功結(jié)點(diǎn)數(shù)為 48 ，比較五次查找成功的結(jié)點(diǎn)數(shù)為 55 ，平均查找長(zhǎng)度為 63.7 。27.在索引查找或分塊查找中，首先查找，然后再查找相應(yīng)的子表或塊 ，整個(gè)索引查找的平均查找長(zhǎng)度等于查找索引表的平均查找長(zhǎng)度與查找相應(yīng)子表的平均查找長(zhǎng)度之 3 和 。28.在散列存儲(chǔ)中，裝填因子的值越大，存取元素時(shí)發(fā)生沖突

25、的可能性就，當(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的同義詞元素共有30.在對(duì)一組記錄(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è)冒泡

26、排序過(guò)程中共需進(jìn)行 25 趟后才能完成。32.在歸并排序中，若待排序記錄的個(gè)數(shù)為20，則共需要進(jìn)行趟歸并中，是把長(zhǎng)度為 24 的有序表歸并為長(zhǎng)度為 38 的有序表。33.在直接插入和直接選擇排序中，若初始數(shù)據(jù)基本正序，則選用序 ，若初始數(shù)據(jù)基本反序，則選用 2 直接選擇排序 。34.在堆排序、快速排序和歸并排序中，若只從節(jié)省空間考慮，則應(yīng)首先選取排序 方法，其次選取 2 快速排序 方法，最后選取 3 歸并排序 方法；若只從 6排序結(jié)果的穩(wěn)定性考慮，則應(yīng)選取 4 歸并排序 ；若只從平均情況下排序最快考慮，則應(yīng)選取 5 快速排序 方法；若只從最壞情況下排序最快并且要節(jié)省內(nèi)存考慮，則應(yīng)選取 6 堆排

27、序 方法。三、判斷題1數(shù)據(jù)元素是數(shù)據(jù)的最小單位（× ）。2數(shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位（ × ）。3順序存儲(chǔ)的線性表可以隨機(jī)存取（ ）。4線性表中的元素可以是各種各樣的，但同一線性表中的數(shù)據(jù)元素具有相同的特性， 因此，是屬于同一數(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使用

28、三元組表示稀疏矩陣的元素，有時(shí)并不能節(jié)省存儲(chǔ)時(shí)間（ ）。*10.線性表可以看成是廣義表的特例，如果廣義表中的每個(gè)元素都是原子，則廣義表便成為線性表（ ）。11.由樹(shù)轉(zhuǎn)換成二叉樹(shù)，其根結(jié)點(diǎn)的右子樹(shù)總是空的（ ）。12.后序遍歷樹(shù)和中序遍歷與該樹(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)椴恢?/p>

29、道樹(shù) 的根結(jié)點(diǎn)是哪一個(gè)（× ）。16.在哈夫曼編碼中，當(dāng)兩個(gè)字符出現(xiàn)的頻率相同時(shí)，其編碼也相同，對(duì)于這種情況應(yīng)作特殊處理（× ）。17.有回路的圖不能進(jìn)行拓?fù)渑判颍?）。18.連通分量是無(wú)向圖中的極小連通子圖（× ）。 /極大/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)的指針

30、， 由空變?yōu)榉强占纯桑?）。24.當(dāng)待排序的元素很多時(shí)，為了交換元素的位置，移動(dòng)元素要占用較多的時(shí)間，這是影響時(shí)間復(fù)雜性的主要因素（ ）。25.對(duì)于n個(gè)記錄的集合進(jìn)行快速排序，所需要的平均時(shí)間是O(nlog2 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.索引順序文件是一種特殊的順序文件，因此通常存放在磁帶上

31、（× ）。四、綜合題1. 線性表有兩種存儲(chǔ)結(jié)構(gòu)：一是順序表，二是鏈表。試問(wèn)：(1)兩種存儲(chǔ)表示各有哪些主要優(yōu)缺點(diǎn)?(2)如果有n個(gè)線性表同時(shí)并存，并且在處理過(guò)程中各表的長(zhǎng)度會(huì)動(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ù)

32、據(jù)元素不如順序存儲(chǔ)方便，但結(jié)點(diǎn)的插入、刪除操作十分簡(jiǎn)單。(2)應(yīng)選用鏈接表存儲(chǔ)結(jié)構(gòu)。其理由是，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)用一組任意的存儲(chǔ)單元依次存儲(chǔ)線性表里各元素，這里存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(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è)城

33、市的設(shè)計(jì)和規(guī)劃合適嗎?為什么?2.解答: 不合適。因?yàn)橐粋€(gè)城市的設(shè)計(jì)和規(guī)劃涉及非常多的項(xiàng)目，很復(fù)雜，經(jīng)常需要修改、 擴(kuò)充和刪除各種信息，才能適應(yīng)不斷發(fā)展的需要。有鑒于此，順序線性表不能很好適應(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)有元素的空

34、集合稱為空棧；(2)線性結(jié)構(gòu)。除棧底元素和棧頂元素外，棧中任一元素均有唯一的前驅(qū)元素和后繼元素；(3)受限制的運(yùn)算。只允許在棧頂實(shí)施壓入或彈出操作，且棧頂位置由棧指針?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ǔ)空間的大小）為m。當(dāng)有元素要加入隊(duì)列時(shí)，若rearm（初始時(shí)rea

35、t0），則發(fā)生隊(duì)列的上溢現(xiàn)象，該元素不能加入隊(duì)列。這里要特別注意的是：隊(duì)列的假溢出現(xiàn)象，隊(duì)列中還有空余的空間，但元素不能進(jìn)隊(duì) 列。造成這種現(xiàn)象的原因是由于隊(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ì)首之前

36、，但邏輯上隊(duì)首依然在前，作插入和刪除運(yùn)算時(shí)仍按“先進(jìn)先出”的原則。6. 兩個(gè)字符串相等的充要條件是什么?6. 解答: 兩個(gè)字符串相等的充要條件是：兩個(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)下圖。E IK 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ù)的前序

37、序列和中序序列，則可唯一地確定一棵二叉樹(shù)。9. 證明利用前序遍歷的結(jié)果序列能夠得到各子樹(shù)的根，即從左到右檢查前序遍歷序列，當(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

38、 ，Pi ；同理，對(duì)于右子樹(shù)有Ii1 ，Ii2 ，InPi1 ，Pi2 ，Pn對(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?，F(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)/2k

39、k(k1)/2(k1)(k1)1/2可知當(dāng)頂點(diǎn)數(shù)k1時(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 條，

40、另一方面，圖G中的任一條邊均關(guān)聯(lián) G中的兩個(gè)頂點(diǎn)，即一條邊均要分別計(jì)入兩個(gè)不同的dj 和di 中，故dj 中的邊數(shù)應(yīng)為G中邊數(shù)的兩倍，即有nj 2ei-112.證明：若無(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

41、 后，vi1 一定為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ù)圖就不存在， 10圖中會(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的記

42、錄；(3)查找成功，且表中有若干個(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ù)

43、量級(jí)上兩者是相同的,即O(n)。(2) 解答:相同的。其分析類似于(1)。兩者在等概率下的平均長(zhǎng)度為(n1)/2，數(shù)量級(jí)上為 O(n)。(3) 解答:不相同。其分析完全與(1)相同，其結(jié)論也完全相同。14.假定有n個(gè)關(guān)鍵字，它們具有相同的Hash函數(shù)值，用線性探測(cè)方法把這n個(gè)關(guān)鍵字存入到Hash地址空間中要做多少次探測(cè)?14. 解答:由于線性探測(cè)的查找次數(shù)主要取決于裝載因子，即與Hash地址空間的占用情況有關(guān)。假定初始時(shí)Hash地址空間為空，在此情況下連續(xù)裝入n個(gè)具有相同的Hash函數(shù)值的關(guān)鍵字所需的總探測(cè)次數(shù)為12nn(n1)/215.有一個(gè)2000項(xiàng)的表，欲采用等分區(qū)間順序查找方法進(jìn)行查找

44、，問(wèn)(1)每塊的理想長(zhǎng)度是多少?(2)分成多少塊最為理想?(3)平均查找長(zhǎng)度是多少?(4)若每塊長(zhǎng)度為20，平均查找長(zhǎng)度是多少?15.解答：(1)在給定n的前提下，理想的塊長(zhǎng)d為n200045(2)因查找方法為等分區(qū)間順序查找，長(zhǎng)度為n的表被分成bn/d塊，d為塊長(zhǎng)，故有bn/d2000/4545(3)平均查找長(zhǎng)度為ASLbd/21(4545)/2146(4)因每塊的長(zhǎng)度為20，所以表被分成b塊，其平均查找ASL長(zhǎng)度為bn/d2000/20100ASL(bd)/21(10020)/216116.在執(zhí)行某種排序算法的過(guò)程中，出現(xiàn)了排序碼朝著最終排序序列相反的方向移動(dòng)， 從而認(rèn)為該排序算法是不穩(wěn)定

45、的，這種說(shuō)法對(duì)嗎?為什么?16. 解答:這種說(shuō)法不對(duì)。因?yàn)榕判虻牟环€(wěn)定性是指排序前兩個(gè)排序碼相同的元素的相對(duì)次 序經(jīng)過(guò)排序后發(fā)生了變化，而題中未涉及到元素的相對(duì)次序（特別是相同排序碼的元素）的改變，只有移動(dòng)方向，所以此種說(shuō)法不對(duì)。17.設(shè)有5000個(gè)無(wú)序的元素，希望用最快速度挑選出其中前10個(gè)最大的元素。在以下 的排序方法中，采用哪種方法最好?為什么?快速排序，堆排序，歸并排序，基數(shù)排序的Shell排序。17. 解答:上面所列的幾種排序方法的速度都很塊，但快速排序、歸并排序、基數(shù)排序和希爾排序都是在排序結(jié)束后才能確定數(shù)據(jù)元素的全部順序，而無(wú)法知道排序過(guò)程中部分元素的有序性。而堆排序則每次輸入一

46、個(gè)最大（或最小）的元素，然后對(duì)堆進(jìn)行調(diào)整，保證堆頂?shù)脑乜偸怯嘞略刂凶畲螅ɑ蜃钚。┑摹８鶕?jù)題意，只要選取前10個(gè)最大的元素，故采用堆排序方法是合適的。*18.證明對(duì)一個(gè)長(zhǎng)度為n的任意文件進(jìn)行排序，至少需要作nlog2 n比較。18.證明在排序過(guò)程中，每次時(shí)行元素的比較產(chǎn)生兩種路徑。如果排序過(guò)程至少需作t次比較， 則有2t 條路徑。由于n個(gè)結(jié)點(diǎn)總共有n 種不同的排列,因而必須有n 種不同的比較路徑。于是 2t n!即 tlog2 n!因?yàn)?log2 n!nlog2 nn/ln21/2log2 nO(1)故有 log2 n!nlog2 ntnlog2 n證畢。19.判斷下列序列是否是堆。若不是堆

47、，則把它們依次調(diào)整為堆。(1) (100，85，98，77，80，60，82，40，20，10，66)；(2) (100，98，85，82，80，77，66，60，40，20，10)(3) (100，85，40，77，80，60，66，98，82，10，20)；(4) (10，20，40，60，66，77，80，82，85，98，100)；19. 解答:根據(jù)堆的定義可知堆中元素滿足下面中的某一個(gè)式子的關(guān)系， k2i k2i ki 或 kik2i1 k2i1因此(1)、(2)和(4)序列是堆。(3)不是堆。(3) 調(diào)整為100,98,66,85,80,60,40,77,82,10,20后成為堆。

48、*20.試列出文件的存儲(chǔ)結(jié)構(gòu)以及其相應(yīng)文件類型，并簡(jiǎn)略回答其特點(diǎn)。20. 解答:(1)順序結(jié)構(gòu)，相應(yīng)的文件為順序文件。這種文件中的記錄按存入文件的時(shí)間先后次序順序存放。當(dāng)記錄的物理存取順序與它們的關(guān)鍵碼大小順序一致時(shí)，則物理順序和邏輯順序是一致的。順序文件適合順序存取。(2)計(jì)算尋址結(jié)構(gòu)，相應(yīng)的文件為散列文件。這種文件中的記錄，在存放時(shí)，是根據(jù)它的關(guān)鍵碼值經(jīng)過(guò)散列函數(shù)計(jì)算來(lái)確定其地址的，散列函數(shù)把一個(gè)記錄的關(guān)鍵碼值經(jīng)過(guò)計(jì)算轉(zhuǎn)化為該記錄所對(duì)應(yīng)的地址。散列文件適合于隨機(jī)存取。(3)帶索引的結(jié)構(gòu)，相應(yīng)的文件為帶索引文件。這種文件帶有一個(gè)索引表，索引表中的每一項(xiàng)內(nèi)容包含一個(gè)關(guān)鍵碼值和對(duì)應(yīng)于該關(guān)鍵碼值的

49、相應(yīng)地址。一般情況下，索引表本身是按關(guān)鍵碼值的大小順序排列的，而帶索引文件本身內(nèi)容的物理順序與其邏輯順序可以是一致的，也可以是不一致的。帶索引文件是以索引表的物理順序來(lái)體現(xiàn)文件的邏輯次序的，即索引表的物理順序?qū)崿F(xiàn)了文件的線性結(jié)構(gòu)。由以上三種文件可以派生出其它類型的文件。21.編寫(xiě)下列算法(1)向類型有l(wèi)ist的線性表L的第i個(gè)元素（0iL.len）之后插入一個(gè)新元素x。(1) 解答: status insert(SqList L,int i,ElemType x)/ 向線性表L中第i個(gè)元素之后插入值為x的新元素(1) if (L.len = =m0) error('overflow&#

50、39;);(2) if (i<0) | (i>L.len) error ('out of range');(3) for (j=L.len ;j>= i1;-j )L.vecj1L.vecj;(4) L.veci1x;(5) L.lenlen1;(2)從類型為list的線性表L中刪除其值等于x的所有元素。(2) 解答: status delete(L,x) / 從線性表L中刪除其值等于x的所有元素i1;while (i<L.len )if (L.veci= =x )() for( ji1 ;j<= L.len ;+j)L.vecj1L.vecj;(

51、) L.lenL.len1;else ii1;(3)將兩個(gè)有序表A和B合并成一個(gè)有序表C，其中A，B，C均為list類型的變參。(3)解答:status merge(A,B,C)/ 將兩個(gè)有序表A和B合并成一個(gè)有序表C(1) if ( A.lenB.len>m0 ) error('overflow'):(2) i=1;j1;k1;/ i和j分別作為掃描數(shù)組A和B的指針，k指示存入數(shù)組C中元素的下標(biāo)位置(3) while (i<A.len) && (j<B.len)if (A.veci<B.vecj) C.veckA.veci;ii1;kk

52、1;else C.veckB.vecj;jj1;kk1;(4) while (i<A.len)C.veckA.veci;ii1;kk1;(5) while (j<B.len )C.veckB.vecj;jj1;kK1;22.編寫(xiě)下列算法，假定單鏈表的表頭指針用HL表示，類型為linklist。(1)將一個(gè)單鏈表中的所有結(jié)點(diǎn)按相反次序鏈接。(1) 解答:status contrary(HL)/ 使HL單鏈表中的所有結(jié)點(diǎn)按相反次序鏈接pHL ; /p指向未被逆序的第一個(gè)結(jié)點(diǎn)，初始指向原表頭結(jié)點(diǎn) HLnil; /HL指向逆序后的表頭結(jié)點(diǎn)，初始值為空while (p!=nil )(1) q

53、p; /q指向?qū)⒈荒嫘蜴溄拥慕Y(jié)點(diǎn)(2) pp.next;(3) q.nextHL;(4) HLq;(2)刪除單鏈表中第i個(gè)（i1）結(jié)點(diǎn)。(2) 解答:status delete(HL,i)(1) if (i<0) or (HLnil) error('not h&&le');(2) if (i1 ) HLHL->next;return ;(3) j1; pHL; /p指針?biāo)赶虻慕Y(jié)點(diǎn)，是單鏈表中第j個(gè)結(jié)點(diǎn) while (j<i1) && (p.next!=nil) jj1;pp->next;/ 尋找第i個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)(4)

54、 if (p->next!= =nil)p->nextp->next->next;else error('out of range');(3)刪除單鏈表中由指針p所指向的結(jié)點(diǎn)。(3) 解答:status delete(HL,P,X)/ 刪除單鏈表HL中由指針p所指向的結(jié)點(diǎn)if (p->nextnil ) error ('not delete');Xp->data; qp->next;p->datap->next->data;p->nextp->next->next;free(q);或者

55、：status delete(HL,P,X) if ( HLp ) XHL->data ; HLHL->next; free(p);else(1) qHL;(2) while (q->next!=nil) && (q->next!=p)qq->next;(3) if (q->nextp)Xp->data;q->nextp->next;free(p)else error('*p結(jié)點(diǎn)不存在');(4)從帶有附加表頭結(jié)點(diǎn)的循環(huán)單鏈表中刪除其值等于x的第一個(gè)結(jié)點(diǎn)。(4) 解答:status delete(HL,x) (1) qHL; pHL->next;(2) while (p!=HL) && (p->data!=x) qp;pp->next;(3) if (p= =HL) error('not found');else q->next