第一章 单元测试

1、 以下可以用于定义一个完整的数据结构的是（ ）。

A:抽象数据类型
B:数据元素
C:数据关系
D:数据对象
答案: 抽象数据类型

2、 以下关于数据结构的说法中，正确的是（ ）。

A:数据的存储结构独立于其逻辑结构
B:数据的逻辑结构唯一决定了其存储结构
C:数据的逻辑结构独立于其存储结构
D:数据结构仅由其逻辑结构和存储结构决定
答案: 数据的逻辑结构独立于其存储结构

3、 计算算法的时间复杂度是属于一种（ ）。

A:事后分析估算的方法
B:事前分析估算的方法
C:事后统计的方法
D:事前统计的方法
答案: 事前分析估算的方法

4、 算法的时间复杂度主要取决于（ ）。

A:数据的类型
B:待处理数据的值
C:计算的环境
D:问题的规模
答案: 问题的规模

5、
int suanfa(int n){
int i=1， s=1;
while(s＜n) s+=++I;
return i;
}
上面算法的时间复杂度是O()。 （ ）

A:对
B:错
答案: 对

第二章 单元测试

1、 线性表L=(a1，a2，……，an)，下列说法正确的是（ ）。

A:每个元素都有一个直接前驱和一个直接后继
B:线性表中至少要有一个元素
C:表中诸元素的排列顺序必须是由小到大或由大到小
D:除第一个和最后一个元素外，其余每个元素都由一个且仅有一个直接前驱和直接后继
答案: 除第一个和最后一个元素外，其余每个元素都由一个且仅有一个直接前驱和直接后继

2、 在长度为n的顺序表中删除第i (1≤i≤n) 个元素时，需向前移动（ ）个元素。

A:n-i+1
B:i-1
C:n-i
D:n
答案: n-i+1

3、 如果线性表最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。

A:双链表
B:仅有头指针的单循环链表
C:仅有尾指针的单循环链表
D:单链表
答案: 仅有尾指针的单循环链表

4、 在一个单链表中，若删除p所指向结点的后续结点，则所需修改指针的操作为（ ）。

A:p=p-＞next;
B:p=p-＞next;p-＞next=p-＞next-＞next;
C:p=p-＞next-＞next;
D:p-＞next=p-＞next-＞next;
答案: p-＞next=p-＞next-＞next;

5、 设线性表有2n个元素，以下操作中，在单链表上实现要比在顺序表上实现效率更高的（ ）。

A:交换第i个元素和第2n-i-1个元素(i=， 1， …， n-1)
B:顺序输出前k个元素
C:删除指定元素
D:在最后一个元素的后面插入一个新元素
答案: 删除指定元素

第三章 单元测试

1、 栈是（ ）。

A:链式存储的线性结构
B:顺序存储的线性结构
C:限制存取点的线性结构
D:限制存取点的非线性结构
答案: 限制存取点的线性结构

2、 一个栈的输入序列为：a，b，c，d，e，则栈的不可能输出的序列是（ ）。

A:d，e，c，b，a
B:d，c，e，a，b
C:a，b，c，d，e
D:e，d，c，b，a
答案: d，c，e，a，b

3、 判断一个循环队列Q（最多n个元素）为满的条件是（ ）。

A:Q-＞rear==Q-＞front+1
B:Q-＞front==(Q-＞rear-1)%n
C:Q-＞front==(Q-＞rear+1)%n
D:Q-＞rear==Q-＞front
答案: Q-＞front==(Q-＞rear+1)%n

4、 在一个链队列中，front和rear分别为头指针和尾指针，则插入一个结点s的操作为（ ）。

A:front=front-＞next;
B:s-＞next=front; front=s;
C:rear-＞next=s; rear=s;
D:s-＞next=rear; rear=s;
答案: rear-＞next=s; rear=s;

5、 在解决计算机主机和打印机之间速度不匹配问题时，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取走数据打印。该缓冲区应该是一个（ ）结构。

A:数组
B:堆栈
C:线性表
D:队列
答案: 队列

第四章 单元测试

1、 与线性表相比，串的插入和删除操作的特点是（ ）。

A:需要更多的辅助空间
B:通常以串整体作为操作对象
C:算法的时间复杂度较高
D:涉及移动的元素更多
答案: 通常以串整体作为操作对象

2、 设串长为n，模式串长为m，则KMP算法所需的附加空间为（ ）。

A:O(n)
B:O(m*n)
C:O(m)
D:O(nlog2m)
答案: O(m)

3、 数组A[0..5，0..6]的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5][5]的地址是（ ）。

A:1175
B:1205
C:1180
D:1210
答案: 1175

4、 对一些特殊矩阵采用压缩存储的目的主要是为了（ ）。

A:减少不必要的存储空间的开销
B:去掉矩阵中的

5、 稀疏矩阵的三元组存储方法（ ）。

A:比十字链表法更高效
B:矩阵的非零元个数和位置在操作过程中变化不大时较有效
C:实现转置运算很简单，只需将每个三元组的行标和列标交换
D:是一种链式存储方法
答案: 矩阵的非零元个数和位置在操作过程中变化不大时较有效