第一章 单元测试

1、单选题：
关于数据结构以下说法正确的是（ ）。
选项：
A:数据结构是带有结构的各数据项的集合
B:数据元素是数据的最小单位
C:数据项是数据的基本单位
D:数据对象是带结构的数据元素的子集
答案: 【数据对象是带结构的数据元素的子集】

2、单选题：
数据结构的定义是（ ）。
选项：
A:相互之间存在一种或多种特定关系的数据元素的集合
B:数据的存储结构
C:一组性质相同的数据元素的集合
D:一种数据类型
答案: 【相互之间存在一种或多种特定关系的数据元素的集合】

3、单选题：
在数据结构中，与所使用的计算机无关的是数据的（ ）结构。
选项：
A:存储
B:逻辑
C:逻辑和存储
D:物理
答案: 【逻辑】

4、单选题：
数据结构在计算机内存中的表示是指（ ）。
选项：
A:数据的存储结构
B:数据元素之间的关系
C:数据的逻辑结构
D:数据结构
答案: 【数据元素之间的关系】

5、单选题：
在存储数据时，通常不仅要存储各数据元素的值，而且还要存储（ ）。
选项：
A:数据的存储方法
B:数据元素之间的关系
C:数据元素的类型
D:数据的处理方法
答案: 【数据元素之间的关系】

6、单选题：
在数据结构中，从逻辑上可以把数据结构分成（ ）。
选项：
A:线性结构和非线性结构
B:内部结构和外部结构
C:紧凑结构和非紧凑结构
D:动态结构和静态结构
答案: 【线性结构和非线性结构】

7、单选题：
可以用（ ）定义一个完整的数据结构。
选项：
A:数据元素
B:抽象数据类型
C:数据对象
D:数据关系
答案: 【抽象数据类型】

8、单选题：
数据的存储结构包括（ ）。
选项：
A:连续结构和非连续结构
B:线性结构和非线性结构
C:虚拟结构和抽象结构
D:逻辑结构和物理结构
答案: 【连续结构和非连续结构】

9、单选题：
计算机算法指的是解决问题的步骤序列，它必须具备（ ） 这五个特性。
选项：
A:易读性、稳定性、安全性、输入、输出
B:可执行性、确定性、有穷性、输入、输出
C:确定性、有穷性、稳定性、输入、输出
D:可执行性、可移植性、可扩充性、输入、输出
答案: 【可执行性、确定性、有穷性、输入、输出】

10、单选题：
算法的时间复杂度取决于（ ）。
选项：
A:待处理数据的初态
B:问题的规模
C:算法执行的实际时间
D:问题的规模和待处理数据的初态
答案: 【问题的规模和待处理数据的初态】

11、单选题：
在下面的程序段中，对x的赋值的语句频度为（ ）。for(i=0;i<n;i++)for(j=0;j<n;j++)x=x+1;
选项：
A:O(n2)
B:O(log2n)
C:O(2n)
D:O(n)
答案: 【O(n2)】

12、单选题：
下面的程序段中，n为正整数，则最后一行的语句频度在最坏情况下是（ ）for(i=n-1;i>=1;i--)for(j=1;j<=i;j++)if (A[j]>A[j+1])A[j]与A[j+1]对换；
选项：
A:O(nlog2n)
B:O(n3)
C:O(n2)
D:O(n)
答案: 【O(n2)】

13、单选题：
算法分析的目的是（ ）。
选项：
A:研究算法中的输入和输出的关系
B:分析算法的易懂性和文档性
C:找出数据结构的合理性
D:分析算法的效率以求改进
答案: 【分析算法的效率以求改进】

14、单选题：
算法指的是（ ）。
选项：
A:解决问题的方法
B:计算机程序
C:求解特定问题的指令有限序列
D:查找或排序过程
答案: 【求解特定问题的指令有限序列】

15、单选题：
算法的效率主要是指（ ）
选项：
A:算法的时间效率
B:其他说法都不对
C:算法的空间效率和时间效率
D:算法的空间效率
答案: 【算法的空间效率和时间效率】

16、单选题：
试分析下面各程序段的时间复杂度为（ ）。i=1;while(i<=n)i=i*3;
选项：
A:O(log3n)
B:O(log2n)
C:O(1)
D:O(n)
答案: 【O(log3n)】

17、单选题：
计算下列程序的渐进时间复杂度为（ ）。x=n; //n>1y=0;while(x≥(y+1)* (y+1))y++;
选项：
A:O(n)
B:O(log3n)
C:O(sqrt(n))
D:O(1)
答案: 【O(sqrt(n))】

第二章 单元测试

