件，当需要进行文件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;i {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; i 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 百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库通信数据结构第一章绪论习题(2)在线全文阅读。
相关推荐：