中科院計算機技術(shù)研究所 碩士生入學試題 程序設(shè)計

1、中科院計算機技術(shù)研究所中科院計算機技術(shù)研究所1994年碩士生入學試題年碩士生入學試題程序設(shè)計程序設(shè)計一、下面關(guān)于程序設(shè)計風格的敘述，那些是正確的？那些是錯誤的？（10分）1、編寫程序是，應(yīng)使用括號以改善表達式的清晰度。2、應(yīng)當盡可能對程序代碼進行優(yōu)化。3、在程序設(shè)計中，不要進行浮點數(shù)相等的比較。4、應(yīng)盡可能多的輸出中間結(jié)果。5、不要使用數(shù)據(jù)類型來對數(shù)據(jù)值進行防范。6、要用計數(shù)方法而不是用文件結(jié)束符來控制輸入的結(jié)束。7、使用有意義的標識符

2、。8、結(jié)構(gòu)化程序設(shè)計語言中沒有GOTO語句。9、一般而言，語言的級別越高，用它編出的程序越短。10、PAL是一種自由格式的弱類型語言。二、填空：（10分）1、FTRAN程序中，變量的作用域以______為單位，PAL程序的作用域遵守_____規(guī)則。2、賦值語句A：=A1左邊的A代表_________含義，右邊的A代表_________含義。3、高級程序設(shè)計語言的語句分為_________和____________二種。4、在查找算法中，

3、順序查找的平均查找長度ASL為________；折半查找的ASL為___________；而二叉排存樹查找記錄時，最壞下的情況ASL為__________；在二叉平衡排存樹上插入一個結(jié)點后最壞情況需要_______次旋轉(zhuǎn)才能保持平衡。三、選擇填空：（10分）1、存貯稀疏圖的數(shù)據(jù)結(jié)構(gòu)常有的是。[1]鄰接矩陣[2]三元組[3]鄰接表[4]十字鏈表2、內(nèi)部排序多個關(guān)鍵字的文件，最壞情況下最快的排列方法是_____相應(yīng)的時間復雜度為______

4、該算法是的穩(wěn)定性__________.[1]快速排序[2]插入排序[3]歸并排序[4]簡單選擇排序[5]O(nlog2(n))[6]O(n^2)[7]O(n^2log2(n))[8]O(n)[9]穩(wěn)定[10]不穩(wěn)定3、倒排文件包含若干個倒排表，倒排表的內(nèi)容是_____________.[1]一個關(guān)鍵字值和關(guān)鍵字的記錄地址；[2]一個屬性值和該屬性的一個記錄地址；[3]一個屬性值和該屬性的全部屬性地址；[4]多個關(guān)鍵字值和它們對應(yīng)的某個記

5、錄的地址。4、設(shè)T為哈夫曼最優(yōu)樹，具有5個葉結(jié)點，樹T的高度最高可以是__________.[1]1，[2]2，[3]3，[4]4，[5]5，[6]65、對正確的AOE網(wǎng)絡(luò)圖而言，必須是____AOE中某邊權(quán)值應(yīng)當是_____權(quán)值為0的邊則表示______.[A]，[1]完全圖；[2]哈密頓圖；[3]無環(huán)圖；[4]強連通圖[B]，[1]實數(shù)；[2]正整數(shù)；[3]正數(shù)；[4]非負數(shù)[C]，[1]為決策而增加的活動；[2]為計算方便而增加的

6、活動；[3]表示活動間的時間順序關(guān)系；[4]該活動為關(guān)鍵活動。6、假定有K個關(guān)鍵字互為同義詞，若用線性探測法把這K個關(guān)鍵字插入表中，至少需要____次探測。beginif(b[i]=b[il])thenl:=l1i:=i1endwrite(l)end六、閱讀如下程序，并填充[A]~[E]，使之成為一個完整的程序。（10分）本程序輸入一個給定的正整數(shù)N，打印出所有不超過N的，其平方為回文的數(shù)。回文是指字符串兩半的字符左右對稱，例如1，22

7、，121，4224等均是回文。程序：programpalindrome(inputoutput)constmax=1000varnmijs:integerd:array[1..max]ofintegerbeginread(n)fm:=1tondobegin______A________j:=0while____B______dobeginj:=j1d[j]:=smod10______C_________endi:=1while(d[i]

8、=d[j]______D______dobegini:=i1j:=j1endif____E____thenwrite(m)endend.答案：[A]________________[B]__________________[C]________________[D]__________________[E]________________七、編寫一個子程序，對于給定的正整數(shù)N和M（N〈M〉，打印出所有滿足條件I1I2…IN=M的正整數(shù)序