文档介绍：福州大学2007〜2008学年第二学期考试A卷
课程名称 算法与数据结构
考生姓名 学号 专业或类别
题号
—一
二
三
四
总分
累分人签名
题分
30
15
10
45
100
树上的运算说法正确的是（）。
A、 从根结点起在二叉搜索树上查找某元素，若当前结点存放的元素比被查找元素 大，则在当前结点的右子树中继续查找
B、 在二叉搜索树中删除一个元素时，若被删元素所在结点存在左右子树，可用其 左子树中最右下结点中的元素替代被删元素，并将该最右下结点的左子树挂接 为其父结点的右子树。调整结构后的二叉树仍为一棵二叉搜索树。
C、 从根结点起在二叉搜索树中查找某元素y的直接前驱元素，若当前结点存放的 元素x小于y,则以x作为y直接前驱的候选者，并继续在当前结点的左子树 中进行查找
D、 从根结点起在二叉搜索树中查找某元素y的直接后继元素，若当前结点存放的 元素x等于y,则在当前结点的左子树中继续查找
二、填空题（每空1分，共15分）
得分
评卷人
1、 若在含n个元素的顺序表中执行删除操作，设删除每个元素的概率相同，则该删除
操作需移动元素的平均次数为 。
2、 在带哨兵结点的双循环链表中，设链结点的后继指针域为next，前驱指针域为prior，
指针header指向哨兵结点，则判断该链表是否为空的表达式为 。
3、 栈的操作原则为 。
4、 若用循环数组实现队列，队首游标front指向队首元素前一单元，队尾游标rear指向
队尾元素所在单元，设循环数组的单元个数为MaxSize，循环数组名为queue。则将 元素x入队应执行的语句为 ； 。
5、 不考虑树结点所存放的元素值，由3个结点可组成 种不同形态的二叉树。
6、 具有50个结点的完全二叉树，高度为 ，叶结点有 个。（设仅含
一个结点的二叉树的高度为1）
7、 若采用二叉链表作为二叉树的存储结构，在含有n个结点的二叉树对应的二叉链表
中，空链域总数为 。
8、 具有25个顶点的无向完全图具有 条边。
9、 对二叉搜索树进行 遍历可得到元素的递增序列。
10、 若含有n个顶点的无向图是一个环，则它有 棵生成树。
11、 对序列28 19 33 30 26 31使用冒泡排序法进行升序排序，进行第一趟冒泡
排序后得到的序列为 。
12、 希尔排序是一种 的排序方法。（填稳定或不稳定）
13、 在含有n个结点的平衡二叉树上执行插入操作的时间复杂度为 。
三、判断题（每题1分，共10分）
得分
评卷人
1、 度为2的有序树一定是二叉树。（）
2、 后序遍历树与后序遍历由该树转换得到的二叉树有相同的遍历结果。（）
3、 在完全二叉树中，叶结点仅可能在最下层出现。（）
4、 满二叉树中不存在度为1的结点。（）
5、 有向图中所有顶点的出度之和等于图中的有向边数。（）
6、 无向图的邻接矩阵一定是对称的。（）
7、 二部图的最大匹配一定是完全匹配。（）
8、 从某顶点出发进行深度优先遍历，最先退出dfs过程的是拓扑序列的最后一个顶点。 （）
9、 检查有向图是否存在回路的一种方法是使用无前驱顶点优先算法对有向图进行拓扑 排序。（）
10、 左偏高树的左