1、數 據 結 構 習 題 集 一、選擇題 .在一個長度為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 。 A. 先存入元素，后移動棧頂指針 B.先移動棧頂指針，后存入元素 .在一個順序存儲的循環隊列中，隊首指針指向隊首元素的 A 。 A. 前一個位置 B. 后一

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

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

6、. 連續與否均可以 15.設單鏈表中指針p指著結點(數據域為m)，指針f指著將要插入的新結點(數據域為x)，當x插在結點m之后時，只要先修改 B 后修改p->link=f即可。 A. f->link=p; B. f->link=p->link; C. p->link=f->link; D. f=nil; 16.在雙向鏈表存儲結構中，刪除p所指的結點時需修改指針 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.在雙向鏈表存儲結構中，刪除p所指的結點的前趨結點（若存在）時需修改指針 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.根據線性表的鏈

9、式存儲結構，每個結點所含指針的個數，鏈表分為單鏈表和 B 。 A. 循環鏈表 B. 多重鏈表 C. 普通鏈表 D. 無頭結點鏈表 19.在數據結構中，與所使用的計算機無關的數據叫 C 結構。 A. 存儲 B. 物理 C. 邏輯 D. 物理和存儲 20.二分法查找 A 存儲結構。 A. 只適用于順序 B. 只適用于鏈式 C. 既適用于順序也適用于鏈式 D. 既不適合于順序也不適合于鏈式 21.在線性表的鏈式存儲結構中，邏輯上相鄰的元素在物理位置上 B 。 A. 一定相鄰 B. 不一定相鄰 C. 有時相鄰 22.設字符串s1='abcdefg',s2='pqrst'

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

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

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

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

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

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

16、成功；當二分查找值為47的元素時， D 次比較后查找成功。 A. 1 B. 2 C. 3 D. 4 43.散列函數有一個共同性質，即函數值應當以 D 取其值域的每個值。 A. 最大概率 B. 最小概率 C. 平均概率 D. 同等概率 44.設散列地址空間為0m1,k為關鍵字，用p去除k，將所得的余數作為k的散列地址，即H(k)k % p。為了減少發生沖突的頻率，一般取p為 D 。 A. 小于m的最大奇數 B. 小于m的最大偶數 C. m D. 小于m的最大素數 45.目前以比較為基礎的內部排序時間復雜度T(n)的范圍是 A ；其比較次數與待排序的記錄的初始排列狀態無關的是 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.設關鍵字序列為：3,7,6,9,8,1,4,5,2。進行排序的最小交換次數是 A 。 A. 6 B. 7 C. 8 D. 20 47.在歸并排序過程中，需歸并的趟數為 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.一組記錄的關鍵碼為(46、79、56、38、40、84)，則利用快速排序的方法，以第一個記錄為基準得到的一次劃分結果為 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.在平均情況下快速排序的時間復雜性為 C ，空間復雜性為 B ；在最壞情況下（如初始記錄已有序），快速排序的時間復雜性為 D

19、 ，空間復雜性為 A 。 A. O(n) B. O(log2 n) C. O(nlog2 n) D. O(n2 ) 二、填空題 1.在線性結構中第一結點 1 無 前驅結點，其余每個結點有且只有 2 一 個前驅結點；最后一個結點 3 無 后繼結點，其余每個結點有且只有 4 一 個后繼結點。 2.在樹型結構中，樹根結點沒有 1 前趨 結點，其余每個結點有且僅有 2 一 個前驅結點；樹葉結點沒有 3 后繼 結點，其余每個結點的 4 后繼 結點數不受限制。 3.一個數據結構用二元組表示時，它包括 1 數據元素 的集合K和K上 2二元關系 的集合R。 * 4.對于一個二維數組A1.m,1.n，若按行序為

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

