一
在每小題列出的四個備選項中只有一個是符合題目要求的
A
C
A
C
s
t = p
A
B
C
D
A
C
A
C
S= 〞 abcdefgh 〞 ; T= 〞 xyzw 〞 ;
substr (X
substr (Y
strcat (X
A
C
A
C
A
C
A
C
A
C
A
C
A
C
A
C
A
C
A
C
二
請在每小題的空格中填上正確答案
product =
for (i = n;i>
for (j = i+ product *=j; 17 .已知指針 p 指向單鏈表中某個結點，則語句 p -> next =p -> next -> next 的作用是 ________________ 。tw.wINgWIt.cOM 18 .假設元素只能按 a,b,c,d 的順序依次進棧，且得到的出棧序列中的第一個元素為 c ，則可能得到的出棧序列為 ________________ ，不可能得到的出棧序列為 ________________ 。 19 .若鏈串結點中的指針占 4 個字節，每個字符占 1 個字節，則結點大小為 2 的鏈串的存儲密度為 ________________ 。
20 .右圖表示的廣義表為 ________________ 。 21 .若一棵滿三叉樹中含有 121 個結點，則該 樹的深度為 ________________ 。 22 .若以鄰接矩陣表示有向圖，則鄰接矩陣上 第 i 行中非零元素的個數即為頂點 v i 的 ________________ 。 23 .若希望只進行 8 趟排序便能在 4800 個元素中找出其中值最小的 8 個元素，並且要求排序過程中所進行的關鍵字比較次數盡可能少，則應該選用 ________________ 排序方法。 24 .在含 20 個關鍵字的 3 階 B 樹( 2 - 3 樹)上查找一個關鍵字，至多需要訪問 ___________ 次外存。 25 .文件上的兩類主要操作為 ________________ 和 ________________ 。 三、解答題(本大題共 4 小題，每小題 5 分，共 20 分) 26 .設棧 S1 的入棧序列為 1 2 3 4 (每個數字為 13 個元素)，則不可能得到出棧序列 3142 。但可通過增設棧 S2 來實現。例如，按下圖中的箭頭指示，依次經過棧 S1 和 S2 ，便可得到序列 3 1 4 2 。
如果用 H1 和 H2 分別表示棧 S1 和 S2 的進棧操作，用 P1 和 P2 分別表示兩個棧的出棧操作，則得到 3 1 4 2 的一個操作步驟為 H1 ， H1 ， H1 ， P1 ， H2 ， P2 ， P1 ， H2 ， P1 ， H2 ， P2 ， H1 ， P1 ， H2 ， P2 ， P2 請仿照上例寫出利用兩個棧從 1 2 3 4 得到 4 1 3 2 的操作步驟。 27 .已知樹如右圖所示，
( 1 )寫出該樹的後序序列; ( 2 )畫出由該樹轉換得到的二叉樹。 28 .為關鍵字( 17 ， 33 ， 31 ， 40 ， 48 )構造一個長度為 7 的散列表，設散列函數為 h(key)=key%7, 用開放定址法解決沖突的探查序列是 hi = (h(key) + i(key%5+1))%7 0 ≤ i ≤ 6 ( 1 )畫出構造所得的散列表; ( 2 )求出在等概率情況下查找成功時的平均查找長度。 29 .已知 R [ 1..8 ]中的元素依次為( 12 ， 5 ， 9 ， 20 ， 6 ， 31 ， 24 ， 27 )，寫出按算法 MergeSortDC 對 R 進行自頂向下的二路歸並排序過程中，前 5 次調用函數 Merge(R, low, mid, high) 時參數 low, mid 和 high 的值。 void MergeSortDC (int R[], int low, int mid, int high ) { int mid; if (low { mid = (low +high)/2; MergeSortDC (R, low, mid); MergeSortDC (R, mid+1, high); Merge (R, low, mid, high); } } // MergeSortDC ( 1 )第一次調用時的參數值; ( 2 )第二次調用時的參數值; ( 3 )第三次調用時的參數值; ( 4 )第四次調用時的參數值; ( 5 )第五次調用時的參數值; 四、算法閱讀題(本大題共 4 小題，每小題 5 分，共 20 分) 30 .下列函數的功能是，對以帶頭結點的單鏈表作為存儲結構的兩個遞增有序表(表中不存在值相同的數據元素)進行如下操作：將所有在 Lb 表中存在而 La 表中不存在的結點插入到 La 中，其中 La 和 Lb 分別為兩個鏈表的頭指針。請在空缺處填入合適內容，使其成為一個完整的算法。 void union (LinkList La, LinkList Lb) { // 本算法的功能是將所有 Lb 表中存在而 La 表中不存在的結點插入到 La 表中 LinkList pre = La, q; LinkList pa = La -> next; LinkList pb = Lb -> next; free (Lb); while (pa && pd) { if (pa -> data { pre = pa; pa = pa -> next;} else if (pa -> data > pb ->data) { (1) ; pre = pb; pb = pb -> next; (2) ; } else { q = pb; pb = pb -> next; free (q); } } if (pb) (3) ; } (1) (2) (3) 31 .已知串的存儲結構為動態存儲分配的順序串。閱讀下列算法，並<
From:http://tw.wingwit.com/Article/program/sjjg/201311/23383.html