1、數據結構復習及答案一是非題（正確的打“” ，錯誤的打“” 。）數據結構可用三元式表示（ D， S， P）。其中： D是數據對象， S 是 D上的關系，P 是對 D 的基本操作集。2.線性表的鏈式存儲結構具有可直接存取表中任一元素的優點。字符串是數據對象特定的線性表。二叉樹是一棵結點的度最大為二的樹。5 鄰接多重表可以用以表示無向圖，也可用以表示有向圖。6 可從任意有向圖中得到關于所有頂點的拓撲次序。7 一棵無向連通圖的生成樹是其極大的連通子圖。8 二叉排序樹的查找長度至多為log 2。 9 對于一棵m階的 B- 樹. 樹中每個結點至多有m 個關鍵字。除根之外的所有非終端結點至少有 m/2個關鍵

2、字。 10對于目前所知的排序方法，快速排序具有最好的平均性能。11. 順序存儲方式的優點是存儲密度大，且插入、刪除運算效率高。二維數組是其數據元素為線性表的線性表。連通圖 G 的生成樹是一個包含 G 的所有 n 個頂點和 n-1 條邊的子圖。 折半查找不適用于有序鏈表的查找。完全二叉樹必定是平衡二叉樹。中序線索二叉樹的優點是便于在中序下查找直接前驅結點和直接后繼結點。隊列是與線性表完全不同的一種數據結構。平均查找長度與記錄的查找概率有關。19. 二叉樹中每個結點有兩個子結點，而對一般的樹，則無此限制，所以，二叉樹是樹的特殊情形。 算法的時間復雜性越好，可讀性就越差；反之，算法的可讀性越好，則時