21、之間的邏輯關系是通過 1 相鄰位置 決定的；在線性表的鏈接存儲中，元素之間的邏輯關系是通過 2 鏈接指針 決定的。 10.一個單鏈表中刪除*p結點時，應執行如下操作: (1)q=p->next; (2)p->data=p->next->data; (3)p->next= 1 q->next或p->next->next ; (4)free(q); 11.若要在一個單鏈表中的*p結點之前插入一個*s結點時，可執行如下操作: (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.對于線性表的順序存儲，需要預先分配好存儲空間，若分配太多則容易造成存儲空間的 1 浪費 ，若分配太少又容易在算法中造成 2 溢出 ，因此適應于數據量變化不大的情況；對于線性表的鏈接存儲(假定采用動態結點)，不需要 3 預先分配 存儲空間，存儲器中的整個 4 動態存儲區 都可供使用，分配和回收結點都非常方便，能夠有效地利用存儲空間，在算法中不必考慮 5 溢出 的發生，因此適應數據量變化較大的情況。 13.無論對于順序存儲還是鏈接存儲的棧和隊列來說，進行插入或刪除運算的時間復 雜性均相同，則

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

24、為A(B(，D)，C(E(G)，F)，則該樹的深度為 14 ， 度為0的結點數為 23 ，度為1的結點數為 3 2 ，度為2的結點數為 42 ；C結點是A 結點的 5 右 孩子，E結點是C結點的 6 左 孩子。 19.在一棵二叉排序樹中，按 中序 遍歷得到的結點序列是一個有序序列。 20.由分別帶權為3,9,6,2,5的共五個葉子結點構成一棵哈夫曼樹，則帶權路徑長度為 55 。 21.假定在二叉樹的鏈接存儲中，每個結點的結構為leftdataright ，其中 data為值域，left和right分別為鏈接左、右孩子結點的指針域，請在下面中序遍歷算法 中畫有橫線的地方填寫合適的語句。 void

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

26、列為 1 ABCDFE ，按廣度優先搜索遍歷得到的頂點序列為 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.已知一個圖如下所示，在該圖的最小生成樹中，各邊的權值之和為 20 。 10 15 5 2 8 12 3 26.假定在有序表A1.20上進行二分查找，則比較一次查找成功的結點數為 11 ， 比較兩次查找成功的結點數為 22 ，比較三次查找成功的結點數為 34 ，比較四次查找成功結點數為 48 ，比較五次查找成功的結點數為 55 ，

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

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

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

30、數據對象（ ）。 5在單鏈表中，任何兩個元素的存儲位置之間都有固定的聯系，因為可以從頭結點查找任何一個元素（× ）。 6在單鏈表中，要取得某個元素，只要知道該元素的指針即可，因此，單鏈表是隨機存取的存儲結構（ × ）。 7鏈表的每個結點中，都恰好包含一個指針（× ）。 *8數組是同類型值的集合（× ）。 /不是集合/ *9使用三元組表示稀疏矩陣的元素，有時并不能節省存儲時間（ ）。 *10.線性表可以看成是廣義表的特例，如果廣義表中的每個元素都是原子，則廣義表便成為線性表（ ）。 11.由樹轉換成二叉樹，其根結點的右子樹總是空的（ ）。 12.后序遍歷樹

31、和中序遍歷與該樹對應的二叉樹，其結果不同（ × ）。 13.若有一個結點是某二叉樹子樹的中序遍歷序列中的最后一個結點，則它必是該子 樹的前序遍歷序列中的最后一個結點（× ）。 14.若一個樹葉是某子樹的中序遍歷序列中的最后一個結點，則它必是該子樹的前序 遍歷序列中的最后一個結點（ ）。 15.已知二叉樹的前序遍歷和后序遍歷序列并不能唯一地確定這棵樹，因為不知道樹 的根結點是哪一個（× ）。 16.在哈夫曼編碼中，當兩個字符出現的頻率相同時，其編碼也相同，對于這種情況應作特殊處理（× ）。 17.有回路的圖不能進行拓撲排序（ ）。 18.連通分量是無向圖中

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

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

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

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

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

37、指針所指示；(4)數學性質。當多個編號元素依某種順序壓入，且可任意時刻彈出時，所獲得的編號元素排列的數目，恰好滿足卡塔南數列的計算，即： n n 2n /(n1) 其中，n為編號元素的個數，Cn 是可能的排列數目。 5. 何謂隊列的上溢現象?解決它有哪些方法，且分別簡述其工作原理。 5. 解答: 在隊列的順序存儲結構中，設隊頭指針為front,隊尾指針為rear,隊的容量（存儲空間的大小）為m。當有元素要加入隊列時，若rearm（初始時reat0），則發生隊列的上溢現象，該元素不能加入隊列。 這里要特別注意的是：隊列的假溢出現象，隊列中還有空余的空間，但元素不能進隊 列。造成這種現象的原因是由

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

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

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

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

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

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

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

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