计算思维复习大纲课件

期末复习－及考试相关关于考试考试时间：1月4号8:00-9:50考试形式：闭卷笔试考试题型：50个单选题（每个1分） 10个填空题（每空1分）

10个判断题（每个1分）

6个综合题（每个5分）考试范围：第1、2、3、4、5章全部内容注意:开考后40分钟后方可交卷,答题纸上印有"座号"字样,请按本班学号排序号填写第一章计算、计算工具的历史沿革：

在电脑史前史里，帕斯卡被公认为制造出机械计算机的第一人。P7

巴贝奇耗费了整整１０年时间，于１８２２年完成了第一台差分机。P9

楚泽的继电器计算机是世界上第一台二进制电子运算机器。P11

美国宾夕法尼亚大学和有关单位在１９４６年制成了第一台电子计算机——电子数字积分仪与计算机”ＥＮＩＡＣ。P11-12计算与学科渗透：P13

随着当代科学技术的发展，不同学科之间的相互渗透、交叉和综合已成为当今科技发展的一个重要趋势。计算机科学并不是一门独立的学科，它在学科融合、渗透中独占鳌头。当前热点计算：云计算：云计算是一种按使用量付费的模式，这种模式提供可用的、便捷的、按需的网络访问，进入可配置的计算资源共享池(资源包括网络、服务器、存储、应用软件、服务)，这些资源能够被快速提供，只需投入很少的管理工作或与服务供应商进行很少的交互。

P24

特点：虚拟化技术、灵活定制、动态可扩展性、高可靠性和安全性、高性价比。物联网：广义的物联网定义认为物联网是在互联网的基础上，借助各种信息传感设备，通过各种接入网络实现物体与互联网连接，形成人与物、物与物互联的巨大智能网络。

广泛应用于航天、交通、农业、物流等领域。P27

大数据：指需要新处理模式才能具有更强的决策力、洞察发现力和流成优化能力的海量、高增长率和多样化的信息资产。P30

特点：数据体量巨大、数据种类繁多、流动速度快、价值密度低。P31

可穿戴计算：智慧城市：思维与计算思维：常见的思维模式分为３种：P38①以观察和归纳自然(包括人类社会活动)规律为特征的实证思维；②以推理和演绎为特征的逻辑思维；③以抽象化和自动化为特征的计算思维；第二章计算机概述：P45-46

1、世界上第一台电子计算机，1946年2月在美国宾夕法尼亚大学诞生,取名为ＥＮＩＡＣ。2、电子计算机的发展按构成计算机的电子器件来划分，至今已经历了４代：第一代电子管计算机，主要用于科学计算；第二代晶体管计算机，提出操作系统概念，出现FORTRAN等高级语言；第三代集成电路计算机；第四代大规模和超大规模集成电路计算机时代，微型计算机开始出现。图灵与图灵机：P55图灵机是英国数学家阿兰图灵于１９３６年提出的一种抽象计算模型。计算机的基本组成及工作原理：

冯诺依曼原理：

P57现代计算机是一个自动化的信息处理装置，而它之所以能实现自动化信息处理，是因为采用了“存储程序”工作原理。这一原理是１９４６年由冯诺依曼提出并论证的，这一原理确立了现代计算机的基本组成和工作方式：①计算机硬件由５个基本部分组成:运算器、控制器、存储器、输入设备和输出设备；②计算机内部采用二进制来表示程序和数据；③采用“存储程序”的方式，将程序和数据放入同一个存储器中，计算机能够自动高速地从存储器中取出指令加以执行。五大部件在控制器的控制下协调统一地工作。首先，把表示计算步骤的程序和计算中需要的原始数据在控制器输入命令的控制下，通过输入设备送入计算机的存储器进行存储；

其次当计算开始时，在取指令作用下把程序指令逐条送入控制器，控制器对指令进行译码，并根据指令的操作要求向存储器和运算器发出存储、取数命令和运算命令，经过运算器计算并把结果存放在存储器内，

最后在控制器的取数和输出命令作用下，通过输出设备输出计算结果。

1、通常将运算器和控制器统称为中央处理器(ＣＰＵ)，它是整个计算机的核心部件，是计算机的“大脑”，它控制了计算机的运算、处理、输入和输出等工作。）2、存储容量的大小以字节为单位来度量，经常使用ＫＢ(千字节)、ＭＢ(兆字节)、ＧＢ(千兆字节)和ＴＢ(兆兆字节)来表示。它们之间的关系是:１ＫＢ＝１０２４Ｂ；１ＭＢ＝１０２４ＫＢ；１ＧＢ＝１０２４ＭＢ；１ＴＢ＝１０２４ＧＢ。3、存储器分为内存储器(主存储器)和外存储器(辅助存储器)两大类。P59

