文档库 最新最全的文档下载
当前位置:文档库 › 浅谈程序设计中的高效算法

浅谈程序设计中的高效算法

浅谈程序设计中的高效算法
浅谈程序设计中的高效算法

序言

C语言以其功能丰富、表达能力强、使用灵活方便、目标程序效率高、可移植性好、应用面广等优点而成为近年在国内外得到迅速推广的计算机程序设计语言,它不仅成为目前国内高校普遍开设的程序设计语言之一,还成为中国计算机软件专业技术资格和水平考试的内容,以及计算机等级考试的首选语言。

但是,C语言与其他程序设计语言相比较,由于牵涉的概念复杂,规则繁多,语句不是很严谨,故在理解C语言时容易出现偏差;加上目前各高校在C语言程序设计课程教学模式上仍采用传统的教学方法,过于注重语句、语法和一些细节的讲解,基本上以程序语言自身的体系为脉络展开教学,却忽略了高级语言的精髓——算法设计的介绍,从而令初学者感到困惑,感到枯燥难学,碰到实际问题时,往往束手无策。笔者经过多年C语言课程的教学研究和实践,试从算法设计的概念入手,谈谈一个良好的算法对程序设计和程序执行效率所起到的事半功倍的效果。

一、绪论

(一)程序设计中的高效算法的目的和意义

从算法设计的概念入手,结合实例,对算法的设计与程序的编写进行了初步探讨,指出算法设计在C语言程序设计中的重要作用。程序中一种高效的算法可以大大提高运算速度,编码编写少,执行效率高。了解算法和程序设计在解决问题过程中的地位和作用;能从简单问题出发,设计解决问题的算法,并能初步使用一种程序设计语言编制程序实现算法、解决问题。

算法是程序的灵魂,算法的好坏直接决定整个程序的运行时间和运行结果的精确度。在实际应用中,绝大多数问题都没有现成的求解方法,需要我们自己去探索,从计算机角度去思考算法。寻求算法的过程就是一个发现、发明和创新的思维过程,这就是C语言及其他高级语言设计教学的重点和难点。

(二)选题背景

自20世纪40年代带内存程序的计算机诞生后,计算机编写程序的工作越来越重要。到60年代中期,计算机应用已相当普遍,但软件设计技术却很落后,许多大型软件的质量低劣,可靠性不高,可维护性极差;软件生产率很低,从而价格昂贵,供不应求,造成所谓的

软件危机。计算机科学家开始认真研究程序设计的基本理论和方法。

以前的操作系统等系统软件主要是由汇编语言编写的(包括Unix操作系统在内)。由于汇编语言依赖于计算机硬件,程序的可读性和可移植性都比较差。为了提高可读性和可移植性,最好改用高级语言,但一般高级语言难以实现汇编语言的某些功能(汇编语言可以直接对硬件进行操作,例如,对内存地址的操作、位操作等)。人们设想能否找到一种既具有一般高级语言特性,又具有低级语言特性的语言,集它们的优点于一身。

(三)程序设计中高效算法的技术线路

技术路线是指从技术的角度完成论文所采取的路线,先介绍分析程序设计,然后通过C 语言程序简单介绍程序设计中的的简单算法等。

二、实现冒泡排序算法的一种新方法

(一)概述

排序是数据处理中经常使用的一种运算,冒泡排序是众多排序方法中的一种。冒泡排序又称起泡排序。其基本思想是通过若干趟相邻元素之间的比较、交换,最终使所有元素按某关键字有序(升序或降序)进行排序。其中,每趟都是在相邻元素间进行关键字的比较和元素的交换。

(二)实现冒泡排序的传统算法

冒泡排序算法的实现需两重循环,通常采用以下方法:外层循环控制变量(设为 i)的变化是从数据比较的趟数考虑的。如:设有n个数据参加排序,需n - 1趟比较,i 的变化范围是1 →n – 1;而其内层循环控制变量(设为j)的变化范围为0 →n - i - 1 (C语言中数组元素下标从 0 开始) 。具体算法描述如下(设排为升序) :

void bpsort (node a[ ] ,int n) // node 为元素虚拟类型 ,可根据需要定义为具体类型

{ node t ;

int i ,j ;

for (i = 1 ; i < = n - 1 ; i + + )

for (j = 0 ; j < = n - i - 1 ; j + + )

if (a[ j ] .key > a[ j + 1 ] .key)

{t = a[ j ] ; a[ j ] = a[ j + 1 ] ; a[ j + 1 ] = t ; } }

(三)实现冒泡排序的新方法

在此介绍一种冒泡排序的新的实现方法 ,其循环控制变量的变化范围是从另一角度考虑的,即每趟比较结束后被确定了最终数据的位置 (指数组元素下标) 。如:有 n 个数据参加冒泡排序,第一趟从第 0个元素到第 n - 1个元素依次进行相邻数据间关键字的比较,若逆序,则进行两元素值的交换,该趟比较结束后,下标为 n - 1的元素有了最终确定的数据;第二趟从第0个元素到第 n - 2个元素依次进行相邻元素间比较,若逆序,则交换两元素值;该趟结束后,下标为 n - 2的元素有了最终确定的数据;依次类推,最后一趟的比较只发生在第0个元素和第1 个元素间,最终第 1 个元素有了确定的数据后,排序过程完成;即i 的变化范围是 n - 1 → 1。而其内层循环控制变量 j 的变化范围是每趟参加比较的元素的下标变化范围 ,每趟比较都是从第0个元素开始,到当前仍未确定数据的最后一个位置的元素,即第 i 个元素,所以j 的变化范围是0 → i - 1。以升序为例写出参考程序(流程图见图1) :

v oid bps ort1 (node a[ ] ,int n) /* node 泛指元素类型 */

{ node t ;

int i ,j ;

for (i = n - 1 ;i > = 1 ;i - - )

for (j = 0 ;j < = i - 1 ;j + + )

if (a[ j ] . key > a[ j + 1 ] . key)

{ t = a[ j ] ; a[ j ] = a[ j + 1 ] ; a[ j + 1 ] = t ; } }

相应于传统的冒泡排序的改进算法,同样有一种改进的冒泡排序算法的新的实现方法 ,即当某趟循环中无交换 ,则表示已排好序。参考程序如下(流程图见图2) :

图1 冒泡排序算法传统流程图图2 冒泡排序算法改进流程图void bpsort2 (node a[ ] ,int n)

{node t ;

int i ,j ,flag ;

flag = 1 ;

for (i = n - 1 ;i > = 1&&flag ; i - - )

{flag = 0 ;

for (j = 0 ;j < = i - 1 ;j + + )

if (a[ j ] . key > a[ j + 1 ] . key)

{t = a[ j ] ;

a[ j ] = a[ j + 1 ] ;

a[ j + 1 ] = t ;

flag = 1 ;

}

}

}

以上改进算法虽较上一算法新增一变量flag ,但仍保持了结构化的设计 ,且较上一算法效率高。

(四)结束语

对多数问题而言 ,解决的方法不止一种。同样为某一问题编写程序可能有多种思路 ,而判断一个程序优劣的标准大致有三个:正确、 易读、 高效。在作者多年的教学中发现 ,用新介绍的冒泡排序算法(用数据位置控制外层循环)讲解 ,学生更易理解冒泡排序的实现。以上介绍的只是众多算法中的一种 ,相信随着计算机及相关学科的不断发展 ,会有许多更优化的算法出现。

三、冒泡排序法的变异——交替排序法

(一)排序算法的描述

计算机对数据的排序方法有很多种,在实际运用中发现了一种新的排序方法,暂时命名

为交替排序法。假设有n 个无序数据,分别为

排序的具体过程如下描述: 第一步:将数据交换标志P 置0。将

与 、 与 ……两两进行比较,如果前者大于后者,则交换,同时将P 置1。

第二步:将 与 、 与 ……两两进行比较,如果前者大于后者,则交换,同时将P 置1。

第三步:如果P 等于0则停止,排序完成,否则返回第一步继续进行排序过程。 第四步:按序输入 ~ 。

(二)交替排序算法的流程图

12......n A A A 1A 2A 3A 4A 1A n A 2A 3A 4

A 5A

交替排序算法的流程图如图3所示:

图3 交替排序算法流程图(三)交替算法的C语言源程序

#define N 10

main()

{ int a[N],c,m,p=1,t;

for(m=0;m<=N-1;m++)

{ printf("a[%d]=",m);

scanf("%d",&a[m]);

}

while(p==1)

{ p=0;

for(c=0;c<=1;c++)

for(m=c;m+1<=N-1;m=m+2)

if(a[m]>a[m+1])

{ t=a[m];

a[m]=a[m+1];

a[m+1]=t;p=1;

}

}

for(m=0;m<=N-1;m++)

printf("%d\n",a[m]);

}

(四)交替排序算法的复杂度

经过计算,交替排序算法的时间复杂度与冒泡排序算法处于同一个数量级上。交替排序算法的空间复杂度略小于冒泡算法的空间复杂度。经过实际数据的测试,交替算法的效率略高于冒泡算法。

