全国自考（数据结构）模拟试卷1（共310题）

全国自考(数据结构)模拟试卷1(共9

套)

（共310题）

全国自考(数据结构)模拟试卷第1套

一、单项选择题(本题共万题，每题1.0分，共15

分。)

1、堆排序的最坏时间复杂度为()

A、O(n)

B、O(10g2n)

C^O(nlog2n)

D、O(n2)

标准答案：C

知识点解析：暂无解析

2、对广义表((a),(b))进行下面的操作head(head((aj,(b)))后的结果是()

A、a

B、(a)

C、()

D、不确定

标准答案：A

知识点解析：暂无解析

3、已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,则它的前序遍

历序列是()

A、acbed

B、decab

CNdeabC

D、cedba

标准答案：D

知识点解析：暂无解析

4、判断一个有向图是否存在回路，除了可以利用拓扑排序方法，还可以利用()

A、求关键路径的方法

B、求最短路径的Dijksira方法

C、广度优先遍历方法

D、深度优先遍历方法

标准答案：D

知识点解析：暂无解析

5、将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到

下、从左到右的顺序对结点编号，那么编号为41的结点的双亲结点编号为()

A、42

B、40

C、21

D、20

标准答案：D

知识点解析：暂无解析

6、设数组A|0,m|作为循环队列sq的存储空间，from为队头指针，rear为队尾指

针，则执行入队操作的语句是()

A、sq.front=(sq.front+1)%m

B、sq.front=(sq.front+1)%(m+1)

C、sq.rear=(sq.rear+1)%rn

D、sq.rcar=(sq.rcar+1)%(m+1)

标准答案：D

知识点解析：暂无解析

7、如果T2是由有序树T转换而来的二叉树，那么T中结点的后序就是T?中结点

的()

前序

A、

中序

B、

后序

、

C层次

D、

标准答案：B

知识点解析：暂无解析

8、链栈与顺序栈相比，有一个比较明显的优点即()

A、插入操作更加方便

B、通常不会出现栈满的情况

C、不会出现栈空的情况

D、删除操作更加方便

标准答案：B

知识点解析：暂无解析

9、串是任意有限个（）

A、符号构成的集合

B、符号构成的序列

C、字符构成的集合

D、字符构成的序列

标准答案：D

知识点解析：暂无解析

10、堆是一个键值序列（ki，k2,k…，ki…，ko）,对仁1,2...,[n/2],满足（）

A、kj<k2i<k2i+1

B、ki<k2i〈k2i+l

C^kj<k2i且k<k2i+l（2i+l<n）

D、ki<k2i或kj<k2i+l（2i+l<n）

标准答案：C

知识点解析：暂无解析

11、带头结点的单链表Head为空的判定条件是（）

A、Head=NULL;

Headt.next=NULL;

C、Hcad|.ncxtHcad;

D、Headt.next=Headt

标准答案：B

知识点解析：暂无解析

12、如果待排序的记录的规模很大，则在下面的排序方式中，我们最好不要选择使

用（）

A、快速排序

B、直接插入排序

C、堆排序

D、归并排序

标准答案：B

知识点解析：暂无解析

13、串是一种特殊的线性表，其特殊性体现在（）

A、可以顺序存储

B、数据元素是一个字符

C、可以链接存储

D、数据元素可以是多个字符

标准答案：B

知识点解析：暂无解析

14、线性表若采用链表存储结构时，要求内存中可用存储单元的地址（）

A、必须是连续的

B、部分地址必须是连续的

C、一定是不连续的

D、连续不连续都可以

标准答案：D

知识点解析：暂无解析

15、假设有一个数组，它的行号从。到8,列号从。到10,数组中每个元素所占的

存储空间为3个单元，则现在将此数组从某一个地址开始连续存放在一个存储器

中，试问至少需要（）个存储单元才能完全将此数组存放进去。

A、240

B、297

C、270

D、300

标准答案：B

知识点解析：暂无解析

二、填空题（本题共10题，每题1.0分，共10分。）

16、在索引顺序文件中需建立一张指示逻辑记录和物理记录之间的一一对应关系的

o它通常采用结构来组织。

标准答案：索引表树

知识点解析：暂无解析

17、数组-2..6,2..8］以行优先顺序存储，设第一个元素的首地址是100,

每个元素占3个存储长度的存储空间，则元素A［5,0,7］的存储地址为o

标准答案:913

知识点解析：暂无解析

18、对磁带上的顺序文，‘牛进行更新某个记录时，必须_____整个文件。而在顺序文

件的最后添加新的记录时，则不必整个文件。

标准答案：复制复制

知识点解析：暂无解析

19、若二叉树的一个叶子是果子树的中序遍历序列中的第一个结点，则它必是孩子

树的后序遍历序中的个结点。

标准答案：第一

知识点解析：暂无解析

20、文件的记录均存放在数据集中，数据集中的一个结点称为,它是一个

操作的基本单位。

标准答案：控制区间I/O

知识点解析：暂无解析

21、设线性表L=(ai，a2,a„)(n>2),表中元素按值的递增顺序排列。对一个

给定的值k,分别用顺序检索和二分法检索查找与k相等的元素，比较次数分别为

s和b,若检索不成功，则s和b的数量关系是_____o

标准答案：s>b

知识点解析：暂无解析

22、在按照顺序存储方式存储的数组中，元素aij的存储地址应该是数组的

加上排在aij前面的元素所占用的单元数。

标准答案：基地址

知识点解析：暂无解析

23、______查找法的平均查找长度与元素个数n无关。

标准答案：散列表

知识点解析：暂无解析

24、在计算机软件系统中，有两种处理字符串长度的方法：一种是采用,第

二种是设置_____。

标准答案：固定长度长度指针

知识点解析：暂无解析

25、在顺序队列中，应该有队头和队尾两个指针来指示，队头指针和队尾指针的初

值在队列的初始化时均应该设置为,当对队列进行插入和删除的操作后，如

果头指针和尾指针相等时，队列为。

标准答案：0空

知识点解析：暂无解析

三、解答题(本题共5题，每题7.0分，共5分。)

26、已知一棵二叉树的前序遍历序列是ABDGCEFH,其中序遍历序列为

DGBAECHFo请画出相应的二叉树，并求出对应此.二叉树的后序遍历序列，此二

义树是完全二叉树吗?完全二义树有什么性质(特点)？

标准答案：根据二叉树的遍历规则，前序遍历总是先访问根结点，然后依次遍历其

左右子树，而中序遍历规则是先遍历左子树，再访问根结点，然后访问右子树，则

由以上规则，我们极易得出此二叉树的根结点是A,中序遍历序列中，根结点左右

两边的结果分别属于其左、右子树，所以得出左子树包含3个节点：B,D,G,

右子树包含四个结点C,E,F,Ho在左子树中，先序遍历序B位于最前，而中序

遍历序列中，B位于最后，则可以得出结点B无右子树，只有左子树，乂在B的

子树中，无论先序遍历还是中序遍历，D都位于G的前面，则G只能是D的石孩

知识点解析：暂无解析

27、已知有一关键字序列为{97,86,53,108,72,34,215,146,11,68},如果我们采用直接

选择排序方法对此序列进行排序（按照升序排列），请给出每一趟的排序结果。

标准答案：直接选择排序的过程为：从第i趟开始时，当前的有序区和无序区分别

为R[L..i]和R[L..n]（lS-lgn-l）,则在该趟排序是从当前无序区中选出关键字最小

的记录R[K],将它与无序区中的第1个记录R[i]交换，使R[1…口和R[i+l...n]分别

变成新的有序区和新的无序区，每次排序都使有序区增加一个记录，无序区减少一

个记录，按照以上规则，我们得到各趟结果如下：初始：

97,86,53,108,72,34,215,232,11,68第1趟:11[86,53,108,72,34,215,232

知识点解析：暂无解析

28、造根据下面所给出的邻接矩阵画出相应的有向图或者是无向图（顶点vi表示）。

X)110O'

r0111-

00010

1011

10001

1100

11000

.1100.

一01010•

知识点解析：暂无解析

判别下列二序列是否为唯，如不是，按照对序列建堆的思想把它调整为堆，用图表

示建堆的过程。

29、(1,5,7,25,21,8,8,42)

标准答案：为堆；

知识点解析：暂无解析

30、(3,9,5,8,4,17,21,6)

四、算法阅读题(本题共4题，每题1.0分，共4分0)

31、以下算法假定以线性探测法解决冲突，在闭散列表HL中查找键值为K的结

点，成功时回送该位置；不成功时回送标志请分析程序，并在_____上填充合

适的语句。intsearch_closehash(keyt,ypeK,closehashHL){d=H(K);/*计算散列地址

*/i=d;vvhilc(HL[i].kcy!=K&&(i!=d-1)i=;)/*未成功且未查遍整个HL时继续

扫描*/if()relum(i);/*查找成功*/elseretum(-l);/*查找失败*/)

标准答案：(i+l)/mHL[i].key==K

知识点解析：暂无解析

32、以下为单链表的删除运算，分析算法，请在处填上正确的语句。void

delete_lklist(lklisthead,inti){p=find」klist(head,i-l)；if(){q=;p—>

ncxt=q—>ncxt;frce(q);)elseerror("不存在第i个结点")}

标准答案：(p!=NULL)&&(p—>next!=NULL)p—>next

知识点解析：暂无解析

33、以下为顺序表的定位运算，分析算法，请在_____处用正确的语句予以填充。

intlocate_sqlist(sqlistL,datatypeX)/*在顺序表L中查找第一个值等于X的结点介若

找到回传该结点序号；否则回传0*/{；while((i<L.last)&&(L.data[i-

l]!=x))i++;if()return(i);elsereturn(O);}

标准答案：i=li<L.last)

知识点解析：暂无解析

34、以下.为单链表的建表算法，分析算法，请在处填上正确的语句。Iklisl

create_iklist2()/*宜接实现的建表算法。*/{head=malloc(size);p=head;

scanf("%M,&x);while(X!=,$,){q=malloc(size);q—>data=x;p一>next=q;;

scanf("%",&x););retum(head);)此算法的量级为。

标准答案：p=qp—>next=NULL0(n)

知识点解析：暂无解析

五、算法设计题(本题共7题，每题1.0分，共I分。)

35、假设在表示一棵二叉树的二叉链表上增加两个域，双亲域用于指示其双亲结

点，标志域flag(可取，0…2)的值，用以区分在遍历过程中到达该结点时继续向左

或向右或访问该结点。试以此存储结构编写不用栈进行后序遍历的递推形式的算

法。

标准答案：要解答该题必须分析结点所在的状态，这可以通过结点的标志域来进

行。对一个结点来说，当前的结点可能由：(1)其双亲结点转换；(2)其左子树遍历

结束转换；(3)其右子树遍历结束转换。所以算法主要执行按这三种状态进行处理

或处理当前结点切换结点的状态。从而可将算法描述为：voidpostorder(r)/*后序遍

历此二义树*/hitree*t7*设为hitree类型的结点含四人域：flag.parent.Ichild.

rehild,其中flag的域初值为0,指针t指向根结点"/{bitree*P;P=t;while(p!=Null)

switch(—>flag){case0:p—>flag=l;if(p—>Ichild!=Null)p=p—>Iehild;break;

casel:p一>flag=2if(jp->rchild!=Null)p=p—>rchild;break;case2:p—>flag=0;

printf(p—>data);p=jp—>parent;break;default;)}/*postorder*/

