2013~2014学年第1学期南阳理工学院软件学院数据结构课程试卷A卷.pdf

南阳理工学院 2013 2014 学年第 一 学期试卷 A 卷 课程 数据结构 课程号 课程 数据结构 课程号 15041081301504108130 考核方式 闭卷 课程性质 专业必修课 适用对象 12 软工媒体 11 软工 NET 12 网工 12 网安 本科 题号 一 二 三 四 五 总分 复核人 满分 10 30 10 30 20 100 得分 一 填空题 每空 1 分 共 10 分 1 是相互之间存在一种或多种特定关系的数据元素的集合 2 一个算法必须满足 确定性 可行性 输入和输出五个重要的特性 3 链接存储的存储结构所占存储空间分两部分 一部分存放结点值 另一部分存放表示 4 在二叉树的第 i 层上至多有 个结点 5 在一个有向图中 所有顶点的入度之和等于所有顶点的出度之和的 倍 6 具有 n 个顶点的有向图最多有 条边 7 对 n 个元素的表做顺序查找时 若查找每个元素的概率相同 则平均查找长度为 8 又称最优树 是一类带权路径长度最短的树 9 从未排序序列中依次取出元素与已排序序列中的元素进行比较 将其放入已排序序列的 正确位置上的方法 这种排序方法称为 10 若一组记录的排序码为 46 79 56 38 40 84 则利用堆排序的方法建立的初始 堆为 二 选择题 每题 2 分 共 30 分 1 以下数据结构中 是非线性数据结构 A 字符串 B 队 C 栈 D 树 2 一个向量第一个元素的存储地址是 100 每个元素的长度为 2 则第 5 个元素的地址是 A 110 B 108 C 100 D 120 3 在单链表中 要将 s 所指结点插入到 p 所指结点之后 其语句应为 A s next p 1 p next s B p next s s next p next C s next p next p next s next D s next p next p next s 评卷人 得分 评卷人 得分 共 5 页 第1 页 4 线性表 在 情况下适用于使用链式结构实现 A 需经常修改 中的结点值 需不断对 进行删除插入 C 中含有大量的结点 中结点结构复杂 5 串是一种特殊的线性表 其特殊性体现在 A 可以顺序存储 B 数据元素是一个字符 C 可以链式存储 D 数据元素可以是多个字符若 6 串的长度是指 A 串中所含不同字母的个数 B 串中所含字符的个数 C 串中所含不同字符的个数 D 串中所含非空格字符的个数 7 数组 A 0 4 1 3 5 7 中含有元素的个数 A 55 B 45 C 36 D 16 8 广义表 A a b c d e f g 则 Head Tail Head Tail Tail A 的值为 A g B d C c D D 9 把一棵树转换为二叉树后 这棵二叉树的形态是 A 唯一的 有多种 C 有多种 但根结点都没有左孩子 有多种 但根结点都没有右孩子 10 由 3 个结点可以构造出多少种不同的二叉树 A 2 B 3 C 4 D 5 11 线索二叉树是一种 结构 A 逻辑 B 逻辑和存储 C 物理 D 线性 12 利用二叉链表存储树 则根结点的右指针是 A 指向最左孩子 B 指向最右孩子 C 空 D 非空 13 在一个图中 所有顶点的度数之和等于图的边数的 倍 A 1 2 B 1 C 2 D 4 14 对 n 个不同的关键字由小到大进行冒泡排序 在下列 情况下比较的次数最多 A 从小到大排列好的 B 从大到小排列好的 C 元素无序 D 元素基本有序 15 下列关键字序列中 是堆 A 16 72 31 23 94 53 B 94 23 31 72 16 53 C 16 53 23 94 31 72 D 16 23 53 31 94 72 三 判断题 每题 1 分 共 10 分 说明 认为陈述正确的在括号内打 否则在括号内打 1 线性表的链式存储结构优于顺序存储结构 2 线性表中每个元素都有一个且仅有一个直接前驱和直接后继 3 线性表若采用链式存储结构时 要求内存中可用存储单元的地址必须连续 4 栈又称先进先出的线性表 5 深度为 k 的满二叉树含有 2k 1 个结点 评卷人 得分 共 5 页 第2 页 6 遍历二叉树可采用深度优先搜索算法进行 7 空串是由空格构成的串 9 若一组记录的排序码为 46 79 56 38 40 84 则利用快速排序的方法 以第一个 记录为基准得到的一次划分结果为 40 38 46 56 79 84 9 从未排序序列中挑选元素 并将其依次放入已排序序列初始时为空的一端的方法 称为选择排序 10 堆的形状是一棵满二叉树 四 应用题 每题 6 分 共 30 分 1 若让元素 1 2 3 4 5 依次进栈 S 至少写出五种出栈的情况 2 设一棵二叉树的后序序列 FDBGHECA 中序序列 BFDAGEHC 要求 1 画出这棵二叉树 2 写出这棵二叉树的前序序列 评卷人 得分 共 5 页 第3 页 3 已知如下图所示的有向图 请给出 1 每个顶点的入度和出度 2 邻接表 4 采用普里姆算法的构造最小成生树 5 已知一组关键字 19 14 23 1 68 20 84 27 55 11 10 79 哈希函数为 H key key MOD 13 哈 希表长为 m 16 设每个记录的查找概率相等 采用线性探测法处理冲突 构造关键字的散列表 并计算查找成功和查的失败时的平均查的长度 共 5 页 第4 页 五 算法分析与设计 第 1 题 8 分 第 2 题 12 分 共 20 分 1 采用顺序存储表示方法 实现循环队列中的出队和入队算法 2 Please write down the code of binary 折半 search algorithm and Binary insertion sort 折 半插入排序 algorithm 评卷人 得分 共 5 页 第5 页 南阳理工学院课程考试 参考答案与评分标准 考试课程 数据结构 学年学期 2013 2014 1 试卷类型 A 考试时间 120 分钟 一 填空题一 填空题 1 数据结构 或其他结构一种结构也正确 2 有穷性 3 结点间关系的指针 4 2i 1 5 1 6 n n 1 7 n 1 2 8 赫夫曼树 9 插入排序 10 84 79 56 38 40 46 或 38 40 56 79 46 84 二 选择题二 选择题 1 5 DBDBB 6 10 BBDAD 11 15CCCBD 三 判断题三 判断题 1 5 6 10 四 应用题四 应用题 1 12345 1 分 分 54321 1 分 分 12354 1 分 分 32145 1 分 分 32154 1 分 分 答案仅供参考并不唯一 改题时具体分析 2 左右子树各 左右子树各 2 分 分 先序序列 A B D F C E G H 2 分 分 3 4 一条正确边给一条正确边给 1 分 全对给满分 分 全对给满分 5 五 五 算法分析与设计算法分析与设计 1 1 结构体定义 结构体定义 define MAXQSIZE 100 typedef struct QElemType base int front int rear SqQueue 2 分 分 若没写出代码 仅写出算法思想给若没写出代码 仅写出算法思想给 5 分 分 循环队列入队算法 循环队列入队算法 Status EnQueue SqQueue Q base Q rear e Q rear Q rear 1 MAXQSIZE return OK 3 分 分 循环队列出队算法 循环队列出队算法 Status DeQueue SqQueue E Q base Q front Q front Q front 1 MAXQSIZE return OK 3 分 分 2 A 拆半查找算法拆半查找算法 int Search Bin SSTable ST KeyType key int low high mid low 1 high ST length 1 分 分 while low high 1 分 分 mid low high 2 1 分 分 if key ST elem mid key return mid 1 分 分 else if key ST elem mid key high mid 1 1 分 分 else low mid 1 1 分 分 return 0 若没写出代码 仅写出算法思想给若没写出代码 仅写出算法思想给 3 分 分 A 拆半插入排序算法拆半插入排序算法 void BInsertSort Sqlist i L length i L r 0 L r i 1 分 分 low 1 high i 1