四、一种改进的冒泡排序算法

(一)排序算法概况及其使用场合

目前,最常见的排序算法有:冒泡排序法,选择排序法,快速排序法,冒泡排序法是一种简单的排序算法,由于性能很差,只有在待排数据量很小的时候才会选用它。选择排序法的性能有很大的提高,但当待排数据量很大的时候,它也不能胜任。据我所知,快速排序法在所有的排序算法之中,效率最高,在对大数据量进行排序时常采用它。本文推出一种效率更高的改进的冒泡排序算法。

(二)一种改进的冒泡排序算法的思想

传统的冒泡排序算法需要元素之间一次次相互比较,这是影响排序速度的一个主要原因。随着待排元素个数的增加,比较次数几乎呈几何级数增长,而这种改进后的冒泡排序算法在大多数情况下,会减少待排数据之间的重复比较,只要增加一个标识变量,如果在某次比较过程中,标识变量未发生变化,则可证明数据已经有序,不必再进行比较,这样

就大大提高了效率。下面是改进的冒泡排序的实验过程。

设待排序数组为一维数组A,其元素个数为NUM。

创建一个标识变量 flag,初始化 flag=0 。

排序开始:( 1 )将数组 A 中的相邻元素进行大小比较,若顺序不对,则进行交换,并将标识变量 flag 置 1,继续比较。( 2 )若在某次循环结束后, flag 为 0,则证明该数组已经排好序,不必再比较,循环结束。

(三)示例源程序

#include

#define NUM 1000000

void bubble(int item[ ]int n);

main()

