ncut数据结构复习题.pdf

数据结构复习题 一 判断题 1 采用循环链表作为存储结构的队列就是循环队列 F P63 2 哈夫曼树一定是完全二叉树 F P124 满二叉树 完全二叉树 P144 哈夫曼树 最优二叉树 3 选择排序是一种稳定的排序方法 F 不稳定 选择排序 快速排序 希尔排序 堆排序不是稳定的排序算法 冒泡排序 插入排 序 归并排序和基数排序是稳定的排序算法 4 在顺序存储结构的线性表中 取第 i 个元素操作的时间复杂度为 O 1 T 5 有向图中第 i 个顶点的出度等于其邻接矩阵中第 i 行非 0 元素的个数 T 6 在按值有序的线性链表中可以采用折半查找法进行查找 F 7 只有在初始数据为逆序时 冒泡排序所执行的比较次数最多 T 老师给的 8 在具有 n 个结点的完全二叉树中 无法确定其叶子结点的个数 F n0 n 1 2 n 为奇数 n 2 n 为偶数 9 一棵树转换成二叉树后 该二叉树的根结点一定没有右子树 T P137 根节点右子树必为空 10 对任意一个图 从它的某个顶点出发进行一次深度或广度优先搜索遍历时 均 可访问到该图的每个结点 F P170 11 二叉树的存储结构必须采用二叉链表结构 F P126 顺序存储 连式存储 12 给定一组关键字序列 按顺序构造二叉排序树 其树的形态与关键字的排列顺 序无关 F P229 有关 1 2 3 2 1 3 3 2 1 分叉条件的改变 13 当初始序列为逆序时 简单选择排序的比较次数达到最多 F 比较次数不变 14 在单链表表示的线性表中 取线性表第 i 个元素操作的时间复杂度为 O n n 为链表长度 T 15 具有 n 结点的二叉树 其最大深度为 n T 16 在具有 13 个叶子结点的二叉树中 其度为 2 的结点个数一定为 12 T P124 性质 3 叶子节点数为 n0 度为 2 的节点数为 n0 1 17 具有 n 个顶点无向图 其生成树中一定存在 n 1 条边 T 18 能采用折半查找法进行查找的查找表必须是有序并为顺序存储 T 19 若一棵二叉树中不存在度为 1 的结点 则该二叉树一定是一棵完全二叉树 F rt2 20 快速排序是目前所有排序方法中效率最高的稳定排序 F 不稳定 二 选择填空 1 下列排序方法中 排序所花时间不受数据初始排列特性影响的算法是 A 冒泡排序 B 简单选择排序 C 快速排序 D 直接插入排序 B 2 在一棵度为 3 的树中 度为 3 的结点数为 2 个 度为 2 的结点数为 1 个 度为 1 的结点数为 2 个 那么度为 0 的结点数为 个 A 4 B 5 C 6 D 7 C 树中结点数等于所有结点度数的和加 1 所以 2 1 2 X 2 3 1 2 2 1 X 0 1 所以 X 6 3 对于给定的 8 个元素 34 76 45 18 26 54 92 65 按给定顺序生成一棵二叉排序树 该树的深度为 A 4 B 5 C 6 D 7 B 4 在具有 n 个结点的线索树中 线索的个数为 A n 1 B n C n 1 D 不确定 C P132 2n n 1 n 1 5 若对给定的关键字序列利用折半查找方法进行查找 则关键字序列需满足的条件是 A 顺序存储且有序 B 顺序存储且升序 C 链式存储且有序 D 有序 A 6 在一个单链表中 已知 q 指针所指结点为 p 指针所指结点的前驱 若在 p q 之间插入 s 所指结点 则主要操作为 A s next p next p next s B q next s s next p C p next s next s next p D p next s s next q B 7 在具有 n 个顶点的无向图的邻接表中表结点总数最多为 A n n 1 B n n C 2 n n 1 D n n 1 2 A P163 8 设一个输入序列为 1 2 3 4 5 6 则借助一个栈所得到的输出序列不可能是 A 3 2 5 6 4 1 B 4 5 3 6 2 1 C 2 4 3 5 1 6 D 1 5 4 6 2 3 D 9 设循环队列存储空间的下标范围是 0 n 1 当队列头尾指针分别为 f 和 r 时 队列长度为 A r f B r f 1 C r f 1 n D r f n n D 10 如果二叉树T是由多叉树F转换而成 那么树F的后根序列应该是二叉树T的 A 层次遍历序列 B 先序序列 C 中序序列 D 后序序列 C 2536741 1 2 3 5 4 6 7 11 下列排序方法中 不稳定的排序方法是 A 冒泡排序 B 简单选择排序 C 归并排序 D 直接插入排序 B 12 在具有 n 个结点的二叉树中 其空指针域的个数为 A 2n 1 B n 1 C n 1 D 不确定 C 同线索 13 对给定模式串 abaabcac 其 next 值为 A 01122312 B 01121321 C 01234512 D 01112212 A 14 若深度为 6 的完全二叉树的第 6 层有 3 个叶结点 则该二叉树一共有 个结点 A 33 B 34 C 35 D 不确定 B 21 22 23 24 25 3 1 2 4 8 16 3 34 每一层最多 2n 1 15 设循环队列存储空间的下标范围是 0 n 1 当队列尾指针 rear 队列长度为 len 时 循 环队列中队头元素所在位置为 A rear len B rear len 1 C rear len 1 n D rear len n n D 16 在非空二叉树的中序遍历序列中 根结点的左边应该 A 只有左子树上的所有结点 B 只有左子树上的部分结点 C 只有右子树上的所有结点 D 只有右子树上的部分结点 A 17 在一个链表中 已知 p 指针指向链表中一个非空结点 现要删除链表中 p 指针所指结点 其时间复杂度为 O 1 的结构为 A 无头单循环链表 B 双循环链表 C 带头单循环链表 D 带头单链表 B 18 已知二叉树的先序序列为 ABDGCEFH 中序序列为 DGBAECHF 则其后序序列 为 A BDGCEFHA B GDBECFHA C BDGAECHF D GDBEHFCA D A B D G C E F H 19 如果二叉树 T 是由多叉树 F 转换而成 那么树 F 的叶子在二叉树 T 中应是满足 条件结点 A 左子树为空且右子树非空 B 左 右子树均为空 C 左子树为空 D 右子树为空 C 20 对二叉排序树进行 遍历 可以得到该二叉树所有结点构成的有序序列 A 层次 B 先序 C 中序 D 后序 C 三 简答下列各题 1 设循环队列存储在一段连续存储空间中 其空间大小为 QSIZE 若队列中只设 rear 和 quelen 来分别指示队尾元素的位置和队列中的元素个数 给出队列的满和空条件以及队头元素的位置 队列满 quelen 1 QSIZE 队列空 quelen 0 头元素位置 rear quelen QSIZE QSIZE 2 对下图 1 写出邻接矩阵 2 画出其最小生成树 3 写出从顶点 A 出发深度优先遍历和广度优先遍历的遍历序列 顶点顺序按从上到下 从左到右 A B C D E A 12 16 18 B12 2 22 C16 2 4 12 D18 4 10 E 22 12 10 3 将下列森林转化为二叉树 A B C D E F G H I J K 4 设 p 指针指向双向循环链表的某个结点 p NULL 写出删除 p 指针所指结点的只要操 作步骤 用类 C 语句描述 p prior next p next p next prior p prior free p 4 2 12 16 12 18 10 22 A B C D E A B C D E F G H I J K 5 写出下列模式的 next 值 按 KMP 算法进行匹配时 a b a a b c a c 0 1 1 2 2 3 1 2 6 设 p 指针指向一个单链表中的某个结点 p NULL 则删除 p 指针所指结点和删除 p 指 针所指结点的后继结点的时间复杂度分别是多少 P O n p next O 1 7 以关键字序列 25 50 15 35 80 85 20 40 36 70 为例 利用归并排序方法对 其进行排序 写出排序的每步过程 直接插入排序 25 50 15 35 80 85 20 40 36 70 15 25 35 50 20 40 80 85 36 70 15 20 25 35 40 50 80 85 36 70 15 20 25 35 36 40 50 70 80 85 8 已知一棵二叉树的中序序列为 DBHEAFICG 先序序列为 ABDEHCFIG 写出该树的后 续序列 DHEBIFGCA T B D E H C F I G 9 已知如下所示长度为 10 的表 29 12 38 32 42 8 40 52 47 50 1 按表中元素的顺序构造一棵二叉排序树 画出该二叉排序树 并求其在等概率情 况下查找成功的平均查找长度 2 若对表中元素先进行排序构成有序表 求在等概率情况下对此有序表进行折半查找时查 找成功的平均查找长度 29 12 8 28 32 42 40 52 47 50 ASLsucc 1 10 1 1 2 2 3 3 4 2 5 1 6 1 3 3 8 12 29 32 38 40 42 47 50 52 3 2 3 4 1 3 4 2 3 4 ASLsucc 1 10 1 1 2 2 3 4 4 3 2 9 10 对于一个具有 n 个结点的单链表 在给定指针 p 所指结点之后和给定值为 x 的结点之后插入 一个新结点的时间复杂度分别是多少 P O 1 X O n 11 关键字序列 39 12 47 60 72 52 按给定顺序构造一棵二叉平衡树 写出构造 过程的每步结果 并求其在等概率情况下查找成功的平均查找长度 四 编算法题 1 试写一算法 实现顺序表的就地逆置 即利用原表的存储空间将线性表 a1 a2 an 逆置 为 an an 1 a1 void reverses SqList inext p p next p next Lb next free Lb Lc La Lb La 3 二叉排序树结点结构为 其中 data 为整数类型 设计一个算法 打印出树中所有据域值为偶数的结点数据 并要求打印出的数据由小到大有序 void printBST BiTree T if T printBST T lchild if T data 2 0 printf T data printBST T rchild data next lchild data rchild 4 已知带头有序单链表 L 设计一个算法 将给定数据 x 插入到链表中 插入后保持链表 的有序性 链表结点结构为 其中数据域为整数类型 5 二叉树结点结构为 设计一个算法 统计出树中度为 1 的结点个数 void d1BiTree BiTree T int if T if T lchild NULL d1BiTree T lchild n d1BiTree T rchild n void insertList LinkList p L next while p next if p data p next data flag 1 p L if flag 1 while p next if flag 1 whil