通信数据结构第一章绪论习题

第一章 绪论

一、选择题

1.以下数据结构中哪一个是非线性结构？( )

A. 队列 B. 栈 C. 线性表 D. 二叉树

2．设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，则数据结构A是（ ）。 A. 线性结构 B. 树型结构 C. 物理结构 D. 图型结构 3．下面程序的时间复杂为（ ）

for（i=1，s=0； i<=n； i++） {t=1；for(j=1；j<=i；j++) t=t*j；s=s+t；} A. O(n) B.O(n2) C. O(n3) D. O(n4) 4．数据的最小单位是（ ）。

A.数据项 B. 数据类型 C.数据元素 D. 数据变量

5．程序段s=i=0；do {i=i+1； s=s+i；}while(i<=n)；的时间复杂度为（ ）。

23

A. O(n) B. O(nlog2n) C. O(n) D. O(n/2) 6．下列程序段的时间复杂度为（ ）。

for(i=0； i

for(i=0； i

A. O(m*n*t) B. O(m+n+t) C. O(m+n*t) D. O(m*t+n) 7．下列程序段的时间复杂度为（ ）。

i=0，s=0； while (s

A. O(n1/2) B. O(n1/3) C. O(n) D. O(n2)

8．某程序的时间复杂度为（3n+nlog2n+n2+8）, 其数量级表示为（ ）。

2

A．O（n） B．O（nlog2n） C．O（n） D．O（log2n） 9．线性表是一个具有n个（）的有限序列。

A．表元素 B．字符 C．数据元素 D．数据项 10．从逻辑上可以把数据结构分为（ ） A.动态结构、静态结构 B.顺序结构、链式结构 C.线性结构、非线性结构 D.初等结构、构造型结构 11．关于算法的描述，不正确的是（ ） ．．．A.算法最终必须由计算机程序实现

B.所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 C.健壮的算法不会因非法的输入数据而出现莫名其妙的状态 D.算法的优劣与算法描述语言无关

12．在数据结构中，数据的基本单位是( ) A. 数据项 B. 数据元素 C. 数据对象 D. 数据文件 13．k=1;

for（i=0；i

for（j=0；j

A［i］［j］=k++；

上述程序段的时间复杂度为( )

1

A.O（n2） B.O（n） C.O（2n） D.O（1） 14．for（i=0；i

for（j=0；j

A［i］［j］=i*j；

上面算法的时间复杂度为( ) A.O(m2) B.O(n2) C.O(m×n) D.O(m+n） 15．从逻辑关系来看，数据元素的直接前驱为0个或1个的数据结构只能是（ ） A．线性结构 B.树形结构

C.线性结构和树型结构 D.线性结构和图状结构 16．下列程序的时间复杂度为（ ）

i=0；s=0； while（s

n） B.O（

2n） C.O（n） D.O（n2

）

17．数据结构中所定义的数据元素，是用于表示数据的（ ）

A.最小单位 B.最大单位 C.基本单位 D.不可分割的单位 18．数据的四种基本存储结构是指（ ）

A.顺序存储结构、索引存储结构、直接存储结构、倒排存储结构 B．顺序存储结构、索引存储结构、链式存储结构、散列存储结构 C．顺序存储结构、非顺序存储结构、指针存储结构、树型存储结构 D.顺序存储结构、链式存储结构、树型存储结构、图型存储结构 19．下列四种基本的逻辑结构中，结构结点间不存在．．．任何逻辑联系的是（ A.集合 B.线性结构 C.树形结构 D.图形结构 20．下列说法正确的是（ ） A．数据是数据元素的基本单位

B．数据元素是数据项中不可分割的最小标识单位 C．数据可由若干个数据元素构成 D．数据项可由若干个数据元素构成 21．数据结构的基本任务是（ ）

A．逻辑结构和存储结构的设计 B．数据结构的运算实现 C．数据结构的评价与选择 D．数据结构的设计与实现 22．一个数组元素a[i]与（ ）的表示等价。

A. *(a+i) B. a+i C. *a+i D. &a+i

23．对于两个函数，若函数名相同，但只是（ ）不同则不是重载函数。A.参数类型 B. 参数个数 C.函数类型

24．若需要利用形参直接访问实参，则应把形参变量说明为（ ）参数 A. 指针 B.引用 C.值

25．下面程序段的时间复杂度为（ ）。 for(int i=0; i

for(int j=0; j

2

） A. O(m2) B. O(n2) C. O(m*n) D. O(m+n) 26．执行下面程序段时，执行S语句的次数为（ ）。 for(int i=1; i<=n; i++)

for(int j=1; j<=i; j++) S;

A. n2 B. n2/2 C. n(n+1) D. n(n+1)/2 27．下面算法的时间复杂度为（ ）。 int f( unsigned int n ) {

if ( n==0 || n==1 ) return 1; else return n*f(n-1); }

2

A. O(1) B. O(n) C. O(n) D. O(n!) 28．组成数据的基本单位是（ ）

A.数据项 B.数据类型 C．数据元素 D．数据变量 29．如某数据结构的数据元素的集合为S={A,B,C,D,E,F,G}，数据元素间的关系为R={,,,,,}，则该数据结构是一种（ ）。 A．线性结构 B．树结构 C．链表结构 D．队列结构 30．下面程序段的时间复杂度为（ ）。 for(i=1;i<=n;i++) for(j=i;j<=n;j++) s++; A．O(1)

B．O(n) C．O(nlogn2) D．O(n2)

31．算法分析的目的是（ ）

A.找出数据结构的合理性 B.研究算法中的输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档特点 32．算法的计算量的大小称为计算的（ ）。

A．效率 B. 复杂性 C. 现实性 D. 难度 33．多项选择：一个算法具有（ ）等特点。 A．可行性 B.至少有一个输入量 C. 确定性 D. 健壮性 34．下面说法错误的是（ ）

(1)算法原地工作的含义是指不需要任何额外的辅助空间

（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法

（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 35．在数据结构中，从逻辑上可以将之分为( )。

A．动态结构和静态结构 B. 紧凑结构和非紧凑结构 C. 内部结构和外部结构 D. 线性结构和非线性结构 36．以下数据结构中，哪一个是线性结构（ ）。

A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 37．数据结构中数据元素之间的逻辑关系被称为( )。 A．数据的存储结构 B. 数据的基本操作 C. 程序的算法 D. 数据的逻辑结

3

构

38．在下面的程序段中，对x的赋值语句的频度为（ ） FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1;

A． O(2n) B．O(n) C．O(n2) D．O(log2n) 39．以下哪个数据结构不是多型数据类型（ ）

A．栈 B．广义表 C．有向图 D．字符串 40．下列数据中，（ ）是非线性数据结构。

A．栈 B. 队列 C. 完全二叉树 D. 堆 41．以下属于逻辑结构的是（ ）。

A．顺序表 B. 哈希表 C.有序表 D. 单链表 42．计算算法的时间复杂度是属于一种( )。 A.事前统计的方法B.事前分析估算的方法 C.事后统计的方法 D.事后分析估算的方法 43．可以用( )定义一个完整的数据结构:

A.数据元素 B.数据对象 C.数据关系 D.抽象数据类型 44．多项选择：数据结构研究的内容涉及( )。 A.数据如何组织 B.数据如何存储

C.数据的运算如何实现 D.算法用什么语言来描述 45．算法分析的目的是（ ）。

A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系

C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性 46．多项选择： 设计一个“好”的算法应考虑达到的目标有（ ）。 A. 是可行的 B. 是健壮的 C.无二义性 D.可读性好

47．计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（ B ）等5个特性。

A.可执行性、可移植性和可扩充性 B.可执行性、有穷性和确定性 C.确定性、有穷性和稳定性 D.易读性、稳定性和确定性 48．具有线性结构的数据结构是（D ）

A. 图 B.树 C.广义表 D.栈 49．算法分析的目的是（ C ）

A.找出数据结构的合理性 B.研究算法中的输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档特点

二、填空题

1．通常从四个方面评价算法的质量：_________、_________、_________和_________。正确性 易读性 强壮性 高效率

3222．一个算法的时间复杂度为(n+nlog2n+14n)/n，其数量级表示为________。O(n) 3．数据的物理结构主要包括_____________和______________两种情况。顺序存储结构、链式存储结构

4．数据结构从逻辑上划分为三种基本类型：___________、__________和___________。线性结构，树型结构，图型结构

4

5．for(i=1，t=1，s=0；i<=n；i++) {t=t*i；s=s+t；}的时间复杂度为_________。O(n)

6．数据结构是研究数据元素之间抽象化的相互关系和这种关系在计算机中的存储结构表示，根据数据元素之间关系的不同特性，通常有下列四类基本结构：集合、线性结构、 和 。 7．评价算法的标准很多，通常是以执行算法所需要的 和所占用的 来判别一个算法的优劣。

8. 数据的存储结构被分为____________、___________、____________和____________四种。顺序结构、链接结构、索引结构、散列结构 9．一个算法应具备的5个特性为 、 、 、

、 。有穷性、确定性、可行性、输入、输出

10．在任何问题中，数据元素都不是孤立的，它们之间总存在某种关系，通常称这种关系为____ ____。逻辑关系

11．存储结点通常有四种基本存储方式，即顺序存储方式、索引存储方式、___ ____和散列存储方式。链式存储

12．数据的逻辑结构通常包括集合、线性结构、___ _________和图状结构。树结构

13．如果操作不改变原逻辑结构的“值”，而只是从中提取某些信息作为运算结果，则称该类运算为_____ _____型运算。引用

14．在数据结构中，各个结点按逻辑关系互相缠绕，任意两个结点可以邻接的结构称为____ ___。图结构

15．每个存储结点只含一个数据元素，所有存储结点连续存放。此外增设一个索引表，索引表中的索引指示各存储结点的存储位置或位置区间端点。按这种方式组织起来的存储结构称为__ _____。索引结构

16．通常从正确性、易读性、_____ ___和高效率等4个方面评价算法（包括程序）的质量。健壮

17．顺序表的存储密度为___100%_____，而链表的存储密度为__<100%______。 18．表示逻辑关系的存储结构可以有四种方式，即顺序存储方式、链式存储方式、______ _________和散列存储方式。索引存储方式

19．数据表示和__________是程序设计者所要考虑的两项基本任务。算法设计 20．在线性结构、树形结构和图形结构中，前驱和后继结点之间分别存在着________、________和________的联系。1:1、1:N、M:N

21．一种抽象数据类型包括__________和__________两个部分。数据定义、操作声明

22．当一个形参类型的长度较大时，应最好说明为_________，以节省参数值的传输时间和存储参数的空间。引用形参 ( 或 指针形参 )

23．当需要用一个形参访问对应的实参时，则该形参应说明为__________。引用类型 ( 或 指针类型 )

24．在函数中对引用形参的修改就是对相应__________的修改，对__________形参的修改只局限在该函数的内部，不会反映到对应的实参上。实参、值

25．当需要进行标准I/O操作时，则应在程序文件中包含________________头文

5

件，当需要进行文件I/O操作时，则应在程序文件中包含________________头文件。iostream.h 、fstream.h

26．在包含有________________头文件的程序文件中，使用________________能够产生出0～20之间的一个随机整数。stdlib.h 、rand( ) !

27．一个数组a所占有的存储空间的大小即数组长度为____________，下标为i的元素a[i]的存储地址为__________，或者为______________________________。sizeof(a)、a+i*sizeof(a[0])、a+i

28．函数重载要求____________、____________或____________有所不同。参数类型、数量、次序

29．对于双目操作符，其重载函数带有__________个参数，其中至少有一个为____________的类型。2、用户自定义

30．若对象ra和rb中至少有一个是属于用户定义的类型，则执行ra==rb时，需要调用__________重载函数，该函数的第一个参数应与__________的类型相同，第二个参数应与__________的类型相同。= = 、ra 、rb

31．从一维数组a[n]中顺序查找出一个最大值元素的时间复杂度为________，输出一个二维数组b[m][n]中所有元素值的时间复杂度为________。O(n)、O(m*n)

32．在下面程序段中，s=s+p语句的执行次数为________，p*=j语句的执行次数为________，该程序段的时间复杂度为________。 int i=0,s=0; while(++i<=n) { int p=1;

for(int j=1;j<=i;j++) p*=j; s=s+p;

} n、n(n+1)/2、O(n2)

33．一个算法的时间复杂度为(3n2+2nlog2n+4n-7)/(5n)，其数量级表示为________。O(n)

34．数据结构讲述的三大关系是 、 、 。一对一的线性关系 一对多的树关系 多对多的图关系

35．已知某算法的执行时间为n+n2,n代表问题规模，则该算法的时间复杂度

2

是 。．O(n);

36．数据结构有线性结构、树结构、 、 等几种逻辑结构。图结构;集合;

37. 数据结构中，非线性逻辑结构有 、 、 。 集合 、 树 、 图

38. 数据的逻辑结构是指 。数据的组织形式，即数据元素之间逻辑关系的总体。而逻辑关系是指数据元素之间的关联方式或称“邻接关系”。 39. 一个数据结构在计算机中 称为存储结构。表示（又称映像）。 40. 数据结构中评价算法的两个重要指标是 算法的时间复杂度和空间复杂度。

41. 一个算法具有5个特性: （1） 、 （2） 、 （3） ，有零个或多个输入、有一个或多个输出 。（1）有穷性 （2）确定性（3）可行性。 42. 下面程序段中带下划线的语句的执行次数的数量级是( )。 i. i:=1;

6

b) WHILE i

43. 下面程序段的时间复杂度为________。(n>1) i. sum=1；

ii. for (i=0;sum

a) ①以下是该函数的程序段，请将未完成的部分填入，使之完整 1. int f(m,n) a) int m,n; 2. {if(m==1)

return (1) ; if(n==1){

return (2) ;} if(m

{return f(m,m);} if (m==n)

{return 1+ (3) ;}

return f(m,n-1)+f(m-n, (4) ); }

②执行程序，f(6,4)= 。

① (1)1 (2)1 (3)f(m,n-1) (4)n ② 9

45. 设有两个算法在同一机器上运行，其执行时间分别为100n2和2n，要使前者快于后者，n至少为（ ）。

(当n<=14时,100n2>2n,而n>=15时100n2<2n)

46. 作为一个算法输入的数据所含数据元素的数目，或与此数目有关的其他参数，称为__ ______。问题规模_

三、判断题

1．( )如果某数据结构的每一个元素最多只有一个直接前驱，则其必为线性表。×

2．( )一个程序的时间复杂度是指该程序运行时间与问题规模的对应关系√ 3．（ ）数据元素是数据的最小单元。 × 4．（ ）数据的基本单位是数据项。╳ 5．（ ）数组元素之间的关系，既不是线性的，也不是树形的。√ 6．（ ）算法和程序没有区别，所以在数据结构中二者是通用的。× 7．（ ）算法的优劣与算法描述语言无关，但与所用计算机有关。 × 四、简答题

1．简述下列概念

数据，数据元素，数据类型，数据结构，逻辑结构，存储结构，算法。

【解答】数据是信息的载体，是描述客观事物的数、字符，以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。

数据元素是数据的基本单位。在不同的条件下，数据元素又可称为元素、结点、

7

顶点、记录等。

数据类型是对数据的取值范围、数据元素之间的结构以及允许施加操作的一种总体描述。每一种计算机程序设计语言都定义有自己的数据类型。

“数据结构”这一术语有两种含义，一是作为一门课程的名称；二是作为一个科学的概念。作为科学概念，目前尚无公认定义，一般认为，讨论数据结构要包括三个方面，一是数据的逻辑结构，二是数据的存储结构，三是对数据进行的操作（运算）。而数据类型是值的集合和操作的集合，可以看作是已实现了的数据结构，后者是前者的一种简化情况。

数据的逻辑结构反映数据元素之间的逻辑关系（即数据元素之间的关联方式或“邻接关系”），数据的存储结构是数据结构在计算机中的表示，包括数据元素的表示及其关系的表示。数据的运算是对数据定义的一组操作，运算是定义在逻辑结构上的，和存储结构无关，而运算的实现则依赖于存储结构。

数据结构在计算机中的表示称为物理结构，又称存储结构。是逻辑结构在存储器中的映像，包括数据元素的表示和关系的表示。逻辑结构与计算机无关。

算法是对特定问题求解步骤的一种描述，是指令的有限序列。其中每一条指令表示一个或多个操作。一个算法应该具有下列特性：有穷性、确定性、可行性、输入和输出。

2． 数据的逻辑结构分哪几种，为什么说逻辑结构是数据组织的主要方面？ 【解答】数据的逻辑结构分为线性结构和非线性结构。（也可以分为集合、线性结构、树形结构和图形即网状结构）。

逻辑结构是数据组织的某种“本质性”的东西： （1）逻辑结构与数据元素本身的形式、内容无关。 （2）逻辑结构与数据元素的相对位置无关。 （3）逻辑结构与所含数据元素的个数无关。

3．试举一个数据结构的例子，叙述其逻辑结构、存储结构、运算三方面的内容。 【解答】学生成绩表，逻辑结构是线性结构，可以顺序存储（也可以链式存储），运算可以有插入、删除、查询，等等。

4．简述算法的五个特性，对算法设计的要求。

【解答】算法的五个特性是：有穷性、确定性、可行性、零至多个输入和一至多个输出。

对算法设计的要求：正确性，易读性，健壮性，和高的时空间效率（运算速度快，存储空间小）。

5．设n是正整数，求下列程序段中带@记号的语句的执行次数。 (1)i=1;k=0; (2) i=1;j=0;

while(i

{k=k+50*i; i++; @ {if(i>j)j++; @ } else i++; } @ (3)x=y=0; (4)x=91;y=100; for(i=0;i0) for(j=0;j100)

{x++; @ {x=x-10; y--; @ for(k=0;k

y++; @ else x++; @ }

8

【解答】(1)n-1

(2)i= n/2(上取整） ，j=n/2（下取整） (3)n+1, n(n+1), n2,(n+1)n2, n3 (4)100, 1000

6．数据结构与数据类型有什么区别？

【解答】“数据结构”这一术语有两种含义，一是作为一门课程的名称；二是作为一个科学的概念。作为科学概念，目前尚无公认定义，一般认为，讨论数据结构要包括三个方面，一是数据的逻辑结构，二是数据的存储结构，三是对数据进行的操作（运算）。而数据类型是值的集合和操作的集合，可以看作是已实现了的数据结构，后者是前者的一种简化情况。 7．下面程序段的时间复杂度是什么？ for(i=0;i

for(j=0;,j

8．运算是数据结构的一个重要方面。试举一例，说明两个数据结构的逻辑结构和存储方式完全相同，只是对于运算的定义不同。因而两个结构具有显著不同的特性，是两个不同的结构。 【解答】栈和队列的逻辑结构相同，其存储表示也可相同（顺序存储和链式存储），但由于其运算集合不同而成为不同的数据结构。

9．试举一例，说明对相同的逻辑结构,同一种运算在不同的存储方式下实现，其运算效率不同。 【解答】线性表中的插入、删除操作，在顺序存储方式下平均移动近一半的元素，时间复杂度为O（n）；而在链式存储方式下，插入和删除时间复杂度都是O（1）。

n

10．有实现同一功能的两个算法A1和A2，其中A1的时间复杂度为Tl=O(2)，A2的时间复杂度为T2=O(n2)，仅就时间复杂度而言，请具体分析这两个算法哪一个好。

【解答】对算法A1和A2的时间复杂度T1和T2取对数，得nlog2和2logn。显然，当n<4时，算法A1好于A2；当n=4时，两个算法时间复杂度相同；当n>4时，算法A2好于A1。

11．设n是偶数，且有程序段： For i:=1 to n Do

if 2*i<=n Then For j:=2*i to n Do y:=y+i*j; 则语句“y:=y+i*j”的执行次数多少？要求列出计算公式。

【解答】n2/4。 语句“y:=y+i*j”在“i=1”时执行n-1次，在“i=2”时执行n-3次，??，最后当“i=n/2”时执行1次，当“i>n/2”就不再执行。故总的执行次数为：

(n-1)+(n-3)+?+3+1=(n/2)2=n2/4

第一层for循环判断n+1次，往下执行n次，第二层for执行次数为(n+(n-1)+(n-2)+?+1)，第三层循环体受第一层循环和第二层循环的控制，其执行次数如下表：

i= 1 2 3 ? n j=n n n n ? n j=n-1 n-1 n-1 n-1 ? ? ? ? ?

9

j=3 3 3 j=2 2 2 j=1 1

12．调用下列C函数f(n)(编者注：略去PASACAL函数f(n)) 回答下列问题 : 试指出f(n)值的大小，并写出f(n) 值的推导过程;

假定n= 5，试指出f(5)值的大小和执行f(5)时的输出结果。 C函数： int f(int n) { int i,j，k,sum= 0; for(i=l; ii-1; j--)

1. for(k=1;k

3. printf(\； }

return (sum); }

2

【解答】执行次数为(1+2+?+n)+(2+3+?+n)+?+n=n*n(n+1)/2-n(n-1)/6。在n=5时，f(5)=55，执行过程中，输出结果为： sum=15 sum=29 sum=41 sum=50 sum=55 13．设n是偶数，试计算运行下列程序段后m的值并给出该程序段的时间复杂度。 m:=0;

FOR i:=1 TO n DO FOR j:=2*i TO n DO m:=m+1;

2

【解答】O(n),m的值等于赋值语句m:=m+1的运行次数，其计算式为

五、应用题 第一章 绪论

1．在如下数组A中链接存储了一个线性表，表头指针为A [0].next，试写出该线性表。

A 0 1 2 3 4 5 6 7 data 60 50 78 90 34 40 next 3 5 7 2 0 4 1 【解答】线性表为：（78，50，40，60，34，90） 2. 设指针变量p指向双向链表中结点A，指针变量q指向被插入结点B，要求给出在结点A的后面插入结点B的操作序列（设双向链表中结点的两个指针域分别为llink和rlink）。

【解答】q->llink=p; q->rlink=p->rlink; p->rlink->llink=q; p->rlink=q; 3．斐波那契数列Fn定义如下

10

F0=0， Fl=1， Fn=Fn-1+Fn-2, n=2,3... 请就此斐波那契数列，回答下列问题。

(1) 在递归计算Fn的时候，需要对较小的Fn-1，Fn-2，?, Fl, F0精确计算多少次? (2) 如果用大O表示法，试给出递归计算Fn时递归函数的时间复杂度录多少? 【解答】

（1）由斐波那契数列的定义可得： 1. Fn=Fn-1+Fn-2 =2Fn-2+Fn-3 =3Fn-3+2Fn-4 =5Fn-4+3Fn-5 ?? =pF1+qF0

设Fm的执行次数为Bm(m=0、1、2、?、n-1)，由以上等式可知，Fn-1被执行一次，即Bn-1=1；Fn-2被执行两次，即Bn-2=2；直至F1被执行p次、F0被执行q次，即B1=p，B0=q。Bm的执行次数为前两等式第一因式系数之和，即Bm=Bm-1+Bm-2，再有Bn-1=1和Bn-2=2，这也是一个斐波那契数列。可以解得：

（2）时间复杂度为O(n)

六、程序填空题（或算法阅读题） 1．void DD ( ) {

ElemType A[ ]={1,3,5,7,9,2,4,6,8,10},B[10]; TwoMerge(A, B,0,4,9);

for ( int i=0; i<10; i++) cout<

调用该算法后，输出结果为：

【解答】1 2 3 4 5 6 7 8 9 10 七、算法设计题

1. 已知输入x，y，z三个不相等的整数，设计一个“高效”算法，使得这三个数按从小到大输出。“高效”的含义是用最少的元素比较次数、元素移动次数和输出次数。 【解答】 void Best()

{//按序输出三个整数的优化算法 int a,b,c,t;

scanf(“%d%d%d”,&a,&b,&c); if(a>b)

11

{t=a; a=b; b=t:} //a和b已正序 if(b>c)

{t=c; c=b; //c已到位

if(a>t) {b=a; a=t;} //a和b已正序 else b=t; }

printf(“%d,%d,%d\\n”,a,b,c);

//最佳2次比较，无移动；最差3次比较，7个赋值 }

2. 在数组A[n]中查找值为k的元素，若找到则输出其位置i(1≤i≤n)，否则输出0作为标志。设计算法求解此问题，并分析在最坏情况下的时间复杂度。 【题目分析】从后向前查找，若找到与k值相同的元素则返回其位置，否则返回0。

【解答】

int Search(ElemType A[n+1], ElemType k) {i=n;

while(i>=1)&&(A[i]!=k)) i--; if(i>=1) return i; else return 0; }

当查找不成功时，总的比较次数为n+1次，所以最坏情况下时间复杂度为O(n)。

在学过第 9 章 “查找”后，可优化以上算法:设“监视哨”。算法如下： int Search(ElemType A[n+1], ElemType k) {i=n; A[0]=k;

while(A[i]!=k) i--; return i; }

研究表明，当n>=1000时，算法效率提高50%。

12

本文来源：https://www.bwwdw.com/article/7343.html