2022年东大18秋学期《数据结构Ⅱ》在线作业3

1、 单项题 1: 下面的说法中正确选项 1 任何一棵二叉树的叶子节点在三种遍历中的相对次序不变； 2 按二叉树定义,具有三个节点的二叉树共有 6 种；A: 1, 2 B: 1 C: 2 , 2 都错 D: 1 正确答案： 单项题 2: n 个顶点的有向完全图中含有向边的数目最多为 A: n-1 B: n C: nn-1/2 D: nn-1 正确答案： 单项题 3: 深度为 h 的满 m叉树的第 k 层的结点 1=k=h 数有 A: mk-1 B: mk-1 C: mh-1 D: mh-1 正确答案： 单项题 4: 下面关于线性表的表达中,错误选项 A: 线性表采纳次序储备,必需占用一片连续的储备

2、单元；B: 线性表采纳次序储备,便于进行插入和删除操作；C: 线性表采纳储备,不必占用一片连续的储备单元；D: 线性表采纳储备,便于插入和删除操作；正确答案： 单项题 5: 在运算机内实现递归算法时所需的帮助数据结构是 A: 栈 B: 队列 C: 树 D: 图 正确答案： 单项题 6: 在目标串 T 0.n-1 = xwxxyxy 中,对模式串 结果是 A: 1 B: 2 C: 3 D: 5 P0.m-1 = xy 进行子串定位操作的正确答案： 单项题 7: 设有一个次序栈,6 个元素 1、2 、3、4、5、6 依次入栈,假如6 个元素出栈的次序是2、3、4、6、5、1,就栈的容量至少应当是

3、A: 2 B: 3 C: 5 D: 6 正确答案： 单项题 8: 如长度为 n 的线性表采纳次序储备结构,在其第 度为 A: O0 B: O1 C: On D: On2 正确答案： 单项题 9: i 个位置插入一个新元素的算法的时间复杂如采纳孩子兄弟链表作为树的储备结构,就树的后序遍历应采纳二叉树的 A: 层次遍历算法 B: 前序遍历算法 C: 中序遍历算法 D: 后序遍历算法正确答案： 单项题 10: 一棵树高为 K 的完全二叉树至少的结点是 A: 2k 1 B: 2k-1 1 C: 2k-1 D: 2k 正确答案： 单项题 11: 一个含 n 个顶点和 e 条弧的有向图以邻接矩阵表示法为储

4、备结构,就运算该有向图中某个顶点出度的时间复杂度为 A: On B: Oe C: On+e D: On2 正确答案： 单项题 12: for（i=0 ；im；i+ ） for（ j=0 ；jt ；j+ ）ci j =0；for （i=0 ；im； i+ ）for （j=0 ；jt ； j+ ）for （k=0；kn； k+）ci j =c i j +a i k*bk j ；上列程序的时间复杂度为 A: O（m+n t ）B: O（m+n+t）C: O （m n t ）D: O （m t+n ）正确答案： 单项题 13: 如在 9 阶 B- 树中插入关键字引起结点分裂,就该结点在插入前含有的关键

5、字个数为 A: 4 B: 5 C: 8 D: 9 正确答案： 单项题 14: 对于哈希函数 Hkey=key%13, 被称为同义词的关键字是 A: 35 和 41 B: 23 和 39 C: 15 和 44 D: 25 和 51 正确答案： 单项题 15: 已知一组关键字为25,48,36,72,79,82,23,40,16,35,其中每相邻两个为有序子序列；对这些子序列进行一趟两两归并的结果是A: .25,36,48,72,23,40,79,82,16,35 B: .25,36,48,72,16,23,40,79,82,35 C: .25,36,48,72,16,23,35,40,79,82

6、 D: .16,23,25,35,36,40,48,72,79,82 正确答案： 单项题 16: 含 n 个关键字的二叉排序树的平均查找长度主要取决于 A: 关键字的个数 B: 树的形状 C: 关键字的取值 X围 D: 关键字的数据类型 正确答案： 单项题 17: 用 DFS遍历一个无环有向图,并在 列是 A: 逆拓扑有序 B: 拓扑有序 C: 无序的DFS算法退栈返回时打印相应的顶点,就输出的顶点序D: A 和 B 正确答案： 单项题 18: 设树 T的度为 4,其中度为1, 2,3 和 4 的结点个数分别为4,2,1,1 就 T 中的叶子数为A: 5 B: 6 C: 7 D: 8 正确答案

