单元测验

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: A和B
答案: 【 A和B】

6、单选题：
‌以下数据结构中，（  ）是非线性数据结构‍
选项：
A: 树
B: 字符串
C: 队列
D: 栈
答案: 【 树】

7、单选题：
​‌树形结构是数据元素之间存在一种（  ）。‌​‌‍‌
选项：
A: 一对一关系    
B: 多对多关系 
C: 多对一关系
D: 一对多关系
答案: 【 一对多关系】

8、单选题：
‏ ‎ 设语句x++的时间是单位时间，则以下语句的时间复杂度为（  ）。‎‏ ‎for(i=1; i<=n; i++)‎‏ ‎for(j=i; j<=n; j++)‎‏ ‎x++;‎‏ ‎‎‏ ‎
选项：
A:  O(1) 
B:  O() 
C:  O(n) 
D:  O(logn)
答案: 【  O() 】

9、单选题：
​‍数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（  ）。‍
选项：
A: 低
B: 高
C: 相同
D: 不好说
答案: 【 高】

10、单选题：
计算机内部数据处理的基本单位是（  ）。​​‏​
选项：
A: 数据
B: 数据元素
C: 数据项 
D: 数据库
答案: 【 数据元素】

11、判断题：
数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的。 ​
选项：
A: 正确
B: 错误
答案: 【 正确】

12、判断题：
顺序存储方式只适用于存储线性表。（ ）‍
选项：
A: 正确
B: 错误
答案: 【 错误】

13、判断题：
只有用面向对象的计算机语言才能描述数据结构算法。（ ）​
选项：
A: 正确
B: 错误
答案: 【 错误】

14、判断题：
算法和程序原则上没有区别，在讨论数据结构时二者是通用的。( ) ‎
选项：
A: 正确
B: 错误
答案: 【 错误】

15、判断题：
​‏算法分析的目的是找出数据结构的合理性。（ ）‏
选项：
A: 正确
B: 错误
答案: 【 错误】

16、判断题：
数据的逻辑结构与数据元素本身的内容和形式无关。 ‏
选项：
A: 正确
B: 错误
答案: 【 正确】

17、判断题：
算法和程序都应具有下面一些特征：有输入，有输出，确定性，有穷性，有效性。（ ）​
选项：
A: 正确
B: 错误
答案: 【 错误】

18、判断题：
‏​数据元素是数据的最小单位。​
选项：
A: 正确
B: 错误
答案: 【 错误】

19、填空题：
‍‏下面程序段的时间复杂度是__________________。‏‍‏for(i=0;i<n;i++)‏‍‏for(j=0;j<n;j++)‏‍‏A[i][j]=0;‏‍‏
答案: 【 O(n2 )】

20、填空题：
​​下面程序段的时间复杂度是__________________。​​​i=1;​​​while(i<=n)​​​i=i*3;​​​
答案: 【 O(log3 n)】

21、填空题：
‌​算法时间复杂度的分析通常有两种方法，即事后统计和___________的方法，通常我们对算法求时间复杂度时，采用后一种方法。​‌​
答案: 【 事前估计】

基本概念-单选题

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

2、单选题：
‏以下数据结构中，（  ）是非线性数据结构‏​​​‏​
选项：
A: 树
B: 字符串
C: 队
D: 栈
答案: 【 树】

算法-单选题

1、单选题：
‎‍下面程序段的时间复杂度为_________________________。‍‎  for (int i=0;i<m;i++)‍‎       for (int j=0;j<n;j++)‍‎         a[i][j]=i*j;‍‎‍‎‍
选项：
A: O(m2)
B: O(n2)
C: O(m*n)
D: O(m+n)
答案: 【 O(m*n)】

线性表测试1

1、单选题：
‎顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（    ）。‌
选项：
A: 110‍
B: 108
C: 100
D: 120
答案: 【 108】

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

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

4、单选题：
‌链接存储的存储结构所占存储空间（   ）。​
选项：
A: 分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
B: 只有一部分，存放结点值
C: 只有一部分，存储表示结点间关系的指针
D: 分两部分，一部分存放结点值，另一部分存放结点所占单元数
答案: 【 分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针】

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

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

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

