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

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

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

3、ontC. (rear-1) % n= =rear D. (rear+1) % n= =front.從一個具有n個節(jié)點的單鏈表中查找其值等于x結(jié)點時，在查找成功的情況下，需 平均比較 D 個結(jié)點。A. n B. n/2 C. (n-1)/2 D. (n+1)/2.在一個單鏈表中，已知*q結(jié)點是*p結(jié)點的前驅(qū)結(jié)點，若在*q和*p之間插入*s結(jié)點， 則執(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.向一個棧項指針為hs的鏈棧中插入一個*s結(jié)點時，則執(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.在一個鏈隊列中，假定front和rear分別為隊首指針和隊尾指針，則進行插入*s結(jié)點的操作時應(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. 一個有限序列，可以為空 B. 一個有限序列，不能為空C. 一個無限序列，可以為空 D. 一個無限序列，不能為空13.對順序存儲的線性表，設(shè)其長度為n，在任何位置上插入或刪除操作都是等概率的， 刪除一個元素時大約要移動表中的 C 個元素。A. n+1 B. n-1 C. (n-1)/2 D. n 114.線性表采用鏈式存儲時，其地址。A. 必須是連續(xù)的 B. 部分地址必須是連續(xù)的C. 一定是不連續(xù)的 D. 連續(xù)與否均可以15.設(shè)單鏈表中指針p指著結(jié)點(數(shù)據(jù)域為m)，指針f指著將要插入的新結(jié)點(數(shù)據(jù)域為x)，當x插在結(jié)點m之

6、后時，只要先修改p->link=f即可。A. f->link=p; B. f->link=p->link;C. p->link=f->link; D. f=nil;16.在雙向鏈表存儲結(jié)構(gòu)中，刪除p所指的結(jié)點時需修改指針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.在雙向鏈表存儲結(jié)構(gòu)中，刪除p所指的結(jié)點的前趨結(jié)點（若存在）時需修改指針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ù)線性表的鏈式存儲結(jié)構(gòu)，每個結(jié)點所含指針的個數(shù)，鏈表分為單鏈表和。A. 循環(huán)鏈表 B. 多重鏈表 C. 普通鏈表 D. 無頭結(jié)點鏈表19.在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的數(shù)據(jù)叫A. 存儲

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

10、9;bcdefef'23.假定在一棵二叉樹中，雙分支結(jié)點數(shù)為15個，單分支結(jié)點數(shù)為32個，則葉子結(jié)點 數(shù)為 B 。 A. 15 B. 16 C. 17 D. 4724.假定一棵二叉樹的結(jié)點數(shù)為18個，則它的最小高度。A. 4 B. 5 C. 6 D. 1825.在一棵二叉樹中第五層上的結(jié)點數(shù)最多為A. 8 B. 15 C. 16 D. 3226.在一棵具有五層的滿二叉樹中，結(jié)點總數(shù)為。A. 31 B. 32 C. 33 D. 1627.已知8個數(shù)據(jù)元素為(34、76、45、18、26、54、92、65)，按照依次插入結(jié)點的方法生成一棵二叉排序樹后，最后兩層上的結(jié)點總數(shù)為 B 。A. 1

11、 B. 2 C. 3 D. 428.由分別帶權(quán)為9、2、5、7的四個葉子結(jié)點構(gòu)造一棵哈夫曼樹，該樹的帶權(quán)路徑長度為 C 。 A. 23 B. 37 C. 44 D. 4629.在樹中除根結(jié)點外，其余結(jié)點分成m (m0)個T1,T2,T3.Tm,每 2個集合又都是樹，此時結(jié)點T稱為Ti的父結(jié)點，Ti稱為T的子結(jié)點(1im)。A. 互不相交 B. 可以相交C. 葉結(jié)點可以相交 D. 樹枝結(jié)點可以相交30.下面答案。A. 二叉樹中的每個結(jié)點的兩棵子樹的高度差的絕對值不大于B. 二叉樹中的每個結(jié)點的兩棵子樹的高度差等于C. 二叉樹中的每個結(jié)點的兩棵子樹是有序的D. 二叉樹中的每個結(jié)點的關(guān)鍵字大于其左子

12、樹（如果存在）所有結(jié)點的關(guān)鍵字值， 且小于其右子樹（如果存在）所有結(jié)點的關(guān)鍵字值。31.如果結(jié)點A有三個兄弟，而且B是A的雙親，則B的出度是A. 3 B. 4 C. 5 D. 132.一個深度為L的滿K叉樹有如下性質(zhì)：第L層上的結(jié)點都是葉子結(jié)點，其余各層上每個結(jié)點都有K棵非空子樹。如果按層次順序從開始對全部結(jié)點編號，編號為n的有右兄弟的條件是 B 。A. (n-1) % k= =0 B. (n-1) % k!=0 C. n % k= =0 D. n % k!=033.在完全二叉樹中，當i為奇數(shù)且不等于時，結(jié)點i的左兄弟是結(jié)點，否則沒有左兄弟。 A. 2i-1 B. i+1 C. 2i+1 D.

13、 i-134.某二叉樹T有n個結(jié)點，設(shè)按某種遍歷順序?qū)中的每個結(jié)點進行編號，編號值為1,2,n且有如下性質(zhì)：T中任一結(jié)點V，其編號等于左子樹上的最小編號減1，而V的右子樹 的結(jié)點中，其最小編號等于V左子樹上結(jié)點的最大編號加1。這時按 B 編號。A. 中序遍歷序列 B. 前序遍歷序列 C. 后序遍歷序列 D. 層次遍歷序列35.在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的A. 1/2 B. 1 C. 2 D. 436.對于一個具有n個頂點和e條邊的無向圖，若采用鄰接表表示，則表頭向量的大小 為 A 。 A. n B. n+1 C. n-1 D. n+e37.具有n個頂點的無向完全

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

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

16、比較為基礎(chǔ)的內(nèi)部排序時間復(fù)雜度T(n)的范圍是待排序的記錄的初始排列狀態(tài)無關(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。進行排序的最小交換次數(shù)是。A. 6 B. 7 C. 8 D. 2047.在歸并排序過程中，需歸并的趟數(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)，則利用快速排序的方法，以第一個記錄為基準得到的一次劃分結(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.在平均情況下快速排序的時間復(fù)雜性為，空間復(fù)雜性為壞情況下（如初始記錄已

18、有序），快速排序的時間復(fù)雜性為 D ，空間復(fù)雜性為 A 。A. O(n) B. O(log2 n) C. O(nlog2 n) D. O(n2 )二、填空題1.在線性結(jié)構(gòu)中第一結(jié)點前驅(qū)結(jié)點，其余每個結(jié)點有且只有驅(qū)結(jié)點；最后一個結(jié)點 3 無 后繼結(jié)點，其余每個結(jié)點有且只有 4 一 個后繼結(jié)點。2.在樹型結(jié)構(gòu)中，樹根結(jié)點沒有 個前驅(qū)結(jié)點；樹葉結(jié)點沒有 3 后繼 結(jié)點，其余每個結(jié)點的 4 后繼 結(jié)點數(shù)不受限制。3.一個數(shù)據(jù)結(jié)構(gòu)用二元組表示時，它包括的集合K和K上關(guān)系 的集合R。* 4.對于一個二維數(shù)組A1.m,1.n，若按行序為主序存儲，則任一元素Ai,j的相對地址（即偏移地址）為 1 (i-1)*

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

20、)q=p->next;(2)p->data=p->next->data;(4)free(q);11.若要在一個單鏈表中的*p結(jié)點之前插入一個*s結(jié)點時，可執(zhí)行如下操作:;(2)p->next=s;(3)t=p->data;12.對于線性表的順序存儲，需要預(yù)先分配好存儲空間，若分配太多則容易造成存儲空間的 1 浪費 ，若分配太少又容易在算法中造成 2 溢出 ，因此適應(yīng)于數(shù)據(jù)量變化不大的情況；對于線性表的鏈接存儲(假定采用動態(tài)結(jié)點)，不需要 3 預(yù)先分配 存儲空間，存儲器中的整個 4 動態(tài)存儲區(qū) 都可供使用，分配和回收結(jié)點都非常方便，能夠有效地利用存儲空間，在算

21、法中不必考慮 5 溢出 的發(fā)生，因此適應(yīng)數(shù)據(jù)量變化較大的情況。13.無論對于順序存儲還是鏈接存儲的棧和隊列來說，進行插入或刪除運算的時間復(fù) 雜性均相同，則為 1 O(1) 。0 0 2 0*14.一個稀疏矩陣為 3 0 0 0，則對應(yīng)的三元組線性表為0 0 -1 5 。 0 0 0 015.對于一棵具有n個結(jié)點的樹，則該樹中所有結(jié)點的度之和為。16.在一棵二叉樹中，度為0的結(jié)點的個數(shù)為n0 ，度為2的結(jié)點的個數(shù)為n2 ，則： n0 = n2 +1 。17.在二叉樹的順序存儲中，對于下標為5的結(jié)點，它的雙親結(jié)點的下標為， 若它存在左孩子，則左孩子結(jié)點的下標為 2 10 ，若它存在右孩子，則右孩子

22、結(jié)點的下標為 3 11 。18.假定一棵二叉樹的廣義表表示為A(B(，D)，C(E(G)，F(xiàn))，則該樹的深度為 度為0的結(jié)點數(shù)為 23 ，度為1的結(jié)點數(shù)為 3 2 ，度為2的結(jié)點數(shù)為 42 ；C結(jié)點是A 結(jié)點的 5 右 孩子，E結(jié)點是C結(jié)點的 6 左 孩子。19.在一棵二叉排序樹中，按遍歷得到的結(jié)點序列是一個有序序列。20.由分別帶權(quán)為3,9,6,2,5的共五個葉子結(jié)點構(gòu)成一棵哈夫曼樹，則帶權(quán)路徑長度為 。21.假定在二叉樹的鏈接存儲中，每個結(jié)點的結(jié)構(gòu)為leftdataright ，其中 data為值域，left和right分別為鏈接左、右孩子結(jié)點的指針域，請在下面中序遍歷算法 中畫有橫線的地

23、方填寫合適的語句。void inorder(bt); if bt!=nil ；22.在圖G的鄰接表表示中，每個頂點鄰接表中所含的結(jié)點數(shù)，對于無向圖來說等于該 頂點的 1 度數(shù) ，對于有向圖來說等于該頂點的 2 出度數(shù) 。23.假定一個圖具有n個頂點和e條邊，則采用鄰接矩陣表示的空間復(fù)雜性為2 ， 采用鄰接表表示的空間復(fù)雜性為。24.已知一個無向圖的鄰接矩陣如下所示，則從頂點A出發(fā)按深度優(yōu)先搜索遍歷得到的 頂點序列為 1 ABCDFE ，按廣度優(yōu)先搜索遍歷得到的頂點序列為 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.已知一個圖如下所示，在該圖的最小生成樹中，各邊的權(quán)值之和為 10226.假定在有序表A1.20上進行二分查找，則比較一次查找成功的結(jié)點數(shù)為， 比較兩次查找成功的結(jié)點數(shù)為 22 ，比較三次查找成功的結(jié)點數(shù)為 34 ，比較四次查找成功結(jié)點數(shù)為 48 ，比較五次查找成功的結(jié)點數(shù)為 55 ，平均查找長度為 63.7 。27.在索引查找或分塊查找中，首先查找，然后再查找相應(yīng)的子表或塊 ，整個索引查找的平均查找長度等于查找索引表的平均查找長度與查找相應(yīng)子表的平均查找長度之 3 和 。28.在散列存儲中，裝填因子的值越大，存取元素時發(fā)生沖突

25、的可能性就，當?shù)闹翟叫?，存取元素時發(fā)生沖突的可能性就 2 越小 。29.給定線性表(18,25,63,50,42,32,90)，用散列方式存儲，若選用h(K)=K % 9作為散列函數(shù)，則元素18的同義詞元素共有 12 個，元素25的同義詞元素共有 20 個，元素50的同義詞元素共有30.在對一組記錄(54,38,96,23,15,72,60,45,83)進行直接選擇排序時，第四次選擇和交換后，未排序記錄(即無序表)為 (54,72,60,96,83) 。31.在對一組記錄(54,38,96,23,15,72,60,45,38)進行冒泡排序時，第一趟需進行相鄰記錄交換的次數(shù)為 17 ，在整個冒泡

26、排序過程中共需進行 25 趟后才能完成。32.在歸并排序中，若待排序記錄的個數(shù)為20，則共需要進行趟歸并中，是把長度為 24 的有序表歸并為長度為 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ù)項是數(shù)據(jù)的基本單位（ × ）。3順序存儲的線性表可以隨機存?。?）。4線性表中的元素可以是各種各樣的，但同一線性表中的數(shù)據(jù)元素具有相同的特性， 因此，是屬于同一數(shù)據(jù)對象（ ）。5在單鏈表中，任何兩個元素的存儲位置之間都有固定的聯(lián)系，因為可以從頭結(jié)點查找任何一個元素（× ）。6在單鏈表中，要取得某個元素，只要知道該元素的指針即可，因此，單鏈表是隨機存取的存儲結(jié)構(gòu)（ × ）。7鏈表的每個結(jié)點中，都恰好包含一個指針（× ）。*8數(shù)組是同類型值的集合（× ）。 /不是集合/*9使用

28、三元組表示稀疏矩陣的元素，有時并不能節(jié)省存儲時間（ ）。*10.線性表可以看成是廣義表的特例，如果廣義表中的每個元素都是原子，則廣義表便成為線性表（ ）。11.由樹轉(zhuǎn)換成二叉樹，其根結(jié)點的右子樹總是空的（ ）。12.后序遍歷樹和中序遍歷與該樹對應(yīng)的二叉樹，其結(jié)果不同（ × ）。13.若有一個結(jié)點是某二叉樹子樹的中序遍歷序列中的最后一個結(jié)點，則它必是該子 樹的前序遍歷序列中的最后一個結(jié)點（× ）。14.若一個樹葉是某子樹的中序遍歷序列中的最后一個結(jié)點，則它必是該子樹的前序 遍歷序列中的最后一個結(jié)點（ ）。15.已知二叉樹的前序遍歷和后序遍歷序列并不能唯一地確定這棵樹，因為不知

29、道樹 的根結(jié)點是哪一個（× ）。16.在哈夫曼編碼中，當兩個字符出現(xiàn)的頻率相同時，其編碼也相同，對于這種情況應(yīng)作特殊處理（× ）。17.有回路的圖不能進行拓撲排序（ ）。18.連通分量是無向圖中的極小連通子圖（× ）。 /極大/19.散列法存儲的基本思想是由關(guān)鍵碼的值決定數(shù)據(jù)的存儲地址（ ）。20.散列表的查找效率取決于散列表造表時選取的散列函數(shù)和處理沖突的方法（ ）。21.m階B-樹每一個結(jié)點的子樹個數(shù)都小于或等于m（ ）。22.中序遍歷二叉排序樹的結(jié)點就可以得到排好序的結(jié)點序列（ ）。23.在二叉排序樹上插入新的結(jié)點時，不必移動其它結(jié)點，僅需改動某個結(jié)點的指針

30、， 由空變?yōu)榉强占纯桑?）。24.當待排序的元素很多時，為了交換元素的位置，移動元素要占用較多的時間，這是影響時間復(fù)雜性的主要因素（ ）。25.對于n個記錄的集合進行快速排序，所需要的平均時間是O(nlog2 n)（ ）。26.對于n個記錄的集合進行歸并排序，所需要的平均時間是O(nlog2 n)（ ）。27.堆中所有非終端結(jié)點的值均小于或等于（大于或等于）左右子樹的值（ ）。 *28.磁盤上的順序文件中插入新的記錄時，必須復(fù)制整個文件（ × ）。*29.在索引順序文件中插入新的記錄時，必須復(fù)制整個文件（× ）。*30.索引順序文件是一種特殊的順序文件，因此通常存放在磁帶上

31、（× ）。四、綜合題1. 線性表有兩種存儲結(jié)構(gòu)：一是順序表，二是鏈表。試問：(1)兩種存儲表示各有哪些主要優(yōu)缺點?(2)如果有n個線性表同時并存，并且在處理過程中各表的長度會動態(tài)發(fā)生變化，線性 表的總數(shù)也會自動地改變。在此情況下，應(yīng)選用哪種存儲結(jié)構(gòu)?為什么?(3)若線性表的總數(shù)基本穩(wěn)定，且很少進行插入和刪除，但要求以最快的速度存取線性表中的元素，那么，應(yīng)采用哪種存儲結(jié)構(gòu)?為什么?1. 解答:(1)順序存儲是按索引（隱含的）直接存取數(shù)據(jù)元素，方便靈活，效率高，但插入、刪除操作時將引起元素移動，因而降低效率；鏈接存儲內(nèi)存采用動態(tài)分配，利用率高，但需增設(shè)指示結(jié)點之間有序關(guān)系的指針域，存取數(shù)

32、據(jù)元素不如順序存儲方便，但結(jié)點的插入、刪除操作十分簡單。(2)應(yīng)選用鏈接表存儲結(jié)構(gòu)。其理由是，鏈式存儲結(jié)構(gòu)用一組任意的存儲單元依次存儲線性表里各元素，這里存儲單元可以是連續(xù)的，也可以是不連續(xù)的。這種存儲結(jié)構(gòu)，在對元素作插入或刪除運算時，不需要移動元素，僅修改指針即可。所以很容易實現(xiàn)表的容量擴充。(3)應(yīng)選用順序存儲結(jié)構(gòu)。其理由是，每個數(shù)據(jù)元素的存儲位置和線性表的起始位置相差一個和數(shù)據(jù)元素在線性表中的序號成正比的常數(shù)。由此，只要確定了起始位置，線性表中任一數(shù)據(jù)元素都可隨機存取，所以線性表的順序存儲結(jié)構(gòu)是一種隨機存取的存儲結(jié)構(gòu)。而鏈表則是一種順序存取的存儲結(jié)構(gòu)。2. 用線性表的順序結(jié)構(gòu)來描述一個城

33、市的設(shè)計和規(guī)劃合適嗎?為什么?2.解答: 不合適。因為一個城市的設(shè)計和規(guī)劃涉及非常多的項目，很復(fù)雜，經(jīng)常需要修改、 擴充和刪除各種信息，才能適應(yīng)不斷發(fā)展的需要。有鑒于此，順序線性表不能很好適應(yīng)其需要，故是不合適的。3. 在單鏈表和雙向表中，能否從當前結(jié)點出發(fā)訪問到任一結(jié)點?3. 解答: 在單鏈表中只能由當前結(jié)點訪問其后的任一結(jié)點，因為沒有指向其前驅(qū)結(jié)點的指 針。而在雙向鏈表中，既有指向后繼結(jié)點的指針又有指向前驅(qū)結(jié)點的指針，故可由當前結(jié)點出發(fā)訪問鏈表中任一結(jié)點。4. 試述棧的基本性質(zhì)?4. 解答: 由棧的定義可知，這種結(jié)構(gòu)的基本性質(zhì)綜述如下：(1)集合性。棧是由若干個元素集合而成，當沒有元素的空

34、集合稱為空棧；(2)線性結(jié)構(gòu)。除棧底元素和棧頂元素外，棧中任一元素均有唯一的前驅(qū)元素和后繼元素；(3)受限制的運算。只允許在棧頂實施壓入或彈出操作，且棧頂位置由棧指針所指示；(4)數(shù)學(xué)性質(zhì)。當多個編號元素依某種順序壓入，且可任意時刻彈出時，所獲得的編號元素排列的數(shù)目，恰好滿足卡塔南數(shù)列的計算，即：n n 2n /(n1)其中，n為編號元素的個數(shù)，Cn 是可能的排列數(shù)目。5. 何謂隊列的上溢現(xiàn)象?解決它有哪些方法，且分別簡述其工作原理。5. 解答: 在隊列的順序存儲結(jié)構(gòu)中，設(shè)隊頭指針為front,隊尾指針為rear,隊的容量（存儲空間的大?。閙。當有元素要加入隊列時，若rearm（初始時rea

35、t0），則發(fā)生隊列的上溢現(xiàn)象，該元素不能加入隊列。這里要特別注意的是：隊列的假溢出現(xiàn)象，隊列中還有空余的空間，但元素不能進隊 列。造成這種現(xiàn)象的原因是由于隊列的操作方式所致。解決隊列的上溢有以下幾種方法：(1)建立一個足夠大的存儲空間，但這樣做往往會造成空間使用的效率低。(2)當出現(xiàn)假溢出時，可采用以下幾種方法：采用平移元素的方法。每當隊列中加入一個元素時，隊列中已有的元素向隊頭 移動一個位置（當然要有空余的空間可移）；每當刪去一個隊頭元素時，則依次序移隊中的元素，始終使front指針指向隊列 中的第一個位置；采用循環(huán)隊列方式。把隊頭隊尾看成是一個首尾相鄰的循環(huán)隊列，雖然物理上 隊尾在隊首之前

36、，但邏輯上隊首依然在前，作插入和刪除運算時仍按“先進先出”的原則。6. 兩個字符串相等的充要條件是什么?6. 解答: 兩個字符串相等的充要條件是：兩個串的長度相等，且對應(yīng)位置的字符相等。*7. 畫出廣義表(A(B(E，F(xiàn)(J)，C，D(G(K，L)，H，I)對應(yīng)的樹型結(jié)構(gòu)。7. 解答: 根據(jù)廣義表的結(jié)構(gòu)可知，該樹的根結(jié)點為A；而B、C、D為A的子樹，B又有兩棵子 樹等等，該廣義表對應(yīng)的樹型結(jié)構(gòu)見下圖。E IK L*8. 對于二叉排序樹，當所有結(jié)點的權(quán)都相等的情況下，最佳二叉排序樹有何特點。8. 解答:其特點是只有最下面的二層結(jié)點可以小于，其它結(jié)點的度數(shù)必須為。9. 試證明：已知一棵二叉樹的前序

37、序列和中序序列，則可唯一地確定一棵二叉樹。9. 證明利用前序遍歷的結(jié)果序列能夠得到各子樹的根，即從左到右檢查前序遍歷序列，當?shù)?到根結(jié)點之后，利用根結(jié)點在中序遍歷序列中的位置可以確定其左右子樹，這樣便可逐次確定整個二叉樹。假設(shè)BT為二叉樹的根，P1 ，P2 ，Pn 為前序遍歷序列，I1 ，I2 ，In 為中 序遍歷序列。由前序遍歷序列可以得到BTP1 。在中序遍歷序列中查找等于P1 的結(jié)點，設(shè)該結(jié)點為Ii ，則有Ii P1 。根據(jù)二叉樹中序遍歷的原理，則該二叉樹可被分成左右兩棵子樹：對于左子樹，在中序遍歷序列中有I1 ，I2 ，Ii1 ，依此序列在前序遍歷序列中可以得到其左子樹為P2 ， P3

38、 ，Pi ；同理，對于右子樹有Ii1 ，Ii2 ，InPi1 ，Pi2 ，Pn對于這兩棵子樹而言，其左子樹的根為P2 ，其右子樹的根為Pi1 。依此類推，用同樣的方法就可以確定整個二叉樹。10.證明n個頂點的無向完全圖的邊數(shù)的n(n1)/2。10.證明方法一：用歸納法證明當n1時，邊數(shù)為0，結(jié)論成立。當n2時，邊數(shù)為1，結(jié)論成立。當n1,2,k時均成立，即當nk時，邊數(shù)為k(k1)/2?，F(xiàn)證明當nk1時若仍然 成立，則結(jié)論正確。由前面證得，對于有k個頂點時，其邊數(shù)總和為 k(k1)/2。當再增加一個新頂點時，由于是無向完全圖，故該頂點到原來各個頂點均有一條邊， 這樣就共有邊數(shù)為k(k1)/2k

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

40、另一方面，圖G中的任一條邊均關(guān)聯(lián) G中的兩個頂點，即一條邊均要分別計入兩個不同的dj 和di 中，故dj 中的邊數(shù)應(yīng)為G中邊數(shù)的兩倍，即有nj 2ei-112.證明：若無向圖G的頂點度數(shù)的最小值大于或等于2，則G有一條回路。12.證明方法一：設(shè)G(V，E)，任取一頂點v1 V，因V1 的度大于或等于2,在v1 的鄰接頂點中任取一個不同于v1 的頂點作為v2 。因v2 的度大于或等于2,在v2 的鄰接頂點中任取一個不同于v2 的頂 點作為v3 。若v1 、v2 、v3 不構(gòu)成回路，則在再v3 的鄰接頂點中任取一個不同于v3 的的頂點 作為v4 ，。因為圖中頂點的集合V是有限的，當取得某個頂點vi

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

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

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

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

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

46、個最大（或最?。┑脑?，然后對堆進行調(diào)整，保證堆頂?shù)脑乜偸怯嘞略刂凶畲螅ɑ蜃钚。┑摹８鶕?jù)題意，只要選取前10個最大的元素，故采用堆排序方法是合適的。*18.證明對一個長度為n的任意文件進行排序，至少需要作nlog2 n比較。18.證明在排序過程中，每次時行元素的比較產(chǎn)生兩種路徑。如果排序過程至少需作t次比較， 則有2t 條路徑。由于n個結(jié)點總共有n 種不同的排列,因而必須有n 種不同的比較路徑。于是 2t n!即 tlog2 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ù)堆的定義可知堆中元素滿足下面中的某一個式子的關(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.試列出文件的存儲結(jié)構(gòu)以及其相應(yīng)文件類型，并簡略回答其特點。20. 解答:(1)順序結(jié)構(gòu)，相應(yīng)的文件為順序文件。這種文件中的記錄按存入文件的時間先后次序順序存放。當記錄的物理存取順序與它們的關(guān)鍵碼大小順序一致時，則物理順序和邏輯順序是一致的。順序文件適合順序存取。(2)計算尋址結(jié)構(gòu)，相應(yīng)的文件為散列文件。這種文件中的記錄，在存放時，是根據(jù)它的關(guān)鍵碼值經(jīng)過散列函數(shù)計算來確定其地址的，散列函數(shù)把一個記錄的關(guān)鍵碼值經(jīng)過計算轉(zhuǎn)化為該記錄所對應(yīng)的地址。散列文件適合于隨機存取。(3)帶索引的結(jié)構(gòu)，相應(yīng)的文件為帶索引文件。這種文件帶有一個索引表，索引表中的每一項內(nèi)容包含一個關(guān)鍵碼值和對應(yīng)于該關(guān)鍵碼值的

49、相應(yīng)地址。一般情況下，索引表本身是按關(guān)鍵碼值的大小順序排列的，而帶索引文件本身內(nèi)容的物理順序與其邏輯順序可以是一致的，也可以是不一致的。帶索引文件是以索引表的物理順序來體現(xiàn)文件的邏輯次序的，即索引表的物理順序?qū)崿F(xiàn)了文件的線性結(jié)構(gòu)。由以上三種文件可以派生出其它類型的文件。21.編寫下列算法(1)向類型有l(wèi)ist的線性表L的第i個元素（0iL.len）之后插入一個新元素x。(1) 解答: status insert(SqList L,int i,ElemType x)/ 向線性表L中第i個元素之后插入值為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)將兩個有序表A和B合并成一個有序表C，其中A，B，C均為list類型的變參。(3)解答:status merge(A,B,C)/ 將兩個有序表A和B合并成一個有序表C(1) if ( A.lenB.len>m0 ) error('overflow'):(2) i=1;j1;k1;/ i和j分別作為掃描數(shù)組A和B的指針，k指示存入數(shù)組C中元素的下標位置(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.編寫下列算法，假定單鏈表的表頭指針用HL表示，類型為linklist。(1)將一個單鏈表中的所有結(jié)點按相反次序鏈接。(1) 解答:status contrary(HL)/ 使HL單鏈表中的所有結(jié)點按相反次序鏈接pHL ; /p指向未被逆序的第一個結(jié)點，初始指向原表頭結(jié)點 HLnil; /HL指向逆序后的表頭結(jié)點，初始值為空while (p!=nil )(1) q

53、p; /q指向?qū)⒈荒嫘蜴溄拥慕Y(jié)點(2) pp.next;(3) q.nextHL;(4) HLq;(2)刪除單鏈表中第i個（i1）結(jié)點。(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指針所指向的結(jié)點，是單鏈表中第j個結(jié)點 while (j<i1) && (p.next!=nil) jj1;pp->next;/ 尋找第i個結(jié)點的前驅(qū)結(jié)點(4)

54、 if (p->next!= =nil)p->nextp->next->next;else error('out of range');(3)刪除單鏈表中由指針p所指向的結(jié)點。(3) 解答:status delete(HL,P,X)/ 刪除單鏈表HL中由指針p所指向的結(jié)點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é)點不存在');(4)從帶有附加表頭結(jié)點的循環(huán)單鏈表中刪除其值等于x的第一個結(jié)點。(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