电大数据结构(本)期末考试2010.1.0.pdf

试卷代号 1 2 5 2座位号 口口 中 央 广 播电 视 大 学2 0 0 9 2 0 1 0 学 年 度 第一 学 期 开 放 本 科 期 末 考 试 数据结构 本 试题 2 0 1 0 年 1 月 题号 四总分 分数 得分评卷人 一 单项选择题 每小题 2 分 共 3 0 分 1 一种逻辑结构 存储结构 A 可以有不同的B 只能有唯一的 C 的数据元素在计算机中的表示称为D 的数据元素之间的关系称为 2 以下说法中不正确的是 A 双向循环链表中每个结点需要包含两个指针域 B 已知单向链表中任一结点的指针就能访问到链表中每个结点 C 顺序存储的线性链表是可以随机访问的 D 单向循环链表中尾结点的指针域中存放的是头指针 3 双向循环链表结点的数据类型为 s t r u c t n o d e i n t d a t a s t r u c t n o d e n e x t 指向 直 接后 继 s t r u c t n o d e p r i o r 设 p 指向表中某一结点 要显示p 所指结点的直接前驱结点的数据元素 可用操作 A p r i n t f 0 o d p 一 n e x t 一 d a t a B p r in t d p 一 p r i o r 一 d a t a C p r in t 0 o d p 一 p r io r n e x t D p r i n t f o o d p 一 d a t a 1 36 5 4 一个栈的进栈序列是e f g h 则栈的不可能的出 栈序列是 进出 栈操作可以交替 进行 A h g f e C f g e h B g f e h D e h f g 5 设t o p 是一个链栈的栈顶指针 栈中每个结点由一个数据域d a t a 和指针域n e x t 组成 设用x 接收栈顶元素 则取栈顶元素的操作为 t o p 一 d a t a x t o p t o p 一 n e x t A B C x t o p 一 d a t a D x t o p 一 d a t a t o p t o p 一 n e x t 6 以下说法不正确的是 A 栈的特点是后进先出 B 队列的特点是先进先出 C 栈的删除操作在栈底进行 插人操作在栈顶进行 D 队列的插入操作在队尾进行 删除操作在队头进行 7 c h a r p p S t r C a t A B D A B C P r i n t f s p 的显示结果为 A 一 1 B AB DABC C AB D 1 8 深度为5 的满二叉树至多有 A 4 0 个结点 根结点为第一层 B 31 C 3 4 D 3 5 9 已知一个图的所有顶点的度数之和为 m 则该 图的边数为 A 2 m C 2 m 1 B m D m 2 1 3 6 6 1 0 以下说法不正确的是 A 连通图G的生成树一定是唯一的 B 连通图G一定存在生成树 C 连通图G的生成树中一定要包含G的所有顶点 D 连通图G的生成树一定是连通而且不包含回路 1 1 有序 表为 1 2 4 6 1 0 1 8 召 0 3 2 用课 本中 折 半查找 算法查找 值1 8 经 次比 较后成功查到 A 3 B 2 C 4 D 5 1 2 在排序过程中 可以通过某一趟排序的相关操作所提供的信息 判断序列是否已经排 好序 从而可以提前结束排序过程的排序算法是 A 冒泡 B 选择 C 直接插人 D 折半插人 1 3 用折半查找法 对长度为 1 2 的有序的线性表进行查找 最坏情况下要进行 次 元素间的比较 A 4 B 3 C 5 D 6 1 4 如图若从顶点a 出发按深度优先搜索法进行遍历 则可能得到的顶点序列为 A a c f g e d b B a e d b g f c C a c f e b d g D a e c b d g f 1 5 一棵哈夫曼树总共有2 5 个结点 该树共有 个非叶结点 非终端结点 A 1 2 B 1 3 C 1 4 D 1 5 1 3 6 7 得分评卷人 二 填空题 每小题2 分 共2 4 分 1 结构中的 元素之间存在多对多的关系称为结构 2 设有一个单向 循环链表 结点的指针域为n e x t 头指针为h e a d 指针P 指向表中某结 点 若 逻 辑 表 达 式的 结 果 为 真 则A 所 指 结 点 为 尾 结 点 3 设有一个链栈 栈顶指针为h s 现有一个s 所指向的结点要人栈 则可执行操作s n e x t h s 4 在一个链队中 f 和r 分别为队头和队尾指针 队结点的 指针域为n e x t s 指向 一个要人 队的结点 则人队操作为 5 循环队列的最大存储空间为 Ma x S iz e 6 采用少用一个元素空间以有效地判断栈空 或栈满 若队头指针f r o n t 4 当队尾指针r e a r 时队满 队列中共有 个元素 6 程序段 c h a r s a B c D n 0 wh i l e s 0 i f S a NUL L b r e a k R e t u r n 5 2 以下函数为链队列的出队操作 链队列带有头结点 出队结点厂的数据域的值由x 返 回 f r o n t r e a r 分别 是 链队 列的 队 头 队 尾 指针 s t r u c t n o d e E l e rn T y p e d a t a s t r u c t n o d e n e x t s t r u c t n o d e f r o n t r e a r E l e rn T y p e O u t Q u e u e 川 E l e r n T y p e x i f 1 p r i n t f 队列下溢错误 n e x i t 1 e l s e s t r u c t n o d e p f r o n t 一 n e x t X P 一 d a t a f r o n t 一 n e x t 2 i f p 一 n e x t N U L L r e a r f r o n t f r e e p 3 1 37 0 试卷代号 1 2 5 2 中 央广播电 视大学2 0 0 9 2 0 1 0 学年度第一学期 开放本科 期末考试 数据结构 本 试题答案及评分标准 供参考 2 0 1 0 年 1 月 一 单项选择题 每小题 2 分 共3 0 分 1 A2 B3 B4 D5 C 6 C7 B 8 B9 D1 0 A 1 1 B 1 2 A1 3 A1 4 B1 5 A 二 填空题 每题 2 分 共 2 4 分 1 图状 2 p 一 n e x t h e a d 3 h s s 4 r 一 n e x t s r s 5 3 5 6 2 7 1 0 8 深度优先广度优先 9 图状 网状 1 0 2 n 一 1 n 顺序存储链式存储 1 2 相等 1 371 三 综合应用题 每小题1 0 分 共3 0 分 1 1 2 e d b c a 3 e l a 2 d 二3 c 4 b 5 2 0 2 5 6 7 8 9 1 0 1 7 1 8 1 9 2 1 3