内存在计算机主机内，它直接与运算器、控制器交换信息，容量虽小，但存取速度快，一般只存放那些正在运行的程序和待处理的数据。

内存分为RAM(可随机读写，断电后数据消失)和ROM（它只能读出信息，不能写入信息，断电后仍能保存数据)

外存储器是指除计算机内存及ＣＰＵ缓存（高速缓存读取速度相对更快）以外的存储器，外存中的程序和数据必须先送入内存才能被计算机执行，外存存取速度慢，但容量很大，此类存储器一般断电后仍然能保存数据。常见的外存储器有硬盘、软盘、光盘、Ｕ盘等。

4、常用的输入设备有键盘、鼠标、光笔、扫描仪、数字化仪、条形码阅读器等；常用的输出设备有显示器、打印机、绘图仪等。

5、没有安装软件的计算机称为“裸机”。

6、计算机软件可分为系统软件和应用软件两大类。P61

系统软件包括操作系统、数据库和数据库管理系统、程序设计语言及其解释编译程序、网络管理软件等；

应用软件包括文字处理、图形图像处理、音频视频处理、杀毒类等。7、操作系统是计算机系统中必不可少的软件，是用户和计算机之间的接口，任何一个用户要使用计算机都必须首先安装操作系统。操作系统是一个管理电脑硬件与软件资源的程序，同时也是计算机系统的内核与基石。目前常见的操作系统有ＤＯＳ、ＯＳ/２、ＵＮＩＸ、Ｌｉｎｕｘ、Ｗｉｎｄｏｗｓ系列、Ｎｅｔｗａｒｅ等8、主板(又称主机板ＭａｉｎＢｏａｒｄ或系统板ＳｙｓｔｅｍＢｏａｒｄ等)是微机内最大的一块集成电路板。计算机问题求解：P68精确问题也可称为界定清晰的问题，是指初始状态、目标状态以及由初始状态如何达到目标状态的一系列过程都很清楚的问题。例如：已知Ａ>Ｂ，Ｂ<Ｃ，问Ａ与Ｃ哪个大？这是一个目的非常明确的问题。模糊问题也称界定含糊的问题，是指那些对问题的初始状态或目标状态没有清楚的说明，或者对二者都没有明确说明的问题，这些问题具有很大的不确定性。例如“如何写一篇论文”这个问题的初始状态和目标状态都是不清楚的。计算机求解问题过程首先是分析问题并建立数学模型

二进制：进制之间的转换：

十－二进制转换：整数部分，除2取余法；小数部分，乘2取整法。二－八进制转换：整数部分，三位一组，从右往左；小数部分，三位一组，从左往右数值信息的表示与运算：在计算机中数值型的数据有两种表示方法，一种叫做定点数，另一种叫做浮点数。原码、反码、补码

第三章非数值型数据：1、非数值信息包括文字、图形、图像、声音等，在计算机中采用编码的方式来表示。2、目前计算机中采用的字符编码主要是ASCII码，它是ＡmericanStandardCodeforInformationInterchange（美国标准信息交换代码)的缩写，已被国际标准化组织(ISO)采纳，作为国际通用的信息交换标准代码。ASCII码有７位ASCII码和８位ASCII码两种编码方式。

７位ASCII

码称为标准ASCII码，用一个字节(８位)表示一个字符，并规定其最高位为０，可表示128个不同字符。

８位ASCII

码称为扩展ASCII码，用８位二进制进行编码，最高位恒为１。扩展部分的范围为128-255，代表128个扩展字符。８位ASCII

码总共可以代表256个字符。

会使用标准ASCII码字符表P98

汉字编码：P99

汉字处理过程：在计算机中输入汉字时，操作者在键盘上输入“输入码”，通过“输入码”找到汉字的国标区位码(也称为交换码)，再计算出汉字的机内码后存储，而当显示或打印汉字时，则首先从指定地址取出汉字内码，根据内码从字模库中取出汉字的字形码，并以汉字字形码输出到屏幕或打印机上。

1、输入码是用键盘上的字母符号编码组合来表示每一个汉字的编码，它使人们通过键入字母符号代替键入汉字，也称为汉字外部码(简称外码)。

