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

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: 错误
答案: 【 错误