数据结构试题 (三)

数据结构

1.顺序表中第一个元素的存储

地址是100,每个元素的长度为

2,则第5个元素的地址是()0

110

108

100

120

2.在n个结点的顺序表中，算法

的时间复杂度是0(1)的操作是

()。

2.[单选题]*

访问第i个结点(l<i<n)和求第i个结点的直接前驱(2<i<n)

在第i个结点后插入一个新结点(l<i<n)

删除第i个结点(l<i<n)

将n个结点从小到大排序

答案解析：采用顺序存储结构的线性表通常称为顺序表。顺序表是将表中的结点依

次存放在计算机内存中一组地址连续的存储单元中。

假设顺序表L,长度为n,求bai第i个节点L[i],直接前驱因此为duO(1)

答案B需要移动zhin-i个节点，因此为0(n)

答案C也需要移动n-i个节点

答案D根据排序方法不同最慢0(22),最快O(nlogn)

3向一个有127个元素的顺序

表中插入一个新元素并保持原

来顺序不变，平均要移动的元

素个数为()。

3.

［单选题］*

8

63.5(正确答案)

63

7

答案解析：n(n+l)/

(2*(n+l))=n/2

4线性表若采用链式存储结构

时,要求内存中可用存储单元的

地址()0

4.［单选题］*

必须是连续的

部分地址必须是连续的

一定是不连续的

连续或不连续都可以

5.将两个各有n个元素的有序

表归并成一个有序表，其最少的

比较次数是（）。

［单选题］*

n（正确答案）

2n-l

2n

n-1

答案解析：归并排序基本思想：归并排序是多次将两个或两个以上的有序表合并成

一个新的有序

表。最简单的归并是直接将两个有序的子表合并成一个有序的表。归并排序最好情

况下的复杂度

为。（叽

6.将两个各有N个元素的有序表归并成一个有序表，其最多的比较次数是（）。

［单选题］*

2n-l（正确答案）

2n

n-1

答案解析：最多的比较次数是当两个有序表的数据刚好是插空顺序的时候，比如：

第一个序列是1,3,5,第二个序列是2,4,6,把第二个序列插入到第一个序列中，先

把第二个序列中的第一个元素2和第一个序列依次比较，需要比较2次（和1,3

比较），第二个元素4需要比较2次（和3,5比较，因为4比2大，2之前的元素

都不用比较了），第三个元素6需要比较1次（只和5比较），所以最多需要比较

5次。即2n-l次。

7.线性表1=（al,a2,………）.下列说法正确的是（）。［单选题］*

每个元素都有一个直接前驱和一个直接后继

线性表中至少有一个元素

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

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

继。（正确答案）

8.以下说法错误的是（）［单选题］*

求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构

时实现的效率低

顺序存储的线性表可以随机存取

由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活

线性表的链式存储结构优于顺序存储结构

9.线性表L在（）情况下适用于使用链式结构实现。［单选题］*

需经常修改L中的结点的值

需不断对L进行删除插入

L中含有大量的结点

L中结点结构复杂

10.在单链表中，要将s所指结点插入到p所指结点之后，其语句为（）［单选题］*

S->next=p+1;p->next=s;.

（*p）.next=s;（*s）.next=（*p）.next;

S->next=p->next;p->next=S->next;

S->next=p->next;p->next=s;正确答案）

答案解析：s所指的结点的指针（s->next）指向当前P指针所指结点的指针（p->next）

所指向的结点

P指针所指结点的指针（p->next）指向的结点为s所指的结点（s）

II.链接存储的存储结构所占存储空间（）［单选题］*

分两部分，一部分存放结点值，另一部分存放表示结点关系的指针

只有一部分，存放结点值

只有一部分，存储表示间关系的指针

分两部分，一部分存放结点值，另一部分存放结点所占单元数

12.()是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

［填空题］*

___________________________________(答案:数据元素)

13._是数据的最小单位，—是讨论数据结构时涉及的最小数据单位。［填空题］

