下载文档原格式
第三章 蛮力法1.选择排序SelectionSort(A[0..n-1])for i=0 to n-2 domin=ifor j=i+1 to n-1 doif A[j]<A[min]min=jswap A[i] and A[min]2.冒泡排序BubbleSort(A[0..n-1])// 输入：数组A，数组中的元素属于某偏序集// 输出：按升序排列的数组Afor i=0 to n-2 dofor j=0 to n-2-i doif A[j+1]<A[j] swap A[j] and A[j+1]3.改进的冒泡算法ALGORITHM BubbleSortImproved( A[0,…,n –1] )// 冒泡排序算法的改进// 输入：数组A，数组中的元素属于某偏序集// 输出：按升序排列的数组Afor i ← 0 to n – 2 doflag ← Truefor j ← 0 to n – 2 – i doif A[j+1] < A[j]swap(A[j], A[j+1])flag ← False// 如果在某一轮的比较中没有交换，则flag为True，算法结束returnif flag = True4. 顺序查找算法算法 SwquentialSearch2(A[0...n],k)//顺序查找算法的实现，它用了查找键来作限位器//输入：一个n个元素的数组A和一个查找键K//输出：第一个值等于K的元素的位置，如果找不到这样的元素就返回 -1A[n]<--ki<--0while A[i]!=K doi<--i+1if i<n return iElse return -15. 蛮力字符串匹配算法 BruteForceStringMatch(T[0...n-1],P[0...m-1])//该算法实现了蛮力字符串匹配代表一段文本//输入：一个n个字符的数组T[0...n-1]// 一个m个字符的数组P[0..m-1]代表一个模式//输出：如果查找成功的话，返回文本的第一个匹配字串中第一个字符的位置， // 否则返回-1For i<--0 to n-m doj<--0While j<m and P[j]=T[i+j]doj<--i+1If j=m return ireturn -1合并排序最差Θ(nlog2n)快速排序最优Θ(nlog2n)最差Θ(n2)平均Θ(1.38nlog2n)选择排序 Θ(n2)冒泡排序 Θ(n2)插入排序最差Θ(n2)最优 Θ(n)平均 Θ(n2)第四章 分治法合并排序算法 MergeSort(A[0..n-1] )排序 // 递归调用mergesort来对数组 A[0...n-1]// 输入：一个可排序数组A[0..n-1]// 输出：非降序排列的数组A[0..n-1]if n > 1n/2 -1]copy A[0.. n/2 -1] to B[0..n/2 -1]copy A[ n/2 ..n-1] to C[0..MergeSort( B )MergeSort( C )Merge( B,C,A )两个数组合并的算法算法 Merge(B[0..p-1],C[0..q-1],A[0..p+q-1])//将两个有序数组合并成一个有序的数组和C[0...q-1]//输入：两个有序数组B[0...p-1]//输出：A[0..p+q-1]中已经有序存放了B和C中的元素 i=0,j=0,k=0;while i<p and j<q do≤C[j]if B[i]A[k]=B[i], i=i+1elseA[k]=C[j], j=j+1k=k+1if i=pcopy C[j..q-1] to A[k..p+q-1]elsecopy B[i..p-1] to A[0..p+q-1]快速排序算法QuickSort(A[l..r])// 使用快速排序法对序列或者子序列排序或者序列本身A[0..n-1]// 输入：子序列A[l..r]// 输出：非递减序列Aif l < rs ← Partition( A[l..r] )QuickSort( A[l..s-1] )QuickSort( A[s+1..r] )//s是中轴元素/基准点，是数组分区位置的标志实现分区的算法Partition( A[l..r] )// 输入：子数组A[l..r]// 输出：分裂点/基准点pivot的位置p ← A[l]i ← l; j ← r+1repeat≥ prepeat i ←i + 1until A[i]≤ prepeat j ← j – 1 until A[j]swap( A[i], A[j] )≥ juntil iswap( A[i], A[j] )swap( A[l], A[j] )return j折半查找BinarySearch( A[0..n-1], k )// 输入：已排序大小为n的序列A，待搜索对象k// 输出：如果搜索成功，则返回k的位置，否则返回-1 l=0,r=n-1;While l≤rmid= (l+r)/2if k = A[mid] return midelse if k < A[mid] r=m-1else l=m+1return -1Strassen矩阵Strassen方法M1=A11(B12-B22)M2=(A11+A12)B22M3=(A21+A22)B11M4=A22(B21-B11)M5=(A11+A22)(B11+B22)M6=(A12-A22)(B21+B22)M7=(A11-A21)(B11+B12)第五章 减治法插入排序ALGORITHM InsertionSort( A[0..n-1] )// 对给定序列进行直接插入排序// 输入：大小为n的无序序列A// 输出：按非递减排列的序列Afor i ← 1 to n-1 dotemp ← A[i]j ← i-1while j ≥ 0 and A[j] > temp doA[j+1] ← A[j]j ← j –1A[j+1] ←temp深度优先查找算法 BFS（G）//实现给定图的深度优先查找遍历//输入：图G=<V,E>//输出：图G的顶点，按照被DFS遍历第一次访问到的先后次序，用连续的整数标记，将V中的每个顶点标记为0，表示还“未访问”count =0//记录这是第几个访问的节点标记为 unvisitedmark each vertex with 0//∈ V dofor each vertex vif v is marked with 0dfs(v)dfs(v)//递归访问所有和v相连接的未访问顶点，然后按照全局变量count的值//根据遇到它们的先后顺序，给它们附上相应的数字count = count + 1mark v with countv dofor each vertexw adjacent toif w is marked with 0dfs(w)广度优先BFS(G)/实现给定图的深度优先查找遍历//输入：图G=<V,E>//输出：图G的顶点，按照被BFS遍历第一次访问到的先后次序，用连续的整数标记，将V中的每个顶点标记为0，表示还“未访问”count =0mark each vertex with 0for each vertex v∈ V dobfs(v)bfs(v)//递归访问所有和v相连接的未访问顶点，然后按照全局变量count的值//根据遇到它们的先后顺序，给它们附上相应的数字count = count + 1mark v with countinitialize queue with vwhile queue is not empty doa = front of queuefor each vertex w adjacent to a doif w is marked with 0count = count + 1mark w with countadd w to the end of the queueremove a from the front of the queue拓扑排序第六章 变治法Gauss消去法GaussElimination(A[1..n], b[1..n])// 输入：系数矩阵A及常数项 b// 输出：方程组的增广矩阵等价的上三角矩阵for i=1 to n doA[i][n+1] =b[i]for j= i+1 to n dofor k = i to n+1 do– A[i][k]*A[j][i]/A[i][i]A[j][k] = A[j][k]堆排序堆排序主要包括两个步骤：对于给定的数组构造相应的堆。
第一套7．关于算法，下列叙述正确的是（A）算法可以用自然语言、流程图和伪代码来描述（B）算法只能用流程图来描述（C）算法不能用伪代码来描述（D）算法不可以用自然语言来描述8．依照中华人民共和国《机动车驾驶员驾车时血液中酒精含量规定》，血液中酒精含量大于或等于0.3mg/ml 驾驶机动车的属“酒后”驾车；大于或等于1.0mg/ml 驾驶机动车的属“醉酒”驾车。
如果要根据血液中的酒精含量确定属于“酒后”驾车还是“醉酒”驾车，用算法描述这一过程，合适的算法结构是（A）顺序模式（B）选择模式（C）循环模式（D）树型模式9．下列属于Visual Basic 字符串常量的是（A）1/2 （B）Int(3.4) （C）"1/2" （D）1+210．在Visual Basic 中，将数字字串转换为数值的函数是（A）Str(x) （B）Val(x) （C）Abs(x) （D）Int(x) 11．在Visual Basic 工程设计中，双击窗体中的对象后，出现的是（A）工程窗口（B）工具箱（C）代码窗口（D）属性窗口12. 下列属于正确的Visual Basic 赋值语句的是（A）x+y=10 （B）x+y-10=0 （C）x,y=10 （D）x=10-y 13. 圆周长的计算公式为L=2πa，其中a为圆半径。
在Visual Basic 中，能正确表示2πa 的表达式是（A）2πa （B）2*π*a （C）2·π·a （D）2*3.1416*a 14．在Visual Basic 中，若x=3.1415926，则表达式Int(x*100+0.5)/100 的值是（A） 3.14 （B）3.146 （C）314 （D）314.6第二套4. 如果一个三位正整数等于它的每个数字的立方和，则此数称为“水仙花”数(如：153＝１^３＋５^３＋３^３)。
下列算法用于求出三位正整数中的所有“水仙花”数:①将100 赋值给变量i；②判断i 是否是“水仙花”数，若是，输出该数；③将变量i加1，若i 还小于或等于999，转②，否则转④；④结束。
选择排序法伪代码及解释
选择排序法的伪代码如下所示：
SelectionSort(A)。
n = length(A)。
for i from 0 to n-1。
minIndex = i.
for j from i+1 to n.
if A[j] < A[minIndex]
minIndex = j.
swap A[i] with A[minIndex]
这段伪代码描述了选择排序的算法过程。
首先，我们遍历整个
数组，从第一个元素开始，将其标记为最小值的索引。
然后，我们
将这个最小值的索引与后续元素进行比较，如果找到比当前最小值
更小的元素，就更新最小值的索引。
最后，我们将当前位置的元素
与最小值所在位置的元素进行交换。
这样，经过一轮遍历，我们就
能将数组中最小的元素放到正确的位置上。
然后，我们继续对剩余
的未排序部分重复这个过程，直到整个数组有序。
选择排序的时间复杂度为O(n^2)，因为它涉及两层嵌套的循环。
虽然选择排序在实际应用中效率较低，但它的实现相对简单直观。
算法设计与分析各种查找算法的性能测试目录摘要 (2)第一章：简介（Introduction） (3)1.1 算法背景 (3)第二章：算法定义（Algorithm Specification） (4)2.1 数据结构 (4)2.2顺序查找法的伪代码 (4)2.3 二分查找（递归）法的伪代码 (5)2.4 二分查找（非递归）法的伪代码 (6)第三章：测试结果（Testing Results） (8)3.1 测试案例表 (8)3.2 散点图 (9)第四章：分析和讨论 (11)4.1 顺序查找 (11)4.1.1 基本原理 (11)4.2.2 时间复杂度分析 (11)4.2.3优缺点 (11)4.2.4该进的方法 (12)4.2 二分查找（递归与非递归） (12)4.2.1 基本原理 (12)4.2.2 时间复杂度分析 (13)4.2.3优缺点 (13)4.2.4 改进的方法 (13)附录：源代码（基于C语言的） (15)摘要在计算机许多应用领域中，查找操作都是十分重要的研究技术。
查找效率的好坏直接影响应用软件的性能，而查找算法又分静态查找和动态查找。
我们设置待查找表的元素为整数，用不同的测试数据做测试比较，长度取固定的三种，对象由随机数生成，无需人工干预来选择或者输入数据。
比较的指标为关键字的查找次数。
经过比较可以看到，当规模不断增加时，各种算法之间的差别是很大的。
这三种查找方法中，顺序查找是一次从序列开始从头到尾逐个检查，是最简单的查找方法，但比较次数最多，虽说二分查找的效率比顺序查找高，但二分查找只适用于有序表，且限于顺序存储结构。
关键字：顺序查找、二分查找（递归与非递归）第一章：简介（Introduction）1.1 算法背景查找问题就是在给定的集合（或者是多重集，它允许多个元素具有相同的值）中找寻一个给定的值，我们称之为查找键。
对于查找问题来说，没有一种算法在任何情况下是都是最优的。
有些算法速度比其他算法快，但是需要较多的存储空间；有些算法速度非常快，但仅适用于有序数组。
2020年信息技术学考算法与程序设计试题整理及解析2020年信息技术学考算法与程序设计试题整理及解析⼀、选择题（每题3分）1.下列选项中，不属于计算机程序设计语⾔的是( C )A.汇编语⾔B.⾼级语⾔C.⾃然语⾔D.机器语⾔解析：计算机程序设计语⾔的种类⾮常的多，总的来说可以分成机器语⾔，汇编语⾔，⾼级语⾔三⼤类。
2. 关于算法的描述，下列选项中正确的是( B )A.算法本⾝就是⼀种程序设计语⾔B.算法的每⼀步骤必须有确切的含义C.算法的步骤可以是⽆穷的D.算法必须有输⼊解析：算法是指解决问题的⽅法和步骤，⼀个算法应该具有以下五个重要的特征:1.有穷性(Finiteness):是指算法必须能在执⾏有限个步骤之后终⽌。
2.确切性(Definiteness):算法的每⼀步骤必须有确切的定义。
3.输⼊项(Input):⼀个算法有0个或多个输⼊,以刻画运算对象的初始情况,所谓0个输⼊是指算法本⾝定出了初始条件。
4.输出项(Output):⼀个算法有⼀个或多个输出,以反映对输⼊数据加⼯后的结果。
没有输出的算法是毫⽆意义的。
5.可⾏性(Effectiveness):算法中执⾏的任何计算步骤都是可以被分解为基本的可执⾏的操作步骤，即每个计算步骤都可以在有限时间内完成（也称之为有效性）。
3. VB程序中“dim n As Integer”这条语句的作⽤是( A )A.定义⼀个变量B.定义⼀个数据输⼊⽅法C.定义⼀个事件过程D.定义⼀个数据处理⽅法解析：Dim 是VB中声明变量并分配存储空间的语句。
格式：Dim 变量名 as 数据类型Integer：变量存储为 16位（2 个字节）的数值形式。
string：变长与定长的字符串。
Boolean：存储为 16 位（2 个字节）的数值形式，但只能是 True 或是 False。
Double：（双精度浮点型）变量存储为 IEEE 64 位（8 个字节）浮点数值的形式。
Long：（长整型）变量存储为 32 位（4 个字节）有符号的数值形式等等。
实现顺序查找和折半查找的算法顺序查找和折半查找（也称为二分查找）是两种常见的查找算法。
以下是它们的Python实现：1. 顺序查找：```pythondef sequential_search(list, item):pos = 0found = Falsewhile pos < len(list) and not found:if list[pos] == item:found = Trueelse:pos = pos+1return found```这个函数会检查列表中的每个元素，直到找到匹配的元素或者遍历完整个列表。
如果找到匹配的元素，函数会返回True，否则返回False。
2. 折半查找：```pythondef binary_search(list, item):low = 0high = len(list) - 1mid = 0found = Falsewhile low <= high and not found:mid = (high + low) // 2if list[mid] == item:found = Trueelif list[mid] < item:low = mid + 1else:high = mid - 1return found```这个函数使用二分查找算法，每次比较列表中间的元素和目标元素。
如果中间元素等于目标元素，函数返回True。
如果中间元素小于目标元素，函数在列表的右半部分继续查找。
如果中间元素大于目标元素，函数在列表的左半部分继续查找。
如果函数遍历完整个列表都没有找到目标元素，那么返回False。
几种排序算法的伪代码.doc
一、冒泡排序
伪代码：
（1）设置一个标记flag，用于判断是否发生了数据的交换，初始设置为TRUE
（2）重复以下操作：
A、从第0个位置开始，比较相邻的数据；若第0个数据比第1个数据大，则将它们交换，否则直接跳过；然后，从第1个位置开始，比较相邻的数据；若第1个数据比第2个数据大，则将它们交换，否则直接跳过……
B、若这次循环发生了交换（若发生交换，flag将变为TRUE），则重复上面提到的A 步；若此次循环没有发生交换（若没有发生交换，flag将变为FALSE），则结束此次循环
（3）结束时若flag为FALSE，表明已排序完毕
（1）首先，找到数组的中心点元素作为对比元素
（2）从数组的头部开始遍历，当遇到比中心点元素小的元素时，将其加入其后面一个指针位置，由此序列小于中心点元素的序列将被形成
（4）数组以序列小于中心点元素和大于中心点元素两个序列分割，重复（1）、（2）、（3）步骤，直至数组的末尾
（5）排序完成
（1）从第0个位置开始，将第1个元素赋值给暂存变量
（2）比较暂存变量与第0个元素，若暂存变量比第0个元素小，则将暂存变量插入到第0个位置，此过程结束；否则，将第0个元素整体后移一位，并将暂存变量插入到第0个位置，此过程结束
（3）重复以上过程，直至最后一个元素完成排序。
一、实验目的1. 理解嵌入式系统中的算法原理和应用场景。
2. 掌握常用嵌入式算法的设计方法和实现技巧。
3. 分析嵌入式算法的性能和优化方法。
4. 培养解决实际问题的能力。
二、实验内容1. 实验背景随着嵌入式系统在各个领域的广泛应用，算法在嵌入式系统中的地位日益重要。
本实验选取了几个典型的嵌入式算法，包括排序算法、查找算法、字符串处理算法等，对它们进行设计、实现和分析。
2. 实验环境操作系统：Linux编程语言：C/C++开发环境：Eclipse编译器：GCC3. 实验步骤（1）排序算法1）选择合适的排序算法：本实验选择了冒泡排序、选择排序和插入排序三种算法。
2）设计算法的伪代码：根据算法原理，分别编写冒泡排序、选择排序和插入排序的伪代码。
3）实现算法：使用C/C++语言将伪代码转换为可执行的程序。
4）测试算法：编写测试用例，对算法进行测试，比较它们的执行效率和稳定性。
（2）查找算法1）选择合适的查找算法：本实验选择了顺序查找、二分查找和散列表查找三种算法。
2）设计算法的伪代码：根据算法原理，分别编写顺序查找、二分查找和散列表查找的伪代码。
3）实现算法：使用C/C++语言将伪代码转换为可执行的程序。
4）测试算法：编写测试用例，对算法进行测试，比较它们的执行效率和稳定性。
（3）字符串处理算法1）选择合适的字符串处理算法：本实验选择了字符串比较、字符串复制和字符串查找三种算法。
2）设计算法的伪代码：根据算法原理，分别编写字符串比较、字符串复制和字符串查找的伪代码。
3）实现算法：使用C/C++语言将伪代码转换为可执行的程序。
4）测试算法：编写测试用例，对算法进行测试，比较它们的执行效率和稳定性。
三、实验结果与分析1. 排序算法（1）冒泡排序：执行效率较低，稳定性较好。
（2）选择排序：执行效率较低，稳定性较差。
（3）插入排序：执行效率中等，稳定性较好。
2. 查找算法（1）顺序查找：执行效率较低，适用于数据量较小的场景。
