国开电大《程序设计基础》形考任务三国家开放大学试题答案.doc

国家开放大学《程序设计基础》形考任务三试题答案一、填空题（答案在最后）1．数据结构研究主要包括三个方面的内容，分别是：数据的______结构______，数据的______结构______，以及定义在这上面的数据的______。2．当向一个顺序表插入一个元素时，从插入位置开始后的所有元素均需______一个位置，移动过程是从______向______依次移动每一个元素。3．要从一个顺序表删除一个元素时，被删除之后的所有元素均需______一个位置，移动过程是从______向______依次移动每一个元素。4．线性表、栈和队列都是______结构，可以在线性表的______位置插入和删除元素，而栈只能在______插入和删除元素；对于队列只能在______插入元素，在______删除元素。5．如果要在链表中删除一个元素，则只要将要删除的元素的______前______一个元素的指针调整为指向要删除的元素的下一个元素。6．为了解决假溢出，通常采用______队列的方法，即把队列的存储空间设想成一个头尾相接的环状结构。7．二叉树的第______层上至多有2i-1(i≥1)个结点。8．在任意二叉树中，有若n0个叶子结点，n2个度为2的结点，则必有：______9．深度为h且含有2h-1个结点的二叉树为______二叉树。10．深度为5的二叉树中至多含有______点。二、选择题（答案在最后）题目2：数据的存储结构分为两种，它们是______。A.线性存储和数组存储B.数组存储和指针存储C.线性存储和树型存储D.顺序存储和链式存储题目3：如果在内存中采用链式保存线性表，则元素之间的逻辑关系通过______。A.元素本身的关键字来表示逻辑次序B.保存在元素中的指针表示先后次序C.设立单独的区域存储元素之间的逻辑次序D.元素在内存中的相对位置表示逻辑次序题目4：进行顺序查找的条件是______。A.数据不需要有序，也不限制存储方式B.数据不需要有序，但需要顺序存储C.数据有序且采用顺序存储方式D.数据有序且采用链式存储方式题目5：队列的最主要特点是______。A.先进先出B.一端进一端出C.先进后出D.两端进出题目6：如果在具有层次结构的一组元素中，存在着一对一的关系，我们可以认为这样的数据的逻辑类型就是______。A.集合B.树型结构C.图型结构D.线性结构题目7：在任意二叉树中，如有N个叶子结点，M个度为_____①_______必有_____②_____。的节点，则A.①1B.①2C.①2②N=M+2②N=M+1②N=M+2题目8：若按照一定的顺序依次访问树中的每一个结点，而且每个结点只被访问一次，则称这样的操作为______。A.排序B.查找C.遍历D.建立题目9：对如图所示的二叉树进行先序遍历的顶点序列是_____①_______，后序遍历时得到的顶点序列是_____②_____。A.①DEBACB.①ABDECC.①EDBCA②ABDEC②EDBCA②DEBAC题目10：设有一个栈，元素进栈的次序为A，B，C，D，E，下列是不可能的出栈序列。A.A，B，C，D，EB.B，C，D，E，AC.E，D，C，B，AD.E，A，B，C，D题目11：已知一个图如下所示，则从顶点a出发按深度优先搜索遍历可以得到的一种顶点序列为哪个？A.a，e，d，f，b，cB.a，c，e，b，d，fC.a，b，f，e，c，dD.a，e，c，b，f，d上面题目答案在最后一页，购买后才能查看