*

空1答案：数据项

空2答案：数据元素

14.从逻辑关系上讲，数据结构主要分为___________和。［填空题］*

空1答案：集合

空2答案：线性结构

空3答案：树结构

空4答案：图结构

15.数据的存储结构主要有—和—两种基本方法，不论哪种存储结构，都要存储

两方面的内容：一和一o［填空题］*

空1答案：顺序存储结构

空2答案：链接存储结构

空3答案：数据元素

空4答案：数据元素之间的关系

16.算法具有五个特性，分别是______________________

［填空题］*

空1答案：有穷性

空2答案：确定性

空3答案：可行性

空4答案：有零个或多个输入

空5答案：有一个或多个输出

17.算法的描述方法通常有__、_、_和一四种，其中，—被称为算法语言。

［填空题］*

空1答案：自然语言

空2答案：程序设计语言

空3答案：流程图

空4答案：伪代码

空5答案：伪代码

18.在一般情况下，一个算法的时间复杂度是()的函数。［填空题］*

___________________________________(答案：问题规模)

19.设待处理问题的规模为n,若一个算法的时间复杂度为一个常数，则表示成数

量级的形式为_,若为n*log25n,则表示成数量级的形式为一。［填空题］*

空1答案：0（1）

空2答案：O（nlog2n）

2（）.顺序存储结构中数据元素之间的逻辑关系是由一表示的，链接存储结构中的数

据元素之间的逻辑关系是由一表示的。［填空题］*

空1答案：存储位置

空2答案：指针

答案解析：顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系

由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链

表中的一个结点，元素之间的逻辑关系由结点中的指针表示。

21.假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲

或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构

应该是（）。［填空题］*

___________________________________（答案：图）

22.算法指的是（）。

［填空题］*

（答案：对特定问题求解步骤的一种描述，是

指令的有限序列。）

答案解析：计算机程序是对算法的具体实现；简单地说，算法是解决问题的方法；

数据处理是通过算法完成的。所以，只有A是算法的准确定义。

算法指的是（）。A对特定问题求解步骤的一种描述，是指令的有限序列。

23.下面（）不是算法所必须具备的特性。［单选题］*

有穷性

确切性

高效性

可行性

24.算法分析的目的是（）,算法分析的两个主要方面是（）。*

A.找出数据结构的合理性

B.研究算法中输入和输出的关系

C.分析算法的效率以求改进

D.分析算法的易读性和文档性

E空间性能和时间性能

F正确性和简明性

G可读性和文档性

H数据复杂性和程序复杂性

25.算法的时间复杂度都要通过算法中的基本语句的执行次数来确定。［判断题］*

对

错正确答案）

答案解析：时间复杂度要通过算法中基本语句执行次数的数量级来确定。

26.每种数据结构都具备三个基本操作：插入、删除和查找。［判断题］*

对

错正确答案）

答案解析：如数组就没有插入和删除操作。此题注意是每种数据结构。

27.所谓数据的逻辑结构指的是数据之间的逻辑关系。［判断题］*

对

错

答案解析：是数据之间的逻辑关系的整体。

28.逻辑结构与数据元素本身的内容和形式无关。［判断题］*

对

错

答案解析：因此逻辑结构是数据组织的主要方面。

29.基于某种逻辑结构之上的基本操作，其实现是唯一的。［判断题］*

对

错（正确答案）

答案解析：基本操作的实现是基于某种存储结构设计的，因而不是唯一的。

简答［矩阵题］*

很不满意不满意一般满意很满意

顺序存储

结构的特OOOOO

点是

链接存储

结构的特OOOOO

点是

答案解析：1.用元素在存储器中的相对位置来表示数据元素之间的逻辑关系。

2.用指示元素存储地址的指针表示数据元素之间的逻辑关系。

30.算法在发生非法操作时可以作出处理的特性称为（）。［填空题］*

___________________________________（答案：健壮性）

31.常见的算法时间复杂度用大。记号表示为：常数阶__、对数阶_、线性阶

