级计应数据结构试卷.pdf

第 1 页 共 7 页 西南交大西南交大 20201515 20201616 学年第学年第 1 1 学期学期期期末末考试试卷考试试卷 课程代码课程代码 21021017171616 课程名称课程名称 数据数据结构结构 考试时间考试时间 120120 分钟分钟 题号题号 一一 二二 三三 四四 五五 六六 总成绩总成绩 得分得分 阅卷教师签阅卷教师签字 字 注意 注意 请将请将一一 二题的答案 二题的答案用用 2 2B B 铅笔填铅笔填涂到机读卡上涂到机读卡上 答答在试卷上不得分 在试卷上不得分 一 一 单项单项选择选择题 每题 每小题小题 1 1 分 共分 共 2525 分 分 1 设某数据结构的二元组形式表示为设某数据结构的二元组形式表示为 A D R D 01 02 03 04 05 06 07 08 09 R r r 则数据结构 则数据结构 A 是 是 A 线性结构线性结构 B 树型结构树型结构 C 物理结构物理结构 D 图型结构图型结构 2 下面下面程序程序的时间复杂为 的时间复杂为 for i 1 s 0 i n i t 1 for j 1 jnext p data q data p next q next free q B q p next q data p data p next q next free q C q p next p next q next free q D q p next p data q data free q 4 设有设有 n 个待排序的记录关键字 则在堆排序中需要 个待排序的记录关键字 则在堆排序中需要 个辅助记录单元 个辅助记录单元 A 1 B n C nlog2n D n2 5 设一组初始关键字记录关键字为设一组初始关键字记录关键字为 20 15 14 18 21 36 40 10 则以 则以 20 为基为基 准记录的一趟快速排序结束后的结果为准记录的一趟快速排序结束后的结果为 A 10 15 14 18 20 36 40 21 B 10 15 14 18 20 40 36 21 C 10 15 14 20 18 40 36 2l D 15 10 14 18 20 36 40 21 6 设二叉排序树中有设二叉排序树中有 n 个结点 则在二叉排序树的平均平均查找长度为 个结点 则在二叉排序树的平均平均查找长度为 A O 1 B O log2n C O n 2 D O n2 班班 级级 学学 号号 姓姓 名名 密封装订线密封装订线 密封装订线密封装订线 密封装订线密封装订线 第 2 页 共 7 页 7 设设无向图无向图 G 中有中有 n 个顶点个顶点 e 条边 则其对应的邻接表中的表头结点和表结点的个数条边 则其对应的邻接表中的表头结点和表结点的个数 分别为 分别为 A n e B e n C 2n e D n 2e 8 设某强连通图中有设某强连通图中有 n 个顶点 则该强连通图中至少有 个顶点 则该强连通图中至少有 条边 条边 A n n 1 B n 1 C n D n n 1 9 设有设有 5000 个待排序的记录关键字 如果需要用最快的方法选出其中最小的个待排序的记录关键字 如果需要用最快的方法选出其中最小的 10 个记个记 录关键字 则用下列 录关键字 则用下列 方法可以达到此目的 方法可以达到此目的 A 快速排序快速排序 B 堆排序堆排序 C 归并排序归并排序 D 插入排序插入排序 10 下列下列四种排序中 四种排序中 的空间复杂度最大 的空间复杂度最大 A 插入排序插入排序 B 冒泡排序冒泡排序 C 堆排序堆排序 D 归并排序归并排序 11 下面有向图所示的拓扑排序的结果序列是 下面有向图所示的拓扑排序的结果序列是 A 125634 B 516234 C 123456 D 521643 12 无向图无向图的邻接矩阵是一个 的邻接矩阵是一个 A 对称矩阵对称矩阵 B 零矩阵零矩阵 C 上三角矩阵上三角矩阵 D 对角矩阵对角矩阵 13 邻接邻接表是图的一种表是图的一种 A 顺序存储结构顺序存储结构 B 链式存储结构链式存储结构 C 索引存储结构索引存储结构 D 散列存储结构散列存储结构 14 设设 G1 V1 E1 和和 G2 V2 E2 为两个图 如果为两个图 如果 V1 V2 E1 E2 则称 则称 A G1是是G2的子图的子图 B G2是是G1的子图的子图 C G1是是G2的连通分量的连通分量 D G2是是G1的连通分量的连通分量 15 下列下列关于关于图遍历的说法不正确的是 图遍历的说法不正确的是 A 连通图的深度优先搜索是一个递归过程连通图的深度优先搜索是一个递归过程 B 图的广度优先搜索中邻接点的寻找具有 先进先出 的特征图的广度优先搜索中邻接点的寻找具有 先进先出 的特征 C 非连通图不能用深度优先搜索法非连通图不能用深度优先搜索法 D 图的遍历要求每一顶点仅被访问一次图的遍历要求每一顶点仅被访问一次 16 关键路径关键路径是事件结点网络中是事件结点网络中 A 从源点到汇点的最长路径从源点到汇点的最长路径 B 从源点到汇点的最短路径从源点到汇点的最短路径 C 最长的回路最长的回路 D 最短的回路最短的回路 17 已知已知表长为表长为 25 的哈希表 用除留取余法 按公式的哈希表 用除留取余法 按公式 H key key MOD p 建立哈希表 建立哈希表 则则 p 应取应取 为宜为宜 A 23 B 24 C 25 D 26 1 2 3 564 第 3 页 共 7 页 18 在散列在散列查找查找中 平均查找长度主要与中 平均查找长度主要与 有关有关 A 散列表长度散列表长度 B 散列元素个数散列元素个数 C 装填因子装填因子 D 处理冲突方法处理冲突方法 19 m 阶阶 B 树中的树中的 m 是指是指 A 每个结点至少具有每个结点至少具有m棵子树棵子树 B 每个结点最多具有每个结点最多具有m棵子树棵子树 C 分支结点中包含的关键字的个数分支结点中包含的关键字的个数 D m阶阶B 树的深度树的深度 20 对线性表进行折半查找时 要求线性表必须对线性表进行折半查找时 要求线性表必须 A 以顺序方式存储以顺序方式存储 B 以链接方式存储以链接方式存储 C 以顺序方式存储 且结点按关键字有序排序以顺序方式存储 且结点按关键字有序排序 D 以链接方式存储 且结点按关键字有序排序以链接方式存储 且结点按关键字有序排序 21 下列二叉树中 下列二叉树中 不不 平衡的二叉树是平衡的二叉树是 22 快速排序快速排序方法方法在在 情况下最不利于发挥其长处情况下最不利于发挥其长处 A 要排序的数据量太大要排序的数据量太大 B 要排序的数据中有多个相同值要排序的数据中有多个相同值 C 要排序的数据已基本有序要排序的数据已基本有序 D 要排序的数据个数为奇数要排序的数据个数为奇数 23 在任何在任何情况情况下 时间复杂度均为下 时间复杂度均为 O nlogn 的不稳定的排序方法是的不稳定的排序方法是 A 直接插入直接插入 B 快速排序快速排序 C 堆排序堆排序 D 归并排序归并排序 24 如果将所有中国人按照生日来排序 则使用 如果将所有中国人按照生日来排序 则使用 算法最快 算法最快 A 归并排序归并排序 B 希尔排序希尔排序 C 快速排序快速排序 D 基数排序基数排序 25 希尔排序的增量序列必须是希尔排序的增量序列必须是 A 递增的递增的 B 递减的递减的 C 随机的随机的 D 非递减的非递减的 二 二 判断题判断题 正确的选正确的选 A A 错误的选 错误的选 B B 共共 1515 分 分 26 若一个叶子结点是某二叉树的中序遍历序列的最后一个结点 则它必是该二叉树的若一个叶子结点是某二叉树的中序遍历序列的最后一个结点 则它必是该二叉树的 先序遍历序列中的最后一个结点 先序遍历序列中的最后一个结点 27 希尔排序算法的时间复杂度为希尔排序算法的时间复杂度为 O n2 28 用邻接矩阵作为图的存储结构时 则其所占用的存储空间与图中顶点数无关而与图用邻接矩阵作为图的存储结构时 则其所占用的存储空间与图中顶点数无关而与图 中边数有关 中边数有关 29 入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况 入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况 30 有向图有向图的邻接表和逆邻接表中表结点的个数不一定相等 的邻接表和逆邻接表中表结点的个数不一定相等 31 对对链表链表进行插入和删除操作时不必移动链表中结点 进行插入和删除操作时不必移动链表中结点 32 子串子串 ABC 在主串在主串 AABCABCD 中的位置为中的位置为 2 第 4 页 共 7 页 33 设一棵二叉树的先序序列和后序序列 则能够唯一确定出该二叉树的形状 设一棵二叉树的先序序列和后序序列 则能够唯一确定出该二叉树的形状 34 当向二叉排序树中插入一个结点 则该结点一定成为叶子结点 当向二叉排序树中插入一个结点 则该结点一定成为叶子结点 35 顺序顺序表查找指的是在顺序存储结构上进行查找 表查找指的是在顺序存储结构上进行查找 36 如果如果两个关键字的值不等但哈希函数值相等 则称这两个关键字为同义词 两个关键字的值不等但哈希函数值相等 则称这两个关键字为同义词 37 哈夫曼哈夫曼树中没有度数为树中没有度数为 1 的结点 的结点 38 冒泡排序冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多 在初始关键字序列为逆序的情况下执行的交换次数最多 39 层次层次遍历初始堆可以得到一个有序的序列 遍历初始堆可以得到一个有序的序列 40 分块分块查找的基本思想是首先在索引表中进行查找 以便确定给定的关键字可能存在查找的基本思想是首先在索引表中进行查找 以便确定给定的关键字可能存在 的块号 然后再在相应的块内进行顺序查找 的块号 然后再在相应的块内进行顺序查找 三 三 填空题 每空填空题 每空 1 1 分 共分 共 2020 分 分 1 设一组初始记录关键字序列为设一组初始记录关键字序列为 45 38 68 95 76 9 26 52 则以 则以 d 4 为增量的为增量的 一趟希尔排序结束后的结果为一趟希尔排序结束后的结果为 1 2 根据初始关键字序列根据初始关键字序列 19 22 25 38 10 15 建立的二叉排序树的高度为建立的二叉排序树的高度为 2 3 解决散列表冲突的两种方法是解决散列表冲突的两种方法是 3 和和 4 4 设一棵二叉树的前序序列为设一棵二叉树的前序序列为 ABC 则有 则有 5 种不同的二叉树可以得到这种序种不同的二叉树可以得到这种序 列 列 5 设设 F 和和 R 分别表示顺序循环队列的头指针和尾指针 则判断该循环队列为空的条件分别表示顺序循环队列的头指针和尾指针 则判断该循环队列为空的条件 为为 6 6 设有一个设有一个 n 阶的下三角矩阵阶的下三角矩阵 A 如果按照行的顺序将下三角矩阵中的元素 包括对 如果按照行的顺序将下三角矩阵中的元素 包括对 角线上元素 存放在角线上元素 存放在 n n 1 个连续的存储单元中 则个连续的存储单元中 则 A i j 与与 A 0 0 之间有之间有 7 个数据元素 个数据元素 7 设有一组初始记录关键字序列为设有一组初始记录关键字序列为 50 16 23 68 94 70 73 则将它们调整成初 则将它们调整成初 始堆只需把始堆只需把 16 与与 8 相互交换即可 相互交换即可 8 设需要对设需要对 5 个不同的记录关键字进行排序 则至少需要比较个不同的记录关键字进行排序 则至少需要比较 9 次 至多需次 至多需 要比较要比较 10 次 次 9 设二叉排序树的高度为设二叉排序树的高度为 h 则在该树中查找关键字 则在该树中查找关键字 key 最多需要比较最多需要比较 11 次 次 10 设指针变量设指针变量 p 指向单链表中结点指向单链表中结点 A 指针变量 指针变量 s 指向被插入的结点指向被插入的结点 X 则在结点 则在结点 A 的后面插入结点的后面插入结点 X 需要执行的语句序列 需要执行的语句序列 s next p next 12 11 设二叉树中结点的两个指针域分别为设二叉树中结点的两个指针域分别为 lchild 和和 rchild 则判断指针变量 则判断指针变量 p 所指向的所指向的 结点为叶子结点的条件是结点为叶子结点的条件是 13 12 设二叉树中度数为设二叉树中度数为 0 的结点数为的结点数为 50 度数为 度数为 1 的结点数为的结点数为 30 则该二叉树中总共有 则该二叉树中总共有 14 个结点数 个结点数 13 设完全有向图中有设完全有向图中有 n 个顶点 则该完全有向图中共有个顶点 则该完全有向图中共有 15 条有向边 设完全条有向边 设完全 无向图中有无向图中有 n 个顶点 则该完全无向图中共有个顶点 则该完全无向图中共有 16 条无向边 条无向边 第 5 页 共 7 页 14 设有向图设有向图 G 的存储结构用邻接矩阵的存储结构用邻接矩阵 A 来表示 则来表示 则 A 中第中第 i 行中所有非零元素个数之行中所有非零元素个数之 和等于顶点和等于顶点 i 的的 17 第 第 i 列中所有非零元素个数之和等于顶点列中所有非零元素个数之和等于顶点 i 的的 18 15 完全二叉树中第完全二叉树中第 5 层上最少有层上最少有 19 个结点 最多有个结点 最多有 20 个结点 个结点 四 四 算法填空算法填空 每 每空空 2 2 分 共分 共 8 8 分 分 1 下面程序段的功能是实现二分查找算法 请在下划线处填上正确的语句 下面程序段的功能是实现二分查找算法 请在下划线处填上正确的语句 struct record int key int others int bisearch struct record r int k int low 0 mid high n 1 while lowdata 五 五 应用题应用题 共 共 3232 分 分 1 已知序列 已知序列 10 18 4 3 6 12 1 9 18 8 请用快速排序 请用快速排序并并写出每一趟排序的写出每一趟排序的 结果 结果 6 分 分 2 设有无向图设有无向图 G 如右图所示 要求画出用普里姆算法构造最小生成树的过程 并给 如右图所示 要求画出用普里姆算法构造最小生成树的过程 并给 第 6 页 共 7 页 出最小生成树的边集 出最小生成树的边集