{int a[NUM]; //数组A

int i;

for (i = 1;i

{

printf(“请输入数组元素a[%d]的值:\n”,i);

scanf(“%d”,&a[i];) //初始化数组A

bubble(a,NUM);

for (i = 1;i

printf(“%d”,a[i]);

}

void bubble (int item [ ]int n)

{

int i,j,temp,flag;

int b[NUM]; //存放每次排序的内循环次数

int p; //存放外循环次数

flag = 0; p = 0;

for(i=1;i

b[i] = 0;

for(i=1;i

{

flag = 0;

for(j = 1;i

{

if(item[j]>item[j]+1)

{

temp = item[j];

item[j] = item[j+1];

item[j+1] = item;

flag = 1;} //交换item[j]与item[j+1],并将flag置1

b[i] =j;

}

p =i;

if(flag = =0)

break;

}

printf(“本次排序外循环的次数为%d次.\n”,i,b[i]);

}

(四)与传统的冒泡排序法的实验比较

(设数组 A 有 9 个元素)

1)如果待排序的数组元素原来已经排序或只有相邻的一对数未排好序,则本算法只执行 8 次循环即可结束,而传统的冒泡排序法需执行 9 * 8 = 72 次循环。

2)经过反复实验比较,本算法在最坏的情况下,即所有待排序元素顺序都不正确时,其时间复杂度与传统的冒泡排序法一样,其余情况本算法的时间复杂度均小于传统冒泡排序法的时间复杂度。

(五)实验结果的进一步分析

根据实验数据可以看出:当待排序元素基本有序时,本排序算法的时间复杂度会大大降低,而传统的冒泡排序算法所需时间度会随着待排序元素个数的增加而大大增加。

(六)结论

本排序算法在待排序元素大多有序的情况下,会大大节省时间,降低算法的时间复杂

度,有时其时间复杂度可达O(n)。

(七)本算法的优缺点

本算法只有待排序数据元素基本有序的情况下,不愧为一种好算法,但如果待排数据元素杂乱无章,和传统的冒泡排序法一样,在大多数场合下,本算法优点大于缺点,是实用的。

五、两种排序算法的改进

排序是计算机程序设计中的一种重要操作 ,它通常是指将一个数据元素 (或记录 )的任意序列 ,重新排列成一个按关键字有序的序列。学习和研究各种排序方法是计算机工作者的重要课题之一。冒泡法和选择法排序是目前最为读者熟悉且实用的基于交换的排序方法。在实际排序过程中 ,如果在传统排序方法的基础上作一下改进 ,即可得到将两种排序都双向进行的新算法 ,本文对新算法进行了分析 ,显示了新算法在比较次数和移动次数上的优越性。

(一)双向冒泡法与双向选择排序法思想

传统冒泡法和选择排序法都是每一趟在 n - i + 1个记录中找出关键字最小或最大的一个记录 ,反复循环 ,直到全部记录有序。整个排序过程需进行 n - 1趟排序。

新的双向排序算法则是在一趟排序过程中 ,同时找出当前未排好序的序列中关键字最小和最大的两个记录 ,反复循环 ,直到全部记录序列都按关键字排好序。可见新算法只需进行 n /2趟排序。

限于篇幅 ,现以选择排序法为例进行分析。

设待排序的序列存于 r[ n + 1 ]中 ( r[ 0 ]闲置 ) ,为使 n个记录的双向选择排序 (升序 )在待排序列的两端实现 ,则完成一趟选择排序必须同时出列两个记录 ,即当前关键字最小和最大的记录 ,这样 ,要实现一趟选出两个记录 ,同时考虑到要使比较次数达到最少 ,则必须在传统选择排序基础上增加两个 if条件判断语句 ,其基本思想是:首先将第一个记录与最后一个记录的关键字进行比较 ,若为逆序 (即 ( r[ 1 ]. key > r[ n ].key) ,则将两个记录交换之;然后将第二个记录与第一个记录的关键字进行比较 ,若为逆序 (即( r[ 2 ]. key< r[ 1 ]. key) ,则将两个记录交换之 ,再将第二个记录与最后一个记录的关键字进行比较 ,若为逆序 (即 ( r[ 2 ]. key > r[ n ]. key) ,则将两个记录交换之。

依此类推 ,直到第 n - i个记录分别与第一和最后一个记录的关键字进行过比较交换为止。上述过程为第一趟双向选择排序,简言之 ,即先将第 1个记录与最后一个记录的关键字进行比较 ,若为逆序 ,则交换之 ,再将第 2到第 n - i个记录的关键字分别与第 1和第 n 个记录的关键字进行比较 ,若为逆序 ,则交换之。其结果使得关键字最小的记录排到了序列中的第一个位置上 ,关键字最大的记录排到了序列中的最后一个记录的位置上。然后对剩下的 n - 2个记录同样操作进行第二趟双向选择排序 ,找出关键字次小和次大的记录分别放在第二个和倒数第二个记录的位置上。重复进行双向选择排序 ,则对具有 n个记录的待排序列 ,只须进行「 n /2」趟 ,就可以实现各记录按关键字排好序(升序 )。

(二)算法描述

根据算法思想给出如下算法:

(1)设待排记录的数据类型为:

struct record

{ int key; //待排关键字

…… //其它数据成员

}

(2)循环 i以 1为步长,从 1到 n /2,执行下列语句。

若 r[ i ]. key > r[ n - i + 1 ]. key则执行 r[ i ]←→r[ n - i + 1 ]

(3)循环 j以 1为步长,从 i + 1到 n - i,执行

若 r[ j ]. key < r[ i ]. key则执行 r[ j ]←→r[ i ]

若 r[ j ]. key >r[n-i+1]. key则执行r[j] ←→r[n-i+1]

(4)算法结束。

算法的主体程序段如下:

/*定义数据类型 */

struct record

{ int key;

} r[N ] ; /* N 在实际设计时根据数据个数定义为一具体正整型常量,且 N = n + 1*/ /*主程序段 */

for ( i = 1; i < = n /2; i + + )

{ if ( r[ i ]. key > r[ n - i + 1 ]. key)

{ t = r[ i ]. key; r[ i ]. key = r[ n - i + 1 ]. key; r[ n - i + 1 ]. key = t ; } for ( j = i + 1; j < = n - i ; j + + )

{ if ( r[ j ]. key < r[ i ]. key)

{ t = r[ i ]. key; r[ i ]. key = r[ j ]. key; r[ j ]. key = t ; }

if ( r[ j ]. key > r[ n - i + 1 ]. key)

{ t = r[ j ]. key; r[ j ]. key = r[ n - i + 1 ]. key; r[ n - i + 1 ]. key = t ; } }

}

(三)算法的理论分析

分析排序算法的性能通常是讨论算法的比较次数和记录的移动次数。现对双向选择排序算法进行分析:

(1)比较次数。无论记录的初始排列如何 ,所需进行的关键字间的比较次数相同 ,均为

,和传统选择排序算法的比较次数是完全相同的。 (2)移动次数。传统选择排序方法所需进行记录移动的最大次数为 ,双向选择排序过程中 ,所需进行记录移动的操作次数较少 ,如果初始待排序列已排好序 ,则很容易看出记录的移动次数为 0次 ,达到最少;而其最大记录移动次数仅为 n – 1,大大低于传统选择排序算法的移动次数。

同理可得出双向冒泡排序法的比较次数为 n ( n - 1) /2,记录的移动次数为 3n ( n -

1) /2,都与传统冒泡法相同。 (四)结束语

通过以上分析可以看出:两种排序方法的双向排序和传统的排序方法在思想上基本一(3)

(1)/2n n -(3)3(1)

n -

致,且同样行之有效,但本文给出的双向选择排序算法有更高的排序效率。双向冒泡排序的排序效率虽然与传统排序算法相同,但也可作为实际排序和教学过程中的思路参考。

六、关于冒泡排序的改进算法的分析与比较

在计算机处理信息的过程中,由于排序数据或记录非常频繁,计算机运行时间的很大部分就被花费在数据或记录的排序上。排序算法对于计算机信息处理很重要,一个好的排序不仅可以使信息查找的效率提高,而且还直接影响着计算机的工作效率。所以排序算法( sorting algo rithm)就成了计算机程序设计中的一个重要环节,同时也成为研究的重要课题。它的功能是将一个数据元素 (或记录 )的任意序列,重新排列成一个按关键字( key word)排序的序列。在众多的排序方法中,冒泡排序 ( bubble sort)是最简单的一种本文主要对冒泡排序算法及其几种改进算法的基本原理进行介绍和分析,并对它们的算法性能进行比较。

(一)排序算法及算法分析

冒泡排序的基本思想:设想被排序的记录数组 R [ 1 、、 n ]垂直竖立,将每个记录R [ i ]看作是重量为 R [ i ]. key的“气泡”。据轻“气泡”不能在重“气泡”下的原则,从下往上扫描数组 R;凡扫描到违反本原则的轻“气泡”,就使其向上“飘浮”如此反复,直到最后任何两个气泡都是轻者在上、重者在下为止。即第 I趟扫描时,R [ 1 、、 i - 1 ]和 R [ i 、、 n ]分别为当前的有序区和无序区,扫描均是从无序区底部向上直至该区顶部,扫描完毕时,该区中最轻气泡飘浮到顶部位置 R [ i ]上,结果R [ 1 、、 i ]变为新的有序区。

算法 1

void Bubble - s ort - 1 ( SeqlistR)

{ / /R[ i 、、 n ]是待排序的记录 ,采用自下向上扫描对 R做冒泡排序

int i, j ;

for ( i = 1; i < n; i + + ) / /最多做 n - 1趟排序

for ( j = n; j > i ; j - - ) / /对当前无序区 R[ i 、、 n ]自下向上扫描

if (R ( j) . key >R ( j - 1) . key) / /逆序则交换

{R (0) =R ( j) ;

R ( j) =R ( j - 1) ;

R ( j - 1) =R (0) ;

}

} / / bubble - - sort

冒泡排序的最好、 最坏、 平均情况下的时间复杂度都为

,故算法的平均时间复杂度也为 。但是若在某趟排序中未发现气泡位置的交换 ,则说明待排序的无序区中所有气泡均满足轻者在上、 重者在下的原则 ,即为正序 ,则冒泡排序过程可在此趟扫描后就终止;在每趟排序过程中 ,无序区 R [ i 、 、 n ]的范围可能会有较大改变 ,而不是递减;对某些不对称性情况 ,在排序过程中 ,可改变其扫描方向。

(二)排序算法的几种改进算法及算法分析

[改进之一 ]:在冒泡排序算法中,引入一个布尔量 exchange ,在每趟排序开始前,先将其置为 FALSE ;若排序过程中发生了交换,则将其置为 TURE ;每趟排序结束后检查 exchange ,若未发生过交换,则终止算法,不再进行下一趟排序,从而减少排序的趟数。

算法 2

void Bubble - s ort - 2 ( SeqlistR)

{ / / R[ 1 、 、 n ]是待排序的记录,采用算法 2自下向上扫描对 R 做冒泡排序 int i, j ;

Boolean: exchange;

For ( i = 1; i < n; i + + ) / /最多做 n - 1趟排序

{ exchange = FLASE;

for ( j = n; j > i ; j - - ) / /对当前无序区 R[ i 、 、 n ]自下向上扫描 if (R ( j) . key >R ( j - 1) . key)

{R (0) =R ( j) ;

R ( j) =R ( j - 1) ;

R ( j - 1) =R (0) ;

2

()O n 2()O n

Exchange = TURE;

}

if ( exchange = FALSE)

return;

} / / endfor (外循环 ) }

} / /bubble sort

从算法 2可以看出 ,若记录的初始状态是有序的,则一趟扫描即可完成排序,所需的关键比较和记录移动的次数分别达到最小值:Cmin = n – 1,Mmin = 0,即算法最好的时间复杂度为 O ( n) ;若初始记录是反序的,则需要进行 n - 1趟排序,每趟排序要进行 n - i 次关键字的比较 ( l ≤i ≤n - 1),且每次比较都必须移动记录三次来达到交换记录位置。在这情况下,比较和移动次数达到最大值:

因此,算法2的最坏时间复杂度也为 。在平均情况下,算法可能在中间的某一趟

排序完后就终止,但总的比较次数仍为 (证明略 ),所以算法的平均时间复杂度

为 。因此,算法2最好的时间复杂度为 O ( n),平均、 最坏时间复杂度为 。 [改进之二 ]:在冒泡排序的每趟扫描中 ,记住最后一次交换发生的位置 lastexchange ,因为该位置之前的相邻记录均已有序,故下一趟排序开始时, R [ 1 、 、 lastexchange - 1 ]是有序区, R [ lastexchange 、 、 n ]是无序区 这里 ,lastexchange 通常大于算法2的内循环中的无序区的下界 I ,二者至多相等。所以一趟排序可能使当前有序区扩充多个记录,即较大缩小无序区范围,而非递减 1,以此减少排序趟数。

算法 3

void Bubble - sort - 3 ( SeqlistR)

{ / /R[ i 、 、 n ]是待排序的记录,采用算法3自下向上扫描对 R 做冒泡排序

int i, j, lastexchange = 1;

while ( i < n) { lastexchange = n;

1

21(1)m ax ()()

2n i n n C n i O n -=-=-=

=∑121m ax 3()3(1)/2()n i M n i n n O n -==-=-=∑2

()O n 2()O n 2()O n 2()O n

for ( j = n; j > i ; j - - ) / /对当前无序区 R[ i 、 、 n ]自下向上扫描

if (R ( j) . key >R ( j - 1) . key)

{R (0) =R ( j) ;

R ( j) =R ( j - 1) ;

R ( j - 1) =R (0) ;

lastexchange = j ;

}

i = lastexchange

}

} / / bubble - - sort

从算法 3可以看出,若记录的初始状态是有序的,一趟扫描也可完成排序,所需的关键比较和记录移动的次数也分别达到最小值: Cmin = n – 1,Mmin = 0,即算法最好的时间复杂度为 O ( n) ;若初始记录是反序的,也需要进行 n - 1趟排序,每趟排序要进行 n - i 次关键字的比较 (1≤i ≤n - 1) ,且每次比较都必须移动记录三次来达到交换记录位置。在这情况下,比较和移动次数也达到最大值:

因此,算法3的最坏时间复杂度也为

。在平均情况下,算法因较大地改变了无序区的范围,从而减少了要排序的趟数,但总的比较次数仍为 (

证明略 )。所以算法3的最好时间复杂度为 O( n) ,平均和最坏时间复杂度为 。 [改进之三 ]:若记录的初始状态为:只有最轻的气泡位于 R [ n ]的位置 (或者最重的气泡位于 R [ 1 ]位置 ) ,其余的气泡均已排好序,在上述三种算法中都要做 n - 1趟扫描。实际上只需一趟扫描就可以完成排序。所以对于这种不对称的情况,可对冒泡排序又作一次改进。在排序过程中交替改变扫描方向,即先从下扫到上 ,再从上扫到下,来回地进行扫描,这样就得到双向冒泡排序算法。

算法 4 void Bubble - sort - 4 ( SeqlistR)

1

21(1)m ax ()()2n i n n C n i O n -=-=-=

=∑121m ax 3()3(1)/2()

n i M n i n n O n

-==-=-=∑2()O n 2()O n 2

()O n

{ / /R[ 1 、、n ]是待排序的记录,采用双向扫描对R做冒泡排序

int i, j = 1;

Boolean: exchange;

Exchange = T URE;

While ( exchange) / /排序趟数

{ exchange = FALSE;

for ( j = n - i + 1; j > i ; j - - ) / /对当前无序区R [ i…n - i + 1 ]自下向上扫描

if (R ( j) . key

{R (0) =R ( j) ;

R ( j) =R ( j - 1) ;

R ( j - 1) =R (0) ;

Exchange = T URE;

}

if ( exchange = FALSE)

return;

exchange = FALSE;

for ( j = i + 1; j < n - i + 1; j + + ) / /对当前无序区R [ i + 1 …n - i + 1 ]自上向下扫描if (R ( j) . key >R ( j + 1) . key)

{R (0) =R ( j) ;

R ( j) =R ( j + 1) ;

R ( j + 1) =R (0) ;

Exchange = TURE;

}

i + + ;

} / / endwhile

} / /double - bubble - - sort

从算法4可以看出,若记录的初始状态是有序的,此算法与算法 2、 3一样,只需一趟扫描即可完成排序,关键字的比较和记录移动的次数分别达到最小值: Cmin = n – 1, Mmax = 0,算法最好的时间复杂度为 O ( n) ;若初始记录是反序的,则需要进行 [ n /2 ]趟排序。若记录的初始状态为:只有最轻的气泡位于 R [ n ]的位置 (或者最重的气泡位于 R [ 1 ]位置 ),其余的气泡均已排好序,则算法 4只需一趟扫描即可完成,关键字的比较次数为 2n - 3次,记录移动的次数为 3 ( n - 1)次,此时算法 4的时间复杂度也为 O ( n) 每趟排序要进行 4 i + 1次关键字的比较 (1≤i ≤ n2) ) ,且每次比较都必须移动记录三次来达到交换记录位置。在这情况下,比较和移动次数达到最大值:

2max (1)()C n n O n ==-=,2

max 3(1)/2()M n O n ==-=

因此,算法4的最坏时间复杂度也为 。 (三)算法性能比较

对于待排序的记,若记录的初始状态是有序的,算法1需进行 n - 1趟扫描才能完成

排序,其时间复杂度为 ;而算法 2、 3、 4,只需一趟扫描即可完成排序 ,它们的最好时间复杂度均为 O ( n) ;若初始记录是反序的,算法 1、 2、 3均需进行 n - 1趟

扫描才能完成排序,其最坏的时间复杂度均为

;算法 4也需要进行 [ n /2 ]趟排序,算法 4的最坏时间复杂度也为 。若记录的初始状态为:只有最轻的气泡位于 R[ n ]的位置,其余的气泡均已排好序,则算法1仍需 n - 1趟扫描才能完成排序,其时间复杂

度为

;算法 2、 3需 2趟扫描即可完成排序,算法 2、 3的时间复杂度为 O( n);算法 4只需进行一趟扫描即可完成排序,其时间复杂度为 O( n)。若记录的初始状态为:只有最重的气泡位于 R [ 1 ]的位置,其余的气泡均已排好序,算法 1、 2、 3均需 n - 1

趟扫描才能完成排序,其时间复杂度均为 ;算法 4 (先自上向下排序,然后自下向上

排序 )则只需进行一趟扫描即可完成排序,其时间复杂度为 O( n)。对于待排序的记录的不同的初始状态,采用不同的冒泡排序,可以提高其效率。

七、设计总结

这篇文章主要介绍了几种改进后的算法,并与传统算法相比较,以凸显新算法的优越性,同是一个案例,需要分析它的很多元素,然后再选择哪种方法更有效率,这是一个繁琐而复杂的工作,其实它们十分相近,因此我们要熟练的掌握这些算法的特征。

2

()O n 2

()O n 2()O n 2()O n 2()O n 2()O n

参考文献

[1]乔月圆,对《C程序设计》的教学实践及认识 [J]。承德民族职业技术学院学

报,2005(1):22-23。

[2]钟频,高级语言程序设计的精髓——算法设计[J]。株洲师范高等专科学校学

报,2005(5): 51-53。

[3]陈元琰,程序设计过程中“循环结构”一届的教学方法 [J].高教论坛,2004(1):76-78。

[4]王树武,C语言程序设计与教程习题与上机指导[M].北京:北京理工大学出版社,2001。

[5]苏小红,陈惠鹏,孙志刚 C 语言大学实用教程[M]。2 版。北京电子工业出版社,2007。

[6]谭浩强,C 语言程序设计[M]。北京清华大学出版社,2000。

[7][美]Kris Jamsa, Lars Klander, C/C++程序员实用大全[M]。北京:中国水利水电出版

社, 2002。

[8]徐金梧,杨德斌,徐科, TURBO C实用大全[M]。北京:机械工业出版社, 2000。

[9]徐士良, C常用算法程序集[M]。北京:清华大学出版社,1994。

[10]徐孝凯,数据结构实用教程(C/ C + +描述)[M]。北京:清华大学出版社 ,2001。

[11]谭浩强, C程序设计(第二版)[M]。北京:清华大学出版社 ,1999。 124 125。

[12]许善祥,高军,纪玉玲。冒泡排序算法的改进[J]。黑龙江科技学院学报,2002,12(1):25

27。

[13]郑启华, PASCAL 程序设计(第二版) [M] 。北京:清华大学出版社 ,1999。

[14]朱清新,算法设计与分析课件 2004 。

[15]严蔚敏,数据结构 [M ]。清华大学出版社 , 1992 。

[16]夏克俭,数据结构 +算法 [M ]。国防工业出版社 , 2001 。

算法分析与设计复习题及参考答案

网络教育课程考试复习题及参考答案算法分析与设计一、名词解释:1.算法 2.程序 3.递归函数 4.子问题的重叠性质 5.队列式分支限界法 6.多机调度问题7.最小生成树二、简答题: 1.备忘录方法和动态规划算法相 比有何异同?简述之。 2.简述回溯法解题的主要步骤。 3.简述动态规划算法求解的基本要素。 4.简述回溯法的基本思想。 5.简要分析在递归算法中消除递归调用,将递归算法转化为非递归算法的方法。 6.简要分析分支限界法与回溯法的异同。7.简述算法复杂性的概念,算法复杂性度量主要指哪两个方面?8.贪心算法求解的问题主要具有哪些性质?简述之。9.分治法的基本思想是什么?合并排序的基本思想是什么?请分别简述之。10.简述分析贪心算法与动态规划 算法的异同。三、算法编写及算法应用分析题: 1.已知有3个物品: (w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10),背包的容积M=20,根据0-1背包动态规划的递推式求出最优解。 2.按要求完成以下关于排序和查找的问题。①对数组A={15,29,135,18,32,1,27,25,5},用快速排序方法将其排成递减序。②请描述递减数组进行二分搜索的基本思想,并给出非递归算法。③给出上述算法的递归算法。④使用上述算法对①所得到的结果搜索如下元素,并给出搜索过程:18,31,135。已知,=1,2,3,4,5,6,=5,=10,=3,=12,=5,=50,=6,kijr*r1234567ii1求矩阵链积A×A×A×A×A×A的最佳求积顺序(要求给出计算步骤)。1234564.根据分枝限界算法基本过程,求解0-1背包问题。已知n=3,M=20,(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10)。 5.试用贪心算法求解汽车加油问题:已知一辆汽车加满油后可行驶n公里,而旅途中有若干个加油站。试设计一个有效算法,指出应在哪些加油站停靠加油,使加油次数最少,请写出该算法。6.试用动态规划算法实现下列问题:设A和B是两个字符串。我们要用最少的字符操作,将字符串A转换为字符串B,这里所说的字符操作包括:①删除一个字符。②插入一个字符。③将一个字符改为另一个字符。请写出该算法。7.对于下图使用Dijkstra算法求由顶点a到顶点h的最短路径。be2g212ad323182cf2h 8.试写出用分治法对数组A[n]实现快速排序的算法。9.有n个活动争用一个活动室。已知活动i占用的时间区域为[s,f ],活动i,j相容的条件是:sj≥f ii,问题的解表示为(x| x =1,2…,n,),x表示顺序为i的活动编号活动,求一个相容的活动子集,iiii且安排的活动数目最多。xxx10.设、、是一个三角形的三条边,而且x+x+x=14。请问有多少种不同的三角形?给出解答过程。12312311.

高中信息技术《算法与程序设计》试题

高中信息技术《算法与程序设计》试题 一、单选题(每小题3分,20小题,共60分) 1、用计算机解决问题时,首先应该确定程序“做什么?”,然后再确定程序“如何做?”请问“如何做?”是属于用计算机解决问题的哪一个步骤?() A、分析问题 B、设计算法 C、编写程序 D、调试程序 2、在调试程序过程中,下列哪一种错误是计算机检查不出来的?() A、编译错误 B、执行错误 C、逻辑错误 D、任何错误计算机都能检查出来 3、下列关于算法的叙述中,错误的是() A、一个算法至少有一个输入和一个输出 B、算法的每一个步骤必须确切地定义 C、一个算法在执行有穷步之后必须结束 D、算法中有待执行的运算和操作必须是相当基本的。 4、流程图中表示判断的是()。 A、矩形框B、菱形框C、圆形框D、椭圆形框 5、任何复杂的算法都可以用三种基本结构组成,下列不属于基本结构的是() A、顺序结构 B、选择结构 C、层次结构 D、循环结构 6、能够被计算机直接识别的语言是() A、伪代码 B、高级语言 C、机器语言 D、汇编语言 7、在VB语言中,下列数据中合法的长整型常量是() A、08A B、2380836E C、88.12345 D、1.2345E6 8、求Mid(“ABCDEFG”,3,2)的结果是() A、“ABC” B、“CD” C、“ABCDEF” D、“BCD” 9、表达式 A+B+C=3 OR NOT C<0 OR D>0 当A=3,B=4,C=-5,D=6时的运算结果是() A、0 B、1 C、TRUE D、FALSE 10、在循环语句 For x=1 to 100 step 2 …… Next x 中,x能达到的最大值是() A、100 B、99 C、98 D、97 11、在下列选项中,不属于VB的对象的是() A、窗体的背景颜色 B、命令按钮 C、文本框 D、标签 12、在调试程序的时候,经常要设置断点,设置断点的快捷键是()

算法分析与设计总结

第一章算法概述 1.算法:解决问题的一种方法或过程;由若干条指令组成的有穷指令。 2.算法的性质: 1)输入:有零个或多个输入 2)输出:有至少一个输出 3)确定性:每条指令是清晰的、无歧义的 4)有限性:每条指令的执行次数和时间都是有限的 3.算法与程序的区别 程序是算法用某种程序设计语言的具体实现 程序可以不满足算法的有限性 4.算法复杂性分析 1)算法的复杂性是算法运行所需要的计算机资源的量,需要时间资源的量称为时间复 杂性,需要空间资源的量称为空间复杂性 2)三种时间复杂性:最坏情况、最好情况、平均情况 3)可操作性最好且最有实际价值的是最坏情况下的时间复杂性 第二章递归与分支策略 1.递归概念:直接或间接调用自身的算法 2.递归函数:用函数自身给出定义的函数 3.递归要素:边界条件、递归方程 4.递归的应用 ?汉诺塔问题 void Hanuo(int n,int a,int b,int c) { if(n==1) return; Hanuo(n-1,a,c,b); move(a,b) Hanuo(n-1,c,b,a); } ?全排列问题 void Perm(Type list[],int k,int m) { //产生list[k,m]的所有排列 if(k == m) { for(int i = 0;I <= m;i++) cout<

算法设计与分析复习题目及答案

一。选择题 1、二分搜索算法是利用( A )实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是( B )。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是( A )的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、在下列算法中有时找不到问题解的是( B )。 A、蒙特卡罗算法 B、拉斯维加斯算法 C、舍伍德算法 D、数值概率算法 5. 回溯法解旅行售货员问题时的解空间树是( B )。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树6.下列算法中通常以自底向上的方式求解最优解的是( B )。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 7、衡量一个算法好坏的标准是(C )。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 8、以下不可以使用分治法求解的是(D )。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 9. 实现循环赛日程表利用的算法是( A )。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 10、下列随机算法中运行时有时候成功有时候失败的是(C ) A 数值概率算法 B 舍伍德算法 C 拉斯维加斯算法 D 蒙特卡罗算法 11.下面不是分支界限法搜索方式的是( D )。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先12.下列算法中通常以深度优先方式系统搜索问题解的是( D )。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13.备忘录方法是那种算法的变形。( B )

《算法与程序设计》试题带答案

《算法与程序设计》试题 学校:_____________ 班级:____________ 学号:____________ 姓名:____________ 一、单选题(每小题3分,20小题,共60分) 1、用计算机解决问题时,首先应该确定程序“做什么?”,然后再确定程序“如何做?”请问“如何做?”是属于用计算机解决问题的哪一个步骤?() A、分析问题 B、设计算法 C、编写程序 D、调试程序 2、在调试程序过程中,下列哪一种错误是计算机检查不出来的?() A、编译错误 B、执行错误 C、逻辑错误 D、任何错误计算机都能检查出来 3、下列关于算法的叙述中,错误的是() A、一个算法至少有一个输入和一个输出 B、算法的每一个步骤必须确切地定义 C、一个算法在执行有穷步之后必须结束 D、算法中有待执行的运算和操作必须是相当基本的。 4、流程图中表示判断的是()。 A、矩形框B、菱形框C、圆形框D、椭圆形框 5、任何复杂的算法都可以用三种基本结构组成,下列不属于基本结构的是() A、顺序结构 B、选择结构 C、层次结构 D、循环结构 6、能够被计算机直接识别的语言是() A、伪代码 B、高级语言 C、机器语言 D、汇编语言 7、在VB语言中,下列数据中合法的长整型常量是() A、08A B、2380836E C、88.12345 D、1.2345E6 8、求Mid(“ABCDEFG”,3,2)的结果是() A、“ABC” B、“CD” C、“ABCDEF” D、“BCD” 9、表达式 A+B+C=3 OR NOT C<0 OR D>0 当A=3,B=4,C=-5,D=6时的运算结果是() A、0 B、1 C、TRUE D、FALSE

高二算法与程序设计试题及答案

高二信息技术(算法与程序设计)试题卷 一、单项选择题(每小题2.5分共50分将正确答案填到答题卷相应题号下) 1、一同学想通过程序设计解决“鸡兔同笼”的问题,他制定的如下工作过程中,更恰当的是()。 A、提出问题、设计算法、编写程序、得到答案 B、提出问题、编写程序、运行程序、得到答案 C、编写程序、设计算法、调试程序、得到答案 D、设计程序、提出问题、编写程序、运行程序 2、下列常量说明中,符合语法的是()。 A、CONST color=red B、CONST const=10*5 C、CONST xl:=3.9; D、CONST color=”abcd” 3、下列代数式的Visual Basic表达式是( )。 A、(x^5-cos(29*3.14))/(sqr(exp(x)+log(y))) B、(x^5-cos(29))/(sqr(exp(x)+ln(y))+5) C、(x^5-cos(29*3.14/)/(sqr(exp(x)+ln(y))+5) D、(x^5-cos(0.506))/(sqr(exp(x)+log(y))+5) 4、下列变量名写法错误的是()。 A、abc B、abc123 C、abc_123 D、123abc 5、visual basic程序设计语言是一种()。 A、高级语言 B、汇编语言 C、机器语言 D、数据库语言 6、下列给出的赋值语句中正确的是()。 A、4 = M B、-M =M C、B=A-3 D、x + y = 0 7、下列Visual Basic中,下列()的表达式的值不等于4。 A、int(4.1) B、fix(4.9) C、Abs(int(-3.9)) D、Abs(int(-4.5)) 8、下面程序运行后的输出S结果为()。 i=1 do WHILE i<8 i=i+2:s=2*i+3 loop PRINT s A、17 B、19 C、21 D、23 9、下列Visual Basic中,下列()类型属于字符串型。 A、Integer B、Single C、String D、Boolean 10、在VB中表达式11\3+11 mod 3 的运算结果值是()。 A、3 B、4 C、5 D、6 11、下列程序执行后,整型变量n的值为( )。 n=0: for I=1 to 100: if I mod 4=0 then n=n+1: next I A、5050 B、25 C、26 D、33 12、以下选项中,不是Visual Basic控件的是( )。 A、文本框 B、定时器 C、窗体 D、命令按钮 13、使用Visual Basic编程,我们把工具箱在的工具称为( )。 A、事件 B、工具 C、控件 D、窗体 14、结构化程序设计由三种基本结构组成,下面哪个不属于这三种基本结构()。 A、顺序结构 B、输入、输出结构 C、选择结构 D、循环结构 15、语句if 3*4>=10 then a=1 else a=2 执行后,a的值为()。 A、12 B、10 C、1 D、2 16、下列结果为True的逻辑表达式是( )。 A、Not (3<8) B、(3<9) And (5>10) C、(3<8) And (5<10) D、(3>8) Or (5>10) 17、要交换变量X和Y之值,应使用的语句组是( )。 A、X=Y;Y=Z;Z=X B、C=X;X=Y;Y=C C、X=Y;Y=X D、Z=Y;Y=X;Y=Z 18、以下程序中的循环体执行的次数是()。

《程序设计与算法分析》课程设计报告

数据结构课程设计报告 设计名称:1)简单个人电话号码查询系统 2)哈希表设计

