1.1 什么是数据结构

1、多选题：
​数据结构的研究对象主要包括：‌
选项：
A: 数据集合中元素之间的关系
B: 数据集合的存储实现方式
C: 对数据集合进行的操作
D: 操作算法优劣的评价
答案: 【 数据集合中元素之间的关系;
数据集合的存储实现方式;
对数据集合进行的操作;
操作算法优劣的评价】

2、判断题：
​数据结构主要研究非数值计算的问题。‌
选项：
A: 正确
B: 错误
答案: 【 正确】

3、判断题：
‍数据结构的研究与计算机硬件无关。‍
选项：
A: 正确
B: 错误
答案: 【 错误】

1.2 数据结构的基本概念（一）——逻辑结构

1、单选题：
‌数据的逻辑结构是指 （        ）关系的整体。‏
选项：
A: 数据存储结构之间
B: 数据类型之间
C: 数据元素之间逻辑
D: 数据项之间逻辑
答案: 【 数据元素之间逻辑】

2、多选题：
​以下说法不正确的是（        ）。‍
选项：
A: 数据可由若干个数据元素构成。
B: 数据项是不可分割的最小可标识单位。
C: 数据项可由若干个数据元素构成。
D: 数据元素是数据的最小单位。
答案: 【 数据项可由若干个数据元素构成。;
数据元素是数据的最小单位。】

3、多选题：
‎数据的逻辑结构可以分为（        ）。‍
选项：
A: 动态结构和静态结构
B: 线性结构和非线性结构
C: 内部结构和外部结构
D: 集合、线性结构、树形结构、图状结构
答案: 【 线性结构和非线性结构;
集合、线性结构、树形结构、图状结构】

1.2 数据结构的基本概念（二）——物理结构

1、单选题：
‍下面关于数据的逻辑结构与存储结构说法正确的是（        ）。‎
选项：
A: 逻辑结构要体现出存储结构。
B: 存储结构要体现出逻辑结构。
C: 两者是一一对应的。
D: 二者毫无关系。
答案: 【 存储结构要体现出逻辑结构。】

2、单选题：
‍在数据的存储中，一个结点通常存储一个（        ）。​
选项：
A: 数据结构
B: 数据类型
C: 数据元素
D: 数据项
答案: 【 数据元素】

3、单选题：
‍在决定选取任何类型的存储结构时，一般不多考虑（        ）。‌
选项：
A: 对数据有哪些运算
B: 结点个数的多少
C: 各结点的具体取何值
D: 所用编程语言实现这种结构是否方便
答案: 【 各结点的具体取何值】

1.3 抽象数据类型

1、多选题：
​下列关于抽象数据类型（ADT）定义的说法，正确的有（        ）。‍
选项：
A: ADT的定义只取决于它的一组逻辑特性。
B: ADT的定义与计算机内部如何表示和实现无关。
C: 不论ADT的内部结构如何变化，只要它的数学特性不变，都不影响它的外部使用。
D: ADT定义了一个完整的（狭义）数据结构。
答案: 【 ADT的定义只取决于它的一组逻辑特性。;
ADT的定义与计算机内部如何表示和实现无关。;
不论ADT的内部结构如何变化，只要它的数学特性不变，都不影响它的外部使用。;
ADT定义了一个完整的（狭义）数据结构。】

2、多选题：
‏调用下列test( )函数，能够在屏幕上输出“hello world”的是（        ）。‎
选项：
A: void GetMemory(char *p){    p = (char *)malloc(100);}void Test(void){    char *str = NULL;    GetMemory(str);    strcpy(str, "hello world");    printf(str);}
B: char *GetMemory(void){    char p[ ] = "hello world";    return p;}void Test(void){    char *str = NULL;    str = GetMemory();    printf(str);}
C: void Test(void){    char *str = (char *) malloc(100);    strcpy(str, "No!");    free(str);    if (str != NULL)    {        strcpy(str, "hello world");        printf(str);    }}
D: void GetMemory(char **p, int num){    *p = (char *)malloc(num);}void Test(void){    char *str = NULL;    GetMemory(&str, 100);    strcpy(str, "hello world");    printf(str);}
答案: 【 void Test(void){    char *str = (char *) malloc(100);    strcpy(str, "No!");    free(str);    if (str != NULL)    {        strcpy(str, "hello world");        printf(str);    }};
void GetMemory(char **p, int num){    *p = (char *)malloc(num);}void Test(void){    char *str = NULL;    GetMemory(&str, 100);    strcpy(str, "hello world");    printf(str);}】

