习题

一、基础题

1．对包含n个元素的数组进行顺序搜索时，若搜索每个元素的概率相同，则平均搜索长度为_____。

A．n/2

B．n

C．(n−1)/2

D．(n+1)/2

2．下面说法正确的是_____。

A．健壮的算法不会因非法的输入数据而出现莫名其妙的状态

B．算法的优劣与算法描述语言无关，但与所用计算机环境因素有关

C．数据的逻辑结构依赖于数据的存储结构

D．以上几个都是错误的

3．从逻辑上可以把数据结构分为_____两大类。

A．初等结构、构造型结构

B．顺序结构、链式结构

C．线性结构、非线性结构

D．动态结构、静态结构

4．数据采用链式存储时，存储单元的地址_____。

A．一定连续

B．一定不连续

C．不一定连续

D．部分连续，部分不连续

5．算法的时间复杂度取决于_____。

A．问题规模

B．计算机的软硬件配置

C．两者都是

D．两者都不是

6．下面的程序段的时间复杂度为_____。

A．O(2n)

B．O(n)

C．O(n2)

D．O(log2n)

二、扩展题

1．简述下列概念：数据、数据元素、数据项。

2．什么是数据结构？

3．简述逻辑结构的四种基本关系。

4．最常见的存储结构有哪两种？

5．算法有哪些特征？

6．算法与程序的区别与联系是什么？

7．简述衡量算法优劣的基本标准。

8．对于下列程序段，分析带下划线语句的执行次数，并给出它们的时间复杂度。