算法最终都必须由计算机程序实现,数据结构第1.2章习题

数据结构练习题

第一章

一．选择题

1.下面属于逻辑结构的是(c)备注：其他都是存储结构，包括循环队列

A 顺序表 B哈希表 C 有序表D 单链表

2.下面关于算法说法错误的是( D ) A．算法最终必须由计算机程序实现(不见得，有些算法是NP完全问题，计算机程序只能实现低数量的值，对于高数量的是实现不了的)

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

C. 算法的可行性是指指令不能有二义性

D. 以上几个都是错误的

3．从逻辑上可以把数据结构分为( C )两大类。A没有此种分法；不按照存储结构划分；D

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

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

4.线性表的静态链表存储结构与顺序存储结构相比优点是( C )。

A. 所有的操作算法实现简单 B. 便于随机存取

C. 便于插入和删除D. 节省存储空间

5.采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为( D )。 A. n B. n/2 C. (n-1)/2 D. (n+1)/2

备注：顺序表的平均查找长度等于所有长度和除以总的次数：

(1+2+3+...+n)/n = (1+n)/2；失败的平局查找次数：(0+1+2+...+n-1)/n=(n-1)/2 所以答案为(1+n)/2

6.数据结构的定义为(D，S)，其中D是( B )的集合。

备注：S是D上关系的集合

A. 算法 B. 数据元素C. 数据操作 D. 逻辑结构

7.以下数据结构中，哪一个是线性结构( D )？

A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串

8.在数据结构中，从逻辑上可以把数据结构分成 ( C )备注：非线性包裹树形和图形结构两种；

A. 动态结构和静态结构 B. 紧凑结构和非紧凑结构

C. 线性结构和非线性结构 D. 内部结构和外部结构

9．下段程序段的时间复杂度是 ( D ).备注：怎么求时间复杂度

i＝1；

while(i<=n) i=i*2；

2 A.O(n/3)B. O(n) C. O(log3n) D. O(log2n)

10．算法分析的目的是( C ).