东北师范大学研究生院计算机考研数据结构真题汇总

2020年11月19日发(作者：羊滔)

一

.

选择题篇

1.

算法的计算量的大小称为计算的（

）。【北京邮电大学

2000

二、

3

（

20/8

分）】

A

．效率

B.

复杂性

C.

现实性

D.

难度

2.

算法的时间复杂度取决于（

）【中科院计算所

1998

二、

1

（

2

分）】

A

．问题的规模

B.

待处理数据的初态

C. A

和

B < /p>

3.

计算机算法指的是（

1

）它必须具备（

2

）

这三个特性。【南京理工大学

1999

一、

1

（

2

分）

通科技大学

1996

一、

1

（

4

分）】

(1) A

．计算方法

B.

排序方法

C.

解决问题的步骤序列

D.

调度方法

(2) A

．可执行性、可移植性、可扩充性

B.

可执行性、确定性、有穷性

C.

确定性、有穷性、稳定性

D.

易读性、稳定性、安全性

4

．一个算法应该是（

）。【中山大学

1998

二、

1

（

2

分）】

A

．程序

B

．问题求解步骤的描述

C

．要满足五个基本特性

D

．

A

和

C.

5.

下面关于算法说法错误的是（

）【南京理工大学

2000

一、

1

< p>（

1.5

分）】

A

．算法最终必须由计算机程序实现

B.

为解决某问题的算法同为该问题编写的程序含义是相同的

C.

算法的可行性是指指令不能有二义性

D.

以上几个都是错误的

6.

下面说法错误的是（

）【南京理工大学

2000

一、

2

（

1.5

分）】

