电大资源网1252《数据结构本b》国家开放大学历届试题2019年1月含答案.pdf

试卷代号 1252座位号E口 国家开放大学 中央广播电视大学 2018年秋季学期 开放本科 期末考试 数据结构 本 试题 2019年1月 问封一 二i二斗引主主 A acebdf B a巳cbfd C aecbdf D acefdb 2 结构中的元素之间存在一对多的关系是 A 集合B 线性结构 c 树形结构D 图状结构 3 设有一个长度为18的顺序表 要在第4个元素之前插入1个元素 也就是插入元素作 为新表的第4个元素 则移动元素个数为 A 15 C 5 B 16 D 4 615 提醒 电大资源网已将该科目2010年到2019年1月的历届试题 整合 汇总 去重复 按字母排版 形成题库 方便大家复习 4 一个不带头结点的单循环链表 尾指针为rear 在链表中插入一个s所指向的新结点 并作为新的尾结点 可执行 A rear一 next 5 5一 next rear next rear s B rear一 next s一 next rear s C s一 next rear一 nextrear一 next s一 nextrear s D s一 next rear一 nextrear一 next s rear s 5 元素a b c d按顺序依次进擒 则该拢的不可能输出序列是 替进行 进找出钱可以交 A c b a d C 日 c b d B d c b a D d c a b 6 在一个钱顶指针为top的链找中进行出钱操作 用变量x保存钱顶元素的值 则执行 A X top一 data top top一 next B X top一 data C top top一 next X top一 data D top top一 next x data 7 设有一个18阶的对称矩阵A 采用压缩存储的方式 将其下三角部分以行序为主序存 储到一维数组B中 数组下标从1开始 则矩阵中alO 8元素对应于数组中第 矩阵中的第1个元素是a1 1 A 51 C 52 B 53 D 54 号元素 8 一棵采用链式存储的二叉树中 共有n个指针域被有效使用 即指针域为非空 该二 叉树有 个指针域为空 A n 1 C n 1 B n D n十2 9 在一棵二叉树中 若编号为9的结点存在右孩子 则右孩子的顺序编号为 A 18 C 15 B 16 D 19 10 设一棵晗夫曼树共有15个非叶结点 则该树总共有 616 A 29 C 31 B 27 D 28 个结点 提醒 电大资源网已将该科目2010年到2019年1月的历届试题 整合 汇总 去重复 按字母排版 形成题库 方便大家复习 E分 附人 二 填空题 每小题2分 共24分 11 在n个整数中求最大数的算法中 其基本操作是一一一一一一一一一 12 设有一个长度为20的顺序表 要删除第5个元素 则最少要移动元素的个数为一一一一 13 在双向链表中 要删除p所指的结点 其中所用的一条语句句一 prior 一 next p 一 next 的功能是 使P所指结点的直接前驱的右指针指向 14 设有一个头指针为head的单向链表 p指向链表中的某结点 若要使该链表成为单向 循环链表 可用语句while p一 next NULL 和p一 next head 15 在一个链队中 设front和rear分别为队头和队尾指针 则s所指结点 数据域已赋 值 的入队操作为s一 next NULL 和rear s 16 字符串a1 heijing a2 hef a3 heifang飞a4 hefi 中最小的是一一一一一 17 拢的特点之一是z元素进 出钱的次序是z后进一一一 18 在对10个记录的序列04 30 10 7 22 13 66 85 47 58 进行直接插入排序时 当把第 6个记录13插入到有序表时 为寻找插入位置 元素间需比较一一一一次 由小到大排列 19 18个元素进行冒泡法排序 通常需要进行17趟冒泡 其中第10趟冒泡共需要进行 一一一一次元素间的比较 20 一棵有15个结点的哈夫曼树 采用链式结构存储 该树结构中有一一一一个叶结点 21 广义表的仙 a b d c e 仆 j 深度是一一一一 22 序列4 2 7 9 5 3 8 6采用归并排序算法 升序 经一趟归并后 序列的结 果为 三 综合题 每小题6分 共30分 23 1 已知某二叉树的后序遍历序列是febch 给出该二叉树的根结点 又该二叉树的中 序遍历序列是fbehc 分别给出该二叉树的左 右子树的结点 2 画出上述二叉树 若上述二叉树的各个结点的字特分别代表不同的整数 其中没有相 等的 并恰好使该树成为一棵二叉排序树 试给出h b c e的大小关系 617 提醒 电大资源网已将该科目2010年到2019年1月的历届试题 整合 汇总 去重复 按字母排版 形成题库 方便大家复习 24 设查找表为 1 2 3 4 5 6 7 8 9 10 11 1 画出对上述查找表进行折半查找所对应的判定树 树中结点用数值表示 2 说明成功查找到元素5 9各需要经过多少次元素间的比较 3 说明查找不到元素4 2 5 5各需要经过多少次元素间的比较 四 程序填空题 每空2分 共16分 25 以不程序是折半插入排序的算法 618 设待排序的记录序列存放在a l a n 中 以a O 作为辅助工作单元 以下程序是 要把a i 插人到已经有序的序列4日 a i 1 中 void binsort NODE a int n int x i j s k m for Ci 2 i 1 i十十 a O a i x a i key s l j i 1 while s j m 2 if x j 1 k一一 5 a j 1 a O a k 提醒 电大资源网已将该科目2010年到2019年1月的历届试题 整合 汇总 去重复 按字母排版 形成题库 方便大家复习 26 以下程序是中序遍历二叉树的递归算法的程序 完成程序中空格部分 树结构中 左 右指针域分别为left和right 数据域data为字符型 BT指向根结点 void lnorder struct BTreeNode铸BT if BT NULL 1 2 Inorder BT一 right 利用上述程序对右图进行遍历 结果是 3 619 提醒 电大资源网已将该科目2010年到2019年1月的历届试题 整合 汇总 去重复 按字母排版 形成题库 方便大家复习 试卷代号 1252 国家开放大学 中央广播电视大学 2018年秋季学期 开放本科 期末考试 数据结构 本 试题答案及评分标准 供参考 一 单项选择题 每小题3分 共30分 1 C 2 C 6 A 7 B 二 填空题 每题2分 共24分 11 元素间的比较 12 15 13 P所指结点的直接后继 14 P p一 next 15 rear next s 16 a2 17 先出 18 4 19 8 20 8 21 4 22 2 4 7 9 3 5 6 8 3