2025年自考数据结构历年考题综合答案

JO

I.若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储构造为（）

A.次序存储构造B.链式存储构造

C.索引存储构造D.散列存储构造

2.在长度为n的次序表的第i（lWiWn+1）个位置上插入一种元素，元素的移动次数为（）

A.n-i+1B.n-i

C.iD.i-1

3.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储构造为（）

A.次序表B.用头指针表达的单循环链表

C.用尾指针表达的单循环链表D.单链表

4.若进栈序列为a,b,c,则通过入出栈操作也许得到的a,b,c的不一样排列个数为（）

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

5.一棵有16结点的完全二叉树，对它按层编号，则对编号为7的结点X,它的双亲结点及右孩子结点的编号分别

为（）

A.2,14B.2,15

C.3,14D.3,15

6.设有一5阶上三角矩阵A[1..5,1..5],现将其上三角中的元素按列优先次序寄存在一堆数组B口..15]中。已

知B[1]的地址为100,每个元素占用2个存储单元，则A[3,4]的地址为（）

A.116B.118

C.120D.122

7.一种带权的无向连通图的最小生成树（）

A.有一棵或多棵B.只有一棵

C.一定有多棵D.也许不存在

8.下列有关图遍历的说法中不对的的是（）

A.连通图的深度优先搜索是一种递归过程

B.图的广度优先搜索中邻接点的寻找具有“先进先出”的特性

C.非连通图不能用深度优先搜索法

D.图的遍历规定每一顶点仅被访问一次

9.某算法的空间花费s（n）=2n+ni0°+nlog2n+n®,则其空间复杂度为（9

,<x）101n

A.O（nlog2n）B.O（n）C.O（n）D.O（2）

10.单链表中的存储密度一定（）o

A.不不小于0.5B.等于1C.不小于0.1D.不不小于I

11.在次序栈中删除一种元素，至少要移动（）元素。

A.0B.IC.n/2D.n

12.空串是（）。

A.只包括空格符的串B.长度为0的串

C.只包括一种空格符的串D.不含字母的串

13.采用三元组表存储稀疏矩阵，是为了（）。

A.节省存取时间B.节省存储空间

C.提高对矩阵元素的访问速度D.提高对矩阵运算的可靠性

14.高度为h的二叉树最多有（）个节点。

A.2h-lB.2hC.2h-'D.2h,+l

15.N个顶点，e条边的无权有向图的邻接矩阵中非零元素有（）个。

A.nB.n-eC.eD.e+n

16.直接选择排序在最佳状况下的时间复杂度是（）。

A.O（n）B.O（nlog2n）C.0（1）D.O（n2）

17.N个结点的m阶B树至少包括（）个关键字。

