自考数据结构试题加答案.docx

自考数据结构试题加答案.docx

《自考数据结构试题加答案.docx》由会员分享，可在线阅读，更多相关《自考数据结构试题加答案.docx（20页珍藏版）》请在冰点文库上搜索。

自考数据结构试题加答案

2008年1月

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

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

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

1.逻辑上通常可以将数据结构分为（　C　）P3

A.动态结构和静态结构B.顺序结构和链式结构C.线性结构和非线性结构D.初等结构和组合结构

2.在下列对顺序表进行的操作中,算法时间复杂度为O

（1）的是（　A　）P16

A.访问第i个元素的前驱（1<

）B.在第i个元素之后插入一个新元素（

）

C.删除第i个元素（

）D.对顺序表中元素进行排序

3.假设带头结点的单向循环链表的头指针为head,则该链表为空的判定条件是（　D　）P26

A.head==NULLB.head–>next==NULLC.head!

=NULLD.head–>next==head

4.已知栈的最大容量为4。

若进栈序列为1,2,3,4,5,6,且进栈和出栈可以穿插进行,则可能出现的出栈序列为（　C　）

A.5,4,3,2,1,6B.2,3,5,6,1,4C.3,2,5,4,1,6D.1,4,6,5,2,3

5.与线性表相比,串的插入和删除操作的特点是（　D　）P54

A.通常以串整体作为操作对象B.需要更多的辅助空间C.算法的时间复杂度较高D.涉及移动的元素更多

6.假设以三元组表表示稀疏矩阵,则与如图所示三元组表对应的4×5的稀疏矩阵是（注：

矩阵的行列下标均从1开始）（　B　）P64

A.

B.

C.

D.

7.以下有关广义表的表述中,正确的是（　A　）P66

A.由0个或多个原子或子表构成的有限序列B.至少有一个元素是子表

C.不能递归定义D.不能为空表

8.树的先根序列等同于与该树对应的二叉树的（　A　）

A.先序序列B.中序序列C.后序序列D.层序序列

9.假设有向图含n个顶点及e条弧,则表示该图的邻接表中包含的弧结点个数为（　B　）P105

A.nB.eC.2eD.n·e

10.如图所示的有向无环图可以得到的不同拓扑序列的个数为（　C　）

A.1B.2C.3D.4

11.下列排序方法中,稳定的排序方法为（　D　）P139

A.希尔排序B.堆排序C.快速排序D.直接插入排序

12.对下列关键字序列进行快速排序时,所需进行比较次数最少的是（　C　）P147

A.（1,2,3,4,5,6,7,8）B.（8,7,6,5,4,3,2,1）

C.（4,3,8,6,1,7,5,2）D.（2,1,5,4,3,6,7,8）

13.含n个关键字的二叉排序树的平均查找长度主要取决于（　B　）P180

A.关键字的个数B.树的形态C.关键字的取值范围D.关键字的数据类型

14.下列查找算法中,平均查找长度与元素个数n不直接相关的查找方法是（　D　）P202

A.分块查找B.顺序查找C.二分查找D.散列查找

15.可有效提高次关键字查找效率的文件是（　B　）P219

A.顺序文件B.倒排文件C.散列文件D.VSAM文件

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

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

错填、不填均无分。

16.数据的存储结构是其逻辑结构映象。

P1

17.输入线性表的n个元素建立带头结点的单链表,其时间复杂度为O（n）。

P22

18.假设循环队列的元素存储空间大小为m,队头指针f指向队头元素,队尾指针r指向队尾元素的下一个位置,则在少用一个元素空间的前提下,表示“队满”的条件是（r+1）%m==f。

P38

19.给定串的联接操作函数：

char*strcat（char*to,char*from）;

//将串from联接到串to的末尾,并返回联接后的串

若字符串s1=〞point〞,s2=〞of〞,则strcat（s1,strcat）（s2,s1））的操作结果是Pointofpoint。

（15460,1523455,123460,

前9层完整29-1=511

第10层489个

n0+n1+n2=1000

n1=1

n0=n2+1

20.假设二维数组A[8][10]按行优先顺序存储,若每个元素占2个存储单元,元素A[0][0]的存储地址为100,则元素A[4][5]的存储地址为190。

=100+（4*10+5）*2

21.假设一棵完全二叉树含1000个结点,则其中度为2的结点数为498。

22.已知一个有向网如图所示,从顶点1到顶点4的最短路径长度为55。

23.在快速排序、堆排序和归并排序中,最坏时间复杂度为O（n2）的排序算法有快速排序。

P156

