试卷代号 : 座位号 I II 中央广播电视大学学年度第二学期 " 开放本科 " 期末考试数据结构试题 2011 年 7 月! 题号 I - I 二三四! 五! 六总分分数 I I I 1 1- I ---1 I 得分评卷人一单项选择

Size: px

Start display at page:

Download "试卷代号 : 座位号 I II 中央广播电视大学学年度第二学期 " 开放本科 " 期末考试数据结构试题 2011 年 7 月! 题号 I - I 二三四! 五! 六总分分数 I I I 1 1- I ---1 I 得分评卷人一单项选择"

缨尔房
5 years ago
Views:

1 试卷代号 : 座位号 I II 中央广播电视大学学年度第二学期 " 开放本科 " 期末考试数据结构试题 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

2 6. 向一棵 AVL 树插入元素时, 可能引起对最小不平衡子树的双向旋转的调整过程, 此时需要修改相关 ( ) 个指针域的值 A. 2 c. 4 B. 3 D 在一个具有 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 的层数为假定树根结点的层数为从一棵二叉搜索树中搜索一个元素时, 若给定值大于根结点的值, 则需要向根的 76 继续搜索

3 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

4 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 得分评卷人五算法分析题 ( 每小题 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

5 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

6 得分评卷人六算法设计题 ( 8 分 ) 已知二叉树中的结点类型 B i ntreen o de 定义为 : struct BinTreeNode {char data; BinTreeNode 祷 left, 铃 right;}; 其中 da ta 为结点值域,left 和 right 分别为指向左右子女结点的指针域, 根据下面函数声明编写出求一棵二叉树中分支结点总数的算法, 该总数值由函数返回假定参数 BT 初始指向这棵二叉树的根结点 int BTreeCount(BinTreeNode 铃 B1') ; 80

7 试卷代号 : 中央广播电视大学学年度第二学期 " 开放本科 " 期末考试数据结构试题答案及评分标准供参考 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) 右子树 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

8 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

试卷代号 : 座位号中央广播电视大学学年度第一学期 " 开放本科 " 期末考试数据结构试题 2011 年 1 月题号一四五总分一一分数得分评卷人一单项选择题, 在括号内填写所选择的标号 ( 每小题 2 分, 共 1 8 分 ) 1. 执行下

试卷代号 : 座位号中央广播电视大学学年度第一学期开放本科期末考试数据结构试题 2011 年 1 月题号一四五总分一一分数得分评卷人一单项选择题, 在括号内填写所选择的标号 ( 每小题 2 分, 共 1 8 分 ) 1. 执行下试卷代号 : 1 0 1 0 座位号中央广播电视大学 2 0 1 0 2011 学年度第一学期 " 开放本科 " 期末考试数据结构试题 2011 年 1 月题号一四五总分一一分数一单项选择题, 在括号内填写所选择的标号 ( 每小题 2 分, 共 1 8 分 ) 1. 执行下面程序段时, s 语句的执行次数为 ( ) forcint i= 1; i

试卷代号 : 座位号 I II 中央广播电视大学 学年度第二学期 " 开放本科 " 期末考试 数据结构试题 2011 年 7 月! 题号 I - I 二 三 四! 五! 六 总分 分数 I I I 1 1- I ---1 I 得分 评卷人 一 单项选择

试卷代号 : 座位号 I II 中央广播电视大学学年度第二学期 " 开放本科 " 期末考试数据结构试题 2011 年 7 月! 题号 I - I 二三四! 五! 六总分分数 I I I 1 1- I ---1 I 得分评卷人一单项选择