A.（m-l）*nB.nC.（「m/2」-l）*（n-l）+lD.n*[m/2j-1）

18.在散列文献中，同一种桶内的所有记录应当具有（）。

A.相似的关键字B.相似的散列值

C.相似的某个属性值D.相似的存取频率

19.在最坏的状况下，查找成功时二叉排序树的平均查找长度（）

A.不不小于次序表的平均查找长度B.不小于次序表的平均查找长度

C.与次序表的平均查找长度相似D.无法与次序表的平均查找长度比较

20.散列表中由于散列到同一种地址而引起的“堆积”现象，是由（）

A,同义词之间发生冲突引起的

B.非同义词之间发生冲突引起的

C.同义词之间或非同义词之间发生冲突引起的

D.散列表“溢出”引起的

二、填空题（每空1.5分，计15分）

21.ALV树是一种平衡的二叉排序树，树中任一结点的（）

22.在VSAM文献的控制区间中，记录的存储方式为（）

23.单链表的存储密度（）次序表的存储密度，

24.设SQ是循环队列，存储在数组D[M]中，则SQ入队操作对其队尾指针rear的修改是

（）。

25.长度为n的串si与长度为2n的串s2的比较运算的时间曳杂度是（）。

26.广义表（（（a,b,c）,d,eQ）的长度是（）。

27.N（n>0）个节点的哈夫曼树恰含（）个度为1的节点。

28.深度为n的二叉树至少有（）个结点。

29.N（n>0）个顶点的连通有向图至少有（）条边。

30.对N（n>0）个记录进行冒泡排序，至少要互换（）记录。

三、简答题（每题5分，计30分）

31.给出下面森林对应的二叉树及二叉树的后续序列。（图1）

0

32.一棵树有3度节点100个，2度节点200个，该树有叶子节点多少个，该树可以有多少个度为1的节点？

33.设有广义表A,A=（（（a,b）,x）,（（a）,（b））,（c,（d,（y））））,写出由A得到y的对广义表A的操作序列。

34.画出用普里姆算法构造下面所示带权无向图的最小生成树的示意图。

（图2）

35.写出下列用快排序对下列序列进行两次划分的过程及成果。

3726514877698221171321395518

36.画出对下面的5阶B树插入关键字37后的成果。

四、理解设计题(每题5分，计15分)

37.设某带头结头的单链表的结点构造阐明如下：

typedefstructnodel{intdata;structnodel*next;Jnode;

试设计一种算法：voidcopy(node*head1,node*head2),将以headI为头指针的单链表复制到一种不带有头结点

且以head2为头指针的单链表中。(5分)

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

(1)该算法采用何种方略进行排序？

(2)算法中R[n+1]的作用是什么？

typedefstruct{KeyTypekey;infbTypeotherinfo;)nodeType;

typedefnodeTypeSqList[MAXLEN];

voidsort(SqListR,intn){//n不不小于MAXLEN-1

intk;i;

fbr(k=n-l;k>=l;k-)

if(R[k].key>R[k+l].key){

R[n+l]=R[k];

for(i=k+l;R[i].key<R[n+l].key;i++)R[i-l]=R[i];

R[i-l]=R[n+l];

))

39.下面函数Bininsert的功能是对线性表R的前n个元素实现二分法插入排序。请在空缺处填入合适的语句，使

其可以对的工作。

TYPEDEFSTRUCTNODE{INTKEY;/*OTHERINFO*/}NODE;

TYPEDEFNODESEQLIST1100];

VOIDBININSERT(SEQLISTR,INTN)

{INTLOW,UP,MID,I,J;

NODET;

FOR(I=0;I<N;I++)

{⑴；

LOW=0;⑵;

WHILE(LOW<UP)

{MID=(L0W+UP)/2;

IF(RIMID].KEY==T.KEY){(3);BREAK;}

IF(T.KEY<R[MID].KEY)(4);ELSE(5);

)

FOR(J=I;J>LOW;J-)R[J]=R[J-1];

(6)；

五、算法实现题（共io分）

40.假设二叉树T采用如下定义的存储构造：

typedefstructnode{DataTypedata;structnode*lchild,*rchild,"parent;JPBinTree;

其中，结点的Ichild域和rchild域已分别填有指向其左、右孩子结点的指针，而parent域中的值为空指针（拟作为

指向双亲结点的指针域）.请编写一种递归算法,将该存储构造中各结点的parent域的值修改成指向其双亲结点的指

针。

一.单项选择题

1.D2.B3.C1.B5.D6.C7.B8.D9.D10.D

II.A12.BI3.B14.A15.C16.A17.C18.B19.C20.B

二.填空题

21.左右子树树高之差的绝对值不不小于123.不不小于24.sq->rear=(sq->rear+l)%m25.0(n)26.127.0

28.n29.n30.0

三.简答题

31.

GFEDCBJIKHA

32、n0=n2+2n3+l

=200+2*100+1

=401

33、Tail(Head(Tail(Head(Tail(Tail(A)))))=(y)

36、

四.阅读理解题

37、一边遍历，一边申请新结点，链接到head2序列中。

38、直接插入排序。

哨兵。防止边界检测，提高程序运行效率。

39、t=R[iJ;up=i-l;

low=mid+l;up=mid-l;）ow=mid+l;

RllowJ=t;

1.某算法的空间花费s（n）=2n+nm+nlog2n+n叫则其空间复杂度为（）。

,（x）101n

A.O（nlog2n）B.O（n）C.O（n）D.O（2）

2.单链表中的存储密度一定（）o

A.不不小于0.5B.等于1C.不小于0.1D.不不小于1

3.在次序栈中删除一种元素，至少要移动（）元素。

A.0B.1C.n/2D.n

4.空吊是（）o

A.只包括空格符的串B.长度为0的串

C.只包括一种空格符的串D.不含字母的串

5.采用三元组表存储稀疏矩阵，是为了()。

A.节省存取时间B.节省存储空间

C.提高对矩冲元素的访问速度D.提高对矩降运算的可靠性

6.高度为h的二叉树最多有()个节点。

A.2h-lB.2hC.2h-*D.2h-'+l

7.N个顶点，。条边的无权有向图的邻接矩阵中非零元素有()个。

A.nB.n-eC.eD.e+n

8.直接选择排序在最住状况下的时间复杂度是()。

A.0(n)B.O(nlog2n)C.0(1)D.0(n2)

9.N个结点的m阶B树至少包括()个关键字。

A.(m-l)*nB.nC.(Fm/2J-l)*(n-l)+lD.n*fm/2j-1)

10.在故列文献中，同种桶内的所有记录应当具有()。

A.相似的关键字B.相似的散列值

C.相似的某个属性值D.相似的存取频率

11.某算法的时间花费T(n)=0.05n2+100n+10,则该算法的时间复杂度为()。

12.单链表的存储密度()次序表的存储密度。

13.设SQ是循环队列，存储在数组D[M]中，则SQ入队操作对其队尾指针rear的修改是()。

14.长度为n的串si与长度为2n的串S2的比较运算的时间复杂度是()。

15.广义表(((a,b,c),d,e,。)的长度是()。

16.N(n>0)个节点的哈夫曼树恰含()个度为1的节点。

17.深度为n的二叉树至少有()个结点。

18.N(n>0)个顶点的连通有向图至少有()条边。

19.对N(n>0)个记录进行冒泡排序，至少要互换()记录。

20.倒排文献的每个倒排表项包括()和记录地址。

21.给出下面森林对应的二叉树及二叉树的后续序列。(图1)

22.一棵树有3度节点100个，2度干点200个，该树有叶子节点多少个，该树可以有多少个度为1的节点？

23.设有广义表A,A=(((a,b),x),((a),(b)),(c,(d,(y)))),写出由A得到y的对广义表A的操作序列。

24.设有程序：

intf(inta1],intn,intkey)

{inii;

for(i=0;i<n;i++)

if(a[i]==key)returni;

return-1;

)

若key在叫](j=012…n-1)中的概率为key不在a中的概率为2川，那么查找Key时平均比较Key的次数是多

少，该算法的时间复杂度是多少？

25.画出用普里姆算法构造下面所示带权无向图的最小生成树的示意图。

(图2)

3

四、理解题(每题6分，计12分)

26.指出下面函数GV的功能及其返回值的含义。其中，Tab是存储稀疏矩阱A的并零元素的长度为LEN的三元组

表。

INCLUDE<STDIO.H>

TYPEDEFSTRUCT{INTROW,COL,VAL;}TRITUPLENODE;

INTGV(INTLINTJ,INTLEN.TRITUPLENODETAB[])

{INTK;

FOR(K=0;K<LEN;K++)

IF(TAB[K].ROW==I&&TABIK].COL==J)RETURNTAB[KJ.VAL;

RETURN0;

)

27.设Pl和P2是两个单链表，他们的元素都递增有序，指出下面函数F的功能。

TYPEDEFINTDATATYPE;

TYPEDEFSTRUCTNODE{DATATYPEDATA;STRUCTNODE*NEXT;}LiSTNODE;

TYPEDEFLISTNODE*LINKLIST:

UNKLISTF(LINKLISTPIJJNKLISTP2)

{LINKLISTH=NULL.P:

WHILE(P1&&P2)

{IF(P1->DATA<P2->DATA){P=PI;P1=P1->NEXT;}

ELSE{P=P2;P2=P2->NEXT;}

P->NEXT=H;H=P;

)

WHII.E(Pl){P=P1；P1=P1->NEXT;P->NEXT=H;H=P;}

WHILE(P2){P=P2;P2=P2->NEXT:P->NEXT=H:H=P:}

RETURNH;

)

五、填充题(每题18分)

28.下面函数Bininsert的功能是对线性表R的前n个元素实现二分法插入排序。请在空缺处填入合适的语句，使其

可以对的工作。

TYPEDEFSTRUCTNODE{INTKEY;/*OTHERINFO*/}NODE;

TYPEDEFNODESEQLIST[100];

VOIDBININSERT(SEQLISTRJNTN)

{INTLOW,URMID,I,J;

NODET;

FOR(I=0;I<N;I++)

{(1):

LOW=0;⑵；

WHILE(LOW<UP)

{MlD=(LOW+UP)/2;

IF(RfMID].KEY==T.KEY){(3):BREAK;}

IF(T.KEY<RIMID].KEY)(4);ELSE(5);

)

FOR(J=I;J>LOW;J-)R[J]=RfJ-l];

(6)；

D

一、单项选择题

l.D2.D3.A4.B5.B6.A7.C8.D9.C10.B

二、填空题(每题2分，共30分)

11.0(/)12.不不小于13.rear=(rear+l)%m14.0(n)15.116.017.nl8.n19.020.次关键

字

三、简答题

21、(见下图)后序序列GFEDCBJIKHA

22、叶结点有401个，度为1的结点可以有任意多种。

24、平均比较次数=1*23)+2*2一“川+……

-2-2'(n',)-n*2'n

