《数据结构导论》作业题

《《数据结构导论》作业题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构导论模拟试题一、考试题型及分值分布：1、单项选择题(本大题共15小题，每小题2分，共30分)2、填空题(本大题共13小题，每小题2分，共26分)3、应用题(本大题共5小题，每小题6分，共30分)4、算法设计题(本大题共2小题，每小题7分，共14分)二、单项选择题和填空题样题参考（一）单项选择题1.在二维数组中，每个数组元素同时处于（c）个向量中.A.0B.1C.2D.n2.已知单链表A长度为m，单链表B长度为n，它们分别由表头指针所指向，若将B整体连接到A的末尾，其时间复杂度应为（A）.矚慫润厲钐瘗睞枥庑赖。A.O(1)

2、B.O(m)C.O(n)D.O(m+n)3.假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为(A).A.front==rearB.front!=NULLC.rear!=NULLD.front==NULL4.若让元素1,2,3依次进栈，则出栈次序不可能出现(c)种情况.A.3,2,1B.2,1,3C.3,1,2D.1,3,25.图的广度优先搜索类似于树的（D）遍历.A.先根B.中根C.后根D.层次6.下面程序段的时间复杂度为(c).for(inti=0;i

3、++)a[i][j]=i*j;A.O(m2)B.O(n2)C.O(m*n)D.O(m+n)7.设有两个串t和p，求p在t中首次出现的位置的运算叫做（B）.A.求子串B.模式匹配C.串替换D.串连接8利用双向链表作线性表的存储结构的优点是（B）.A.便于单向进行插入和删除的操作B.便于双向进行插入和删除的操作C.节省空间D.便于销毁结构释放空间9.设链式栈中结点的结构为（data,link），且top是指向栈顶的指针.若想在链式栈的栈顶插入一个由指针s所指的结点，则应执行(C)操作.聞創沟燴鐺險爱氇谴净。A.top->link=s

4、;B.s->link=top->link;top->link=s;C.s->link=top;top=s;D.s->link=top;top=top->link;残骛楼諍锩瀨濟溆塹籟。10.一棵具有35个结点的完全二叉树的高度为(B).假定空树的高度为-1.A.5B.6C.7D.811.一个有n个顶点和n条边的无向图一定是(A)的.A．连通B．不连通C．无回路D．有回路12.在一个长度为n的顺序表的任一位置插入一个新元素的时间复杂度为（A）.A.O(n)B.O(n/2)C.O(1)D.O(n2)13.已知广义表为A((a,b,c

5、),(d,e,f))，从A中取出原子e的运算是（D）.A．Tail(Head(A))B．Head(Tail(A))C．Head(Tail(Head(Tail(A))))D．Head(Head(Tail(Tail(A))))酽锕极額閉镇桧猪訣锥。14.在一棵树的静态双亲表示中，每个存储结点包含(B)个域.9A1B2C3D415.有向图中的一个顶点的度数等于该顶点的(C).A．入度B．出度C．入度与出度之和D．(入度+出度)/２16.与邻接矩阵相比，邻接表更适合于存储(A).A．无向图B．连通图C．稀疏图D．稠密图17.较快的数据搜

6、索方法是（B）搜索方法.A.顺序B.折半C.单链D.散列18.在闭散列表中，散列到同一个地址而引起的“堆积”问题是由于（C）引起的.A.同义词之间发生冲突B.非同义词之间发生冲突C.同义词之间或非同义词之间发生冲突D.散列表“溢出”19.根据n个元素建立一个有序单链表的时间复杂度为（B）.A.O(1)B.O(n)C.O(n2)D.O(nlog2n)20.假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear，则判断队空的条件为(D).彈贸摄尔霁毙攬砖卤庑。A.front+1==rearB.rear+1==front

7、C.front==0D.front==rear21.假定一棵二叉树的第i层上有3i个结点，则第i+1层上最多有(B)个结点.A.3iB.6iC.9iD.2i22.对于具有e条边的无向图，它的邻接表中共有(C)个边结点.A．e-1B．e+1C．2eD．3e23.图的深度优先搜索遍历类似于树的（A）次序遍历.A.先根B.中根C.后根D.层次24．栈S最多能容纳4个元素.现有6个元素按A、B、C、D、E、F的顺序进栈,问下列哪一个序列是可能的出栈序列?(C)謀荞抟箧飆鐸怼类蒋薔。A.E、D、C、B、A、FB.B、C、E、F、A、DC.

8、C、B、E、D、A、FD.A、D、F、E、B、C25．将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为49的结点的左孩子的编号为：(A)厦礴恳蹒骈時盡继價骚。A.98B.99C.50D.4826.对下列关