2024版数据结构考试内部题库含答案解析

数据结构考试内部题库含答案解析（全考点）

1、以下属于逻辑结构的是（）

•・A:顺序表

・・B:哈希表

・•C:有序表

・・D:单链表

解析

顺序表、哈希表和单链表是三种不同的数据结构，既

描述逻辑结构，又描述存储结构和数据运算。而有序

表是指关键字有序的线性表，仅描述元素之间的逻辑

关系，它既可以链式存储，又可以顺序存储，故属于

逻辑结构。

答案：C

2、链式存储设计时，结点内的存储单元地址（）。

・・A:一定连续

・•B:一定不连续

・•C:不一定连续

••D:部分连续，部分不连续

解析

链式存储设计时，各个不同结点的存储空间可以不连

续，但结点内的存储单元地址必须连续。

答案：A

3、对于两种不同的数据结构，逻辑结构或物理结构一定不

相同吗？

数据的运算也是数据结构的一个重要方面。对于两

种不同的数据结构，它们的逻辑结构和物理结构完全

有可能相同。比如二叉树和二叉排序树，二叉排序树

可以采用二叉树的逻辑表示和存储方式，前者通常用

于表示层次关系，而后者通常用于排序和查找。虽然

它们的运算都有建立树、插入结点、删除结点和查找

结点等功能，但对于二叉树和二叉排序树，这些运算

的定义是不同的，以查找结点为例，二叉树的时间复

杂度为0(n),而二叉排序树的时间复杂度为O(log

乙)。

4、试举一例，说明对相同的逻辑结构，同一种运算在不同

的存储方式下实现时，其运算效率不同。

线性表既可以用顺序存储方式实现，又可以用链式存

储方式实现。在顺序存储方式下，在线性表中插入和

删除元素，平均要移动近一半的元素，时间复杂度为

0(n);而在链式存储方式下，插入和删除的时间复杂

度都是0(1)。

5、下面关于倒排文件的说法中正确的是—o

・­A:倒排文件是对主关键字建立索引

・•B:倒排文件是对次关键字建立索引

.­C:倒排文件的优点是维护简单

・•D:采用倒排文件是为了节省存储空间

解析

倒排文件：用记录的非主属性(也叫副键)来查找记

录而组织的文件叫倒排文件，即次索引。倒排文件中

包括了所有副键值，并列出了与之有关的所有记录主

键值，主要用于复杂查询。倒排文件的优点是检索记

录较快。特别是对某些询问，不用读取记录，就可得

到解答。

答案：B

6、下列术语中与数据的存储结构无关。

・・A:循环队列

・•B:堆栈

・•C:散歹［］表

・・D:单链表

解析

数据的存储结构有顺序存储、链式存储、索引存储和

散列存储。栈是一种抽象数据类型，可采用顺序存储

或链式存储，是一种逻辑结构。散列表和单链表表示

几种数据结构，既描述逻辑结构，又描述存储结构。

答案：B

7、下面程序的时间复杂度为一o

for(i=1,s=0;i<n;i++){

t=1;

for(j=1;j<=i;j++)

t=t*j;

s=s+t；｝

•A:O(n)

n2

•B:O()

.C：M

.D:oM

解析

分析代码：内层循环执行i次,外层循环执行n次，

i从1取到no得知执行最内层循环语句总次数为

(1+n)*n

5n2

2，即o()o

答案：B

8、下面算法的时间复杂度是—o

Voidfun(intn)

inti0,s=0;

while(s<n)

++i；

s=s+i;

・A:0(n)

.B:o/)

