《数据结构》考试试题

第1页共7页A卷河北科技大学2010——2011学年第1学期《数据结构》期末考试试题(A)学院班级姓名学号题号一二三四五总分得分一判断题（共10分，每题1分）√或×1.对一颗二叉排序树，按后序遍历得出的结点序列是从小到大的序列。2.就平均查找长度而言，顺序查找最大，折半次之，分块查找最小。3.哈希查找需要多次比较才能找到。4.一个有向图的邻接表与逆邻接表中的结点个数可能不等。5.在具有n个顶点的无向图中，若边数大于n-1，则该图可能不连通。6.二叉树中序线索化后，任一结点均有指向其前驱和后继的线索指针。7.用堆结构存储串可不必建立索引表。8.循环队列不存在溢出问题。9.栈是实现函数递归调用所必须的存储结构。10．从某串中任意取出若干个字符序列可称为该串的子串。二选择填空题(共30分，每题3分)1．用顺序存储结构实现线性表的优点是()。A.便于随机存取B.存储空间可动态管理C.便于数据元素的插入和删除操作D.数据元素的物理顺序与逻辑顺序不相同2.设数据项abcdef以所给的次序进栈，若在进栈操作时，允许出栈操作,则下面可得到的出栈序列为()。A．fedcabB.becafdC.dcefbaD.cabdef第2页共7页A卷3．若串Ｓ＝＂English＂，其子串的个数是()。A．9B．16C．36D．294.设树T的度为3，其中度为1，2和3的结点个数分别为4，2，1则T中的叶子数为()。A．5B．6C．7D．85.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为()个。A．2h-2B．2h-1C．2h+1D．2h+26.设给定权值的叶子总数有n个，其哈夫曼树的结点总数为()。A．不确定B．2nC．2n+1D．2n-17.已知一颗二叉树的中序和后序遍历序列分别为BDCEAFHG和DECBHGFA,该树的先序遍历序列为（）。A.EFGHABCDB.ABGHCDEFCABCFGHDED.ABCDEFGH8.有向图G=(V,E)，其中V={a,b,c,d,e,f}，E={a,b，a,c，a,e，b,e，c,f，f,d，e,d}，对该图进行深度优先遍历的正确结果是()。A.a,b,e,c,f,dB.a,c,f,e,b,dC.a,e,b,c,f,dD.a,e,d,f,c,b9．在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的()倍，在一个无向图中，所有顶点的度数之和等于所有边数()倍。A.1/2B.2C.1D.410．若查找每个记录的概率相等，则在具有n个的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为()。A．(n-1)/2B.n/2C.(n+1)/2D.n程序填空（共20分,每空2分）第1题：折半查找typedefstruct{intkey；…}DataType；第3页共7页A卷typedefstruct{DataTyper[32]；int__________；}Sqlist；BinSearch(Sqlists,KeyTypek){intlow,mid,high；low=0；high=s.length-1；while(low=__________){mid=(low+high)/2；if(s.r[mid].key==_______)return_________；if(s.r[mid].keyk)high=mid-1；elselow=mid+________；}return-1；}第2题：图的深度遍历typedefstructNode{intadjvex;structNode*next;}EdgeNode;typedefstructVNode{charVertex;EdgeNode*firstedge;}VertexNode;第4页共7页A卷typedefstruct{__________adjlist[32];intn,e;}ALGraph;intvisited[32];voidDFS(ALGraphG,intv){EdgeNode*p;intw;printf(%c\t,G.adjlist[v].Vertex);visited[v]=1;for(p=G.adjlist[v].firstedge;p!=________;p=p-next){w=p-adjvex;if(!visited[w])DFS(G,_________);}}voidDFStravese(ALGraph&G){intv;for(v=0;vG.n;v++){visited[v]=0;}for(v=0;v_________;v++)if(!visited[v])_________(G,v);}四简述题（共15分，每题5分）第5页共7页A卷1.线性表可由顺序结构与链式结构实现，简述这两种存储结构的特点及应用场合。2.栈是一种“后入先出”的线性表，队列是一种“先入先出”的线性表，请各举一个例说明堆栈和队列在软件中的应用。3.对于任意一颗二叉树，设度为0的结点个数为n0，度为2的结点个数为n2，试证明n2=n0+1。五编程题（25分）1.已知一个带头结点的链表，拥有A,B,C,D,E五个结点，指针H指向该表的头结点，编程实现该链表的逆置(10分)。第6页共7页A卷typedefstructnode{chardata;structnode*next;}node,*pLinkList;2.已知一个拥有N个结点的二叉树，指针T指向该树根结点，编程统计该树的结点个数。(15分)第7页共7页A卷typedefstructbnode{chardata;structbnode*left,*right;}bNode,*pTree;