时间复杂度为：0(1)

25、见图。

25题

四、理解题

26、在三元组表Tab中，查找稀疏矩阵中元素A[I,J]的值，并把此值作为函数的返回值。

27、把两个递增有序的单链表合并为一种递减有序的单链表。

五、填充题

t=R[i];up=i-llow=mid+1

up=mid-llow=mid+1R[low]=t

-10

一、单项选择题(本大题共15小题，每题2分，共30分)在每题列出的四个选项中只有一种选项是符合题目规定的，请

将对的选项前的字母填在题后的括号内。

1.若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储构造为()

A.次序存储构造B.链式存储构造

C.索引存储构造D.散列存储构造

2.在长度为n的次序表的第i(lWiWn+1)个位置上插入一种元素，元素的移动次数为()

A.n-i+1B.n-i

C.iD.i-1

3.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储构造为()

A.次序表B.用头指针表达的单循环链表

C.用尾指针表达的单循环链表D.单链表

4.若进栈序列为a,b,c,则通过入出栈操作也许得到的a,b,c的不一样排列个数为()

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

5.为查找某一特定单词在文本中出现的位置，可应用的串运算是()

A.插入B.删除C.串联接D.子串定位

6.已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,l)的功能为复制串I到s。若字

符串S="SCIENCESTUDY”,则调用函数Scopy(P.Sub(S』,7))后得到()

