武汉科技大学421数据结构参考答案2005考研试题研究生入学考试试题考研真题
● 摘要
参考答案
填空题（1×25＝25分）
1．算法的5，，，。 2．在树形结构中，树根结点没有（前驱）结点，其余每个结点有且只有（一）个前驱结点，叶子结点没有（后续）结点。 3．在图形结构中，每个结点的前驱节点数和后续结点数可以有（任意多个），6个顶点的无向图至少要（5）条边才是连通图。
4．从一个具有n 个结点的单链表中查找其值等于x 的结点时，在查找成功的情况下，平均需要比较（ (n+1)/2 ）个结点。
5．若n×n的下三角矩阵A 已经压缩存储到一维数组S[1..n*(n+1)/2]中，则A[i][j]对应的S 中的存储位置是（i(i+1)/2+j+1）。
6．已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，那么它的前序遍历序列是（cedba）。
h 7．对于一个n 个结点的满二叉树，假设该树有m 个树叶，深度为h，则(n= 2-1).
8. 具有5层结点的二叉平衡树至少有（15）个结点，至多有（31）个结点；广义表（a,b,c,d）的表头是（a），表尾是（(b,c,d)）。
9．设计Hash 函数时要求其函数值应按（ 平均概率 ）取其值域的每一个值。
10．用冒泡排序法对n 个记录进行排序，第一趟要比较（ n-1 ）个元素, 第二趟要比较（ n-2 ）个元素。
11．对给定的一个有n 个元素的数组，建立一个有序单链表的算法的时间复杂度是
2（O(n)）。
12．有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为（ 37/12）。
13．设高度为h 的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点h 数至少为（2h-1），至多为（2-1）。
14．在所有排序方法中，关键字比较的次数与记录的初始排序次序无关的排序方法是（选择排序）。直接存取文件是按（哈希）方法组织的。
简答
1、在单链表、双链表和单循环链表中，若仅知道指针p 指向某内部结点，不知道头指针，能否将结点*p从相应的链表中删除？若可以，其时间复杂度各为多少？
答：单链表：可以删除。将*p结点的数据和其后继结点的数据交换位置，再删除其后继结点，时间复杂度为O （1）； 双链表：可以删除，其时间复杂度为O （1）；单循环：可以删除。其时间复杂度为O （n ），若采用上述单链表的删除方法，时间复杂度也为O （1）。
2、已知一棵度为m 的树中有n 1个度为1的结点，n 2个度为2的结点，…，n m 个度为m 的结点，问该树中有多少片叶子？
答：（1）总结点数N =n0 +n1 +n2 +…+nm-1 +nm ①
（2）因为1度结点发出一个分支，2度结点发出两个分支，…，m 度结点发出m 个分支，叶结点不发出分支，所以总分支数B 为：B= n1 +2n2 +…+m*nm ②
（3）又因为除根结点之外，其他结点有且仅有一个进入支，因此，总分支数应等于总结点数减1，即B ＝N-1 ③
（4）由②、③两式可得：N＝n 1 +2n2 +…+m*nm ＋1 ④
（5）由①、④两式可得叶结点数：n 0＝n 2 +2n3 +3n4 +…+(m-1)nm
1
相关内容
相关标签