专升本数据结构试题解析

第2部分 习题解析

第1章 绪论

1.1 选择题

1. 算法的时间复杂度取决于（ C ）

A）问题的规模 B） 待处理数据的初态 C） A和B

【答案】C

2.计算机算法指的是解决问题的步骤序列，它必须具备（B ） 这三个特性。

A）可执行性、可移植性、可扩充性 B） 可执行性、确定性、有穷性

C） 确定性、有穷性、稳定性 D） 易读性、稳定性、安全性

【答案】B

5．从逻辑上可以把数据结构分为（ C ）两大类。

A）动态结构、静态结构 B）顺序结构、链式结构

C）线性结构、非线性结构 D）初等结构、构造型结构

【答案】C

6．在下面的程序段中，对x的赋值的语句频度为（ C ）

for(i=0;i<n;i++)

for(j=0;j<n;j++) x=x+1;

A） O(2n) B）O(n) C．O(n2) D．O(log2n)

【答案】C

7．下面的程序段中， n为正整数，则最后一行的语句频度在最坏情况下是（D ）

for(i=n-1;i>=1;i--)

for(j=1;j<=i;j++)

if (A[j]>A[j+1])

A[j]与A[j+1]对换；

A. O（n） B） O(nlog2n) C） O(n3) D） O(n2)

【答案】D

1.2 填空题

2. 对于给定的n个元素,可以构造出的逻辑结构有_____________，_____________， _____________四种。

【答案】（1）集合 （2）线性结构 （3）树形结构（4）图状结构或网状结构

4．数据结构中评价算法的两个重要指标是_____________。

【答案】算法的时间复杂度和空间复杂度。

5. 数据结构是研讨数据的_____________和构定义相应的_____________，设计出相应的_____________。

【答案】（1）逻辑结构（2）物理结构（3）操作（运算）（4）算法。

6．一个算法具有5个特性：_____________、_____________、_____________，有零个或多个输入、有一个或多个输出。

【答案】（1）有穷性 （2）确定性 （3）可行性。

9．已知如下程序段

for(i=n;i>0;i--) {语句1}

{ x=x+1; {语句2}

for(j=n;j>=i;j--) {语句3}

y=y+1; {语句4}

}

语句1执行的频度为_____________；语句2执行的频度为_____________；语句3执行的频度为_____________；语句4执行的频度为_____________。

【答案】（1）n+1 （2）n （3）n(n+3)/2 （4）n(n+1)/2

10．在下面的程序段中，对ｘ的赋值语句的频度为_____________（表示为n的函数）

for(i=0;i>n;i++)

for(j=0;j>i;j++)

for(k=0;k>j;k++)

ｘ=ｘ+delta;