##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次。

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