知识点解析：暂无解析

全国自考(数据结构)模拟试卷第2套

一、单项选择题(本题共乃题，每题1.0分，共乃

分。)

1、在图的邻接表存储结构上执行深度优先搜索遍历类似于二叉树上的()

A、先序遍历

B、中序遍历

C、后序遍历

D、按层次遍历

标准答案：A

知识点解析：暂无解析

2、已知一个向量的第一个元素的存储地址是loO,每个元素的长度为2,则第6个

元素的地址是（）

A、120

B、112

C、110

D、114

标准答案：C

知识点解析：暂无解析

3、在单链表中，删除p所指结点的直接后继的操作是（）

A、p—>next=p—>next->next;

B、p=p->next;p->next=p->next->next;

C^p—>ncxt=p—>next;

D、p=p—>next—>next;

标准答案：A

知识点解析：暂无解析

4、深度为6（根的层次为1）的二叉树至多有（）个结点。

A、31

B、32

C、63

D、64

标准答案：B

知识点解析：暂无解析

5、设二叉树有n个结点，则其深度为（）

A、n-I

B、n

C、510g2n」十1

D、不确定

标准答案：D

知识点解析：暂无解析

6、在图的邻接表存储结构上执行广度优先搜索遍历类似于二叉树上的（）

A、先根遍历