一、平方阶一和指数阶一。［填空题］*

空1答案：0(1)

空2答案：O(log2n)

空3答案：0(n)

空4答案：0(nA2)

空5答案：0(2人n)

32.将下列函数按它们在n时的无穷大阶数，从小到大排列。

n,n-nA3+7nA5,nlog2n,2A(n/2),nA3,log2n,nA(l/2)+log2n,(3/2)An,n!,nA2+log2n

［填空题】*

空1答案：log2n

空2答案："(1/2)+log2n

空3答案：n

空4答案:nlog2n

空5答案:nA2+log2n

空6答案:nA3

空7答案：n-nA3+7nA5

空8答案:2A(n/2)

空9答案：(3/2)人n

空10答案：n!

33.可以用()定义一个完整的数据结构。［单选题］*

数据元素

数据对象

数据关系

抽象数据类型

34.数据的逻辑结构分为—和—

前者包括一般线性表、受限线性表______________线性表的推广__、

后者包括一，一形结构_________一状结构________［填空题］*

空1答案：线性结构

空2答案：非线性结构

空3答案：栈

空4答案：队列

空5答案：串

空6答案：数组

空7答案：广义表

空8答案：集合

空9答案：树

空10答案：一般树

空11答案：二叉树

空12答案：图

空13答案：有向图

空14答案：无向图

35.以下属于逻辑结构的是［单选题］*

顺序表

哈希表

有序表

单链表

答案解析：顺序表、哈希表和单链表表示几种数据结构，既描述逻辑结构，又描述

存储结构和数据运算。

而有序表是指关键字有序的线性表，可以链式存储也可以顺序存储，仅描述元素之

间的逻辑关系，故它属于逻辑结构。

36.以下与数据的存储结构无关的术语是（）［单选题］*

循环队列

链表

哈希表

栈（正确答案）

答案解析：数据的存储结构有顺序存储、链式存储、索引存储和散列存储。循环队

列（易错点）是用顺序表表示的队列（见322节），是一种数据结构。栈是一种

抽象数据类型，可采用顺序存储或链式存储，只表示逻辑结构。

37.以下关于数据结构的说法中，正确的是（）.

［单选题］*

A.数据的逻辑结构独立于其存储结构

B.数据的存储结构独立于其逻辑结构

C.数据的逻辑结构唯一决定了其存储结构

D.数据结构仅由其逻辑结构和存储结构决定

答案解析：A数据的逻辑结构是从面向实际问题的角度出发的，只采用抽象表达方

式，独立于存储结构，数据的存储方式有多种不同的选择：而数据的存储结构是逻

辑结构在计算机上的映射，它不能独立于逻辑结构而存在。数据结构包括三个要

素，缺一不可。

38.在存储数据时，通常不仅要存储各数据元素的值，而且要存储（）.

［单选题］*

数据的操作方法

数据元素的类型

数据元素之间的关系

数据的存取方法

39.链式存储设计时，结点内的存储单元地址（）［单选题］*

一定连续（正确答案）

一定不连续

不一定连续

部分连续，部分不连续

答案解析：链式存储设计时，各个不同结点的存储空间可以不连续，但结点内的存

储单元地址必须连续。

40.数据的存储结构有_________________［填空题］*

空1答案：顺序存储

空2答案：链式存储

空3答案：索引存储

空4答案：散列存储

41.一个算法应该是()*

程序

问题求解步骤的描述

满足五个基本特征

A和C

42.某算法的时间复杂度为O(22),表明该算法的().

［单选题］*

问题规模是nA2

执行时间等于22

执行时间与22成正比

问题规模与nA2成正比

答案解析：时间复杂度为O(22),说明算法的时间复杂度T(n)满足T(n)

(c为比例常数)，即T(n)=O(22),时间复杂度T(n)是问题规模n

的函数，其问题规模仍然是n而不是心2。

4.12011统考A题】设〃是描述问题规模的非负整数，下面的程序片段的时间复杂度是().