1.4 什么是算法

1、单选题：
‍计算机中算法是解决某一问题的有限运算序列，必须具备输入、输出、（        ）等5个特性。‍
选项：
A: 确定性、有穷性和健壮性
B: 可读性、正确性和健壮性
C: 可行性、正确性和可读性
D: 可行性、确定性和有穷性
答案: 【 可行性、确定性和有穷性】

2、单选题：
‏数据的运算（即操作） （        ）。‎
选项：
A: 在不同计算机上的实现方法都是相同的。
B: 必须用程序设计语言来描述
C: 与采用何种存储结构有关
D: 有算术运算和关系运算两大类
答案: 【 与采用何种存储结构有关】

3、多选题：
‎算法的设计目标有（        ）等等。​
选项：
A: 可行性
B: 健壮性
C: 有穷性
D: 正确性
答案: 【 健壮性;
正确性】

1.5 算法的分析与度量

1、单选题：
​算法分析的主要任务之一是分析（        ）。‍
选项：
A: 算法中是否存在语法错误
B: 算法的执行时间与问题规模之间的关系
C: 算法中输入和输出之间的关系
D: 算法是否具有较好的可读性
答案: 【 算法的执行时间与问题规模之间的关系】

2、单选题：
‍给出算法的时间复杂度是属于一种（        ）。‏
选项：
A: 事前统计的方法
B: 事前分析估算的方法
C: 事后统计的方法
D: 事后分析估算的方法
答案: 【 事前分析估算的方法】

3、单选题：
‎下述函数中时间复杂度最小的是（        ） 。‎
选项：
A:
B:
C:
D:
答案: 【 】

4、单选题：
‎下面程序段的时间复杂度是（        ）。‌‎i=1;‌‎while (i<=n)‌‎    i=i*5;‌
选项：
A:
B: n
C:
D:
答案: 【 】

第一周 绪论 单元测验

1、单选题：

‎某算法的时间复杂度为。若该算法在规模为n的数据集上，运行时间为10秒；如果数据规模扩大为2n，该算法大约需要运行（        ）。

‏选项：
A: 10秒
B: 100秒
C: 6-7分钟
D: 以上都不对
答案: 【 以上都不对】

2、单选题：
‍以下函数中时间复杂度最小的是（        ）。‍
选项：
A:
B:
C:
D:
E:
F:
G:
答案: 【 ;
】

3、单选题：
‍下列程序段的时间复杂度是（        ）。​‍count=0;​‍for (k=1;k<=n;k*=2)​‍    for (j=1;j<=n;j+1)​‍        count++;​
选项：
A:
B:
C:
D:
答案: 【 】

4、单选题：
下列程序段的时间复杂度是（        ）。‏int k=0,j=0;‏while (j<=n) {
    k++;‏    j+=k;
}‏
选项：
A:

B:
C:
D:
E:
答案: 【 】

5、单选题：
‌下面的数据结构是（        ）。‌‌DS=(D,R)，其中D={a,b,c,d,e}，R={r}，‌‌r={<a,b>,<a,e>,<b,c>,<d,e>}。‌‌注：“<>"表示有序对。‌‌‌
选项：
A: 集合
B: 线性结构
C: 树形结构
D: 图状结构
E: 顺序存储结构
F: 链式存储结构
答案: 【 图状结构】

