计算机软件基础知识讲座

《计算机软件基础知识讲座》由会员分享，可在线阅读，更多相关《计算机软件基础知识讲座（132页珍藏版）》请在金锄头文库上搜索。

1、信息科学与技术学院信息科学与技术学院第三讲 计算机软件基础知识1.1 算法的基本概念及其特征1. 算法：是一组有穷指令集，是解题方案的准确而完整的描述 。通俗地说，算法就是计算机解题的过程。 2. *算法的基本特征：(1)可行性：算法中的操作能够用已经实现的基本运算执行 有限次来实现。(2)确定性：算法中的每一步都有确切的含义。 (3)有穷性：一个算法在执行有穷步骤后能够结束。(4)拥有足够多情报：算法执行过程中要尽可能考虑各种情 况；一个算法至少有一个输出。第一部分 数据结构与算法数据结构与算法23.算法的基本要素：(1)对数据对象的运算和操作(2)算法的控制结构4.*算法设计基本方法： (

2、1)列举法 (2)归纳法 (3)递推 (4)递归(5)减半递推 (6)回溯法第一部分 数据结构与算法数据结构与算法35.*算法复杂度：(1)算法的时间复杂度：是指算法所需要的计算工作量。 用基本运算次数来衡量，与程序中的执行的指令条数 密切相关。(2)算法的空间复杂度：是指执行这个算法所需要的内存 空间。第一部分 数据结构与算法数据结构与算法4例题: (1)算法的时间复杂度是指( ) A)执行算法程序所需要的时间 B)算法程序的长度 C)算法执行过程中所需要的基本运算次数 D)算法程序中的指令条数(2)算法的空间复杂度是指( ) A)算法程序的长度 B)算法程序中的指令条数 C)算法程序所占的

3、存储空间 D)算法执行过程中所需要的存储空间第一部分 数据结构与算法数据结构与算法5(3)下列叙述中正确的是( )。 A)算法的效率只与问题的规模有关，而与数据的存储结构无关 B)算法的时间复杂度是指执行算法所需要的计算工作量 C)数据的逻辑结构与存储结构是一一对应的 D)算法的时间复杂度与空间复杂度一定相关 (4)下列叙述中正确的是( )。 A)一个算法的空间复杂度大，则其时间复杂度也必定大 B)一个算法的空间复杂度大，则其时间复杂度必定小 C)一个算法的时间复杂度大，则其空间复杂度必定小 D)上述三种说法都不对第一部分 数据结构与算法数据结构与算法6(5)问题处理方案的正确而完整的描述称为

4、【 】。 (6)算法复杂度主要包括时间复杂度和【 】复杂度。 (7)以下不属于算法特性的是( ) A)有穷性 B)简捷性 C)可行性 D)确定性算法 空间第一部分 数据结构与算法数据结构与算法71.2 数据结结构的基本概念1、数据结结构是计计算机科学与技术领术领 域广泛使用的一个 基本术语术语 ，用来反映数据的内部构成。数据结结构研究的三个方面： (1)数据集合中各数据元素之间间所固有的逻辑逻辑 关系,即数 据的逻辑结逻辑结 构 (2)在对对数据进进行处处理时时,各元素在计计算机中的存储储关 系,即数据的存储结储结 构(物理结结构) (3)对对各种数据结结构进进行的运算第一部分 数据结构与算法

5、数据结构与算法8数据结构类型1数据的逻辑结构 2、数据的存储结构 3、数据的运算：检索、排序、插入、删除、修改等。 A线性结构 B非线性结构A 顺序存储B 链式存储 线性表栈队树形结构图形结构数据结构的三个方 面 9 数据的逻辑结构 线性结构(顺序表、链表、队列、堆栈) 非线性结构(树、图) 数据的逻辑结构是反映数据元素之间逻辑关系的数 据结构(与所使用的计算机无关)。数据的逻辑结构包 含： (1)表示数据元素的信息； (2)表示各数据元素之间的前后件关系。第一部分 数据结构与算法数据结构与算法10线线性结结构：必须满须满 足以下两个条件 (1)有且只有一个根结结点, (2)每个结结点最多有一

