试卷代号：1010 座位■■ 中央广播电视大学2011-2012学年度第一学期“开放本科”期末考试 数据结构 试题 2012年1月 题 号 二 三 四 五 六 总分 分 数 得 分 评卷人 一、单项选择题（在括号内填写所选择的标号。每小题2分，共18 分) 1.执行下面程序段时，S语句的执行次数为( for(int i=1;ilink==NULL; C.first->link==first; D.first！=NULL: 4.若让元素1,2,3依次进栈，则出栈次序不可能出现( )种情况。 A.3,2,1 B.2,1,3 C.3,1,2 D.1,3,2 5.在一棵具有n个结点的满二叉树中，共包含有( )个分支结点。 A.n-1 B.n/2 C.n/2+1 D.n/2-1 74
试卷代号 座位号CD 中央广播电视大学 2 0 11一 2学年度第一学期"开放本科"期末考试 数据结构试题 2012 年1 一、单项选择题{在括号内填写所选捧的标号。每小题 2分，共 分) 1.执行下面程序段时， 5语句的执行次数为( )。 |题号 - 六l |分数 I I I I I I I |得分|评卷人| I I I for (int i=l; i link = = first; B. first->link==NULL; D. first! =NULL; 4. 素1 ，2 ，3 依次 )种情况。 A. 3 ,2,1 C. 3,1,2 B. 2 ,1,3 D. 1 ,3,2 5. 在一 个结 )个分支结点。 A. n-l C. B. n/2 D. n/2-1 74
6.若搜索每个元素的概率相等，则在长度为的顺序表上搜索任一元素的平均搜索长 度为( A.n B.n+1 C.(n-1)/2 D.(n+1)/2 7.向一棵AVL树插人元素时，可能引起对最小不平衡子树的调整过程，此调整分为 )种旋转类型。 A.2 B.3 C.4 D.5 8.为了实现图的广度优先搜素遍历，其算法使用的一个辅助数据结构是()。 A.栈 B.队列 C.二叉树 D.树 9.在一棵5阶B树中，每个结点最多允许有( )个关键码。 A.2 B.3 C.4 D.5 得 分 评卷人 二、填空题（在横线处填写合适的内容。每小题2分，共14分） 1.属性与操作相同的对象构成类，类中的每个对象又称为该类的 2.队列的删除操作在 进行。 3.在一棵三叉树中，若度为3的结点数有2个，度为2的结点数有1个，度为1的结点数 有2个，则度为0的结点数有个。 4.在一个最小堆中，堆顶结点的值是所有结点中的 5.在一棵具有n个结点的AVL树上进行插入或删除元素的时间复杂度大致为 6.在对个元素进行直接选择排序的算法中，记录比较总次数的时间复杂度为 7.在堆排序中，如果n个对象的初始堆已经建好，则在堆排序阶段，需要进行 次对堆顶结点的调整（筛）运算。 75
6. 若搜索每 概率 在长度 表上搜 索任 一 平均搜 度为( )。 A. n C. (n 1) B. n+1 D. (n+1)/2 7. 棵AVL 树插 素 时 小不 调 整 调 整 ( )种旋转类型。 A. 2 C. 4 B. 3 D. 5 8. 图 的广度优先搜索遍历 法使用 据结构是 )。 A. 枝B.队列 C. 树D. 9. 棵5 阶B 最多允许 )个关键码。 A. 2 C. 4 |得分|评卷人 I I I B. 3 D. 5 二、填空题{在横线处填写合适的内容。每小题 2分，共 4分) 1.属性与操作相同的对象构成类，类中的每个对象又称为该类的一一一一 2. 队列 删 除操作 3. 在一 为3 的 有2 为2 的 有1 为1 2个，则度为 O的结点数有一一一一-个。 4. 在一 小堆 堆顶 5. 结 点 的AVL 进 行 或 删 复 杂 度 大 致 6. 在对 直 接 选 择 7. 在 堆 排 果n 个 对 象 建 好 堆 排 要 进 行 次对堆顶结点的调整(筛)运算。 75
得分 评卷人 三、判断题（在每小题后面的括号内打对号“√”表示叙述正确或打叉 号“×"表示叙述错误。每小题2分，共14分)】 1.数据的逻辑结构与数据元素本身的内容和形式无关。() 2.使用三元组表示稀疏矩阵中的非零元素比采用二维数组表示能节省存储空间。 () 3.在一棵二叉树中，假定每个结点只有左子女，没有右子女，则对它分别进行前序遍历和 按层遍历时具有相同的结果。() 4.能够在链接存储的有序表上进行折半搜索，其时间复杂度与在顺序存储的有序表上相 同。() 5.邻接表表示只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。 () 6.在索引顺序结构上实施分块搜索，在等概率情况下，其平均搜索长度不仅与子表个数 有关，而且与每一个子表中的元素个数也有关。() 7.向一棵B树插人元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度减 少1。( 得 分 评卷人 四、运算题（每小题6分，共30分） 1.假定一棵二叉树广义表表示为a(b(c),d(e,f),分别写出对它进行中序、后序和按层 遍历的结果。 中序： 后序： 按层： 2.假定一维数组a[10]中存储的有序表为(15,26,34,39,45,56,58,63,74,76)，根据折半 搜索所对应的判定树，分别求出该判定树中度为1和2的结点个数。 度为1的结点个数： 度为2的结点个数： 76
|得分|评卷人| I I I 三、判断题(在每小题后面的括号内打对号"~"表示叙述正确或打叉 "表示叙述错误。每小题 2分，共 4分} 1.数据的逻辑结构与数据元素本身的内容和形式无关。( ) 2. 用三元组表 稀疏 采用二维数组表示 ( ) 3. 左子女 有右子女 行前 遍历 按层遍历时具有相同的结果。( ) 4. 能够在链接存储 序表上进行折半搜 表上 同。( ) 5. 邻接表表 能用 于有 向 图 存储 存储 ( ) 6. 引}119t 构 上 分块 有关，而且与每一个子表中的元素个数也有关。( ) 7. 棵B 过程 若最 树根 分裂 原树 度减 少Ie ( ) 得分|评卷人 四、运算题(每小题 6分，共 0分) 1.假定一棵二叉树广义表表示为 )， dee , f))，分别写出对它进行中序、后序和按层 遍历的结果。 中序: 后序: 按层: 2. 定→维数组a[10J 存储 为(15 ，26 ，34 ，39 ，45 ，56 ，58 ，63 ，74 ，76) 根据 搜索所对应的判定树，分别求出该判定树中度为 1和 2的结点个数。 度为 1的结点个数 度为 2的结点个数 76
3.假定一个线性表为(38,42,55,15,23,44,30,74,48,20)，根据此线性表中元素的排列 次序生成一棵二叉搜索树，求出该二叉搜索树的高度和叶子结点数。假定树根层的高度为1。 二叉搜索树的高度： 叶子结点数： 4.已知一个图的顶点集V和边集G分别为： V={1,2,3,4,5,6}; E={,,,,,,,, }: 假定该图采用邻接表表示，每个顶点邻接表中的边结点都是按照终点序号从小到大的次 序链接的，试写出： (1)从顶点1出发进行深度优先搜索所得到的顶点序列； (2)从顶点1出发进行广度优先搜索所得到的顶点序列。 (1): (2): 5.已知一个数据序列为{16,45,27,23,41,15,56,64}，请把它调整为一个最大堆。 最大堆： 得分评卷人 五、算法分析题（每小题8分，共16分） l.设rear是以循环链表表示的队列的队尾指针，EnQueue函数实现把x插人到队尾的 操作。阅读算法，在划有横线的上面填写合适的内容。 void EnLQueue(ListNode *rear,ElemType x) { ListNode p; p=new ListNode; /p指向动态分配的结点空间 p->data=x; p->link= rear->link=p; }； 77
3. 性表为(38 ，42 ，55 ，15 ，23 ，44 ，30 ，74 ，48 ，20) 据此 性表 次序生成一棵二叉搜索树，求出该二叉搜索树的高度和叶子结点数。假定树根层的高度为 1。 二叉搜索树的高度 叶子结点数: 4. 图 的 集V 集G V={1 ,2 ,3 ,4 ,5 ,6} ; E= {, , , , , ,,, }; 假定该图采用邻接表表示，每个顶点邻接表中的边结点都是按照终点序号从小到大的次 序链接的，试写出: (1)从顶点 1出发进行深度优先搜索所得到的顶点序列; (2) 点1 发进行广度优先搜 顶点 (1) : (2): 5. 知一 序列 为{16 ，45 ，27 ，23 ，41 ，15 ，56 ，64} 把它调 最大 最大堆 |得分 l评卷人| I I I 五、算法分析题(每小题 8分，共 6分} 1.设 表表示 队列 尾 指 实 现 插 入到 队 操作。阅读算法，在划有横线的上面填写合适的内容。 void EnLQueue(ListNode &. rear, ElemType x) ListNode 铸p; p= new ListNode; / /p 动态 一>data=x; 一>link= rear- > link= p; 77
2.假定HL为一个单链表的表头指针，K为一个待查找的值，请指出算法功能。 bool Unknown(ListNode HL,int K) if(HL==NULL)return false; if(HL->data==K)return true; ListNode cp; cp=HL->link; while(cp！=NULL) if(cp->data==K)return true; else cp=cp->link; return false; 算法功能： 得分 评卷人 六、算法设计题(8分) 已知二叉树中的结点类型BinTreeNode定义为： struct BinTreeNode (char data;BinTreeNode left,right;); 其中data为结点值域，left和right分别为指向左、右子女结点的指针域，根据下面函数声 明编写出求一棵二叉树中叶子结点总数的算法，该总数值由函数返回。假定参数BT初始指 向这棵二叉树的根结点。 int BTreeLeafCount(BinTreeNode BT); 78
2. 定HL 一个 链表 ，K 为一 待查找 算法功 bool Unknown( ListNode 祷HL int K) if(HL= =NULL) return false; if(HL- >data= = K) return true; ListNode 椅cp; cp=HL一>link; while(cp! =NULL) if(cp->data= =K) return true; else cp=cp一>link; return false; 算法功能 |得分|评卷人| I I I 六、算法设计题 8分} 已知二叉树中的结点类型 re ode定义为 struct BinTreeNode {char data; BinTreeNode 铃left ，特 ; 其中 a为结点值域， left 和right 别为 右子女结 据下 明编写出求一棵二叉树中叶子结点总数的算法，该总数值由函数返回。假定参数 T初始指 向这棵二叉树的根结点。 int BTreeLeafCount(BinTreeNode铃BT); 78
试卷代号：1010 中央广播电视大学2011一2012学年度第一学期“开放本科”期末考试 数据结构 试题答案及评分标准 (供参考) 2012年1月 一、单项选择题（在括号内填写所选择的标号。每小题2分，共18分） 1.D 2.A 3.A 4.C 5.B 6.D 7.C 8.B 9.C 二、填空题（在横线处填写合适的内容。每小题2分，共14分】 1.实例 2.队头（或队首） 3.6 4.最小值 5.O(logzn) 6.0(n2) 7.n-1 三、判断题（在每小题后面的括号内打对号“√”表示叙述正确或打叉号“X”表示叙述错误。每 小题2分，共14分】 1.对 2.对 3.对 4.错 5.错 6.对 7.错 四、运算题（每小题6分，共30分） 1.中序：c,b,a,e,d,f /2分 后序：c,b,e,f,d,a //2分 按层：a,b,d,c,e,f /2分 2.度为1的结点个数：3 /13分 度为2的结点个数：3 /3分 3.二叉搜索树的高度：5/3分 79
试卷代号 中央广播电视大学 11 2学年度第-学期"开放本科"期末考试 数据结构试题答案及评分标准 (供参考) 2012 年1 一、单项选择题{在括号内填写所选择的标号。每小题 1. D 2. A 3. A 4. C 5. B 6. D 7. C 8. B 9. C 二、填空题{在横线处填写合适的内窑。每小题 1.实例 2. 3. 6 4. 小值 5. 0 (10g 2n ) 6. O(n2 ) 7. n-l 三、 j断题{在每小题后面的捂号内打对号 小题 1.对 .对 .对 .错 .错 .对 .错 四、运算题(每小题 1.中序 //2 后序 //2 按层 //2 2. 为1 数:3 //3 度为 个数 / /3 3. 度:5 //3 79
叶子结点数：4//3分 4.(1)1,2,4,5,6,3 //3分 (2)1,2,3,4,5,6/3分 5.最大堆：{64,45,56,23,41,15,27,16} 五、算法分析题（每小题8分，共16分】 l.rear->link、rear=p /每空4分 2.从HL单链表中顺序查找出值为K的结点，若查找成功则返回真，否则返回假。 六、算法设计题(8分) int BTreeLeafCount(BinTreeNode BT) if(BT==NULL)return 0;//1 else if(BT->left==NULL &&BT->right==NULL)return 1; /14分 else return BTreeLeafCount(BT->left)+BTreeLeafCount(BT->right); /18分 说明：函数体中的两个else保留字可以省略。 80
叶子结点数: 4 / /3 4. (1) 1 ,2 ,4 ,5 ,6 ,3 //3 (2 ，2 ，3 ，4 ，5 ，6 //3 5. 最大 {64 ,45 ,56 ,23 ,41 ,15 ,27 ,16} 五、算法分析题{每小题8分，共 6分} 1. rear 1ink 、rear=p / /每空 4分 2. 从HL 单链表 序查 为K 查找成功则 六、算法设计题 8分} int BTreeLeafCount(BinTreeNode 提BT) 80 if(BT= =NULL) return 0; / /1 else f(BT left = = NULL &. &. BT 一>right= =NULL) return 1; else return BτreeLeafCount (BT left)+BTreeLeafCount (BT - >right) ; 说明 z函数体中的两个 el e保留字可以省略。 //4 //8