1、单选题：
线性表的顺序存储结构是一种（ ）的存储结构。
选项：
A:散列存取
B:顺序存取
C:随机存取
D:索引存取
答案: 【随机存取】

2、单选题：
对线性表的定义是（ ）。
选项：
A:一个无限序列，可以为空
B:一个有限序列，可以为空
C:一个无限序列，不可以为空
D:一个有限序列，不可以为空
答案: 【一个有限序列，可以为空】

3、单选题：
线性结构的数据元素之间存在一种（ ）。
选项：
A:一对多关系
B:多对多关系
C:一对一关系
D:多对一关系
答案: 【一对一关系】

4、单选题：
有关线性表L=(a1，a2,……an)，下列说法正确的是（ ）。
选项：
A:每个元素都有一个直接前驱和一个直接后继
B:线性表中至少有一个元素
C:表中诸元素的排列必须是由小到大或由大到小
D:除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。
答案: 【除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。】

5、单选题：
以下关于顺序表的说法中，正确的是（ ）。
选项：
A:顺序表可以利用一维数组表示,因此顺序表与一维数组在结构上是一致的，它们可以通用
B:顺序表和一维数组一样,都可以按下标随机(或直接)访问，顺序表还可以从某一指定元素开始,向前或向后逐个元素顺序访问
C:在顺序表中每一元素的数据类型还可以是顺序表
D:在顺序表中,逻辑上相邻的元素在物理位置上不一定相邻
答案: 【顺序表和一维数组一样,都可以按下标随机(或直接)访问，顺序表还可以从某一指定元素开始,向前或向后逐个元素顺序访问】

6、单选题：
顺序表具有的特点是（ ）。
选项：
A:可随机访问任一元素
B:插入、删除不需要移动元素
C:所需空间不必连续
D:不必事先估计存储空间
答案: 【可随机访问任一元素】

7、单选题：
若长度为n的顺序表在其第i个位置插入一个新元素，需移动的元素个数是（ ）。
选项：
A:n
B:i
C:n-i
D:n-i+1
答案: 【n-i+1】

8、单选题：
向一个有126个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（ ）。
选项：
A:7
B:8
C:63
D:63.5
答案: 【63】

9、单选题：
假设删除长度为n的顺序表中的每个元素的概率相同，则删除一个元素平均要移动的元素个数是（ ）。
选项：
A:n/2
B:n
C:(n-1)/2
D:(n+1)/2
答案: 【(n-1)/2】

10、单选题：
假设长度为127的顺序表，在任意位置上插入和删除元素都是等概率的，删除一个新元素时需平均移动表中的（ ）个元素。
选项：
A:63.5
B:63
C:127
D:64
答案: 【63】

11、单选题：
若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ ）(1<=i<=n+1)。
选项：
A:O(n2)
B:O(n)
C:O(0)
D:O(1)
答案: 【O(n)】

12、单选题：
在长度为n的顺序表中删除一个元素的时间复杂度为（ ）。
选项：
A:O(1)
B:O(log2n)
C:O(n)
D:O(n^2)
答案: 【O(n)】

13、单选题：
若设一个顺序表的长度为n,那么，在表中顺序查找一个值为x的元素时，在等概率的情况下，查找成功的数据平均比较次数为（ ） 。
选项：
A:(n-1)/2
B:(n+1)/2
C:n
D:NULL
答案: 【(n+1)/2】

14、单选题：
在n个结点的顺序表中，算法的时间复杂度是O(n)的操作是（ ）。
选项：
A:访问第i个结点（1≤i≤n）
B:将n个结点从小到大排序
C:在第i个结点后插入一个新结点（1≤i≤n）
D:求第i个结点的直接前驱（2≤i≤n）
答案: 【在第i个结点后插入一个新结点（1≤i≤n）】

15、单选题：
线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ ）。
选项：
A:一定是不连续的
B:必须是连续的
C:连续或不连续都可以
D:部分地址必须是连续的
答案: 【连续或不连续都可以】

16、单选题：
在单链表中，要将s所指结点插入到p所指结点之后，其语句应为（ ）。
选项：
A:s->next=p+1; p->next=s;
B:s->next=p->next; p->next=s;
C:s->next=p->next; p->next=s->next;
D:(*p).next=s; (*s).next=(*p).next;
答案: 【s->next=p->next; p->next=s;】

17、单选题：
已知L是带头结点的单链表，则删除首元结点的语句是（ ）。
选项：
A:L=L->next;
B:L->next=L;
C:L->next=L->next->next;
D:L=L->next->next;
答案: 【L->next=L->next->next;】

18、单选题：
在一个单链表中,若删除p所指结点的后继结点q(注:P既不是第一个结点,也不是最后一个结点)，则执行（ ）操作。
选项：
A:p=p->next->next;
B:p-next=q->next;
C:p=q->next;
D:q->next=p->next;
答案: 【p-next=q->next;】