24.假设散列表的表长为11,散列函数为H（key）=key%7,若用线性探测处理冲突,则探查地址序列hi的计算公式为Hi=（H（key）+i）%11i=0,1,….10

。

25.VSAM文件由索引集、顺序集和数据集三部分组成。

P215

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

26.已知广义表的图形表示如图所示,

（1）写出该广义表L;（（e）,（）,（a,（b,c,d）,（b,c,d））

（2）分别写出该广义表的深度和长度。

3,4

27.已知二叉树的先序序列和中序序列分别为ABDEHCFI和DBHEACIF,

（1）画出该二叉树的二叉链表存储表示;

（2）

写出该二叉树的后序序列。

DHEBIFCA

28.已知有向图的邻接表如图所示,

（1）写出从顶点A出发,对该图进行广度优先搜索遍历的顶点序列;ABDCE

（2）

画出该有向图的逆邻接表。

29.依次读入给定的整数序列{7,16,4,8,20,9,6,18,5},完成下列操作：

1）构造一棵二叉排序树,计算在等概率情况下该二叉排序树的平均查找长度ASL;

2）若变更序列中元素的排列,可构造出平均查找长度达到最小的二叉排序树。

写出满足上述要求的序列中的第一个元素。

（1）ASL=（1+2*2+3*4+4*2）/9=25/9

（2）7,16,4,8,20,9,6,18,5

4,5,6,7,8,9,16,18,20

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

30.假设以带头结点的单链表表示线性表,阅读下列算法f30,并回答问题:

（1）设线性表为（a1,a2,a3,a4,a5,a6,a7）,写出执行算法f30后的线性表；

（1）a2,a4,a6

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

（2）删除编号为奇数的节点

voidf30（LinkListL）

{

//L为带头结点单链表的头指针

LinkListp,q;

P=L;

while（p&&p–>next）{

q=p–>next;

p–>next=q–>next;

p=q–>next;

free（q）;

}

}

31.算法f31的功能是借助栈结构实现整数从10进制到8进制的转换,阅读算法并回答问题：

（1）画出n为十进制的1348时算法执行过程中栈的动态变化情况;

（2）说明算法中while循环完成的操作。

voidf31（intn）//n为非负的十进制整数

{

inte;

SeqStackS;

InitStack（&S）;

do{

Push（&S,n%8）;

n=n/8;

}while（n）;

while（!

StackEmpty（&S））{

e=Pop（&S）;

printf（〞%ld〞,e）;

}

}

（1）右图

（2）将栈中的数依次输出

32.已知以二叉链表作二叉树的存储结构,阅读算法f32,并回答问题：

（1）设二叉树T如图所示,写出执行f32（T）的返回值;4

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

求二叉树T的深度

intf32（BinTreeT）

{

intm,n;

if（!

T）

return0;

else{

m=f32（T–>lchild）;

n=f32（T–>rchild）;

if（m>n）returnm+1;

elsereturnn+1;

}

}

33.设有向图邻接表定义如下；

typedefstruct{

VertexNodeadjlist[MaxVertexNum];

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

}ALGraph;//邻接表类型

vertex

firstedge

其中顶点表结点VertexNode结构为：

adjvex

next

边表结点EdegNode结构为：

阅读下列算法f33,并回答问题：

（1）已知有向图G的邻接表如图所示,写出算法f33的输出结果;

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

voiddfs（ALGraph*G,intv）

{

EdgeNode*p;

visited[v]=TRUE;

printf（〞%c〞,G–>adjlist[v]·vertex）;

for（p=G–>adjlist[v]）·firstedge;p;p=p–>next）

if（!

visited[p–>adjvex]）

dfs（G,p–>adjvex）;

}

voidf33（ALGraph*G）

{

intv,w;

for（v=0;vn;v++）{

for（w=0;wn;w++）

visited[w]=FALSE;

printf（〞%d:

〞,v）;

dfs（G,v）;

printf（〞﹨n〞）;

}

}

（1）ABCED

（2）深度优先搜索有向图

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

34.假设以单链表表示线性表,单链表的类型定义如下:

typedefstructnode{

DataTypedata;

structnode*next;

}LinkNode,*LinkList;

编写算法,将一个头指针为head且不带头结点的单链表改造为一个含头结点且头指针仍为head的单向循环链表,并分析算法的时间复杂度。

LinkListModifyList（head）

{

LinkNodep;

p=（LinkList）malloc（sizeof（LinkNode））;

p->next=head;

head=p;

while（p->next）p=p->next

p->next=head;

}

2008年10月数据结构

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

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

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

1.如果在数据结构中每个数据元素只可能有一个直接前驱,但可以有多个直接后继,则该结构是（C）

