C语言二级公共基础知识

一、算法

1、算法的基本概念

算法 是指解决方案准确而完备【不仅仅是理论】的描述

算法的基本特点：可行性、确定性、有穷性、拥有足够的情报。

算法的基本要素：算法对数据的基本运算和操作，算法的控制结构（顺序结构、选择结构、循环结构）。

2、算法的复杂度

算法的时间复杂度，是执行算法所需要的计算工作量【并不是时间】。

算法的空间复杂度，是执行这个算法所需要的内存空间。

3、本节练习

1、算法的空间复杂度是指

A）算法在执行过程中所需要的计算机存储空间

B）算法在执行过程中所需要的临时工作单元数

C）算法所处理的数据量

D）算法程序中语句或指令条数

A

2、算法的时间复杂度是指

A）设计该算法所需的工作量

B）算法中指令的条数

C）执行该算法所需要的时间

D）执行该算法时所需要的基本运算次数

D

3、算法的有穷性是指

A）算法是只能被有限的用户使用

B）算法程序的运行时间是有限的

C）算法程序的运行时间是有限的

D）算法程序所处理的数据量是有限的

B

4、下列叙述中正确的是

A）对同一批数据不同的处理，如果数据存储的结构相同，不同算法的时间复杂度肯定相同

B）对同一批数据作同一种处理，如果数据存储结构不同，不同算法的时间复杂度肯定相同

C）解决同一个问题的不同算法的时间复杂度一般是不同的

D）解决同一个问题的不同算法的时间复杂度必定的相同的

C

5、下列叙述中正确的是

A）一个算法的时间复杂度大，则其空间复杂度必定小

B）一个算法的空间复杂度大，则其时间复杂度小

C）算法的时间复杂度与空间复杂度都没有直接的关系

D）一个算法的空间复杂度大，则其时间复杂度必定大

C

二、数据结构的基本概念

1、什么是数据结构

事务的存在有两种形式：实体、关系。

数据结构研究和讨论问题：

（1）数据集合各种数据质之间所固有的逻辑关系，即数据的逻辑结构；

（2）在对数据处理时，各数据在计算机的存储结构，即数据的存储结构

（3）对各种数据结构进行的运算。

数据结构是指相互有关联数据元素集合的表示。更通俗的讲数据结构是带有结构的数据元素的集合，以上表述可知一个数据结构应该包含以下二个方面内容：

（1）表示数据元素信息即数据元素的集合，通常记为D；

（2）表示各数据之间的前后件关系通常记为R。即一个数据结构可以表示为B=(D,R)。

列如B=（D,R）

D={春，夏，秋，冬}

R={（春，夏），（夏，秋），（秋，冬）}

数据处理是指对数据集合中的各元素以各种方式进行运算，包括插入，删除，查找，更改，等运算，也可以包括对数据元素进行分析。

2、数据结构的图形表示

一个数据结构处理用二元关系表示外，还可以直观的用图形表示。在数据结构的图形表示中，对于数据结合D中的每一个元素用中间标有元素的方框表示，一般称为数据节点，

并简称为节点：

为了进一步表示数据之间的前后关系，对于关系R中的每一个二元组，用一条有向线段从前件节点指向后减节点。

3、线性结构和非线性结构

如果一个非空的数据结构满足下列两个条件：

（1）有且只有一个根节点。

（2）每一个节点最多有一个前件，也最多有一个后件。

则称该数据结构为线性结构。线性结构又称线性表。

一个数据结构不是线性结构，则为非线性结构

4、线性表的基本概念

线性表有一组元素组成。比如一年中的（春、夏、秋、冬）、

其中的矩阵也是线性表（存储时数据是100010001）分为三段

1.有且仅有一个根节点。

2.集合中必存在唯一的一个“第一元素”。

3.集合中必存在唯一的一个 “最后元素” 。

4.除最后一个元素之外，均有唯一的后继(后件)。

5.除第一个元素之外，均有唯一的前驱(前件)。

5、线性表的顺序存储结构

线性表的顺序存储结构具有以下两个基本特点：

（1）线性表中所有元素所占的存储空间是连续的