A.P=〃SCIENCE,zB.P="STUDY

C.S=〃SCIENCE/zD.S二〃STUDY”

7.三维数组AMH5][6]按行优先存储措施存储在内存中，若每个元素占2个存储单元，且数组中第-种元素的存储地

址为120,则元素A[3][4]⑸的存储地址为（）

A.356B.358C.360D.362

8.如右图所示广义表是一种（）

A.线性表

B.纯表

C.结点共享表

D.递归表

题8图

9.下列陈说中对的的是（）

A.二叉树是度为2的有序树

B.二叉树中结点只有一种孩子时无左右之分

C.二叉树中必有度为2的结点

D.二叉树中最多只有两棵子树，并且有左右之分

C.452I3

D.42315

14.ALV树是一种平衡的二叉排序树，树中任一结点的（）

A.左、右子树的高度均相似B.左、右子树高度差的绝对值不超过1

C.左子树的高度均不小于右子树的高度D.左子树的高度均不不小于右子树的高度

15.在VSAM文献的控制区间中，记录的存储方式为（）

A.无序次序B.有序次序

C.无序链接D.有序链接

二、填空题（本大题共1（）小题，每题2分，若有两个空格，每个空格1分，共20分）

16.若一种算法中的语句频度之和为T（n）=3720n+4nlogn,则算法的时间复杂度为。

17.在如图所示的链表中，若在指针p所指的结点之后插入数据域值相继为a和b的两个结点，则可用下列两个语句实

现该操作，它们依次是和。

H——

题17图

