北京广播电视大学程序设计基础形考任务3-形考任务三0答案

1、试卷总分:100 得分:60一、填空题(每空2分,合计40分, 如果以附件形式提交，请在答题输入框中输入提示文字”见附件“）1数据结构研究主要包括三个方面的内容，分别是：数据的 ? ? ? ? ? ? ? ? 结构?，数据的 ? ? ? ? ? ? ? ? ? ? 结构? ?，以及定义在这上面的数据的? ? ? ? ? ? ? ? ?。2当向一个顺序表插入一个元素时，从插入位置开始后的所有元素均需 ? ? ? ? ? ? ? ?一个位置，移动过程是从 ? ? ? ? ? ? ? ? ?向 ? ? ? ? ? ? ? ?依次移动每一个元素。3要从一个顺序表删除一个元素时，被删除之后的所有元素均需

2、 ? ? ? ? ? ? ? ? ? ? ?一个位置，移动过程是从 ? ? ? ? ? ? ? ?向 ? ? ? ? ? ? ? ?依次移动每一个元素。4线性表、栈和队列都是? ? ? ? ? ? ? ? ? ? ?结构，可以在线性表的 ? ? ? ? ? ? ? ? ? ?位置插入和删除元素，而栈只能在 ? ? ? ? ? ? ? ? ? 插入和删除元素；对于队列只能在 ? ? ? ? ? ? ? ? ? ?插入元素，在 ? ? ? ? ? ? ? ? ? ? ? ?删除元素。5如果要在链表中删除一个元素，则只要将要删除的元素的 ? 前 ? 一个元素的指针调整为指向要删除的元素的下一个元素。

3、6为了解决假溢出，通常采用 ? ? ? ? ? ? ? ? ? 队列的方法，即把队列的存储空间设想成一个头尾相接的环状结构。7二叉树的第 ? ? ? ? ? ? ? ?层上至多有2 i-1 (i1)个结点。8在任意二叉树中，若有n0个叶子结点，n2个度为2的结点，则必有：? ? ? ? ? ? ? ? ? ? ? ?9深度为h且含有2 h ? -1个结点的二叉树为 ? ? ? ? ? ? ? ? 二叉树。10深度为5的二叉树中至多含有 ? ? ? ? ? ? ? 点。答案:1数据结构研究主要包括三个方面的内容，分别是：数据的逻辑结构，数据的存储结构 ，以及定义在这上面的数据的运算。2当向一个顺

4、序表插入一个元素时，从插入位置开始后的所有元素均需向后移动一个位置，移动过程是从后向前依次移动每一个元素。3、要从一个顺序表删除一个元素时，被删除之后的所有元素均需向前移动一个位置，移动过程是从前向后依次移动每一个元素。4、线性表、栈和队列都是线性结构，可以在线性表的任意位置插入和删除元素，而栈只能在栈顶插入和删除元素；对于队列只能在队尾插入元素，在_队头_删除元素。5、如果要在链表中删除一个元素，则只要将要删除的元素的前一个元素的指针调整为指向要删除的元素的下一个元素。6、为了解决假溢出，通常采用循环队列的方法，即把队列的存储空间设想成一个头尾相接的环状结构。7、二叉树的第 i层上至多有2i

5、-1(i1)个结点。8、在任意二叉树中，若有n0个叶子结点，n2个度为2的结点，则必有：n0n29、深度为h且含有2h -1个结点的二叉树为满二叉树。10、深度为5的二叉树中至多含有31点。二、选择题（每题6分，合计60分）数据的存储结构分为两种，它们是_。线性存储和树型存储线性存储和数组存储数组存储和指针存储顺序存储和链式存储答案:D3.如果在内存中采用链式保存线性表，则元素之间的逻辑关系通过_。设立单独的区域存储元素之间的逻辑次序元素本身的关键字来表示逻辑次序元素在内存中的相对位置表示逻辑次序保存在元素中的指针表示先后次序答案:D4.进行顺序查找的条件是_。数据不需要有序，也不限制存储方式

6、数据不需要有序，但需要顺序存储数据有序且采用顺序存储方式数据有序且采用链式存储方式答案:A5.队列的最主要特点是_。先进后出一端进一端出两端进出先进先出答案:B6.如果在具有层次结构的一组元素中，存在着一对一的关系，我们可以认为这样的数据的逻辑类型就是_。树型结构图型结构集合线性结构答案:D7.在任意二叉树中，如有N个叶子结点，M个度为 _? 的节点，则必有_。? 2? N=M+2 2 ? ? ? N=M+1 1? N=M+2答案:B8.若按照一定的顺序依次访问树中的每一个结点，而且每个结点只被访问一次，则称这样的操作为_。遍历查找? ? ?排序建立答案:A9.对如图所示的二叉树进行先序遍历的顶点序列是_，后序遍历时得到的顶点序列是_。图? DEBAC ? ? ? ? ABDEC ABDEC? EDBCA? EDBCA DEBAC答案:B10.设有一个栈，元素进栈的次序为A，B，C，D，E，下列 ? 是不可能的出栈序列。E，D，C，B，AB，C，D，E，AA，B，C，D，E?E，A，