试卷代号 : 1 0 1 0 座位号 I II 中央广播电视大学 2 0 1 0-2 0 1 1 学年度第二学期 " 开放本科 " 期末考试 数据结构试题 2011 年 7 月! 题号 I - I 二 三 四! 五! 六 总分 分数 I I I 1 1- I ---1 I 得分 评卷人 一 单项选择题 ( 在括号内填写所选择的标号 每小题 2 分, 共 1 8 分 ) 1. 一种抽象数据类型包括数据和 ( ) 两个部分 A. 数据类型 B. 操作 c. 数据抽象 D. 类型说明 2. 在一个长度为 n 的顺序表的表尾插入一个新元素的时间复杂度为 ( ) f\. OC 1) B. O(n) c. O(n 2 ) D. O(log2n) 3. 已知 L 是带表头附加结点的单链表, 删除第一个元素结点的语句是 ( ) A. L = 1., 一 > l i nk ; c. L->link 一 >link = L. B. L->1ink = L 一 >link 一 >link; D. L 一 >link = L; 4. 在下列广义表中, ( A. E ( a, (b, c) ) C. E(a, b) ) 又是一个线性表 B. E(a,E) D. E(a, (» 5. 在一棵深度为 3 的三叉树中, 最多含有 ( ) 个结点 o 假定树根结点的深度为 1 A. 10 B. 11 c. 12 D. 13 75
6. 向一棵 AVL 树插入元素时, 可能引起对最小不平衡子树的双向旋转的调整过程, 此 时需要修改相关 ( ) 个指针域的值 A. 2 c. 4 B. 3 D. 5 7. 在一个具有 n 个顶点的有向图的邻接矩阵表示中, 删除一条边 < i, j > 需要的时间复杂 度为 ( ) A.O(l) B.O(i) C.O(n) D. 0(n 2 ) 8. 在一棵 B 树中, 当插入一个元素时, 若最终引起树根结点的分裂, 则新树的高度比原 树的高度 ( ) A. 减 1 B. 减 2 c. 增 1 D. 增 2 9. 对存储有 n 个元素的长度为 m 的散列表进行搜索, 平均搜索长度与 ( ) 有关 A. n c. n/m B. m D. n 长 m 得分 评卷人 二 填空题 ( 在横线处填写合适的内容 每小题 2 分, 共 1 4 分 ) 1. 链表只适用于查找 2. 归并排序算法的时间复杂度为 3. 在一个链式队列中, 若队头指针与队尾指针的值相同, 则表示该队列至多有 个结点 o 4. 假定一棵树的广义表表示为 a 仙,c, d 怡, f ), g (h) ), 则结点 f 的层数为 假定 树根结点的层数为 0 0 5. 从一棵二叉搜索树中搜索一个元素时, 若给定值大于根结点的值, 则需要向根的 76 继续搜索
6. 每次从第 i 至第 n 个元素中顺序挑选出一个最小元素, 把它交换到第 i 个位置, 此种排 序方法叫做排序 7. 快速排序在最坏情况下的时间复杂度为 得分 评卷入 1 三 判断题 ( 在每小题后面的括号内打对号 " 飞 I " 表示叙述正确或打叉 号 " x " 表示叙述错误 每小题 2 分, 共 1 4 分 ) 1. 若每次从队列中取出的是具有最高优先权的元素, 则称此队列为优先级队列 ( ) 2. 递归定义的数据结构通常不需要采用递归的算法对其运算 ( ) 3. 当从一个最小堆中删除一个元素时, 需要把堆尾元素填补到堆顶位置, 然后再按条件把它逐层向下调整, 直到调整到合适位置为止 ( ) 4. 对于一棵具有 n 个结点 高度为 h 的二叉树, 进行任一种次序遍历的时间复杂度均为 O(n) 0 ( ) 5. 对于同一组记录集合, 生成二叉搜索树的形态与插入记录的次序无关 ( ) 6. 装载因子是散列存储中的一个重要指标, 它反映了散列表的装满程度 ( ) 7. 在一棵 B 树中, 所有叶结点都处在同一层上 ( ) 得分 评卷人 1 四 运算题 ( 每小题 6 分, 共 3 0 分 ) 1. 假定一棵普通树的广义表表示为 a(b(e), c(f( h,i,j ), g», 分别写出对其进行先根和按层遍历的结果 先根 : 按层 : 2. 假定一个线性表为 (38,52,25,74, 邸,16,30), 根据此表中的元素排列次序生成一棵二叉搜索树, 求出该二叉搜索树中分支结点数和叶子结点数 o 分支结点数 : 叶子结点数 : 77
V= {1,2,3,4,5}; E= {< 1, 2>, < 1, 3>, < 2, 4>, < 2, 5>, < 3, 4>, < 4, 5>, < 5, 1>, < 5, 2>, <5,3> 订假定此图采用邻接矩阵表表示, 根据图的遍历算法分别写出丛顶点 i 出发进行深度优先搜索和广度优先搜索所得到的顶点序列 c 深度优先搜索序列 : 广度优先搜索序列 : 5. 设散列表的长度 m=7, 散列函数为 H ( K) = K mod nl, 若采用线性探查法解决冲突, 待依次插入的关键码序列为 { 1 9, 1 4, 2 3, 6 8, 2 0 }, 试求出最后得到的散列表 o 123 4 5 6 得分 评卷人 五 算法分析题 ( 每小题 8 分, 共 1 6 分 ) 1. 下面算法的功能为 : 将两个有序单链表合并成一个有序单链表并返回其表头指针 阅 读算法, 在划有横线的上面填写合适的内容 ListNode 头 Merge1 (ListNode 头 & pi, ListNode 头 & p2) ListNode 头 p=new ListNode, 美 =p; whilecpi! = NULL && p2! = NULL) if(pl 一 >data<=p2 一 - >data) { p 一 >link=pl; 78
else {p 一 >link=p2; p2==p2 一 >link 川 if(pl! =NULL) p 一 >link=pl; else p->link=p2; pl=p2=null; return f- > link; 2. 已知二叉树中的结点类型 BinTreeNode 定义为 : struct Bin'freeNode {ElemType data; BinTreeNode 头 left, 关 right;}; 其中 d a ta 为结点值域, left 和 right 分别为指向左 右子女结点的指针域 根据下面算法 的定义指出其功能 算法中参数 BT 指向一棵二叉树 BinTreeNode 祷 BTreeSwopXCBinTreeNode 关 BT) ifcbt= = NULL) return NULL; else { BinTreeNode 头 pt=new BinTreeNode; pt 一 >data=b1' 一 >data; pt 一 >right=b1'reeswopx(bt 一 >left); pt 一 > left = BTreeSwopX(BT 一 >right); return pt; 算法功能 : 79
得分 评卷人 六 算法设计题 ( 8 分 ) 已知二叉树中的结点类型 B i ntreen o de 定义为 : struct BinTreeNode {char data; BinTreeNode 祷 left, 铃 right;}; 其中 da ta 为结点值域,left 和 right 分别为指向左 右子女结点的指针域, 根据下面函数声 明编写出求一棵二叉树中分支结点总数的算法, 该总数值由函数返回 假定参数 BT 初始指 向这棵二叉树的根结点 int BTreeCount(BinTreeNode 铃 B1') ; 80
试卷代号 : 1 0 1 0 中央广播电视大学 2 0 1 0-2 0 1 1 学年度第二学期 " 开放本科 " 期末考试 数据结构试题答案及评分标准 供参考 2011 年 7 月一 单项选择题 ( 在括号内填写所选择的标号 每小题 2 分, 共 1 8 分 ) 1. B 2. A 3. B 4. C 5. D 6. D 7. A 8. C 9. C 二 填空题 ( 在横线处填写合适内容 每小题 2 分, 共 1 4 分 ) 1. 顺序 2. O(nlogzn) 3. 1 4. 2 5. 右子树 6. 直接选择 7. 0(n 2 ) 三 判断题 ( 在每小题后面的括号内打对号 "~ " 表示叙述正确或打叉号 " x " 表示叙述错误 每 小题 2 分, 共 1 4 分 ) 1. 对 2. 错 3. 对 4. 对 5. 错 6. 对 7. 对 四 运算题 ( 每小题 6 分, 共 3 0 分 ) 1. 先根 : a, b, e, c, f,h, i 汀, g //3 分 按层 : a, b, c, e, f, g, h, i, j //3 分 2. 分支结点数 :4 //3 分 叶子结点数 : 3 //3 分 3. {49,34,30,12,28,16} 81
4. 深度搜索序列 :1,2,4,5,3 //3 分广度搜索序列 : 1, 2, 3, 4, 5 //3 分 5. 散列表中的每个元素占 1 分, 全对得 6 分 I 14 I 20 I 23 I I 五 算法分析题 ( 每小题 8 分, 共 1 6 分 ) 1. p1=p1 一 >link p=p 一 >link / / 每空 4 分 2. 生成一棵新二叉树并返回树根指针, 该二叉树是已知二叉树 BT 中所有结点的左 右子树 ( 或左 右孩子的值 交换的结果 六 算法设计题 ( 8 分 ) 评分标准 : 根据编程酌情给分 int BTreeCount(BinTreeNode 赞 BT) if(b1'==null) return 0; //2 分 else if(bt 一 >left==null && BT 一 - >right= = NULL) return 0; else return BTreeCount(BT 一 >left) 十 BTreeCount(BT 一 >right) 十 1 ; //4 分 //8 分 说明 : 函数体中的每个 e l se 保留字可以省略 82