专升本吉林省数据结构试题及答案

1、2005年吉林省普通高校专升本教育试点考试计算机科学与技术专业综合试卷（数据结构部分共90分）一、填空题（每小题2分，共26分）栈的主要特点是_先进后出_；队列的主要特点是_先进先出_。在一长度为n的向量中的第i个元素（next=P;P-next=S;B.S-next=P-next;P-next=S;C.S-next=P-next;P=S;D.P-next=S;S-next=P;一个栈的入栈序列为1，2,，n，其输出序列为P1，P2，Pn，若P1=n，则Pi为（）。A.iB.n-iIC.n-i+1D.不确定数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址为S

2、A开始连续存放在存储器内，该数组按行序存放时，元素A85的起始地址为（）。A.SA+141B.SA+144C.SA+222D.SA+225将递归算法换成对应的非递归算法时，通常需要使用（）。A.栈B.队列C.链表D.树任何一棵二叉树的叶结点在前序、中序和后序遍历中的相对次序是（）。A.不发生改变B.发生改变C.不能确定D.以上都不对已知一有向图的邻接表存储结构如图所示，根据有向图的深度优先遍历算法从顶点V出发，所得到的顶点序列为（）。A.V1,V2,V3,V5,V4B.V1,V2,V3,V4,V5C.V1,V3,V4,V5,V2D.V1,V4,V3,V5,V2快速排序方法在（）情况下最不利于发

3、挥其长处。A.要排序的数据量太大B.要排序的数据中含有多个相同值C.要排序的数据已基本有序D.要排序的数据个数为奇数有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为（）。A.35/12B.37/12C.39/12D.43/12三、算法设计与解答（共44分）设有一组关键字19，01，23，14，55，20，84，27，68，11，10，77，采用哈希函数：H（key）=key%13,采用开放地址法的二次探测再散列方法解决冲突，试在018的散列地址空间中对该关键字序列构造哈希表。（7分）012345678910111213141516171

4、8270114556884192010231177试用普里姆法构造如图所示的一棵最小生成树（。要求每加入一个结点，画一个图）。（8分）参考答案：4(1)(2)(4)611825748364(5)(6)已知二叉树的先序遍历序列为“-,+,a,*,b,c,-,/,d,e,f”中序遍历序列为：“a,+,b,*,c,-,d,/,e,-,f”，画出此二叉树，并写出它的后序遍历序列。（8分）参考答案：后序遍历序列：a,b,c,*,+,d,e,/,f,-,-a*/fbcde二叉树采用链式存储结构，试设计一个算法计算一棵给定二叉树的单孩子结点数。(只写算法函数)(11分)intonechild(btree*b

5、)参考答案代码：intonechild(btree*b)intnum1,num2;if(b=NULL)return(0);elseif(b-left=NULL&b-right!=NULL)|(b-left!=NULL&b-right=NULL)return(1);elsenum1=onechile(b-left);num2=onechile(b-right);return(num1+num2);已知线性表中的元素以值递增有序排列，并以单链表作为存储结构，试写一高效的算法，删除表中所有值相同的多余元素(使得操作后的线性表中所有元素的值均不相同)，同时释放被删除结点空间，并分析你的算法的时间复杂度。(10分)statusDelete_Equal(Linklist&L)参考答案代码：statusDelete_Equal(Linklist&L)p=L-next;q=p-next;while(p-next)/pODo%Iif(p-d