文档介绍：公共基础知识
1
数据结构与算法
程序设计基础
软件工程基础
数据库基础知识
2
第 1 章数据结构与算法
一、算法的基本概念
二、线形结构与非线形结构、栈和对列的定义
三、二叉树的定义
四、查找技术与排序技术
3
一、算法的基本概念:
(1)算法的空间复杂度:是指算法在运行过程中需辅
助存储空间的大小。
(2)算法的时间复杂度:是指执行算法所需要的计算
工作量(基本运算次数)。
(3)算法的基本特征:确定性、可行性、有穷性、拥
有足够的情报。
(4)算法的有穷性:是指一个算法必须在执行有限的
步骤以后结束。
4
例1:在下列选项中,不是一个算法一般应该具有的基本特征的是____。(5-1)
(A) 确定性(B) 可行性(C) 无穷性(D) 拥有足够的情报
√
√
√
例2: 算法的时间复杂度是指____。(2-1)
(A) 执行算法程序所需的时间(B) 算法程序的长度
(C) 算法执行过程中所需要的基本运算次数
(D) 算法程序中的指令条数
例3:算法的空间复杂度是指____。(3-1)
(A) 算法程序的长度(B) 算法程序中的指令条数
(C) 算法程序所占的存储空间
(D) 算法执行过程中所需要的存储空间
5
例4: 下面叙述正确的是___。(1-1)
(A) 算法的执行效率与数据的存储结构无关
(B) 算法的空间复杂度是指算法程序中指令(或语句)的条数
(C) 算法的有穷性是指算法必须能在执行有限个步骤之后终止
(D) 算法的时间复杂度是指执行算法程序所需要的时间
√
√
例5:在计算机中,算法是指____。(6-1)
(A) 查询方法(B) 加工方法
(C) 解题方案的准确而完整的描述(D) 排序方法
例6: 算法分析的目的是________。(8-1)
(A) 找出数据结构的合理性
(B) 找出算法中输入和输出之间的关系
(C) 分析算法的易懂性和可靠性(D) 分析算法的效率以求改进
√
6
(7)下列叙述中正确的是________。(069)
A)一个算法的空间复杂度大,则其时间复杂度也必定大
B)一个算法的空间复杂度大,则其时间复杂度必定小
C)一个算法的时间复杂度大,则其空间可复杂度必定小
D)上述三种说法都不对
√
7
例9:算法的基本特征是可行性、确定性、_______和拥有足够的情报。(7-1)
例7:算法的复杂度主要包括时间复杂度和_____复杂度。
(1-1)
空间
例8:实现算法所需的存储单元多少和算法的工作量大小分别称为算法的_____________________。(6-1)
空间复杂度和时间复杂
有穷性
(5)问题处理方案的正确而完整的描述称为【5】。(054)
算法
8
二、线形结构与非线形结构、栈和对列的定义
(1)数据结构的基本概念
数据结构主要研究和讨论以下三个方面的问题:
①数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构。
②在对数据进行处理时,各数据元素在计算机中的存储存储关系,即数据的存储结构。
③对各种数据结构进行的运算。
9
(2)根据数据结构中各数据元素之间前后间关系的复
杂程度,一般将数据结构分为两大类型:线形结构与非
线形结构。
如果一个非空的数据结构满足下列两个条件:
①有且只有一个根结点;
②每个结点最多有一个前件,也最多有一个后件。则称
该数据结构为线形结构,又称线形表。
所以线形表、栈与队列、线形链表都是线形结构,而二
叉树是非线形结构。
10