第一章 绪论 习题
一．单选
1．数据的逻辑结构被形式地定义为B=(K,R)，其中K是（ ）的有限集合，R是K上的（ ）的有限集合。 A．算法 B．数据元素 C．数据操作 D．逻辑结构 E．操作 F．映像 G．存储 H．关系 2．在数据结构中，从逻辑上可以把数据结构分成（ ） A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．内部结构和外部结构 3．数据结构在计算机内存中的表示是指（ ） A．数据的存储结构 B．数据结构 C．数据的逻辑结构 D．数据元素之间的关系 4．在数据结构中，与所使用的计算机无关的是数据的（ ）结构。 A．逻辑 B．存储 C．逻辑和存储 D．物理 5．算法分析的目的是（ ），算法分析的两个主要方面是（ ）。 A．找出数据结构的合理性 B．研究算法中的输入和输出的关系 C．分析算法的效率以求改进 D．分析算法的易懂性和文档性 E．空间复杂度和时间复杂度 F．正确性和简明性 G．可读性和文档性 H．数据复杂性和程序复杂性 6．计算机算法指的是（ ），它必须具备输入、输出和（ ）等5个特性。 A．计算方法 B．排序方法 C．解决问题的有限运算序列 D．调度方法
E．可行性、可移植性和可扩充性 F．可行性、确定性和有穷性 G．确定性、有穷性和稳定性 H．易读性、稳定性和安全性
7．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储（ ） A．数据的处理方法 B．数据元素的类型 C．数据元素之间的关系 D．数据的存储方法 二．填空
1．数据逻辑结构包括（ ）、（ ）和（ ）三种类型，树形结构和图形结构合称为（ ）
2．在线性结构中，第一个结点（ ）前驱结点，其余每个结点有且只有（ ）个前驱结点；最后一个结点（ ）后续结点，其余每个结点有且只有（ ）个后续结点。
3．在树型结构中，树根结点没有（ ）结点，其余每个结点有且只有（ ）个前驱结点，叶子结点没有（ ）结点，其余每个结点的后续结点可以（ ）。 4．在图形结构中，每个结点的前驱结点数和后续结点数可以（ ）。
5．线性结构中元素之间存在（ ）关系，树形结构中元素之间存在（ ）关系，图形结构中元素之间存在（ ）关系。
三．简答，分析下列程序段的时间复杂度 （1）for (i=0; i1（5）分析如下递归函数的时间复杂度 int fact ( int n ) { if (n<=1) return 1; else
return ( n*fact ( n-1 ) ); }
参
一．1．B H 2.C 3.A 4. A 5. C E 6. C F 7. C 二．1．线性结构、树形结构和图形结构，非线性结构 2．没有 1 没有 1 3．前驱 1 后续 任意多个 4．任意多个 5．一对一 一对多 多对多 三．（1）a[i][j]的语句频度T(n)=n*m ，时间复杂度为O(n*m) （2）设 while循环语句执行T(n)次，有 s=1+2+3+……+T(n)（3）T（n）=1nni0j0i0n1n1n12O(n2)
T(n)（4）设while循环语句执行T（n）次，有3<=n，即T（n）<=log3n=O(log3n)
（5）设fact(n)的运行时间函数是T(n)。则T(n)=1 (n<=1)，T(n)=T(n-1)+O(1) (n>1) 则 T（n）=O(1)+T(n-1)=2*O(1)+T(n-2)=……=(n-1)*O(1)+T(1)=n*O(1)=O(n) 所以时间复杂度为：O(n)
2