6、多选题：
‍下列关于算法的叙述正确的是（        ）。‎
选项：
A: 算法的有穷性是指算法必须能在执行有限个步骤之后终止。
B: 算法的时间复杂度与空间复杂度紧密相关。
C: 算法的效率只与问题规模有关，而与数据的存储结构无关。
D: 用不同算法求解同一问题的时间复杂度不同。
E: 算法的优劣与算法描述语言无关，与所用计算机也无关。
F: 算法原地工作的含义是指该算法不需要任何额外的辅助空间。
G: 对于相同规模的n，时间复杂度O(n)的算法运行时间总是小于时间复杂度的算法的运行时间。
H: 所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界。
答案: 【 算法的有穷性是指算法必须能在执行有限个步骤之后终止。;
算法的优劣与算法描述语言无关，与所用计算机也无关。;
所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界。】

7、多选题：
‏下列叙述正确的是（        ）。​‏​
选项：
A: 数据元素是数据项中不可分割的最小可标识单位。
B: 从逻辑上可以把数据结构分为顺序结构、链式结构等类别。
C: 研究数据结构就是研究数据的逻辑结构和存储结构。
D: 数据类型可看成是程序设计语言中已实现的数据结构。
E: 数据元素之间的关联关系在数据的逻辑结构中体现。
F: 数据对象是由有限个类型相同的数据元素构成的。
G: 逻辑结构不相同的数据，必须采用不同类型的存储方法。
H: 如果数据元素值发生改变，则数据的逻辑结构也随之改变。
I: 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
答案: 【 数据类型可看成是程序设计语言中已实现的数据结构。;
数据元素之间的关联关系在数据的逻辑结构中体现。;
数据对象是由有限个类型相同的数据元素构成的。;
数据结构是相互之间存在一种或多种特定关系的数据元素的集合。】

2.1 线性表的定义（一）——概念和ADT

1、单选题：
‍下列有关线性表的叙述中，正确的是（      ）。‎
选项：
A: 线性表中元素之间的关系是线性关系。
B: 线性表中至少有一个元素。
C: 线性表中的任一元素有且仅有一个直接前趋。
D: 线性表中的任一元素有且仅有一个直接后继。
答案: 【 线性表中元素之间的关系是线性关系。】

2、判断题：
‏插入和删除操作是线性表的基本操作，这两种操作在数组中也经常使用。‏
选项：
A: 正确
B: 错误
答案: 【 错误】

2.1 线性表的定义（二）——合并与归并

1、单选题：
​将两个长度均为n的有序线性表归并成一个有序线性表，最少需要（    ）次比较。‏
选项：
A: n-1
B: n
C: 2n-1
D: 2n
答案: 【 n】

2、单选题：
‌假设两个集合分别存储在两个线性表中，长度分别为m和n，将它们合并到一个新的线性表中，则该线性表的最小长度是（    ）。​
选项：
A: m+n
B: min(m,n)
C: max(m,n)
D: 无法确定
答案: 【 max(m,n)】

2.2 顺序表

1、单选题：
​顺序表具有随机存取特性，指的是（    ）。‌
选项：
A: 查找值为 x 的元素与顺序表中元素个数 n 无关
B: 查找值为 x 的元素与顺序表中元素个数 n 有关
C: 查找序号为 i 的元素与顺序表中元素个数 n 无关
D: 查找序号为 i 的元素与顺序表中元素个数 n 有关
答案: 【 查找序号为 i 的元素与顺序表中元素个数 n 无关】

2、单选题：
‎顺序表中，删除一个元素所需要的时间（    ）。‌
选项：
A: 与删除元素的位置及顺序表的长度都有关
B: 只与删除元素的位置有关
C: 只与顺序表的长度有关
D: 与删除元素的位置及顺序表的长度都无关
答案: 【 与删除元素的位置及顺序表的长度都有关】

3、单选题：
‎假设某顺序表中第一个元素的存储地址是1010H，每个元素占8个存储单元，则第5个元素的存储地址是（    ）。‍
选项：
A: 1042H
B: 1050H
C: 1030H
D: 1038H
答案: 【 1030H】

4、判断题：
‍顺序表中元素的逻辑顺序与存储顺序总是一致的。‏
选项：
A: 正确
B: 错误
答案: 【 正确】

2.3 线性链表（一）——单链表