•C:0(

•D:O(nlog(n))

解析

最底层的代码为S=s+i,s到达n的过程刚好是

1+2+3+4.…+m这样累加起来的,根据等差队列之

和的公式，（l+m）*m=2n,故m约等于根号n,所

以此题选Co

答案：C

9、下面算法的空间复杂度为一。

floataver(floata[n]){

intj;

for(j=n;j>0;j-)

H

printf(%8.2f"za[j]);

)

・・A:0(1)

c\n

・•B:O(log)

・•C:0(n)

n2

・•D:0()

解析

函数体定义中出现数组，数组在初始化时需要分配空

间,此时空间复杂度为0(n),所以选C。

答案：C

10、已知程序如下所示，程序运行时使用栈来保存调用过程

的信息，自栈底到栈顶保存的信息依次对应的是一O

intS(intn){

return(n<=0)?0:S(n-1)+n;

voidmain(){

cout<<S(1);

}

・・A:main()->S(l)->S(0)

・・B:S(0)->S(l)->main()

・・C:main()->S(0)->S(l)

・・D:S(l)->S(0)->main()

解析

程序都是从main函数开始的,进入main函数后执

行S(l),之后递归执行S(0)o

答案：A

1、下列函数的时间复杂度是一O

intfunc(intn)

inti=0,sum=O;

while(sum<n)sum+=++i;

returni;

)

•A:O(log(n))

I'I

•B:0(一)

・C:0(n)

•D:O(nlog(n))

解析

z,

sum+=++i;相当于"++i;sum=sum+i"o进

行到第k趟循环，sum=(l+k)*k/2。(l+k)*k/2<n,

显然需要进行0()趟循环，因此这也是该函数的时

间复杂度。

答案：B

2、从一个具有n个结点的单链表中检索其值等于x的结点

时，在检索成功的情况下，需平均比较的结点个数是—O

・•A:n/2

・•B:n

・・C:(n+l)/2

・・D:(n-l)/2

解析

由于单链表只能进行单向顺序查找，以从第一个节点

开始查找为例，查找第m个节点需要比较的节点数

f(m)=m，查找成功的最好情况是第一次就查找成功,

只用比较1个节点，最坏情况则是最后才查找成功，

需要比较n个节点。所以一共有n种情况，平均下

来需要比较的节点为(1+2+3+...+(n-l)+n)/n=

(n+l)/2

答案：C

3、当n足够大时，下述函数中渐近时间最小的是—o

・•A:T(n)=nlog(n)-1000log(n)

・・B:T(n)=nlog(3)-1000log(n)

・C:T(n)=-lOOOIog(n)

・・D:T(n)=2nlog(n)-1000log(n)

解析

ABCD四个选项时间复杂度依次为0(n)、0(n)、

0()、0(nn)o所以n足够大时，时间复杂度最

小的是0(n),选Bo

答案：B

4、倒排文件包含有若干个倒排表，倒排表的内容是—o

・•A:一个关键字值和该关键字的记录地址

・•B:一个属性值和该属性的一个记录地址

・•C:一个属性值和该属性的全部记录地址

••D:多个关键字和它们相对应的某个记录的地址

解析

有倒排索引的文件我们称为倒排索引文件，简称倒排

文件。倒排索引，也常被称为反向索引，是一种索引

方法，被用来存储在全文搜索下某个单词在一个文档

或者一组文档中的存储位置的映射。倒排索引源于实

际应用中需要根据属性的值来查找记录。这种索引表

中的每一项都包括一个属性值和具有该属性值的各

记录的地址。

答案：C

5、下述编码中不是前缀码的是—o

・・A:{0,10,110,111)

・・B:{0,1,00,11)

・・C:{1z01,000,001)

・・D:{00,01,10,11)

解析

前缀编码是指对字符集进行编码时，要求字符集中任

一字符的编码都不是其他字符的编码的前缀。选项B

中。和00不符合前缀码要求。

答案：B

6、下面程序段的时间复杂度是—o

i=s=0;while(s<n)

i++；s+=i;

・A:O(log(n))

・B:oO

・C:0(n)

•D:0()

解析

第一次执行完s+=is=l第二次S=3=1+2第三次

s=6=1+2+3第四次s=10=l+2+3+4第k次

l+2+3+4+...+k=那么当>二n的时候停止,

也就是k二—所以复杂度是。

答案：B

7、在有向图中每个顶点的度等于该顶点的—o

・•A:入读

.・B:出度

・・C:入读与出度之和

・•D:入读与出度之差

解析

在有向图中每个顶点的度等于该顶点的入度与出度

之和。

答案：C

8、具有n个顶点的无向完全图有一条边。

・•A:n

・・B:n*(n-l)/2

・・C:n*(n+l)/2

・•D:n*n/2

解析

具有n个顶点的无向完全图有n*(n-l)/2条弧

答案：B

9、下列程序段的时间复杂度是—o

count=0;for(k=l;k<=n;k*=2)

for(j=l;j<=n;j++)

count++;

•A:0(n)

・B:0(n)

・C:O(nOn)