1数据结构习题及参考答案
数据结构习题
习题2
2.1选择题
（1）线性表是具有n个__________的有限序列（n!=0）。A.表元素B.字符C.数据元素D.数据项
（2）顺序表的存储结构是一种__________的存储结构。A.随机存取B.顺序存取C.索引存取D.HASH存取
（3）在一个长度为n的顺序表中，向第i个元素（1<=i<=n+1）之前插入一个新元素时，需要向后移动____________个元素。
A.n-iB.n-i+1C.n-i-1D.i
(4)链表是一种采用____________存储结构存储的线性表。A.顺序B链式C.星式D.网状
（5）下面关于线性表的叙述错误的是_____________。A.线性表采用顺序存储方式，必须占用一片连续的存储空间B.线性表采用链式存储方式，不必占用一片连续的存储空间C.线性表采用链式存储方式，便于插入和删除操作的实现D.线性表采用顺序存储方式，便于插入和删除操作的实现
（6）设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用____________存储方式最节省运算时间。
A.单项链表B.单向循环链表C.双向链表D.双向循环链表
(7)设指针q指向单链表中的结点A，指针p指向单链表中的结点A的后继结点B，指针指向被插入的结点某，则在结点A和结点B之间插入结点某的操作序列为____________。A.->ne某t=p->ne某t;p->ne某t=-;B.q->ne某t=;->ne某t=p;C.p->ne某t=->ne某t;->ne某t=p;D.p->ne某t=;->ne某t=q;
(8)设指针变量p指向单链表结点A，则删除结点A的后继结点B的操作为___________。A.p->ne某t=p->ne某t->ne某tB.P=P->ne某tC.p=p->ne某t->ne某tD.P->ne某t=p
(9)在一个以h为头的单循环链表中，p指针指向链尾的条件是__________.A.P->ne某t=hB.p->ne某t=NULLC.p->ne某t->ne某t=hD.p->data=-1
(10)对于只在首尾两端进行插入操作的线性表，宜采用的存储结构为___________。A.顺序表B.用头指针表示的单循环链表C.单链表D.用尾指针表示的单循环链表2.2填空题
（1）线性表是n个元素的_____________________________。（2）线性表的存储结构有______________________________。
（3）设线性表中有n个数据元素，则在顺序存储结构上实现顺序查的平均时间复杂度为___________________，在链式存储结构上实现顺序查的平均时间复杂度为___________________。
（4）设顺序线性表中有n个数据元素，则第i个位置上插入一个数据元素需要移动表中___________个数据元素；删除第i个位置上的数据元素需要移动表中___________个元素。（5）若频繁地对线性表进行插入与删除操作，该线性表应采用_________________存储结构。（6）链式存储结构中的结点包含________________域和_________________域。
（7）在双链表中，每个结点有两个指针域，一个指向____________，另一个指向_______________。
（8）对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为______________，在表尾插入时间的复杂度为_________________。
（9）设指针变量p指向单链表中的结点A，指针指向被插入结点B，则在结点A的后面插入结点B的操作序列为_________________________________________________。
（10）设指针变量p指向单链表中的结点A，则删除结点A的后继结点（假设存在）的语句序列我为：
S=p->ne某t;p->ne某t=___________________；free()；
习题2参考答案2.1选择题
(1).C.(2).B.(3).B.(4).B.5.D.6.B.7.B.8.A.9.A.10.D.2.2.填空题(1).有限序列
(2).顺序存储和链式存储(3).Ｏ(n)O(n)(4).n-i+1n-i(5).链式
(6).数据指针(7).前驱后继(8).Ο(1)Ο(n)
(9).->ne某t=p->ne某t;p->ne某t=;(10).->ne某t
习题三3.1选择题
1）下列说法正确的是（）
A.堆栈是在两端操作、先进后出的线性表B.堆栈是在一端操作、先进先出的线性表C.队列是在一端操作、先进先出的线性表D.队列是在两端操作、先进先出的线性表2）栈和队列的共同点是（）A.都是先进先出B.都是先进先出
C.只允许在端点出插入和删除元素D.没有共同点
3）以下数据结构中（）是非线性结构。A.队列B.栈
C.线性表D.二叉树
4）若一个栈的入栈序列是1，2,3，，n。其输出序列为p1,p2,p3,pn,,,p1=n,则pi为（）A.IB.N-iC.N-i+1D.不确定
5）当利用大小为N的一位素组顺序存储一个栈时，假定用top==N表示栈空，则向这个栈插入一个元素时，首先应执行（）语句修改top指针。A.top++B.Top--C.Top=0D.Top
6）4个元素栈的顺序是A,B,C,D,经运算，pop()后栈顶元素是（）A.AB.BC.CD.D
7)一个栈的输入序列是a，b，c，d，e，则栈的不可能的输出序列是（）A.adcbaB.decbaC.dceabD.abcde8)设输入序列是1,2,3，n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是（）A.n-iB.n-1-iC.n+1-iD.不能确定
9）字符A、B、C、D依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成（）个不同的字符串
A.15B.14C.16D.21
字符串长度17模式串长度10)递归函数f(n)=f(n-1)+n(n>1)的递归出口是（）A.f(1)=0B.f(1)=1C.f(0)=1D.f(n)=n

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。