##C语言《公共基础知识》数据结构与算法知识点和错题（二级题）

###前63题

一、算法

算法的有穷性是指：算法程序的运行时间是有限的（算法必须能在执行有限个步骤之后终止）

算法的时间复杂度是指：1.算法在执行过程中所需要的基本运算次数（计算工作量）

2.时间复杂度与所用的计算工具无关（如硬件、计算机速度），因为这些工具只影响实际运行时间，而不改变算法本身的运算次数增长率。

3.与采用的算法描述语言无关，时间复杂度是算法本身的属性，描述语言（如C++、Python或伪代码）只影响代码的实现细节和实际执行效率，但不改变算法的基本运算次数和其增长率。时间复杂度作为理论度量，是语言无关的。

二、数据结构

1. 数据结构的分类主要基于元素之间的关系：

①线性结构：元素之间存在一对一的关系，如数组、单向链表、双向链表、循环链表、栈、队列等。线性结构通常只有一个起始点（根结点或头结点）。

②非线性结构：元素之间存在一对多或多对多的关系，如树、图等。

T16

A. 有一个以上根结点的数据结构不一定是非线性结构

此叙述错误。如果一个数据结构有多个根结点（如森林（多个树）或多个独立的链表），则元素之间不是单一的线性序列，而是存在多个独立分支或连通分量，因此一定是非线性结构。线性结构（如链表或数组）只能有一个起始点（根结点或头结点），不可能有多个根结点。（T28 具有两个根结点的数据结构一定是非线性结构 正确）

B. 只有一个根结点的数据结构不一定是线性结构

此叙述正确。

如果只有一个根结点，且元素呈线性序列（如单向链表、双向链表、循环链表），则它是线性结构。

如果只有一个根结点，但元素存在分支（如树或二叉树），则它是非线性结构。

例如：

链表（线性结构）只有一个头结点（根结点）。

二叉树（非线性结构）只有一个根结点，但结点之间有父子关系，形成分支。

C. 循环链表是非线性结构

此叙述错误。循环链表是线性结构的一种，元素之间仍然是一对一的关系，只是最后一个结点指向头结点形成环。线性结构包括循环链表、双向链表等。

‌D. 双向链表是非线性结构

此叙述错误。双向链表是线性结构，元素之间通过前驱和后继指针形成一对一的关系，没有分支或多对多关系。

ps：根结点：通常指数据结构的起始入口点（如链表的头结点、树的根节点）。线性结构一般只有一个根结点，而非线性结构可能有多个根结点（如森林）或没有特定根结点（如无向图，没有特定的根节点，所有结点平等，但元素键存在多对多的关系）  

、、没有根结点或没有叶子结点的数据结构一定是非线性结构 正确T29

、、只有一个根结点，且只有一个叶子结点的数据结构一定是线性结构吗？

反例证明：

   A

  / \

 B   C

  \ /

   D

存在一对多的关系，显然是非线性 

2. 数据结构中，主要研究的是数据的逻辑结构、数据的运算和 （ 数据的存储结构）。T22  

、、、与所使用的计算机无关的是数据的（ 逻辑）结构。T21

、、、逻辑结构和存储结构的关系：逻辑结构是上层抽象，定义了数据元素间的关联规则，存储结构是底层实现，通过物理机制（如指针或连续地址）实现这些规则

、、、同一个逻辑结构可以采用多种存储结构来实现，不同存储结构会影响操作效率

3. 顺序存储结构的存储空间一定是连续的，链式存储结构的存储空间不一定是连续的。T17

4.线性表的定义（略）和存储结构特征：

分为 顺序存储：为连续存储空间、支持随机访问、增删效率低、预分配固定控件、存储密度高

ps：在线性表的顺序存储结构中，其存储空间连续，各个元素所占的 字节数（相同，元素的存储顺序与逻辑顺序一致  原因：在线性表的顺序存储结构中，存储空间连续，且元素类型必须相同（如同质数据），因此各个元素所占的字节数必须是相等的

链式存储： 动态内存分配、增删效率高、访问效率低（不支持随机访问，需从头指针开始遍历链表定位元素）、额外存储开销（每个元素需要附带指针域存储地址信息）

5.二元关系图的考察