B、中根遍历

C、后根遍历

D、按层次遍历

标准答案：D

知识点解析：暂无解析

7、一个栈的入栈序列为al,a2,a3,a4,a5,则此栈不可能的输出序列是（）

A、a5,a4,a3,a2,al

a4,a5,a3,a2,al

C、a4,a3,a5,al,a2

D、al,a2,a3,a4,a5

标准答案：C

知识点解析：暂无解析

8、设rear是指向非空带头结点的循环单链表的尾指针，则删除起始结点的操作可

表示为（）

A、s=rcar;

B、rear=rear->next;rear=rear—>next;free(rear);free(s);

C、rear=rear->next->next;

D^s=rcar——>ncxt——>ncxt;frce(rcar);rear——>next—>ncxt=s—>ncxt;frce(s);

标准答案：D

知识点解析：暂无解析

9、以下有关数据结构的叙述，正确的是（）

A、线性表的线性存储结构优于链式存储结构

B、二叉树的第i层上有2i-l个结点，深度为K的二叉树上有2k-l个结点

C、二维数组是其数据元素为线性表的线性表

D、栈的操作方式是先进先出

标准答案：C

知识点解析：暂无解析

10、已知一个单链表中有3000个结点，每个结点存放一个整数，（）可用于解决这

3000个整数的排序问题且不需要对算法作大的变动。

A、直接插入排序方法

B、简单选择排序方法

C、快速排序方法

D、堆排序方法

标准答案：D

知识点解析：暂无解析

11、二维数组M[i,j]的元素是4个字符（每个字符占一个存储单元）组成的串，行下

标i的范围从0到4,列下标j的范围从0到5。M按行存储时元素M[3,5]的起始

地址与M按列存储时元素（）的起始地址相同。

A、M[2,4]

B、M[3,4]

C、M[3,5]

D、M[4,4]

标准答案：B

知识点解析：暂无解析

12、在一棵二叉树中，第k层上最多有（）个结点。

A、2k

B、2k-1

C、2k

D、2k-1

标准答案：D

知识点解析：暂无解析

13、一棵二叉树如图所示，其中序遍历的序列为（）

A、ABDGCEFH

B、DGBAECHF

C、GDBEHFCA

D、ABCDEFGH

标准答案：B

知识点解析：暂无解析

14、设计一个判别表达式中左、右括号是否配对出现的算法，采用（）数据结构最

佳。

A、线性表的顺序存储结构

B、栈

C、队列

D、线性表的链式存储结构

标准答案：B

知识点解析：暂无解析

15、设有一顺序栈S,元素S],S2,S3,S4,S5,S6依次进栈，如果6个元素出栈的

顺序是S2,S3，S4，S5，S6，S1，则栈的容量至少应该是（）

A、2

B、3

C、5

D、6

标准答案：B

知识点解析：暂无解析

二、填空题(本题共10题，每题1.0分，共10分。)

16、在直接插入和直接选择排序中，如果初始数据基本正序，则选用,若初

始数据基本反序，则选用。

标准答案：直接插入排序直接选择排序

知识点解析：暂无解析

17、设一个链栈的栈顶韦针为1s,栈中结点两个字段分别为info和nexl,其中next

是指示后继结点的指针，栈空的条件是______。如果栈不空，则退栈操作为p：

=ls；；dispose(p)o

标准答案：1s=null这是指链栈没有设置头结点的情况，一般情况下也不必设置1s：

=lsf.next：这一操作让头指针指示下一个结点

知识点解析：暂无解析

