数据结构练习-第一章-绪论.docx

数据结构练习第一章绪论一、选择题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,0>,<03,07>,<03,08>,<03,09»,那么数据结构A是()。A.线性结构B.树型结构C.物理结构D.图型结构3 .下面程序的时间复杂为()for(i=l,s=0；i<=n；i+)t=l:for(j=l；j<=i;j+)t=t*j;s=s+t;A.0(n)B.0(n2)C.0(n)D.0(n,)4 .数据的最小单位是()。A.数据项B.数据类型C.数据元素D.数据变量5 .程序段s=i=0;doi=i+l;s=s÷i;)while(i<=n)；的时间复杂度为()。A.0(n)B.0(nlog2n)C.0(n2)D.0(n32)6 .以下程序段的时间复杂度为()。for(i=0;i<m；i+)for(j=0;j<t;j+)cij=0;for(i=0；i<m；i+)for(j=0；j<t；j+)for(k=0；k<n；k+)cij=cij+aik*bkj;A.0(m*n*t)B.0(m+n+t)C.0(m+n*t)D.0(m*t+n)7 .以下程序段的时间复杂度为()oi=0,s=0；while(s<n)s=s+i;i+；A.0(n,z2)B.0(nz3)C.0(n)D.0(n2)8 .某程序的时间复杂度为(3n+nlog2n÷n2+8),其数量级表示为()。A.0(n)B.0(nlog2n)C.0(n2)D.0(log2n)9 .线性表是一个具有n个()的有限序列。A.表元素B.字符C.数据元素D.数据项10 .从逻辑上可以把数据结构分为()A.动态结构、静态结构B.顺序结构、链式结构C.线性结构、非线性结构D.初等结构、构造型结构11 .关于算法的描述，不正确的选项是()A.算法最终必须由计算机程序实现B.所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界C健壮的算法不会因非法的输入数据而出现莫名其妙的状态D.算法的优劣与算法描述语言无关12.在数据结构中，数据的根本单位是()A.数据项B.数据元素C.数据对象D.数据文件13. k=l;for(i=0；i<n；i+)for(j=0；j<n；j+)Aij=k+÷上述程序段的时间复杂度为()A.O(n2)B,O(n)C.O(2n)D.O(1)14. for(i=0；i<m；i+)for(j=0；j<n；j+)Aij=i*j;上面算法的时间复杂度为()A.0(m2)B.0(n2)C.0(m×n)D.0(m+n)15 .从逻辑关系来看，数据元素的直接前驱为0个或1个的数据结构只能是()A,线性结构B.树形结构C.线性结构和树型结构D.线性结构和图状结构16 .以下程序的时间复杂度为()i=0；s=0;while(s<n)i+;s=s+i;)A. 0 ( )B.0C.0 (n) D.0 (n2)17.数据结构中所定义的数据元素,A.最小单位B.最大单位是用于表示数据的()C,根本单位D,不可分割的单位18 .数据的四种根本存储结构是指()A.顺序存储结构、索引存储结构、直接存储结构、倒排存储结构B.顺序存储结构、索引存储结构、链式存储结构、散列存储结构C.顺序存储结构、非顺序存储结构、指针存储结构、树型存储结构D.顺序存储结构、链式存储结构、树型存储结构、图型存储结构19 .以下四种根本的逻辑结构中，结构结点间不奇有任何逻辑联系的是()A.集合B.线性结构C.树形结构D.图形结构20 .以下说法正确的选项是().数据是数据元素的根本单位B.数据元素是数据项中不可分割的最小标识单位C.数据可由假设干个数据元素构成D.数据项可由假设干个数据元素构成21 .数据结构的根本任务是( A.逻辑结构和存储结构的设计 C.数据结构的评价与选择22 . 一个数组元素ai与(A. *(a+i) B. a+iB.数据结构的运算实现D.数据结构的设计与实现 )的表示等价。C. *a÷iD. &a+i23 .对于两个函数，假设函数名相同，但只是()不同那么不是重载函数。A.参数类型B.参数个数C.函数类型24 .假设需要利用形参直接访问实参，那么应把形参变量说明为()参数A.指针B.引用C.值25 .下面程序段的时间复杂度为()。for(inti=0;i<m;i+)for(intj=0;j<n;j+)aij=i*j;A.0(m2)B.0(n2)C.0(m*n)D.0(m+n)26 .执行下面程序段时，执行S语句的次数为()。for(inti=l;i<=n;i+)for(intj=l;j<=i;j+)A. n2S;B. n2227 .下面算法的时间复杂度为(intf( unsigned int if ( n=0 I I n=lC. n(n+l)On ) )return1；), 0(1)B. 0(n)C. 0(n2)D. n(n+l)2else return n*f(n-l);D. 0(n!)28 .组成数据的根本单位是()A.数据项 B.数据类型C.数据元素D.数据变量29 .如某数据结构的数据元素的集合为S=A, B, C, D, E, F, G,数据元素间的关系为 R=<A, D>, <A, G>, <D, B>, <D, O, <G, E>, <G, F>,那么该数据结构是一种()<>A.线性结构B.树结构 C.链表结构30 .下面程序段的时间复杂度为()ofor(i=l;i<=n;i+)for(j=i;j<=n;j+)I).队列结构s+;A, 0(1)B. 0(n) C. 0(nlog) D, 0(n2)31 .算法分析的目的是( A找出数据结构的合理性 C.分析算法的效率以求改良)B.研究算法中的输入和输出的关系D.分析算法的易懂性和文档特点32 .算法的计算量的大小称为计算的()。.效率B,复杂性 C.现实性D,难度33 .多项选择：一个算法具有()等特点。A.可行性B.至少有一个输入量C.确定性D.健壮性34 .下面说法错误的选项是()算法原地工作的含义是指不需要任何额外的辅助空间(2)在相同的规模n下，复杂度0(n)的算法在时间上总是优于复杂度0(2。)的算法(3)所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界(4)同一个算法，实现语言的级别越高，执行效率就越低. (1) B. (1), (2) C. (1), (4) D. (3)35 .在数据结构中，从逻辑上可以将之分为()。A.动态结构和静态结构B.紧凑结构和非紧凑结构C.内部结构和外部结构D,线性结构和非线性结构36 .以下数据结构中，哪一个是线性结构()。.广义表B.二叉树 C.稀疏矩阵D.串37 .数据结构中数据元素之间的逻辑关系被称为()。A.数据的存储结构B.数据的根本操作C.程序的算法 I).数据的逻辑结构38 .在下面的程序段中，对X的赋值语句的频度为()FOR i:=l TO n DO FOR j:=l TO n DO x:=x+l;. 0(2n) B. 0(n)C. 0(n2)D. 0(log2n)39 .以下哪个数据结构不是多型数据类型（）A.栈B.广义表C.有向图D.字符串40 .以下数据中，（）是非线性数据结构。A.栈B.队列C.完全二叉树D.堆41 .以下属于逻辑结构的是（）。A.顺序表B.哈希表C.有序表D.单链表42,计算算法的时间复杂度是属于一种（）oA.事前统计的方法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.可执行性、可移植性和可扩充性C.确定性、有穷性和稳定性48.具有线性结构的数据结构是（DB.可执行性、有穷性和确定性D.易读性、稳定性和确定性A.图B.树）C.广义表D.栈49.算法分析的目的是（ A.找出数据结构的合理性 C.分析算法的效率以求改良）B.研究算法中的输入和输出的关系D.分析算法的易懂性和文档特点二、填空题1 .通常从四个方面评价算法的质量：、和o正确性易读性强壮性高效率2 .一个算法的时间复杂度为（/+/log?加14）/炉，其数量级表示为O0（n）3 .数据的物理结构主要包括和两种情况。顺序存储结构、链式存储结构4 .数据结构从逻辑上划分为三种根本类型：、和线性结构，树型结构，图型结构5 .for（i=l,t=l,s=0；i<=n；i+）t=t*i;s=s+t;的时间复杂度为。0（n）6 .数据结构是研究数据元素之间抽象化的相互关系和这种关系在计算机中的存储结构表示，根据数据元素之间关系的不同特性，通常有以下四类根本结构：集合、线性结构、和O7 .评价算法的标准很多，通常是以执行算法所需要的和所占用的来判别一个算法的优劣。8 .数据的存储结构被分为、和四种。顺序结构、链接结构、索引结构、散列结构9 一个算法应具备的5个特性为、O有穷性、确定性、可行性、输入、输出10 .在任何问题中，数据元素都不是孤立的，它们之间总存在某种关系，通常称这种关系为o逻辑关系11 .存储结点通常有四种根本存储方式，即顺序存储方式、索引存储方式、和散列存储方式。链式存储12 .数据的逻辑结构通常包括集合、线性结构、和图状结构。树结构13 .如果操作不改变原逻辑结构的“值”，而只是从中提取某些信息作为运算结果，那么称该类运算为型运算。引用14 .在数据结构中，各个结点按逻辑关系互相缠绕，任意两个结点可以邻接的结构称为_o图结构15 .每个存储结点只含一个数据元素，所有存储结点连续存放。此外增设一个索引表，索引表中的索引指示各存储结点的存储位置或位置区间端点。按这种方式组织起来的存储结构称为o索引结构16 .通常从正确性、易读性、和高效率等4个方面评价算法(包括程序)的质量。健壮17 .顺序表的存储密度为100%,而链表的存储密度为<100%。18 .表示逻辑关系的存储结构可以有四种方式，即顺序存储方式、链式存储方式、-和散列存储方式。索引存储方式19 .数据表示和是程序设计者所要考虑的两项根本任务。算法设计20 .在线性结构、树形结构和图形结构中，前驱和后继结点之间分别存在着、和的联系。1:1、1：N、M:N21 .一种抽象数据类型包括和两个局部。数据定义、操作声明22 .当一个形参类型的长度较大时，应最好说明为以节省参数值的传输时间和存储参数的空间。引用形参(或指针形参)23 .当需要用一个形参访问对应的实参时，那么该形参应说明为。引用类型(或指针类型)24 .在函数中对引用形参的修改就是对相应的修改，对形参的修改只局限在该函数的内部，不会反映到对应的实参上。实参、值25 .当需要进行标准I/O操作时，那么应在程序文件中包含头文件，当需要进行文件I/O操作时，那么应在程序文件中包含头文件。iostream,h、fstream,h26 .在包含有头文件的程序文件中，使用能够产生出020之间的一个随机整数。stdlib.h、rand()%2127 .一个数组a所占有的存储空间的大小即数组长度为,下标为i的元素ai的存储地址为,或者为osizeof(a).a+i*sizeof(a0)>a+i28 .函数重载要求、或有所不同。参数类型、数量、次序29 .对于双目操作符，其重载函数带有个参数，其中至少有一个为的类型。2、用户自定义30 .假设对象ra和rb中至少有一个是属于用户定义的类型，那么执行ra=rb时;需要调用重载函数，该函数的第一个参数应与的类型相同，第二个参数应与的类型相同。二二、ra、rb31 .从一维数组an中顺序查找出一个最大值元素的时间复杂度为,输出一个二维数组bmn中所有元素值的时间复杂度为o0(n)>0(m*n)32 .在下面程序段中，s=s+p语句的执行次数为p*=j语句的执行次数为该程序段的时间复杂度为Ointi=0,s=0;while(+i<=n)intp=l;for(intj=l;j<=i;j+)p*=j;s=s+p;nn(n+l)/20(n2)33 .一个算法的时间复杂度为(37+2log2T?+4/?7)/(5)，其数量级表示为一。0(n)34 .数据结构讲述的三大关系是、。一对一的线性关系一对多的树关系多对多的图关系35 .某算法的执行时间为n+n2,n代表问题规模，那么该算法的时间复杂度是0.0(n2);36 .数据结构有线性结构、树结构、等几种逻辑结构。图结构;集合;37 .数据结构中，非线性逻辑结构有、。、树、图38 .数据的逻辑结构是指。数据的组织形式，即数据元素之间逻辑关系的总体。而逻辑关系是指数据元素之间的关联方式或称“邻接关系”。39 .一个数据结构在计算机中称为存储结构。表示(又称映像)。40 .数据结构中评价算法的两个重要指标是算法的时间复杂度和空间复杂度。41 .一个算法具有5个特性：(1)、，有零个或多个输入、有一个或多个输出。(1)有穷性(2)确定性(3)可行性。42 .下面程序段中带下划线的语句的执行次数的数量级是()。1. i:=l;b) WHILEi<nBEGINFORj:=lTOnDox:=x+l;i:=i*2END；c) nlog2n43.下面程序段的时间复杂度为_。(n>l)i. sum=l；ii. for(i=0;sum<n;i+)sum÷=l;0(n)44.设m.n均为自然数，m可表示为一些不超过n的自然数之和，f(m,n)为这种表示方式的数目。例f(5,3)=5,有5种表示方式：3+2,3+1+1,2+2+1,2+1+1+1,l+l+l+l+Ua)以下是该函数的程序段，请将未完成的局部填入，使之完整1. intf(m,n)a)intm,n;2. if(m-l)return(1);if(n=l)return(2);if(m<n)returnf(m,m);if(m=n)return1+(3);)returnf(m,n-l)+f(m-n,(4);)执行程序，f(6,4)=。1(2)1(3)f(m,n-l)(4)n945 .设有两个算法在同一机器上运行，其执行时间分别为100n2和2:要使前者快于后者，n至少为()。(当n<=14,100n2>2n,而n>=15时100n2<2n)46 .作为一个算法输入的数据所含数据元素的数目，或与此数目有关的其他参数，称为_o问题规模一三、判断题1 .()如果某数据结构的每一个元素最多只有一个直接前驱，那么其必为线性表。×2 .()一个程序的时间复杂度是指该程序运行时间与问题规模的对应关系J3 .()数据元素是数据的最小单元。×4 .()数据的根本单位是数据项。X5 .()数组元素之间的关系，既不是线性的，也不是树形的。6 .()算法和程序没有区别，所以在数据结构中二者是通用的。×7 .()算法的优劣与算法描述语言无关，但与所用计算机有关。X四、简答题1 .简述以下概念数据，数据元素，数据类型，数据结构，逻辑结构，存储结构，算法。【解答】数据是信息的载体，是描述客观事物的数、字符，以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据元素是数据的根本单位。在不同的条件下，数据元素又可称为元素、结点、顶点、记录等。数据类型是对数据的取值范围、数据元素之间的结构以及允许施加操作的一种总体描述。每一种计算机程序设计语言都定义有自己的数据类型。“数据结构”这一术语有两种含义，一是作为一门课程的名称；二是作为一个科学的概念。作为科学概念，目前尚无公认定义，一般认为，讨论数据结构要包括三个方面，-是数据的逻辑结构，二是数据的存储结构，三是对数据进行的操作(运算)。而数据类型是值的集合和操作的集合，可以看作是已实现了的数据结构，后者是前者的一种简化情况。数据的逻辑结构反映数据元素之间的逻辑关系(即数据元素之间的关联方式或“邻接关系”)，数据的存储结构是数据结构在计算机中的表示，包括数据元素的表示及其关系的表示。数据的运算是对数据定义的一组操作，运算是定义在逻辑结构上的，和存储结构无关，而运算的实现那么依赖于存储结构。数据结构在计算机中的表示称为物理结构，又称存储结构。是逻辑结构在存储器中的映像,包括数据元素的表示和关系的表示。逻辑结构与计算机无关。算法是对特定问题求解步骤的一种描述，是指令的有限序列。其中每一条指令表示一个或多个操作。一个算法应该具有以下特性：有穷性、确定性、可行性、输入和输出。2 .数据的逻辑结构分哪几种，为什么说逻辑结构是数据组织的主要方面？【解答】数据的逻辑结构分为线性结构和非线性结构。(也可以分为集合、线性结构、树形结构和图形即网状结构)。逻辑结构是数据组织的某种“本质性”的东西：(1)逻辑结构与数据元素本身的形式、内容无关。(2)逻辑结构与数据元素的相对位置无关。(3)逻辑结构与所含数据元素的个数无关。3 .试举一个数据结构的例子，表达其逻辑结构、存储结构、运算三方面的内容。【解答】学生成绩表，逻辑结构是线性结构，可以顺序存储(也可以链式存储)，运算可以有插入、删除、查询，等等。4,简述算法的五个特性，对算法设计的要求。【解答】算法的五个特性是：有穷性、确定性、可行性、零至多个输入和一至多个输出。对算法设计的要求：正确性，易读性，健壮性，和高的时空间效率(运算速度快，存储空间小)。5.设n是正整数，求以下程序段中带记号的语句的执行次数。(l)i=l;k=0;(2)i=llj=O; while(i<n) while(i+j<=n)i+;) else i+; (3)x=y=0;4)x=91;y=100;for (i=0;i<n;i+)e(y>0)for(j=0; j<n; j+)if(x>100)+;x=x-10; y一；k=k+50*i;if(i>j)j+; y+;else x+;)【解答】(l)n-l(2)i= n2(上取整) (3)n+l, n(n+l), n2, (n+l)n2, n3 (4) 100, 10006.数据结构与数据类型有什么区别？whilfor(k=O;k<n;k+)，j=n2 (下取整)【解答】“数据结构”这一术语有两种含义，一是作为一门课程的名称；二是作为一个科学的概念。作为科学概念，目前尚无公认定义，一般认为，讨论数据结构要包括三个方面,一是数据的逻辑结构，二是数据的存储结构，三是对数据进行的操作(运算)。而数据类型是值的集合和操作的集合，可以看作是已实现了的数据结构，后者是前者的一种简化情况。7 .下面程序段的时间复杂度是什么？for(i=0;i<n;i+)for(j=0;,j<m;j+)aij=0;【解答】0(m*n)8 .运算是数据结构的一个重要方面。试举一例，说明两个数据结构的逻辑结构和存储方式完全相同，只是对于运算的定义不同。因而两个结构具有显著不同的特性，是两个不同的结构。【解答】栈和队列的逻辑结构相同，其存储表示也可相同(顺序存储和链式存储)，但由于其运算集合不同而成为不同的数据结构。9 .试举一-例，说明对相同的逻辑结构，同一种运算在不同的存储方式下实现，其运算效率不同。【解答】线性表中的插入、删除操作，在顺序存储方式下平均移动近一半的元素，时间复杂度为O(n)；而在链式存储方式下，插入和删除时间复杂度都是O(1)。10 .有实现同一功能的两个算法Al和A2,其中Al的时间复杂度为门二0(20)，A2的时间复杂度为T2=0(112),仅就时间复杂度而言，请具体分析这两个算法哪一个好。【解答】对算法Al和A2的时间复杂度Tl和T2取对数，得nl(和210gno显然，当n<4时，算法AI好于A2；当n=4时，两个算法时间复杂度相同；当n4时，算法A2好于Ah11.设n是偶数，且有程序段：Fori:=1tonDoif2*i<=nThenForj:=2*itonDoy:=y+i*j;那么语句"y：=y+i*j”的执行次数多少？要求列出计算公式。【解答】nj=nnnnnj=n-ln-ln-ln-l j=333j=222J=I112.调用以下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<n+l;i+)for(j=n;j>i-l; j)for(k=l;k<j+l;k+ )sum+;printf ("sum=%dn”, sum)；)return (sum);)【解答】执行次数为(1+2+n) + (2+3+n)+n=n*n(n+l)2-n(n2T)6o 在 n=5 时， f(5)=55,执行过程中,输出结果为： sum=15 sum=29 sum=41 sum=50 SUm=55 13.设n是偶数，试计算运行以下程序段后m的值并给出该程序段的时间复杂度。 m:=0;FOR i:=l TO n DO4o语句“y:=y+i*j"在“i=l”时执行11-1次，在“i=2”时执行11-3次，”，最后当"i=n/2”时执行1次，当"i>n/2”就不再执行。故总的执行次数为：(n-l)+(n-3)+3+l=(n2)2=n2/4第一层for循环判断n+1次,往下执行n次,第二层for执行次数为(n+(11-1)+(11-2)+l),第三层循环体受第一层循环和第二层循环的控制，其执行次数如下表：i=123nFORj:=2*iTOnDOm:=m+l;【解答】0(n%m的值等于赋值语句=+l的运行次数，其计算式为五、应用题第一章绪论1 .在如下数组A中链接存储了一个线性表，表头指针为A0.next,试写出该线性表。AO1234567data605078903440next3572041【解答】线性表为：(78,50,40,60,34,90)2 .设指针变量P指向双向链表中结点A,指针变量q指向被插入结点B,要求给出在结点A的后面插入结点B的操作序列(设双向链表中结点的两个指针域分别为Ilink和rlink)0【解答】q->llink=p;q->rlink=p->rlink;p->rlink->llink=q;p->rlink=q;3 .斐波那契数列Fn定义如下Fo=O,Fl=I,Fn=Fn-I+Fn-2,11=2,3.请就此斐波那契数列，答复以下问题。(1)在递归计算Fn的时候，需要对较小的FnT,%2，Fl,Fo精确计算多少次？(2)如果用大0表示法，试给出递归计算Fn时递归函数的时间复杂度录多少？【解答】(1)由斐波那契数列的定义可得：1.Fn=F-1+Fn-2=2Fn-2÷F-3=3F11-3+2F11-4-5F11-t+3Fn-5=pF1+qF0设Fn的执行次数为Bm(m=01、2、n-l),由以上等式可知，FnT被执行一次，即反一尸1；FnT被执行两次，即反一2二2；直至Fl被执行P次、FO被执行q次，即B=p,BO=q。B中的执行次数为前两等式第一因式系数之和，即Be=Bg+B,再有Bn-Fl和B2=2,这也是一个斐波那契数列。可以解得：Bm=y()i-c-()-(m=0,1,2*,n-l)(2)时间复杂度为0(n)六、程序填空题(或算法阅读题)1.voidDD()ElemTypeA=1,3,5,7,9,2,4,6,8,10,B10;TwoMerge(A,B,0,4,9);for(inti=0;i<10;i+)cout«Bi«,“；cout<<endl;调用该算法后，输出结果为：【解答】123456789K)七、算法设计题1 .输入X,y,Z三个不相等的整数，设计一个“高效”算法，使得这三个数按从小到大输出。“高效”的含义是用最少的元素比拟次数、元素移动次数和输出次数。【解答】voidBest()按序输出三个整数的优化算法inta,b,c,t;scanf("%d%d%d”,&a,&b,&c);if(a>b)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已正序elseb=t;)printf("%d,%d,%dn”，a,b,c);最正确2次比拟，无移动；最差3次比拟，7个赋值)2 .在数组An中查找值为k的元素，假设找到那么输出其位置i(liWn),否那么输出0作为标志。设计算法求解此问题，并分析在最坏情况下的时间复杂度。【题目分析】从后向前查找，假设找到与k值相同的元素那么返回其位置，否那么返回0。【解答】intSearch(ElemTypeAn+1,ElemTypek)i=n;while(i>=l)&&(Ai!=k)i;if(i>=l)returni;elsereturn0;)当查找不成功时，总的比拟次数为n+1次，所以最坏情况下时间复杂度为0(n)。在学过第9章“查找”后，可优化以上算法:设“监视哨”。算法如下：intSearch(ElemTypeAn+1,ElemTypek)i=n;AO=k;while(Ai!=k)i-;returni;)研究说明，当n>=1000时，算法效率提高50%。