___________。线性结构，树型结构，图型结构 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．在函数中对引用形参的修改就是对相应__________的修改，对__________形参的修改只局限在该函数的内部，不会反映到对应的实参上。实参、值
5
25．当需要进行标准I/O操作时，则应在程序文件中包含________________头文件，当需要进行文件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代表问题规模，则该算法的时间复杂度是 。．O(n2);
36．数据结构有线性结构、树结构、 、 等几种逻辑结构。图结构;集合;
37. 数据结构中，非线性逻辑结构有 、 、 。 集合 、 树 、 图
38. 数据的逻辑结构是指 。数据的组织形式，即数据元素之间逻辑关系的总体。而逻辑关系是指数据元素之间的关联方式或称“邻接关系”。 39. 一个数据结构在计算机中 称为存储结构。表示（又称映像）。 40. 数据结构中评价算法的两个重要指标是 算法的时间复杂度和空间复杂度。
41. 一个算法具有5个特性: （1） 、 （2） 、 （3） ，有零个或多个输入、有一个或多个输出 。（1）有穷性 （2）确定性（3）可行性。 42. 下面程序段中带下划线的语句的执行次数的数量级是( )。
6
i. i:=1;
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;i {x++; @ {x=x-10; y--; @ for(k=0;k y++; @ else x++; @ 8
