1、一、填空 1. 線性表是具有n個 的有限序列。 A. 表元素 B. 字符C. 數(shù)據(jù)元素 D. 數(shù)據(jù)項 E. 信息項 2. 若長度為n的線性表采用順序存儲結(jié)構(gòu)，在其第I個位置插入一個新元素的算法的時間復(fù)雜度為 。（1In+1） A. O(0)B. O(1) C. O(n)D. O(n2) 3 .一棵有124個葉結(jié)點的完全二叉樹，最多有 個結(jié)點。 A. 247 B. 248 C. 249 D. 251,期中考試題,4.設(shè)高為h的二叉樹只有度為0和2的結(jié)點，則此類二叉樹的結(jié)點數(shù)至少為 ，至多為 。高為h的完全二叉樹的結(jié)點數(shù)至少為 ，至多為 。 A 2h B. 2h-1 C. 2h+1 D.h+1 E

2、. 2h-1 F. 2h-1 G. 2h+1-1 H. 2h+1 5. Hash技術(shù)廣泛應(yīng)用于查找過程，選擇Hash函數(shù)的標(biāo)準(zhǔn)是 和 。處理沖突的技術(shù)有優(yōu)有劣，其共同標(biāo)準(zhǔn)是 。 6. 在下述排序算法中，所需輔助存儲空間最多的是 ，所需輔助存儲空間最小是 ，平均速度最快的是 。 A.快速排序 B. 歸并排序C. 堆排序,7. 閱讀以下算法，填充空格，使其成為完整的算法。其功能是在一個非遞減的順序存儲線性表中(從下標(biāo)1處開始存儲)，刪除所有值相等的多余元素。 #define MAXSIZE 30 typedef struct int elemMAXSIZE; int length;/*表長*/ s

3、qlisttype; void exam21(sqlisttype *L) int I,j; I=2,j=1; while( (1) ) if(L-elemIL-elemj) (2) ; (3) ; I+; (4) ;,二、舉例說明數(shù)據(jù)結(jié)構(gòu)與算法的關(guān)系。 三、試寫一算法，自大到小依次輸出順序讀入 的三個數(shù)X、Y和Z的值。你的算法的執(zhí)行 時間是多少？ 四、描述以下三個概念的區(qū)別：頭指針、頭結(jié) 點、首元結(jié)點。并說明頭指針和頭結(jié)點的 作用。 五、已知線性表中的元素以值遞增有序排列，并 以單鏈表作存儲結(jié)構(gòu)。試寫一高效的算法， 刪除表中所有值大于Kmin且小于Kmax的 元素（若表中存在這樣的元素），同

4、時釋 放被刪除結(jié)點空間，并分析你的算法的時 間復(fù)雜度。,六、設(shè)有編號為1、2、3、4的四輛列車，順序進(jìn) 入一個棧式結(jié)構(gòu)的站臺，具體寫出這四輛列 車開出站的所有可能的順序。 七、二維數(shù)組A的元素是6個字符組成的串，行 下標(biāo)i的范圍從0到8，列下標(biāo)j的范圍從1到 10 。試問： 存放A至少需要多少字節(jié)？ A的第8列和第5行共占多少字節(jié)？ 若A按行存放，元素A8，5的起始地址與當(dāng)A按列存放時的哪個元素的起始地址一致？（必須有計算分析過程）,八、試找出分別滿足下面條件的所有二叉樹： 先序遍歷序列與中序遍歷序列相同； 中序遍歷序列與后序遍歷序列相同； 先序遍歷序列與后序遍歷序列相同。 九、設(shè)有序序列中數(shù)據(jù)元素的關(guān)鍵字分別為 3,10,13,17,4