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

数据结构练习第一章绪论一、选择题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)；的时间复杂度为〔〕。A.O(n) B.O(nlog2n) C.O(n2) D.O(n3/2)6．以下程序段的时间复杂度为〔〕。for(i=0；i<m；i++)for(j=0；j<t；j++)c[i][j]=0；for(i=0；i<m；i++)for(j=0；j<t；j++)for(k=0；k<n；k++)c[i][j]=c[i][j]+a[i][k]*b[k][j]；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<n){s=s+i；i++；}A.O(n1/2) B.O(n1/3) C.O(n) D.O(n2)8．某程序的时间复杂度为〔3n+nlog2n+n2+8〕,其数量级表示为〔〕。A．O〔n〕B．O〔nlog2n〕C．O〔n2〕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<n；i++〕for〔j=0；j<n；j++〕A［i］［j］=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++〕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〕{i++；s=s+i；}A.O〔〕B.O〔〕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+iC.*a+iD.&a+i23．对于两个函数，假设函数名相同，但只是〔〕不同那么不是重载函数。A.参数类型B.参数个数C.函数类型24．假设需要利用形参直接访问实参，那么应把形参变量说明为〔〕参数A.指针B.引用C.值25．下面程序段的时间复杂度为〔〕。for(inti=0;i<m;i++)for(intj=0;j<n;j++)a[i][j]=i*j;A.O(m2)B.O(n2)C.O(m*n)D.O(m+n)26．执行下面程序段时，执行S语句的次数为〔〕。for(inti=1;i<=n;i++)for(intj=1;j<=i;j++)S;A.n2B.n2/2C.n(n+1)D.n(n+1)/227．下面算法的时间复杂度为〔〕。intf(unsignedintn){if(n==0||n==1)return1;elsereturnn*f(n-1);}A.O(1)B.O(n)C.O(n2)D.O(n!)28．组成数据的根本单位是〔〕A.数据项 B.数据类型C．数据元素D．数据变量29．如某数据结构的数据元素的集合为S={A,B,C,D,E,F,G}，数据元素间的关系为R={<A,D>,<A,G>,<D,B>,<D,C>,<G,E>,<G,F>}，那么该数据结构是一种〔〕。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(n)D．O(n)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.数据的逻辑结构38．在下面的程序段中，对x的赋值语句的频度为〔〕FORi:=1TOnDOFORj:=1TOnDOx:=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．通常从四个方面评价算法的质量：_________、_________、_________和_________。正确性易读性强壮性高效率2．一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。O(n)3．数据的物理结构主要包括_____________和______________两种情况。顺序存储结构、链式存储结构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:N21．一种抽象数据类型包括__________和__________两个局部。数据定义、操作声明22．当一个形参类型的长度较大时，应最好说明为_________，以节省参数值的传输时间和存储参数的空间。引用形参(或指针形参)23．当需要用一个形参访问对应的实参时，那么该形参应说明为__________。引用类型(或指针类型)24．在函数中对引用形参的修改就是对相应__________的修改，对__________形参的修改只局限在该函数的内部，不会反映到对应的实参上。实参、值25．当需要进行标准I/O操作时，那么应在程序文件中包含________________头文件，当需要进行文件I/O操作时，那么应在程序文件中包含________________头文件。iostream.h、fstream.h26．在包含有________________头文件的程序文件中，使用________________能够产生出0～20之间的一个随机整数。stdlib.h、rand()%2127．一个数组a所占有的存储空间的大小即数组长度为____________，下标为i的元素a[i]的存储地址为__________，或者为______________________________。sizeof(a)、a+i*sizeof(a[0])、a+i28．函数重载要求____________、____________或____________有所不同。参数类型、数量、次序29．对于双目操作符，其重载函数带有__________个参数，其中至少有一个为____________的类型。2、用户自定义30．假设对象ra和rb中至少有一个是属于用户定义的类型，那么执行ra==rb时，需要调用__________重载函数，该函数的第一个参数应与__________的类型相同，第二个参数应与__________的类型相同。==、ra、rb31．从一维数组a[n]中顺序查找出一个最大值元素的时间复杂度为________，输出一个二维数组b[m][n]中所有元素值的时间复杂度为________。O(n)、O(m*n)32．在下面程序段中，s=s+p语句的执行次数为________，p*=j语句的执行次数为________，该程序段的时间复杂度为________。inti=0,s=0;while(++i<=n){intp=1;for(intj=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.下面程序段中带下划线的语句的执行次数的数量级是()。i.i:=1;b)WHILEi<nBEGINFORj:=1TOnDOx:=x+1;i:=i*2END；c)nlog2n43.下面程序段的时间复杂度为________。(n>1)i.sum=1；ii.for(i=0;sum<n;i++)sum+=1;O(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，1+1+1+1+1。a)①以下是该函数的程序段，请将未完成的局部填入，使之完整1.intf(m,n)a)intm,n;2.{if(m==1)return(1);if(n==1){return(2);}if(m<n){returnf(m,m);}if(m==n){return1+(3);}returnf(m,n-1)+f(m-n,(4));}②执行程序，f(6,4)=。①(1)1(2)1(3)f(m,n-1)(4)n②945.设有两个算法在同一机器上运行，其执行时间分别为100n2和2n，要使前者快于后者，n至少为〔〕。(当n<=14时,100n2>2n,而n>=15时100n2<2n)46.作为一个算法输入的数据所含数据元素的数目，或与此数目有关的其他参数，称为________。问题规模_三、判断题1．()如果某数据结构的每一个元素最多只有一个直接前驱，那么其必为线性表。×2．()一个程序的时间复杂度是指该程序运行时间与问题规模的对应关系√3．〔〕数据元素是数据的最小单元。×4．〔〕数据的根本单位是数据项。╳5．〔〕数组元素之间的关系，既不是线性的，也不是树形的。√6．〔〕算法和程序没有区别，所以在数据结构中二者是通用的。×7．〔〕算法的优劣与算法描述语言无关，但与所用计算机有关。×四、简答题1．简述以下概念数据，数据元素，数据类型，数据结构，逻辑结构，存储结构，算法。【解答】数据是信息的载体，是描述客观事物的数、字符，以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据元素是数据的根本单位。在不同的条件下，数据元素又可称为元素、结点、顶点、记录等。数据类型是对数据的取值范围、数据元素之间的结构以及允许施加操作的一种总体描述。每一种计算机程序设计语言都定义有自己的数据类型。“数据结构”这一术语有两种含义，一是作为一门课程的名称；二是作为一个科学的概念。作为科学概念，目前尚无公认定义，一般认为，讨论数据结构要包括三个方面，一是数据的逻辑结构，二是数据的存储结构，三是对数据进行的操作〔运算〕。而数据类型是值的集合和操作的集合，可以看作是已实现了的数据结构，后者是前者的一种简化情况。数据的逻辑结构反映数据元素之间的逻辑关系〔即数据元素之间的关联方式或“邻接关系”〕，数据的存储结构是数据结构在计算机中的表示，包括数据元素的表示及其关系的表示。数据的运算是对数据定义的一组操作，运算是定义在逻辑结构上的，和存储结构无关，而运算的实现那么依赖于存储结构。数据结构在计算机中的表示称为物理结构，又称存储结构。是逻辑结构在存储器中的映像，包括数据元素的表示和关系的表示。逻辑结构与计算机无关。算法是对特定问题求解步骤的一种描述，是指令的有限序列。其中每一条指令表示一个或多个操作。一个算法应该具有以下特性：有穷性、确定性、可行性、输入和输出。2．

