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