考研数据结构1800题 第一章 绪论

《数据结构 1800 题》

1
第一章 绪论


一、选择题
一、选择题
1. 算法的计算量的大小称为计算的（ ） 。 【北京邮电大学 2000 二、3 （20/8 分） 】
A．效率 B. 复杂性 C. 现实性 D. 难度
2. 算法的时间复杂度取决于（ ） 【中科院计算所 1998 二、1 （2 分） 】
A．问题的规模 B. 待处理数据的初态 C. A 和 B
3.计算机算法指的是（1） ，它必须具备（2） 这三个特性。
(1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法
(2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性
C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性
【南京理工大学 1999 一、1（2 分） 【武汉交通科技大学 1996 一、1（ 4 分） 】
4．一个算法应该是（ ） 。 【中山大学 1998 二、1（2 分） 】
A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A 和 C.
5. 下面关于算法说法错误的是（ ） 【南京理工大学 2000 一、1（1.5 分） 】
A．算法最终必须由计算机程序实现
B.为解决某问题的算法同为该问题编写的程序含义是相同的
C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的
6. 下面说法错误的是（ ） 【南京理工大学 2000 一、2 （1.5 分） 】
(1）算法原地工作的含义是指不需要任何额外的辅助空间
（2）在相同的规模 n 下，复杂度 O(n)的算法在时间上总是优于复杂度 O(2
n)的算法
（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
F

OR j:=1 TO n DO
x:=x+1;
A． O(2n) B．O(n) C．O(n
2) D．O(log2
n)
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 为正整数，则最后一行的语句频度在最坏情况下是（ ）

《数据结构 1800 题》

2
A. O（n） B. O(nlogn) C. O(n
3) D. O(n
2) 【南京理工大学 1998 一、1(2 分)】
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. 数据元素是数据的最小单位。( )
【北京邮电大学 1998 一、1（2 分） 】 【青岛大学 2000 一、1 （1 分） 】
【上海交通大学 1998 一、1】 【山东师范大学 2001 一、1 （2 分） 】
2. 记录是数据处理的最小单位。 ( ) 【上海海运学院 1998 一、5（1 分） 】
3. 数据的逻辑结构是指数据的各数据项之间的逻辑关系；( )【北京邮电大学 2002 一、1（1 分） 】
4．算法的优劣与算法描述语言无关，但与所用计算机有关。( )【大连海事大学 2001 一、10（1 分） 】
5． 健壮的算法不会因非法的输入数据而出现莫名其妙的状态。 ( ) 【大连海事大学 2001 一、 11 （1 分） 】
6．算法可以用不同的语言描述，如果用 C 语言或 PASCAL 语言等高级语言来描述，则算法实际上就是程序
了。( )【西安交通大学 1996 二、7（3 分）】
7．程序一定是算法。( )【燕山大学 1998 二、2（2 分）并改错】
8．数据的物理结构是指数据在计算机内的实际存储形式。( )【山东师范大学 2001 一、2（2 分） 】
9. 数据结构的抽象操作的定义与具体实现有关。( )【华南理工大学 2002 一、1（1 分） 】
10. 在顺序存储结构中，有时也存储数据结构中元素之间的关系。( )【华南理工大学 2002 一、2 （1 分） 】
11. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( )【上海海

运学院 1999 一、1（1 分） 】
12. 数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。( )
【华南理工大学 2002 一、5（1 分） 】
13. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构. ( )
【上海海运学院 1998 一、1（1 分） 】

三、填空

三、填空
1．数据的物理结构包括 的表示和 的表示。 【燕山大学 1998 一、1（2 分） 】
2. 对于给定的 n 个元素,可以构造出的逻辑结构有 （1） ， （2） ， （3） ，__（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）_和_（2）_，以及它们之间的相互关系，并对与这种结构定义相应的_（3）
_，设计出相应的（4）_。 【西安电子科技大学 1998 二、2（3 分） 】
8． 一个算法具有 5 个特性: （1） 、 （2） 、 （3） ，有零个或多个输入、有一个或多个输出。

《数据结构 1800 题》

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 执行的频度为 （3） ；语句 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.下面程序段中带下划线的语句的执行次数的数量级是： 【合肥工业大学 1999 三、1（2 分） 】
i：=1； WHILE i12. 下面程序段中带下划线的语句的执行次数的数量级是( )。 【合肥工业大学 2000 三、1（2 分） 】
i:=1;
WHILE i13. 下面程序段中带有下划线的语句的执行次数的数量级是( ) 【合肥工业大学 2001 三、1（2 分） 】
i：=n*n
WHI

LE i<>1 DO i:=i div 2;
14. 计算机执行下面的语句时，语句 s 的执行次数为 _______ 。 【南京理工大学 2000 二、1（1.5 分） 】
FOR(i=l；iFOR(j=n;j>=i;j--)
s;
15. 下面程序段的时间复杂度为________。(n>1)
sum=1；
for (i=0;sum16． 设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) );

《数据结构 1800 题》

4
}
②执行程序，f(6,4)= 。 【中科院软件所 1997 二、1 （9 分） 】
17. 在有 n 个选手参加的单循环赛中，总共将进行______场比赛。 【合肥工业大学 1999 三、8（2 分） 】

四、应用题
四、应用题
1. 数据结构是一门研究什么内容的学科？【燕山大学 1999 二、1 （4 分） 】
2. 数据元素之间的关系在计算机中有几种表示方法？各有什么特点？【燕山大学 1999 二、2（4 分） 】
3. 数据类型和抽象数据类型是如何定义的。 二者有何相同和不同之处， 抽象数据类型的主要特点是什么？
使用抽象数据类型的主要好处是什么？【北京邮电大学 1994 一（8 分） 】
4. 回答问题（每题 2 分） 【山东工业大学 1997 一 （8 分） 】
（1）在数据结构课程中，数据的逻辑结构，数据的存储结构及数据的运算之间存在着怎样的关系？
（2）若逻辑结构相同但存储结构不同，则为不同的数据结构。这样的说法对吗？举例说明之。
（3）在给定的逻辑结构及其存储表示上可以定义不同的运算集合，从而得到不同的数据结构。这样说
法对吗？举例说明之。
（4）评价各种不同数据结构的标准是什么？
5．评价一个好的算法，您是从哪几方面来考虑的？
【大连海事大学 1996 二、3 （2 分） 】 【中山大学 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）,说明符号 D，R 应分别表示什么？
【北京科技大学 2001 一、1（2 分） 】
11．数据结构与数据类型有什么区别？【哈尔滨工业大学 2001 三、1（3 分） 】
12．数据的存储结构由哪四种基本的存储方法实现？【山东科技大学 2001 一、1（4 分） 】
13．若有 100 个学生，每个学生有学号，姓名，平均成绩，采用什么样的数据结构最方便，写出这些结构？
【山东师范大学 1996 二、2（2 分） 】
14. 运算是数据结构的一个重要方面。试举一例，说明两个数据结构的逻辑结构和存储方式完全相同，只
是对于运算的定义不同。因而两个结构具有显著不同的特性，是两个不同的结构。
【北京大学 1998 一、1（5 分） 】
15. 在编制管理通讯录的程序时, 什么样的数据结构合适? 为什么?【 长沙铁道学院 1998 四、3(6 分)】
16. 试举一例，说明对相同的逻辑结构,同一种运算在不同的存储方式下实现，其运算效率不同。
【北京理工大学 2000 三、1（4.5 分） 】
17. 有实现同一功能的两个算法 A1 和 A2， 其中 A1 的时间复杂度为 Tl=O(2
n)， A2 的时间复杂度为 T2=O(n
2)，
仅就时间复杂度而言，请具体分析这两个算法哪一个好。 【北京航空航天大学 2000 二（10 分） 】
18．设计一数据结构，用来表示某一银行储户的基本信息： 账号、姓名、开户年月日、储蓄类型、存入
累加数、利息、帐面总数。【浙江大学 1994 一 、3（5 分）】
19. 写出下面算法中带标号语句的频度。

《数据结构 1800 题》

5
TYPE ar=ARRAY[1..n] OF datatype;
PROCEDURE perm ( a: ar; k, n: integer);
VAR x: datatype; i:integer;
BEGIN
（1）IF k=n
THEN BEGIN
（2）FOR i:=1 TO n DO
（3）write (a[i]);
writeln;
END
ELSE BEGIN
（4） FOR i:=k TO n DO
（5）a[i]:=a[i]+i*i;
（6） perm (a, k+1, n);
END;
END;
设 k 的初值等于 1。
【北京邮电大学 1997 二（10 分） 】
20. 分析下面程序段中循环语句的执行次数。
i:=0;s:=0;n:=100;
REPEAT
i:=i+1;
s:=s+10*i;
UNTIL NOT((i【北京邮电大学 1998 四、1（5 分） 】
21．下列算法对一 n 位二进制数加 1，假如无溢出，该算法的最坏时间复杂性是什么？并分析它的平均时

间复杂性。
TYPE num=ARRAY [1..n] of [0..1]；
PROCEDURE Inc （VAR a：num） ；
VAR i：integer；
BEGIN i：=n；
WHILE A[i]=1 DO
BEGIN A[i]：=0； i：=i-1；END；
END；
A[i]：=1；
END Inc；
【东南大学 1998 三 (8 分) 1994 二（15 分） 】
22. 阅读下列算法，指出算法 A 的功能和时间复杂性
PROCEDURE A (h,g:pointer);
(h,g 分别为单循环链表（single linked circular list）中两个结点指针)
PROCEDURE B(s,q:pointer)；
VAR p:pointer;
BEGIN
p:=s;

《数据结构 1800 题》

6
WHILE p^.next<>q DO p:=p^.next;
p^.next:=s;
END;(of B)
BEGIN
B(h,g); B(g,h);
END;（of A）
【东南大学 1999 二（10 分） 】
23. 调用下列 C 函数 f(n)或 PASACAL 函数 f(n) 回答下列问题 :
（1） 试指出 f(n)值的大小，并写出 f(n) 值的推导过程;
（2） 假定 n= 5，试指出 f(5)值的大小和执行 f(5)时的输出结果 。
C 函数： int f(int n)
{ int i,j，k,sum= 0;
for(i=l; i{for(j=n;j>i-1; j--)
for(k=1;ksum++;
printf("sum=%d\n",sum)；
}
return (sum);
} 【华中理工大学 2000 六（10 分） 】
24．设 n 是偶数，试计算运行下列程序段后 m 的值并给出该程序段的时间复杂度。
m:=0;
FOR i:=1 TO n DO
FOR j:=2*i TO n DO
m:=m+1;
【南京邮电大学 2000 一、1】
25．有下列运行时间函数：
（1）T1 (n)=1000; （2）T2(n)=n
2+1000n; （3）T3(n)=3n
3+100n
2+n+1;
分别写出相应的大 O 表示的运算时间。
【吉林工业大学 1999 二（12 分） 】
26. 试给出下面两个算法的运算时间。
（1） for i←1 to n do
x ← x+1
END
（2） for i← 1 to n do
for j←1 to n do
x← x+1
end
end
【中科院自动化研究所 1995 二、2 （6 分） 】
27. 斐波那契数列 Fn定义如下
F0=0， Fl=1， Fn=Fn-1+Fn-2, n=2,3...
请就此斐波那契数列，回答下列问题。
(1) (7 分) 在递归计算 Fn的时候，需要对较小的 Fn-1，Fn-2，…, Fl, F0精确计算多少次?

《数据结构 1800 题》

7
(2) (5 分) 如果用大 O 表示法，试给出递归计算 Fn时递归函数的时间复杂度录多少?
【清华大学 2000 二（12 分） 】
28．将下列函数，按它们在 n→∝时的无穷大阶数，从小到大排序。
n, n-n
3+7n
5, nlogn, 2
n/2, n
3, logn, n
1/2+logn, (3/2)
n,
?
?
?
?
?
?
n
n
2
,n!, n
2+logn
【中科院计算所 1995 】