2011年韩山师范学院本科插班生《数据结构》试卷

（A卷）第1页共6页12011年韩山师范学院本科插班生考试试卷计算机科学与技术专业数据结构一、单项选择题（每题2分，共40分）1、在一个长度为n的顺序存储的线性表中，向第i个元素（1≤i≤n+1）之前插入一个新元素时，需要向后依次移个元素。A.n-iB.n-i+1C.n-i-1D.i2、若进栈序列为1、2、3、4；进栈过程中可以出栈，则是不可能的出栈序列。A.3、4、2、1B.2、4、3、1C.1、4、2、3D.3、2、1、43、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂性为。A.O(1)B.O(n)C.O(n2)D.O(log2n)4、从一个具有n个结点的单链表中查找其值等于X结点时，在查找成功的情况下，需平均比较个结点。A.nB.n/2C.（n-1）/2D.（n+1）/25、一个中缀算术表达式为[5+（7-X）]*Y，则对应的后缀算术表达式为。A.57-+X–Y*B.57X+-Y*C.57X-+Y*D.57XY-+*6、在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，那么度为0的结点数为个。A.4B.5C.6D.77、在存储数据时，通常不仅要存储各数据元素的值，而且还要存储。A.数据的处理方法B.数据元素之间的关系C.数据元素的类型D.数据的存储方法8、在一棵二叉树中第五层上的结点数最多为。A.8B.15C.16D.329、在一棵完全二叉树中，若编号为i的结点有右子女，则该结点的编号为。A.2i-1B.2i+1C.2i-1D.i/210、由权值分别为16,12,19,16,28的叶子结点生成一棵哈夫曼树，它的带权路径长度为。A.91B.126C.148D.21011、以知8个数据元素为（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成一棵二叉排序树，则该树的深度为。A.4B.5C.6D.712、在一个图中，所有顶点的度数之和等于所有边数的倍。（A卷）第2页共6页2A.1/2B.1C.2D.413、用二分法查找一个长度为10的、排好序的线性表，查找不成功时，最多需要比较次。A.5B.2C.4D.114、设散列(Hash)函数为H(K)=KMOD7,一组关键码为（23,14,9,6,30,12，18），散列表T的地址空间为0..6。用线性探测法解决冲突，依次将这组关键码插入T中，得到的散列表为。A.0123456146239183012B.0123456141823930126C.0123456141292330186D.0123456142330141812915、如果一棵二叉树中任何一个结点的值都小于它的左子树上所有结点的值而大于它的右树上所有结点的值，要得到这棵二叉树中各结点值的递减序列，应按次序排列结点？A.先序B.中序C.后序D.按层16、在一个具有N个顶点的无向完全图中，包含有条边。A.n（n-1）/2B.n（n-1）C.n（n+1）/2D.n217、在一个3阶的B树上，每个结点所含的子树数目最多为，最少为。A.1，3B.2，1C.3，2D.4，418、采用二分查找的方法查找长度为n的有序表时，查找每个元素时平均比较次数对应的判定树的高度（假定高度大于等于2）。A.小于B.大于C.等于D.大于等于19、一组记录的排序码为（25，48，16，35，79，82，23，40，36，72），其中含有5个长度为2的有序表，按归并排序方法对该序列进行一趟归并后的结果为。A.（16，25，35，48，23，40，79，82，36，72）B.（16，25，35，48，79，82，23，36，40，72）C.（16，25，48，35，79，82，23，36，40，72）D.（16，25，35，48，23，40，36，72，79，82）20、一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为。A.（79，46，56，38，40，80）（A卷）第3页共6页3B.（84，79，56，38，40，46）C.（84，79，56，46，40，38）D.（84，56，79，40，46，38）二、名词解析（每题3分，共6分）1、算法的时间复杂度：2、二叉排序树：三、填空题（每空2分，共18分）1、从一维数组a[n]中顺序查找出一个最大值元素的时间复杂度为，输出一个二维数组b[m][n]中所有元素值的时间复杂度为。2、在下面数组a中链接存储着一个线性表，表头指针为a[0].next，则该线性表为。a012345678datanext3、在循环双向链表中表头结点的左指针域指向结点，最后一个结点的右指针域指向结点。4、快速排序在平均情况下的时间复杂度为，在最坏情况下的时间复杂度为。5、已知一棵3阶B树中含有50个关键字，则该树的最小高度为，最大高度为。四、分析题（每小题4分，共8分）请对下图的无向带权图；（1）写出它的邻接矩阵；（2）并按普里姆算法求其最小生成树。6056423874254376201（A卷）第4页共6页4五、程序填空题（每个空2分，共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]==t[];j++);if(j)//找到了与t匹配的子串{for(k=i;k=s[0]-t[0];k++)s[k]=s[k+t[0]];//左移删除s[0]-=t[0];n++;}}//forreturn;}//Delete_SubString2、下面是基于图的深度优先搜索策略写的一算法，判别以邻接表方式存储的有向图中是否存在由顶点Vi到Vj的路径（i≠j）。#defineMAX_VERTEX_NUM20typedefstructArcNode{intadjvex;structArcNode*nextarc;InfoType*info;}ArcNode;typedefstructVNode{VertexTypedata;ArcNode*firstarc;（A卷）第5页共6页5}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices;intvexnum,arcnum;intkind;}ALGraph;intvisited[MAXSIZE];//指示顶点是否在当前路径上intexist_path_DFS(ALGraphG,inti,intj)//深度优先判断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0{if()return1;//i就是jelse{visited[i]=1;for(p=G.vertices[i].firstarc;p;p=){k=p-adjvex;if(&&exist_path(k,j))return1;//i下游的顶点到j有路径}//for}//else}//exist_path_DFS六、算法设计题（每题8分，16分）1、已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一算法，删除表L中所有值大于mink且小于maxk的所有元素。typedefstructLNode{ElemTypedata;structLNode*next;}LNode,LinkList;StatusDelete_Between(Linklist&L,intmink,intmaxk)（A卷）第6页共6页62、编写递归算法，求二叉树中以元素值为x的结点为根的子树的深度(求子树深度函数用递归算法)。typedefStructBiTNode{TElemTypedata;//数据域StructBiTNode*lchild,*rchild;//指向其左右孩子结点}BiTNodeBitree;intGet_Sub_Depth(BitreeT,intx)