18、在分块查找法中，首先查找,然后再查找相应的。

标准答案；索引表块

知识点解析：暂无解析

19、对于一个二维数组若按行序为主序存储，则任一元素相对于

A[0][0]的地址为,

标准答案：ixj+i全元素位置

知识点解析：暂无解析

20、在一个按行优先顺序存储的二维数组(MxN)中，假设数组的基地址是P,并且

数组的每一个元素所占的存储空间为d个字节，则ahj的地址计算公式为o

标准答案：LOC(a[ij)=P+[ixN+j]xd

知识点解析：暂无解析

21、对角矩阵中，除了的元素之外，其余的元素都是零。则对于一个k对角

线矩阵(k为奇数)A是满足下面的条件的矩阵：如果,则元素a[ij=O。

标准答案：主对角线和主对角线相临两侧的若干条对角线上i>k或j>k

知识点解析：暂无解析

22、中结点的最大度数允许大于2,而中结点的最大度数不允许大于

2o

标准答案：树二叉树

知识点解析：暂无解析

23、计算机软件系统中，有两种处理字符串长度的方法：一种是采用,第二

种是。

标准答案：固定长度设置长度指针

知识点解析：暂无解析

24、在单链表中，除了首元结点外，任一结点的存储位置是由_____指示“

标准答案：其直接前趋结点的链域的值

知识点解析：暂无解析

25、大多数排序算法都有两个基本操作，它们是______和o

标准答案：比较两个关健字的大小改变指向记录的指针或者移动记录本身

知识点解析：暂无解析

三、解答题（本题共4题，每题分，共4分。）

26、对于下面用三元组表示的稀疏矩阵，请分别写出它们所对应的稀疏矩阵。

554576

02304-1

14-1061

12120一19

4013245

433

（1）（2）

标准答案：从三元组表还原稀疏矩阵时，首先根据表的第1行得出稀疏矩阵的行数

和列数，否则，我们无法确定所求的稀疏矩阵的维数，然后根据三元组表所提供的

行号和列号在稀疏矩阵的对应位置上写上相应的元素的值，在其他地方补零即可，

根据上述原则，此题答案如图(I),(2)所示。

rO030On-0000-10In

01000T9000000

0000000450000

_1000000030Q0

⑴(2)

知识点解析：暂无解析

27、假设有下面所示的稀疏矩阵，请写出其三元组表(按行优先的顺序)。

■01000-1

30002

0000o!

00200

00001

标准答案：稀疏矩阵的三元组指的是矩阵中非零元素的行号、列号和其对应的元

素，而三元组表就是将其结点是三元组的线性表按照顺序结构进行存储，其表的结

构为：(其中i代表行号，j代表列号，v指的是相应的元素值)

555

011

103

141

322

441

知识点解析：暂无解析

28、假设有一个长度为n的有序序列，在进行查找」寸，可以借助二叉树来进行，请

结合二叉树的性质来分析二分查找的最坏性能和平均性能。

标准答案：假设判定树的内部结点的总数为片2卜」。则判定树是深度为

h=lg(n+l)的满二叉树，树中第k层上的结点的个数为2口，查找它们所需要比较的

次数是匕则在等概率下，二分查找成功时的平均查找长度为：

—如果。很大，则可以用如下近似公式：ig(n+l)“，作为二分查

找成功时的平均查找长度。二分查找在查找失败时所需要比较的关键字的个数不超

过判定树的深度，在最坏情况下查找成功的比较次数也不超过判定树的深度。因为

判定树中度数小于2的结点只可能在最下面的两层上

知识点解析：暂无解析

29、已知一棵二叉树按照顺序结构存储，其存储结构如下:

10ABCDHEFJGM

012345678910111213141516171819

则请回答如下问题：(1)请画出此二叉树的树形结构。(2)请写出此二叉树的前序遍

历、中序遍历和后序遍历序列。(3)此二叉树的高度是多少？(4)结点F的双亲、孩

子，以及祖先分别是什么？(5)此树中，度数为1的结点共有几个?分别是哪几个？

(6)结点C有左孩子吗?如果有左孩子，则C的左孩子的编号应该是什么？

标准答案：(I)此二叉树如图所示：

为：ABDEFGMCHJ中序遍历序列为:EDGFMBACHJ后序遍历序列为:

EGMFDBAJHC(3)此树的高度是5。(4)结点F的双亲是D,孩子是G,M(其口G

是其左孩子，M是其右孩子)，祖先是D,B,Ao(5)此树中度数为1的结点共有3

个，分别为B,C,Ho(6)结点C没有左孩子，如果它有左孩子，则左孩子的编号

为6(2x3=6)

知识点解析：暂无解析

四、算法阅读题(本题共4题，每题7.0分，共4分0)

30、以下为单链表按序号查找的运算，分析算法，请在处填上正确的语句。

pointerfind_lklist(lklistheadjnti){p=head;j=O;while(){p=p->next;j++;J

if(i==j)return(p);elsereturn(NULL);)

标准答案：(p—>next!:NULL)&&(jVi)

知识点解析：暂无解析

31、以下算法实现若开散列表HP中存在键值为K的结点，则将其删除。请分析程

序，并在_____上填充合适的语句。voiddeletc_opcnhash(keytypeK,openhashHP)

{i=H(K);if(HP[i]=NULL)retum;/*空表则退出*/p=HV[i];if(p—>

key==K){=p—>next;free(p);return;)/*表首结点为彳寺删除结点时的删除*/

while(p—>next!二NULL)/*其他情况下的删除*/{q=p;p=p一>next;if(p一>

key==K){=p—>next;delete(p);return;)}}

标准答案:HP|i|q—>next

知识点解析：暂无解析

32、以下运算实现在循环队上的出队列，请在处用适当的语句予以填充。

intOutCycQueue(CycqueueTp*sq,DataType*x){if(sq—>front==){error("火空

");return(0);)else{;;return(l);))

标准答案：sq—>rearsq—>front=(sq—>front+1)%maxsize*x=sq—>data[sq一>

front]

知识点解析：暂无解析

33、以下为求单链表表长的运算，分析算法，请在处填上正确的语句。血

length_lklist(lklisthead)求表的长度。*/{;j=0;while(p—>next!=NULL)

{;j++;(retum(j);}/*回传表长*/

标准答案：p=headp=p—>next

知识点解析：暂无解析

五、算法设计题(本题共7题，每题1.0分，共/分。)

34、从键盘上输入若干字符(每行K度不等)，输入后把它们存储到磁盘文件中，

再从该文件中读出这些数据，将其中小写字母转换成大写字母再进行屏幕输出。

标准答案：本题的程序为：includeVstdio.h>main。/*输入字符串到文件，取出并

将小写转换成大写*/{inti,flag;charstr[80],ch;fILE*fp;fpMbpcnC'tcxt'V'w");

for(flag=l:flag;;)/*输入字符串*/{prini「("\n输入字符通\n")gets(str);

fprintf(fp,u%t\str);printf(neoutinnue?Y/N")；iR(ch=getchar(»=="n")!!(ch=='n'))

flag=0;getehar();}fseek(fp,0,0);while(fscanf(fp,n%sH,str)!=EOF)

{for(i=O;str[i]=,e,;i==)if((str[i]=,a,)&&str[i]<=,Z,/*小写字母进行转换*/

str[i]=str[i]-32;printf("\n%\n",str);}fclose(fp);}/*main*/

知识点解析：暂无解析

全国自考(数据结构)模拟试卷第3套

一、单项选择题(本题共75题，每题1.0分，共75

分。)

1、对文件进行直接存取的是根据()

A、逻辑记录号去存取某个记录

B、逻辑记录的关键字去存取某个记录

C、逻辑记录的结构去存取某个记录

D、逻辑记录的具体内容去存取某个记录

标准答案：A

知识点解析：暂无解析

2、一个栈的人栈序列是a,b,c,d,e,则栈的不可能的输出序列是（）

A、edcba

B、decba

C^dceab

D、abcde

标准答案：C

知识点解析：暂无解析

3、带头结点的单链表head为空的判断条件是（）

A、head=NULL

head—>next=NULL

C、head—>next=head

D、head!=NULL

标准答案：B

知识点解析：暂无解析

4、非空的单循环链表L的尾结点Pf,满足（）

A、Pf.ncxt=NULL;

B、P=NULL;

C>Pf.next=L;

D、P=L

标准答案：C

知识点解析：暂无解析

5、在下面的排序方法中，不需要通过比较关键字就能进行排序的是（）

A、箱排序

B、快速排序

C、插入排序

D、希尔排序

标准答案：A

知识点解析：暂无解析

6、通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）

A、数据元素具有同一特点

B、不仅数据元素所包含的数据项的个数要相同，而R对应数据项的类型要一致

C、每个数据元素都一样

D、数据元素所包含的数据项的个数要相等

标准答案：B

知识点解析：暂无解析

7、从具有n个结点的单链表中查找值等于x的结点时，在查找成功的情况下，平

均需比较()个结点。

A、n

B、n/2

C、(n-l)/2

D、(n+l)/2

标准答案：D

知识点解析：暂无解析

8、在一个链队列中，茬f,r分别为队首、队尾指针，则插入s所指结点的操作为

()

A、f—>next=c;f=s;

B、r—>next=s;r=s;

C、s—>next=r;r=s

D、s—>next=f,f=s;

标准答案：B

知识点解析：暂无解析

9、设散列函数为H(k)=kmod7,一组关键码为23,14,9,6,30,12和18,散列表T的

地址空间为0.6,用线性探测法解决冲突，依次将这组关键码插入T中，得到的散

A.

0123456

146239183012

B.

0123456

141823930126

C,

A、

B、

C、

D、

标准答案：B

知识点解析：暂无解析

10、邻接表存储结构下图的深度优先遍历算法结构类似于于义树的()

A、先序遍历

B、中序遍历

C、后序遍历

D、按层遍历

标准答案：A

知识点解析：暂无解析

11、线索二叉树是一种()结构。

A、物理

B、逻辑

C、存储

D、线性

标准答案：A

知识点解析：暂无解析

12、排序的重要目的是为了以后对已排序的数据元素进行()

A、打印输出

B、分类

C、查找

D、合并

标准答案.C

知识点初斤：暂无解析

13、在一非空二叉树的中序遍历序列中，根结点的右边()

A、只有右子树上的所有结点

B、只有右子树上的部分结点

C、只有左子树上的所有结点

D、只有左子树上的部分结点

标准答案：A

知识点解析：暂无解析

14、设图G采用邻接表存储，则拓扑排序算法的时间复杂度为()

A、O(n)

B、O(n+e)

C、O(n2)

D、O(nxe)

标准答案：B

知识点解析：暂无解析

15、在下面的排序方法中，属于不稳定的排序方法的是()

A、直接插入排序

B、冒泡法排序

C、堆排序

D、归并排序

标准答案：C

知识点解析：暂无解析

二、填空题(本题共70题，每题1.0分，共10分。)

16、对于一个具有n个结点的单链表，在已知p结点后插入一个新结点的事件的时

间复杂性为，在给定值为x的结点后插入一个新结点的时间复杂性为

标准答案：0(1)O(n)

知识点解析：暂无解析

17、设有两个串p和q,求q在p中首次出现的位置的运算叫o

标准答案：模式匹配

知识点解析：暂无解析

18、对于一个长度为n的线性表，假设表中各结点的查找概率相同，则在查找成功

的情况下，平均杳找长度为,如果k不在表中，则需要讲行次比较后

才能确定查找失败。

标准答案:(n+1)/2n+1

知识点解析：暂无解析

19、在二叉排序树中，其左子树中任何一个结点的关键字一定_____其右子树的各

结点的关键字。

标准答案：小于

知识点解析：暂无解析

20、数组0[1……n]表示一个环形队列，设f的值为队列中第一个元素的位置，r的

值为队列中实际队尾元素的位置加1,并假定队列中至多只有n-1个元素，则计算

队列中元素个数的公式为o

标准答案：(n+r-f)modn

知识点解析：暂无解析

21、一般来说，数组中的元素具有的数据类型，并且数组元素的下标的上界

和下界都是的。

标准答案：统一固定

知识点解析：暂无解析

22、一个nxn的对称矩阵，如果以行为主序或以列为主序存入内存，则其容量为

标准答案：nx(n+l)/2

知识点解析：暂无解析

23、在线性表的顺序存储中，假设每个结点所占用的存储空间为c,且第一个单元

的存储地址则是该结点的存储地址，设开始结点山的存储地址是LOC(a。，则结

点ai存储地址LOC®)可以通过下式得到。

标准答案：LOC(ai)=LOC(ai)+(i-l)*c

知识点解析：暂无解析

24、在具有n个单元的循环队列中，队满时共有个元素。

标准答案：n—1

知识点解析：暂无解析

25,查找表按其所包括的运算的不同分为_____查找表和______查找表。

标准答案：静态动态

知识点解析：暂无解析

三、解答题(本题共4题，每题分，共4分。)

26、请根据下面所给出的邻接矩阵画出相应的有向图或者是无向图(顶点w表示)。

6111.rOllOO-rO0100-|

Vi1JL0001000010

11B/1111

11nfl1000100001

11\J

linn1100010000

11UV

0101001000

(A)(B)(C)

标准答案：A,B,C对应的图分别为:

知识点解析：暂无解析

27、对于如下一个有序的关键字序列｛5,9,12,18,23,31,37,46,59,66,71,78,85),现在要

求用二分法进行查找值为18的关键字，则经过几次比较之后能查找成功？

标准答案：根据二分查找的过程，我们可以得到如下的比较结果：第一次比较：

[5,9,12,18,23,31,37,46,59,66,71,78,85,]f第二次比较:

[5,9,12,18,23,31],37,46,59,66,71,78,85T第三次比较:

5,9,12[18,23,31],37,46,59,66,71,78,85

知识点解析：暂无解析

28、已知有一关键字序列为｛505,94,512,61,908,170,397,275,653,463),如果我们采

用快速法对此序列进行排序(按照升序排序)，请给出每一趟排序的结果。

标准答案：快速排序采用分治法进行，其基本思想如下：将原问题分解成为若干个

规模更小但结构和原问题相似的子问题，递归地解这些子问题，然后将这些子问题

的解的组合为原问题的解，根据上述思想，我们可以得到如下快速排序的各趟结果

如下:初始:505,94,512,61,908,170,897,275,653,432第1趟:

[462,94,295,61,170]505[897,908,653,5⑵第2趟:

[170,94,295,61]462,505(897,908,653,512]第3趟

知识点解析：暂无解析

29、已知数据序列为{12,5

和冒泡排序每趟的结果。

标准答案:初始值键值序列[12]592063124

ri=l[512]92063124

i=3[5912J2063124

插入排外i=4[591220]63124

每热结果i=5[5691220]63124

i=8[569122031]24

i=7[56912202431]初始键值序列[12592063124]

第一趟之后[591262024]31第二趟之后[5961220]2431第三趟之后[56912]20

2431第四趟之后56912202431

知识点解析：暂无解析

四、算法阅读题(本题共4题，每题7.0分，共4分。)

30、INITIATE。的功能是建立一个空表。请在处填上正确的语句。Iklist

initiate」klist()/*建立一空表*/{;;return(t);}

标准答案：t=malloc(size)t—>next二NULL

知识点解析：暂无解析

31、以下运算实现在顺序栈上的退栈，请在______处用适当的语句予以填充。血

Pop(SqStackTp*sq,DataType*x){if(sq—>top==0){error("卜溢)return(O);)

else{*x=;;return(l);))

标准答案：sq->data[sq->top]sq->top-

知识点解析：暂无解析

32、以F算法在开散列表HP中查找键值等于K的结点，成功时返回指向该点的指

针，不成功时返回空指针。请分析程序，并在上填充合适的语句。pointer

research_opcnhash(keytypeK,openhashHP){i=H(K);/*计算K的散列地址*/p=HP[i];

/*i的同义词子表表头箱针传给P*/while()p=p—>nexl;/*未达到表尾且未找

到时，继续扫描*/；}

标准答案：(P!=NULL)&&(p—>key!=K)rcturn(p)

知识点解析：暂无解析

33、基于三元组的稀疏矩阵转置的处理方法有两种，以下运算按照矩阵A的列序

米进行转置，请在_____处用适当的语句予以填充。lrans_Sparmat(SpMatnxrp

a,SpMatrixTp*b){(*b).mum=a.nu;(*b),nu=a.mu;(*b),tu=a.tuif(a.tu){q=l;

for(col=I;;col++)for(p=l;p<=a.tu;p++)if()==col)

{(*b).data[q].i=a.data[p].j;(*b).data[q].j=a.data[p].i;(<!b).data[ql.v=a.data[p].v;

_一；}1}

标准答案:col<=a.nua.data[p].jq++

知识点解析：暂无解析

五、算法设计题(本题共［题，每题7.0分，共1分。)

34、采用单链表作为存储结构，试编写一个函数来实现用选择排序方法进行升序排

列。

标准答案：首先定义单链表的结点:structnode{intkey;structnode*link;)函数如

下：struct*selectsort(structnode*h){struelnode*P,*q,*r,*s,*t;t=Null;while(h!=Null)

{p=h;q=Null;s=h;r=NulI;while(P!=Null){if(p->key<s—>key){s=p;p=q;)q=p;

p=p->link;}if(s==h)h=h—>link;elseh=s;s—>lind=t;t=s;}h=t;retum(h);}

知识点解析：暂无解析

全国自考(数据结构)模拟试卷第4套

一、单项选择题(本题共乃题，每题1.0分，共15

分。)

1、内部排序的方法有许多种，()方法是从未排序序列中依次取出元素，与己排序

序列中的元素作比较，将其放入已排序序列的正确位置上。

A、归并排序

B、插入排序

C、快速排序

D、选择排序

标准答案：B

知识点解析：暂无解析

2、散列表的目的是()

A、插•入

B、删除

C、快速查找

D、排序

标准答案：C

知识点解析：暂无解析

3、设数组data[O..m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾

指针，则执行出队操作的语句为()

A、front:=front+1

B、front:=(front+l)modin

C、rear:=(rear+1)modm

D、front:=(front+1)mod(m+1)

标准答案：D

知识点解析：暂无解析

4、在一个长度为n的顺序表(顺序存储的线性表)中，向第i个元素(此切+1)之前插

入一个新元素时，需向后移动()个元素工

A、n-i

B、n-i+1

C、n-i-1

D、i

标准答案：B

知识点解析：暂无解析

5、线性表L=®,a2，...»ai，an),下列说法正确的是()

A、每个元素都有一个直接前趋和直接后继

B、线性表中至少要有一个元素

C、表中诸元素的排列顺序必须是由小到大或由大到小的

D、除第一个元素和最后一个元素外，其余每个元素都有一个且仅有一个直接前趋

和直接后继

标准答案：D

知识点解析：暂无解析

度优选遍历图的顶点序列是()

A、V|V5V3V4V2V6V7

B、V|V5V3V4V2V7V6

C、V|V7V2V6V4V5V3

D、V|V2V4V7V6V5V3

标准答案：A

知识点解析：暂无解析

7、在Hash函数H(k)=kMODm中，一般来讲，m应取()

A、奇数

B、偶数

C、素数

D、充分大的数

标准答案：C

知识点解析：暂无解析

8、如果我们采用二分查找法查找一个长度为n的有序表，则查找每个元素的平均

比较次数()对应的判定树的高度(假设树高h>2)0

A、大于

B、小于

C、等于

D、无法确定

标准答案：B

知识点解析：暂无解析

9、对于一个具有N个顶点的图，如果我们采用邻接矩阵法表示，则此矩阵的维数

应该是()

A、(N-l)x(N-l)

B、NxN

C、(N+l)x(N+l)

D、不确定

标准答案：B

知识点解析：暂无解析

10、快速排序在最坏情况卜.的时间复杂度是()

A、O(nlogn)

B、O(n2)

C、O(n3)

D、都不对

标准答案：B

知识点解析：暂无解析

11、向一个栈顶指针为T叩的链栈中插入一个s所指结点时，其操作步骤为()

A、Top->ncxt=s;

B、s->next=Top—>next;Top—>next=s;

C^s一>next=Top;top=s;

D、s—>next=Top;Top=Top—>next;

标准答案：C

知识点解析：暂无解析

12、树最适合用来表示()

A、有序数据元素

B、无序数据元素

C、元素之间具有分支层次关系的数据

D、元素之间无联系的数据

标准答案：C

知识点解析：暂无解析

13、设有一个无向图G=(V,E)和G，=(V，,E)如果G，是G的生成树，则下面不正

确的说法是()

A、G，为G的子图

R、为G的连通分量

C、G，为G的极小连通子图且V=V

D、G，是G的一个无环子图

标准答案：B

知识点解析：暂无解析

14、实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树

采用()存储结构。

A、二叉链表

B、广义表

C、三叉链表

D、顺序

标准答案：C

知识点解析：暂无解析

15、下面四种排序方法中，平均查找长度最小的是()

A、插入排序

B、选择排序

C、快速排序

D、归并排序

标准答案：C

知识点解析：暂无解析

二、填空题(本题共70题，每题分，共70分。)

16、对快速排序来讲，其最好情况下的时间复杂度是,其最坏情况下的时间

复杂度是_____o

标准答案：O(nlog2n)0(】/)

知识点解析：暂无解析

17、假设在线索二叉树中，结点的标志域的值为。时，表示其指针域是指向孩子的

指针，当结点的标志域为1时，表示其指针域是指向前趋或者后继的线索，则一个

结点是叶结点的充要条件是_____。

标准答案：结点的左右标志都是1

知识点解析：暂无解析

18、散列函数的作用是：o

标准答案：压缩待处理的下标范围，待处理的|u|个值减少到m个值，从而降低空

间开销

知识点解析；暂无解析

19、内部排序的方法可以分为五类：、、、、o

标准答案：插入排序选择排序交换排序归并排序分配排序

知识点解析：暂无解析

20、树的结点数目至少为,二叉树的结点数目至少为o

标准答案：10

知识点解析：暂无解析

21、在结点数目相同的二叉树中，的路径长度最短。

标准答案：完全二叉树

知识点解析：暂无解析

22、从一个顺序存储的循环队列中删除一个元素时，应该o

标准答案：先移动队首指针，后取出元素

知识点解析：暂无解析

23、对于数组，通常具有的基本操作有种，它们分别是______o

标准答案：两查找和修改

知识点解析：暂无解析

24、设有两个散列函数Hl(k)=kmod13和H2(k)=kmod11+1,散列表为

T[0...12],用双重散列解决冲突。函数HI用来计算散列地址，当发生冲突时，H2

作为计算下一个探测地址的地址增量，假定在某一时刻表T的状态为

T«0123456789101112

IDE匚匚□下一个

被插入的关键码是42,其插入的位置是：o

标准答案：位置为0

知识点解析：暂无解析

25、无向图的邻接矩阵是,并且主对角线上的元素的值为o

标准答案：对称零

知识点解析：暂无解析

三、解答题(本题共4题，每题分，共4分。)

26、对于散列文件来说，其存储单位是什么?对于一个能存储m个桶，若需要存放

的同义词大于m,则需要如何处理?现在假设一个文件有18个记录，其关键字分别

为:30,11,27,04,19,86,73,89,32,05,103,58,45,67,77,81,08,48,假设桶的容量m=3,桶

数b=7,现在要求用除余法做散列函数H(key尸key%7,请给出该散列文件的表示

方法。

标准答案：磁盘上的文件记录通常是成组存放的，若干个记录组成一个存储单位，

在散列文件中，这个存储单位叫做桶。如果一个桶能放m个记录，则如果现在已

经存放了m个记录时，继续存放记录就会产生“溢出”，当发生"溢出”时，一般采

用拉链法，就是将第m+1个同义词存放在另外一个桶中，通常此桶就称为“溢出

桶”，相应的前m个同义词存放的桶就称为是“基桶”，溢出桶和基桶大小相同,根

据散列函数,得到对应的关键字的散列地址为:2,4,6,4,5,2,3,5,4,5,5,2,3,4,041,6,

桶墉号基桶溢出桶

27、已知下面的一个图，请根据普里姆算法构出它的一棵最小生成的树。

标准答案：构造最小生成树的过程如下:

28、假设在树中，如果结点x是结点y的双亲时，用(x,y)来表示树边，已知一棵树

的树边的集合为(i,n),(e,i),(b,e),(b,d),(a,b),(g,j),(g,k),(c,g),(c,f),

(hj),(c,h),(a,c)),请用树形结构画出此树，并回答下面的问题。(1)哪个是根结

点？(2)哪些是叶结点？⑶哪个是g的双亲？(4)哪些是g的祖先？⑸哪些是g的孩子?

(6)哪些是e的子孙？(7)哪些是e的兄弟？(8)树的深度是多少？(9)树的度数是多少？

标准答案：树的结构如下图所示：(1总是根结点(2)01,儿山门」上是叶结点(3飨是8

的双亲(4)a和e是g的祖先(5)j,k是g的孩子(6)i,m,n是e的子孙(7)d是e的兄弟

(X)树的深度是5(9)树的度数是3皿n

知识点解析：暂无解析

29、对于如图所示的二叉树，请画出其顺序存储结构图。

标准答案：二叉树的顺序存储就是将二叉树的结点按编号存在向量B[O,n]中，其中

B[0]用来存放结点T数，如果树中某些编号对应的结点不存在，则对应存储空间为

“空二根据上述规则，我们得到：

012345678910111213

8ABCDGI4EF0H

知识点解析：暂无解析

四、算法阅读题(本题共4题，每题7.0分，共4分。)

30、以下算法实现若开散列表HP中无键值为K的结点，则插入一个这样的结点。

请分析程序，并在_____上填充合适的语句。voidinscrt_opcnhash(kcytypc

K,openhashHP){if(research_opcnhash(K,HP)==NULL){i=H(K);q=malloc(size);q

>key=;/*生成新结点*/=HP[i];HP[i]=;/*前插法链入新结点

*/}}

标准答案：Kq—>ncxtq

知识点解析：暂无解析

31、以下运算实现在链队上的出队列，请在处用适当的语句予以填充。int

OutQucue(QucptrTp*lq,DataType*x){LqueueTp*s;if(lq—>front==lq—>

rear){error("队空");relurn(0);}else{s=(lq->front)一>next;=s一>dala;(Iq一

>front)—>next;if(s—>next==NULL)lq—>rear=lq—>front;free(s);

return(l);})

标准答案：*xs—>next

知识点解析：暂无解析

32、以下运算实现在链戌上的进栈，请在处用适当的语句予以填充。void

Push(LStackTp*ls,DataTypex){LStackTp*p;p=malloc(sizeo