3、間復雜性就越差。 二選擇題1.若廣義表 LS 滿足 GetHead(LS)=GetTail(LS)，則 LS為(b ) 。A.()B.()C. ( ),( )D. ( ),( ),( )3.在下列數據結構中 (c )具有先進先出（ FIFO）特性， (b ) 具有先進后出 (FILO ）特性。a: 線性表b:棧c:隊列d:廣義表4.假設用于通訊的電文僅由6 個字符組成， 字母在電文中出現的頻率分別為7, 19, 22, 6,32, 14 。 若為這 6 個字母設計哈夫曼編碼（設生成新的二叉樹的規則是按給出的次序從左至右的結合，新生成的二叉樹總是插入在最右），則頻率為7 的字符編碼是（g），頻率

4、為32 的字符編碼是（c ）。a: 00b: 01c: 10d: 11e: 011f: 110g: 1110h:1111對二叉排序樹按（ c ）可得到有序序列。? ? a:層次遍歷b:前序遍歷c:中序遍歷d:后序遍歷6已知某樹的先根遍歷次序為abcdefg ，后根遍歷次序為cdebgfa 。若將該樹轉換為二叉樹，其后序遍歷次序為（d ）。a: abcdefgb: cdebgfac: cdegbfad: edcgfba7對一棵完全二叉樹進行層序編號。則編號為n 的結點若存在右孩子，其編號是(d ) 。編號為 n 的結點若存在雙親，其編號是(a ) 。a:n/2b:2nc:2n-1d:2n+1e:

5、nf:2(n+1)8關鍵路徑是指在只有一個源點和一個匯點的有向無環網中源點至匯點（c ）的路徑。a: 弧的數目最多b:弧的數目最少c:權值之和最大d:權值之和最小哈希表的查找效率取決于（d ）。哈希函數 b: 處理沖突的方法。 c: 哈希表的裝填因子。 d: 以上都是10從邏輯上可以把數據結構分成(c ) 。a:動態結構和靜態結構b:順序組織和鏈接組織c:線性結構和非線性結構d:基本類型和組合類型11在計算遞歸函數時，如不用遞歸過程，應借助于(b ) 這種數據結構。a:線性表b:棧c:隊列d:雙向隊列12若已知某二叉樹的中序和后序遍歷序列分別BCAEFD 和 CBFEDA ，則該二叉樹的先序序

6、列為 (a ) 。a: ABCDEFb: ABDCEFc: ABDCFEd: ACBDFE13當待排序序列的關鍵字次序為倒序時，若需為之進行正序排序，下列方案中( d ) 為佳。a:起泡排序b:快速排序c:直接插入排序d:簡單選擇排序14若從二叉樹的根結點到其它任一結點的路徑上所經過的結點序列按其關鍵字遞增有序，則該二叉樹是 ( c ) 。a:二叉排序樹b:赫夫曼樹c:堆d:平衡二叉樹15下圖所有可能的拓撲序列有(b ) 種。a: 2b: 3c: 4d: 516下列排序算法中，(d ) 算法可能會出現：初始數據為正序時，花費的時間反而最多。a: 堆排序b:起泡排序c:歸并排序d:快速排序17右

7、圖為一棵3 階 B-樹。20，25在該樹上插入元素15后的 B- 樹是 ( c ) 。10,142135a:15,25b:20,2510,1420,213510,1415,2135c:20d:14,25142510,1520,21351015213518設森林 F 中有三棵樹，第一、第二和第三棵樹的結點個數分別為m1、 m2 和 m3，則與森林 F 對應的二叉樹根結點的右子樹上的結點個數是( d ) 。a: m1b: m1+m2c: m3d: m2+m3根據插入次序（ 80，90， 100，110，85，70，75，60，72）建立二叉排序樹。圖（a ）是最終變化的結果。若仍以該插入次序建立平

8、衡二叉樹。圖（c ）是最終變化的結果。a:b:8080709075906075851006070851007211072110c:d:909075100801007080110757085110607285607220. 設輸入序列為 20,45,30,89,70,38,62， 19，依次插入到一棵2-3 樹中 ( 初始狀態為空 ) ，該 B- 樹為（ b ）。再刪除 38，該 B- 樹為（ f）。a:b:（3062）（ 45）（ 19， 20）（ 38 45）（70，89）（ 30）（70 ）（1920 ）（ 38）（62 ）（89）c:d:（4570）（ 45）（ 20）（ 62）（89

9、）（ 20）（70 ）（19）（ 30）（ 19） ( 30,38）（62 ）（89）e:f:（30 70）（ 45）（ 19，20） （ 45 62 ）（ 89）（ 20）（ 70）（ 19）（ 30）（ 62）（ 89）21已知一組待排序的記錄關鍵字初始排列如下：45,34,87,25,67,43,11,66,27,78 。(g ) 是快速排序法一趟排序的結果；(a ) 是希爾排序法（初始步長為4）一趟排序的結果；( b ) 是初始堆（大堆頂） ；(d ) 是基數排序法一趟排序的結果。a： 27,34,11,25,45,43,87,66,67,78b: 87,78,45,66,67,43,

10、11,25,27,34c: 11,43,34,25,45,66,27,67,87,78d:11,43,34,45,25,66,87,67,27,78e: 34,45,25,67,43,11,66,27,78,87f: 87,45,11,25,34,78,27,66,67,43g: 27,34,11,25,43,45,67,66,87,78h: 34,11,27,25,43,78,45,67,66,8722若有序表中關鍵字序列為：14， 20，25，32，34， 45，57，69，77， 83，92。對其進行折半查找，則在等概率情況下，查找成功時的平均查找長度是( c ) 。查找 32 時需進行

11、( c ) 次比較。a: 1b: 2c: 3d: 4設一棵二叉樹 BT的存儲結構如下 : 12345678lchild23006000data A B C DEFG Hrchild05408700其中 lchild， rchild分別為結點的左、右孩子指針域，data 為結點的數據域。則該二叉樹的高度為(d ) ；第 3 層有 (a ) 個結點（根結點為第1 層）。a: 2b: 3c: 4d: 5一個連通圖的最小生成樹 ( b ) 。只有一棵b:有一棵或多棵c:一定有多棵d:可能不存在25若某二叉樹有20 個葉子結點， 有 20個結點僅有一個孩子， 則該二叉樹的總結點數是( c ) 。a: 4

12、0b: 55c: 59d: 6126已知哈希表地址空間為A0.8，哈希函數為H(k)=k mod 7，采用線性探測再散列處理沖突。若依次將數據序列：76,45,88,21,94,77,17存入該散列表中，則元素17 存儲的下標為 (f ) ；在等概率情況下查找成功的平均查找長度為(c ) 。a: 0b: 1c: 2d: 3e: 4f: 5g: 6h: 727已知某有向圖的鄰接表存儲結構如圖所示。?0E211D0342C43B1204A2根據存儲結構，依教材中的算法其深度優先遍歷次序為（廣度優先遍歷次序為（ c ）。各強連通分量的頂點集為（fd ）。）。a: abcde.b: edcba.c:

13、ecdab.d: ecadb.e: abc及 edf: ac及 bedg: ab及cedh: bc及aed已知某無向圖的鄰接表如下所示； ( e ) 是其原圖。( c ) 是按該鄰接表遍歷所得深度優先生成樹。 ( d ) 是按該鄰接表遍歷所得廣度優先生成樹。0 a3211b302c4303d52104e525f43a: abb: abc: abcdcdcdefefefd: abe: abf: abdccdcdfeefef29設有二維數組 A 5 x 7 , 每一元素用相鄰的 4 個字節存儲，存儲器按字節編址。已知 A的起始地址為 100。則按行存儲時，元素 A06 的存儲地址是（ d ）；按列

14、存儲時，元素 A06 的存儲地址是（ a ）。a. 220b. 200c. 140d. 124若順序表中各結點的查找概率不等，則可用如下策略提高順序查找的效率：若找到指定的結點，將該結點與其后繼（若存在） 結點交換位置，使得經常被查找的結點逐漸移至表尾。以下為據此策略編寫的算法，請選擇適當的內容，完成此功能。順序表的存儲結構為： typedef structElemType *elem; /數據元素存儲空間，0 號單元作監視哨intlength; /表長度SSTable;int search_seq(SSTable ST, KeyType key) /在順序表 ST 中順序查找關鍵字等于 ke

15、y 的數據元素。/若找到，則將該元素與其后繼交換位置，并返回其在表中的位置，否則為0。ST.elem0.key=key;i=ST.length;while(ST.elemi.key!=key)f;if(g) ST.elemi ST.elemi+1；e；return i;a: i0b: i=0c: iST.lengthd: i=ST.lengthe: i+f: i-g: A和 C同時滿足h: B和 D 同時滿足31.若對編號為1， 2， 3 的列車車廂依次通過扳道棧進行調度，不能得到(e )的序列。a:1,2,3b:1,3,2c:2,1,3d:2,3,1e:3,1,2f:3,2,132.遞歸程序

16、可借助于(b )轉化為非遞歸程序。a:線性表b:棧c:隊列d:數組33.對字符串s=data - structure 執行操作的結果是 (d )。a:database b: data-base c:replace(s,substring(s,6,8),bas) basd: data-basucture設有二維數組 A 5 x 7 , 每一元素用相鄰的 4 個字節存儲，存儲器按字節編址。已知 A的起始地址為100。則按行存儲時，元素A06 的第一個字節的地址是（按列存儲時，元素A06 的第一個字節的地址是（a ）a: 220b:200c: 140d:124d ）35.對廣義表 A= （a,(b)

17、的結果是：（ b ） 。a: （）b:）,(c,(),d（）執行操作c: dd: (d)gettail(gethead(gettail(A)36下列函數為堆排序中的堆調整過程（調整 H.rs的關鍵字，使請在“”處填上合適的內容, 完成該算法。Void heapadjust( heaptype & H , int s , int m ) rc=H.rs;for (j=2*s;j=m;j*=2) if (jH.rj+1.key);b: !(rc.key H.rj.key);c: (H.rj.keyH.rj.key);H.rs=rc;rc=H.rs;h.rj=rc;rc=H.rj;三算法設計題單鏈表

18、結點的類型定義如下：typedef struct LNode int data;struct LNode *next; LNode, *Linklist;寫一算法， Contrary(linklist &L) ,對一帶頭結點且僅設尾指針L 的循環單鏈表就地逆置。（即表頭變表尾，表尾變表頭。）void Contrary(linklist &L) p=L-next; q=L; while(p!=L) r=p-next; p-next=q; q=p; p=r; p-next=q;2二叉樹用二叉鏈表存儲表示。typedef struct BiTNode TelemTypedata;Struct BiTNode *lchild, *rchild