《程序设计与算法分析》课程设计报告 一、简单个人电话号码查询系统 1、需求分析 1、程序的功能:实现一个简单的个人电话号码查询系统,根据用户输入的信息进行排序(按电话号码)并且可以进行快速查询(按姓名),同时还可以进行插入、删除、修改等维护功能 2、输入输出的要求:电话本中每个人的各项信息需要由键盘进 行输入,应用getch 函数进行输入,printf 函数实现输出。 3、测试数据。 2、概要设计 1、存储结构设计说明: 应用结构体类型的数组对电话本中的记录进行存储。 struct record { char name[20]; char phone[20]; char mailbox[20]; }people[60]; 2、程序设计组成框图 3、详细设计 1、主函数 函数功能:对写入文件函数及主菜单函数进行调用。实现主菜单的显示 函数类型:未调用参数,且无返回值。 函数调用关系描述:调用主菜单函数及写入文件函数,实现主菜 个人电话本系统 主菜单 文件导入函数 添加记录函 数 修改菜单 按姓名修改 删除菜单 删除函数 查找菜单 查找函数 排序菜单 排序函数 显示所有 写入文件

单的显示。 2、从文件导入函数 函数功能:判断文件是否存在,存在进行导入,不存在进行文件导入。 函数类型:未调用参数,且无返回值。 算法说明(流程图表示) 开始 是否为输入打开文件失败 是否为输出打开文件失败 建立失败 通讯录 已建立 返回主菜单 退出 指针调到文件尾 文件当 前位置 是否大 于0 返回文件头部,遍历 向电话本中写入信 息 文件导入 成功 任意键回主 菜单 文件导入成功, 无任何记录,任 意键回主菜单 返回主菜单 否 否 否 是 是 是 从文件导入函数流程图