2、汉字交换码是指具有汉字处理功能的不同计算机系统之间在交换汉字信息时所使用的代码标准，也称国标码。为了能区分汉字与ASCII码，在计算机内部表示汉字时把交换码(国标码)两个字节的最高位改为１，称为机内码。在汉字信息系统内部对汉字信息的采集、传输、存储、加工运算的各个过程都要用到机内码，机内码是计算机内部真正用来存储和处理汉字信息的代码。

3、字形码记录汉字的外形，用来将汉字显示到屏幕上或打印到纸上，是汉字的输出形式。记录汉字字形通常有点阵法和矢量法两种方法，其中点阵规模越大，字形越清晰美观，在字模库中所占用的空间也越大。“大”③机内码：汉字在计算机内部采用汉字内码存储，每个汉字占两字节且最高位均为1的0，1型编码。计算机内部由外到内由内到外b7

b6b5b4b3b2b1b0

b7

b6b5b4b3b2b1b0

0011010001110011国标码1011010011110011(机)内码“大”汉字字形码是一种字模点阵码。也有不同的处理汉字点阵信息的编码，如向量编码等oooooo11oooooooooooooo11oooooooooooooo11oooooooooooooo11ooooo1oo1111111111111111oooooo11oooooooooooooo11oooooooooooooo11oooooooooooooo11oooooooooooooo111oooooooooooo11oo1oooooooooo11oooo1oooooooo11ooooo11ooooooo1ooooooo11ooooo1ooooooooo111o

11ooooooooooo1oo计算机内部由外到内由内到外大④字形码是用0和1编码有、无亮点像素，形成一种点阵形式的汉字字形编码，通过显示器或打印机输出汉字。0和1与字母符号---编码(6)汉字如何进行处理?为什么会有那么多种汉字编码?简易１６Ｘ１６，普及２４Ｘ２４，提高３２Ｘ３２，精密４８Ｘ４８，点阵规模越大，字形越清晰美观，在字模库中所战胜的空间也越大。多媒体信息的表示和处理：1、图像是由扫描仪、照相机等输入设备捕捉实际的画面产生的数字化文件，由像素点阵构成。图像中的每个像素点用二进制位表示，位数越高，所表示的图像越接近自然影像，所以图像又称为位图。

常用的图像文件格式有:BMP、GIF、JPEG、TIFF、PNG、WMF、PSD、PDF等

2、图形是由一组存储在计算机中的指令组成的，这些指令描述点、线、面等大小形状及其位置、维数，计算机通过读取这些指令并将其转换为屏幕上所显示的形状和颜色的方式来显示的图像，又称为矢量图，如office中的剪贴画。总的来说，由于矢量图像存储的是指令，所以要比位图图像文件小得多。

3、音频文件：常用的声音文件格式有：WAV、MP3、MIDI等。

数据结构数据结构分为逻辑结构和物理结构。逻辑结构是指数据对象中数据元素之间的相互关系。包括以下四种：集合线性结构树结构图结构物理结构是指数据对象在计算机中的存储形式。

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。数据、数据之间的关系第四章四种逻辑结构：每个数据元素看做是一个结点，用圆圈表示。元素之间的关系用连线表示。281954736集合：数据元素除了同属于一个集合外，它们之间没有什么关系。各元素是平等的。123456789线性结构：数据元素之间是一对一关系。数据元素之间存在线性关系，也称先后关系，每个元素都有一个唯一的前导元素和一个唯一的后继元素，第一个元素没有前导，最后一个元素没有后继。四种逻辑结构：树结构：数据元素之间存在一对多的层次关系。1234567图结构：数据元素之间是任意（孤立点、一对一，一对多，多对多）关系。281954736数据元素之间呈现层次关系，在树形结构中，每一个元素通常称为一个结点，每个结点（根结点除外）有一个父结点，一个结点可以有多个子结点在图状结构中每个元素称为一个结点，图状结构又称网状结构。图结构可表达元素之间的任意关系。物理结构：也称为存储结构，即如何把数据元素存储到计算机的存储器中（主要指内存，外存通常用文件来描述）。物理结构应正确反映数据元素之间的逻辑关系。两种存储结构：顺序结构：逻辑上相邻的元素存储在连续的存储单元里。用一组地址连续的存储单元依次存储数据集合中的元素。

借助于数据在存储器中的相对位置表示数据之间的关系。链式结构：数据元素可存放在任意存储单元里，数据元素之间的关系用箭头（指针）表示。用一个指针表示结点（数据元素）之间的逻辑关系。每个结点之间没有对应的物理关系

