《数据结构与算法》（c语言版）期末考复习题.docx

《《数据结构与算法》（c语言版）期末考复习题.docx》由会员分享，可在线阅读，更多相关《《数据结构与算法》（c语言版）期末考复习题.docx（30页珍藏版）》请在优知文库上搜索。

1、数据结构与算法（C语言版）期末考复习题一、选择题。1 .在数据结构中，从逻辑上可以把数据结构分为C。A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构2 .数据结构在计第机内存中的表示是指上。A.数据的存储结构B.数据结构C.数据的逻辑结构D.数据元素之间的关系3 .在数据结构中，与所使用的计算机无关的是数据的A结构。A.逻辑B.存储C.逻辑和存储D.物理4 .在存储数据时，通常不仅要存储各数据元素的值，而且还要存储C.A.数据的处理方法B.数据元素的类型C.数据元素之间的关系D.数据的存储方法5 .在决定选取何种存储结构时，一般不考虑AA.各结点的值

2、如何B.结点个数的多少C.对数据有哪些运算D.所用的编程语言实现这种结构是否方便。6 .以下说法正确的是_D0A.数据项是数据的基本单位B.数据元素是数据的最小单位C.数据结构是带结构的数据项的集合D.一些表面上很不相同的数据可以有相同的逻辑结构7 .算法分析的目的是,算法分析的两个主要方面是(1) A.找出数据结构的合理性C.分析算法的效率以求改进(2) A.空间复杂度和时间复杂度C.可读性和文档性B.研究算法中的输入和输出的关系C.分析算法的易读性和文档性B.正确性和简明性D.数据红杂性和程序复杂性8 .下面程序段的时间灯杂度是0(心)s=0;tbr(I=0:in;i+)for(j=0yj

3、)s+=BiU1.;sum=s;9 .下面程序段的时间复杂度是O(n*m)tbr(i=0;in;i+)for(j=OJnj+)AIiJUJ=0；10 .下面程序段的时间第杂度是i=0；whi1.e(inext=NU1.1.C.head-next=headDhead!=NU1.1.15 .带头结点的单链表head为空的判定条件是B。A.head=三NU1.1.Bhead-next三=NU1.1.C.head-next=heac1.Dhead!=NU1.1.16 .若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用D存储方式最节省运第时间。A.单链表B.给出表头指针的单循

4、环链表C.双链表D.带头结点的双循环链表17 .需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是BoA.单链表B.静态链表C.线性链表D顺序存储结构18 .非空的循环单链表head的尾结点（由P所指向）满足C。A.p-next=NU1.1.B.p=-NU1.1.C.p-next=headD.p=head19.在循环双链表的P所指的结点之前插入s所指结点的操作是D.A. p-prior=s：s-next=p；-prior-next=s；s-prior=p-riorB. p-prior=s；p-prior-next=s；s-next=p：s-prior=p-priorC. s-ne

5、xt=p；s-prior=p-prior:p-prior=s；p-prior-next=sD. s-next=p；s-prior=-prior:p-prior-next=s：p-prior=s20 .如果最常用的操作是取第i个结点及其前驱，则采用D存储方式最节省时间。A.单链表B.双链表C.单循环链表D.顺序表21 .在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是B_：A.0(1)B.O(n)C.O(n2)D.O(n1.og2n)22 .在一个长度为n(n1.)的单链表上，设有头和尾两个指针，执行1.操作与链表的长度有关。A.删除单链表中的第一个元素B.删除单链表中

6、的最后一个元素C.在单链表第一个元素前插入一个新元素D.在单链表最后一个元素后插入一个新元素23 .与单链表相比，双链表的优点之一是A.插入、删除操作更简单B.可以进行随机访问C.可以省略表头指针或表尾指针D.顺序访问相邻结点更灵活24 .如果对线性表的操作只有两种，即删除第一个元素，在最后一个元素的后面插入新元素，则最好使用BA.只有表头指针没有表尾指针的循环单链表B.只有表尾指针没有表头指针的循环单链表C.非循环双链表D.循环双链表25 .在长度为n的顺序表的第i个位置上插入一个元素(ISin+1.),元素的移动次数为：A_oA.n-i+1B.n-iC.iD.i-126 .对于只在表的首、

7、尾两端进行插入操作的线性表，宜采用的存储结构为COA.顺序表B.用头指针表示的循环单链表C.用尾指针表示的循环单链表D.单链表27 .下述哪一条是顺序存储结构的优点？CA插入运算方便B可方便地用于各种逻辑结构的存储表示C存储密度大D删除运算方便28 .下面关于线性表的叙述中，错误的是哪一个？BA线性表采用顺序存储，必须占用一片连续的存储单元B线性表采用顺序存储，便于进行插入和删除操作。C线性表采用链式存储，不必占用一片连续的存储单元D线性表采用链式存储，便于进行插入和删除操作。29 .线性表是具有n个B的有限序列。A.字符B.数据元素C.数据项D.表元素30 .在n个结点的线性表的数组实现中，

8、算法的时间复杂度是O(I)的操作是AcA.访问第i(1.=i=n)个结点和求第i个结点的宜接前驱(1.i=n)B.在第i(1.=i=n)个结点后插入一个新结点C.删除第i(1.=inext=s;s-next=p-nextB.s-next=p-next；p-next=s;C.p-next=s:p-next=s-nextD.p-next=s-nex(;p-next=s36 .线性表的顺序存储结构是一种B.顺序存取的存储结构DHash存取的存储结构AoA.随机存取的存储结构C.索引存取的存储结构37 .栈的特点是B,队列的特点是A.先进先出B.先进后出38 .栈和队列的共同点是C。B.都是先进先出D

9、.没有共同点CA.都是先进后出C.只允许在端点处插入和删除元素39 .一个栈的进栈序列是a,b,c,d,e,则栈的不可能的输出序列是A.edcbaB.decbaC.dceabD.abcde40 .设有一个栈，元素依次进栈的顺序为A、B、C、D,E。下列C是不可能的出栈序列。A.A.B,C.D.EB.B,C,D.E,AC.E,A,B.C.DD.E,D,C,B,A41 .以下B不是队列的基本运筑?A.从队尾插入一个新元素B.从队列中删除第i个元素C.判断一个队列是否为空D.读取队头元素的值42 .若已知一个栈的进栈序列是1,2,3,n,其输出序列为p1.,p2,p3,n,若P1.=n,则Pi为C。

10、A.iB.n-iC.ni1D.不确定43 .判定一个顺序栈St（最多元素为MaXSiZe）为空的条件是A. st-top!=-1B. st-top=-1C.st-top!=MaxSizeD.st-top=MaxSize44 .判定一个顺序栈st（最多元素为MaXSiZe）为满的条件是A. st-top!=-1C.st-top!=MaxSizeB. st-top=-1D.st-top=MaxSize45 .一个队列的入队序列是1,2,3,4,则队列的输出序列是。A.4,3,2,1B.1,2,3,4C.I,4,3,2D.3,2,4,I46 .判定一个循环队列qu（最多元素为MaXSiZe）为空的条

11、件是_。A.qu-rearqu-front=MaxSizeB.qu-rear-qu-front-1=MaxSizeC.qu-rear=qu-frontD.qu-rear=qu-front-147.在循环队列中，若from与rear分别表示对头元素和队尾元素的位置，则判断循环队列空的条件是C0A.front=rear+1.B.rear=front+1.C.front=rearD.front=048.向一个栈顶指针为h的带头结点的链栈中插入指针S所指的结点时，应执行D操作。A.h-next=s;B.s-next=h;C.s-next=h:h=s;D.s-next=h-next;h-next=s:4

12、9.输入序列为ABC,可以变为CBA时，经过的栈操作为BA.push,pop.push,pop,push,popB.push,push,push,pop,pop.POPC. push.push,pop,pop.push,popD.push,pop,push,push,pop.PoP50.若栈采用顺序存储方式存储，现两栈共享空间Vnm,top1.htop2分别代表第1和第2个栈的栈顶，栈1的底在V1.,栈2的底在Vn,则栈满的条件是B.A.ItOP2-top1.=0B.top1.+1.=1.opC.top1.+top2=mD. top1.=top251 .设计一个判别表达式中左、右括号是否配对出现的算法，采用D数据结构最佳。A.线性表的顺序存储结构B.队列C.线性表的链式存储结构D.栈52 .允许对队列进行的操作有D。A.对队列中的元素排序B.取出最近进队的元素C.在队头元素之前插入元素D.删除队头元素53 .对于循环队列DA.无法判