电大期末考试数据结构

试卷代号：1010

中央广播电视大学2005—2006学年度第二学期“开放本科”期末考试

计算机专业数据结构试题

2006年7月

一、一、单项选择题，在括号内填写所选择的标号(9小题，每小题2分，共18分)

5．如果一个递归函数过程中只有一个递归语句，而且它是过程体的最后可执行语句，则称这种递归为( )，它很容易被改写为非递归过程。

A．单向递归B．回溯递归

C. 间接递归D．尾递归

6．假定一棵二叉树的第i层上有3i个结点，则第i+l层上最多有( )个结点。

A．8i B．6i

C. 9i D．2i

7．从具有n个结点的A VL树中搜索一个元素时，在等概率情况下进行成功搜索的时间

复杂度大致为( )。

9．图的深度优先搜索遍历类似于树的( )次序遍历。

A．先根B．中根

C. 后根D．层次

二、填空题，在横线处填写合适内容(每小题1分，共12分)

1。数据结构的存储结构包括顺序、——、索引和散列四种。

2，在程序运行过程中进行存储空间分配的数组是——分配的数组。这种数组在声

明它时需要使用数组指针。

3．在链表中进行插入和————操作的效率比在顺序存储结构中进行相同操作的效率高。4．栈是一种限定在表的一端进行插入和删除操作的线性表，又称它为——表。

5．如果一个对象部分地包含自己，或自己定义自己，则称这个对象是——的对象。

6．假定一棵树的广义表表示为a(b，c，d(e，f)，g(h))，则结点f的层数为——·假定树根结点的层数为0。

7．若把一棵树按照左子女一右兄弟表示法转换成一棵对应的二叉树，则该二叉树的树根结点肯定没有——子女。

8．向一棵二叉搜索树中插入一个元素时，若元素的值小于根结点的值，则应把它插入到根结点的——上。

9．设图G＝(V，E)，V=(1，2，3，4}，E={<l，2>，<l，3>，<2，4>，<3，4>}，从顶点1出发，对图G进行广度优先搜索的序列有——种。

10．每次直接或通过基准元素间接比较两个元素，若出现逆序排列就交换它们的位置，这种排序方法叫做——类排序。

11．快速排序在平均情况下的空间复杂度为——。

12．若对长度n＝10000的线性表进行二级索引存储，每级索引表中的索引项是下一级20个表项的索引，则一级索引表的长度为——。

三、判断题，在每小题前面打对号表示正确或打叉号表示错误(每小题1分，共10分) ( )1．算法和程序的概念完全相同，在讨论数据结构时二者是通用的。

( )2．插入与删除操作是数据结构中最基本的两种操作，因此这两种操作在数组中也经常被使用。

( )3．栈和队列都是顺序存取的线性表，但它们对存取位置的限制不同。

( )4．将f＝1十1／2十1／3+…十1／n转化为递归函数时，递归部分为f(n)=f(n一1)+l ／n，递归结束条件为f(1)＝1。

( )5．在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和中序遍历时具有相同的结果。

( )6．进行折半搜索的表必须是顺序存储的有序表。

( )7．用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数有关，而与图的边数无关。

( )8．对于AOE网络，任一关键活动延迟都将导致整个工程的延迟完成。

( )9．将一批杂乱无章的数据按小根堆结构组织起来并存储到一维数组中，则堆中的数据必然按从小到大的线性顺序排列。

( )10．一棵m阶B树中每个结点都最多有m-1个关键码，最少有【M／2】-1个关键码。

四、运算题(每小题6分，共30分)

提示：在进行每题运算时，若需要最好先在草稿纸上根据题意画出对应的图形，这样会更直观和简便。

1．设有一个lOXl0的矩阵A，将其下三角部分按行存放在一个一维数组B中，A[0][[0]存放于B[0]中，那么A[8][5]存放于B中什么位置。

A[8][5]在B中的存放位置(即下标位置)为：

2．已知一棵树的静态双亲表示如下，其中用-1表示空指针，树根结点存于。号单元，分别求出该树的叶子结点数、单分支结点数、两分支结点数和三分支结点数。

叶子结点数：单分支结点数:

两分支结点数：三分支结点数：

3．已知图G=(V，E)，其中

V={6，b，c，d，e}

E＝{<a，b>，<b，o>，<c，b>，<c，d>，<d，e>，<e，a>，<e，c>}

请写出各结点的出度和入度。

4．已知一个AOV网络的顶点集V和边集G分别为：

V＝{0，1，2，3，4，5，6，7}；

E＝{<0，2>，<1，3>，<1，4>，<2，4>，<2，5>，<3，6>，<3，7>，<4，7>，<5，7 >，<6，7>}；

若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号(即dest域的值)从小到大的次序链接的，则按主教材中介绍的进行拓扑排序的算法，写出得到的拓扑序列。

拓扑序列：

5．已知有一个数据表为{30，18，20，15，38，12，44，53，46，18*，26，86}，给出进行归并排序的过程中每一趟排序后的数据表变化。

(0)[30 18 20 15 38 12 44 53 46 18 26 86]

(1)

(2)

(3)

(4)

五、算法分析题(3小题，每小题6分，共18分)

1．该算法功能为：从表头指针为Ia的、按值从小到大排列的有序链表中删除所有值相同的多余元素，并释放被删结点的动态存储空间。阅读算法，按标号填写空缺的内容，要求统一填写在算法后面的标记处。

2．请写出下面算法的功能，其中Stack表示栈类，Queue表示队列类。

算法功能：

3．已知二叉树中的结点类型Bin Tree Node定义为：

struct Bin Tree Node {Elem Type data；Bin Tree Node*left,*right；}；

其中data为结点值域，left和right分别为指向左、右子女结点的指针域。根据下面算法的定义指出其功能o—算法中参数BT指向一棵二叉树。

Bin Tree Node*B Tree Swop X( Bin Tree Node*BT)

{

六、算法设计题(2小题，每小题6分，共12分)

1．已知f为单链表的表头指针，单链表中的结点结构为(data，link)，并假定每个结点的值均为大于。的整数。根据下面函数声明写出递归算法，返回单链表中所有结点的最大值，若单链表为空则返回数值0。

int Max(Link Node * f)；

2．设Q是一个由其队尾指针和队列长度标识的循环队列，按照下面队列定义和函数声

明写出从此队列中删除一个元素的算法。

／／若队列非空则删除队头元素并由引用参数x带回，同时返回true;否则若队列为空则返回false。

bool DelCQueue ( Cyclic Queue & Q，Elem Type & x)；

卷代号：1010

中央广播电视大学2005—2006学年度第二学期“开放本科”期末考试

计算机专业数据结构试题答案及评分标准

(供参考)

2006年7，

一、单项选择题，在括号内填写所选择的标号(9小题，每小题2分，共18分)

l。A 2．A 3．C 4. D 5．D

6．D 7。C 8．C 9．A

二、填空题，在横线处填写合适内容(每小题1分，共12分)

1．链接

2．动态

3．删除

4．后出先进

5．递归

6．2

7．右

8．左子树

9．2

10．交换

11．O(10&n)

12．500

三、判断题，在每小题前面打对号或打叉 …… 此处隐藏：2285字，全部文档内容请下载后查看。喜欢就下载吧 ……