结点2012年10月--2007年1月自考2331数据结构历年试题和答案

全国2012年 月高等教育自学考试

数据结构试题

课程代码  331

请考生按规定用笔将所有试题的答案涂、写在答题纸上。

选择题部分

注意事项:

 . 答题前,考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。

. 每小题选出答案后用B铅笔把答题纸上对应题目的答案标号涂黑。如需改动用橡皮擦干净后,再选涂其他答案标号。不能答在试题卷上。

一、单项选择题(本大题共l5小题,每小题分共30分)

在每小题列出的四个备选项中只有一个是符合题目要求的,请将其选出并将“答题

纸”的相应代码涂黑。错涂、多涂或未涂均无分。

1一个算法的时间耗费的数量级称为该算法的

A效率 .难度

.可实现性 D时间复杂度

.顺序表便于

A插入结点 B.删除结点

C按值查找结点 D按序号查找结点

3.设带头结点的单循环链表的头指针为hed,指针变量P指向尾结点的条件是

A.-nxt->net==head  p-nex=ead

C.p-nx>et==NUL LD.>next=UL

4.设以数组A  . .m 存放循环队列,front指向队头元素 rear指向队尾元素的下一个

位置,则当前队列中的元素个数为

A.( er- rntm)%m . e -fr ont+1

C.  rot-rar)%m  ( ear- rot)m

5.下列关于顺序栈的叙述中,正确的是

A.入栈操作需要判断栈满,出栈操作需要判断栈空

B入栈操作不需要判断栈满,出栈操作需要判断栈空

C.入栈操作需要判断栈满,出栈操作不需要判断栈空

D入栈操作不需要判断栈满 出栈操作不需要判断栈空

6.A是一个1  ×1 的对称矩阵,若采用行优先的下三角压缩存储第一个元素a ,0的存储地址为1每个元素占一个存储单元,则a,5的地址为

A 5 .26

.  D.34

7.树的后序遍历等价于该树对应二叉树的

A.层次遍历 .前序遍历

C.中序遍历 D后序遍历

8使用二叉线索树的目的是便于

A.二叉树中结点的插入与删除 .在二叉树中查找双亲

C确定二叉树的高度 D.查找一个结点的前趋和后继

9设无向图的顶点个数为n则该图边的数目最多为

A n-l B  -  )/2

C n(n+1)  D.n

0可进行拓扑排序的图只能是

.有向图 B.无向图

C有向无环图 D无向连通图

11下列排序方法中稳定的是

A直接插入排序 直接选择排序

C.堆排序 D快速排序

1  下列序列不为堆的是

A.75,4,65 3 ,  5 5 B 75,65,45 30, ,15

C 75,65,30,  5,25 5 D.7,5,6,5,30 15

13.对线性表进行二分查找时要求线性表必须是

A顺序存储 B链式存储

C顺序存储且按关键字有序 链式存储且按关键字有序

 .分别用以下序列生成二叉排序树,其中三个序列生成的二叉排序树是相同的,不同

的序列是

 (4,1,,3,5) B (4,2,,l,5

C 4,5,2,1 3)  (4 2 1,5,3)

 5下列关于m阶树的叙述中,错误的是

每个结点至多有m个关键字

B每个结点至多有棵子树

.插入关键字时,通过结点分裂使树高增加

D删除关键字时通过结点合并使树高降低

非选择题部分

注意事项:

用黑色字迹的签字笔或钢笔将答案写在答题纸上不能答在试题卷上。

二、填空题(本大题共1小题,每小题2分,共20分

6.数据元素之间的逻辑关系称为数据的_____结构。

7在线性表中表的长度定义为_____。

18.用S表示入栈操作,X表示出栈操作,若元素入栈的顺序为1、 2、  、 为了得到

1、 3、 4、 2的出栈顺序,相应的S和X的操作序列为______。

19在二叉树中,带权路径长度最短的树称为____。

0 已知广义表G,ead(G与ai l(G)的深度分别为4和6则G的深度是___。  一组字符(,b,c,)在文中出现的次数分别为(7 6 ,5)字符'd'的哈夫曼编码的长度为___。

2 在一个具有n个顶点的无向图中要连通全部顶点至少需要_____条边。

23.直接选择排序算法的时间复杂度是______。

24.对于长度为 1的表,若采用分块查找,每块的最佳长度为___。

25.用二叉链表保存有个结点的二叉树,则结点中有_____个空指针域。

三、解答题本大题共小题,每小题5分,共2分)

26.假设是一个具有11个元素存储空间的循环队列队尾指针指向队尾元素的下一

个位置 队头指针指向队头元素),初始状态Q frotQ. er=0写出依次执行

