数据结构概述测试

1、单选题：
‏计算机算法指的是（）‍
选项：
A: 计算机程序
B: 解决问题的有限运算序列
C: 排序方法
D: 检索方法
答案: 【 解决问题的有限运算序列】

2、单选题：
​下面程序段的算法复杂度是（）‎min=A[0];‎for(i=1;i<n;i++)‎   if( min>A[i]) min=A[i];‎其中 n为正整数。‎
选项：
A: O(n^2)   
B: O(n)
C: O(nlogn)
D: O(n^3) 
答案: 【 O(n)】

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、单选题：
‏若某算法的时间复杂度为O(n^2)，则表明该算法的（ ）。‎
选项：
A: 执行时间与n^2成正比
B: 问题规模是n^2
C: 问题规模与n^2成正比
D: 执行时间等于n^2
答案: 【 执行时间与n^2成正比】

10、单选题：
‎下列函数中时间复杂度是O(n)的是（）。​
选项：
A:
B: T(n)=500n
C:

D: T(n)=2n^2
答案: 【 T(n)=500n】

11、单选题：
‏下面代码段的时间复杂度为（）。‍‏{   int i=1; ‍‏while (i<=n) i=i*2;}‍
选项：
A: O(1)
B: O(n）
C: O(n^2)
D:
答案: 【 】

12、单选题：
‎下面代码段的时间复杂度为（）。​‎{   int i=0, s=0;​‎   while (i<n)  { s=s+a[i];i=i+2;}​‎}​
选项：
A: O(1)
B: O(n)
C:
D:
答案: 【 O(n)】

13、多选题：
​算法的时间复杂度取决于（ ）。 ‍​‍
选项：
A: 问题的规模
B: 待处理数据的初态
C: 实现算法所使用的的语言
D: 数据采用的存储结构
答案: 【 问题的规模;
待处理数据的初态】

14、多选题：
‍数据结构包括数据的（）、数据的（）和数据的（）这三个方面的内容。‍
选项：
A: 逻辑结构
B: 存储结构  
C: 运算
D: 输入输出
答案: 【 逻辑结构;
存储结构  ;
运算】

15、多选题：
‏常见的逻辑结构有集合 ，（），（），（）四种。‍
选项：
A: 顺序表
B: 线性结构
C: 树形结构
D: 图形结构
答案: 【 线性结构;
树形结构;
图形结构】

16、多选题：
‎计算机中算法指的是解决某一问题的有限运算序列，它必须具备0或多个输入、1或多个输出、（ ）、（）、（）。​
选项：
A: 确定性
B: 有穷性
C: 可移植性
D: 可行性
答案: 【 确定性;
有穷性;
可行性】

17、判断题：
‌数据的物理结构是指数据的各数据项之间的逻辑关系。‎
选项：
A: 正确
B: 错误
答案: 【 错误】

18、判断题：
‏数据的逻辑结构说明数据元素之间的顺序关系，它依赖于计算机的储存结构。‌
选项：
A: 正确
B: 错误
答案: 【 错误】

19、判断题：
​某算法的时间复杂度是O(n^3)，表明该算法的执行时间与n^3成正比。‍
选项：
A: 正确
B: 错误
答案: 【 正确】

20、判断题：
​顺序存储的优点是逻辑上相邻的元素，物理上也是相邻的，因此可以实现随机存储。‏
选项：
A: 正确
B: 错误
答案: 【 正确】

21、判断题：
‎数据元素是数据的基本单位‏
选项：
A: 正确
B: 错误
答案: 【 正确】

课堂小测验

1、单选题：
​关于算法复杂度说法正确的是（  ）‏
选项：
A: 算法复杂度指时间复杂度
B:  算法复杂度指空间复杂度
C: 算法复杂度包含时间复杂度、空间复杂度
D: 算法复杂度通常与数据规模无关
答案: 【 算法复杂度包含时间复杂度、空间复杂度】

线性表单元测试上

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

2、单选题：
‍对于长度为n的顺序表（下标范围0..n-1），在第i个位置插入一个元素需要移动（ ）个元素。其中，0≤i≤n。‍
选项：
A: n-i
B: n-i-1
C: n-i+1
D: i
答案: 【 n-i】

3、单选题：
‏若数组A可存放100个元素，每个元素占4个字节，从首地址1000开始按顺序连续存放，那么，元素A[16]的起始地址为（ ）。‎
选项：
A: 1128
B: 1064
C: 1032
D: 1016
答案: 【 1064】

4、单选题：
‏对于顺序存储的长度为n的线性表，删除第i个位置的元素需要移动(       )个元素。其中，0≤i＜n。​
选项：
A: i
B: n-i+1
C: n-i-1
D: n-i
答案: 【 n-i-1】

5、单选题：
‍对于线性表，下列说法正确的是（）。‎
选项：
A: 表中元素必须是有序的
B: 每个元素有且仅有一个直接前驱和一个直接后继
C: 除第一个元素与最后一个元素，其他每个元素有且仅有一个直接前驱和一个直接后继
D: 线性表不允许为空
答案: 【 除第一个元素与最后一个元素，其他每个元素有且仅有一个直接前驱和一个直接后继】

6、单选题：
‏线性表采用顺序存储结构，下列说法不正确的是（   ）。‏
选项：
A: 插入、删除操作不必移动元素
B: 需要事先估计所需存储空间，可能出现顺序表满的情况
C: 内容空间地址必须是连续的
D: 可以进行随机存取
答案: 【 插入、删除操作不必移动元素】

7、单选题：
‍线性表的顺序存储最适合于实现 （  ）运算。‌
选项：
A: 将x插入第i个位置
B: 查找值为x
C: 删除第i个位置元素
D: 取第i个位置元素
答案: 【 取第i个位置元素】

8、单选题：
​在长度为n的顺序表中，查找值为x的数据元素的时间复杂度为（）‎
选项：
A: O(1)
B: O(n)
C: O(n^2)
D:
答案: 【 O(n)】

9、单选题：
​在长度为n的顺序表中，查找第i个位置的数据元素的时间复杂度为（）‍
选项：
A: O(1)
B: O(n)
C: O(n^2)
D:
答案: 【 O(1)】

10、单选题：
‌对顺序存储的长度为n的线性表，假设在任何位置上进行删除操作是等概率的。则删除一个元素时平均要移动表中的（       ）个元素。​
选项：
A: n
B: (n+1)/2
C: n/2
D: (n-1)/2
答案: 【 (n-1)/2】

11、单选题：
​对顺序存储的长度为n的线性表，假设在任何位置上进行插入操作是等概率的。则插入一个元素时平均要移动表中的（       ）个元素。‍
选项：
A: n
B: n/2
C: (n+1)/2
D: (n-1)/2
答案: 【 n/2】

12、单选题：
​在长度为n的顺序表的运算中，算法的时间复杂度是O(1)的操作是（      ）。​
选项：
A: 在第i个位置上插入一个新元素（0≤i≤n）
B: 求第i个位置的元素的直接前驱（1≤i<n）
C: 删除第i个位置上的元素（0≤i<n）
D: 以上都不对
答案: 【 求第i个位置的元素的直接前驱（1≤i<n）】

13、判断题：
‍线性表采用顺序存储结构进行存储，取第i个位置元素的时间与i值的大小有关。‍
选项：
A: 正确
B: 错误
答案: 【 错误】

14、判断题：
​具有100个元素的顺序表（下标从0开始），删除第50个位置的元素，需要移动51个元素。‌
选项：
A: 正确
B: 错误
答案: 【 错误】

15、判断题：
​线性表的特点是除了第一个元素以及最后一个元素外，其他元素有且仅有一个直接前驱和一个直接后继。‍
选项：
A: 正确
B: 错误
答案: 【 正确】

16、判断题：
‎线性表中的所有数据元素的数据类型必须相同。‎
选项：
A: 正确
B: 错误
答案: 【 正确】

17、判断题：
‏顺序表的插入、删除总是伴随着大量数据的移动。​
选项：
A: 正确
B: 错误
答案: 【 正确】

18、判断题：
‌顺序存储方式的优点是存储密度大，数据存储在连续的内存空间中，但是插入、删除运算效率低。‍
选项：
A: 正确
B: 错误
答案: 【 正确】

课堂小测验

1、单选题：
‎在一个不带头结点的单链表中，若要删除 p 所指结点的后继结点q，则执行（  ）。‍
选项：
A: p->next=q->next;free(q);
B: p=p->next; p->next=q->next;free(q);
C: p->next=p->next;free(q);
D: p =p->next->next;free(q);
答案: 【 p->next=q->next;free(q);】

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

3、单选题：
‏若用指针head指向不带头结点的单链表的表头，则该单链表为空的判定条件是（）。​
选项：
A: head->next==head 
B: head!=NULL
C: head->next==NULL 
D: head==NULL 
答案: 【 head==NULL 】

4、单选题：
‎在一个不带头结点的单链表中，若 p 所指结点不是最后结点，在 p 之后插入 s 所指结点，则执行（）。​
选项：
A: s->next=p;p->next=s; 
B: s->next=p->next;p=s; 
C: s->next=p->next;p->next=s; 
D: p->next=s;s->next=p->next; 
答案: 【 s->next=p->next;p->next=s; 】

线性表单元测试下

1、单选题：
‎关于线性表的链式存储，以下说法正确的是（    ）‌
选项：
A: 可方便地进行随机存取
B: 存储密度大
C: 插入、删除运算方便
D: 以上都不对
答案: 【 插入、删除运算方便】

2、单选题：
‌下面关于线性表的叙述中，错误的是哪一个？（    ）‍
选项：
A: 线性表采用顺序存储，便于进行插入和删除操作
B: 线性表采用顺序存储，必须占用一片连续的存储空间
C: 线性表采用链接存储，便于插入和删除操作
D: 线性表采用链接存储，存储空间连不连续都可以
答案: 【 线性表采用顺序存储，便于进行插入和删除操作】

3、单选题：
‏如果线性表最常用的操作是取第i个结点及其前驱，则采用_____存储方式最节省时间。‎
选项：
A: 单向链表
B: 双向链表
C: 顺序表
D: 单向循环链表
答案: 【 顺序表】

4、单选题：
​对于使用带头结点的单链表，若头指针为head，判定该表为空的条件是（    ）。‏
选项：
A: head!=NULL
B: head->next==head
C: head==NULL 
D: head->next==NULL 
答案: 【 head->next==NULL 】

5、单选题：
​对于使用不带头结点的单链表，若头指针为head，判定该表为空的条件是（    ）‍
选项：
A: head==NULL
B: head->next==NULL
C: head->next=head
D: head!=NULL
答案: 【 head==NULL】

6、单选题：
‎已知指针p指向在一个单链表中的某个结点，若在该结点之后插入指针s指向的结点，则需执行（     ）。‎
选项：
A: s->next=p->next;p->next=s;
B: p->next=s;s->next=p;
C: s->next=p->next;s=p;
D: s->next=p->next;s=p->next;
答案: 【 s->next=p->next;p->next=s;】

7、单选题：
​已知指针p指向单链表head中的某个结点，若删除其后继结点，则需执行（）。‌
选项：
A: r=p; p->next=r->next; free(r);
B: r=p->next; p=r->next; free(r);
C: r=p->next; p->next=r->next; free(r);
D: r=p->next; r->next=p->next; free(r);
答案: 【 r=p->next; p->next=r->next; free(r);】

8、单选题：
‎对于一个具有n个结点的单链表，在给定值为x的结点后插入一个新结点的时间复杂度为（）‏
选项：
A: O(1)
B: O(n)
C: O(n^2)
D:
答案: 【 O(n)】

9、单选题：
‍在单链表head中，指针p所指结点是线性表中最后一个元素的条件是（  ）​
选项：
A: p==NULL
B: p->next==NULL
C: p!=NULL
D: p->next!=NULL
答案: 【 p->next==NULL】

10、单选题：