算法与程序设计试题带答案

高一第二学期《算法与程序设计》学分认定试题 学校:_____________ 班级:____________ 学号:____________ 姓名:____________ 一、单选题(每小题3分,20小题,共60分) 1、用计算机解决问题时,首先应该确定程序“做什么”,然后再确定程序“如何做”请问“如何做”是属于用计算机解决问题的哪一个步骤() A、分析问题 B、设计算法 C、编写程序 D、调试程序 2、在调试程序过程中,下列哪一种错误是计算机检查不出来的() A、编译错误 B、执行错误 C、逻辑错误 D、任何错误计算机都能检查出来 3、下列关于算法的叙述中,错误的是() A、一个算法至少有一个输入和一个输出 B、算法的每一个步骤必须确切地定义 C、一个算法在执行有穷步之后必须结束 D、算法中有待执行的运算和操作必须是相当基本的。 4、流程图中表示判断的是()。 A、矩形框B、菱形框C、圆形框D、椭圆形框 5、任何复杂的算法都可以用三种基本结构组成,下列不属于基本结构的是() A、顺序结构 B、选择结构 C、层次结构 D、循环结构 6、能够被计算机直接识别的语言是() A、伪代码 B、高级语言 C、机器语言 D、汇编语言 7、在VB语言中,下列数据中合法的长整型常量是() A、08A B、2380836E C、 D、 8、求Mid(“ABCDEFG”,3,2)的结果是() A、“ABC” B、“CD” C、“ABCDEF” D、“BCD” 9、表达式A+B+C=3 OR NOT C<0 OR D>0 当A=3,B=4,C=-5,D=6时的运算结果是() A、0 B、1 C、TRUE D、FALSE 10、在循环语句For x=1 to 100 step 2 …… Next x 中,x能达到的最大值是() A、100 B、99 C、98 D、97 11、在下列选项中,不属于VB的对象的是() A、窗体的背景颜色 B、命令按钮 C、文本框 D、标签 12、在调试程序的时候,经常要设置断点,设置断点的快捷键是()A、F1 B、F8 C、F9 D、F12 13、算法描述可以有多种表达方法,下面哪些方法不可以描述“闰年问题”的算法() A、自然语言 B、流程图 C、伪代码 D、机器语言 14、以下不属于非法用户自定义标识符(常量和变量命名)的是() A、8ad B、ad8 C、_a8d D、const 15、已知A,B,C,D是整型变量,且都已有互不相同的值,执行语句B=0;A=C;D=A;D=B;后,其值相等的变量是() A、A,D B、A,C C、C,B D、B,A 16、要交换变量A和B的值,应使用的语句组是( ) A、A=B;B=C;C=A B、C=A;A=B;B=C C、A=B;B=A D、C=A;B=A;B=C 17、VisualBasic中以单引号开头一行文字称为注释,它对程序的运行() A、起一定作用 B、有时候起作用 C、不起任何作用,但是必须的 D、不起任何作用,但能增加程序的可阅读性 18、要使一个命令按钮显示文字“确定”,正确的设置是把该命令按钮的()。 A、属性Font设置为“确定” B、属性.ForeColor设置为“确定” C、属性Caption设置为“确定” D、属性BorderStyle设置为“确定” 19、要从文本框TXTShowOut中输出"中国您好!",代码为( ) A ="中国您好!" B ="中国您好!" C ="中国您好!" D Val=“中国您好!” 20、下列Visual Basic程序段运行后,变量max的值为()。 a=11; b=15; max=a IF b>max Then max =b A、15 B、11 C、15或11都有可能 D、以上都不是 二、阅读程序写结果(第1~2小题每题5分,第3小题10分,共20分) 1、Private Sub Form_Load() N=InputBox(“请输入N的值:”,“输入”) S=1 For i=1 to N S=S*i Next i MsgBox “S=”+Str(s),0,”计算结果” End Sub 当N=5时,运行的结果是__________________。

