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