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

　　試題 1

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

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

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

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

　　算法的計(jì)算量的大小稱為計(jì)算的 __E__ 。

　　供選擇的答案：

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

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

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

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

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

　　試題 2

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

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

　　② 當(dāng) k≥ 1時(shí)，高度為 k 的二叉樹至多有 2k-1 個(gè)結(jié)點(diǎn)。

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

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

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

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

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

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

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

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

　　試題 3

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

　　① 使用括號(hào)以改善表達(dá)式的清晰性。

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

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

　　④ 不要修補(bǔ)不好的程序，要重新寫。

　�、� 不要進(jìn)行浮點(diǎn)數(shù)的相等比較。

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

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

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

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

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