(1

）算法原地工作的含义是指不需要任何额外的辅助空间

【武汉交

（

< p>2

）在相同的规模

n

下，复杂度

O(n)

的算法在时间上总是优于复杂度

O(2n)

的算法

（

3

）所谓时间复杂度是指最坏情 况下，估算算法执行时间的一个上界

（

4

）同一个算法，实现语言的级别越高，执行效率就越低

A

．

(1) B.(1),(2) C.(1),(4) D.(3)

7

．从逻辑上可以把数据结构分为（

）两大类。【武汉交通科技大学

1996

一

、

4

（

2

分）】

A

．动态结构、静态结构

B

．顺序结构、链式结构

C

．线性结构、非线性结构

D

．初等结构、构造型结构

8

．以下与数据的存储结构无关的术语是（

）。【北方交通大学

2000

二、

1

（

2

分）】

A

．循环队列

B.

链表

C.

哈希表

D.

栈

9

．以下数据结构中，哪一个是线性结构（

）？【北方交通大学

2001

一、

1

（

2

分）】

A

．广义表

B.

二叉树

C.

稀疏矩阵

D.

串

10

．以下那一个术语与数据的存储结构无关？（

）【北方交通大学

2001

一、

2

（

2

分）

A

．栈

B.

哈希表

C.

线索树

D.

双向链表

11

．在下面的程序 段中，对

x

的赋值语句的频度为（

）【北京工商大学

2001

一、

10

（

3

分）】

FOR i:=1 TO n DO

FOR j:=1 TO n DO

x:=x+1;

A

．

O(2n) B

．

O(n) C

．

O(n2) D

．

O(log2n)

12

．程序段

FOR i:=n-1 DOWNTO 1 DO

FOR j:=1 TO i DO

IF A[j]>A[j+1]

THEN A[j]

与

A[j+1]

对换；

其中

n

为正整数，则最后一行的语句频度在最坏情况下是（

）【 南京理工大学

1998

一、

1(2

分

)

】

A. O

（

n

）

B. O(nlogn) C. O(n3) D. O(n2)

13

．以下哪个数据结构不是多型数据类型（

）【中山大学

1999

一、

3

（

1

分）】

A

．栈

B

．广义表

C

．有向图

D

．字符串

14

．以下数据结构中，（

）是非线性数据结构【中山大学

1999

一、

4

】

A

．树

B

．字符串

C

．队

D

．栈

15.

下列数据中，（

）是非线性数据结构。【北京理工大学

2001

六、

1

（

2

分）】

A

．栈

B.

队列

C.

完全二叉树

D.

堆

16

．连续存储设计时，存储单元的地址（

）。【中山大学

1999

一、

1

（

1

分）】

A

．一定连续

B

．一定不连续

C

．不一定连续

D

．部分连续，部分不连续

17

．以下属于逻辑结构的是（

）。【西安电子科技大学应用

2001

一、

1

】

A

．顺序表

B.

哈希表

C.

有序表

D.

单链表

答案如下：

1.B 2.C 3.1C 3.2B 4.B 5.D

6.C 7.C 8.D 9.D 10.A 11.C

12.D 13.D 14.A 15.C 16.A 17.C

二、填空题篇

1< /p>

．数据的物理结构包括＿＿的表示和＿＿的表示。【燕山大学

1998

一、

1

（

2

分）】

2.

对于给定的

n

个元素

,

可以构造出的逻辑结构有＿（

1

）＿

，＿（

2

）＿，＿（

3

）＿，

< p>__

（

4

）

_

四种。

【中科院计算所

1999

二、

1

（

4

分）】

3

．数据的逻辑结构是指＿＿

。【北京邮电大学

2001

二、

1

（

2

分）】

4

．一个数据结构在计算机中＿＿称为存储结构。【华中理工大学

2000

一、

1

（

1

分）】

5

．抽象数据类型的定义仅取决于它的一组

__

（

1

）

_

，而与

_

（

2

）

_

无关，即不论其内部结构如何变化 ，只

要它的

_

（

3

）

_

不变，都不影响其外部使用。【山东大学

2001

三、

3

（

2

分）】

6

．数据结构中评价算法的两个重要指标是＿＿【北京理工大学

2001

七、

1

（

2

分）】

7.

数据结构是研讨数据的

_

（

1

）

_

和

_

（

< p>2

）

_

，

以及它们之间的相互关系，

并对与这种结构定义相应的

_

（

3

）

_

，设计出相应的（

4

）

_

。【西安电子科技大学

1998

二、

2

（

3

分）】

8

．

一个算法具有

5< /p>

个特性

:

＿（

1

）＿、＿（

2

）＿、＿（

3

）＿，有零个或多个输入、有一个或多个输 出。

【华中理工大学

2000

一、

2

（

5

分）】【燕山大学

1998

一、

2

（

5

分）】

9

．已知如下程序段

FOR i:= n DOWNTO 1 DO {

语句

1}

BEGIN

x:=x+1

；

{

语句

2}

FOR j:=n DOWNTO i DO {

语句

3}

y:=y+1; {

语句

4}

END

；

语句

1

执行的频度为＿（

1

）＿；语句

2

执行的频度为＿（

2

）＿；语句

3< /p>

执行的频度为＿（

3

）＿；语

句

< p>4

执行的频度为＿（

4

）＿。【北方交通大学

1999

二、

4

（

5

分）】

10

．在下面的程序段中，对ｘ的赋值语句的频度为

__ ____

（表示为

n

的函数）

FOR

i

：＝１

TO n

DO

FOR

j

：＝１

TO i

DO

FOR

k

：＝

1

TO

j

DO

ｘ：＝ｘ＋

delta

；

【北京工业大学

1999

一、

6

（

2

分）】

11.

下面程序段中带下划线的语句的执行次数的数量级是：

< p>

【合肥工业大学

1999

三、

< p>1

（

2

分）

】

i

：

=1

；

WHILE i

：

=i*2;

12.

下面程序段中带下划线的语句的执行次数的数量级是

( )

。【合肥工业大学

2000

三、

1

（

2

分）】

i:=1;

WHILE i

；

13.

下面程序段中带有下划线的语句的执行次数的数量级是

( )

【合肥工业大学

2001

三、

1

（

2

分）

】

i

：

=n*n WHILE i<>1 DO i:=i div 2;

14.

计算机执行下面的语句时，语句

s

的执行次数为

_______

。【南京理工大学

2000

二、

1

（

1.5

分）】

FOR(i=l

；

i

；

i++)

FOR(j=n;j>=i;j--)

s;

15. < /p>

下面程序段的时间复杂度为

________

。

(n >1)

sum=1

；

for (i=0;sum

【南京理工大学

2001

二、

1

（

2

分）】

16

．

设

m.n

均为自然 数，

m

可表示为一些不超过

n

的自然数之和，

f(m,n)

为这种表示方式的数目。

例

f(5,3) =5

，

有

5

种表示方式：

3+2

，

3+1+1

，

2+2+1

，

2+1+1+1

，

1+1+1+1+1

。

①以下是该函数的程序段，请将未完成的部分填入，使之完整

int f(m,n)

int m,n;

{ if(m==1)

return (1) ;

if(n==1){

return (2) }

if(m

{return f(m,m);}

if (m==n)

{return 1+ (3) }

return f(m.n-1)+f(m-n, (4) );

}

②执行程序，

f(6,4)=

。

【中科院软件所

1997

二、

1

（

9

分）】

17. < /p>

在有

n

个选手参加的单循环赛中，总共将进行

___ ___

场比赛。【合肥工业大学

1999

三、

8< /p>

（

2

分）】

答案如下：

1

．数据元素

数据元素间关系

2

．集合

线性结构

树形结构

图状结构或网状结构。

3

．

数据的组织形式，

即数据元素之间逻辑关系的 总体。

而逻辑关系是指数据元素之间的关联方式或称“邻

接关系”。

4

．表示（又称映像）。

5

．（

1

）逻辑特性

（

2

）在计算机内部如何表示和实现

（

3

）数学特性。

6

．算法的时间复杂度和空间复杂度。

7

．（

1

）逻辑结构（

2

）物理结构（

3

）操作（运算）（

4

）算法。

8

．（

1

）有穷性

（

2

）确定性

（

3

）可行性。

9

．（

1

）

n+1

（

2

）

n

（

3

）

n(n+3)/2

（

4

）

n(n+1)/2

。

10

．

1+

（

1+2++

（

1+2+3

）+?+（1+2+?+n）

=n(n+1 )(n+2)/6 O(n3)

11. log2n

12. nlog2n

13. log2n2

14. (n+3)(n-2)/2

15. O(n)

16.

① (1)1

(2)1 (3)f(m,n-1) (4)n

② 9

17. n(n-1)/2

三、判断题篇

1.

数据元素是数据的最小单位。

( )

【北京邮电大学

1998

一、

1

（

2

分）】【青岛大学

2000

一、

1

（

1

分）】

【上海交通大学

1998

一、

1

】

【山东师范大学

2001

一、

1

（

2

分）】

2.

记录是数据处理的最小单位。

( )

【上海海运学院

1998

一、

5

（

1

分）】

3.

数据的逻辑结构是指数据的各数据项之间的逻辑关系；

( )

【北京邮电大学

2002

一、

1

（

1

分）】

4

．

算法的优劣与算法描述语言无关，

但 与所用计算机有关。

( )

【大连海事大学

2001 < /p>

一、

10

（

1

分）

】

5

．

健壮的算法不会因非法的输入数据 而出现莫名其妙的状态。

( )

【大连海事大学

2001

一、

11

（

1

分）

】

6

．算法可以用不同的语言描述，如果用

C

< p>语言或

PASCAL

语言等高级语言来描述，则算法实际上就是程序

了。

( )

【西安交通大学

1996

二、

7

（

3

分）】

7

．程序一定是算法。

( )

【燕山大学

1998

二、

2

（

2

分）并改错】

8

． 数据的物理结构是指数据在计算机内的实际存储形式。

( )

【山东师范大学

2001

一、

2

（

2

分）】

9.

数据结构的抽象操作的定义与具体实现有关。

( )

【华南理工大学

2002

一、

1

（

1

分）】

答案如下：

1. ×

2. ×

3.×

4.×

5. √

6. ×

7. ×

8. √

9.×

10.×

11.×

12. √

13. ×

四、应用题篇

1.

数据结构是一门研究什么内容的学科？【燕山大学

1999

二、

1

（

4

分）】

2.

数据元素之间的关系在计算机中有几种表示方法？各有什么特点？【燕山大学

1999

二、

2

（

4

分）】

3.

数据类型和抽象数据类型是如何定义的。

二者有何 相同和不同之处，

抽象数据类型的主要特点是什么？

使用抽象数据类型的 主要好处是什么？【北京邮电大学

1994

一（

8

分）】

4.

回答问题（每题

2

分）【山东工业大学

1997

一

（

8

分）】

（

1

）在数据结构课 程中，数据的逻辑结构，数据的存储结构及数据的运算之间存在着怎样的关系？

（

2

）若逻辑结构相 同但存储结构不同，则为不同的数据结构。这样的说法对吗？举例说明之。

（

3

）在给定的逻辑 结构及其存储表示上可以定义不同的运算集合，从而得到不同的数据结构。这样说

法对吗 ？举例说明之。

（

4

）评价各种不同数据结构的标准是什么？

< /p>

5

．

评价一个好的算法，

您是从哪几方面来 考虑的？

【大连海事大学

1996

二、

3

（

2

分）

】

【中山大学

< p> 1998

三、

1

（

5

分）】

6

．解释和比较以下各组概念【华南师范大学

2000

一（

10

分）】

（

1

）抽象数据类型及数据类型

（

2

）数据结构、逻辑结构、存储结构

（

3

）抽象数据类型【哈尔滨工业大学

2000

一、

1

（

3

分）】

（

4

）算法的时间复杂性

【河海大学

1998

一、

2

（

3

分）】

（

5

）算法【吉林工业大学

1999

一、

1

（

2

分）】

（

6

）频度【吉林工业大学

1999

一、

2

（

2

分）】

7.

根据数据元素之间的逻辑关系，一般有哪几类基本的数据结构？【北京科技大学

1998

一、

1

】【同济

大学

1998

】

8

．对于一个数据结构，一 般包括哪三个方面的讨论？【北京科技大学

1999

一、

1

（

2

分）】

9.

当你为解决某一问题而选择数据结构时，应从哪些方面考虑？【西 安电子北京科技大学

2000

】

10.

若将数据结构定义为一个二元组

（

D

，

R

）

,

说明符号

< p>D

，

R

应分别表示什么？

【北京科技大学

2001

一 、

1

（

2

分）】

11

．数据结构与数据类型有什么区别？【哈尔滨工业大学

2001

三、

1

（

3

分）】

12

．数据的存储结构由哪四种基本的存储方法实现？【山东科技大学< /p>

2001

一、

1

（

4

分）】

13

．

若有

100

个学生 ，

每个学生有学号，

姓名，

平均成绩，

采用什么样 的数据结构最方便，

写出这些结构？

【山东师范大学

1996

二、

2

（

2

分）】

14.

运算是数据结构的一个重要方面。试举一例，说明两个数据结构 的逻辑结构和存储方式完全相同，只

是对于运算的定义不同。因而两个结构具有显著不同 的特性，是两个不同的结构。【北京大学

1998

一、

1

（

5

分）】

15.

在编制管理通讯录的程序时

,

什么样的数据结构合适

?

为什么

?

【

长沙铁道学院

1998

四、

3(6

分

)

】

16.

试举一例，说明对相同的逻辑结构

,

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

【北京理

工大学

2000

三、

1

（< /p>

4.5

分）】

17.

有 实现同一功能的两个算法

A1

和

A2

，

< p>其中

A1

的时间复杂度为

Tl=O(2n)

，

A2

的时间复杂度为

T2=O(n2)

，

仅就时间复杂度而言，请具体分析这两个算法哪一个好。【北京航空航天大学

2000

二（

10

分）】

18

．设计一数据结构，用来表示某一银行储户的基本信息：

账号、姓名、开户年月日、储蓄类型、存入累

加数、利息、帐面总数。【浙江大学

1994

一

、

3

（

5

分）】

19.

写出下面算法中带标号语句的频度。

TYPE ar=ARRAY[1..n] OF datatype;