计算机二级C语言公共基础知识手册
1.算法的时间复杂度是指执行算法所需要的计算工作量.算法的工作量由算法所执行的基本运算次数来度量,而算法所执行的基本运算次数是问题规模的函数.
2.算法的空间复杂度是指算法执行过程中所需要的存储空间,存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间.
3.一个算法通常由两种基本要素组成:一是对数据对象的运算和操作;而是算法的控制结构.
4算法设计基本方法主要包括有列举法、归纳法、递推、递归和减半递推技术.
5.数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构(也称数据的物理结构).、
6.数据处理是指对数据集合中的各元素以各种方式进行运算,包括插入、删除、查找、更改等运算,也包括对数据元素进行分析.
7.数据元素是指相互有关联的数据元素的集合.
8.前驱和后继关系是数据元素之间的一个基本关系,但前驱个后继关系所表示的实际意义随具体对象的不同而不同.一般说来,数据元素之间的任何关系都可以用前驱和后继关系来描述.
9.常用的存储结构有顺序链接、索引等存储结构.而采用不同的存储结构,其数据处理的效率是不同的.
10.在数据结构中,没有前驱的结点称为根结点;没有后继的结点称为终端结点(叶子结点);数据结构中除了根结点与终端结点外的其他结点一般称为内部结点.
11.在数据结构中,结点几结点的相互关系有线性结构和非线性结构.
12.线性结构(线性表):非空数据结构满足(1)有且只有一个根结点;(2)每个结点最多有一个前驱,也最多有一个后继.
在一个线性结构中插入或删除任何一个结点后还应该是线性结构,若删除或插入后不是线性结构,则该数据结构不能称为线性结构.
13.线性表是最简单、最常用的一种数据结构.有一组数据元素组成.在稍微复杂的线性表中,一个数据元素可以由若干个数据项组成,在这种情况下,常把数据元素称为记录,含有大量记录的线性表就称作文件.
14.非空线性表如与如下结构特征(1)有且只有一个根结点A1,它无前驱;(2)有且只有一个终端结点AI,它无后继;(3)除根结点与终端结点外,其他所有结点有且只有一个前驱,也只有一个后继.线性表中结点的个数N称为线性表的长度.当
N=0时,称其为空表.
15.在计算机中存放线性表,一种最简单的方法是顺序存储,也称顺序分配.
16.线性表的顺序存储结构具有以下两种基本特点:(1)线性表中所有元素所占的存储空间是连续的;(2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的. 在线性表的存储结构中,其前后继两个元素在存
储空间中是紧邻的,且前驱元素一定存储在后继元素的前面.
17.假设线性表中第一个数据元素的存储地址是ADR(AI),每一个数据元素占K 个字节,则线性表中第I个元素AI在计算机存储空间中的存储地址是
ADR(AI)=ADR(A1)+(I-1)K.
18.在栈中,允许插入与删除的一端叫做栈顶,而不允许插入与删除的另一端叫做栈底.栈顶元素总是最后被插入的元素,从而也是最先被删除的元素;栈底元素总是最先被插入的元素,从而也是最后才能被删除的元素.既栈是按照"先进后出"(FILO.FIRST IN LAST OUT)或"后进先出"(LIFO,LAST IN FIRST OUT).因此,栈也被叫做"先进后出"或"后进先出"表.栈具有记忆作用.
19.栈是一种特殊的线性表.
20.栈的基本运算有三种:入栈(会出现"上溢"错误)、退栈(会出现"下溢"错误)和读栈顶元素.
21.队列是指允许在一端进行插入、在另一端进行删除的线性表.允许插入的
一端叫做队尾,通常用一个称为尾指针(REAR)的指针指向队尾元素.既尾指针总是指向最后被插入的元素;允许删除的一端称为排头(对头),通常也用一个排头指针指向排头元素的前一位置。显然,最先插入的元素将最先能够被删除,最后插入的元素最后才能被删除。因此,队列又称为“先进先出”或“后进后出”的线性表,它体现了“先来先服务”的原则。在队列中,对尾指针REAR与派头指针FRONT共同反映了队列中元素动态变化的情况。
22。往队列的对尾插入一个元素称为入队运算,从队列的排头删除一个元素的运算称为退队运算。
23。循环队列主要有两种基本运算:入队运算和退队运算。每进行一次入队运算,队尾指针就进一;每进行一次退队运算,排头指针就进一。
24递归算法一般需要利用栈来实现。
25。在链式存储方式中,要求每个结点由两部分组成:一部分用于存放数据元
素值,称为数据域;另一部分用于存放指针,称为指针域。其中指针用于指向该结点的前一个或后一个结点(既前驱或后继)。
26。数据结构作为计算机的一门学科主要讨论和研究三方面的问题:数据的逻辑结构;数据的存储结构;对各种数据进行的运算。
27。数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构(物理结构)。线性链表属于存储结构。
28,在线性单链表中,每一个结点只有一个指针域,由这个结点只能找到后继结点,但不能找到前驱结点,必须从头指针开始重新寻找。
29。为了弥补线性单链的这个缺点,在某些应用中,对线性链表中的每个结点
设置两个指针,一个称为左指针(LLINK),用以指向前驱结点,另一个称为右指针(RLINK),用以指向后继结点,这样的线性链表称为双向链表。
30。栈也是线性表,也可以采用链式存储结构。
在实际应用中,带链的栈可以用来收集计算机存储空间中所以空闲的存储结点,这种带链的栈称为可利用栈。
31。线性链表的插入是指在链式存储结构下的线性表中插入一个新元素。
为了要在线性链表中插入一个新元素,首先要给该元素分配一个新结点,以便
用于存放该元素的值。
新结点可以从可利用栈中取得。然后将存放新元素值的结点连接到线性链表
中指定的位置。
32。在线性链表中删除一个元素后,不需要移动表的数据元素,只须改变被删
除元素所在结点的前一个结点的指针域即可。
33。循环链表中设置了一个表头结点,因此,在任何情况下,循环链表中至少有一个结点存在,从而使空表与非空表的统一;
在对循环链表进行插入和删除的过程中,实现了空表与非空表的同意。
34。二叉树的遍历可以分三种:前序遍历,中序遍历,后序遍历。
前序遍历:1,访问根结点;2,前序遍历左子树;3,前序遍历右子树;
中序遍历:1,中序遍历左子树;2,访问根结点;3,中序遍历右子树;
后序遍历:1,后序遍历左子树;2。后序遍历右子树;3,访问根结点。
35。满二叉数:除最后一层外,每一层上的所有结点都有两个子结点。也就是说,在满二叉树中,每一层上的结点数都达到最大值,既在满二叉树的第K层上有2的K次方减1个结点,且深度为M的满二叉树有2的M次减1个结点。
36。在树结构中,一个结点所拥有的后继个数称为该结点的度。在树中,所有结点中最大的度称为树的度。
37.完全二叉树是指除最后一层外,每一层上的结点数均达到最大值;在最后一层上只缺少右边的若干结点。更确切的说,从根结点算起,对二叉树的结点自上而下、自坐至右用自然数进行连续编号,则深度为M、且有N个结点的二叉树,当且仅当其每一个结点都与深度为M的满二叉树中编号从1到N的结点一一对应,称为完全二叉树。
38。满二叉树是完全二叉树,而完全二叉树一般不是满二叉树。
39。如果按从上到下、从左到右顺序存储完全二叉树的各结点,则很容易确定每一个结点的父结点、左子结点和右子结点的位置。
40。二分法查找只适用与顺序存储的有序表。此有序表指线性表中的元素按值非递减排列。对于长度为N 的有序线性表,在最坏的情况下,二分查找只需要比较LOG下2上N次,而顺序查找需要比较N次。
41,虽然顺序查找的效率不高,但有两种情况必须用该方法:1,线性表为无序表2。采用链式存储结构
42。假设线性表的长度为N,则在最坏情况下,冒泡发需要比较次数为N(N-1)/2,从前往后和从后往前个需要N/2遍的扫描。
43。堆排序的方法对较大规模的线性表来说是很有效的。在最坏情况下,他需比较的次数是O(nlog下2上n)。堆排序时间复杂度最小,
44。队排序方法如下:1,先将一个无序序列建成堆;2,将堆顶元素(序列中的最大项)与堆中最后一个元素交换(最大项应该在序列的最后)。不考虑已经换到最后的那个元素,只考虑前N-1个元素构成的子序列。显然,该子序列已不在是堆,但左右子树仍为堆,可调整为堆,反复,直到剩下的子序列为空为止。
45,快速排序发也是一种互换类的排序方法,比冒泡发速度快,可实现通过一次交换而消除多个逆序。
46,快速排序基本思想如下:从线性表中选取一个元素,设为T,将线性表中小于T的元素移到前面,而前面大于T的数移到后面,结果就将线性表分成两部分(两个子表),T插入到其分界线的位置,这个过程称为线性表的分割。这样,前面子表中的所有元素均不大于T,后面所以元素均不小于T。若对分割后的各子表在按上述方法进行分割,一直持续下去,直到所以子表为空为止,此时的线性表就变成了有序表。因此,快速排序发的关键是对线性表进行分割,并对各分割出的子表进行分割。
47,简单插入排序法中,每次比较后最多移掉一个呢序。因此,他与冒泡排序法相同,在最坏情况下,需要N(N-1)/2次比较。
48,希尔排序法属于插入类排序,但他对简单插入排序作了较大改进。选择类排序法主要有简单选择排序法和堆排序法;交换类排序法主要有,冒泡排序法和快速排序法;插入类排序法主要有简单插入排序法和希尔排序法。
49,源程序文档化时应注意考虑:符号名的命名、程序注释和视觉组织。注释一般分为序言性注释和功能性注释。序言性注释通常位于每个程序的开头部分,它给出程序的整体说明,主要描述内容包括:程序标题、程序功能说明、主要算法、接口说明、程序位置、开发简历、程序设计者、复审者、复审日期、修改日期等。功能性注释的位置一般嵌在源程序体之中,主要描述其后的语句或程序做什么。
50,在编写程序时,开发者需注意数据说明的风格,以便使程序中的数据说明更易于理解个维护。程序编写要作到清晰第一,效率第二。
51,当程序设计语言对输入格式有严格要求时,应保持输入格式与输入语句的一致性。
52,程序的易读性是结构话程序设计最重要的特点。
53,按结构化设计方法设计的程序具有以下特点:1,程序易于理解、使用和维护,程序员采用结构化编程方法,便于控制、降低程序的复杂性,因此便于编写程序。2,提高了编程的效率,降低软件开发的成本。3,结构化程序设计选用的每个控制结构只允许有一个入口和一个出口,
54,模块是指执行某一个特定任务(也可以是实现某一特定的抽象数据类型)的数据结构和程序代码。一个模块有他的外部特征和内部特征。外部特征包括模块的接口和模块的功能;内部特征包括模块的局部数据和实现该模块的程序代码。调用一个模块时只需知道它的外部特征即可。
55,在结构化程序设计的具体实施中要主要把握以下要素:1,使用程序设计语言中的顺序、选择、循环等有限的控制结构表示程序的控制逻辑;2,选用的控制结构只准有一个入口和一个出口;3,程序语句组成容易识别的快,每快只准有一个入口和一个出口;4,复杂结构应该