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

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

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

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

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

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

6、活動(dòng)；[3]表示活動(dòng)間的時(shí)間順序關(guān)系；[4]該活動(dòng)為關(guān)鍵活動(dòng)。6、假定有K個(gè)關(guān)鍵字互為同義詞，若用線性探測(cè)法把這K個(gè)關(guān)鍵字插入表中，至少需要____次探測(cè)。beginif(b[i]=b[il])thenl:=l1i:=i1endwrite(l)end六、閱讀如下程序，并填充[A]~[E]，使之成為一個(gè)完整的程序。（10分）本程序輸入一個(gè)給定的正整數(shù)N，打印出所有不超過N的，其平方為回文的數(shù)?；匚氖侵缸址畠砂氲淖址笥覍?duì)稱，例如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]________________七、編寫一個(gè)子程序，對(duì)于給定的正整數(shù)N和M（N〈M〉，打印出所有滿足條件I1I2…IN=M的正整數(shù)序