线性结构（栈、队列、线性表）线性结构是一种描述元素先后关系的数据结构，也称为线性表。线性表的顺序存储结构可以用数组来表示。

a、元素存储在一组地址连续的存储单元；b、元素的物理顺序和逻辑顺序一致；c、线性表中的数据元素可以随机存取。

d、不便于进行插入和删除操作。

线性表的链式存储：a、元素存储在一组地址不连续的存储单元；b、元素的物理顺序和逻辑顺序不一致；c、线性表中的数据元素不可以随机存取。

d、便于进行插入和删除操作。数据域指针域CBAbottomtop栈(Stack)是一种后进先出操作受限的线性表，它的插入和删除操作只能在表的一端(表尾)进行。插入：入栈，把新元素放入栈顶top上移删除：出栈，把栈顶的元素删除top下移头指针尾指针队列（Queue）是一种先进先出（FirstInLastOut，FILO）的线性表。只能在表的一端进行插入操作（头指针改变），在另一端进行删除操作（尾指针改变）。【例】已知线性表

(A，B，C，D，E，F，G)存储地址如下表所示，头指针是1438，填写指针域中的指针并画出单链表结构图。存储地址数据域指针域1306F1320D1423C1438A1465G1489B1503EBLAMFECGIDHKJNO结点树根叶子结点孩子双亲兄弟度深度树结构：数据元素之间存在一对多的层次关系。树形结构a、数据元素之间呈现层次关系，b、在树形结构中，根结点除外，

每个结点有一个双亲结点。c、一个结点可以有多个子结点，

数据之间的关系是一对多的。d、

叶子结点没有子结点。e、度是指节点的孩子的个数。f、深度是组成树的结点的最大层数。2二叉树二叉树（BinaryTree）是n（n≥0）个结点的有限集合，或者是空集，或者是由一个根和分别称为左子树、右子树的两个不相交的二叉树构成。二叉树的两棵子树有左右之分。树中结点的度是任意的，二叉树中每个结点的度不能大于2。BGAHEDCFI二叉树的应用：二叉查找树（二叉判定树）二叉排序树（中序遍历）霍夫曼编码（带权的二叉树）图图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成。通常表示为：G(V,E)，其中：G表示一个图；V是图G中顶点的集合；E是图G中边的集合。图的基本概念：顶点(Vertex)边：无向边、有向边无向图、有向图权：与边相关的数，如顶点之间的距离、花费等ABCD246254abcd贪心算法贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。TSP问题，在下图中，现要从济南出发，依次旅行完每一个城市，且每个城市只去一次，最后回到济南，用贪心算法，应按何种顺序旅游？最短路程是多少？图的应用数据管理技术(1)人工管理阶段约20世纪50年代中期之前数据管理（DataManagement）:对数据进行高效地组织、编目、分类、定位、排序、存储、检索和维护等。(2)文件系统阶段在20世纪50年代后期到60年代中期(3)数据库系统阶段

20世纪60年代后期以来数据库数据库(DB):DataBase数据库管理员(DBA):DataBaseAdministrator数据库管理系统(DBMS):DataBbaseManagementSystem数据库应用(DBAP):DataBaseApplication数据库管理系统（DBMS)的基本功能

a、数据库定义：定义数据库中数据表的名称、标题等。