x-2；

while(x<n/2)

xsss2*x；

O(log2n)B.O(n)

5川og?〃)D.0(/)

［单选题］*

A(正确答案)

答案解析：

4.A

在程序中,执行频率以高的语句为x=2*x.设这一语句共执行了/次，则有2^<〃/2,所以

log2(w/2)-1=login-2.得l\n)=O(log2w).

注意是t+1

5.12012统考真题】求整数〃(〃>0)的阶乘的算法如下，其时间复杂度是().

intfact(intn){

if(n<«l)return1;

returnn*fact(n-1);

D.5〃2)

A.O(log2n)B.5〃)C.5"log2")

［单选题］*

A

B（正1

C

D

答案解析：

5.B

本题是求阶乘〃!的递归代码，即〃X(〃-1)x…X1,共执行〃次乘法操作，故”〃)=。(〃)・

45.

6.12013统考真题】已知两个长度分别为，〃和〃的升序徒友，若将它们合并为西!巡勰

一个长度为即+〃的降序性表，则最坏情况下的时间复杂度是().

A.。(〃)B.O(mn)

C.O(min(/ii,〃))D.O(max(/n,n))

［单选题］*

A

B

C

D(正确答案)

答案解析：

6.D

两个升序缸表会并，两两比较表中的元素，每比较一次，确定一个元素的徒接位置(取较小

元素，头插法).当个倍表比较结束后，将另一•个倍衣的剩余元素插入即可.圾坏的情况是两

个链衣中的元素依次进行比较，时间复杂度为tXmax(m,/»)).

46.

7.【2014统考攵题】下列程序段的时间复杂度是().

count-0;

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

for(j-1;j<-n;j++)

count++;

A.O(log2〃)B.O(n)

2

C.O(nlog2n)D.O(n)

［单选题］*

A

B

C(I

D

答案解析：

7.C

内展循环条件与外层循环的变盘无关，每次循环/白增1.每次内层循环都执行”次.

外层循环条件为AW〃.增Id定义为k*・2,可知循环次数为2*W〃，即大41。区〃・所以内层循环的

时间攵杂度是0(”)，外层砧环的时间必杂度是0(1。刎)・对于嵌套循环，根据乘法规则可知，读

段程序的时间女杂度n〃)-A(〃)xTK〃)-a")xaiogM=0(nl0fe/»).

47.

8.12017统才算题】下列函数的时间复杂度是().

intfunc(intn)(

inti«0,sum«0;

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

return1;

J

A.O(logn)B.O(nia)

C.0(")D.O(nlogn)

［单选题］*

A

B（正1

C

答案解析：

8.B

sum+=++i;相当于++i;sum-sum+i;.进行到第上次循环，sum-(1+k)*k/2.显然需

要进行5/c)次循环，因此这也是该函数的时间复杂度.

48.

9.有以下算法，其时间复杂度为（）.

voidfun（intn）｛

inti"0;

while

2020年数据结构考研复习指导

i++;

)

A.O(n)B.O(〃logn)

C.5匕)D.5«)

［单选题］*

A(正确答案)

B

C

D

答案解析：

9.C

基本运算是i++,设其执行次数为1,有nxW”，即故有/W防，则”〃)=5防).

49.

10.程序段如下：

for(i=n-l;i>l;i--)

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

if(A[j]>A[j+lJ)

A[j]与A[j+1]对换;

其中”为正整数，则最后一行语句的频度在最坏情况下是().

A.0(/i)B.。(川。部)

C.0(n3)D.0(〃2)

[单选题]*

A

B

C

D(正确答案)

答案解析：

10.D

当所有相邻元索都为逆序时，则最后一行的语句每次都会执行.此时,

T(〃)=£W】=£iT=d)("l)/2=°(/)

1■2/■1M

所以在最坏情况下的该语句频度是。0?)・

11.以下算法中加下画线的语句的执行次数为().

intmN。，，，j;

for