北航入学考试数据结构与语言试题答案.pdfVIP

2011年入学考试

“数据结构与C语言程序设计”(科目代码:991)试题与答案

一、单项选择题(本题共20分，每小题各2分)

1.下列关于线性表的结构的叙述中，错误的是。

A．线性表的顺序结构中隐式地了数据元间的逻辑关系

B．线性表的顺序结构一定需要占用一片地址连续的空间

C．线性表的链式结构通过指针来反映数据元间的逻辑关系

D．线性表的链式结构占用的空间一定不连续

2.若front和rear分别表示队列的队头指针与队尾指针，则向队列中一个由p

指的新元素的过程是依次执行。

A．rear=p;front=p;B．front=p;rear=p;

C．rear−link=p;rear=p;D．front−link=p;rear=p;

3．下列关于二叉树的叙述中，正确的是。

A．二叉树的度可以小于2B．二叉树的度等于2

C．二叉树中至少有一个结点的度为2D．二叉树中每一个结点的度都为2

4．若某二叉树有40个叶结点，则该二叉树的结点总数最少是。

A．78B．79C．80D．81

5．若采用邻接矩阵一个有向图，且邻接矩阵主对角线以下元素均为0，则该有向

图的拓扑序列。

A．存在且惟一B．存在但可能不惟一

C．不存在D．无法确定

6．下面关于AOE网的叙述中，正确的是。

A．AOE网是一个带权的连通图

B．AOE网是一个带权的强连通图

C．AOE网是一个带权的无回路的连通图

D．AOE网是一个带权且无回路的有向图

7．下列关于线性表查找方法的叙述中，错误的是。

A．顺序查找法适合于采用顺序结构和链式结构的线性表的查找

B．对于相同元素，顺序查找法一定能够查找到表中首次出现的元素

C．对于相同元素，折半查找法一定能够查找到表中首次出现的元素

D．对于相同元素，折半查找法不一定能够查找到表中首次出现的元素

8．在二叉排序树中进行查找的平均时间效率主要与下列因一有关，该因素是。

A．二叉排序树的深度B．二叉排序树中结点的个数的多少

C．被查找结点的度D．二叉排序树的结构

9．下列4种排序方法中，每一趟排序结束时不一定能够确定一个元素排序最终位置的

是。

A．排序B．快速排序

C．堆积(Heap)排序D．二路归并排序

2

10．下列4种排序方法中，当待排序的序列中元素初始时已经按值有序，排序所花费的

时间反而有可能最多的是。

A．泡排序B．Shell)排序

C．快速排序D．堆积(Heap)排序

二、简答题(本题共20分，每小题各5分)

1.等概率情况下，在长度为n的顺序表中和删除一个数据元素分别需要平均移动

多少个元素？移动的元素个数主要取决于哪几个因素？

2.在采用循环单链表作为某队列的结构时，可以只设置一个队头指针，也可以只

设置一个队尾指针。请问：从操作的时间效率考虑，采用哪种方案更合适？为什么？

4.什么是小顶堆积(Heap)？在小顶堆积中，值最大的元素可能处在什么位置？（可以

借助一棵二叉树描述）

三、综合题(本题共20分，每小题各5分)

1.下列算法的功能是删除长度为n的顺序表A中重复出现的多余元素，即对于重复出