数据结构试题.pdf

数据结构试题数据结构试题 导弹学院 数据结构 课程结束考试卷 一 一 单项选择题 每题 2 分 共 20 分 1 链表中最常用的操作是在最后一个结点之后插入一个结点和 删除一个结点 则采用 D 存储方式最节省运算时间 A 单链表B 双向链表C 单循环链表D 带头结点的双向 循环链表 2 设一个栈的输入序列为 A B C D 则借助一个栈所得到的输 出序列不可能是 D A A B C DB D C B AC A C D BD D A B C 3 串是 D A 不少于一个字母的序列 B 任意个字母 的序列 C 不少于一个字符的序列 D 有限个字符的序列 4 链表不具有的特点是 A A 可随机访问任一元素B 插入 删除操作不需要移动元素 C 不必事先估计存储空间D 所需空间与线性表长度成正比 5 在有 n 个叶子结点的赫夫曼树中 其结点数为 D A 不确定B 2nC 2n 1D 2n 1 6 任何一个无向连通网的最小生成树 B A 只有一棵B 有一棵或多棵C 一定有多棵D 可 能不存在 7 将一棵有 100 个结点的完全二叉树从上到下 从左到右依次对结 点进行编号 根结点为 1 则编号为 49 的结点的左孩子编号为 A A 98B 99C 50D 482n 8 下列序列中 A 是执行第一趟快递排序后 得到的序列 排 序的关键字类型是字符串 A da ax eb de bb ff ha gc B cd eb ax da ff ha gc bb C gc ax eb cd bb ff da ha D ax bb cd da ff eb gc ha 9 用 n 个值构造一棵二叉排序树 最低高度为 D A n 2 B nlog2nC D 10 折半查找法要求查找表中各元素的关键字必须是 A 排列 A 非递增或非递减B 非递增C 非递减D 无序 二 判断题 每题 2 分 共 10 分 1 串长度是指串中不同字符的个数 2 一个有向图的邻接表和逆邻接表中的结点个数一定相等 3 在顺序表中取出第 I 个元素花费的时间与 I 成正比 n 1 4 在顺序栈满情况下不能作进栈运算 否则产生 上溢 5 二叉排列树或者是一空树 或者是有下列情况的二叉树 若它的左子树非空则根结点的值大于其左孩子的值 若它的右子树非 空 则根结点的值小于其右孩子的值 它的左右子树分别也为二叉 排序树 三 填空题 每题 2 分 共 20 分 1 带有头结点的单链表 L 中 第一个元素结点的指针是 L next 2 双向循环链表中 在指针 p 所指结点前插入指针 s 所指的结点 需执行下列语句 s prior p prior p prior next s s next p p prior s 3 设 S 为一个顺序栈 变量 top 指示栈顶位置 base 指示栈底 位置 则判断栈为空的条件是 S top S base 4 具有 100 个结点的完全二叉树的深度为 7 5 有向图 G 用邻接矩阵 A 存储 其第 I 行的所有元素之和等于第 I 个顶点的 出度 6 先序遍历森林正好等同于先序遍历对应的二叉树 7 对于下面图 1 所示的二叉树 按中序遍历得到的结点序列为 dbgeacf 四 应用题 1 答案 8 分别采用堆排序 快速排序 插入排序和归并排序算法对初始状 态为递增序列的表按递增顺序排序 最省时间的是 插入排序 算法 最费时间的是 快速排序 算法 9 数据的结构分为四个类型 分别是集合 线性结构 树形结构 和 图状结构或网状结构 10 对于关键字序列 12 13 11 18 60 15 7 18 25 100 用筛选法建堆 必须从关键字为 60 的结点开始 四 应用题 每题 7 分 共 42 分 1 已知二叉树的后序序列为 ABCDEFG 中序序列为 ACBGEDF 请构造出该二叉树 2 有一组关键字序列 38 19 65 13 97 49 41 95 1 73 采用冒泡排序方法由小到大进行排序 请写出每趟的结果 3819651397494195173 第一趟1938136549419517397 第二趟19133849416517395 第三趟131938414916573 第四趟1319384114965 第五第六趟131913841 第七趟1311938 第八趟11319 第九趟113 3 设 图 G V E 其 中 V 1 2 3 4 5 6 E 1 2 1 3 2 5 3 6 6 5 5 4 6 4 请写出图 G 中顶点的所有拓 扑序列 4 设哈希函数为 H key key mod 7 地址空间为 0 6 开始 时哈希表为空 用线性探测法解决冲突 请画出关键字为 23 14 9 6 30 12 18 时的哈希表 哈希表 0123456 14 18 23 930 12 6 5 对下面图 2 和图 3 所示的两棵二叉树 分别画出它们的顺序存储 结构 图 2 所示二叉树的顺序存储结构是 ABCD EFG 图 3 所示二叉树的顺序存储结构是 ABCD E0000FG 6 已知图的邻接表如下 画出图 G 的所有连通分量 1A 2 B 3C 4D 5E 6 F 7 G 8 H 9 I 五 算法设计题 8 分 设一个环上有若干个整数 现采用单循环链表 L 存储该环 已知 L 的结点结构为 Data next 试编写算法判断环上任意两个相邻元素值的差的绝对值是否不超过 2 当环上没有元素或只有一个元素时 或者任 意两个相邻元素值的差的绝对值都不超过 2 时返回 1 否则返回 0 intjudge LinkListL Lnode p int a p L next if p L p next L return 1 没有元素或只 有一个元素时 while p next L a abs p data p next data if a2 return 0 p p next return 1 导弹学院 数据结构 课程结束考试卷 二 一 选择题 每题 2 分 共 20 分 1 若线性表最常用的操作是存取第 i 个元素及其前驱的值 则采用 D 存储方式最节省时间 A 单链表B 双链表C 单循环链表D 顺序表 2 从 1 开始从上到下 从左至右对深度为 5 的完全二叉树进行连续 编号 则编号为 16 的结点 其右孩子的编号为 D A 31B 32C 33D 不存在 3 在一个长度为 n 的顺序存储线性表中 向第 i 个元素 1 i n 1 之前插入一个新元素时 需要从后向前依次后移B 个元素 A n iB n i 1C n i 1D i 4 用数组来表示图的存储结构叫B A 顺序存储结构B 数组表示法C 邻接表D 邻接矩阵 5 下列排序算法中 C 算法可能会出现下面情况 初始数据有序 时 花费的时间反而最多 A 堆排序B 冒泡排序C 快速排序D 希尔排序 6 对有 18 个元素的有序表 A 1 18 作折半查找 则查找 A 3 需比 较的元素的下标序列为 D A 1 2 3B 9 5 2 3C 9 5 3D 9 4 2 3 7 设循环队列中数组的长度是 n 其头尾指针分别为 f 和 r 则其 元素个数为 D A r fB r f 1C r f n 1 D r f n n 8 串是 D A 不少于一个字母的序列B 任意个字母的序列 C 不少于一个字符的序列D 有限个字符的序列 9 在树中 互为兄弟的结点拥有相同的 A A 双亲B 子孙C 路径D 孩子 10 若一棵二叉树具有 10 个度为 2 的结点 则该二叉树的度为 0 的结点个数是 B A 9B 11C 12D 不确定 二 判断题 每题 1 分 共 10 分 1 二叉树的先序遍历序列中 任意一个结点均处在其孩子结 点的前面 2 在带头结点的单循环链表中 任一结点的后 继指针均不空 3 若一棵二叉树的任一非叶子结点的度为 2 则该二叉树为满二叉树 4 二叉树只能采用二叉链表 来存储 5 有向图用邻接矩阵表示后 顶点 i 的出度等于 第 i 行中非 0 元素的个数 6 图 G 的某一最小生成树的代 价一定小于其它生成树的代价 7 在 AOE 网中一定只有一 条关键路径 8 插入排序是稳定的排序方法 9 单链表和顺序表执行插入和删除 操作的时间复杂度都是 O n 10 在快速排序算法中 以待排序的 n 个记录中的第一个记录的关键字值为基准 将所有记录 分为两组 该记录就在这两组的中间 这也是该记录的最终位置 三 填空 每题 2 分 共 20 分 1 在单链表中 删除指针 P 所指结点的后继结点的语句是 p next p next next 2 已知完全二叉树的第八层有八个结点 则其叶子结点数是 68 3 有三个结点的二叉树的不同型态有 5 种 4 有 n 个结点的二叉树 采用二叉链表作存储结构时 有 n 1 个空链域 5 有 n 个顶点的连通图 G 至少有 n 1 条边 6 有向网的邻接矩阵表示中 计算顶点 vi 的入度的方法是 求邻接 矩阵第 i 列非 元素的个数 7 有 n 个结点的完全二叉树的深度为 1 8 折半查找适用于 顺序 存储结构的有序表 9 若用起泡排序对关键字序列 18 16 14 12 10 8 进行从 小到大的排序 所要进行的关键字比较总次数为 15 10 在直接插入排序和简单选择排序中 若初始关键字基本有序 则应选用 直接插入 排序 四 解答下列各题 每题 7 分 共 35 分 1 一棵二叉树的先序序列和中序序列分别如下 画出该二叉树 先序序列 abdegcf中序序列 dbgeacf 2 对下面给出的权值序列 构造一棵赫夫曼树 并求出其带权路径 长度 4 5 6 7 10 12 15 18 23 赫夫曼树 带权路径长度 WPL 4 4 5 4 6 4 7 4 10 3 12 3 15 3 18 3 23 2 299 3 对下列关键字序列 写出采用基数排序算法将其排列成非递减有 序序列的每一趟结果 60 44 55 61 202 39 86 150 04 28 初始关键字 60 44 55 61 202 39 86 150 04 28 第一趟 按个位排序 60 150 61 202 44 04 55 86 28 39 第二趟 按十位排序 202 04 28 39 44 150 55 60 61 86 第三趟 按百位排序 04 28 39 44 55 60 61 86 150 202 4 已知哈希表地址空间为 0 8 哈希函数为 H key key mod 8 采用线性探测再散列法处理冲突 将下面的关键字序列依次存入哈希 表中 100 20 21 35 3 78 99 45 5 对下示有向图中 完成下列要求 1 画出其相应的邻接表 邻接点由大到小排列 1 2 3 4 5 6 1 邻接表为 2 指出从顶点 5 出发的所有拓扑有序序列 3 指出对应于邻接表 应得到的拓扑排序 2 从顶点 5 出发的所有拓扑排序序列有 5 1 3 2 4 6 2 5 1 3 4 2 6 35 1 3 4 6 2 4 5 1 4 3 2 6 5 5 1 4 3 6 2 3 对应于邻接表 应得到的拓扑排序 5 1 3 2 4 6 五 算法设计 共 15 分 1 8 分 设计算法统计二叉树 T 中所有结点的总数 C1 和叶子结点 的总数 C2 voidCount BiTreeBT int C1 int C2 if BT C1 统计所有结点数 if BT lchild NULL BT rchild NULL C2 统计叶子结点数 Count BT lchild C1 C2 Count BT rchild C1 C2 2 7 分 比较字符表 A 和 B 并用返回值表示结果 值为正 表示 AB 值为负 表示 AB 值为零 表示 A B 假设字符表 A 和 B 存储在顺序表中 int ListComp SqList A SqList B for i 1 A elem i B elem i i if A elem i B elem i return A elem i B elem i return 0 ListComp 导弹学院 数据结构 课程结束考试卷 三 一 单选题 每题 2 分 共 20 分 1 一个栈的输入序列为 1 2 3 4 下面哪一个序列不可能是这 个栈的输出序列 C A 1 3 2 4B 2 3 4 1C 4 3 1 2D 3 4 2 1 2 下列排序方法中 哪一种方法的比较次数与记录的初始排列状态无 关 D A 直接插入排序B 起泡排序C 快速排序D 简单选择排序 3 对 n 个记录进行快速排序 平均时间复杂度为 A A O nlogn B O n2 C O logn D O n 4 若一棵二叉树具有 10 个度为 2 的结点 则该二叉树的度为 0 的结 点个数是 B A 9B 11C 12D 不确定 5 有 n 个结点的完全二叉树的深度是 C A log2nB log2n 1C 1D 下列说法中错误的是 B A n 个结点的树的各结点度数之和为 n 1B n 个结点的无向图最 多有 n n 1 条边 C 用邻接矩阵存储图时所需存储空间大小与图的结点数有关 而与 边数无关 D 栈是后进先出的线性表 7 任何一个连通图的最小生成树B A 只有一棵B 有一棵或多棵C 一定有多棵D 可能不存在 8 个不同的数据元素进行直接插入排序 最多需要进行 C 次比较 A B C 4D 9 在一个长度为 n 的顺序存储线性表中 删除第 i 个元素 1 i n 时 需 要 从 前 向 后 依 次 前 移 A 个 元 素 A n iB n i 1C n i 1D i 10 一棵有 层的满二叉树中结点总数为 A A B C D 二 填空题 每题 2 分 共 20 分 1 在线性结构和图结构中 数据元素之间分别存在着一个对一个 和多个对多个的关系 2 从一个栈中删除元素时 首先移 动指针 将指针减 1 然后取出该元素 3 串的表示方法有 定长顺序存储表示 堆分配 存储表示 和块链存储表示三种 4 直接插入排序的时间复杂度为O n2 5 先序 遍历森林正好等同于先序 根 遍历对应的二叉树 6 对于一个长度为 n 的单链表 在表头插入元素的时间复杂度为O 1 在表尾插入元素的时间复杂度为O n 7 对于一个具有 n 个顶点和 e 条边的无向图 在其对应的邻接表中 所含表结点为 2e 个 8 在一个大顶堆中 堆顶结点的值是所有结点中的 最大值 9 以折半查找方法查找一个线性表时 此线性表必须是 最大值 存储结构的 有序 表 10 带权的图又称为网 三 判断题 每题 2 分 共 10 分 1 只有最下面两层的结点的度数小于 2 的二叉树一定是完 全二叉树 2 n 个结点的无向图 若它有 n n 1 2 条边 则它一定是连通的 3 栈和队列都是操作受限的线性表 4 邻接矩阵表示图所用的存储空间大小与图的边数成正比 5 赫夫曼树一定是满二叉树 四 简答 应用题 每题 9 分 共 36 分 1 以下面数据作为叶子结点的数值构造一棵赫夫曼树 并计算出 其带权路径长度 6 7 8 9 10 18 20 22 2 已知待排序记录的关键字序列如下 7273712394160568 请列出快速排序全过程 初始状态 7273712394160568 一次划分后 6805712316 72 9473 分别快速排序 160523 68 71 73 94 05 16 23 有序序列 0516236871727394 3 一个无向网的邻接矩阵如下 要求 1 画出该无向网 2 构造对应的最小生成树 假设 该无向网的顶点序列是 v0 v1 v2 v3 v4 v5 v6 最小生成树 4 一棵二叉树的先序序列为 ABCDEFGH 中序序列为 CBEDAGFH 试构造此二叉树 五 算法设计题 每题 7 分 共 14 分 1 设计算法把链表 hb 接在链表 ha 后面形成链表 hc void ListConcat LinkList ha LinkList hb LinkList hc 把 链表 hb 接在 ha 后面形成链表 hc hc ha p ha while p next p p next p next hb ListConcat 2 编写算法实现直接插入排序 导弹学院 数据结构 课程结束考试卷 四 一 单项选择题 每题 2 分 共 20 分 1 一个栈的输入序列为 1 2 3 4 5 则下列序列中是栈的输出序列 是 a a 2 3 4 1 5b 5 4 1 3 2c 3 1 2 4 5d 1 4 2 5 3 2 若某线性表最常用的操作是在最后一个元素之后插入一个元素和 删除第一个元素 则采用下列 c 存储方式最节省时间 a 单链表b 双向链表c 带头结点的双向循环链表d 单循 环链表 3 二叉树有 n 个结点 则其深度为 d a nb 1c d 不确定 4 带权有向图 G 用邻接矩阵 A 存储 则顶点 i 的出度等于 A 中a a 第 i 行非 的元素个数b 第 i 列非 的元素个数 c 第 i 行非 0 的元素个数d 第 i 列非 0 的元素个数 5 下列排序算法中 在待排序的数据表已经为有序时花费时间反而 最多的是 a a 快速排序b 希尔排序c 冒泡排序d 直接插 入排序 6 下列排序算法中 c 每一趟都能选出一个元素放在其最终位置 上 a 归并排序b 希尔排序c 冒泡排序d 直接插入排 序 7 下列排序算法中 b是稳定的排序方法 a 希尔排序b 归并排序c 快速排序d 堆排序 8 在一个单链表 HL 中 若要删除由指针 q 所指向结点的后继结点 则执行c a p q next p next q next b p q next q next p c p q next q next p next d q next q next next q next q 9 有 n 个结点的二叉树若符合条件 d 则是完全二叉树 a 深度为 1b 树的路径长度最短 c 叶子只出现在最下面的两层上d 结点编号与满二叉树的前 n 个结点一一对应 10 折半查找方法适用于 b a 单链表的查找b 顺序表的查找 c 双向链表的查找d 任意线性表的查找 二 判断题 每题 1 分 共 10 分 1 线性表的唯一存储形式是链表 2 已知指针 p 指向链表 L 中的某结点 执行 p p next 语句不会删除这个链 表中的结点 3 在链队列中 即使不设置尾指针也能进行 入队操作 4 如果一个串中的所有字符均在另一串中出现 则说前者是后者的子串 5 二叉树中的叶子结点就是二叉 树中左 右子树都为空的结点 6 任一 AOE 网中最多只有 一条关键路径 7 若图 G 的最小生成树不唯一 则 G 的边 数一定多于 n 1 n 为顶点数 8 当一个二叉树的结点数 n 2k k 为大于 0 的整数 时 这个二叉树才有可能是满二叉树 9 直接插入排序是一种稳定的排序方法 10 二叉树的先序和后序序列不能唯一确定这棵二叉树 三 填空 每题 2 分 共 20 分 1 带头结点的单链表 L 为空表的条件是 L next NULL 2 在双向链表中 在指针 p 所指结点前插入一个结点 s 的语句序 列 是 s prior p prior p prior next s s next p p prior s 3 衡量算法好坏的依据是 正确性 可读性 健壮性 效率和低存 储量需求 4 已知深度为 7 的完全二叉树 第 7 层上有 10 个叶子结点 则整 个二叉树的结点数 是 73 5 有 n 个结点的二叉树的深度最多是 n 6 在一个具有 n 个顶点的无向完全图中 包含有 n n 1 2 条边 7 已知二叉树有 50 个叶子结点 则该二叉树度为 2 的结点数是 49 8 线性表的长度为 n 则插入位置有n 1个 9 列出两种构造哈希函数的方法 直接定址法 数字分析法 平 方取中法 折叠法 除留余数法 随机数法 六种方法中的任意两种 10 假定一组记录的排序码为 46 79 56 38 40 80 对其进行起泡 排序的过程中 第二趟排序的结果为 46 38 40 56 79 80 四 解答题 每题 8 分 共 40 分 1 已知二叉树的中序与后序遍历序列如下 构造此二叉树 中序 cbedahgijf 后序 cedbhjigfa 2 以下面数据做叶子结点的权值构造一棵赫夫曼树 并计算出其带 权路径长度 5 6 7 8 9 10 15 18 22 4 答案 判定树 3 对下面数据表写出采用归并排序算法排序的每一趟的结果 50 12 20 31 1 5 44 166 61 100 30 50 12 20 31 1 5 44 166 61 100 30 第一趟 12 50 20 31 1 5 44 166 61 100 30 第二趟 12 20 31 50 1 5 44 166 30 61 100 第三趟 1 5 12 20 31 44 50 166 30 61 100 第四趟 1 5 12 20 30 31 44 50 61 100 166 4 画出在递增有序表 A 1 21 中进行折半查找的判定树 5 求出下图的所有拓扑有序序列 并指出哪一种是采用邻接表 邻 接点由大到小排列 存储时拓扑排序算法的运行结果 五 算法设计 每题 5 分 共 10 分 1 设计算法在无头结点链表 L 的第 i 个元素之前插入元素 b Status Insert LinkList L int i int b 在无头结点链表 L 的 第 i 个元素之前插入元素 b p L q LinkList malloc sizeof LNode q data b if i 1 q next p L q 插入在链表头部 else while i1 p p next q next p next p next q 插入在第 i 个元素的 位置 Insert 2 编写算法实现顺序查找 导弹学院 数据结构 课程结束考试卷 五 一 填空题 第 2 题和第 8 题各 2 分 其余每空 1 分 共 24 分 1 在线性结构和树形结构中 数据元素之间分别存在着 一个对一 个 和 一个对多个 的关系 2 假定一组记录序列为 46 79 56 38 40 84 则利用堆排序方法建立的初始大顶堆为 84 79 56 38 40 46 3 队列的插入操作在 队尾 进行 删除操作在 队头 进行 4 向一个顺序栈插入一个元素时 首先把待插入元素 插入 赋值 到这个位置上 然后使 指针 后移一 个位置 5 串的表示方法主要有 定长顺序存储表示 堆分配存储表示 和 块链存储表示 三种 6 从一棵二叉排序树中查找一个元素时 若元素的值等于根结点的 值 则表明 查找成功 若元素的值小于根结点的值 则继续向 左 子树 查找 若元素的大于根结点的值 则继续向 右子树 查找 7 对于下面图 1 所示的无向图 从顶点 A 开始进行深度优先搜索遍 历得到的顶点序列之一为 A B E C D F 从顶点 A 开始进行广度 优先搜索遍历得到的顶点序列之一为 A B C D E F 8 对于下面图 2 所示的 AOE 网 V0 V1 V5 V2 V3 V6 V4 是它的一个拓扑有序序列 9 对于一个具有 n 个顶点和 e 条边的连通图 其生成树中的顶点数 和边数分别为 n 和 n 1 10 以折半查找方法查找一个线性表时 此线性表必须是 顺序 存储的 有序 表 11 每次从无序表中取出一个元素 把它插入到有序表中的适当位 置 此种排序方法叫做 插入 排序 每次使两个相邻的有序表合并 成一个有序表的排序方法叫做 归并 排序 二 判断题 每题 1 分 共 10 分 1 线性表采用链式和顺序存储方式存储 执行插入和删除操 作的时间复杂度都是 n 2 二叉树中的叶子结点就是 二叉树中左 右子树都为空的结点 3 在 AOE 网中一定只 有一条关键路径 4 栈和队列都是操作受限的线性表 5 在一个有向图的邻接表或逆邻接表中 如果某个顶点的链 表为空 则该顶点的度一定为 0 6 在索引顺序表的查找 中 对索引表既可采用顺序查找方法 也可采用折半查找方法 7 在快速排序算法中 以待排序的 n 个记录中的第一个记录 的关键字值为基准 将所有记录分为两组 该记录就在这两组的中间 这也是该记录的最终位置 8 当一个二叉树的结点数 n 2k k 为大于 0 的整数 时 这个二叉树才有可能是满二叉树 9 基数排序是一种不稳定的排序方法 10 在循环队列中 若尾指针 Rear 大于头指针 Front 则 其元素数为 Rear Front 三 选择题 每题 2 分 共 20 分 1 在一个长度为 n 的顺序存储线性表中 向第 i 个元素 1 i n 1 之前插入一个新元素时 需要从后向前依次后移B个元素 A n iB n i 1C n i 1D i 2 在一个单链表 HL 中 若要在指针 q 所指的结点的后面插入一个 由指针 p 所指的结点 则执行D A q next p next p next q B p next q next q p C q next p next p next q next D p next q next q next p 3 串的长度是D A 串中不同字母的个数 B 串中不同字符的个数 C 串中所含字符的个数 且大于 0D 串中所含字符的个数 4 有 64 个结点的完全二叉树的深度为B A 8B 7C 6D 5 5 用数组来表示图的存储结构叫 B A 顺序存储结构B 数组表示法C 邻接表D 邻接矩阵 6 对有 18 个元素的有序表 A 1 18 作折半查找 则查找 A 3 需比 较的元素序列下标为 D A 1 2 3B 9 5 2 3C 9 5 3D 9 4 2 3 7 用某种排序方法对记录序列 25 84 21 47 15 27 68 35 20 进行排序时 记录序列的变化情况如下 1 25 84 21 47 15 27 68 35 20 2 20 15 21 25 47 27 68 35 84 3 15 20 21 25 35 27 47 68 84 4 15 20 21 25 27 35 47 68 84 则所采用的排序方法是 D A 选择排序B 希尔排序C 归并排序D 快速排序 8 一个栈的输入序列为 12345 则下列序列中不可能是栈的输出序 列是D A 12345B 54321C 23451D 41235 9 链表不具有的特点是A A 可随机访问任一元素B 插入 删除操作不需要移动元 素 C 不必事先估计存储空间D 所需空间与线性表长度成正比 10 将一棵有 100 个结点的完全二叉树从根这一层开始 每一层上 从左到右依次对结点进行编号 根结点为 1 则编号为 49 的结点的 左孩子编号为A A 98B 99C 50D 48 四 算法填空题 在画有横线的地方填写合适的内容 6 分 在有序表 ST 中折半查找其关键字等于 key 的数据元素的算法 若找 到 则函数值为该元素在表中的位置 否则为 0 intSearch Bin SSTableST KeyTypekey low 1 high ST length while low high mid low high 2 if EQ key ST elem mid key returnmid else if LT key ST elem mid key high mid 1 else low mid 1 return0 Search Bin 1 二叉树 对应的二叉链表 五 解答题 每题 8 分 共 40 分 1 一 棵 二 叉 树 的 先 序 序 列 为 ABCDEFGH 中 序 序 列 为 CBDAFEHG 试构造此二叉树 并画出它所对应的二叉链表 2 2 用起泡排序算法 对关键字序列 46 32 55 81 65 11 25 43 按从小到大的次序进行排列 写出每趟排序的结果 46 32 55 81 65 11 25 43 第一趟32 46 55 65 11 25 43 81 第二趟32 46 55 11 25 43 65 第三趟32 46 11 25 43 55 第四趟32 11 25 43 46 第五趟11 25 32 43 第六趟11 25 32 3 一个无向网的邻接矩阵如下 要求 1 画出该无向网 2 利用克鲁斯卡尔算法构造相应的最小生成树 假设该无向网的 顶点序列是 v0 v1 v2 v3 v4 v5 v6利用 克鲁斯卡尔算法构造的最小生成树 4 假设有一份电文共使用了八 种字符 a b c d e f g h 这 8 种字符在电文中出现的概 率分别为 0 07 0 19 0 02 0 06 0 32 0 03 0 21 0 10 请构造相应的赫夫曼树 并求出每个字符的赫夫曼编码 5 设有一组关键字 19 01 23 14 55 20 84 27 68 11 采用哈希函数 H key key 13 并用开放定址法的线性探测再 散列处理冲突 试在 0 12 的散列地址空间中对该关键字序列构造哈 希表 字符赫夫曼编码 a1110 b00 c11010 d1100 e10 f11011 g01 h1111 4 设这 8 种字符的权值分别是 7 19 2 6 32 3 21 10 导弹学院 数据结构 课程结束考试卷 六 一 选择题 每题 2 分 共 20 分 1 下面程序段的时间复杂度为 C for int i 0 im i for int j 0 jn j a i j i j A O m2 B O n2 C O mn D O m n 2 在一个长度为 n 的顺序存储线性表中 向第 i 个元素 1 i n 之 前插入一个新元素时 需要从后向前依次后移B个元素 A n iB n i 1C n i 1D i 3 在一个带头结点的单链表 HL 中 若要向表头插入一个由指针 p 指向的结点 则执行D A HL p p next HL B p next HL HL p C p next HL p HL D p next HL next HL next p 4 栈的插入与删除操作在A进行 A 栈顶B 栈底C 任意位置D 指定 位置 5 从一个循环顺序队列删除元素时 首先需要C A 前移一 位队首指针 B 后移一位队首指针C 取出队首指针所指位置上 的元素D 取出队尾指针所指位置上的元素 6 在一棵二叉树中 度为 2 的结点数有 15 个 则度为 0 的结点数 为 C个 A 14B 15C 16D 不确定 7 在 一 棵 二 叉 树 中 第 5 层 上 的 结 点 数 最 多 为 B A 10B 16C 31D 不确定 8 在一个无向图中 所有顶点的度数之和等于所有边数的 C 倍 A 1 2B 1C 2D 4 9 下列排序算法中 D 算法可能会出现下面情况 在最后一趟开 始之前 所有元素都不在最终的位置上 A 堆排序B 冒泡排序C 快速排序D 插入排序 10 有 n 个 叶 子 的 赫 夫 曼 树 其 总 结 点 数 为 D A nB 2nC 2n 1D 2n 1 二 判断题 每题 1 分 共 10 分 1 在对链队列作出队操作时 不会改变 front 指针的值 2 若一个栈的输入序列为 123456 且其输出序列的第一个元 素为 6 则其输出序列一定是 654321 3 二叉树中的 叶子结点就是二叉树中左 右子树都为空的 结点 4 一棵有 n 个结点的二叉树的深度为 1 5 有向图用邻接矩阵表示后 顶点 i 的入度等于邻接矩阵中第 i 列的元 素个数 6 有向图的邻接表和逆邻接表中的结点数相同 7 在索引顺序表的查找中 对索引表既可采用顺序查找方法 也可采用折半查找方法 8 若有 n 个顶点的有向图 G 的拓 扑序列唯一 则图中必定仅有一个顶点的入度为 0 一个顶点的出度 为 0 9 任何情况下快速排序是所有排序算法中最快的一种 10 一个有向图中 最多可有 n n 1 条弧 三 填空 每题 2 分 共 20 分 1 在单循环链表中 最后一个结点的指针指向头 结点 2 串的表示方法有 3 种 分别是 定长顺序存储表示 堆分配存储 表示和块链存储表示 3 已知深度为 6 的完全二叉树的第 6 层有 8 个结点 则叶子结点数 是 20 4 队列的插入操作在队尾 进行 删除操作在 队头 进行 5 对于一个具有 n 个顶点的图 若采用邻接矩阵表示 则矩阵大小 为 n n 6 在一个具有 n 个顶点的无向图中 要连通所有顶点则至少需要 n 1 条边 7 在有序表 A 1 18 中 采用折半查找算法查找元素值等于 A 7 的元素 所比较过的元素的下标依次为 9 4 6 7 8 冒泡排序在最好情况下的元素交换次数为 0 9 在造哈希表时 若不产生冲突 那么哈希地址与关键字之间应有 一一对应 关系 10 若要合并两个线性表 采用 循环链表 存储最省时 四 解答题 每题 9 分 共 36 分 1 一棵树的中序遍历序列为 cbedahgijf 后序遍历序列为 cedbhjigfa 试画出此树 答案如图 1 所示 2 对下面数据表 写出采用快速排序算法时的排序全过程 70 12 20 31 1 5 44 66 61 200 30 3 取哈希函数 H Key Key MOD 11 用链地址法处理冲突 试对关键字序列 22 41 53 46 30 13 1 67 构造哈希 表 答案如图 2 所示 4 试列出下图中全部可能的拓扑有序序列 并指出用邻接表 邻 接点由大到小排列 作存储结构时应得到哪一个 五 算法设计 每题 7 分 共 14 分 1 设计算法实现折半查找 2 设计算法在无头结点链表 L 中删除第 i 个元素 2 Status Delete LinkList L int i 在无头结点链表 L 中删除第 i 个元素 if i 1 L L next 删除第一个元素 else p L while i1 p p next p next p next next 删除第 i 个元素 Delete 导弹学院 数据结构 课程结束 考试卷 七 一 单项选择题 每题 2 分 共 20 分 1 链表不具有的特点是 a a 可随机访问任一元素b 插入 删除操作不需要移动元素 c 不必事先估计存储空间d 所需空间与线性表长度成正比 2 在一个长度为 n 的顺序存储线性表中 删除第 i 个元素 1 i n 时 需要从前向后依次前移 c 个元素 a n i 1b n i 1c n id i 3 栈的插入与删除操作在a进行 a 栈顶b 栈底 c 任意位置d 指定位置 4 任何一个无向连通图的最小生成树b a 只有一棵b 有一棵或多棵c 一定有多棵d 可 能不存在 5 有 32 个结点的完全二叉树的深度为 c a 8 b 7c 6d 5 6 在有 n 个结点的二叉链表中 空链域的个数为c a n 1b 2n 1c n 1d 2n 1 7 用数组来表示图的存储结构叫 b a 顺序存储结构b 数组表示法c 邻接表d 邻接矩阵 8 对有 18 个元素的有序表 A 1 18 作折半查找 则查找 A 3 比较 的序列下标为 d a 1 2 3b 9 5 2 3c 9 5 3d 9 4 2 3 9 下列排序算法中 b是稳定的排序方法 a 希尔排序b 归并排序c 快速排序d 堆排序 10 一组记录的关键字为 46 79 56 38 40 84 则利用 堆 排 序 的 方 法 建 立 的 初 始 大 顶 堆 是 b a 79 46 56 38 40 80b 84 79 56 38 40 46 c 84 79 56 46 40 38d 84 56 79 40 46 38 二 判断题 每题 1 分 共 10 分 1 线性表就是顺序表 2 链表只能借助于指针来实现 3 线性表的长 度是指其中元素所占用的存储空间的字节数 4 栈是后进 先出的线性表 5 在对链队列作出队操作时 不会改变 front 指针的值 6 在一棵树中 互为兄弟的结点具有相同的祖 先 7 AOE 网所表示的工程至少所需的时间等于从源点到 汇点的最短路径的长度 8 若从某顶点开始对有 n 个顶点 的有向图 G 进行深度优先遍历 所得的遍历序列唯一 则可断定其 弧度数为 n 1 9 在快速排序算法中 以待排序的 n 个记 录中的第一个记录的键值为基准 将所有记录分为两组 该记录就在 这两组的中间 这也是该记录的最终位置 10 静态查找 表的 0 号单元存放着表中第一个记录 三 填空题 每题 2 分 共 20 分 1 在带头结点的双向循环链表 L 中 最后一个结点的指针是 L prior 用 L 表示 2 在一个无向图中 所有顶点的度数之和等于所有边数的 2 倍 3 判 断 顺 序 栈 S 为 空 的 条 件 是 S top S base 4 已知循环队列用长度为 n 的数组存储元素值 用 f r 分别作头尾 指针 则当前元素个数为 r f n n 5 若某二叉树有 20 个叶子结点 有 30 个结点仅有一个孩子 则该 二叉树的结点总数是 69 6 对于一棵有 100 个结点的二叉树 若一个结点的编号为 30 则 它的左孩子结点的编号为 60 右孩子结点的编号为 61 7 对于一个具有 n 个顶点和 e 条弧的有向图 在其对应的邻接表中 所含表结点为 e 个 8 对于一个具有 n 个顶点和 e 条边的连通图 其生成树中的顶点数 和边数分别为 n 和 n 1 9 简单选择排序在最好情况下所作的交换元素的次数为 0 10 以折半查找方法查找一个线性表时 此线性表必须是 顺序 存储的 有序 表 四 解答下列各题 每题 9 分 共 36 分 1 已知一树的双亲表示如下 其中各兄弟结点是依次出现的 画出 该树及对应的二叉树 12345678910 11 12 1314 15 DaABCD EFG H IJKLM N O Pt 011122334456678 1 树及对应的二叉树 2 一棵二叉排序树结构如下 各结点的值从小到大依次为 1 8 请 标出各结点的值 3 对下面数据表 写出采用起泡排序算法排序的每一趟结果 25 10 20 31 5 44 16 61 100 35 4 求出下图的一棵最小生成树 3 6453 7 4 5 5886 5 五 算法设计 每题 7 分 共 14 分 1 已知单链线性表 La 和 Lb 的元素按值非递减排列 设计算法归并 La 和 Lb 后得到新的单链线 性表 Lc 元素也按值非递减排列 2 设计算法实现链表的就地逆置 void LinkList reverse Linklist L 链表的就地逆置 为简化 算法 假设表长大于 2 p L next q p next s q next p next NULL while s next q next p p q q s s s next 把 L 的元素逐个插入新表表头 q next p s next q L next s LinkList reverse 导弹学院 数据结构 课程结束考试卷 八 一 单项选择题 每题 2 分 共 20 分 1 设循环队列中数组的长度是 n 其头尾指针分别为 f 和 r 则其 元素个数为 d a r fb r f 1c r f n 1 d r f n n 2 有 n 个结点的完全二叉树一定是 a a 唯一的b 不唯一c 满二叉树d 赫夫曼树 3 若某链表最常用的操作是在最后一个结点之后插入一个结点和删 除最后一个结点 则采用 c 存储方式最节省时间 a 单链表b 双向链表c 带头结点的双向循环链表d 单循 环链表 4 一个栈的输入序列为 1234 5 则下列序列中不可能是栈的输出序列 是 d a 12345b 54321c 23451 d 41235 5 在一个长度为 n 的顺序存储线性表中 向第 i 个元素 1 i n 之 前插入一个新元素时 需要从后向前依次后移b 个元素 a n ib n i 1c n i 1d I 6 在一棵非空二叉树的中序遍历序列中 根结点的右边 a a 只有右子树上的所有结点b 只有右子树上的部分结点 c 只有左子树上的所有结点d 只有左子树上的部分结点 7 在一个有向图中 所有顶点的入度之和等于所有顶点的出度之和 的 b 倍 a 1 2b 1c 2d 4 8 顺序查找法适合于存储结构为 b 的线性表 a 顺序存储b 顺序存储或链式存储c 链式存储 d 索引存储 9 深度为 5 的二叉树至多有 c 个结点 a 16b 32c 31d 10 10 若待排序列已按关键字非递减有序排列 则 a 算法的比较次 数最少 a 直接插入排序b 快速排序c 归并排序 d 选择排序 二 判断题 每题 1 分 共 10 分 1 设指针 P 指向单链表中一个结点 则语句序列 q P next q q next 将删除一个结点 2 栈和 队列都是操作受限的线性表 3 当一个二叉树的结点数 n 2k k 是大于 0 的整数 时 这个二叉树才有可能是满二叉树 4 线性表的长度是线性表所占用的存储空间的大小 5 如果两 个串含有相同的字符 则说它们相等 6 一个无向图中 最 多可有 n n 1 2 条边 7 若无向图以顶点 1 为起点的深度 优先遍历的序列唯一 则表明这个图中不存在环 8 只要是 有序表都可以采用折半查找法进行查找 9 图 G 的一棵最 小代价生成树的代价未必小于 G 的其它任何生成树的代价 10 在带头结点的单循环链表中 任一结点的后继指针均不空 三 填空 每题 2 分 共 20 分 1 在单链表中 删除指针 P 所指结点的后面一个结点的语句序列为 P next P next next 2 已知一个栈的输入 序列为 1 2 3 n 则其输出的第一个元素为 n 的输出序列的个 数是 1 3 对 4 5 6 7 8 3 2 1 进行快速排序 则第 一趟排序结束时的状态是 1 2 3 4 8 7 6 5 5 队列的特性是 先进先出 4 以 4 5 6 7 8 作为叶子结点的数值构造赫夫曼树 则其带 权路径长度是 69 6 已知二叉树有 50 个叶子结点 则该二叉树度为 2 的结点数是 49 7 在按关键字递增的数组 A 1 20 中 按折半查找方法进行查找时 查找元素 A 5 的比较次数是 2 8 在一个大顶堆中 堆 顶结点的值是所有结点中的 最大值 9 每次从无序表中取出一个元素 把它插入到有序表中的适当位置 此种排序方法叫做 插入 排序 10 有 3 个结点的二叉树的不同形态有 5 种 四 解答题 前 3 题每题 8 分 第四题 12 分 共 36 分 1 将下面关键字序列建成一个初始大顶堆 70 12 20 31 5 44 66 61 200 30 80 初始大顶堆 2 已知上面二叉排序树的各结点的值依次为 1 9 请标出各结点的 值 3 一棵二叉树的先序序列为 ABCDEFGH 中序序列为 CBEDAGFH 试构造此二叉树 4 对右边所示的图 完成下列操作 求每个顶点的入度和出度 画出相应的 邻接矩阵 画出相应的邻接表 画出相应的 逆邻接表 写出采用邻接表存储时 从 2 出发的深度优先搜索的顶点访问序列 4 1 每个顶点的入 出度如下表所示 顶点入度出度 130