18.假设以S和X分别表达进栈和退栈操作，则对输入序列a,b,c,d.e进行•系列栈操作SSXSXSSXXX之后，得到的输

出序列为o

19.串S='Iamaworker"的长度是。

20.假设一种10阶的下三角矩阵A按列优次序压缩存储在一维数组C中，则C数组的大小应为。

21.在n个结点的线索二叉链表中，有个线索指针。

22.若采用邻接矩阱构造存储具有n个顶点的图，则对该图进行广度优先遍历的算法时间复:杂度为.

23.对关键字序列(52,80,63,44,48,91)进行一趟迅速排序之后得到的成果为。

24.由10000个结点构成的二叉排序树，在等概率查找的假设下，查找成功时的平均查找长度的最大值也许到达

25.若要找出所有工资低于1500元，职祢是副专家，及所有工资低于元，职称是专家的记录，则查询条件是o

三、解答题(本大题共4小题，每题5分，共20分)

26.已知一种6行5列的稀疏矩阵中非零元的值分别为：-90,41,-76,28,-54,65和-8,它们在矩阵中的列号依次为:

1,4,5,1,2,4和5。当以带行表的三元组表作存储构造时，其行表RowTab中的值依次为0,0,2,2,3和5。

请写出该稀疏矩阵(注：矩阵元素的行列下标均从1开始)。

27.己知树T的先序遍历序列为ABCDEFGHIJKL,后序遍历序列为CBEFDJIKLHGAo请画由树T。

28.对关键字序列(72,87,61,23,94,16,05,58)进行堆排序，使之按关键字递减次序排列。请写出排序过程中得

到的初始堆和前三趟的序列状态。

初始堆：第1趟：

第2趟：第3趟：

29.在关键字序列(07,12,15,18,27,32,41,92)中用二分查找法查找和给定值92相等的关键字，请写出查找过程

中依次和给定值“92”比较的关键字。

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

30.如下函数中，h是带头结点的双向循环链表的头指针。

(1)阐明程序的功能；(2)当链表中结点数分别为1和6(不包括头结点)时，请写出程序中while循环体的执行次数。

intf(DListNodc*h)q=h->prior;q=q->prior;

(while(p!=q&&p->prior!=q))

DListNodc*p,*q;if(p->data==q->data)elsej=0;

intj=l;returnj;

p=h->next;p=p->next;)

31.设栈S=(1,2,345,6,7),其中7为栈顶元素。请写出调用algo(&s)后栈S的状态。

voidalgo(Stack*S)

