1990年程序员上午试卷及答案

试题1

从供选择的答案中选出应填入下列叙述中的 __?__ 内的正确答案，把编号写在答卷的对应栏内。

在排序算法中每一项都与其他诸项进行比较，计算出小于该项的项的个数，以确定该项的位置叫 __A__ 。

散列函数有一个共同性质，即函数值应当以 __B__ 取其值域的每个值。

设有两个串 p 和 q，其中 q 是 p 的子串。把 q 在 p 中首次出现的位置作为子串 q 在 p 中的位置的算法称为 __C__ 。

如果要求一个线性表既能较快地查找，又能适应动态变化的要求，则可采用 __D__ 的方法。

供选择的答案

试题2

从下列有关树的叙述中，选出五条正确叙述，并按编号从小到大的次序写在答卷的 A～E 栏内。

① 二叉树中每个结点有两个子结点，而对一般的树则无此限制，因此二叉树是树的特殊情形。

② 当 k≥ 1时，高度为 k 的二叉树至多有 2^k-1 个结点。

③ 用树的前序遍历和中序遍历可以导出树的后序遍历。

④ 线索二叉树的优点是便于在中序下查找前趋结点和后继结点。

⑤ 将一棵树转换成二叉树后，根结点没有左子树。

⑥ 一棵含有 n 个结点的完全二叉树，它的高度是 |log₂n」+l。

⑦ 在二叉树中插入结点，该二叉树便不再是二叉树。

⑧ 采用二叉链表作树的存贮结构，树的前序遍历和其相应的二叉树的前序遍历的结果是一样的。

⑨ 哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。

⑩ 用一维数组存贮二叉树时，总是以前序遍历顺序存贮结点。

试题3

从下列叙述中选出五条关于好的编程风格的正确叙述，把编号依次写在答卷的A～E栏内。

① 使用括号以改善表达式的清晰性。

② 对递归定义的数据结构不要使用递归过程。

⑧ 尽可能对程序代码进行优化。

④ 不要修补不好的程序，要重新写。

⑤ 不要进行浮点数的相等比较。

⑥ 应尽可能多输出中间结果。

⑦ 利用数据类型对数据值进行防范。

⑧ 用计数方法而不是用文件结束符来判别输入的结束。

⑨ 程序中的注释是可有可无的。

    ⑩ 使用有意义的标识符。