数据结构试题四套[1][1].doc.pdf

A 卷 选择 共 20 分 每题只有一个正确答案 每题 2 分 1 数据结构是 D A 一种数据类型 B 数据的存储结构 C 一组性质相同的数据元素的集合 D 相互之间存在一种或多种特定关系的数据元素的集合 2 若进栈序列为 1 2 3 4 5 6 且进栈和出栈可以穿插进行 则可能出现的出栈序列为 B A 3 2 6 1 4 5B 3 4 2 1 6 5 C 1 2 5 3 4 6D 5 6 4 2 3 1 3 求单链表中当前结点的后继和前驱的时间复杂度分别是 C A O n 和 O 1 B O 1 和 O 1 C O 1 和 O n D O n 和 O n 4 已知指针 p 和 q 分别指向某单链表中第一个结点和最后一个结点 假设指针 s 指向另一个单链表中 某个结点 则在 s 所指结点之后插入上述链表应执行的语句为 A A q next s next s next p B s next p q next s next C p next s next s next q D s next q p next s next 5 已知函数 Sub s i j 的功能是返回串 s 中从第 i 个字符起长度为 j 的子串 函数 Scopy s t 的功能 为复制串 t 到 s 若字符串 S SCIENCESTUDY 则调用函数 Scopy S Sub S 1 7 后得到 C A P SCIENCE B P STUDY C S SCIENCE D S STUDY 6 对 N 个元素的表做顺序查找时 若查找每个元素的概率相同 则平均查找长度为 A A N 1 2 B N 2 C N D 1 N N 2 7 下列陈述中正确的是 D A 二叉树是度为 2 的有序树 B 二叉树中结点只有一个孩子时无左右之分 C 二叉树中必有度为 2 的结点 D 二叉树中最多只有两棵子树 并且有左右之分 8 设有一个 10 阶的对称矩阵 A 采用下三角压缩存储方式 以行序为主存储 a11 为第一元素 其存 储地址为 1 每个元素占一个地址空间 则 a85 的地址为 B A 13B 33C 18D 40 9 设循环队列中数组的下标范围是 1 n 其头尾指针分别为 f 和 r 则其元素个数为 D A r fB r f 1C r f mod n 1D r f n mod n 10 下列关键字序列中 构成小根堆的是 D A 84 46 62 41 28 58 15 37 B 84 62 58 46 41 37 28 15 C 15 28 46 37 84 41 58 62 D 15 28 46 37 84 58 62 41 二 填空题 共 20 分 每空 2 分 1 链式存储结构的特点是借助 指针 来表示数据元素之间的逻辑关系 2 假设带头结点的非空单循环链表中仅设尾指针 L 则在第 1 个数据元素结点之前插入指针 s 所指结点 的语句依次是 s next L next next L next next s 3 无表头结点的链队列 Q 为空的条件是 Q front Q rear Null 4 不含任何字符的串称为 空串 5 表达式 a b c d f g 的后缀表达式为 ab cd f g 6 如果排序过程 具有相同关键字的待排记录的相对位置没有发生改变 称该排序方法是稳定的 7 由权值分别为 4 6 2 3 的叶子生成一个哈夫曼树 它的带权路径长度为 29 8 从空树起 依次插入关键字 73 1l 35 48 52 27 66 构造所得的二叉排序树 在等概率查找的 假设下 查找成功时的平均查找长度为 25 7 9 判断线索二叉树中某结点指针 P 所指结点有左孩子的条件是 P Ltag 0 三 应用题 共 50 分 1 简述顺序表和链表存储方式的特点 6 分 2 1 已知一个二叉树如图 1 所示 写出该二叉树的先序 中序 后序遍历序列 3 分 2 把图 1 对应的二叉树转换为所对应的森林 3 分 3 已知一棵二叉树的中序遍历序列为 dfebagc 先序遍历序列为 abdefcg 请画出这棵二叉树 4 分 图 1 3 对一组关键字 26 85 37 20 62 13 29 15 18 采用快速排序方法进行排序 用第一个关键 字作枢轴 请写出每趟排序结果 只写每趟结果 8 分 4 依次输入序列 62 68 30 61 25 14 53 47 90 84 中元素 生成一棵二插排序树 1 画出生成后的二叉排序树 3 分 2 画出删除结点 30 后的二叉排序树 4 分 5 画出右图所示二叉树的中序线索链表的存储表示 带头结点 7 分 6 利用广义表的 head 和 tail 操作 可从广义表 L a b c d 中分解得到原子 c 其操作表达 式为 head head tail L 分别写出从下列广义表中分解得到 b 的操作表达式 1 L1 a b c d 2 L2 a b c d 6 分 7 求出下图的一棵最小生成树试画出构造过程 表明你使用的算法以及起始顶点 6 分 四 算法设计 任选一题 共 10 分 1 假设以带头结点的单链表表示非递减有序表 设计一算法删除表中所有值大于 min 且小于 max 假 设 minnext L next next L next next s 3 Q front Q rear Null 4 空串 5 ab cd f g 6 具有相同关键字的待排记录的相对位置没有发生改变 7 29 8 25 7 9 P Ltag 0 三 应用题 共 50 分 1 共 6 分 答 顺序存储 用地址连续的地址表示逻辑上的相邻关系 可以实现随机存取 但进 行插入删除操作时需要移动大量元素 适合于查询操作比较多时 3 分 链式存储 用随机的不连续的存储地址存储线性表 通过指针来表示逻辑上的相邻关系 不能随机存储 要找到链表里面某一元素时必须从头指针开始 依次访问链表 插入删除操作时只需修改指针 不用移动 元素 适合插入 删除操作比较多时 3 分 评分细则 两者定义 2 分 优点 2 分 缺点 2 分 2 共 10 分 1 先 a b d g f h c e中 d f g h b a c e后 f h g d b e c a 评分细则 一个遍历序列 1 分 2 评分细则 一个图 1 分 3 评分细则 4 分 3 共 8 分 第一趟 181513202662293785 4 分 第二趟 131518202637296285 2 分 第三趟 131518202629376285 2 分 评分细则 第一趟 4 分 第二趟 第三趟各 2 分 4 共 7 分 1 2 或者 2 评分细则 1 3 分 2 4 分 5 共 7 分 评分细则 整体框架 2 分 标志域 2 分 线索 3 分 6 共 6 分 1 head tail L1 2 head head tail head L2 评分细则 1 3 分 2 3 分 7 共 6 分 答案一 答案二 答案三 评分细则 1 2 3 4 步 2 分 5 6 步 2 分 7 步 2 分 四 算法设计 任选一题 共 10 分 1 共 10 分 Status Delete Between LinkList 2 分 While p next datanext 3 分 if p next q p next While q datanext free k 3 分 p next q 2 分 2 共 10 分 int LeafCount Bitree BiTree T if T return 0 3 分 else if T lch 3 分 else return LeafCount Bitree T lch LeafCount Bitree T rch 4 分 B 卷 一 选择 共 20 分 每题只有一个正确答案 每题 2 分 1 一个算法应该是 B A 程序B 问题求解步骤的描述 C 要满足五个基本特性D A 和 C 2 下面程序段的时间复杂度为 D s 0 for i 1 i n i for j 1 jnext s next s next p B s next p q next s next C p next s next s next q D s next q p next s next 4 已知循环队列的存储空间为数组 data 21 且当前队列的头指针和尾指针的值分别为 8 和 3 则该队 列的当前长度为 C A 5B 6C 16D 17 5 通常将链串的结点大小设置为大于 1 是为了 B A 提高串匹配效率B 提高存储密度 C 便于插入操作D 便于删除操作 6 表头和表尾均为空表的广义表是 B A B C D 7 设栈的输入序列是 1 2 3 4 则 D 不可能是其出栈序列 A 1 2 4 3 B 2 1 3 4 C 1 4 3 2 D 4 3 1 2 8 用二叉链表表示具有 n 个结点的二叉树时 值为空的指针域的个数为 C A n 1B n C n lD 2n 9 为便于判别有向图中是否存在回路 可借助于 D A 广度优先搜索算法B 最小生成树算法 C 最短路径算法D 拓扑排序算法 10 下列四个序列中 哪一个是堆 C A 75 65 30 15 25 45 20 10B 75 65 45 10 30 25 20 15 C 75 45 65 30 15 25 20 10D 75 45 65 10 25 30 20 15 二 填空题 共 20 分 每空 2 分 1 线性表 L a1 a2 an 含有 n 个元素 用数组表示 假定删除表中任一元素的概率相同 则删除 一个元素平均需要移动元素的个数是 n 1 2 2 操作受限后进先出的线性表是栈 3 在目标串 S 0 n 1 xwxxyxy 中 T xy 则 Index S T 0 的执行结果是3 4 由权值分别为 4 6 2 8 的叶子生成一个哈夫曼树 它的带权路径长度为38 5 三元组表适合存储稀疏矩阵 6 从空树起 依次插入关键字 73 81 35 48 52 27 66 和构造所得的二叉排序树 在等概率查找 的假设下 查找成功时的平均查找长度为20 7 7 在折半查找中 要求被查找的元素必须采用顺序存储结构 8 产生冲突现象的两个关键字称为该散列函数的同义词 9 若采用孩子兄弟链表作为树的存储结构 则树的后根遍历应对应采用二叉树的中根遍历 10 对一个栈 S 栈底指针用 base 表示 栈顶指针用 top 表示 数组的长度为 L 则栈满的条件为 s top s base L 三 应用题 共 50 分 1 简述顺序表和链表存储方式的特点 5 分 2 1 已知一个二叉树如图 1 所示 写出该二叉树的先序 中序 后序遍历序列 3 分 2 把图 1 对应的二叉树转换为所对应的森林 3 分 3 已知一棵二叉树的中序遍历序列为 dfebagc 先序遍历序列为 abdefcg 请画出这棵二叉树 4 分 3 画出图 2 所示二叉树的中序线索链表的存储表示 带头结点 5 分 4 已知带权图的邻接表如下所示 其中边表结点的结构为 8 分 依此邻接表从顶点 C 出发进行深度优先遍历 1 写出依次从顶点 C 出发进行的深度优先遍历序列 2 写出依次从顶点 C 出发进行的广度优先遍历序列 5 对一组关键字 26 85 37 10 62 18 29 15 采用快速排序方法进行排序 用第一个关键字作 枢轴 请写出每趟排序结果 只写每趟结果 7 分 6 利用广义表的 head 和 tail 操作 可从广义表 L a b c d 中分解得到原子 c 其操作表达 式为 head head tail L 分别写出从下列广义表中分解得到 b 的操作表达式 1 L1 a b c d 2 L2 a b c d 7 分 7 已知一个无向图如下图所示 要求分别用 Prim 普里姆 假设以 为起点 和 Kruskal 克鲁斯卡尔 算法生成最小树 试画出构造过程 8 分 四 算法设计 10 分 1 假设以带头结点的单链表表示非递减有序表 单链表的类型定义如下 typedef struct node DataType data struct node next LinkNode LinkList 设计一算法使得插入一个数值为 x 的结点后 单链表仍有序 5 分 2 设从键盘输入一整数的序列 a1 a2 a3 an 试编写算法实现 用栈结构存储输入的整数 当 ai 1 时 将 ai 进栈 当 ai 1 时 输出栈顶整数并出栈 算法应对异常情况 入栈满等 给出相应的 信息 注意 算法中直接利用栈的基本操作 如 push pop stackempty stacklength 等 来实现 5 分 B 卷答案 一 选择 每题 2 分 共 20 分 1 5 BDACB6 10 BDCDC 二 填空题 每空 2 分 共 20 分 1 n 1 2 2 操作受限后进先出的线性表 3 3 4 38 5 稀疏 6 20 7 7 顺序 8 同义词 9 中根 10 s top s base L 三 应用题 共 50 分 1 5 分 答 顺序存储 用地址连续的地址表示逻辑上的相邻关系 可以实现随机存取 但进行插入删除操作时需 要移动大量元素 适合于查询操作比较多时 链式存储 用随机的不连续的存储地址存储线性表 通过指针来表示逻辑上的相邻关系 不能随机存 储 要找到链表里面某一元素时必须从头指针开始 依次访问链表 插入删除操作时只需修改指针 不用 移动元素 适合插入 删除操作比较多时 评分细则 两者定义 2 分 优点 2 分 缺点 2 分 2 答 1 先 abdghcef中 dhgbaefc后 hgdbfeca 3 分 2 3 分 3 4 分 3 5 分 答 4 8 分 答 1 C D B A F E 2 C D A B F E 评分细则 1 4 分 2 4 分 5 7 分 答 1 15 18 10 26 62 37 29 85 2 10 15 18 26 29 37 62 85 3 10 15 18 26 29 37 62 85 评分细则 1 2 分 2 2 分 3 3 分 6 7 分 答 1 head tail head L1 2 head head head tail L2 评分细则 1 3 分 2 4 分 7 8 分 答 1 2 3 4 5 1 2 3 4 5 评分细则 Prim 普里姆 和 Kruskal 克鲁斯卡尔 最小树各 4 分 四 算法设计 每题 5 分 共 10 分 1 5 分 void InsertLlist LinkList P L next q L for P S LinkList malloc sizeof LinkNode S data x S next NULL S next P q next S 2 5 分 voidFunction Stack S int a n int i e length for i 0 i StackLength S S base ElemTyp realloc S base S stacksize StackIncrement sizeof ElemType S top S base S stacksize S stacksize S stacksize StackIncrement Push S s i else if StackEmpty Pop S e Printf e C 卷 一 单项选择 共 20 分 每小题 2 分 1 下列关于存储结构的叙述中 正确的是 C A 顺序存储方式只能用于存储线性结构 B 线性表的逻辑顺序与存储顺序总是一致的 C 散列法存储的基本思想是由关键字的值决定数据的存储地址 D 静态链表具有动态链表的优点 它存取表中第 i 个元素的时间与 i 无关 2 在一个长度为 n 的顺序存储线性表中 向第 i 个元素 1 i n 1 之前插入一个新元素时 需要从后 向前依次后移C个元素 A n iB n i 1C n i 1D i 3 设 n 个元素的进栈序列是 a 1 a 2 a 3 a n 出栈序列是 1 2 3 n 若 a 3 1 则 a 1 的值是C A 可能是 2B 一定是 2C 不可能是 2D 不可能是 3 4 设栈 s 和队列 Q 的初始状态为空 元素 b 1 b 2 b 3 b 4 b 5 和 b 6依次通过栈 S 一个元素出栈后即进队列 Q 若 6 个元素出队的序列是 b 2 b 4 b 3 b 6 b 5 b 1 则栈 S 的容量至少应该是A A 3B 4C 5D 其它 5 由权值分别为 3 8 6 2 5 的叶子结点生成一棵哈夫曼树 它的带权路径长度为A A 53B 48C 72D 24 6 如将一棵有 n 个结点的完全二叉树按顺序存放方式 存放在下标编号为 0 1 n 1 的一维数组中 设某结点下标为 k k 0 则其双亲结点的下标是A A k 1 2B k 1 2C k 2D k 1 7 在一棵高度小于 3 的二叉树中 若结点的前序序列为 ABCDEF 则结点的中序序列有可能为B A DCEBAFB CBDAFEC BCDAFED FCADBE 8 在下面几组关键字中 哪个是最小堆 B A 05 13 55 94 17 46 42 B 05 42 13 55 94 17 46 C 05 42 17 94 55 13 46 D 94 42 55 01 17 13 46 9 有数据 53 30 37 12 45 24 96 从空二叉树开始逐个插入数据来形成二叉搜索树 若希望高 度最小 则应选择下面哪个序列输入B A 45 24 53 12 37 96 30B 37 24 12 30 53 45 96 C 12 24 30 37 45 53 96D 30 24 12 37 45 96 53 10 如右图所示 给出由 7 个顶点组成的无向图 从顶点 1 出发 对它进行深度优先遍历可能得到的顶 点序列是A A 1534276B 1347625 C 1354267D 1247653 二 判断题 共 20 分 每题 2 分 1 算法的时间复杂度取决于代码的长度和占用内存的大小 F 2 顺序存储方式只能用于存储线性结构 F 3 可以随机访问任一元素是链表不具有的特点 T 4 顺序队列的队首指针指向的并不是队首元素 T 5 递归工作栈的栈顶记录必定是当前正在执行的工作记录 T 6 树中结点的度是指从根到该结点所经过分支的条数 F 7 AVL 树是高度平衡的二叉树 其平均搜索长度可以保持在 O log 2 n T 8 无向图的邻接矩阵是对称的 有向图的邻接矩阵也可能是对称的 T 9 直接插入排序的关键码比较次数与初始排列有关 T 10 装载因子越大 插入元素时发生冲突的可能性就越大 T 三 应用题 共 36 分 每题 6 分 1 写出下图所示的树的先根遍历序列 并将它转化为二叉树 题 1 图 2 设某带权无向图如图 画出用 Kruskal 算法生成最小生成树每一步的结果 题 2 图题 4 图 题 5 图 3 已知一组元素的排序码为 46 74 16 53 14 26 40 38 86 65 27 34 使之按关键字递 增次序排序时 写出按最左元素作为划分基准的快速排序 第一趟排序后的结果 4 已知 AVL 树如图 现向其中依次插入关键码 59 和 65 分别画出每一步插入后 AVL 树的形态 若有旋 转 说明旋转的类型 5 试对图所示的 AOE 网络 1 求每个活动的最早开始时间 e 和最迟开始时间 l 2 确定哪些活动是关键活动 6 设散列表为 HT 13 散列函数为 H key key 13 用闭散列法解决冲突 对下列关键码序列 12 23 45 57 20 3 78 31 15 36 造表 采用线性探查法寻找下一个空位 画出相应的散列表 并计算等 概率下查找成功的平均搜索长度和搜索不成功的平均搜索长度 四 算法题 共 24 分 1 程序填空 完善起泡排序算法 6 分 template void BubbleSort Type a int n int pass 1 exchange 1 while pass pass i if a i 1 a i swap a i 1 a i 2 设有一带表头结点的单链表 first 是指向其表头结点的指针 请写出计算单链表长度 Length 的算 法 已知单链表的结点类以及 first 定义如下 8 分 template class ListNode private Type data 数据域 ListNode link 链指针域 ListNode first 3 试以二叉链表作存储结构 编写算法统计二叉树中的叶子结点的个数 要求用中序遍历的思想实现 10 分 C 卷答案 一 单项选择题 共 20 分 每小题 2 分 1 5 CCCAA6 10 ABBBA 二 判断题 共 20 分 每小题 2 分 1 5 6 10 三 应用题 共 36 分 每小题 6 分 1 先根序列 ABECFD 题 1 图题 2 图 2 3 38341627142640 46 86655374 4 题 4 图 5 按拓扑有序的顺序计算各个顶点的最早可能开始时间 Ve 和最迟允许开始时间 Vl 然后再计算各 个活动的最早可能开始时间 e 和最迟允许开始时间 l 根据 l e 0 来确定关键活动 从而确定关键 路径 此工程的关键路径为 6 ASLsucc 1 123456 Ve01915293843 Vl01915373843 e00151919152938 l170152719273738 l e1700801280 0123456789 10 11 12 Key7815 357 45 20 3123 36 12 成功时的比较次数1111114121 不成功时的比较次数2132154321543 1 1 1 1 1 4 1 2 1 10 1 4 ASLunsucc 2 1 3 2 1 5 4 3 2 1 5 4 3 13 36 13 四 算法题 共 24 分 1 6 分 exchange 1 pass 2 8 分 template int List Length const ListNode p first link int count 0 while p Null p p Link count return count 3 10 分 template void BinTree countLeaf BinTreeNode root int if root leftChild NULL countLeaf root rightChild D 卷 一 单项选择 共 20 分 每小题 2 分 1 算法与程序的主要区别在于算法必须满足 D A 先进性B 正确性C 高效性D 有穷性 2 若算法中语句频度之和为 T n 123n n 2 45 6nlog 2 n 7891 则算法的时间复杂度为 D A O 1 B O n C O nlog 2 n D O n 2 3 若长度为 n 的无序线性表采用顺序存储结构 在其中插入某个元素的平均移动次数为 C A nB n 1 2C n 2D n 1 2 4 在单链表中 若要在指针 p 所指结点后面插入一个由指针 q 所指结点 设 next 域存放指针 则执行的 语句系列是 B A p next q next q p B q next p next p next q C p next q next q next p D p next q q next p next 5 假设一个循环顺序队列的队首和队尾指针分别为 front 和 rear 存储空间大小为 n 则判断队空的条 件是 B A front 1 n r earB front r ear C rear 1 n f rontD front 0 6 如果将一棵有 n 个结点的完全二叉树按层次遍历次序 存放在下标编号为 0 1 n 1 的一维数组 中 设某结点下标为 k k 0 如果其左孩子存在 则其左孩子结点的下标是 C A 2k 1B 2kC 2k 1D 2k 2 7 若编号1 7的7个数按照5274163 的次序进栈 进栈的中间可以出栈 则出栈序列不可能是 A A 5217463B 5714623C 2471536D 5143672 8 用整数5 7 3 6 4作为五个树叶的权值 可以构造一棵带权路径长度值为 C 的Huffman树 A 78B 62C 57D 25 9 由某树等价转换得到的二叉树称为该树对应的二叉树 则以下结论正确的是 A A 树的先根遍历序列与其对应二叉树的前序遍历序列相同 B 树的先根遍历序列与其对应二叉树的中序遍历序列相同 C 树的后根遍历序列与其对应二叉树的前序遍历序列相同 D 树的后根遍历序列与其对应二叉树的后序遍历序列相同 10 在一棵空 AVL 树中依次插入关键字 55 71 92 6 38 69 12 16 56 15 则插入过程中使得 树产生旋转的关键码个数是 A A 5B 7C 8D 10 二 判断题 共 20 分 每题 2 分 1 线性结构的基本特征是每个结点至多只有一个直接前驱和一个直接后继 F 2 队列的特点是先进先出 优先级队列也不例外 同样也是先进先出 T 3 在栈为空的情况下 不能作出栈操作 否则会产生下溢 T 4 二叉树中每个结点的两棵子树的高度差不大于 1 F 5 广义表 2 2 的表尾是 2 T 6 如果树用二叉树链表表示 则判断某个结点是不是树叶的条件是该结点左 右两个指针域的值都为空 F 7 若邻接表中有奇数个边结点 则该图一定为有向图 T 8 9 阶 B 树中 除根以外的任何一个非叶子结点中的关键字数目均在 5 9 之间 F 9 直接插入排序是一种稳定的排序方法 T 10 散列表的装载因子表明表的装满程度 它与预设的最大桶长有关 F 三 应用题 共 36 分 第 1 4 题每题 6 分 第 5 题 5 分 第 6 题 7 分 1 求广义表 L a b c d e f g h 的长度和深度 并利用广义表的求表头操作和求表尾操作 将原子 d 分离出来 2 写出将序列 20 71 44 62 61 57 16 85 77 调为最大堆的全过程 3 某二叉树的中序遍历序列为 ADEBCGFHIJ 后序遍历序列为 ADCBGEIHJF 1 还原该二叉树 2 写出该二叉树的前序遍历序列 4 已知一组元素的关键码为 67 6 38 11 9 41 52 27 50 12 89 56 利用 Shell 排序使 之 按关键字递增次序排序 设排序间隔分别是 5 3 1 依次写出各趟排序后的结果 5 设某带权无向图如右图 画出用 Prim 算法 从顶点 A 开始生成最小生成树的 每一步结果 题 5 图 6 设散列表长 13 散列函数为 H key key 13 对关键码序列 93 63 81 78 17 8 85 7 30 22 造表 用线性探测法解决冲突 画出相应的散列表 并计算等概 率下查找成功时的平均查找长度 四 算法题 共 24 分 1 在有头结点双向循环链表中 设前驱指针为 prior 后继指针为 next 若要删除并释放指针 p 所指结 点的 前驱结点 非头结点 写出该过程执行的完整语句序列 2 设有二个同类型数组 a 和 b 编写算法将数组 a 的前 n 个元素 即 a 0 a 1 a n 2 a n 1 复制到 b 数组中 使得 b 数组的前 n 个