下列操作后头、尾指针的当前值。

,,   d, ,f入队,a b,c,出队  1) .fr ont___;Q.r r=_____。

,,i j,k,l入队,   ,,h出队; (2)Q.fr  =______;Q.rear=_____。

M,,,P入队 i j,k,l,m出队 3)Q.fr ont_____;Q.  ar=_____。

27.已知一个无向图如题2图所示,以①为起点,用普里姆rim)算法求其最小生成树,

画出最小生成树的构造过程。

28.用归并排序法对序列(98,   -9, ,7,23,1,8)进行排序,问

( )一共需要几趟归并可完成排序。

2)写出第一趟归并后数据的排列次序。

9.一组记录关键字(55,76,44 32, 4 82,20, 6,43),用散列函数H(ey)ey%1 将记录

散列到散列表HT[0.  1 ]中去用线性探测法解决冲突。

1)画出存入所有记录后的散列表。

()求在等概率情况下查找成功的平均查找长度。

四、算法阅读题(本大题共小题,每小题分,共2分)

30.顺序表类型定义如下:

 define Li  tSize 100t    f struct {

n d a[L stS  e ;in lngth

}  is t;

阅读下列算法,并回答问题:vi f0(SeL st L)

{ int i  i0;

wh  e( L->lengt)if (L->d a[i]%2! )

{ for(j=i1 j<L-leg ; j++ }

L->aa j-1]L-> ta[ ] 

L>length

}el  e i++

}

1)若L->dat 中的数据为22,4 63,0 15,29,4, ,3 ,则执行上述算法后L->dat中的数据以及L-> ngth的值各是什么

(2该算法的功能是什么

31.有向图的邻接矩阵类型定义如下:

#defne MVN 100 ∥最大顶点数typ e d e int Typ  ∥边上权值类型typedef strut{

ETyp e dg e s MVN][M VN]  ∥邻接矩阵,即边表

nt n; ∥ 图的顶点数

}MGaph; ∥ 图类型

例如一个有向图的邻接矩阵如下所示:

A

阅读下列算法并回答问题

Vi 31(Graph G

{

    ,j,k=0

Step 1:

 r ( =  <G.; i+)for (j0; j<G n j+)

i (. dges[i][j]==1 k++;pri  f(“ n”,k);step2for (j=0; j<G.n j++)

{ k=0;

or (i=0; i<G.n j)if (G.  ges[   [j]= 1) +;pritf “%d n”,k ;



}

(  )step到s  p2之间的二重循环语句的功能是什么?

(2  tep2之后的二重循环语句的功能是什么

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

od  2( ntr ], int n)

{

I   ,j;fo ( =2 i<n;i++

{  0]= [i ;ji-l;wil (  [  ]r[j])

{ r[l]=r[j];j=j-1;



 [l]=r 0];



}

  )这是哪一种插入排序算法?该算法是否稳定?

(2)设置r[0的作用是什么?

3.顺序表类型定义如下:

ypedef nt SeLi   [100 ;

阅读下列算法,并回答问题:vod f33 SeL st r, n n)

 in a, ,  ;if (r[0]< [1]

{ a=r 0 ;b=r[1]; >els e { a=r[1 ; b=[0 ; fo ( 2;i<n; ++)if (r[  ]) ar[i];el  e if ( [i]>b b=r[i] pritf("a=,=%d。    ,b);

}

 1)给出该算法的功能;

2)给出该算法的时间复杂度。

五、算法设计题(本题10分)

 .二叉树的存储结构类型定义如下ty def struct noe{it a  s truc  od *lc hild * cild;

}BnNode;

ypdef Bnde *inTree

编写递归算法,求只有一个孩子结点的结点总数,并计算这些结点的数据值的和。函数的原型为:vod f34(Binre 

* o unt和*sm的初值为 。