1、2007年武汉理工大学计算机专业基础综合（数据结构）真题试卷及答案与解析 一、判断题 1 判断某个算法是否容易阅读是算法分析的任务之一。 （ A）正确 （ B）错误 2 对顺序栈进行插入、删除操作，不涉及元素的前、后移动问题。 （ A）正确 （ B）错误 3 循环队列中每个元素都有后继。 （ A）正确 （ B）错误 4 前缀编码指的是任意字符的编码都是另一个编码的前缀。 （ A）正确 （ B）错误 5 往链表中插入一个元素，平均要移动大约一半的元素。 （ A）正确 （ B）错误 6 将一个树转换为二叉树后，根结点没有右孩子。 （ A）正确 （ B）错误 7 由二叉树的中序遍历序列和后序遍历序列
2、可以得到该树的前序遍历序列。 （ A）正确 （ B）错误 8 堆的存储即可以是顺序的，也可以是链接的。 （ A）正确 （ B）错误 9 稀疏炬阵压缩存储后，必会失去随机存取功能。 （ A）正确 （ B）错误 10 若散列表的装载因子小于 1，则可以避免冲突的产生。 （ A）正确 （ B）错误 二、单项选择题 11 计算机所处理的数据一般具备某种内在联系性，这是指 ( )。 （ A）数据和数据之间存在某种关系 （ B）元素和元素之间存在某种关系 （ C）元素内部具有某种结构 （ D）数据项和数据项之间存在某种关系 12 算法的时间复杂度与 ( )有关。 （ A）问题规模 （ B）计算机硬件性能
3、（ C）编译程序质量 （ D）程序设计语言 13 顺序表的长度与 ( )有关。 （ A）线性表中有多少个结点 （ B）每个结点有多少个字段 （ C）每个结点中各字段的类型 （ D）存储线性表的数组类型 14 在解决计算机主机和打印机之间速度不匹配问题时通常设置一个打印数 据缓冲区，主机将要输出的数据依次写人该缓冲区，而打印机则从该缓冲区中取出数据打印。这个缓冲区应该是一个 ( )结构。 （ A）栈 （ B）队列 （ C）数组 （ D）线性表 15 设 n个元素的进栈序列是 P1， P2， ， Pn，出栈序列是 l， 2， 3， n 。若Pn=1，则 Pi(1in)的值 ( )。 （ A）是 i
4、 （ B）是 n i （ C）是 n i+1 （ D）有多种可能 16 如果在表示树的孩子一兄弟链表中有 6个空的左指针域， 7个空的右指针域， 5个结点左、右指针域都为空，则该树中叶子的 个数 ( )。 （ A）有 7个 （ B）有 6个 （ C）有 5个 （ D）不能确定 17 若图的邻接矩阵中主对角线上的元素全是 0，其余元素全是 1，则可以断定该图一定 ( )。 （ A）是无向图 （ B）不是带权图 （ C）是有向图 （ D）是完全图 18 在平衡二叉： H序树中，每个结点 ( )。 （ A）左子树结点个数和右子树结点个数相差不超过 1 （ B）平衡因子为 O （ C）左子树度数和右子
5、树度数相差不超过 1 （ D）左子树深度 (高度 )和右子树深度 (高度 )相差不超过 1 19 排序过程中，元素的移动次数与各元素原始的排列顺序无关的排序方法是 ( )排序。 （ A）简单选择 （ B）快速 （ C）堆 （ D）归并 20 如果 ( )，则称这种排序方法是不稳定的。 （ A）排序前后，排序码相同的元素在线性表中的相对位置可能会被颠倒 （ B）排序前后，排序码相同的元素在线性表中的相对位置一定会被颠倒 （ C）对同一个线性表，每次排序的结果可能不相同 （ D）排序结果不可预测 三、分析题 21 22 23 四、计算题 24 己知完全二叉树结 点的前序序列是 abcdefghi，
6、请画出这棵完全二叉树的逻辑结构图。 25 对 27， 188， 9， 570， 333， 480， 659， 103进行二路归并排序。请写出每一趟的排序结果。 五、设计题 26 线性表以顺序结构存储且递增有序，写一个算法实现二分查找。 要求： 用类 C语言编写算法； 在算法中给出必要的类型描述和注释。 2007年武汉理工大学计算机专业基础综合（数据结构）真题试卷答案与解析 一、判断题 1 【正确答案】 B 2 【正确答案】 A 3 【正确答案】 A 4 【正确答案】 B 5 【正确答案】 B 6 【正确答案】 A 7 【正确答案】 A 8 【正确答案】 B 9 【正确答案】 A 10 【正确答案】 B 二、单项选择题 11 【正确答案】 B 12 【正确答案】 A 13 【正确答案】 A 14 【正确答案】 B 15 【正确答案】 C 16 【正确答案】 C 17 【正确答案】 D 18 【正确答案】 D 19 【正确答案】 A 20 【正确答案】 A 三、分析题 21 【正确答案 】 n(n+1)/2 O(n+1)/2 22 【正确答案】 求 xn的值。 23 【正确答案】 节点左右子树相互交换。 四、计算题 24 【正确答案】 25 【正确答案】 五、设计题 26 【正确答案】