A.栈B.队列C.树D.图

2.下面程序段的时间复杂度为（C）

for（i=0;i

for（j=0;j

A[i][j]=i*j;

A.O（m2）B.O（n2）C.O（m*n）D.O（m+n）

3.在头指针为head的非空单循环链表中,指针p指向尾结点,下列关系成立的是（A）

A.p->next==headB.p->next->next==head

C.p->next==NULLD.p==head

4.若以S和X分别表示进栈和退栈操作,则对初始状态为空的栈可以进行的栈操作系列是（D）

A.SXSSXXXXB.SXXSXSSXC.SXSXXSSXD.SSSXXSXX

5.两个字符串相等的条件是（D）

A.串的长度相等B.含有相同的字符集C.都是非空串D.串的长度相等且对应的字符相同

6.如果将矩阵An×n的每一列看成一个子表,整个矩阵看成是一个广义表L,即L=（（a11,a21,…,an1）,（a12,a22,…,an2）,…,（a1n,a2n,…,ann））,并且可以通过求表头head和求表尾tail的运算求取矩阵中的每一个元素,则求得a21的运算是（A）

A.head（tail（head（L）））B.head（head（head（L）））

C.tail（head（tail（L）））D.head（head（tail（L）））

7.已知一棵含50个结点的二叉树中只有一个叶子结点,则该树中度为1的结点个数为（D）

A.0B.1C.48D.49

8.在一个具有n个顶点的有向图中,所有顶点的出度之和为Dout,则所有顶点的入度之和为（A）

A.DoutB.Dout-1C.Dout+1D.n

9.如图所示的有向无环图可以得到的拓扑序列的个数是（C）

A.3B.4C.5D.6

2653426354256346253465234

10.如图所示的带权无向图的最小生成树的权为（C）

A.51B.52C.54D.56

11.对长度为n的关键字序列进行堆排序的空间复杂度为（B）

A.O（log2n）B.O

（1）C.O（n）D.O（n*log2n）

12.已知用某种排序方法对关键字序列（51,35,93,24,13,68,56,42,77）进行排序时,前两趟排序的结果为

（35,51,24,13,68,56,42,77,93）（35,24,13,51,56,42,68,77,93）

所采用的排序方法是（B）

A.插入排序B.冒泡排序C.快速排序D.归并排序

13.已知散列表的存储空间为T[0..18],散列函数H（key）=key%17,并用二次探测法处理冲突。

散列表中已插入下列关键字：

T[5]=39,T[6]=57和T[7]=7,则下一个关键字23插入的位置是（D）

A.T[2]B.T[4]C.T[8]D.T[10]

14.适宜进行批量处理的文件类型是（A）

A.顺序文件B.索引顺序文件C.散列文件D.多关键字文件

15.VSAM文件的索引结构为（A）

A.B+树B.二叉排序树C.B-树D.最优二叉树

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

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

错填、不填均无分。

16.如果某算法对于规模为n的问题的时间耗费为T（n）=3n3,在一台计算机上运行时间为t秒,则在另一台运行速度是其64倍的机器上,用同样的时间能解决的问题规模是原问题规模的4倍。

17.将两个长度分别为m和n的递增有序单链表,归并成一个按元素递减有序的单链表,可能达到的最好的时间复杂度是O（m+n）。

18.已知循环队列的存储空间大小为m,队头指针front指向队头元素,队尾指针rear指向队尾元素的下一个位置,则在队列不满的情况下,队列的长度是（rear-front+m）%m。

19.字符串“sgabacbadfgbacst”中存在有3个与字符串“ba”相同的子串。

20.假设以列优先顺序存储二维数组A[5][8],其中元素A[0][0]的存储地址为LOC（a00）,且每个元素占4个存储单元,则数组元素A[i][j]的存储地址为LOC（a00）+4（5j+i）。

21.假设用表示树的边（其中x是y的双亲）,已知一棵树的边集为

{,,,,,},该树的度是3。

22.n个顶点且含有环路的无向连通图中,至少含有n条边。

23.在一般情况下用直接插入排序、选择排序和冒泡排序的过程中,所需记录交换次数最少的是选择排序。

24.和二分查找相比,顺序查找的优点是除了不要求表中数据元素有序之外,对存储结构也无特殊要求。

25.顺序文件中记录存放的物理顺序和逻辑顺序一致。

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

26.由森林转换得到的对应二叉树如图所示,写出原森林中第三棵树的前序序列和后序序列。

前序序列：

GHIJ（2分）

后序序列：

HJIG（3分）

27.图的邻接表的类型定义如下所示：