b、数据库操作:向数据库的Table中增加/删除/更新数据及对数据进行查询、检索、统计等。c、数据库管理控制:控制数据库中数据的使用---哪些用户可以使用,哪些不可以。常见的数据库管理系统有:AccessSQLServerOracleMySQLFoxProSybase……数据模型数据库常见的数据模型:层次模型：以树的形式组织数据网状模型：以图/网的形式组织数据关系模型：以二维表格的形式组织数据面向对象模型：采用面向对象的方法来设计数据库其中关系模型是目前最常见的数据模型。数据模型是描述数据库数据结构的模式，是对客观事物及其联系的抽象化描述。集合运算RABCa12c32d32TABCb22c32d32(1)并R∪TABCa12b22c32d32(2)交R∩TABCc32d32集合运算RABCa12c32d32TABCb22c32d32(3)差R-TABCa12T-RABCb22集合运算RABCa12c32d32TABCb22c32d32(4)广义笛卡尔积a12a12a12b22c32d32R×TR.AR.BR.CT.AT.BT.Cc32c32c32b22c32d32d32d32d32b22c32d32选择(Selection)SnoSname95001李勇SsexSageSdept男20计算机95002刘琛女19计算机95003王敏女18信息95004章立男19机械Student查询计算机系全体学生：查询计算机系女同学：投影(Projection)SnoSname95001李勇SsexSageSdept男20计算机95002刘琛女19计算机95003王敏女18信息95004章立男19机械StudentSname李勇Sdept计算机刘琛计算机王敏信息章立机械b.查询学生所在系：Sdept计算机信息机械查询学生姓名和所在系：投影之后不仅取消了原关系中的某些列，而且还可能取消某些元组（避免重复行）计算机问题求解过程利用计算机求解问题是问题求解手段的改变，计算机求解问题的过程与人的计算过程不同。计算机问题求解过程包括数学建模、算法设计、程序设计，最后运行程序才能得到问题的解。数学建模算法设计程序设计问题的解问题分析运行程序问题数学建模：将问题抽象为一个数学问题，并给出求解该数学问题的数学模型。问题求解的第一步就是要数学建模百钱百鸡问题、哥尼斯堡七桥问题、汉诺塔问题、TSP问题、阿基米德分牛问题等通过问题分析抽象或引入数学变量从而将一个具体问题的求解推广为一类问题的求解。首要的和关键的一步就是建立研究对象的数学模型，然后才能借助计算机求解。第五章算法设计算法设计包括算法策略设计、数据结构设计和控制结构设计。(1)算法策略设计算法是解决问题的方法和步骤，算法设计即设计解决问题的算法策略。TSP问题的算法策略设计：

遍历算法：出现的问题是：

组合爆炸！对于n个城市路径组合数目：(n-1)!

贪心算法：则可以在局部最优的基础上找出可行路径，但不一定是全局最优解。(2)数据结构设计算法的数据结构设计是指与问题或算法相关的数据之间的逻辑关系及存储关系的设计，即如何来组织数据，才能更高效的解决问题。TSP问题：城市映射为编号:A--1,B--2,C--3,D--4城市间距离关系:矩阵或二维数组D，用D[i][j]或D[i,j]来城市间的距离

访问路径/解:

一维数组S，用S[j]来按顺序存放到过的城市(3)控制结构设计算法的控制结构设计即设计算法的计算步骤或计算规则，即如何构造和表达处理的规则，以便能够按规则逐步计算出结果。控制结构分为三种：①顺序结构：即按书写的顺序从上到下、从左到右执行。假设a=5，b=10，如要交换a、b的值，则需按顺序执行语句：

temp=a;a=b;b=temp;②分支（选择）结构：根据条件，成立时执行某些操作，不成立则执行另一些操作，或者从多个分支中选择一个来执行。③循环结构：根据条件，成立则重复执行某些操作，不成立时则不再循环。sum=0;for(i=1;i<=n;i++)sum=sum+i;printf("%d",sum);程序设计程序设计是根据选定的算法策略和数据结构、控制结构设计结果，给出解决特定问题程序的过程。程序设计往往以某种计算机程序设计语言为工具，如C语言、C++语言、Java语言等，写出这种语言下的程序。从发展历程来看，程序设计语言一般分为机器语言、汇编语言和高级语言。

高级语言程序的通用性和可移植性大为提高。但高级语言所编制的程序不能直接被计算机识别，必须经过翻译才能被执行，按照翻译方式的不同，可将它们分为解释和编译两类程序设计过程应当包括分析、设计、编码、测试、排错等不同阶段。最后，运行程序，即可得到问题的解。

算法算法（Algorithm）是指解决问题的方案的准确而完整的描述，是一系列解决问题的清晰指令的计算序列。算法具有的５个重要特征：有穷性、确定性、0个或多个输入、一个或多个输出、可行性。

