百度文库 - 让每个人平等地提升自我
习题
知识点：数据结构的定义
一、选择题
1① 数据结构通常是研究数据的（ A ）及它们之间的相互联系。 A．存储和逻辑结构 B．存储结构 C．顺序结构 D．链式存储结构
2① 数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为（ C ）
A．存储结构 B．逻辑结构 C． 顺序存储结构 D．链式存储结构 3① 线性结构是数据元素之间存在一种（ D ）。
A．一对多关系 B. 多对多关系 C 多对一关系 D 一对一关系 4① 计算机内部数据处理的基本单位是（ B ）。 A. 数据 B．数据元素 C.数据项 D．数据库
5② 从逻辑上可以把数据结构分为（C ）两大类。【武汉交通科技大学 1996】 A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 二、填空题
1① 数据结构按逻辑结构可分为四大类，它们分别是 集合 、 线性 、 树 、 图 。
2① 数据的存储结构可用四种基本的存储方法表示，它们分别是 顺序 、 链式 、 散列 、 索引 。 三、判断题
（ F）1① 数据元素是数据的最小单位。 （ T ）2① 记录是数据处理的最小单位。
（ F ）3① 数据的逻辑结构是指数据的各数据项之间的逻辑关系。 （ T ）4① 数据的物理结构是指数据在计算机内的实际存储形式。 四、简答题
1① 简述什么是数据结构?
2② 数据结构与数据类型有什么区别? 【哈尔滨工业大学 2001】
知识点：算法的概念
一、选择题
1① 计算机算法指的是（C ）
A．计算方法 B．排序方法 C．解决问题的有限运算序列 D．调度方法
2① 算法分析的目的是（ （1）C ），算法分析的两个主要方面（ （2）A ）． （1） A．找出数据结构的合理性 B．研究算法中的输入与输出的关系 4
百度文库 - 让每个人平等地提升自我
C．分析算法的效率以求改进 D．分析算法的易查性和文档性 （2） A．空间复杂度和时间复杂度 B．正确性和简明性 C．可读性和文档性 D．数据复杂性和程序复杂性 3② 设语句X++的时间是单位时间，则语句： for（i=1;i<=n;i++） x++;
时间复杂度为（ C ）。
A．O（1） B．O （n） C．O （n2） D．O （n3） 4② 算法的计算量的大小称为计算的（ B ）。【北京邮电大学2000】 A．效率 B．复杂性 C．现实性 D．难度
5② 算法的时间复杂度取决于（ C ）【中科院计算所 1998】 A．问题的规模 B．待处理数据的初态 C．A 和B
6② 下面关于算法说法错误的是（ A ）【南京理工大学 2000】 A．算法最终必须由计算机程序实现
B．为解决某问题的算法同为该问题编写的程序含义是相同的 C．算法的可行性是指指令不能有二义性 D．以上几个都是错误的
7② 下面说法错误的是（ D ）【南京理工大学 2000】 （1）算法原地工作的含义是指不需要任何额外的辅助空间
（2）在相同的规模n 下，复杂度O（n）的算法在时间上总是优于复杂度O（2n）的算法
（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．（1） B．（1）,（2） C．（1）,（4） D．（3） 8② 程序段 for（i=n-1;i>=1;i++）
for（ j=1;j<= i;j++）
if（ A[j]>A[j+1]） A[j]与A[j+1]对换；
其中 n 为正整数，则最后一行的语句频度在最坏情况下是（ D ）【南京理工大学1998】 A．O（n） B．O（nlog2n） C． O（n3） D． O（n2） 二、填空题
1① 以夹杂自然语言和程序语句的形式来描述解决问题的方法称为____伪码________。 2① 一个算法的效率可分为___时间______效率和__空间_______效率． 3② 有一个程序片断如下：
4
百度文库 - 让每个人平等地提升自我
for（i=0;i 则其时间复杂度为：_O（n）________ 4② 有一个程序片断如下： for（i=0;i m=1; 则其时间复杂度为： O（n3） 5② 有一个程序片断如下： for（i=0;i while（j>=2） j=j/2; } 则其时间复杂度为： O（nlog2n） 三、判断题 （ T ）1① 算法的优劣与算法描述语言无关，但与所用计算机有关。 （ T ）2① 健壮的算法不会因非法的输入数据而出现莫名其妙的状态。 （ F ）3① 程序一定是算法。 四、简答题 1① 如何判断一个算法的好坏? 2③ 调用下列C 函数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;k printf（\）; 4 百度文库 - 让每个人平等地提升自我 } return （sum）; } 【华中理工大学 2000】 4
数据结构第章习题参考答案