{inti=0;

QueueQ;StackT;

InitQueue(&Q);InitStack(&T);

while(!S(ackEmpty(S))

(

if((i=!i)!=0)Push(&T,Pop(&S)):

elseEnQueue(&Q.Pop(&S));

)

while(!QueueEmpty(Q))

Push(&S,DcQueue(&Q));

while(!StackEmpty(T))

Push(&S,Pop(&T))；}

32.已知带权图的邻接矩阵表达和邻接表表达的形式阐明分别如下:

#dcfincMaxNum50〃图的最大顶点数inin,e;〃图中目前的顶点数和边数

#defineINFINITYINT_MAX//INT.MAX为最大整}MGr叩h;〃邻接矩阵构造描述

数，表达8typedefstructnode{

typedefstruct{imadjvex;//邻接点域

charvexs[MaxNum];〃字符类型的顶点表intweightJ/边的权值

intedges[MaxNum][MaxMum];〃权值为整型的邻接structnode*nexl;〃链指针域

矩阵}EdgeNode;〃边表结点构造描述

typedefstruct{typedefstruct{

charvertex;〃顶点域VerexNodeadjlisl[MaxNum];〃邻接表

EdgeNode*firstedge;〃边表头指针int1）©〃图中目前的顶点数和边数

}VertexNode;〃顶点表结点构造描述}ALGraph;〃邻接表构造描述

下列算法是根据一种带权图的邻接矩阵存储构造G1建立该图的邻接表存储构造G2,请填入合适的内容，使其成为一

种完整的算法。

voidcon\ertM(MGraph*G1,ALGraph*G2)(1)该算法采用何种方略进行排序？

{皿i,j；(2)算法中R[n+I]的作用是什么？

EdgeNode*p;Typedefstruct{

G2->n=Gl->n;KeyTypckey;

G2->e=G1->e;infoTypeolherinfo;

fur(i=O;i<Gl->ii;i++)}nodcTypc;

{typedefnodeTypeSqList[MAXLEN];

G2->adjlist[i].vertex=G1->vexs[i];voidsort(SqListR.intn)

G2->adjlist[il.firstedge=⑴;{

)Z/n不不小于MAXLEN-1

for(i=0;i<Gl->n;i++)intk:i.

for(j=O;j<G1->n;j++)for(k=n-1;k>=1;k—)

if(G1->edges[i][j]<INFINITY)if(R[k].key>R[k+l].key)

{p=(EdgeNode*)malloc(sizeof(EdgeNode));(

p->weight=(2):R|n+lJ=R|kJ;

p->adjvcx=j;for(i=k+l;R[i].kcy<R(n+l].kcy;i++)

p->next=G2->adjlist|i].firstedge;Rn-H=R[i]；

⑶：R[i-l]=R|n+l];

}}1

33.阅读下列算法，并回答问题：)

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

34.假设二叉树T采用如下定义的存储构造：

typedefstructnode!

DataTj^pedata;

structnode*lchild,*rchild,*parent;

}PBir.Tree;

其中，结点的Ichild域和「child域已分别填有指向其左、右孩子结点的指针，而parent域中的值为空指针（拟作为指

向双亲结点的指针域）。请编写一种递归算法，将该存储构造中各结点的parent域的值修改成指向其双亲结点的指针。

一.单项选择题

I.D2.A3.A4.B5.D-9041

6.A7.A8.C9.D10.D

ILA12.B13.A14.B15.D-76

二.填空题2854

16.O(nlogn)17.b->next=p->ncxt;p->ncxt=s;

65-8

18.bceda19.14

20.4621.n+l

22.0(n2)23.48,44,82,63,80,91

24.(10000+1)/2

25.职称="副专家”and工资<1500or职称="专家”andand工资<

三.简答题

26.

27.由于树的后序序列就是等价二叉树的中序遍历序列，因此先得到等价二叉树，然后转化为对应的树。

等价二叉树最终结果树

28.初始堆:05,23,16,58,94,72,61,87第趟：16,23,61,58,94,72,87,05

第二趟：23,58,61,87,94,72,16,05第三趟：58,72,61,87,94,23,16,05

29.18324192

四.算法阅读题

30.(1).检查循环链表中头结点两端对应位置处的结点值与否对称相等。

(2).当结点个数为1时，循环次数为0次。

当结点个数为0时，循环次数为3次。

31.7531246(7为栈顶)(3)G2->adjlist[i].firstedge=p

32.(1)NULL33.(I)从右侧进行的直接插入排序

(2)Gl->edgesli]|jJ(2)R[n+lJ的作用为哨兵

五.算法设计题

34.BintreeNode*pre;pre=NULL;

voidxiugai(BinTrcc*T)

{if(T)

{xiugai((*T)->lchild);

(*T)->parent=pre;

pre=(*T);

xiugai((*T)->rchild);

})

.10

1.下列说法对的的是()

A,数据是数据元素的基本单位

B.数据元素是数据项中不可分割的最小标识单位

C.数据可由若干个数据元素构成

D.数据项可由若干个数据元素构成

2.数据构造的基本任务是()

A.逻辑构造和存储构造的设计B.数据构造的运算实现

C.数据构造的评价与选择D.数据构造的设计与实现

3.在一种具有n个结点的有序单链表中插入一种新结点，并使插入后仍然有序，则该操作的时间复杂性量级为()

A.O(1)B.O(n)

C.O(nlog2n)D.O(n2)

4.次序存储的线性表(a/2,…,所)，在任一结点前插入一种新结点时所需移动结点的平均次数为()

A.nB.n/2

C.n+1D.(n+l)/2

5.下列树U',经剪枝运算DELETE(U'，x,2)后为()

怎

A.B.⑥C.

‘%

①

©

6.棵有16结点的完全二叉树,对它按层编号，则对编号为7的结点X,它的双亲结点及右孩了结点的编号分别为

）

A.2,14B.2,15

C.3,14D.3,15