算法描述：自然语言、流程图、N-S流程图、伪代码，掌握任意一种。算法的评价和分析算法设计首先要保证算法正确性。只有在算法正确的前提下，讨论算法的优劣才有意义。首先：要对算法进行正确性分析，这个算法是正确的吗？算法的输出是问题的解吗？其次：算法的复杂性分析。最常见的是时间复杂度分析和空间复杂度分析。求的值，即表达式1+2+3+…+n的值。n为正整数，由键盘输入。算法描述自然语言描述的算法如下：Step1：从键盘输入正整数nStep2：设表达式的值用s表示，且s初始化为0，即s←0Step3：设变量i的初值为1，即i←1Step4：把i累加到s中，即s←s+iStep5：i的值增1，即i←i+1Step6：如果i<=n，则转Step4；否则转Step7Step7：输出s的值Step8：结束开始输入ns=0i=1i<=n?s=s+1i=i+1输出s结束NY开始输入nsum=0i=1i<=n?sum=sum+ii=i+1输出sum结束伪代码描述：begininputns=0i=1whilei<=ndobegins←s+ii←i+1endoutputsendN-S流程图描述流程图描述分析下列程序段的时间复杂度。temp=a;a=b;b=temp;上面3个语句均为赋值语句，都是元操作，执行频度均为1，因此该段代码的执行时间是与问题规模n无关的常数，即算法的时间复杂度为常数阶，记作T(n)=O(1)。同理，如果算法中仅仅是执行了若干条基本操作语句，即使有成千上万条语句，执行时间也不过是一个较大的常数，也不会随着问题规模n的增加而有所增加，因此这类算法的时间复杂度都是O(1)，称为常量阶。分析下列程序段的时间复杂度。s=0;i=1;for(i=1;i<=n;i++)s=s+i;分析该算法，各行执行的次数分别为1、1、n、n，因此时间复杂度为：T(n)=2n+2=O(n)，称为线性阶。

经典问题的算法求解穷举法：银行密码：n位0～9之间的任何数字，密码有10n种可能。

0-1背包问题：如果有n件物品，所有可能解的情况则有：

要用一个n位二进制计数器，来表示n件物品放入背包的情况。

TSP旅行商问题：实际上就是路径的遍历，出现的问题是：

组合爆炸！对于n个城市路径组合数目：(n-1)!贪心算法：0-1背包问题，为了使包内物品的总价值最大，先计算出所有物品的单位价值，然后从单位价值由高到低的顺序依次选择物品放入背包，在不超过背包限重的情况下尽可能放更多的物品

TSP旅行商问题：依据贪心算法思想，每次在选择下一个城市

的时候，只考虑当前情况，保证迄今为止所经过的总路程最短。

经典问题的算法求解递推法：菲波那切数列

走楼梯：有一段楼梯有N级台阶，规定每一步只能跨一级或两级，要登上第N级台阶有几种不同的走法,台阶走法：f(1)=1f(2)=2f(N)=f(N-1)+f(N-2)

兔子繁殖：1-12月份：幼兔：f(1)=0f(2)=1f(n)=f(n-1)+f(n-2)1-12月份：成兔：f(1)=1f(2)=1f(n)=f(n-1)+f(n-2)

1-12月份：总兔：f(1)=1f(2)=2f(n)=f(n-1)+f(n-2)

递归法：菲波那切数列、自然数的定义自然数n的阶乘定义：

汉诺塔的求解：对于n个金片，移动的次数是2n-1查找所谓查找，也称为搜索，是指从若干个对象中，找出想要的对象。顺序查找：就是在查找范围内，将给定值按顺序逐个与查找对象进行比较，相等即为查找成功，如果全部比较完还没有相等的则查找失败。

查找成功的平均长度为：ASL=折半查找：（二分查找）线性表中的记录是按照关键字有序的（升序或降序）排列。查找成功的平均长度为：ASL=

算法：首先选取表的中间元素，设序号为mid=(1+n)/2，元素Rmid将数据表分成大致相等的两部分{R1,R2,…,Rmid-1}和{Rmid+1,Rmid+2,…,Rn}。先对Rmid和key作比较，假设序列升序有序，则比较结果有三种情况：首先，将表中间位置元素值与查找数据比较：key=Rmid：查找成功，返回元素序号mid。key<Rmid：折半查找前一子表{R1,R2,…,Rmid-1}。key>Rmid：折半查找后一子表{Rmid+1,Rmid+2,…,Rn}。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。折半查找算法演示：数据表（查找key=8）K1K2K3K4K5K6K7K8K9K10368121622304558633681216223045586336812162230455863结论：比较3次终于找到。问题：有哪些数需要比较1次、2次、3次或4次才能找到？16645382258123063排序：排序是对一组对象按照某种规则进行有序排列，通常是把一组对象整理成按关键字递增(或递减)的排列，关键字是指对象的一个用于排序的特性。选择排序：首先在所有数据（保存于数组中）中找出最小值，放在第一个数组元素中；接着在不包含第一个数组元素的余下的数组元素中再找出最小值的元素，放置在第二个数组元素中；如此下去，一直到最后一个元素。冒泡