第1章 绪 论（习题）

习题

一、 选择题

1、以下说法错误的是( )

A.用数字式计算机解决问题的实质是对数据的加工处理 B.程序设计的实质是数据处理

C.数据的逻辑结构表达了数据之间的内在关系 D.数据处理方式总是与数据的逻辑结构相联系

2、根据数据元素之间关系的不同特性，以下四类基本的逻辑结构反映了四类基本的 数据组织形式。以下解释错误的是 ( ) A.集合中任何两个结点之间都有逻辑关系但组织形式松散 B.线性结构中结点按逻辑关系依次排列形成一条\锁链\

C.树形结构具有分支、层次特性，其形态有点像自然界中的树

D.图状结构中的各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接 3、关于逻辑结构，以下说法错误的是 ( )

A.逻辑结构与数据元素本身的形成、内容无关 B.逻辑结构与数据元素的相对位置有关 C.逻辑结构与所含结点个数无关

D.一些表面上很不相同的数据可以有相同的逻辑结构 E.逻辑结构是数据组织的某种\本质性\的东西 4、一个算法应该是（ ）。

A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 5、下面关于算法说法错误的是（ ）

A．算法最终必须由计算机程序实现

B.为解决某问题的算法同为该问题编写的程序含义是相同的

C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6、程序段 FOR(i=n-1;i>=0;i--)

FOR(j=1;j<=n;j++) IF A[j]>A[j+1]

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

其中 n为正整数，则最后一行的语句频度在最坏情况下是（ ）

32

A. O（n） B. O(nlogn) C. O(n) D. O(n)

7、以下说法正确的是

A.数据元素是数据的最小单位 B.数据项是数据的基本单位

C.数据结构是带有结构的各数据项的集合 D.数据结构是带有结构的数据元素的集合 二、填空题

1、通常从___________、___________、___________、___________等几方面评价算法的(包括程序)的质量。

2、对于给定的n个元素,可以构造出的逻辑结构有 ， ， ，__ _四种。 3、一般地，一个存储结构包括__________、__________、__________三个主要部分。 4、抽象数据类型的定义仅取决于它的一组__ _，而与_ _无关，即不论其内部结构如何变

化，只要它的_ _不变，都不影响其外部使用。

5、 一个算法具有5个特性: 、 、 ，有零个或多个输入、有一个或多个输出。 6、一个算法的输入规模或问题的规模是指___________。 三、判断题

1、数据元素是数据的最小单位。

2、数据的逻辑结构是指数据的各数据项之间的逻辑关系； 3、算法的优劣与算法描述语言无关，但与所用计算机有关。 4、程序一定是算法。

5、数据的物理结构是指数据在计算机内的实际存储形式。 6、数据结构的抽象操作的定义与具体实现有关。

7、数据的逻辑结构表达了数据元素之间的关系,它依赖于计算机的存储结构。 四、应用题

1、 解释下列概念：数据；数据元素；数据类型；数据结构；逻辑结构；存储结构；线性结构；非线性结构；算法；算法的时间复杂度；算法的空间复杂度

2 、数据的逻辑结构有哪几种？常用的存储结构有哪几种？

3 、试举一个数据结构的例子，叙述其逻辑结构、存储结构和运算三方面的内容。 4 、什么叫算法？它有哪些特性？

5 、设n为正整数，用大“O”记号，将下列程序段的执行时间表示为n的函数。 （1） int sum1(int n)

{

int p=1,s=0;

for(int i=1;i<=n;i++) {

p*=i； s+=p；

}

return s;

}

（2） int sum2(int n)

{

int s=0;

for(int i=1;i<=n;i++) {

int p=1;

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

p*=j;

s+=p;

}

return s; }

（3） int fun(int n)

{

int i=1,s=1;

while(s

s+=++i;

return i; }

五、算法设计题

1 、 写一算法，从键盘输入若干个非0整数（以0作结束标志），找出其中最大和最小的数，并分析算法的时间复杂度（输入数据不需保存）。

2、设计求解下列问题的类C语言算法，并分析其最坏情况时间复杂性及其量级。 （1） 在数组A[1..n]中查找值为K的元素,若找到则输出其位置i(1<=i<=n),否则输

出0作为标志。

（2） 找出数组A[1..n]中元素的最大值和次最大值（本小题以数组元素的比较为标

准操作）。

本文来源：https://www.bwwdw.com/article/i732.html