1、单选题：
‌已知两个长度分别为m和n的升序链表，若将它们合并为一个长度为m+n的降序链表，则最坏情况下的时间复杂度是（    ）。‎
选项：
A: O(n)
B: O(m*n)
C: O(min(m,n))
D: O(max(m,n))
答案: 【 O(max(m,n))】

2、单选题：
‏下列关于单链表的说法，错误的是（    ）。‍
选项：
A: 数据域用于存储线性表的一个数据元素。
B: 指针域用于存储一个指向本结点对应元素的直接后继所在结点的指针。
C: 单链表中各结点的地址不可以连续。
D: 单链表无法随机存取。
答案: 【 单链表中各结点的地址不可以连续。】

3、多选题：
‍单链表具备的特点有（    ）。 ‌
选项：
A: 插入和删除不需要移动元素。
B: 不必事先估计整个线性表所需的存储空间。
C: 所需存储空间与线性表长度成正比。
D: 只能顺序访问。
答案: 【 插入和删除不需要移动元素。;
不必事先估计整个线性表所需的存储空间。;
所需存储空间与线性表长度成正比。;
只能顺序访问。】

4、多选题：
‍在一个单链表中，已知 q 是 p 的前趋结点，若在 q 和 p 之间插入结点 s ，则应当执行语句序列（    ）。‌
选项：
A: s -> next = p -> next;     p -> next = s;
B: s -> next = q -> next;     p -> next = s;
C: s -> next = q -> next;     q -> next = s;
D: q -> next = s;     s -> next = p;
答案: 【 s -> next = q -> next;     q -> next = s;;
q -> next = s;     s -> next = p;】

2.3 线性链表（二）——静态链表

1、单选题：
‎静态链表中的指针域存放的是（    ）。‎
选项：
A: 下一个元素的地址
B: 内存地址
C: 下一个元素在数组中的位置
D: 以上都不对
答案: 【 下一个元素在数组中的位置】

2、判断题：
‌静态链表不需要一开始就分配所有的存储空间，可以等到要插入数据元素时再申请‌
选项：
A: 正确
B: 错误
答案: 【 错误】

2.4 循环链表和双向链表

1、单选题：
‍对于双向链表，在两个结点之间插入一个新结点需修改的指针共（    ）个。‌
选项：
A: 1
B: 2
C: 3
D: 4
答案: 【 4】

2、单选题：
‍非空的循环单链表 head 的尾结点 p 满足 （    ）。‍
选项：
A: p -> next == head
B: p -> next == NULL
C: p == NULL
D: p == head
答案: 【 p -> next == head】

3、单选题：
​对于长度为 n（n≥1）的双向链表 L ，在 p 所指结点之前插入一个新结点，其时间复杂度为（    ）。​
选项：
A: O(1)
B: O(n)
C: O(nlogn)
D:
答案: 【 O(1)】

4、多选题：
‏对于一个头指针为 head 的带头结点的双向循环链表，可以作为判定该表为空表的条件是（    ）。‌
选项：
A: head == NULL
B: head == NULL
C: head -> prior == head
D: head -> next == head
答案: 【 head -> prior == head;
head -> next == head】

2.5 顺序表与线性链表的比较（一）——顺序表与链表

1、单选题：
‏静态链表与顺序表相比，优点在于（    ）。‌
选项：
A: 所有操作的算法实现更简单
B: 便于随机存取
C: 便于插入和删除
D: 便于利用零散的存储空间
答案: 【 便于插入和删除】

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

3、单选题：
‏设线性表中有 2n 个元素，以下操作中，（    ）在单链表上实现要比在顺序表上实现效率更高。​
选项：
A: 删除指定位置元素的下一个元素
B: 在最后一个元素的后面插入一个新元素
C: 顺序输出前 k 个元素
D: 交换第 i 个元素和第 n-i+1 个元素的值 （i=1, 2, …, n）
答案: 【 删除指定位置元素的下一个元素】

2.5 顺序表与线性链表的比较（二）——各种链表的对比

1、单选题：
‍与非循环单链表相比，循环单链表的主要优点是（    ）。‍
选项：
A: 不再需要头指针
B: 已知某个节点的位置后，能够容易找到它的前驱节点
C: 在进行插入、删除操作时，能更好地保证链表不断开
D: 从表中任意节点出发都能扫描到整个链表
答案: 【 从表中任意节点出发都能扫描到整个链表】

