一、填空题
01、数据结构是一门研究非数值计算的程序设计问题中计算机的 学科。
02、数据结构被形式地定义为 （D,R），其中D是（数据元素）的有限集合，R是D上的（关系）有限集合。 03 、数据结构包括数据的（逻辑结构）、数据的（存储结构）和数据的（运算）这三个方面的内容。 04（线性结构）和（非线性结构）。 、数据结构按逻辑结构可分为两大类，它们分别是 05、线性结构中元素之间存在 （一对一）关系，树形结构中元素之间存在
在（多对多）关系。 （一对多）关系，图形结构中元素之间存
06、在线性结构中，第一个结点 （没有）前驱结点，其余每个结点有且只有
后续结点，其余每个结点有且只有 07、在树形结构中，树根结点没有 点，其余每个结点的后续结点数可以 1个前驱结点；最后一个结点 （没有）
1个后续结点。
（1）个前驱结点；叶子结点没有 （后续）结 （前驱）结点，其余每个结点有且只有 （操作对象）以及它们之间的（关系和运算）等的
（任意多个）。 08、在图形结构中，每个结点的前驱结点数和后续结点数可以 09、数据的存储结构可用四种基本的存储方法表示，它们分别是（任意多个）。 10、 对于给定的n个元素，可以构造出的逻辑结构有 （集合）、（线性结构（顺序））、（链式）、）（索引）、（散） 、（树形结构、（图状结构
四种。 11
、 数据的运算最常用的有 5种，它们分别是（插入）、（删除）、（列修改）。） 、（查找）、（排序）。 12
、 一个算法的效率可分为（时间）效率和（空间）效率。 13 、 数据结构中评价算法的两个重要指标是算法的 （时间复杂度）和（空间复杂度）。 14、 一个数据结构在计算机中的 （映射）称为存储结构。
15
、 算法的五个重要特性是 16
、 已知如下程序段
（有穷性）、（确定性）、（可行性）、输入、输出。 for （i=n; i>=1; i--） //
{ x++; //
语句1 语句2
for （j=n; j>=i; j--） // y++; //
} 语句3
语句4
语句1执行的频度为（n+1）;语句2执行的频度为（n）;语句3执行的频度为（n（n+3）/2 ）
;语句4执 行的频度为（
n（n+1）/2 ）。 17
、 在下面的程序段中，对X的赋值语句的频度为 （n（n+1）（ n+2）/6 for（i=1; i<=n; i++）
for（j=1; j<=i; j++）
for（k=1; k<=j; k++）
x+=y; 解释：1+ （1+2++ （1+2+3） + …+ （1+2+…+n） =n（n +1）（ n+2）/6 O（n
3)
n
2
18、下面程序段中带下划线的语句的执行次数的数量级是 （O（log
)) i=1;
while（i< n）
i=i* ______ 19、下面程序段中带下划线的语句的执行次数的数量级是 (O(n log2))。
i=1； while （i< n） { for（j=1; j<=n; j++） { x=x+1; ________
i=i*2; }
}
n2
20、 下面程序段中带有下划线的语句的执行次数的数量级是
（o（iog 2
))。
i=n*n;
while（i!=1） i=i/2; ____
21
、 计算机执行下面的语句时，“语句 S”的执行次数为
((n+3)(n-2)/2 )。
for（i=1; i
1
语句S；
22、在有n个选手参加的单循环赛中，总共将进行
(n(n-1)/2 )场比赛。
二、判断题
01、数据元素是数据的最小单位。
X 02、数据的逻辑结构是指数据的各数据项之间的逻辑关系。 X
03、算法的优劣与算法描述语言无关，但与所用计算机有关。 V 04、健壮的算法不会因非法的输入数据而出现莫名其妙的状态。
X 05X
、算法可以用不同的语言描述，则算法实际上就是程序了。 06V
、程序一定是算法。 X
07、数据的物理结构是指数据在计算机内的实际存储形式。 X
08、数据结构的抽象操作的定义与具体实现有关。 X
09、在顺序存储结构中，有时也存储数据结构中元素之间的关系。 V
10、 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 X
11、 数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。 12、 数据的逻辑结构说明数据元素之间的顺序关系 ，它依赖于计算机的储存结构。 B01、 三、单项选择题
和运算等的学科。A) 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的 结构 关系 运算 B) 算法
C) 数据的逻辑结构被形式地定义为
B=(K,R)，其中K是_的有限集合，R是K上的__有限集合。 D)
第1空的选项： BD02、 A) 算法 B) 数据元素 C)
数据操作 D) 逻辑结构
第2空的选项： 操作 B) 映像 C) 存储 D) 关系 数据结构在计算机内存中的表示是指 数据的存储结构
数据结构 数据的逻辑结构 数据元素之间的关系 数据结构中，与所使用的计算机无关的是数据的
__结构。
A) 存储 B) 物理 C) 逻辑 D)
物理和存储
A03、算法分析的目的是 _。 A)
找出数据结构的合理性 研究算法中的输入和输出的关系 分析算法的效率以求改进 分析算法的易懂性和文
B)
档性 算法分析的两个主要方面是 空间复杂性和时间复杂性 正确性和简明性 可读性和文档性 数据复杂性和程C) 序复杂性 计算机算法指的是__。
D) 计算方法 排序方法 解决问题的有限运算序列 调度方法 C04、 计算机算法必须具备输入、输出和 可行等5个特性。 A) 性、可移植性和可扩充性 可行性、确定性C05、 和有穷性 确定性、有穷性和稳定性A) B) C) D) A06、 A) B) C) D) C07、 A) B) C) D) B08、 A) B) C)
2
D) 易读性、稳定性和安全性
A09、 在决定选取何种存储结构时，一般不考虑 A)
各结点的值如何
结构个数的多少 对数据有哪些运算
B)
所用编程语言实现这种结构是否方便 在存储数据时，通常不仅要存储各数据元素的值，而还 C) 要存储 D)
数据的处理方法
C10、 数据元素的类型 A)
数据元素之间的关系 数据的存储方法 算法的计算量的大小称为计算的 _o B) 效率 B) 复杂性 C) 现实性 D) 难度
C) 下面说法错误的是 __o
D) 算法原地工作的含义是指不需要任何额外的辅助空间
B11、
在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度 O(2n
)的算法
所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 同一个算法，实现语言的 A) 级别越高，执行效率就越低
A12、 B) (1) 、(2) C) (1) 、(4) D) (3)
(1)
(2) (3) A) (1)
C13(4)
、 从逻辑上可以把数据结构分为—两大类。 A) 动态结构、静态结构 B) 顺序结构、链式结构 C)
线性结构、非线性结构 D)初等结构、构造型结构
D14
、 以下与数据的存储结构无关的术语是 _ A) A15、
循环队列 B) 链表 C) 哈希表
D) 栈 A)
以下数据结构中，__是非线性数据结构。
C16、 树 B) 字符串 C) 队列 D)
A) 以下属于逻辑结构的是 __o 顺序表 B) 哈希表 C) 有序表 D) 单链表
四分析下面各程序段的时间复杂度 、 for (i=0; i< n; i++) 01 、
for (j=0; j A[i][j]=0； 答: 0( m n ) 02s=0; 、 for (i=0; i sum=s; 答： O(n2) 03 、 x=0; for (i=1; i x++; 答： O(n2) 04、 i=1; while(i<=n) i=i*3; 答: O( log3n) 3
数据结构第1章-答案