数据的逻辑结构分哪几种，为什么说逻辑结构是数据组织的主要方面？【解答】数据的逻辑结构分为线性结构和非线性结构。〔也可以分为集合、线性结构、树形结构和图形即网状结构〕。逻辑结构是数据组织的某种“本质性”的东西：〔1〕逻辑结构与数据元素本身的形式、内容无关。〔2〕逻辑结构与数据元素的相对位置无关。〔3〕逻辑结构与所含数据元素的个数无关。3．试举一个数据结构的例子，表达其逻辑结构、存储结构、运算三方面的内容。【解答】学生成绩表，逻辑结构是线性结构，可以顺序存储〔也可以链式存储〕，运算可以有插入、删除、查询，等等。4．简述算法的五个特性，对算法设计的要求。【解答】算法的五个特性是：有穷性、确定性、可行性、零至多个输入和一至多个输出。对算法设计的要求：正确性，易读性，健壮性，和高的时空间效率〔运算速度快，存储空间小〕。5．设n是正整数，求以下程序段中带@记号的语句的执行次数。(1)i=1;k=0;

(2)i=1;j=0;

while(i<n)

while(i+j<=n)

{k=k+50*i;i++;

@

{if(i>j)j++;

@

}

elsei++;

}

@

(3)x=y=0;

