国开《程序设计基础》形考任务三

【答案为下面试题答案，请核对试题后再购买】

一、填空题(每空2分,合计40分, 如果以附件形式提交，请在答题输入框中输入提示文字”见附件“）

1．1．数据结构研究主要包括三个方面的内容，分别是：数据的                结构     ，数据的                    结构     ，以及定义在这上面的数据的                  。

2．当向一个顺序表插入一个元素时，从插入位置开始后的所有元素均需                         一个位置，移动过程是从               向               依次移动每一个元素。

3．要从一个顺序表删除一个元素时，被删除之后的所有元素均需                     一个位置，移动过程是从               向               依次移动每一个元素。

4．线性表、栈和队列都是                   结构，可以在线性表的                   位置插入和删除元素，而栈只能在                 插入和删除元素；对于队列只能在                    插入元素，在                       删除元素。

5．如果要在链表中删除一个元素，则只要将要删除的元素的   前   一个元素的指针调整为指向要删除的元素的下一个元素。

6．为了解决假溢出，通常采用                 队列的方法，即把队列的存储空间设想成一个头尾相接的环状结构。

7．二叉树的第              层上至多有2^i-1(i≥1)个结点。

8．在任意二叉树中，若有n0个叶子结点，n2个度为2的结点，则必有：                       

9．深度为h且含有2^h  -1个结点的二叉树为                 二叉树。

10．深度为5的二叉树中至多含有               点。

二、选择题（每题6分，合计60分）

2．数据的存储结构分为两种，它们是______。

线性存储和数组存储

顺序存储和链式存储

线性存储和树型存储

数组存储和指针存储

3．如果在内存中采用链式保存线性表，则元素之间的逻辑关系通过______。

元素在内存中的相对位置表示逻辑次序

保存在元素中的指针表示先后次序

设立单独的区域存储元素之间的逻辑次序

元素本身的关键字来表示逻辑次序

4．进行顺序查找的条件是______。

数据有序且采用顺序存储方式

数据不需要有序，但需要顺序存储

数据有序且采用链式存储方式

数据不需要有序，也不限制存储方式

5．队列的最主要特点是______。

先进先出

先进后出

两端进出

一端进一端出

6．如果在具有层次结构的一组元素中，存在着一对一的关系，我们可以认为这样的数据的逻辑类型就是______。

集合

线性结构

树型结构

图型结构

7．在任意二叉树中，如有N个叶子结点，M个度为 _____①_______     的节点，则必有_____②_____。

① 1      ② N=M+2

① 2      ② N=M+1

 ① 2      ② N=M+2

8．若按照一定的顺序依次访问树中的每一个结点，而且每个结点只被访问一次，则称这样的操作为______。

排序

查找      

遍历

建立

9．

对如图所示的二叉树进行先序遍历的顶点序列是　_____①_______，后序遍历时得到的顶点序列是_____②_____。

① ABDEC 　　  ②　EDBCA

①  EDBCA 　　 ② DEBAC

①  DEBAC        ② ABDEC

10．设有一个栈，元素进栈的次序为A，B，C，D，E，下列       是不可能的出栈序列。

A，B，C，D，E  

B，C，D，E，A

E，A，B，C，D

E，D，C，B，A

11．已知一个图如下所示，则从顶点a出发按深度优先搜索遍历可以得到的一种顶点序列为

哪个？

a，c，e，b，d，f

a，b，f，e，c，d

a，e，c，b，f，d

a，e，d，f，b，c