国家开放大学中央广播电视大学2018 年春季学期期末考试 数据结构.pdf

试卷代号 1252座位号 II 国家开放大学 中央广播电视大学 2018年春季学期 开放本科 期末考试 数据结构 本 试题 2018年7月 题号 一 一 四总分 一一 一一 分数 L一 得分 评卷入 一 单项选择题 每小题3分 共30分 1 数据的存储结构包括数据元素的表示和 A 数据处理的方法B 相关算法 c 数据元素的类型D 数据元素间的关系的表示 2 在一个头指针为head的单向链表中 p指向尾结点 要使该链表成为单向循环链表可 执行 A p head一 next c head一 next p一 next B head一 next p D p一 next head 3 元素111 113 115 117按顺序依次进钱 则该校的不可能输出序列是 进找出 钱可以交替进行 A 117 115 113 111 C 117 115 111 113 4 以下说法正确的是 A 校的特点是先进后出 C 队列的特点是先进后出 B 111 113 115 117 D 113 111 117 115 B 校的特点是先进先出 D 校和队列的特点都是先进后出 5 设有一个20阶的对称矩阵A 第一个元素为a1 1 采用压缩存储的方式 将其下三角 部分以行序为主序存储到一维数组B中 数组下标从1开始 则矩阵中元素a6 2在一维数组 B中的下标是 A 24 B 17 C 16 D 23 703 6 设一棵有2n 1个结点的二叉树 除叶结点外每个结点度数都为2 则该树共有 个叶结点 A n c n十2 B n 1 D n 1 7 已知如图1所示的一个图 若从顶点a出发 按广度优先搜索法进行遍历 则可能得到 的一种顶点序列为 图1 A abecdf c aebcfd B aecbdf D aedfcb 行 执 m只 值 的 素 一兀 顶 钱 存 点保 结 山川量 树 变 序叉用 顺二职 58札 是 BD 层 BD操 UU 一钱 制指出 折品行 厅附进 进叉核 能二链 全的 涮芹 uw Z 旧恨 这 改川即如优 序个指 A 白 H 以醉接剧情 味关链陨76J NE 和 V 牛 UJ 线 AC ACX nu A e top next top data e B top top next e top data C e top data top top一 next D top top next e data 704 得分 评卷人 二 填空题 每小题2分 共24分 11 数组a经初始化chara J English a 7J中存放的是 12 设有串p1 ABADF P2 ABAFD P3 ABADF A P4 ABAF 四个串中最 大的是 13 在一棵二叉树中 若编号为i的结点存在右孩子 则右孩子的顺序编号为 14 设有一个长度为20的顺序表 要插入一个元素 并作为第8个元素 需移动元素的个 数为 15 结构中的数据元素存在多对多的关系称为结构 16 设有一棵深度为4的完全二叉树 第四层上有5个结点 该树共有 根所在结点为第1层 17 一棵二叉树中有n个非叶结点 每一个非叶结点的度数都为2 则该树共有 个叶结点 个结点 18 在对一组记录 55 39 97 22 16 73 65 47 88 进行直接插入排序时 当把第7个记 录65插入到有序表时 为寻找插入位置需比较次 由小到大排序 19 n个元素进行冒泡法排序 第j趟冒泡要进行次元素间的比较 20 一棵有n个叶结点的哈夫曼树 则该树共有个结点 21 中序遍历可得到一个有序序列 22 广义表 a b d e i j k 的长度是 705 4得分 评卷入 三 综合题 每小题中每问6分 共30分 造 构 据 数 各 中 A 口 集 取 次 依 o qL A丛 E AU 哼i qL AU A哇 A口 集 据 数 有 设树 序 抖扫 n叉 棵 2 一组记录的关键字序列为 5 8 6 3 4 7 利用堆排序 堆顶元素是最小元素 的方法 建立初始堆 要求用完全二叉树表示 24 1 以2 3 4 7 8 9作为叶结点的权 构造一棵哈夫曼树 2 给出上述哈夫曼树叶结点的哈夫曼编码 3 一组记录的关键字序列为 37 70 47 29 31 85 利用快速排序 以第一个关键字为分 割元素 给出经过一次划分后结果 从小到大排序 得分 评卷人i 囚 程序填空题 每空2分 共16分 25 设线性表为 6 10 16 的 以下程序用说明结构变量的方法建立单向链表 并输出链 表中各结点中的数据 define NULL 0 void main NODE a b c d 关head 兴p a data 6 b da ta 10 c da ta 16 d da ta 4 头d是尾结点头 head 1 706 a next b next c next 2 铃以上结束建表过程铃 p head 祷p为工作指针 准备输出链表铃 do printf d n 3 4 while 5 26 以下程序是中序遍历二叉树的递归算法的程序 完成程序中空格部分 树结构中左 右指针域分别为left和right 数据域data为字符型 BT指向根结点儿 void lnorder struct BTreeNode兴BT if BT NULL 1 2 Inorder BT一 right 利用上述程序对右图进行遍历 结果是 3 图2 707 试卷代号 1252 国家开放大学 中央广播电视大学 2018年春季学期 开放本科 期未考试 数据结构 本 试题答案及评分标准 供参考 一 单项选择题 每小题3分 共30分 1 D 2 D 3 C 6 B 7 B 8 A 二 填空题 每小题2分 共24分 11 字符串的结束符12 p2 14 13 15 图状 17 n 1 18 3 20 2n 1 21 二叉排序树 三 综合题 每小题中每问6分 共30分 23 1 708 图3 4 A 5 B 9 A 10 C 13 2i 1 16 12 19 n j 22 4 2018年7月 2 3 4 6 8 5 7 24 1 2 2 0000 3 0001 4 001 7 10 8 11 9 01 3 31 29 37 47 70 85