8、单选题：
‍‎ 线性表是________。‎‍‎
选项：
A: 一个有限序列，可以为空
B: 一个有限序列，不可以为空
C: 一个无限序列，可以为空
D: 一个无限序列，不可以为空
答案: 【 一个有限序列，可以为空】

9、单选题：
‎‎线性表采用链式存储时，其地址________。‎
选项：
A: 必须是连续的
B: 一定是不连续的
C: 部分地址必须是连续的
D: 连续与否均可以
答案: 【 连续与否均可以】

10、单选题：
‌从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较________个元素结点。‏
选项：
A: n/2
B: n
C: （n+1）/2
D: （n-1）/2
答案: 【 （n+1）/2】

11、单选题：
‌‏在顺序表中，只要知道_______，就可在相同时间内求出任一结点的存储地址。‏‌‏
选项：
A: 基地址
B: 结点大小
C: 向量大小
D: 基地址和结点大小
答案: 【 基地址和结点大小】

12、判断题：
‌‎在长度为n的顺序表中，求第i个元素的直接前驱算法的时间复杂度为0（1）。（ ）‎
选项：
A: 正确
B: 错误
答案: 【 正确】

13、判断题：
 线性表若采用链式存储表示时，其存储结点的地址可连续也可不连续。（ ） ‍
选项：
A: 正确
B: 错误
答案: 【 正确】

14、判断题：
在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻。（ ）‌
选项：
A: 正确
B: 错误
答案: 【 错误】

15、判断题：
线性表的逻辑顺序总是与其物理顺序一致。（ ）‌
选项：
A: 正确
B: 错误
答案: 【 错误】

16、判断题：
线性表若采用链式存储表示, 在删除时不需要移动元素。（ ） ‏
选项：
A: 正确
B: 错误
答案: 【 正确】

17、判断题：
在线性链表中删除中间的结点时，只需将被删结点释放。（ ）‍
选项：
A: 正确
B: 错误
答案: 【 错误】

18、判断题：
单链表可以实现随机存取。（ ） ‌
选项：
A: 正确
B: 错误
答案: 【 错误】

19、判断题：
‎​顺序表的空间利用率高于链表。（ ）​
选项：
A: 正确
B: 错误
答案: 【 正确】

20、判断题：
顺序表和一维数组一样，都可以按下标随机（或直接）访问。（ ）‎
选项：
A: 正确
B: 错误
答案: 【 正确】

21、判断题：
线性表的顺序存储优于链式存储。（ ）‍​‍
选项：
A: 正确
B: 错误
答案: 【 错误】

22、填空题：
‏在一个长度为n的顺序表的第i个元素之前插入一个元素，需要后移____个元素。‏
答案: 【 n-i+1】

23、填空题：
​线性表是一种典型的_________结构。‏
答案: 【 线性】

24、填空题：
‌顺序表中逻辑上相邻的元素的物理位置________。‏
答案: 【 相邻】

25、填空题：
​对于一个具有n个结点的单链表，在给定值为x的结点后插入一个新结点的时间复杂度为_______。‎
答案: 【 O(n)】

26、填空题：
‍当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用_______存储结构为宜。‍
答案: 【 顺序】

随堂测试

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

线性表单元测试2

1、单选题：
‍将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（   ）。‍
选项：
A: n
B: 2n-1
C: 2n
D: n-1
答案: 【 n】

2、单选题：
​在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时须向后移动（   ）个元素。n-i ‍
选项：
A: n-i
B: n-i +1
C: n-i -1
D: i
答案: 【 n-i +1】

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

4、单选题：
​创建一个包括n个结点的有序单链表的时间复杂度是（    ）。‍
选项：
A: O(1)
B: O(n)
C: O(n^2)
D: O(nlog2n)
答案: 【 O(n^2) 】