计算机算法设计与分析习题和答案解析

《计算机算法设计与分析》习题及答案 一.选择题 1、二分搜索算法是利用(A )实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是(A )。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是( A )的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4. 回溯法解旅行售货员问题时的解空间树是( A )。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树 5.下列算法中通常以自底向上的方式求解最优解的是( B )。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 6、衡量一个算法好坏的标准是(C )。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 7、以下不可以使用分治法求解的是(D )。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 8. 实现循环赛日程表利用的算法是( A )。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 9.下面不是分支界限法搜索方式的是( D )。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 10.下列算法中通常以深度优先方式系统搜索问题解的是( D )。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 11.备忘录方法是那种算法的变形。(B ) A、分治法 B、动态规划法 C、贪心法 D、回溯法 12.哈夫曼编码的贪心算法所需的计算时间为( B )。 A、O(n2n) B、O(nlogn) C、O(2n) D、O(n) 13.分支限界法解最大团问题时,活结点表的组织形式是( B )。 A、最小堆 B、最大堆 C、栈 D、数组 14.最长公共子序列算法利用的算法是( B )。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15.实现棋盘覆盖算法利用的算法是( A )。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 16.下面是贪心算法的基本要素的是( C )。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解 17.回溯法的效率不依赖于下列哪些因素( D ) A.满足显约束的值的个数 B. 计算约束函数的时间 C.计算限界函数的时间 D. 确定解空间的时间 18.下面哪种函数是回溯法中为避免无效搜索采取的策略( B ) A.递归函数 B.剪枝函数C。随机数函数 D.搜索函数 19. ( D )是贪心算法与动态规划算法的共同点。

2014山东省信息技术学考算法与程序设计试题答案附后讲解

2014山东省信息技术学考算法与程序设计试题答案附后讲解

山东省学考算法与程序设计试题 选择题 1、下列VB表达式中: ⑴Sqr(x) ⑵Text1.text ⑶Command1.caption ⑷"45"+"34" ⑸45+34值为字符串类型的是() A⑴⑵⑶ B⑵⑶⑷ C ⑴⑶⑸ D⑵⑷⑸ 2、如果给出三条线段的长分别为a、b、c,且已知a≤b≤c,要问这三条线段能否构成三角形,仅需下列选项中的哪个判定条件即可?() A 其他选项都不对 B a+c>b C a+b>c D b+c>a 3、VB程序中“Dim n As Integer”这条语句的作用是() A 定义一个事件过程 B 定义一个数据输入方法 C 定义一个变量 D 定义一个数据处理方法 4、关于算法的描述,下列选项中正确的是() A 算法的每一步骤必须有确切的含义 B 算法必须有输入 C 算法的步骤可以是无穷的 D 算法本身就是一种程序设计语言 5、关于算法的描述,正确的是() A同一种算法只能用一种程序语言实现 B算法就是数值计算的方法 C描述算法的方法只有流程图 D算法是描述解决问题的方法和步骤 6、算法的描述方法有多种,下列选项中不适合描述算法的是() A机器语言 B自然语言 C流程图 D伪代码 7、长度分别为a、b、c的三条线段,能够组成三角形的条件是() A a+b>c Or a+c>b Or b+c>a B a+b>c or a+c>b And b+c>a C a+b>c Or a+c>b And b+c>a D a+b>c And a+c>b And b+c>a 8、已知海伦公式:()()() p p a p b p c ---p=1 2 (a+b+c),a、b、c分别为三角形的三条 边长。利用海伦公式求三角形面积的算法属于() A 排序法 B 解析法 C 穷举法 D 查找法 9、以下程序段中循环体执行的次数是() s=0 i=0 Do While s<10 i=i+1 s=s+i*i Loop A 1 B 3 C 2 D 4 10、下列VB表达式中,能正确表达不等式方程|x|>1的解的是() A x>-1 and x<1 B x>-1 or x<1 C x<-1 and x>1 D x<-1 or x>1 11、一元二次方程ax2+bx+c=0(a≠0)的两个实数根分别为: x 1 24 b b ac -+- 2 24 b b ac ---下列表达式正确的是() A x 2=-b-sqr(b^2-4*a*c)/(2*a) B x 1 =(-b+sqr(b^2-4ac))/(2*a)

算法与程序设计模块(选择题)汇总

算法与程序设计模块(选择题) 1.用流程图描述算法中表示“条件判断”的图形符号是 A. B. C. D. 答案:A 2.以下为求0到1000以内所有奇数和的算法,从中选出描述正确的算法 A. ①s=0; ②i=1; ③s=s+i; ④i=i+2; ⑤如果i≤1000,则返回③; ⑥结束 B. ①s=0; ②i=1; ③i=i+2; ④s=s+i; ⑤如果i≤1000,则返回③; ⑥结束 C. ①s=1; ②i=1; ③s=s+i; ④i=i+2; ⑤如果i≤1000,则返回③; ⑥结束 D. ①s=1;

