南京理工大学紫金学院《数据结构》试卷_高清数位重置版

文档鉴赏 一 选择题 1 树最适合用来表示 A 有序数据B 无序数据元素 C 元素之间具有分支层次关系的数据D 元素之间无联系的数据 2 一个堆是一棵 二叉树 A 普通B 排序C 满D 完全 3 设哈夫曼树中的叶子结点总数为m 若用二叉链表作为存储结构 则该哈夫曼树中共有 个空指针域 A 2m 1B 2m C 2m 1D 4m 4 线性结构的顺序存储结构是一种 的存储结构 A 随机存取B 顺序存取C 索引存取D 散列存取 5 一下是平衡二叉树的是 A B C D 6 对图进行广度优先遍历时 通常采用 来实现算法 A 栈B 队列C 树D 图 文档鉴赏 7 有一个有序表为 8 15 20 22 32 41 45 62 75 77 82 85 97 当二分查找值为22 的数据时要进行 次比较 A 2B 3C 4D 5 8 设单链表中结点的结构为 data next 已知指针n所指结点不是尾结点 若在指针p所指结点之后插入结点s 则应执行下列哪 一个操作 A s next p p next s B s next p next p next s C s next p next p s D p next s s next p 9 由权值分别为11 8 6 2 5的叶子结点生成一棵哈夫曼树 它的带权路径长度为 A 24B 71C 48D 53 10 无向图G V E 其中V a b c d e f E a b a c a e b e c f f d e d 对该图进行深度优先遍历 下面不能得到的序列是 A acfdebB aebdfcC aedfcbD abecdf 11 设有广义表D a b D 其长度为 深度为 A B 3C 2D 5 12 线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素 则采用 存储方式最节省运算时间 A 单链表B 仅有头指针的单循环链表C 双链表D 仅有头指针的单循环链表 13 在有n个结点的二叉链表中 值为非空的链域的个数为 文档鉴赏 A n 1B 2n 1C n 1D 2n 1 14 稀疏矩阵一般的压缩存储方法有两种 即 A 二维数组和三维数组B 三元组与散列C 三元组与十字链表 D 散列和十字链表 15 以下不是堆的序列是 A 100 85 98 77 80 60 82 40 20 10 66 B 100 98 85 82 80 77 66 60 40 20 10 C 10 20 40 60 66 77 80 82 85 98 100 D 100 85 40 77 80 60 66 98 82 10 20 16 一个栈的入栈序列是 a b c d e 则栈的不可能输出序列是 A edcbaB decbaC dceadD abcde 二 填空题 1 下面程序段的时间复杂度是 i 1 While i n i i 5 2 在一个单链表中 要删除某一个结点 必须找到该结点的 结点 3 在一个长度为n的顺序表中 在第1个元素 1 i n 1 之前插入一个新元素时须向后移动 个元素 4 有一个10阶对称矩阵A 采用压缩存储方式 以行为主存储 且LOC A 0 0 1 则A 8 5 的地址是 文档鉴赏 5 设在一棵二叉树中 度为0的结点个数为8 度为2的结点个数为 6 设二叉树结点的先根序列为ABEDCFGH 中根序列为EDBAFCHG 则二叉树中叶子结点 是 7 求最小生成树算法有Prim算法和Kruskal算法两种 算法适合稠密图 算法适合稀疏图 8 数据表中有10000个元素 如果仅要求求出其中最大的10个元素 则采用 是 算法最节省时间 9 循环队列中队满条件为 三 综合题 1 画出广义表LS e a b c d 的头尾链表存储结构 2 已知一棵二叉树的先序序列与中序序列分别为 ABCDEFGHI和BCAEDGHFI 1 给出该二叉树的后序遍历序列 2 画出该二叉树的带头结点的中序线索二叉树 3 将该二叉树转换成森林 3 设有无向图G 要求使用Prim算法构造以顶点C为起点的最小生成树 同时 写出构造最 小生成树的每一步过程 无需注明权值 D C A B 1 5 5 56 6 4 23 E F 6 第3题图 V5 V4 V1 V0 V2 V3 第4题图 6 7 4 8 9 10 3 20 文档鉴赏 4 根据下图所示的AOE网 请回答以下问题 1 求这个工程最早可能在什么时间结束 2 求每个活动的最早开始时间和最迟开始时间 3 确定哪些活动是关键活动 活动 最早发 生时间 最迟发 生时间 5 输入一个正整数序列 23 32 16 14 42 71 57 28 55 19 12 50 1 构造一棵二叉排序树 只需最后结果图 2 画出构造的一棵平衡二叉树 只需最后结果图 3 HASH表表长为12 HASH函数为H key key 11 试用线性探测再散列解决冲突的方法构造哈希表 01234567891011 文档鉴赏 6 设待排序的关键字序列为 27 46 5 18 16 51 32 26 分别使用以下排序方法进行排序 写出题目所给定趟数的结果 1 第三趟直接插入排序的结果 2 第一趟希尔排序的结果 增量为3 3 第二趟归并排序 4 第一趟快速排序 四 算法设计题 有一个带头结点的单链表head 其Ele