7、： 单项题 19: 某二叉树的先序序列和后序序列正好相反,就该二叉树的特点肯定是 A: 空或只有一个结点 B: 高度等于其结点数 C: 任一结点无左孩子 D: 任一结点无右孩子 正确答案： 单项题 20: 无向图中一个顶点的度是指图中 A: 通过该顶点的简洁路径数 B: 与该顶点相邻接的顶点数 C: 通过该顶点的回路数 D: 与该顶点连通的顶点数 正确答案： 单项题 1: 下面的说法中正确选项 1 任何一棵二叉树的叶子节点在三种遍历中的相对次序不变； 2 按二叉树定义,具有三个节点的二叉树共有 6 种；A: 1, 2 B: 1 C: 2 D: 1, 2 都错 正确答案： 单项题 2: n 个顶

8、点的有向完全图中含有向边的数目最多为 A: n-1 B: n C: nn-1/2 D: nn-1 正确答案： 单项题 3: 深度为 h 的满 m叉树的第 k 层的结点 1=k=h 数有 A: mk-1 B: mk-1 C: mh-1 D: mh-1 正确答案： 单项题 4: 下面关于线性表的表达中,错误选项 A: 线性表采纳次序储备,必需占用一片连续的储备单元；B: 线性表采纳次序储备,便于进行插入和删除操作；C: 线性表采纳储备,不必占用一片连续的储备单元；D: 线性表采纳储备,便于插入和删除操作；正确答案： 单项题 5: 在运算机内实现递归算法时所需的帮助数据结构是 A: 栈 B: 队列

9、C: 树 D: 图 正确答案： 单项题 6: 在目标串 T 0.n-1 = xwxxyxy 中,对模式串 结果是 A: 1 B: 2 C: 3 D: 5 正确答案： 单项题 7: P0.m-1 = xy 进行子串定位操作的设有一个次序栈,6 个元素 1、2 、3、4、5、6 依次入栈,假如6 个元素出栈的次序是2、3、4、6、5、1,就栈的容量至少应当是 A: 2 B: 3 C: 5 D: 6 正确答案： 单项题 8: 如长度为 n 的线性表采纳次序储备结构,在其第 度为 A: O0 B: O1 C: On D: On2 正确答案： 单项题 9: i 个位置插入一个新元素的算法的时间复杂如采纳

10、孩子兄弟链表作为树的储备结构,就树的后序遍历应采纳二叉树的 A: 层次遍历算法 B: 前序遍历算法C: 中序遍历算法 D: 后序遍历算法 正确答案： 单项题 10: 一棵树高为 K 的完全二叉树至少的结点是 A: 2k 1 B: 2k-1 1 C: 2k-1 D: 2k 正确答案： 单项题 11: 一个含 n 个顶点和 e 条弧的有向图以邻接矩阵表示法为储备结构,就运算该有向图中某个顶 点出度的时间复杂度为A: On B: Oe C: On+e D: On2 正确答案： 单项题 12: for（i=0 ；im；i+ ） for（ j=0 ；jt ；j+ ）ci j =0；for （i=0 ；i

11、m； i+ ）for （j=0 ；jt ； j+ ）for （k=0；kn； k+）ci j =c i j +a i k*bk j ；上列程序的时间复杂度为 A: O（m+n t ）B: O（m+n+t）C: O （ m n t ）D: O （ m t+n ）正确答案： 单项题 13: 如在 9 阶 B- 树中插入关键字引起结点分裂,就该结点在插入前含有的关键字个数为 A: 4 B: 5 C: 8 D: 9 正确答案： 单项题 14: 对于哈希函数 Hkey=key%13, 被称为同义词的关键字是 A: 35 和 41 B: 23 和 39 C: 15 和 44 D: 25 和 51 正确答案

12、： 单项题 15: 已知一组关键字为25,48,36,72,79,82,23,40,16,35,其中每相邻两个为有序子序列；对这些子序列进行一趟两两归并的结果是 A: .25,36,48,72,23,40,79,82,16,35 B: .25,36,48,72,16,23,40,79,82,35 C: .25,36,48,72,16,23,35,40,79,82 D: .16,23,25,35,36,40,48,72,79,82 正确答案： 单项题 16: 含 n 个关键字的二叉排序树的平均查找长度主要取决于 A: 关键字的个数 B: 树的形状 C: 关键字的取值 X围 D: 关键字的数据类型 正确答案： 单项题 17: 用 DFS遍历一个无环有向图,并在 列是 A: 逆拓扑有序 B: 拓扑有序 C: 无序的 D: A 和 B 正确答案： 单项题 18: DFS算法退栈返回时打印相应的顶点,就输出的顶点序设树 T的度为 4,其中度为1, 2,3 和 4 的结点个数分别为4,2,1,1 就 T 中的叶子数为A: