高等教育自学考试全国统一命题考1.docx

高等教育自学考试全国统一命题考1.docx

《高等教育自学考试全国统一命题考1.docx》由会员分享，可在线阅读，更多相关《高等教育自学考试全国统一命题考1.docx（13页珍藏版）》请在冰点文库上搜索。

高等教育自学考试全国统一命题考1

2007年1月高等教育自学考试全国统一命题考试

数据结构试题

课程代码2331

一、单项选择题（本大题共15小题，每小题2分，共30分）

在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。

错选、多选或未选均无分。

1．抽象数据类型的三个组成部分分别为（　　　）

A．数据对象、数据关系和基本操作

B．数据元素、逻辑结构和存储结构

C．数据项、数据元素和数据类型

D．数据元素、数据结构和数据类型

2．若算法中语句的最大频度为T（n）=2006n+6nlogn+29log2n,则其时间复杂度为（　　　）

A．O（logn）B．O（n）

C．O（nlogn）D．O（log2n）

3．若线性表的插入和删除操作频繁地在表头或表尾位置进行，则更适宜采用的存储结构为

（　　　）

A．无头结点的双向链表B．带尾指针的循环链表

C．无头结点的单链表D．带头指针的循环链表

4．上溢现象通常出现在（　　　）

A．顺序栈的入栈操作过程中B．顺序栈的出栈操作过程中

C．链栈的入栈操作过程中D．链栈的出栈操作过程中

5．已知串s=″aabacbabcaccab″，串t1=″abc″,串t2=″cba″,函数index（s,t）的返回值为串t在串s中首次出现的位置，则能求得串″abcacba″的操作序列为（　　　）

A．substr（s1,s,6,index（s,t1））;substr（s2,s,index（s,t1）,1）;strcat（s1,s2）;

B．substr（s1,s,7,index（s,t1））;substr（s2,s,index（s,t1）,1）;strcat（s2,s1）;

C．substr（s1,s,6,index（s,t2））;substr（s2,s,index（s,t2）,3）;strcat（s1,s2）;

D．substr（s1,s,6,index（s,t2））;substr（s2,s,index（s,t2）,3）;strcat（s2,s1）;

6．对广义表L=（（a,b）,（（c,d）,（e,f）））执行head（tail（head（tail（L））））操作的结果是（　　　）

A．dB．e

C．（e）D．（e,f）

7．已知一棵完全二叉树有64个叶子结点，则该树可能达到的最大深度为（　　　）

A．7B．8

C．9D．10

8．若一棵二叉树有11个叶子结点，则该二叉树中度为2的结点个数是（　　　）

A．10B．11

C．12D．不确定的

9．对于有向图，其邻接矩阵表示相比邻接表表示更易于进行的操作为（　　　）

A．求一个顶点的邻接点B．求一个顶点的度

C．深度优先遍历D．广度优先遍历

10．若用邻接矩阵表示带权有向图，则顶点i的入度等于矩阵中（　　　）

A．第i行非∞元素之和B．第i列非∞元素之和

C．第i行非∞元素个数D．第i列非∞元素个数

11．对关键字序列（5，1，4，3，7，2，8，6）进行快速排序时，以第一个元素5为基准的一次划分的结果为（　　　）

A．（1，2，3，4，5，6，7，8）B．（1，4，3，2，5，7，8，6）

C．（2，1，4，3，5，7，8，6）D．（8，7，6，5，4，3，2，1）

12．下列二叉树中，不平衡的二叉树是（　　　）

13．下列序列中，不构成堆的是（　　　）

A．（1，2，5，3，4，6，7，8，9，10）

B．（10，5，8，4，2，6，7，1，3）

C．（10，9，8，7，3，5，4，6，2）

D．（1，2，3，4，10，9，8，7，6，5）

14．主关键字能唯一标识（　　　）

A．一个记录B．一组记录

C．一个类型D．一个文件

15．稀疏索引是指在文件的索引表中（　　　）

A．为每个字段设一个索引项B．为每个记录设一个索引项

C．为每组字段设一个索引项D．为每组记录设一个索引项

二、填空题（本大题共10小题，每小题2分，共20分）

请在每小题的空格中填上正确答案。

错填、不填均无分。

16．链式存储结构的特点是借助_______来表示数据元素之间的逻辑关系。

17．假设带头结点的非空单循环链表中仅设尾指针L，则在第1个结点之前插入指针s所指结点的语句依次是_______；_______。

18．无表头结点的链队列Q为空的条件是_______。

19．不含任何字符的串称为_______。

20．假设按行优先顺序将一个20阶的三对角矩阵A压缩存储在一维数组Q中，其中Q[0]存放矩阵的第1个元素a1,1，那么矩阵元素a3,4在Q中的存储位置k=_______。

21．前序序列和中序序列不相同的二叉树的特征是_______。

22．在含有n个顶点的连通图中，任意两个不同顶点之间的简单路径的最大长度为_______。

23．用_______排序方法对关键字序列（20，25，12，47，15，83，30，76）进行排序时，前三趟排序的结果为：

20，12，25，15，47，30，76，83

12，20，15，25，30，47，76，83

12，15，20，25，30，47，76，83

24．哈希表常用的两类解决冲突的方法是_______和_______。

25．倒排文件和多重表文件的主要区别在于_______的结构不同。

三、解答题（本大题共4小题，每小题5分，共20分）

26．已知主串为″ccgcgccgcgcbcb″，模式串为″cgcgcb″。

下表所列为按照朴素的串匹配算法进行的前两趟匹配。

请继续完成余下各趟匹配，直至结束。

27．已知带权图G如图所示，画出图G的一棵最小生成树。

28．对于直接插入排序，希尔排序，冒泡排序，快速排序，直接选择排序，堆排序和归并排序等排序方法，分别写出：

（1）平均时间复杂度低于O（n2）的排序方法；

（2）所需辅助空间最多的排序方法；

（3）最好情况和最坏情况下的时间复杂度相同的排序方法。

（1）

（2）

（3）

29．已知一棵线索化的二叉排序树如图所示。

（1）说明该树的线索化是基于何种遍历次序的；

（2）在该树中插入元素值为53的结点并修改相应线索，画出修改之后的树。

（1）

（2）

四、算法阅读题（本大题共4小题，每小题5分，共20分）

30．假设线性表采用顺序存储结构，表中元素值为整型。

阅读算法f30，并回答下列问题：

（1）设顺序表L=（3,7,3,2,1,1,8,7,3）,写出执行算法f30后的L;

（2）简述算法f30的功能。

voidf30（SeqList*L）

{inti,j,k;

k=0;

for（i=0;ilength;i++）

{for（j=0;jdata[i]!

=L->data[j];j++）;

if（j==k）

{if（k!

=i）L->data[k]=L->data[i];

k++;

}

}

L->length=k;

}

（1）

（2）

31．阅读算法f31,并回答下列问题：

（1）设队列Q=（1，3，5，2，4，6）。

写出执行算法f31后的队列Q;

（2）简述算法f31的功能。

voidf31（Queue*Q）{

DataTypee;

if（!

QueueEmpty（Q））{

e=DeQueue（Q）;

f31（Q）;

EnQueue（Q,e）;

}

}

（1）

（2）

32．已知树的存储结构为孩子兄弟链表，其类型定义如下：

typedefstructCSTNode{

chardata;

structCSTNodeleftmostchild,*rightsibling;

}CSTNode,*CSTree;

阅读函数f32,并回答下列问题：

（1）对于如图所示树，写出函数调用f32（T）的返回值；

（2）简述树T非空时函数f32返回值的含义。

intf32（CSTreeT）{

intc;

CSTreep;

if（!

T->leftmostchild）return1;

else{

c=0;

for（p=T->leftmostchild;p;p=p->rightsibling）

c+=f32（p）;

returnc;

}

}

（1）

（2）

33．已知数组R[1..p-1]中的元素序列为一个大根堆，函数Adjust（R,p）将R[1..p]重新调整为一个大根堆。

（1）在函数Adjust的空缺处填入适当内容，使其成为一个完整的函数；

（2）简述函数f33（R,n）的功能。

voidAdjust（SeqListR,intp）

{inti,j;

RecTypetemp=R[p];

i=p;

j=i/2;

while（j>=1&&R[j].key

{R[i]=R[j];

i=j;

①;

}

R[i]=②;

}

voidf33（SeqListR,intn）

{intk;

for（k=2;k<=n;k++）

Adjust（R,k）;

}

（1）①

②

（2）

五、算法设计题（本大题10分）

34．已知有向图的邻接表表示的形式描述如下：

#defineMaxNum50//图的最大顶点数

typedefstructArcNode{

intadjvex;//邻接点域

structArcNode*nextArc;//链域

}ArcNode;//弧结点类型

typedefstruct{

charvertex;//顶点域

ArcNode*firstArc;//弧表头指针

}VertexNode;//顶点表结点类型

typedefstruct{

VertexNodeadjList[MaxNum];//邻接表

intn,e;//图中当前的顶点数和边数

}ALGraph;//邻接表类型

按以下函数原型编写算法，求有向图G中第i顶点的度，并写出算法的时间复杂度。

intf34（ALGraph*G,inti）;