19、单选题：
单链表的存储结构中增加了一个头结点，关于头结点的描述中，下面哪一项是错误的（ ）
选项：
A:在单链表中增加头结点，插入或删除首元结点时不必进行特殊处理
B:头结点中不存储链表的数据元素，而是一些诸如表长之类的辅助信息
C:若链表中有头结点，则头指针一定不为空
D:有没有头结点对算法执行的效率没有任何影响
答案: 【有没有头结点对算法执行的效率没有任何影响】

20、单选题：
带头结点的单链表head为空的判定条件是（ ）。
选项：
A:head->next==NULL
B:head==NULL
C:head!=NULL
D:head->next==L
答案: 【head->next==NULL】

21、单选题：
单链表的存储密度（ ）。
选项：
A:大于1
B:等于1
C:小于1
D:不能确定
答案: 【小于1】

22、单选题：
以下关于单链表的叙述中，不正确的是（ ）。
选项：
A:逻辑上相邻的元素物理上不必相邻
B:插入、删除运算操作方便，不必移动结点
C:可以通过头结点直接计算第i个结点的存储地址
D:结点除自身信息外还包括指针域，因此存储密度小于顺序存储结构
答案: 【可以通过头结点直接计算第i个结点的存储地址】

23、单选题：
单链表又称线性链表，在单链表上实施删除操作（ ）。
选项：
A:既需移动结点，又需要改变结点指针
B:不需移动结点，只需改变结点指针
C:只需移动结点，不需改变结点指针
D:不需要移动结点，不需改变结点指针
答案: 【不需移动结点，只需改变结点指针】

24、单选题：
单链表又称线性链表，在单链表上实施插入操作（ ）
选项：
A:既需移动结点，又需要改变结点指针
B:不需要移动结点，不需改变结点指针
C:不需移动结点，只需改变结点指针
D:只需移动结点，不需改变结点指针
答案: 【不需移动结点，只需改变结点指针】

25、单选题：
在双向循环链表中，在p指针所指的结点后插入q所指向的新结点，其修改指针的操作是（ ）。
选项：
A:q->prior=p; q->next=p->next; p->next->prior=q; p->next=q;
B:p->next=q; p->next->prior=q; q->prior=p; q->next=p->next;
C:p->next=q; q->prior=p; p->next->prior=q; q->next=q;
D:q->prior=p; q->next=p->next; p->next=q; p->next->prior=q;
答案: 【q->prior=p; q->next=p->next; p->next->prior=q; p->next=q;】

26、单选题：
在双向链表存储结构中，删除p所指的结点时须修改指针（ ）。
选项：
A:p->prior=p->next->next; p->next=p->prior->prior;
B:p->prior->next=p; p->prior=p->prior->prior;
C:p->next=p->next->next; p->next->prior=p;
D:p->next->prior=p->prior; p->prior->next=p->next;
答案: 【p->next->prior=p->prior; p->prior->next=p->next;】

27、单选题：
以下链表结构中，从当前结点出发能够访问到任一结点的是（ ）。
选项：
A:双向链表和循环链表
B:单向链表、双向链表和循环链表
C:单向链表和循环链表
D:单向链表和双向链表
答案: 【双向链表和循环链表】

28、单选题：
循环链表的主要特点是（ ）
选项：
A:在进行插入删除运算时，能更好的保证链表不断开
B:在链表的任意位置出发都能扫描到整个链表
C:已知某个结点的位置后，能容易找到它的直接前驱
D:不再需要头指针了
答案: 【在链表的任意位置出发都能扫描到整个链表】

29、单选题：
双向链表的主要特点是（ ）
选项：
A:在链表的任意位置出发都能扫描到整个链表
B:不再需要头指针了
C:在进行插入删除运算时，能更好的保证链表不断开
D:已知某个结点的位置后，能容易找到它的直接前驱
答案: 【已知某个结点的位置后，能容易找到它的直接前驱】

30、单选题：
线性表Ｌ在（ ）情况下适用于使用链式结构实现。
选项：
A:Ｌ中含有大量的结点
B:需经常修改Ｌ中的结点值
C:Ｌ中结点结构复杂
D:需不断对Ｌ进行删除插入
答案: 【需不断对Ｌ进行删除插入】

31、单选题：
若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。
选项：
A:单循环链表
B:双链表
C:带头结点的双循环链表
D:顺序表
答案: 【顺序表】

32、单选题：
某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。
选项：
A:单链表
B:双链表
C:循环链表
D:仅有尾指针的单循环链表
答案: 【仅有尾指针的单循环链表】