2007年武汉理工大学数据结构考研真题.pdfVIP

2007年武汉理工大学数据结构考研真题.pdf 第1页 共3页 武汉理工大学 考研真题 2007年武汉理工大学数据结构考研真题.pdf 第1页 共3页 2007年武汉理工大学数据结构考研真题.pdf 第2页 共3页 一、判断题（20 分，每小题 2 分。1:正确，0:错误） 1.判断某个算法是否容易阅读是算法分析的任务之一。 2.对顺序栈进行插入、删除操作，不涉及元素的前、后移动问题。 3.循环队列中每个元素都有后继。 4.前缀编码指的是任意字符的编码都是另一个编码的前缀。 5.往链表中插入一个元素，平均要移动大约一半的元素。 6.将一个树转换为二叉树后，根结点没有右孩子。 7. 由二叉树的中序遍历序列和后序遍历序列可以得到该树的前序遍历序列。 8.堆的存储即可以是顺序的，也可以是链接的。 9.稀疏炬阵压缩存储后，必会失去随机存取功能。 10.若散列表的装载因子小于 1，则可以避免冲突的产生。 二、选择题（20 分，每题 2 分） 11.计算机所处理的数据一般具备某种内在联系性，这是指_____ 。 A.数据和数据之间存在某种关系 B.元素和元素之间存在某种关系 C.元素内部具有某种结构 D.数据项和数据项之间存在某种关系 12.算法的时间复杂度与_____有关。 A. 问题规模 B.计算机硬件性能 C.编译程序质量 D.程序设计语言 13.顺序表的长度与_____有关。 A.线性表中有多少个结点 B.每个结点有多少个字段 C.每个结点中各字段的类型 D.存储线性表的数组类型 14.在解决计算机主机和打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数 据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印。这个缓冲区应该是一个_____结构。 A.栈 B. 队列 C.数组 D.线性表 15.设 n 个元素的进栈序列是 P1,P2,P3, …，Pn, 出栈序列是 1，2 ，3，…n 。若Pn=1,则 pi （1≤in ）的值 _____ 。 A.是 i 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.在平衡二叉排序树中，每个结点_____ 。 A.左子树结点个数和右子树结点个数相差不超过 1 B.平衡因子为 0 C.左子树度数和右子树度数相差不超过 1 D.左子树深度（高度）和右子树深度（高度）相差不超过 1 19.排序过程中，元素的移动次数与各元素原始的排列顺序无关的排序方法是_____排序。 A.简单选择 B.快速 C.堆 D.归并 20.如果_____ ，则称这种排序方法是不稳定的。 A.排序前后，排序码相同的元素在线性表中的相对位置可能会被颠倒 B.排序前后，排序码相同的元素在线性表中的相对位置一定会被颠倒 C.对同一个线性表，每次排序的结果可能不相同 D.排序结果不可预测 三、算法分析题（20 分，每小题 4 分） void what （int n, int a[ ][ ],int s ）{//算法 1 int i,j,s=0; 2007年武汉理工大学数据结构考研真题.pdf 第2页 共3页 2007年武汉理工大学数据结构考研真题.pdf 第3页 共3页 for （i=l;i=n;i++ ） for （j=l;j=i;j++ ） s=s+a[i][j]; } 21.在算法 1 中，对变量s 的赋值操作总共执行了_____次。 22.算法 1 的时间复杂度是_ 。 int what （int x, int n ）{//算法 2 if （n==0 ） y=1; else{y=what （x, n/2 ）； y=y*y; if （n%2==1 ） y=y*x; } return y; } 23.算法 2 的功能是_____ 。 24.算法