习 题 1
1-1 选择题
（1）顺序存储结构中数据元素之间的逻辑关系是由（ ）表示的，链接存储结构中的数据元素之间的逻辑关系是由（ ）表示的。
A.线性结构
B.非线性结构
C.存储位置
D.指针
（2）假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的数据结构应该是（ ）。
A.树
B.图
C.线性表
D.集合
（3）计算机所处理的数据一般具有某种内在联系，这是指（ ）。
A.数据和数据之间存在某种关系
B.元素和元素之间存在某种关系
C.元素内部具有某种结构
D.数据项和数据项之间存在某种关系
（4）对于数据结构的描述，下列说法中不正确的是（ ）。
A.相同的逻辑结构对应的存储结构也必相同
B.数据结构由逻辑结构、存储结构和基本操作三方面组成
C.对数据结构基本操作的实现与存储结构有关
D.数据的存储结构是数据的逻辑结构的机内实现
（5）算法指的是（ ）。
A.对特定问题求解步骤的一种描述，是指令的有限序列
B.计算机程序
C.解决问题的计算方法
D.数据处理
（6）下面（ ）不是算法所必须具备的特性。
A.有穷性
B.确切性
C.高效性
D.可行性
（7）算法分析的目的是（ ），算法分析的两个主要方面是（ ）。
A.找出数据结构的合理性
B.研究算法中输入和输出的关系
C.分析算法的效率以求改进
D.分析算法的易读性和文档性
E.空间性能和时间性能
F.正确性和简明性
G.可读性和文档性
H.数据复杂性和程序复杂性
（8）假设时间复杂度为O（n2）的算法在有200个元素的数组上运行需要3.1毫秒，则在有400个元素的数组上运行需要（ ）毫秒。
A.3.1
B.6.2
C.12.4
D.9.61
（9）下列程序段加下划线的语句执行（ ）次。
for（m=0，i=1；i＜=n；i++）
for（j=1；j＜=2*i；j++）
m=m+1；
A.n2
B.3n
C.n（n+1）
D.n3
1-2 分析以下各程序段，并用大O记号表示其执行时间。
（1）i=1；k=0；
while（i＜=n）
{
k=k+10*i；
i++；
}
（2）i=1；k=0；
do
{
k=k+10*i；
i++；
}while（i＜=n）；
（3）i=1；j=0；
while（i+j＜=n）
if（i＞j）j++；
elsei++；
（4）y=0；
while（（y+1）*（y+1）＜=n）
y=y+1；
（5）for（i=1；i＜=n；i++）
for（j=1；j＜=i；j++）
for（k=1；k＜=j；k++）
x++；
（6）for（i=1；i＜=n；i++）
if（2*i＜=n）
for（j=2*i；j＜=n；j++）
y=y+i*j；
1-3 解答下列问题
（1）假设有数据结构（D，R），其中D={1，2，3，4，5，6}，R={（1，2），（1，4），（2，3），（2，4），（3，4），（3，5），（3，6），（4，5），（5，6）}。试画出其逻辑结构图并指出属于何种结构。
（2）为整数定义一个抽象数据类型，包含整数的常见运算，每个运算对应一个基本操作，每个基本操作的接口需定义前置条件、输入、功能、输出和后置条件。
（3）求多项式A（x）的算法可根据下列两个公式之一来设计：
① A（x）=anxn+an-1xn-1+…+a1x+a0
② A（x）=（…（anx+an-1）x+…+a1）x+a0
根据算法的时间复杂度分析比较这两种算法的优劣。
1-4 算法设计（要求：用伪代码和类C语言描述两种方法描述算法，并分析时间复杂度）
（1）找出整型数组A[n]中的最大值和次最大值。
（2）对一个整型数组A[n]设计一个排序算法。
（3）判断给定字符串是否是回文。所谓回文是正读和反读均相同的字符串，例如＂abcba＂或＂abba＂是回文，而＂abcda＂不是回文。
（4）已知数组A[n]中的元素为整型，设计算法将其调整为左右两部分，左边所有元素为奇数，右边所有元素为偶数，并要求算法的时间复杂度为O（n）。
（5）荷兰国旗问题。要求重新排列一个由字符R，W，B（R代表红色，W代表白色，B代表兰色，这都是荷兰国旗的颜色）构成的数组，使得所有的R都排在最前面，W排在其次，B排在最后。为荷兰国旗问题设计一个算法，其时间性能是O（n）。