数据结构考试题库（含参考答案）（2）
第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(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为正整数，则最后⼀⾏的语句频度在最坏情况下是（）
A. O（n）
B. O(nlogn)
C. O(n3)
D. O(n2) 【南京理⼯⼤学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个元素，可以构造出的逻辑结构有集合，线性结
构，树形结构，__图状结构或⽹状结构_四种。
【中科院计算所1999 ⼆、1（4分）】
3．数据的逻辑结构是指数据的组织形式，即数据元素之间逻辑关系的总体。⽽逻
辑关系是指数据元素之间的关联⽅式或称“邻接关系”。【北京邮电⼤
学2001 ⼆、1（2分）】
4．⼀个数据结构在计算机中的表⽰（或称映像）称为存储结构（⼜数
据的物理结构）。【华中理⼯⼤学2000 ⼀、1（1分）】
5．抽象数据类型的定义仅取决于它的⼀组__逻辑特性_，⽽与_在计算机内部如何表⽰和实现_⽆关，即不论其内部结构如何变化，只要它的_数学特性_不变，都不影响其外部使⽤。【⼭东⼤学2001 三、3（2分）】
6．数据结构中评价算法的两个重要指标是算法的时间复杂度和空间复杂
度【北京理⼯⼤学2001 七、1（2分）】
7. 数据结构是研讨数据的_逻辑结构_和_物理结构_，以及它们之间的相互关系，并对与这种结构定义相应的_操作（运算）_，设计出相应的_算法。【西安电⼦科技⼤学1998 ⼆、2（3分）】
8．⼀个算法具有5个特性: 有穷性、确定性、可⾏性，有零个或多个输⼊、
有⼀个或多个输出。
【华中理⼯⼤学2000 ⼀、2（5分）】【燕⼭⼤学1998 ⼀、2（5分）】
9．已知如下程序段
FOR i:= n DOWNTO1DO{语句1}
BEGIN
x:=x+1；{语句2}
FOR j:=n DOWNTO i DO{语句3}
y:=y+1;{语句4}
语句1执⾏的频度为n+1 ；语句2执⾏的频度为n ；语句3执⾏的频度
为n(n+3)/2 ；语句4执⾏的频度为n(n+1)/2 。【北⽅交通⼤学1999 ⼆、4（5
分）】
10．在下⾯的程序段中，对ｘ的赋值语句的频度为___1+（1+2++（1+2+3）+…+（1+2+…+n）
=n(n+1)(n+2)/6 ___（表⽰为n的函数）
FOR i：＝１TO n DO
FOR j：＝１TO i DO
FOR k：＝1 TO j DO
ｘ：＝ｘ＋delta；
【北京⼯业⼤学1999 ⼀、6（2分）】
11.下⾯程序段中带下划线的语句的执⾏次数的数量级是：log2n 【合肥⼯业⼤学1999三、1（2分）
i：=1；WHILE i
12. 下⾯程序段中带下划线的语句的执⾏次数的数量级是( nlog2n )。【合肥⼯
业⼤学2000 三、1（2分）】
i:=1;
WHILE i
13. 下⾯程序段中带有下划线的语句的执⾏次数的数量级是( log2n2) 【合肥⼯业
⼤学2001 三、1（2分）】
i：=n*n WHILE i<>1 DO i:=i div 2;
14. 计算机执⾏下⾯的语句时，语句s的执⾏次数为___(n+3)(n-2)/2 ____ 。【南京
理⼯⼤学2000⼆、1（1.5分）】
FOR(i=l；i
FOR(j=n;j>=i;j--)
s;
15. 下⾯程序段的时间复杂度为___O（n）_____。(n>1)
sum=1；
for (i=0;sum
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){
if(m
{return f(m,m);}
if (m==n)
{return 1+ f(m,n-1) ;}
return f(m.n-1)+f(m-n, n );
}
②执⾏程序，f(6,4)= 9 。【中科院软件所1997 ⼆、1 （9分）】
17. 在有n个选⼿参加的单循环赛中，总共将进⾏__n(n-1)/2____场⽐赛。【合肥⼯业⼤学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分）】

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。