设数据集合为D={1,3,5,7,9}，D上的关系为R，下列数据结构B= (D,R)中为非线性结构的是（  ）。

A. R={(5,1),(7,9),(1,7),(9,3)}

B. R={(9,7),(1,3),(7,1),(3,5)}

C. R={(1,9),(9,7),(7,5),(5,3)}

D. R={(1,3),(3,5),(5,9),(7,3)}

正确答案：D

三、栈和队列

栈：先进后出

在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化  正确

解释：栈底指针通常固定不变（指向栈的起始位置），元素的变化主要由栈顶指针的移动引起（如压栈和弹栈操作）。栈底指针变化的情况（如栈内存重新分配）非常罕见，且元素变化的核心驱动因素是栈顶指针，而非栈底指针。

队列：先进先出

循环队列是队列的一种顺序存储结构T35

在带链队列中，队头指针和队尾指针都是在动态变化的

在带链队列中，队头指针和队尾指针可以指向同一个位置

栈和队列的存储结构都支持顺序存储和链式存储

栈的顺序存储

T48

设栈的顺序存储空间为S（1：m），初始状态为top=m+1。现经过 一系列入栈与退栈运算后，top=20，则当前栈中的元素个数为 （  ）。

A. 30

B. 20

C. m-19

D. m-20

正确答案：C

解析：栈的顺序存储空间为 

S(1:m)初始状态为 top=m+1

这表示栈采用向下增长的方式（即栈顶从高地址向低地址移动），且初始时栈为空。

入栈操作：

top 减 1，元素存入 S(top)。

退栈操作：元素从 S(top) 取出，top 加 1。

栈中元素个数等于净入栈次数（入栈次数减去退栈次数）。初始 top=m+1

top=m+1，经过一系列操作后，

top=20

元素个数 N

N 的计算公式为：

N=(初始 top)−(当前 top)

N=(初始 top)−(当前 top)

代入已知值：

N=(m+1)−20=m−19

N=(m+1)−20=m−19

因此，当前栈中的元素个数为 m−19

循环对列：

例题：

！循环队列的存储空间为Q(0:59)，初始状态为空。经过一系列正常的入队与退队操作后，front=25，rear=24。循环队列中的元素个数为（59） 

ps:循环队列求元素个数 常用到公式(此处的rear和front是经过入队退队运算后的）

（rear-front）=resul 若差为负数，则（rear-front)+（对列总容量）=result . 不过要注意存储空间Q（0：59），如果是从0开始，则要加上“1  ”，如此处储存总容量为60

！若rear==front 表示队列此时为空，或者已满=总容量

T49设循环队列的存储空间为Q（1：35），初始状态为 front=rear=35。现经过一系列入队与退队运算后，front=15，rear=15， 则循环队列的元素个数为（  ）。

A. 15

B. 16

C. 20

D. 0或35

正确答案：D

解析：

rear = front 空或满 T50 同上

T51设循环队列为Q（1：m），其初始状态为front=rear=m。经过一系 列入队与退队运算后，front=15，rear=20。现要在该循环队列中寻找 最大值的元素，最坏情况下需要比较的次数为（ 4 ）。

解析：首先计算该循环队列中的元素个数：rear-front=20-15=5 。 故最坏情况下比较四次。

T52设循环队列为Q（1：m），其初始状态为front=rear=m。经过一系 列入队与退队运算后，front=20，rear=15，要在该循环队列中寻找最 小值的元素，最坏情况下需要比较的次数为（m-6  ）

同上逻辑，计算元素个数：rear-front=-5  ， 结果为负数，加上容量，结果为m-5个，所以最坏比较m-6次。

线性链表（单链表）：在定义的链表中,若只含有一个指针域来存放下一个元素地址,称这样的链表为单链表或线性链表。 在链式存储方式中,要求每个结点由两部分组成:一部分用于存放数据元素值,称为数据域;另一部分用于存放指针,称为指针域。其中指针用于指向该结点的前一个或后一个结点(即前件或后件)。、、进行插入与删除时，不需要移动表中的元素

###后64-126题

一、链表

数据元素间存在的关系可以是线性也可以是非线性的 

链表结点中具有两个指针域的数据结构可以是线性结构，也可以是非线性结构（树结构）

