当前位置：问答库＞考研试题

武汉科技大学

2005年硕士研究生入学考试试题 课程名称：数据结构 总页数：4 说 明：1．适用专业：计算机应用技术

2．答题内容写在答题纸上，写在试卷或草稿纸上一律无效。

3．算法描述可用类PASCAL 、C 语言。

4．本试卷共6大题，分值150分，考试时间为3小时。 一、填空题（1×25＝25分）

，，， 1．算法的5个重要特性是和（ 输出 ）。

2．在树形结构中，树根结点没有（ ）结点，其余每个结点有且只有（ ）个前驱结点，叶子结点没有（ ）结点。

3．在图形结构中，每个结点的前驱节点数和后续结点数可以有（ ），6个顶点的无向图至少要（ ）条边才是连通图。

4．从一个具有n 个结点的单链表中查找其值等于x 的结点时，在查找成功的情况下，平均需要比较（ ）个结点。

5．若n×n的下三角矩阵A 已经压缩存储到一维数组S[1..n*(n+1)/2]中，则A[i][j]对应的S 中的存储位置是（ ）。

6．已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，那么它的前序遍历序列是（ ）。

7．对于一个n 个结点的满二叉树，假设该树有m 个树叶，深度为h，则( h= ).

8. 具有5层结点的二叉平衡树至少有（ ）个结点，至多有（ ）

，表尾是（ ）。 个结点；广义表（a,b,c,d）的表头是（ ）

9．设计Hash 函数时要求其函数值应按（ ）取其值域的每一个值。

10．用冒泡排序法对n 个记录进行排序，第一趟要比较（ ）个元素, 第二趟要比较（ ）个元素。

11．对给定的一个有n 个元素的数组，建立一个有序单链表的算法的时间复杂度是（ ）。

12．有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为（ ）。

13．设高度为h 的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（ ），至多为（ ）。

14．在所有排序方法中，关键字比较的次数与记录的初始排序次序无关的排序方法是（ ）。直接存取文件是按（ ）方法组织的。

二、简答（共25分）

1．在单链表、双链表和单循环链表中，若仅知道指针p 指向某内部结点，不知道头指针，能否将结点*p从相应的链表中删除？若可以，其时间复杂度各为多少？（5分）

1