(4)x=91;y=100;

for(i=0;i<n;i++)

@

while(y>0)

for(j=0;j<n;j++)

@

if(x>100)

{x++;

@

{x=x-10;y--;

@

for(k=0;k<n;k++)@

}

y++;

@

elsex++;

@

}

【解答】(1)n-1

(2)i=

n/2(上取整〕

，j=n/2〔下取整〕

(3)n+1,n(n+1),n2,(n+1)n2,n3

(4)100,10006．数据结构与数据类型有什么区别？【解答】“数据结构”这一术语有两种含义，一是作为一门课程的名称；二是作为一个科学的概念。作为科学概念，目前尚无公认定义，一般认为，讨论数据结构要包括三个方面，一是数据的逻辑结构，二是数据的存储结构，三是对数据进行的操作〔运算〕。而数据类型是值的集合和操作的集合，可以看作是已实现了的数据结构，后者是前者的一种简化情况。7．下面程序段的时间复杂度是什么？for(i=0;i<n;i++)for(j=0;,j<m;j++)a[i][j]=0;【解答】O(m*n)8．运算是数据结构的一个重要方面。试举一例，说明两个数据结构的逻辑结构和存储方式完全相同，只是对于运算的定义不同。因而两个结构具有显著不同的特性，是两个不同的结构。【解答】栈和队列的逻辑结构相同，其存储表示也可相同〔顺序存储和链式存储〕，但由于其运算集合不同而成为不同的数据结构。9．试举一例，说明对相同的逻辑结构,同一种运算在不同的存储方式下实现，其运算效率不同。【解答】线性表中的插入、删除操作，在顺序存储方式下平均移动近一半的元素，时间复杂度为O〔n〕；而在链式存储方式下，插入和删除时间复杂度都是O〔1〕。10．有实现同一功能的两个算法A1和A2，其中A1的时间复杂度为Tl=O(2n)，A2的时间复杂度为T2=O(n2)，仅就时间复杂度而言，请具体分析这两个算法哪一个好。【解答】对算法A1和A2的时间复杂度T1和T2取对数，得nlog2和2logn。显然，当n<4时，算法A1好于A2；当n=4时，两个算法时间复杂度相同；当n>4时，算法A2好于A1。11．设n是偶数，且有程序段：Fori:=1tonDoif2*i<=nThenForj:=2*itonDoy:=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=123…nj=nnnn…nj=n-1n-1n-1n-1……………j=333j=222j=1112．调用以下C函数f(n)(编者注：略去PASACAL函数f(n))答复以下问题:试指出f(n)值的大小，并写出f(n)值的推导过程;假定n=5，试指出f(5)值的大小和执行f(5)时的输出结果。C函数：intf(intn){inti,j，k,sum=0;for(i=l;i<n+1;i++){for(j=n;j>i-1;j--)1.for(k=1;k<j+1;k++)2.sum++;3.printf("sum=%d\n",sum)；}return(sum);}【解答】执行次数为(1+2+…+n)+(2+3+…+n)+…+n=n*n(n+1)/2-n(n2-1)/6。在n=5时，f(5)=55，执行过程中，输出结果为：sum=15sum=29sum=41sum=50sum=5513．设n是偶数，试计算运行以下程序段后m的值并给出该程序段的时间复杂度。m:=0;FORi:=1TOnDOFORj:=2*iTOnDOm:=m+1;【解答】O(n2),m的值等于赋值语句m:=m+1的运行次数，其计算式为五、应用题第一章绪论1．在如下数组A中链接存储了一个线性表，表头指针为A[0].next，试写出该线性表。A01234567data605078903440next3572041【解答】线性表为：〔78，50，40，60，34，90〕2.设指针变量p指向双向链表中结点A，指针变量q指向被插入结点B，要求给出在结点A的后面插入结点B的操作序列〔设双向链表中结点的两个指针域分别为llink和rlink〕。【解答】q->llink=p;q->rlink=p->rlink;p->rlink->ll