#defineMaxVertexNum50

typedefstructnode{

intadjvex;

structnode*next;

}EdgeNode;

typedefstruct{

VertexTypevertex;

EdgeNode*firstedge;

}VertexNode;

题27图

typedefVertexNodeAdjList[MaxVertexNum];

typedefstruct{

AdjListadjlist;

intn,e;

}ALGraph;

为便于删除和插入图的顶点的操作,可将邻接表的表头向量定义为链式结构,两种定义的存储表示实例如下图所示,请写出重新定义的类型说明。

28.某类物品的编号由一个大写英文字母及2位数字（0..9）组成,形如E32。

运用基数排序

对下列物品编号序列进行按字典序的排序,写出每一趟（分配和收集）后的结果。

E13,A37,F43,B32,B47,E12,F37,B12

第一趟：

B32，E12，B12，E13，F43，A37，B47，F37（2分）

第二趟：

E12，B12，E13，B32，A37，F37，F43，B47（2分）

第三趟：

A37，B12，B32，B47，E12，E13，F37，F43（1分）

29.

（1）画出对表长为13的有序顺序表进行二分查找的判定树；

（2）已知关键字序列为（12,14,16,21,24,28,35,43,52,67,71,84,99）,写出在该序列中二分查找37时所需进行的比较次数。

（1）如图

（2）3次

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

30.已知线性表的存储结构为顺序表,阅读下列算法,并回答问题：

（1）设线性表L=（21,-7,-8,19,0,-11,34,30,-10）,写出执行f30（&L）后的L状态；

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

voidf30（SeqList*L）{

inti,j;

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

if（L->data[i]>=0）{

if（i!

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

j++；

}

L->length=j;

}

（1）L=（21，19，0，34，30）（2分）

（2）删除顺序表中的负值元素。

（3分）

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

（1）Q、Q1和Q2都是队列结构,设队列Q=（1,0,-5,2,-4,-6,9）,其中1为队头元素,写出执行f31（&Q,&Q1,&Q2）之后队列Q、Q1和Q2的状态；

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

（注：

lnitQueue、EnQueue、DeQueue和QueueEmpty分别是队列初始化、入列、出队和判队空的操作）

voidf31（Queue*Q,Queue*Q1,Queue*Q2）{

inte;

lnitQueue（Q1）;

lnitQueue（Q2）;

while（!

QueueEmpty（Q））{

e=DeQueue（Q）;

if（e>=0）EnQueue（Q1,e）;

elseEnQueue（Q2,e）

}

}

（1）Q=（）（1分）Q1=（1，0，2，9）（1分）Q2=（-5，-4，-6）（1分）

（2）将队列Q的元素依次退队，并将正值及0元素入队到Q1，负值元素入队到Q2。

（2分）

32.阅读下列算法,并回答问题：

（1）假设串由合法的英文字母和空格组成,并以’\0’作结束符。

设串s=”⊔⊔|⊔am⊔a⊔⊔⊔student”（⊔表示空格符）,写出f32（s）的返回值；

（1）4（2分）

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

（2）对字符串内的单词个数进行累加计数。

（3分）

intf32（char*s）{

inti,n,inword;

n=inword=0;

for（i=0;s[i]!

=’\0’;i++）

if（s[i]!

=’⊔’&&inword==0）{

inword=1;

n++;

}

elseif（s[i]==’⊔’&&inword==1）

inword=0;

returnn;

}

33.阅读下列对正整数关键字序列L操作的算法,并回答问题：

（1）设L=（28,19,27,49,56,12,10,25,20,50）,写出f33（L,4）的返回值；20

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

利用快速排序的“划分”机制进行查找，以求取序列中排行第k小的元素。

intPartition（SeqList*L,intlow,inthigh）;

∥对L[low..high]做划分,返回基准记录的位置,并使左部的关键字

∥都小于或等于基准记录的关键字,右部的关键字都大于基准记录的关键字

intf33（SeqListL,intk）{

intlow,high,pivotpos;

low=1;

high=L.length;

if（khigh）

return-1;

do{

pivotpos=Partition（&L,low,high）;∥调用快速排序的划分算法

if（pivotpos

low=pivotpos+1;

elseif（pivotpos>k）

high=pivotpos-1;

}while（pivotpos!

=k）;

returnL.data[pivotpos];

}

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

34.二叉排序树的类型定义如下：

typedefstructBSTNode{∥二叉排序树的结点结构

intdata;∥数据域

structBSTNode*lchild,*rchild;∥左、右孩子指针

}BSTNode,*BSTree;

设计递归算法,统计一棵二叉排序树T中值小于a的结点个数。