1990年計算機軟考程序員水平考試試題(上午)

　　試題 1

　　在排序算法中每一項都與其他諸項進行比較，計算出小于該項的項的個數(shù)，以確定該項的位置叫 __A__ 。

　　散列函數(shù)有一個共同性質(zhì)，即函數(shù)值應(yīng)當(dāng)以 __B__ 取其值域的每個值。

　　設(shè)有兩個串 p 和 q，其中 q 是 p 的子串。把 q 在 p 中首次出現(xiàn)的位置作為子串 q 在 p 中的位置的算法稱為 __C__ 。

　　如果要求一個線性表既能較快地查找，又能適應(yīng)動態(tài)變化的要求，則可采用 __D__ 的方法。

　　算法的計算量的大小稱為計算的 __E__ 。

　　供選擇的答案：

　　A: ① 插入排序 ② 交換排序 ③ 選擇排序 ④ 枚舉排序

　　B： ① 最大概率 ② 最小概率 ③ 平均概率 ④ 同等概率

　　C： ① 聯(lián)接 ② 匹配 ③ 求子串 ④ 求串長

　　D： ① 分塊 ② 順序 ③ 二分法 ④ 基于屬性

　　E： ① 現(xiàn)實性 ② 難度 ③ 復(fù)雜性 ④ 效率

　　試題 2

　　從下列有關(guān)樹的敘述中，選出五條正確敘述，并按編號從小到大的次序?qū)懺诖鹁淼?A～E 欄內(nèi)。

　　① 二叉樹中每個結(jié)點有兩個子結(jié)點，而對一般的樹則無此限制，因此二叉樹是樹的特殊情形。

　�、� 當(dāng) k≥ 1時，高度為 k 的二叉樹至多有 2k-1 個結(jié)點。

　�、� 用樹的前序遍歷和中序遍歷可以導(dǎo)出樹的后序遍歷。

　　④ 線索二叉樹的優(yōu)點是便于在中序下查找前趨結(jié)點和后繼結(jié)點。

　�、� 將一棵樹轉(zhuǎn)換成二叉樹后，根結(jié)點沒有左子樹。

　　⑥ 一棵含有 n 個結(jié)點的完全二叉樹，它的高度是 |log2n」+l。

　�、� 在二叉樹中插入結(jié)點，該二叉樹便不再是二叉樹。

　�、� 采用二叉鏈表作樹的存貯結(jié)構(gòu)，樹的前序遍歷和其相應(yīng)的二叉樹的前序遍歷的結(jié)果是一樣的。

　�、� 哈夫曼樹是帶權(quán)路徑長度最短的樹，路徑上權(quán)值較大的結(jié)點離根較近。

　　⑩ 用一維數(shù)組存貯二叉樹時，總是以前序遍歷順序存貯結(jié)點。

　　試題 3

　　從下列敘述中選出五條關(guān)于好的編程風(fēng)格的正確敘述，把編號依次寫在答卷的 A～E欄內(nèi)。

　　① 使用括號以改善表達式的清晰性。

　�、� 對遞歸定義的數(shù)據(jù)結(jié)構(gòu)不要使用遞歸過程。

　�、� 盡可能對程序代碼進行優(yōu)化。

　　④ 不要修補不好的程序，要重新寫。

　�、� 不要進行浮點數(shù)的相等比較。

　�、� 應(yīng)盡可能多輸出中間結(jié)果。

　�、� 利用數(shù)據(jù)類型對數(shù)據(jù)值進行防范。

　�、� 用計數(shù)方法而不是用文件結(jié)束符來判別輸入的結(jié)束。

　�、� 程序中的注釋是可有可無的。

　�、� 使用有意義的標(biāo)識符。