数据结构练习题

《数据结构练习题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第1章绪论一、选择题1.算法的计算量的大小称为计算的（）。A．效率B.复杂性C.现实性D.难度2.算法的时间复杂度取决于（）A．问题的规模B.待处理数据的初态C.A和B3.下面说法错误的是（）(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A．(1)B.(1),(2)C.(1),(4)D.(3)4.以下数据结构中，

2、哪一个是线性结构（）A．广义表B.二叉树C.稀疏矩阵D.串5.在下面的程序段中，对x的赋值语句的频度为（）for(inti=1;i<=n;i++)for(intj=1;i<=n;j++)x+=1;A．2nB．nC．n2D．log2n二、判断题1.数据元素是数据的最小单位。()2.算法的优劣与算法描述语言无关，但与所用计算机有关。()3.数据的物理结构是指数据在计算机内的实际存储形式。()4.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。()5.数据结构的抽象操作的定义与具体实现有关。()三、填空1．数

3、据的物理结构包括的表示和的表示2.数据结构中的逻辑结构有（1），（2），（3），__（4）_四种。3.一个数据结构在计算机中称为存储结构4.数据结构中评价算法的两个重要指标是5.一个算法具有5个特性:（1）、（2）、（3），有零个或多个输入、有一个或多个输出。6.已知如下程序段,语句1执行的频度为（1）；语句2执行的频度为（2）；for(inti=n;i>=1;i--){x=x+1;//语句1for(intj=n;j>=1;j--)y=y+1;//语句2}7.下面程序段中带下划线的语句的执行次数的渐进时间复杂度

4、为inti=1;while(i

5、算法的最坏时间复杂性是什么？并分析它的平均时间复杂性。intA[n];inti=n;while(A[i]==1){A[i]=0;i-=1;}A[i]=1;5.调用下列C函数f(n),回答下列问题:假定n=5，试指出f(5)值的大小和执行f(5)时的输出结果。intf(intn){inti,j，k,sum=0;for(i=l;ii-1;j--)for(k=1;k

6、运行时间函数：（1）T1(n)=1000;（2）T2(n)=n2+1000n;（3）T3(n)=3n3+100n2+n+1;分别写出相应的大O表示的运算时间7.将下列函数，按它们n→∝时的时间复杂度，从小到大排序。（提示limn→∝logn/n=0）n,n-n3+7n5,nlogn,2n/2,n3,logn,n1/2+logn,(3/2)n,n!,n2+logn第2章线性表一选择题1．下述哪一条是顺序存储结构的优点？（）A．存储密度大,且随机访问B．插入运算方便C．删除运算方便D．可方便地用于各种逻辑结构的存储

7、表示2．下面关于线性表的叙述中，错误的是哪一个？（）A．线性表采用顺序存储，必须占用一片连续的存储单元。B．线性表采用顺序存储，便于进行插入和删除操作。C．线性表采用链接存储，不必占用一片连续的存储单元。D．线性表采用链接存储，便于插入和删除操作。3．线性表是具有n个（）的有限序列（n>0）。A．表元素B．字符C．数据元素D．数据项E．信息项4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表5．某

8、线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。A．单链表B．仅有头指针的单循环链表C．双链表D．仅有尾指针的单循环链表6．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用()最节省时间。A.单链表B.单循环链表C.带尾指针的单循环链表D.带头结点的双循环链表7．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最