②i=1; ③i=i+2; ④s=s+i; ⑤如果i≤1000,则返回③; ⑥结束 答案:A 3.在VB语言中,下列数据中合法的长整型常量是 A. 123456 B. 1234.56 C. 12345A D. A12345 答案:A 4.在VB语言中可以作为变量名的是 A. Print B. ab=cd C. 123abc D. abc_123 答案:D 5.设置TextBox的字体时,应改变TextBox的 A. Text属性 B. Font属性 C. ForeColor属性 D. Name属性 答案:B 7.代数式a ac b 24 2 对应的VB表达式是 A. sqr(b*b-4*a*c)/2*a B. sqr(b*b-4*a*c)/2/a C. sqr(b*b-4*a*c)/(2/a) D. sqr(b*b-4*a*c)/2a

答案:B 8.在VB语言中,下列正确的赋值语句是 A. I=I+1 B. I+1=I C. I*3=I D. 2I=I+1 答案:A 9.下列计算机程序设计语言中不属于高级语言的是 A. C++ B. Visual Basic C.机器语言 D. Java 答案:C 计算机程序设计语言:机器语言010*******汇编语言高级语言10.在VB语言中,下列逻辑表达式的值为"假"的是 A. #1/11/2009# > #11/15/2008# B. #1/11/2009# < #11/15/2008# C. 5 > 3 and 6 < 9 D. 5 > 3 or 6 > 9 答案:B 11.用流程图描述算法中表示“开始/结束”的图形符号是 A. B. C. D. 答案:B

最新高中信息技术《算法与程序设计》试题精品版

2020年高中信息技术《算法与程序设计》 试题精品版

新课标高中信息技术《算法与程序设计》试题一、单选题(每小题3分,20小题,共60分) 1、用计算机解决问题时,首先应该确定程序“做什么?”,然后再确定程序“如何做?”请问“如何做?”是属于用计算机解决问题的哪一个步骤?() A、分析问题 B、设计算法 C、编写程序 D、调试程序 2、在调试程序过程中,下列哪一种错误是计算机检查不出来的?() A、编译错误 B、执行错误 C、逻辑错误 D、任何错误计算机都能检查出来 3、下列关于算法的叙述中,错误的是() A、一个算法至少有一个输入和一个输出 B、算法的每一个步骤必须确切地定义 C、一个算法在执行有穷步之后必须结束 D、算法中有待执行的运算和操作必须是相当基本的。 4、流程图中表示判断的是()。 A、矩形框B、菱形框C、圆形框D、椭圆形框 5、任何复杂的算法都可以用三种基本结构组成,下列不属于基本结构的是( ) A、顺序结构 B、选择结构 C、层次结构 D、循环结构 6、能够被计算机直接识别的语言是() A、伪代码 B、高级语言 C、机器语言 D、汇编语言 7、在VB语言中,下列数据中合法的长整型常量是() A、08A B、2380836E C、88.12345 D、1.2345E6 8、求Mid(“ABCDEFG”,3,2)的结果是() A、“ABC” B、“CD” C、“ABCDEF” D、“BCD” 9、表达式 A+B+C=3 OR NOT C<0 OR D>0 当A=3,B=4,C=-5,D=6时的运算结果是() A、0 B、1 C、TRUE D、FALSE 10、在循环语句 For x=1 to 100 step 2 ……

历年算法与程序设计学业水平考试真题带答案

一、选择题 1、流程图是描述()的常用方式。 A、程序 B、算法 C、数据结构 D、计算规则 2、下面不属于算法描述方式的是()。 A、自然语言 B、伪代码 C、流程图 D、机器语言 3、以下运算符中运算优先级最高的是()。 A、+ B、^ C、>= D、* 4、某程序中三个连续语句如下: a=1 b=2 c=b+a 它属于() A、顺序结构 B、选择结构 C、循环结构 D、以上三种都不是 5、穷举法的适用范围是() A、一切问题 B、解的个数极多的问题 C、解的个数有限且可一一列举 D、不适合设计算法 6、在现实生活中,人工解题的过程一般分为() A、理解分析问题→寻找解题方法→用工具计算→验证结果

B、寻找解题方法→理解分析问题→用工具计算→验证结果 C、用工具计算→验证结果→寻找解题方法→理解分析问题 D、用工具计算→验证结果→理解分析问题→寻找解题方法 7、下列关于算法的特征描述不正确的是() A、有穷性:算法必须在有限步之内结束 B、确定性:算法的每一步必须确切的定义 C、输入:算法必须至少有一个输入 D、输出:算法必须至少有一个输出 8、下列哪一个不是用于程序设计的软件() A、BASIC B、C语言 C、Word D、Pascal 9、下列可以作为合作变量名的是() A、a7 B、7a C、a-3 D、8 10、编程求1+2+3+........+1000的和,该题设计最适合使用的控制结构为()。 A、顺序结构 B、分支结构 C、循环结构 D、选择结构 11、下列步骤不属于软件开发过程的是() A、任务分析与系统设计 B、软件的销售 C、代码编写与测试 D、软件测试与维护12.以下程序段运行时,语句k=k+1 执行的次数为()次。

算法设计与分析基础课后习题答案

Program算法设计与分析基础中文版答案 习题 5..证明等式gcd(m,n)=gcd(n,m mod n)对每一对正整数m,n都成立. Hint: 根据除法的定义不难证明: 如果d整除u和v, 那么d一定能整除u±v; 如果d整除u,那么d也能够整除u的任何整数倍ku. 对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n和r=m mod n=m-qn;显然,若d能整除n和r,也一定能整除m=r+qn和n。 数对(m,n)和(n,r)具有相同的公约数的有限非空集,其中也包括了最大公约数。故gcd(m,n)=gcd(n,r) 6.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次? Hint: 对于任何形如0<=m

设sqrt(x)是求平方根的函数) 算法Quadratic(a,b,c) 描述将十进制整数表达为二进制整数的标准算法 a.用文字描述 b.用伪代码描述 解答: a.将十进制整数转换为二进制整数的算法 输入:一个正整数n 输出:正整数n相应的二进制数 第一步:用n除以2,余数赋给Ki(i=0,1,2...),商赋给n 第二步:如果n=0,则到第三步,否则重复第一步 第三步:将Ki按照i从高到低的顺序输出 b.伪代码 算法 DectoBin(n) .n]中 i=1 while n!=0 do { Bin[i]=n%2; n=(int)n/2; i++; } while i!=0 do{ print Bin[i]; i--; } 9.考虑下面这个算法,它求的是数组中大小相差最小的两个元素的差.(算法略)对这个算法做尽可能多的改进. 算法 MinDistance(A[0..n-1])

算法与程序设计试题

算法与程序设计试题 一、选择题(每题两分,共14分每题2分) 1、要进行元旦晚会比赛,学校请你设计一个能够对元旦晚会节目分数自动排序的软件,你接到任务后,准备开始设计此软件,比较好的方法和步骤是() A、设计算法,编写程序,提出问题,调试程序 B、分析问题,编写程序,设计算法,调试程序 C、分析问题,设计算法,编写程序,调试程序 D、设计算法,提出问题,编写程序,调试程序 2、数值型数据包括两种。 A、整型和长整型 B、整型和浮点型 C、单精度型和双精度型 D、整型、实型和货币型 3、具有输出数据功能的控件是:() A、窗体控件和标签控件 B、复选框控件和文本框控件 C、标签控件和文本框控件 D、选项框按钮控件和复选框控件 4、要使循环体至少执行一次,应使用循环。 5、下列程序段是计算公式的: s=0;t=1 for I =1 to 10 t:=t*I s:=s+t Next I A、s=1+2+3+......10B、s=1*2*3* (10) C、s=1!+2!+3! ......10! D、s=1+2*3+3*4+4*5+......9*10 6、在窗体(Name属性为Formal)上画两个文本框(其Name属性分别为Text1和Text2)和一个命令按钮(Name属性为Command1),然后编写如下两个事件过程: Private Sub Command1_Click() A = Text1Text + Text2.Text Print a End Sub Private Sub Formal_Load() Text1.Text = " " Text2.Text = " " End Sub 程序运行后,在第一个文本框(Text1)和第二个文本框(Text2)中分别输入123和321,然后单击命令按钮,则输出结果为()。 A、444 B、321123 C、123321 D、132231 7、使用函数与过程是为了。 A、使程序模块化B、使程序易于阅读

解析算法和程序实现教学设计Word版