（2）线性表中各种元素在存储空间中是按逻辑顺序依次存放的。【链表】

在线性表的顺序存储结构下可以对线性表进行各种处理。主要的运算有以下几种：线性表的插入，删除，查找，排序等。

6、本节练习

1、设元素集合为D={1,2,3,4,5,6}。B={D,R}为线性结构所对应的R是

A)、R={(6,1),(5,6),(1,3),(3,4),(3,2)};

B)、R={(6,1),(5,6),(1,3),(2,4),(3,2)}

C)、R={(6,1),(5,6),(1,3),(2,4),(3.2)}

D)、R={(4,5),(6,1),(5,6),(1,3),(2,4),(3,2)}

C

证明选项A是非线性的

证明选项B也是非线性的

5->6->1->3->2->4

证明C选项是线性的结构

证明D是非线性结构

2、下列叙述中正确的是、

A）有且只有一个根结点的数据结构可能是线性结构，也可能是非线性结构

B）每一个结点最多有一个前件也最多有一个后件的数据结构一定是线性结构

C）有且只有一个根节点的数据结构一定是线性结构

D）有且只有一个根节点的数据结构一定是非线性结构

A

比如树就是非线性结构但是只有一个根结点所以A是正确的

数也是只有一个前件和一个后件B是错误的

树可以推翻上方所有的概念

3、下列叙述中正确的是

A）具有两个根结点的数据结构一定是非线性结构

B）存储空间连续的数据结构一定是线性结构

C）没有根结点的非空数据结构一定是非线性结构

D）存储空间不连续的数据结构一定是非线性结构

A

4、在线性表的顺序存储结构当中，其存储空间连续，各元素所占的字节数

A）相同，元素的存储顺序与逻辑顺序一致

B）相同，但其元素的存储顺序可以与逻辑顺序不一致

C）不同，但是元素的存储顺序与逻辑顺序一致

D）不同，且其元素的存储顺序可以与逻辑顺序不一致

A

三、栈和队列

1、栈及其基本运算

栈是限定在一端插入与删除的线性表。

允许插入与删除的一端称为栈顶（Top），而不允许插入与删除的另外一端称为栈底（Bottom）。

栈是按照“先进后出”或“后进先出”的原则组织数据。

在栈的顺序存储空间S（1:m）中，S（bottom）通常栈底元素（在非空情况下），S（top）为栈顶元素。top=0表示栈空，top=m表示为栈满。

入栈运算是栈顶插入一个元素，top=top+1。如果栈空间已满，不能再进入到栈。这种情况称为“上溢”错误。

推栈运算是栈顶取出一个元素，top=top-1。如果为空栈。不能再退栈。这种情况称为“下溢”错误。

Top=0，栈的开口向上，元素的个数是Top。

Top=Bottom+1,栈的开口向下，元素个数是Buttom-Top+1;

2、队列及其基本运算

队列：队头删除元素，队尾插入元素的线性表。

允许插入元素的一端称为队尾（Rear），允许删除元素的称为队头（Front）。

队列又称为“先进先出”或“后进后出”的线性表，它体现了“先来先服务”的原则。

队列的顺序存储结构一般采用循环队列的形式。

(R-F)+m

习题练习、

C

B

C

C

D

C

(R-F)+m=m-1===》答案为B

C

C

B

A

D

C

四、线性链表的基本概念

线性表的顺序存储结构具有简单，运算方便等优点，特别是对于小线性表或者长度固定的线性表，采用顺序存储结构的优越性更为突出。

但是，对于大的线性表，特别是元素变动频繁的大线性表，不宜采取顺序存储结构，而是采用的链式存储结构。

1、概念理解

一般的线性表（顺序存储结构）

改进存储数据的方式（线性链表）

注意：线性链表是线性结构

2、习题练习

答案： C（列如双向链表）

D选项当中列如：

所以D选项是错误的

D

A

B

C

B

A

B

解析：

循环队列本身是一种顺序存储结构，而循环列表是一种链式存储结构。两者之间是平级关系。

线性链表是线性表的链式存储结构，包括单链表，双链表，循环链表等。

队列的顺序存储结构一般采用循环队列的形式。

D

B

C

B