您好,欢迎访问三七文档
当前位置:首页 > 办公文档 > 会议纪要 > 2011专升本插班生《数据结构》试卷
(A卷)第1页共7页韩山师范学院2011年专升本插班生考试试题计算机科学与技术专业数据结构试卷(A卷)题号一二三四五六七八总分评卷人得分一、单项选择题(每题2分,共40分)题号12345678910答案题号11121314151617181920答案1、下列选项中不是算法的必须具有的重要特性的是。A.有穷性B.正确性C.确定性D.可行性2、下列关于算法渐近阶表达式中,时间复杂度最高的是。A.5n2B.n3/2C.2nD.nlognE.n23、数据是对客观事物的符号表示,在计算机科学中,数据的含义广泛,如图像、声音等都属于数据范畴,数据不意义的最小不可分割的单位是。A.数据元素B.数据对象C.数据结构D.数据项E.位4、下列有关线性表的叙述中,正确的是。A.线性表中的元素必须具有相同的特性B.线性表中的元素都有且仅有一个直接前驱C.线性表中的元素都有且仅有一个直接后继D.以上表述都不正确5、在一个长度为n有序的链式存储的线性表中插入一个元素,使其保持有序,其操作的时间复杂度是。A.O(n)B.O(1)C.O()D.O(n2)(A卷)第2页共7页6、关于线性表的结点的存储地址表述正确的是。A.必须是不连续的B.连续与否由其存储方式确定C.必须是连续的D.和头结点的存储地址相连续7、如下陈述中正确的是。A.串是一种特殊的线性表B.串的长度必须大于零C.串元素中的字母不区分大小写D.空串与空格串是相同的概念8、数组的逻辑结构不同于下列的逻辑结构。A.线性表B.栈C.树D.队列9、设S为一个长度为n的字符串,其中的字符各不相同,则S中的互异的非平凡子串(非空且不同于S本身)的个数为。A.2n-1B.n2C.(n2+n)/2D.(n2+n)/2-1E.(n2-n)/2-1F.以上都不对10、中缀表达式(A+B)*D+E/(F+A*D)+C的后缀形式是。A.ABDEFADC+*+/+*+B.D*AB+EFAD*+/+C+C.+*+/+*+ABDEFADCD.AB+D*EFAD*+/+C+11、链表不具有的特点是。A.插入、删除不需要移动元素B.可随机访问任一元素C.不必事先估计存储空间D.所需空间与线性长度成正比12、在一个图中,所有边数等于所有顶点的度数之和的倍。A.1/2B.1C.2D.413、设某棵二叉树中有2000个结点,则该二叉树的最小高度为。A.10B.11C.12D.1314、设某棵二叉树的中序遍历序列为BGDAECHFI,前序遍历序列为ABDGCEFHI,则后序遍历该二叉树得到序列为。A.GDBAECHFIB.IHGFEDCBAC.GDBECHIFAD.GDBEHIFCA15、已知广义表L=((x,y,z),a,(u,t,w)),从L表中取出原子项t的运算是。(A卷)第3页共7页A.head(tail(tail(L)))B.tail(head(head(tail(L))))C.head(tail(head(tail(L))))D.head(tail(head(tail(tail(L)))))16、设指针变量top指向当前链式栈的栈顶,则删除栈顶元素的操作序列为。A.top=top-1B.top=top-nextC.top-next=topD.top-next=top-next17、设森林F中有三棵树,第一,第二,第三棵树的结点个数分别为n1,n2和n3。则与森林F对应的二叉树根结点的右子树上的结点个数是。A.n1+n2B.n1+n3C.n2+n3D.n1+n2+n318、设一组权值集合W={2,3,4,5,6},则由该权值集合构造的哈夫曼树中带权路径长度之和为。A.430B.45C.50D.5519、设无向图的顶点个数为n,则该图最多有条边。A.n-1B.nC.n(n-1)D.n(n+1)/2E.n(n-1)/220、在二叉排序树中插入一个关键字值的平均时间复杂度为。A.O(1ogn)B.O(n)C.O(nlogn)D.O(n2)。二、名词解析(每题3分,共6分)1、平衡二叉树:2、哈夫曼(Huffman)树:(A卷)第4页共7页三、填空题(每空2分,共18分)1、在完全二叉树的第6层上最少有__________个结点,最多有_________个结点。2、普里姆(Prime)算法的时间复杂度为______,它对______图较为适合。3、顺序查找n个元素的顺序表,若查找成功,则比较关键字的次数最多为__次;当使用监视哨时,若查找失败,则比较关键字的次数为。4、设有一组初始记录关键字序列为(49,38,65,85,97,76,13,90,27,50),则以d=3为增量的一趟希尔排序结束后的结果为_____________________________。5、设某无向图G中有n个顶点,用邻接矩阵A作为该图的存储结构,则顶点i与顶点j互为邻接点的条件是______________________,无向图的邻接矩阵具有特性。6、若不考虑基数排序,则在排序过程中,主要进行的两种基本操作是关键字的______和记录的_____。7、在一个带头结点的单循环链表中,p指向尾结点的直接前驱,则指向头结点的指针head可用p表示为head=。8、数据的存储结构包括的表示和的表示。9、散列检索技术的关键是______和______。四、判断题(每小题1分,共8分)1、调用一次深度优先遍历可以访问到图中的所有顶点。()2、完全二叉树一定是满二叉树,满二叉树不一定是完全二叉树。()3、顺序存储结构的主要缺点是不利于插入或删除操作。()4、数组不适合作为任何二叉树的存储结构。()5、任何一个递归过程都可以转换成非递归过程。()6、设一棵树T可以转化成二叉树BT,则二叉树BT中一定没有右子树。()7、带权无向图的最小生成树的权值必是固定的。()8、在AOE图中,关键路径上某个活动的时间缩短,整个工程的时间也就必(A卷)第5页共7页定缩短。()五、程序填空题(每个空1分,共12分)1、如下的算法是从串s中删除所有与t相同的子串,并返回删除次数。intSubString_Delete(Stringtype&s,Stringtypet)//从串s中删除所有与t相同的子串,并返回删除次数{for(n=0,i=1;i=s[0]-t[0]+1;i++){for(j=1;j=t[0]&&s[i+j-1]==(1);j++);if(j(2))//找到了与t匹配的子串{for(k=i;k=s[0]-t[0];k++)s[k]=s[k+t[0]];//左移删除s[0]-=t[0];(3)}}//forreturn(4);}//Delete_SubString2、n个顶点的有向图用邻接矩阵array表示,下面是其拓扑排序算法,试补充完整。注:(1)图的顶点号从0开始计;(2)indegree是有n个分量的一维数组,放顶点的入度;(3)函数crein用于算顶点入度;(4)有三个函数push(data),pop(),check()其含义为数据data进栈,退栈和测试栈是否空(不空返回1,否则0)。crein(array,indegree,n){for(i=0;in;i++)indegree[i]=__(1)_____for(i=0,in;i++)for(j=0;jn;j++)indegree[i]+=____(2)___;(A卷)第6页共7页}topsort(array,indegree,n){count=___(3)____for(i=0;in;i++)if(___(4)____)push(i)while(check()){vex=pop();printf(vex);count++;for(i=0;in;i++){k=__(5)_____if(____(6)___){indegree[i]--;if(___(7)____)push(i);}}}if(_(8)__)printf(“图有回路”);}六、算法设计题(每题8分,16分)1、设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。typedefstruct{intvertex[m];intedge[m][m];}gadjmatrix;typedefstructnode1{intinfo;intadjvertex;structnode1*nextarc;}glinklistnode;typedefstructnode2{(A卷)第7页共7页intvertexinfo;glinklistnode*firstarc;}glinkheadnode;2、众数问题:在一个由整数组成的线性表中,出现数数最多的数称为众数.试设计一个寻找众数的算法,并分析其计算复杂性。
本文标题:2011专升本插班生《数据结构》试卷
链接地址:https://www.777doc.com/doc-5315435 .html