解析算法及程序实现教学设计 一、设计思想 根据《新课标》的要求,本课“解析算法”的学习目的是使学生进一步体验算法设计思想。为了让学生更易理解其算法的思想:用解析法找出数学表达式,用它来描述问题的原始数据与结果之间的关系。本堂课的设计思路:通过一元二次方程求解实例引入主题——认知主题——实践体验主题——扩展与提高这几个阶段层层深入的递进式方法使学生充分掌握解析算法。从而使学生形成解析算法的科学逻辑结构。 二、教材分析 本课的课程标准内容: 结合实例,经历分析问题、确定算法、编程求解等用计算机解决问题的基本过程,认识算法和程序设计在其中的地位和作用。掌握使用解析算法设计程序解决问题的方法基本要求:1.初步掌握解析算法。2.初步掌握解析算法的程序实现。 教材中很多例子,但是考虑到课时,具体采用了“计算1900年开始的任意一天是星期几”的问题。 三、学情分析 学生对程序的3种基本模式已有一个了解的基础,对于简单的程序段也有一定的认知意识。并且已学习了枚举算法,这对本节课的教学产生积极的作用。但学生还是会觉得算法设计比较难掌握,困难之处在于,如何将题目的设计思想转化为流程图,根据流程图写出相应的代码并通过自己编制程序上机实践来体验。因此在课堂分析过程中,学生应当从听课认识——分析理解——实践探究这些过程中全面掌握解析算法的设计思想,并能用此算法来解决日常生活问题及与其他学科有所关联的一些简单问题。 四、教学目标 知识与技能:理解解析算法的概念和特点,通过分析了解解析算法的解题结构,初步掌握对解析算法的程序实现。 过程与方法:通过具体问题分析,归纳解析算法的基本思想和方法,确定解题步骤。让学生理解如何用3步法来解决实际问题(提出问题——分析问题——解决问题); 情感态度与价值观:通过小组合作,增进学生间的学习交流,培养合作能力,激发学生学习能动性;感受解析算法的魅力,养成始终坚持、不断积累才能获得成功的意志品质。 五、重点与难点 重点:通过计算1900年开始的任意一天是星期几,让学生理解解析算法的思想,初步

高考算法与程序设计试题及答案

A .算法与程序设计 一、选择题(本大题共17小题,每题2分,共34分) 1.下列问题不能用算法描述的是 A.已知a 、b 、c 的值,求一元二次方程ax 2+bx+c=0(a ≠0)的实数解 B.计算某个班级英语成绩的平均分 C.列出方程y=2x+1的所有实数解 D.根据矩形的长和宽求面积 2.下列可以作为VB 变量名的是 A. A&s B. A+S C. AS D. A_s 3.将数学表达式 2 || y x x 写成VB 表达式正确的是 A.(y – Int (x ))/x*x B.(y – Abs (x ))/x^2 C.(y – Int (x ))/x^2 D.(y – Abs (x ))/ x*x 4. 某宾涫的房间号由5位字符组成(例如A0823表示A 幢8层23号房间)末位数字为奇数时表示房间朝南,为偶数时表示房间朝北,字符串变量s 中存储了1个房间号,下列能正确判断房间朝南的VB 表达式是 A.V al (Mid (s ,5,1))Mod 2 = 1 B. Val (Mid (s ,5,1))Mod 2 = 0 C. Val (Mid (s ,5,1))\ 2 = 1 D. V al (Mid (s ,5,1))\ 2 = 0 5.下列VB 表达式中:①Sin (x ) ②Text1.Text ③Label1.Caption ④Chr (x ) ⑤Asc (x ) 值为字符串型的是 A. ①③⑤ B. ①②③ C. ②④⑤ D. ②③④ 6.下列能准确表达“如果明天不下雨,那久我们骑车去郊游”的伪代码是 A .lf (明天下雨)Then (我们骑求去郊游) B .If (明天不下雨)Then (我们骑车去郊游)Else (我们不去郊游) C ,If (明天下雨)Then (我们不去郊游)Else (我们骑车去郊游) D .lf (明天不下雨)Then (我们骑车去郊游) 到a(10)中最小值min 程序段如 For i = 2 To 10 If a (i )< min Then min = a(i) Next i 方框中最合适的语句是 A. a (1)= min B. a (1)= 0 C. min = a(1) D. min = 0 8.某VB 的事件过程如下: Private Sub Command1_Click() Dim a As Integer a = Val(Text1.Text) a = 2 * a + 1 Text1.Text = Str(a) End Sub 程序运行时,在文本框Text1中输入1,连续两次单击命令按钮Command1后,Text1中显示的内容是 A. 7 B.5 C. 3 D. 1

算法分析与设计复习题及答案

算法分析与设计复习题及答案一、单选题 1.D 2.B 3.C 4.D 5.D 6.D 7.C 8.D 9.B 10.C 11.D 12.B 13.D 14.C 15.C 16.D 17.D 18.D 19.D 20.C 1.与算法英文单词algorithm具有相同来源的单词是()。 A logarithm B algiros C arithmos D algebra 2.根据执行算法的计算机指令体系结构,算法可以分为()。 A精确算法与近似算法B串行算法语并行算法 C稳定算法与不稳定算法D32位算法与64位算法 3.具有10个节点的完全二叉树的高度是()。 A6B5C3D 2 4.下列函数关系随着输入量增大增加最快的是()。 Alog2n B n2 C 2n D n! 5.下列程序段的S执行的次数为( )。 for i ←0 to n-1 do for j ←0 to i-1 do s //某种基本操作 A.n2 B n2/2 C n*(n+1) D n(n+1)/2 6.Fibonacci数列的第十项为( )。 A 3 B 13 C 21 D 34 7.4个盘子的汉诺塔,至少要执行移动操作的次数为( )。 A 11次 B 13次 C 15次 D 17次 8.下列序列不是堆的是()。 A 99,85,98,77,80,60,82,40,22,10,66 B 99,98,85,82,80,77,66,60,40,22,10 C 10,22,40,60,66,77,80,82,85,98,99 D 99,85,40,77,80,60,66,98,82,10,22 9.Strassen矩阵乘法的算法复杂度为()。 AΘ(n3)BΘ(n2.807) CΘ(n2) DΘ(n) 10.集合A的幂集是()。 A.A中所有元素的集合 B. A的子集合 C. A 的所有子集合的集合 D. 空集 11.与算法英文单词algorithm具有相同来源的单词是()。 A logarithm B algiros C arithmos D algebra 12.从排序过程是否完全在内存中显示,排序问题可以分为()。 A稳定排序与不稳定排序B内排序与外排序 C直接排序与间接排序D主排序与辅助排序 13.下列()不是衡量算法的标准。 A时间效率B空间效率 C问题难度D适应能力 14.对于根树,出度为零的节点为()。 A0节点B根节点C叶节点D分支节点 15.对完全二叉树自顶向下,从左向右给节点编号,节点编号为10的父节点编号为()。 A0B2C4D6 16.下列程序段的算法时间的复杂度为()。 for i ←0 to n do for j ←0 to m do

算法分析与设计习题集

算法分析与设计习题集 基础篇 1、算法有哪些特点?它有哪些特征?它和程序的主要区别是什么? 2、算法的时间复杂度指的是什么?如何表示? 3、算法的空间复杂度指的是什么?如何表示? 4、设某一函数定义如下: 编写一个递归函数计算给定x的M(x)的值。 本函数是一个递归函数,其递归出口是: M(x)= x-10x>100 递归体是: M(M(x+11))x ≤100 实现本题功能的递归函数如下: intm ( intx ) { int y; if ( x>100 )return(x-10 ); else { y =m(x+11) ; return (m (y )); } } 5、已知一个顺序表中的元素按元素值非递减有序排列,编写一个函数删除表中多余的值相 同的元素。 本题的算法思想是:由于顺序表中元素已按元素值非递减有序排列,值相同的元素比为相邻的元素,因此依次比较相邻两个元素,若值相等,则删除其中一个,否则继续向后查找,直到最后一个元素。实现本题功能的函数如下: voiddel ( seqlist*a ) { inti=0, j; while ( ilength) if ( a->data[i]!= a->data[i+1])i++; else { for ( j=i; jlength; j++)a->data[j]=a->data[j+1]; a->length--; } } 6、分别写出求二叉树结点总数及叶子总数的算法。

①计算结点总数 int CountNode(BinTree *root) { int num1,num2; if(root==Null) return(0); else if(root->lchild==Null&&rooot->rchild==Null) return(1); else { num1=CountNode(root->lchild); num2=CountNode(root->rchild); return(num1+num2+1); } } ②计算叶子总数 int CountLeafs(BinTree *root) { int num1,num2; if(root==Null) return(0); else if(root->lchild==Null&&root->rchild==Null) return(1); else { num1=CountLeafs(root->lchild); num2=CountLeafs(root->rchild); return(num1+num2); } } 分治术 7、有金币15枚,已知其中有一枚是假的,而且它的重量比真币轻。要求用一个天平将假 的金币找出来,试设计一种算法(方案),使在最坏情况下用天平的次数最少。 8、利用分治策略,在n个不同元素中找出第k个最小元素。 9、设有n个运动员要进行网球循环赛。设计一个满足以下要求的比赛日程表。 (1)每个选手必须与其它n-1选手各赛一次; (2)每个选手一天只能赛一次。 10、已知序列{503,87,512,61,908,170,897,275,652,462},写一个自底向上的 归并分类算法对该序列作升序排序,写出算法中每一次归并执行的结果。 void Merge(ElemType *r,ElemType *rf,int u,int v,int t) { f or(i=u,j=v,k=u;i

相关文档
相关文档 最新文档