2、单选题：
‌若某线性表最常用的操作是在表尾结点插入新结点和删除表尾结点，则采用（        ）存储方式最节省时间。‎
选项：
A: 带头结点的双向循环链表
B: 不带头结点的单链表
C: 仅有尾指针的循环单链表
D: 仅有头指针的循环单链表
答案: 【 带头结点的双向循环链表】

3、单选题：
‌若某线性表最常用的操作是在表尾结点之后插入新结点和删除表头结点，则采用（        ）存储方式最节省时间。‏
选项：
A: 仅有头指针的循环单链表
B: 仅有尾指针的循环单链表
C: 带头结点的单链表
D: 带头结点的双向循环链表
答案: 【 仅有尾指针的循环单链表】

4、单选题：
‎下列关于链表的描述，错误的是（    ）。‌
选项：
A: 在循环单链表中，从表中任一结点出发都可以通过前后移动操作来遍历整个循环链表。
B: 在双向链表中，可以从任一结点开始沿同一方向查找到任何其他结点。
C: 单链表不具有随机存取特性，而双向链表具有随机存取特性。
D: 为了方便插入和删除，可以使用双向链表存放数据。
答案: 【 为了方便插入和删除，可以使用双向链表存放数据。】

第二周 线性表 单元测验

1、单选题：
‏顺序表中，结点的插入和删除操作的时间复杂度分别为（        ）。‌
选项：
A: O(1)、O(1)
B: O(n)、O(1)
C: O(1)、O(n)
D: O(n)、O(n)
答案: 【 O(n)、O(n)】

2、单选题：
‎在表长为n的顺序表中，下列操作中需要移动元素最多的是（        ）。​
选项：
A: 删除表中的第一个元素。
B: 删除表中的最后一个元素。
C: 在第一个元素之前插入一个元素。
D: 在最后一个元素之前插入一个元素。
E: 在最后一个元素之后插入一个元素。
F: 在最后一个元素之后插入一个元素。
答案: 【 在第一个元素之前插入一个元素。】

3、单选题：
‌带头结点的双向链表 L 为空表时应满足（        ）。‏
选项：
A: L == NULL
B: L -> prior == L -> next
C: L -> prior == NULL
D: L -> next == NULL
答案: 【 L -> next == NULL】

4、单选题：
‍在只设有表尾指针 rear 但没有头结点的非空循环单链表中，删除表尾结点的时间复杂度为（        ）。‌
选项：
A: O(1)
B: O(n)
C: O(nlogn)
D:
答案: 【 O(n)】

5、单选题：
‏当元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用（        ）存储结构。‏
选项：
A: 顺序表
B: 静态单链表
C: 双向循环链表
D: 单链表
E: 循环单链表
F: 双向链表
G: 静态循环单链表
答案: 【 顺序表】

6、单选题：
‌已知指针 p 指向某双向链表的一个中间结点，下列语句序列实现的操作是（        ）。​‌q = p -> prior; ​‌p -> prior = q -> prior;​‌q -> prior -> next = p;​‌free(q);​
选项：
A: 删除 p 结点
B: 删除 p 结点的直接前驱结点
C: 删除 p 结点的直接后继结点
D: 删除 p 结点及其所有后继结点
答案: 【 删除 p 结点的直接前驱结点】

7、多选题：
‏下面关于静态链表的表述中，错误的有（        ）。‍
选项：
A: 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第 i 个元素的时间与 i 无关。
B: 静态链表在创建时确定了能容纳的元素个数的最大值。
C: 静态链表与动态链表在元素的插入、删除操作上类似，不需做元素的移动。
D: 静态链表需要分配较大的连续空间。
E: 静态链表中元素的指针域存储的是下一个数据元素的内存地址。
F: 静态链表无法实现随机存取。
G: 所谓静态链表就是不允许插入和删除元素的链表。
答案: 【 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第 i 个元素的时间与 i 无关。;
静态链表