2024年4月30日发(作者：)

第一部分习题

一、选择

1、 下列叙述中关于好的编程风格，正确的描述是：C

A、 程序中的注释是可有可无的 为了增强可读性我们要在必要语句之后加注释

B、 对递归定义的数据结构不要使用递归过程 递归的可读性强

C、 递归应是封闭的，尽量少使用全局变量

D、 多采用一些技巧以提高程序运行效率

2、通常从正确性、易读性、健壮性、高效性等四个方面评价算法(包括程序)的质量。

以下解释错误的是 ( C )

A、正确性 算法应能正确地实现预定的功能(即处理要求)

B、易读性 算法应易于阅读和理解 以便于调试 修改和扩充

C、健壮性 当环境发生变化时，算法能适当地做出反应或进行处理，不会产生不需

要的运行结果 见课本14页

D、高效性 即达到所需要的时间性能

3、以下说法正确的是 ( D )

A、数据元素是数据的最小单位

B、数据项是数据的基本单位

C、数据结构是带有结构的各数据项的集合

D、数据结构是带有结构的数据元素的集合

4、对于顺序表，以下说法错误的是 （ A ）

A、顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址

B、顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列

C、顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻

D、顺序表的特点是:逻辑上相邻的元素，存储在物理位置也相邻的单元中

5、对顺序表上的插入、删除算法的时间复杂性分析来说，通常以（B ）为标准操作

A、条件判断 B、结点移动

C、算术表达式 D、赋值语句

6、对于顺序表的优缺点，以下说法错误的是 （ C ）

A、无需为表示结点间的逻辑关系而增加额外的存储空间

B、可以方便地随机存取表中的任一结点

C、插入和删除运算较方便

D、容易造成一部分空间长期闲置而得不到充分利用

7、链表不具有的特点是：A

A、可随机访问任一个元素 B、插入删除不需要移动元素

C、不必事先估计存储空间 D、所需空间与线性表长度成正比

8、 若线性表最常用的操作是存取第i个元素及其前驱的值，则采用（D ）存储方式节

省时间

A单链表B、双向链表 C、单循环链表D、顺序表

9、有时为了叙述方便，可以对一些概念进行简称，以下说法错误的是 （D ）

A将“指针型变量”简称为“指针”

B将“头指针变量”称为“头指针”

C将“修改某指针型变量的值”称为“修改某指针”

D将“p中指针所指结点”称为“P值”

10．设指针P指向双链表的某一结点，则双链表结构的对称性可用（C ）式来刻画

1

A p->prior->next->==p->next->next

B p->prior->prior->==p->next->prior

C p->prior->next->==p->next->prior

D p->next->next==p->prior->prior

11.以下说错误的是 （ A ）

A对循环来说，从表中任一结点出发都能通过前后操作而扫描整个循环链表

B对单链表来说，只有从头结点开始才能扫描表中全部结点

C双链表的特点是找结点的前趋和后继都很容易

D对双链表来说，结点*P的存储位置既存放在其前趋结点的后继指针域中，也存

放在它的后继结点的前趋指针域中。

12．在循环链表中，将头指针改设为尾指针（rear）后，其头结点和尾结点的存储位置

分别是 （ B ）

A rear和rear->next->next

B rear->next 和rear

C rear->next->next和rear

D rear和rear->next

13.以下说错误的是 ( C)

A 对于线性表来说，定位运算在顺序表和单链表上的量级均为O（n）

B读表元运算在顺序表上只需常数时间O（1）便可实现，因此顺序表是一种随机

存取结构

C在链表上实现读表元运算的平均时间复杂性为O（1）

D插入、删除操作在链表上的实现可在O（n）时间内完成

14．循环链表主要优点是 （D ）

A不再需要头指针了

B已知某个结点的位置后，能够容易找到它的直接前趋

C在进行插入、删除运算时，能更好地保证链表不断开

D从表中任一结点出发都能扫描到整个链表

15．以下说法错误的是 （B ）

A数据的物理结构是指数据在计算机内实际的存储形式

B算法和程序没有区别，所以在数据结构中二者是通用的

C对链表进行插人和删除操作时，不必移动结点

D双链表中至多只有一个结点的后继指针为空

16．以下说法正确的是C

A线性结构的基本特征是：每个结点有且仅有一个直接前趋和一个直接后继

B线性表的各种基本运算在顺序存储结构上的实现均比在链式存储结构上的实现

效率要低

C在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素位置

有关

D顺序存储的线性表的插入和删除操作不需要付出很大的代价，因为平均每次操作

只有近一半的元素需要移动

17．以下说法错误的是 （ D）

A求表长、定位这二种运算在采用顺序存储结构时实现的效率不比采用链式存储

结构时实现的效率低

B顺序存储的线性表可以随机存取

2