6、个前件,也最多有一个后件。 线线性结结构也称线线性表。图1-1线性结构第一部分 数据结构与算法数据结构与算法11线性结构和非线性结构 线性结构条件线性结构条件（1）有且只有一个根结点； （2）每一个结点最多有一个前件，也最多有一个后件。 （3）首节点无前件，尾节点无后件。 非线性结构：非线性结构：不满足线性结构条件的数据结构 注意：在一个线性结构中插入或删除任何一个节点后还应是线性结构；否则，不 能称为线性结构。学学 生生 成成 绩绩 表表86胡孝臣986110395刘忠赏9861107100张卓9861109成绩姓名学号12图图1-1线线性结结构 如果一个结结构不是线线性结结构,则则称为为非

7、线线性结结构 。如图图1-2、图图1-3图1-2非线性结构中的“树”形结构图1-3非线性结构中的“图”形结构第一部分 数据结构与算法数据结构与算法13树形结构全校学生档案管理的树形结构的组织方式全校学生档案管理的树形结构的组织方式非线性 结构 树树形形结结构构14树形结构ABCDEFGH树形结构树形结构 结点间具有分层次的连接关系结点间具有分层次的连接关系HBCDEFGA15图形结构 图图形形结结构构：节节点点间间的的连连接任意接任意1423D= 1 , 2 , 3 , 4R=(1,2) , (1,3) , (1,4) , (2,3)(3,4) , (2,4) 无向图213D= 1 , 2 ,

8、 3 R= (1,2) , (2,3) , (3,2) , (1,3) 有向图16存储结构：也称数据的物理结构,是指数据的逻辑结构 在计算机存储空间中的存放形式。其形式包括顺序、 链接、索引等。顺序存储：顺序存储：逻辑上相邻的结点存储在物理位置相邻的存储单 元里，结点间的逻辑关系由存储单元的邻接关系(位置)来体 现 链式存储：链式存储：不要求逻辑上相邻的结点在物理位置上亦相邻， 结点间的逻辑关系是由附加的指针字段表示的第一部分 数据结构与算法数据结构与算法17顺序存储与链式存储Lo+（n-1)*m元素n元素i元素2元素1LoLo+mLo+(i-1)*m存储地址存储内容Loc(a)=Lo+（i-

9、1)*m每个元 素所占 用的存 储单元 个数 顺序存储顺序存储常用于线性数据结构， 将逻辑上相邻的数据元 素存储在物理上相邻的 存储单元里。 三个弱点三个弱点插入或删除操作时，需 移动大量元数。 长度变化较大时，需按 最大空间分配。 表的容量难以扩充18顺序存储与链式存储 1346 元素3 1536 . . 1536 元素2 1400 . . 元素4 1346 1400 元素1 1345 指针 存储内容存储地址1536元素21400元素11346元素3 元素4head1345链式链式 存储存储 的地的地 址映址映 射表射表19例题 (1)数据的存储结构是指( )A)存储在外存中的数据 B)数据

10、所占的存储空间C)数据在计算机中的顺序存储方式 D)数据的逻辑结构在计算机中的表示(2)以下数据结构中不属于线性数据结构的是 ( )A)队列B)线性表 C)二叉树D) 栈第一部分 数据结构与算法数据结构与算法20(3)下列叙述中正确的是( )A)一个逻辑数据结构只能有一种存储结构B)数据的逻辑结构属于线性结构，存储结构属于非线性结构C)一个逻辑结构可以有多种存储结构，且各种存储结构不影响 数据处理的效率D)一个逻辑结构可以有多种存储结构，且各种存储结构影响数 据处理的效率第一部分 数据结构与算法数据结构与算法211.3 线性表及其顺序存储结构1、线性表的基本概念：线性表是一种最简单,最常用的一