链表不支持随机访问，故不能对分查找，只能顺序遍历T101

线性表的链式存储结构：

可能有双向链表、单链表等

单链表中每个结点只有一个指向后件的指针；而双向链表的结点有指向前件和后件的两个指针

二叉链表：是一种用于存储二叉树的链式存储结构

循环链表是在单链表的基础上，让最后一个结点的指针指向头节点，形成的一个环的链表结构；而循环队列则是队列的一种顺序存储结构，它是利用数组首尾相连的特性来实现循环存储数据的，二者是把不同数据结构的不同存储方式，不能混为一谈。

带链的栈：本质是单链表的形式，它有栈顶指针来指向栈顶元素，栈底指针指向栈底元素

 双重链表（双向链表）的每个结点有指向前件和后件的两个指针，因此和“带链的栈”不相同

多重链表：

结点中具有多个指针域的链表

二、二叉树

第h层j数最多： 2的（h-1）次方

深度为k 总结点数最多为：2的k次方 - 1

具有x个结点的二叉树有几种形态： 1/（x+1） *   [（2x）！/x！*（2x-x）！]

即 

                                     x

        1/（x+1）* C

                                    2x

T83深度为7的完全二叉树中共有125个结点，则该完全二叉树中的叶 子结点数为（ 63 ）。

解析：

1. 完全二叉树的性质回顾：

- 对于深度为h的完全二叉树，其前h - 1层是满二叉树。满二叉树第i层的结点数为2^{i - 1}个，前h-1层满二叉树的结点总数为\sum_{i = 1}^{h - 1}2^{i - 1}=2^{h - 1}-1。

- 深度为7的完全二叉树，前6层是满二叉树，前6层的结点总数为2^{6}-1 = 64 - 1=63个。

2. 计算第7层的结点数：

- 已知该完全二叉树共有125个结点，那么第7层的结点数为125-(2^{6}-1)=125 - 63 = 62个。

- 因为完全二叉树的特点，第7层的62个结点是从左到右依次排列的。这62个结点的父结点是第6层的部分结点。

- 第6层结点数为2^{6 - 1}=2^{5}=32个。第7层有62个结点，说明第6层有\left\lceil\frac{62}{2}\right\rceil = 31个结点有两个子结点（\left\lceil x\right\rceil表示向上取整），那么第6层剩余32 - 31 = 1个结点只有一个子结点（在完全二叉树中这种情况存在）。

3. 计算叶子结点数：

- 叶子结点数就是第7层的结点数加上第6层中没有子结点的结点数。第7层有62个叶子结点，第6层有1个叶子结点（即只有一个子结点的那个结点本身也是叶子结点，因为它的另一个子结点不存在），所以叶子结点总数为62 + 1=63个。

故本题答案为B。

三、查找排序：

在长度为n的有序线性表中进行二分查找，最坏情况下需要比较 的次数是（O（log2n）  ）

为了对有序表进行二分查找，则要求有序表（ 只能顺序存储 ）

下列排序方法中，最坏情况下时间复杂度最小的是（  ）。

A. 冒泡排序 O（n方）

B. 快速排序O（n方）

C. 堆排序 O（n*以2为底log n）

D. 直接插入排序 O（n方）

正确答案：C

ABD三种排序以及简单插入排序方法在最坏情况下，比较次数都是n（n-1）/2

希尔排序在最坏情况下的比较次数很难用数学公式准确表示，它和所取的增量序列有关，在最坏情况下，其比较次数远远大于n ，平均时间复杂度约为O（n的1.3次方）

希尔排序的时间复杂度比直接插入排序的时间复杂度要小

明确堆的定义：

- 堆分为大顶堆和小顶堆。大顶堆要求每个节点的值都大于或等于其左右子节点的值，即根节点是堆中的最大值；小顶堆要求每个节点的值都小于或等于其左右子节点的值，即根节点是堆中的最小值。对于一个长度为n的完全二叉树（数组存储时，若节点下标从1开始编号，节点i的左子节点下标为2i，右子节点下标为2i + 1；若从0开始编号，节点i的左子节点下标为2i + 1，右子节点下标为2i + 2），我们可以根据数组元素的位置关系来判断是否满足堆的性质。