第一章练习
一、选择题
1.试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。
【解答】
学生成绩表，逻辑结构是线性结构，可以顺序存储（也可以链式存储），运算可以有插入、删除、查询，等等。
2.在数据结构中，从逻辑上可以把数据结构分成（ C ）。
A．动态结构和静态结构 B．紧凑结构和非紧凑结构
C．线性结构和非线性结构 D．内部结构和外部结构
3.与数据元素本身的形式、内容、相对位置、个数无关的是数据的（ C ）。
A．存储结构 B．存储实现
C．逻辑结构 D．运算实现
4.通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（ B ）。
A．数据具有同一特点
B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致
C．每个数据元素都一样
D．数据元素所包含的数据项的个数要相等
5.以下说法正确的是（ D ）。
A．数据元素是数据的最小单位
B．数据项是数据的基本单位
C．数据结构是带有结构的各数据项的集合
D．一些表面上很不相同的数据可以有相同的逻辑结构
6.算法的时间复杂度取决于（ D ）。
A．问题的规模 B．待处理数据的初态
C．计算机的配置 D．A和B
7.以下数据结构中，（ A ）是非线性数据结构
A．树 B．字符串 C．队列 D．栈
8.数据结构在计算机内存中的表示是指（ A ）。
A．数据的存储结构 B．数据结构
C．数据的逻辑结构 D．数据元素之间的关系
9.在数据结构中，与所使用的计算机无关的是数据的（ A ） 结构。
A．逻辑 B．存储 C．逻辑和存储 D．物理
10.在存储数据时，通常不仅要存储各数据元素的值，而且还要存储（ C ）
A．数据的处理方法 B．数据元素的类型
C．数据元素之间的关系 D．数据的存储方法
11.在决定选取何种存储结构时，一般不考虑（ A ）
A．各结点的值如何 B．结点个数的多少
C．对数据有哪些运算 D．所用的编程语言实现这种结构是否方便。
12.算法分析的目的是（ C ）
A．找出数据结构的合理性 B．研究算法中的输入和输出的关系
C．分析算法的效率以求改进 D．分析算法的易读性和文档性
13.算法分析的两个主要方面是（ A ）。
A．空间复杂度和时间复杂度 B．正确性和简明性
C．可读性和文档性 D．数据复杂性和程序复杂性
14.通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（ B ）。
A．数据元素具有同一特点
B．不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致
C．每个数据元素都一样
D．数据元素所包含的数据项的个数要相等
15.下面几种算法时间复杂度中，值最大的是（ D ）。
A.O(nlog2n) B.O(n2) C.O(n) D.O(2n)
16.即使输入非法数据，算法也能适当地做出反应或进行处理，不会产生预料不到的运行结果，这种算法好坏的评价因素称为（ B ）。
A.正确性 B.健壮性 C.易读性 D.时空性
二、填空题
1.下面程序段的时间复杂度是 n^2 。
s=0；
for（ i＝0； i＜n； i＋＋）
for（j＝0；j＜n；j＋＋）
s ＋＝B[i][j]；
sum ＝ s ；
2.下面程序段的时间复杂度是 n*m 。
for（ i ＝0； i＜n； i＋＋）
for（j＝0；j＜m；j＋＋）
A[i][j] ＝ 0；
3.下面程序段的时间复杂度是 log3(n) 。注:log以3为底，n的对数
i ＝ 1；
while（i＜＝n）
i ＝ i * 3；
4.下面程序段的时间复杂度是 log2(n) 。注：log以2为底，n的对数
i ＝ 1；
while（i<=n）
i = i * 2；
5.数据逻辑结构包括集合、线性结构、树形结构和 图状结构或网状结构 四种类型。
6.线性结构中元素之间存在 一对一 关系。
7.树形结构中元素之间存在 一对多 关系。
8.图形结构中元素之间存在 多对多 关系。
9.树形结构和图状结构合称 非线性结构 。
10.所有存储结点存放在一个连续的存储区里，利用结点在存储器中的相对位置来表示数据元素之间的逻辑关系。这种存储方式是 顺序存储 。
11.数据结构的基本存储方法是顺序、 链式存储 、索引和散列存储 。
12.设计一个“好”的算法应考虑达到以下目标：正确性、可读性、 健壮性 和效率与低存储量需求。
13.评估一个算法的优劣，通常从 时间复杂度 和空间复杂度两个方面考察。
14.算法的5个重要特性是有穷性、确定性、 可行性 、输入和输出。
15.若一个算法中的语句频度之和为T(n)=3720n+4nlogn，则算法的时间复杂度为___O（nlogn）_____。
三、判断题
1.数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的 关系和运算等的学科。（ ✔ ）
2.线性结构中元素之间存在一对一关系，树形结构中元素之间存在多对多关系，图形结构中元素之间存在一对多关系。（ ✖ ）
3.算法分析的两个主要方面是数据复杂性和程序复杂性。（ ✖ ）
4.算法分析的目的是找出数据结构的合理性。（ ✖ ）
5.数据结构中，与所使用的计算机无关的是数据的物理结构。（ ✖ ）
6.散列是逻辑结构的表示形式。（ ✖ ）
7.在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个 。（ ✔ ）
8.链式存储是将所有存储结点存放在一个连续的存储区里，利用结点在存储器中的相对位置来表示数据元素之间的逻辑关系。（ ✖ ）
9.某些情况下，可以不用考虑算法的存储复杂度。（ ✔ ）
10.计算机算法必须具备输入、输出和易读性、稳定性和安全性等5个特性。（ ✖ ）
11.计算机算法指的是解决问题的有限运算序列。（ ✔ ）
12.若一个算法中的语句频度之和为T(n)=3720n+4，则算法的时间复杂度为O(n)。（ ✔ ）
13.数据的存储结构由哪四种基本的存储方法实现？
解答：顺序存储、链式存储、索引存储、散列存储
14.当你为解决某一问题而选择数据结构时，应从哪些方面考虑？
15.在编制管理通讯录的程序时, 什么样的数据结构合适? 为什么?
16.分析以下程序段的时间复杂度。
inti，j，k；
For（i=0；i〈n；i++〉①
For（j=0；j〈n；j++〉②
{
c[i][j]=0；③
for（k=0；k〈n；k++〉④
c[i][j]=c[i][j]+a[i][k]+b[k][j]；⑤
}
注：标红色的是我暂时不确定的