11、种数据 结构。它由一组数据元素构成。 2、线性表的顺序存储结构：(两个特点)(1)线性表中所有元素所占的存储空间是连续的(2)线性表中各元素在存储空间中是按逻辑顺序依次存放的 3、元素ai的存储地址为：ADR(ai)=ADR(a1)+(i-1)k,，ADR(a1)为 第一个元素的地址，k代表每个元素占的字节数。 4、线性表的顺序存储基本操作：插入，删除，查找第一部分 数据结构与算法数据结构与算法221.4 线性链表概念：用一组任意的存储单元来依次存放线性表的各结点。这组存储单元既可以是连续的，也可以是不连续的，甚 至是零散分布在内存中的任意位置上的。因此，链表中结点 的逻辑次序和物理次序不一定

12、相同。线性链表的基本运算：插入、删除、查找第一部分 数据结构与算法数据结构与算法23线性链表的结点由两部分组成：(1)用于存储数据元素值， 称为数据域；(2)用于存放指针，称为指针域，用于指向前一个 或后一个结点。在链式存储结构中，存储数据结构的空间可以不连续，各 数据结点的存储顺序与数据元素之间的逻辑关系可以不一致， 而数据元素之间的逻辑关系是由指针域来确定的。所以，链式 存储方式即可用于表示线性结构，也可用于表示非线性结构。第一部分 数据结构与算法数据结构与算法24几种常见的链表：(1)单向链表，HEAD称为头指针，HEAD=NULL(或0)称为空表；数据 域指针 域head第一部分 数据

13、结构与算法数据结构与算法(2)双向链表：左指针(Llink)指向前件结点，右指针(Rlink) 指向后件结点。(3)循环链表：25 线性表的顺序存储结构称为顺序表 线性表的链式存储结构称为线性链表 二者的比较： 1)顺序表存储数据时在逻辑上相连的在物理上也一定相连。 2)链表存储数据时在逻辑上相连的在物理上不一定相连。 3)顺序表插入和删除比较麻烦，但是访问每一个结点比较简单 4)链表插入和删除比较简单，但是访问每一个结点比较麻烦第一部分 数据结构与算法数据结构与算法261.5 栈和队列栈：也叫堆栈，是指限定在一端进行插入与删除的线性表。 允许插入与删除的一端称为栈顶；不允许插入与删除的另一端

14、称 为栈底。栈按照“先进后出”(FILO)或“后进先出”(LIFO)组织 数据，栈具有记忆作用。栈的基本运算：(1)插入元素：也称为入栈运算(2)删除元素：也称为退栈运算(3)读栈顶元素：将栈顶元素赋给一个指定的变量(此时指针无变化)第一部分 数据结构与算法数据结构与算法27队列：允许在一端(队尾)进入插入，而在另一端(队头)进 行删除的线性表。队列按照“先进先出”(FIFO)或“后进后出 ”(LILO)组织数据。队列基本运算：(1)入队运算：从队尾插入一个元素；(2)退队运算：从队头删除一个元素。循环队列：是将队列的存储空间的最后一个位置绕到第一 个位置，形成逻辑上的形状空间，供队列循环使用

15、，其实质还 是顺序存储结构。第一部分 数据结构与算法数据结构与算法28例题 (1)下列关于栈叙述正确的是( )A) 在栈中只能插入数据B) 在栈中只能删除数据C) 栈是先进先出的线性表D) 栈是先进后出的线性表(2)下列关于队列的叙述中正确的是( ) A) 在队列中只能插入数据B) 在队列中只能删除数据C) 队列是先进先出的线性表D) 队列是先进后出的线性表第一部分 数据结构与算法数据结构与算法29(3)栈和队列的共同特点是( )A) 都是先进先出B) 都是先进后出C) 只允许在端点处插入和删除元素D) 没有共同点(4)设输入序列为1、2、3、4，则借助一个栈可以得到的输出序 列是( )A) 1，3，4，2B) 3，1，4，2C) 4，3，1，2D) 4，1，2，3第一部分 数据结构与算法数据结构与算法30(5)在一个容量为15的循环队列中，若队头front=6,队尾rear=9， 则该循环队列中有( )个元素。答案：3 分析：如图1-8与图1-9的两种循环队列存放数据的形式第一部分 数据结构与算法数据结构与算法在非空队列中，头指针始终指向队头元素前一个 位置，而尾指针始终指向队尾元素的位置31由此可以得出元素的个数为：rear-front=3 可是当