资源描述:
《数据结构样题new》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、系别班次学号姓名.………密………封………线………以………内………答………题………无………效……电子科技大学成都学院数据结构(样题)题号一二三四总分评卷教师分数说明:本试卷共四大题,试卷满分100分,考试时间120分钟。一.填空题(每题2分,共20分);1.数据结构算法中,通常用时间复杂度和__________________两种方法衡量其效率。。2.下面程序段的时间复杂度为________________。(n>1)for(i=1;i<=n;i++)for(j=1;j<=i;j++)x=x+1;3.
2、在一个长度为n的顺序表中第i个元素(1<=i<=n)之前插入一个元素时,需向后移动________个元素。4.在n个结点的单链表中要删除已知结点*p,需找到它的________________________。5.在具有n个元素空间的循环队列中,队满时共有_________________个元素。6.两个串相等的充分必要条件是_____________________________________________________。7.具有256个结点的完全二叉树的深度为______________
3、___。8.G是一个非连通无向图,共有36条边,则该图至少有______个顶点。9.在顺序表(8,11,15,19,21,25,26,30,33,42,48,50)中,用二分(折半)法查找关键码值20,需做的关键码比较次数为___________________。10.直接插入排序用监视哨的作用是___________________________________________________。二.单项选择题(每题2分,共30分);(说明:请将答案填入下表中)题号12345678910答案题号1
4、112131415答案1.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算,则利用()存储方式最节省时间。A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表2.设a1、a2、a3为3个结点,则如下的链式存储结构称为:第1页共5页系别班次学号姓名.………密………封………线………以………内………答………题………无………效……表元编号结点表元间关系1a132a213a32A.循环链表B.单链表C.双向循环链表D.双向链表3.有六个元素6,5,4,3,2,1的顺序进栈,问下列
5、哪一个不是合法的出栈序列?()A.543612B.346521C.453126D.2341564.若栈采用顺序存储方式存储,现两栈共享空间V[1..m],top[i]代表第i个栈(i=1,2)栈顶,栈1的底在v[1],栈2的底在V[m],则栈满的条件是()。A.top[2]-top[1]
6、=0B.top[1]+1=top[2]C.top[1]+top[2]=mD.top[1]=top[2]5.数组Q[n]用来表示一个循环队列,front为当前队列头元素的前一位置,rear为队尾元素的位置,假定队列中
7、元素的个数小于n,计算队列中元素的公式为A.rear-frontB.(n+front-rear)%nC.n+rear-frontD.(n+rear-front)%n6.设栈S和队列Q的初始状态为空,元素e1,e2,e3,e4,e5和e6依次通过栈S,一个元素出栈后即进队列Q,若6个元素出队的序列是e2,e4,e6,e5,e3,e1则栈S的容量至少应该是()。A.6B.4C.3D.27.设有数组A[i,j],数组的每个元素长度为3字节,i的值为1到8,j的值为1到10,数组从内存首地址BA开始顺序存放
8、,当用以列为主存放时,元素A[5,8]的存储首地址为()。A.BA+141B.BA+180C.BA+222D.BA+2258.已知广义表L=((x,y,z),a,(u,t,w)),从L表中取出原子项t的运算是()。A.head(tail(tail(L)))B.tail(head(head(tail(L))))C.head(tail(head(tail(L))))D.head(tail(head(tail(tail(L)))))9.一棵树高为K的完全二叉树至少有()个结点?kk-1k-1kA.2–1B
9、.2–1C.2D.210.某二叉树的前序序列和后序序列正好相反,则该二叉树一定是()的二叉树。A.空或只有一个结点B.任一结点无左子树C.高度等于其结点数D.任一结点无右子树11.无向图G=(V,E),其中:V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)},对该图进行深度优先遍历,得到的顶点序列正确的是()。A.a,b,e,c,d,fB.a,c,f,e,b,dC.a,e,b,c,f,dD.a,e