7.设有一5阶上三角矩阵A[1..5,L.5],现将其上三角中的元素按列优先次序寄存在一堆数组B[1..15]中。已知B

[1]的地址为100,每个元素占用2个存储单元，则A[3,4]的地址为（)

A.116B.118

C.120D.122

8.一种带权的无向连通图的最小生成树（)

A.后一棵或多棵B.只有一棵

C.一定有多棵D.也许不存在

9.下列有关图遍历的说法中不对的的是（)

A.连通图的深度优先搜索是一种递归过程

B.图的广度优先搜索中邻接点的寻找具有“先进先出”的特性

C.非连通图不能用深度优先搜索法

D.图的遍历规定每一顶点仅被访问一次

10.在最坏的状况下，查找成功时二叉排序树的平均查找长度（)

A.不不小于次序表的平均查找长度B.不小于次序表的平均查找长度

C.与次序表的平均查找长度相似D.无法与次序表的平均查找长度比较

11.闭散列表中由于散列到同一种地址而引起的“堆积”现象，是由（)

A.同义词之间发生冲突引起的

B.非同义词之间发生冲突引起的

C.同义词之间或非同义词之间发生冲突引起的

D.散列表“溢出”引起的

12.从外存设备的观点看，存取操作的基本单位是（)

A.逻辑记录B.数据元素

C.文献D.物理记录

13.对文献进行检索操作时.，每次都要从第一种记录开始的文献是（)

A.次序文献B.索引文献

C.次序索引文献D.散列文献

14.一组记录的键值为(46,74,18,53,14,20,40,38,86,65),运用堆排序的措施建立的初始堆为（)

A.(14,18,38,46,65,40,20,53,86,74)

B.(14,38,18,46,65,20,40,53,86,74)

C.(14,18,20,38,40,46,53,65,74,86）

D.(14,86,20,38,40,46,53,65,74,18）

15.对序列(22,86,19,49,12,30,65,35,18）进行一趟排序后得到的成果如下：（18,12,19,22,49,30,

65,35,86）,则可以认为使用的排序措施是)

A.选择排序B.冒泡排序

C.迅速排序D.插入排序

二、填空题(本大题共13小题，每空2分，共26分)

请在每题的空格中填上对的答案。错填、不填均无分。

16.表达逻辑关系的存储构造可以有四种方式，即次序存储方式、链式存储方式、

---------------和散列存储方式。prior]dala|ne；,

17.设某非空双链表，其结点形式为若要删除指针q所指向的结点，则需执行下述

语句段：q->prior->next=q->next;。

18.如图所示，设输入元素的次序是A,B,C,D,通过栈的变换，在输出端可得到多种排列。若输出序列的第一种

元素为D,则输出序列为o

_________ARCD

输窈端输入端

栈

19.队歹।.中容许进行删除的一端为。

20.设一棵二叉树中度为2的结点数为10,则该树的叶子数为_______________o

21.如图所示的二叉树，若按后根遍历，则其输出序列为0/③、

⑥、©

22.一种具有n个顶点的有向完全图的弧数为。%⑥/

23.查找表的数据构造有别于线性表、树型构造等，其逻辑构造为。黔/\

24.长度为L的次序表，采用设置岗哨方式次序查找，若查找不成功，其查找长度为1/©

&

Q

25.在开散列表上查找某元素时，一般分两步进行，首先必须计算该键值的散列地址，然后在地址指针所指

中杳找该结点。

26.文献的检索有次序存取、和按关键字存取三种方式。

27.在待排序的n个记录中任取一种记录，以该记录的键值作为原贝!，将所有记录分为两组，使得第一组中各记录的

键值均不不小于或等于该键值，第二组中的各记录的键值均不小于该键值；然后将该记录排在两组中间。再对所提

成的两组分别使用上述措施，直到所有记录都排在合适位置为止。这种排序措施称为o

28.在对一组记录关键字(54,38,96,23,15,72,60,45,83)进行冒泡排序时，整个冒泡排序过程中需进行

趟才能完毕。

三、应用题(本大题共5小题，共30分)

29.设有一次序队列sq,容量为5,初始状态时.sq.fron『sq.rear=0,面出做完下列操作后队列及