5、单选题：
以下说法错误的是（   ）。                                                           ‎     ‎‎ ‎
选项：
A:  求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低
B:  顺序存储的线性表可以随机存取
C:  由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活
D:  线性表的链式存储结构优于顺序存储结构      
答案: 【  线性表的链式存储结构优于顺序存储结构      】

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

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

8、单选题：
在双向循环链表中，在p指针所指的结点后插入q所指向的新结点，其修改指针的操作是（   ）。‏‏‏
选项：
A: p->next=q; q->prior=p; p->next->prior=q; q->next=q;
B: p->next=q; p->next->prior=q; q->prior=p; q->next=p->next;
C: q->prior=p; q->next=p->next; p->next->prior=q; p->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;】

9、判断题：
​ 线性表的链式存储结构优于顺序存储结构‌
选项：
A: 正确
B: 错误
答案: 【 错误】

10、判断题：
​在单链表P指针所指结点之后插入S结点的操作是：P->next= S ; S-> next = P->next‏
选项：
A: 正确
B: 错误
答案: 【 错误】

11、判断题：
‎若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用顺序表存储最节省时间​
选项：
A: 正确
B: 错误
答案: 【 正确】

12、判断题：
‌对于顺序存储的长度为N的线性表，删除第一个元素和插入最后一个元素的时间复杂度分别对应为O(1)和O(N)。 ‎
选项：
A: 正确
B: 错误
答案: 【 错误】

13、判断题：
‍顺序存储的线性表不支持随机存取.‎
选项：
A: 正确
B: 错误
答案: 【 错误】

14、判断题：
‍在具有N个结点的单链表中，访问结点和增加结点的时间复杂度分别对应为O(1)和O(N)。 ‍
选项：
A: 正确
B: 错误
答案: 【 错误】

15、判断题：
循环链表的结点与单链表的结点结构完全相同，只是结点间的连接方式不同。（ ）‏
选项：
A: 正确
B: 错误
答案: 【 正确】

16、判断题：
‌​在对双向循环链表做删除一个结点操作时，应先将被删除结点的前驱结点和后继结点链接好再执行删除结点操作。（ ）​
选项：
A: 正确
B: 错误
答案: 【 正确】

17、判断题：
‌‍双向循环链表的结点与单链表的结点结构相同，只是结点间的连接方式不同。（ ） ‍
选项：
A: 正确
B: 错误
答案: 【 错误】

第三章单元测试1

1、单选题：
‏若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（  ）种情况。‏‏‏‏
选项：
A: 5，4，3，2，1
B: 2，1，5，4，3  
C: 4，3，1，2，5    
D: 2，3，5，4，1
答案: 【 4，3，1，2，5    】

2、单选题：
若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（  ）。‏‏‏
选项：
A: i 
B: n-i 
C: n-i+1
D: 不确定
答案: 【 n-i+1】

3、单选题：
链式栈结点为：(data,link)，top指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作（  ）。​​​
选项：
A: x=top->data;top=top->link； 
B: top=top->link;x=top->link；
C: x=top;top=top->link；   
D: x=top->link；
答案: 【 x=top->data;top=top->link；  】

4、单选题：
设有一个递归算法如下​        int fact(int n) {  //n大于等于0​             if(n<=0) return 1;​             else return n*fact(n-1);        }​则计算fact(n)需要调用该函数的次数为（  ）。 ​​
选项：
A: n+1  
B: n-1  
C: n
D: n+2
答案: 【 n+1  】

5、单选题：
‍‎栈在 （  ）中有所应用。‎‍‎
选项：
A: 递归调用       
B: 函数调用      
C: 表达式求值 
D: 前三个选项都有
答案: 【 前三个选项都有】

6、单选题：
若一个栈以向量V[1..n]存储，初始栈顶指针top设为n+1，则元素x进栈的正确操作是(    )。‍A．                  ‍B．‍C．;                   ‍D．‍‌‍
选项：
A: top++; V[top]=x; 
B: V[top]=x; top++;
C: top–; V[top]=x
D: V[top]=x; top–;
答案: 【 top–;