内容发布更新时间 : 2024/9/22 1:41:14星期一 下面是文章的全部内容请认真阅读。
数据结构模拟试卷（8）
一、填空。
1．算法的健壮性是指 应 。
对于非法的输入也要能够给予正确的响
2．对一个线性表分别进行遍历和逆置运算，其最好的时间复杂度分别为 和
O(n) O(n) 。
3．n个数入栈，所有可能的出栈序列共有 4．下面程序段的时间复杂度为 O(
sum=1;
)
种。
（n>1）。
for(i=0; sum 5．若某二叉树有20个叶子节点，有30个节点仅有一个孩子，则该二叉树的总的节点数是 20+30+19=69 。 6．若以{4，5，6，7，8}作为叶子节点的权值构造哈夫曼树，则该Huffman树的根结点权值为 30 。 7．线索二叉树的左线索指向其 前驱 ，右线索指向其 后继 。 8．若含n个顶点的图形成一个环，则它的生成树可能有 n 种。 9．对于具有300个记录的文件，采用分块索引查找法查找，其中用二分查找法查找索引表，用顺序查找法查找块内元素，假定每块长度均为30个元素，则平均查找长度为 29/10+31/2=18.4 。 10．有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值为82的结点时，经 4 次比较后查找成功。 二、设一组记录的关键字为{4，5，7，2，1，3，6}，请回答相关问题： （1）按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成后的二叉排序树，并求出在等概率情况下查找成功的平均查找长度。 查找成功的平均查找长度18/7 （2）按表中元素的顺序进行插入生成一棵AVL树，画出该树。并求出在等概率情况下查找成功的平均查找长度。 1 ?查找成功的平均查找长度? 17/7 三、下图是一个四阶B树，请回答相关问题： （1）B+树和B树的主要区别是什么？（2）插入关键字87，画出插入调整后树的形状。 B树：每个结点的关键字个数等于指针个数减1。 B+树：每个结点的关键字个数等于指针个数。 B+树中所有叶子结点包含了全部关键字信息,以及指向关键字记录的指针,叶子节点依关键字大小自小到大链接。非终端结点作索引,结点中含有其子树根结点的最大(最小)关键字。 四、已知记录关键字集合为（53，17，19，61，98，75，79，63，46，49），要求散列到地址区间[0，10]中，散列函数选用除留余数法（mod 11）。请回答相关问题： （1）画出形成的散列表（若产生冲突，用开放定址的线性探测再散列法解决）。 0 75 1 63 2 79 3 46 4 5 49 6 17 7 61 8 19 9 53 10 98 （2）计算在等概率情况下查找成功时的平均查找长度。 18/10或1.8或9/5 (2)在等概率情况下查找成功时的平均查找长度 五、有7个顶点（v1,v2,v3,v4,v5,v6,v7）的有向图 的邻接矩阵如右图。请回答相关问题： 2 ∞ 2 ∞ ∞ ∞ ∞ ∞ ∞ 5 2 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 9 5 ∞ ∞ ∞ ∞ ∞ ∞ ∞ 3 ∞ ∞ ∞ ∞ 8 1 3 5 ∞ 5 ∞ ∞ ∞ 3 ∞ ∞ ∞ ∞ ∞ ∞ ∞ （1）画出该有向图 （2）画出邻接表 （3）写出从v1出发的深度优先遍历和广度优先遍历序列（4分） 深度dfs v1 v4 v5 v7 v6 v3 v2 广度bfs v1 v4 v3 v2 v5 v6? v7 （4）将图看成AOE网，画出关键活动及相应的有向边，写出关键路径的长度 关键路径的长度为20 六、设计算法。 1．已知一棵树T用二叉树表示，其结点形式如下，试编写一算法求树T中各结点的度数。 （1）写出相应的结构定义。 （2）编写算法。 left data right degree 3