山东大学计算机学院数据结构真题

2012年山东大学计算机学院数据结构真题共13大题150分1、分析下列函数，描述函数功能，并求函数的时间复杂度。S=0For(inti=1;i<=n;i++){Intp=1;For(intj=1;j<=I;j++)P*=j:S+=p;}2、对于含有n个元素的有序数组，查找各个元素的概率相等，采取折半查找时，最少要比较多少次，最多要比较多少次，平均要比较多少次。当n个元素无序时，采取折半查找，最多需要多少次，最少需要多少次。3、描述栈与队列的相同点和不同点。4、二叉树，先序遍历得到abdfceg，中序遍历得到fdbaceg，该二叉树的叶节点是什么。5、有5000个无序元素，公式化描述（数组），要求最快速度选取最大的10个元素，请问，在快速排序，堆排序，基数排序，归并排序四种方法中，采取哪种方法最好，为什么？6、构建散列表，散列函数为hashf（k）=k%11.已知关键字序列为（8,15,27,2,13,31,19）（具体数字记不清了，我写的数字性质是一样的），请画图表示采取线性开放式寻址和链表地址法存贮。7、（1）如果G1是一个具有n个顶点的连通无向图，那么G1最多有多少条边，最少有多少条边？（2）如果G2是一个具有n个顶点的强连通有向图，那么G2最多有多少条边，最少有多少条边？8、在一篇电码中，由abcde字母组成，其分别出现的次数为4,8,25,37,6（具体数字记不清了，我写的数字性质是一样的）。构造huffman树，给出各个字母的huffman编码，该篇电码的总电码数是多少。9、有一图，顶点为v1，v2，v3，v4，v5，边的集合为（v2，v1），（v5，v3），（v1，v4）（v3，v2），（v1，v3），（v3，v4），（v4，v5），画出该图，该图是强连通有向图吗？10、有一函数fun的功能是将字符串中每个单词的最后一个字母改成大写，例如Iamastudenttoexam.改成IaMAstudenTtOexaM.请将该函数补全。Voidfun(char*P){Intk=0;For(;p;p++)If(k=1){If(*p==‘’){【1】；【2】=upper(*(p-1));}}ElseK=1;}11、编写算法，求出二叉树中节点的度数为1的个数，并以n返回。（要求不能使用递归），写出算法思想，并写出程序。12、编写程序，给一正整数m，求出在1至m之间（包括m）中，能够被11或7整除的数字，保存在数组a中，函数返回在1至m之间（包括m）中，能够被11或7整除的数字的个数，例如m为,30，则将（7,11,14,22,21，28）保存在数组a中，函数返回5.13、有向图和无向图，分别采取邻接矩阵和邻接链表的方法存储。（1）怎样求出图中的边的数目？（2）怎样判断在顶点i，j之间是否存在边？（3）怎样计算顶点i的度？山东大学07计算机真题（回忆整理）1.（8分）（1）for(inti=1;i<=n;i++){intp=1;for(intj=1;j<=I;j++)p*=j;s+=p;}描述功能，并分析时间复杂度。（2）对于1个n元素顺序表，用折半查找，成功查找时，最大最小比较次数各是多少？2.（8分）n阶三对角矩阵A，按行保存到一个数组B中，其中A[1][1]存入B[0]，问：（1）B中有多少元素（2）用i,j表示矩阵元素在B中的索引k（3）用k表示i,j3.（10分）（1）.一个中缀表达式为3*y-a/y↑2，求其后缀表达式（2）描述堆栈在处理后缀表达式中的作用（3）对于（1）中后缀式写出栈的变化]4.（12分）写出用数组实现字符串类String的类定义，并实现IsSym函数。其中IsSym表示该字符串是中心对称的，例如xyzzyx，xyzyx，若是返回true，否则返回false5.（12分）写出单链表类chain的类定义，并实现BubbleSort函数，不能创建新节点，也不能删除旧节点，其他函数省略。BubbleSort表示将原链表按非递减顺序冒泡排序。6.（10分）一个二叉搜索树，设任一条从根到叶子的路径包含的节点集合为S2，这条路经所有左边的点的集合为S1，右边所有点集合为S3，设a,b,c分别为S1，S2，S3中的任意元素，是否有a<b<c？为什么？7.（20分）（1）写出最小堆的类声明。（2）写出用最小堆实现Huffman编码的思想，并给出算法。8.（10分）一个8key值的3阶B树最多有多少节点？最少有多少？并画出图表示。9.（10分）如下图所示的AVL搜索树若先后插入70和60两个数后，树的最小不平衡树各是哪个？怎样旋转能使其达到平衡？画出树的形态。为什么仅调整最小不平衡树就不存在其他不平衡点？10.（20分）加权有向图的邻接矩阵类为AdjacencyWDigraph（1）举出一个至少包括5个节点的例子，并写出他的邻接矩阵。（2）写出AdjacencyWDigraph的类定义。（3）在此基础上写出宽度优先搜索算法BFS，可以使用队列类Queue。11.（20分）（1）从一点S出发对一个有向连通图求最短路径，按照如下贪婪准则：每次选择一个节点，该节点是与已选节点最近的尚未被选到的节点，直到到达目的节点。问：这种方法得到的是最短路径吗？（2）若不是，举一反例，并写出你认为正确的一种方法。12（10分）.什么是分治法？有什么原则？有哪些算法用了这种思想？举出一例，写出算法思想。祝以后的学弟学妹们考个好成绩，在考研中这个论坛给了我很大的帮助，现在我将我的考研经验分享一下山东计算机的自主命题比较简单，建议（1）将05年以后的真题，回忆版好好做一下，有重复，并且出题重点一脉相承。（2）对照考研大纲将原书看一遍，时间少也要将大纲标明“掌握”的内容精读，时间多将标明“了解”的内容通读，时间再多也不用去读未明确的内，或许山东本校都不学习。（3）买一本复习资料（算法与数据结构考研试题精析），机械工业出版社，一定要看，有原题，有解题方法。只要做好以上三点，考研130+在等你。相信你自己，你行的。写于2012年考研结束第二天，为我自己留个mark，也希望看到的你能够将它流传下去。（为我家子洋求祝福，都快成孩他爹了，我容易吗我）2002年考研试题一、回答下列问题：（24分）1，如果用一个循环数组q[0..m-1]表示队列时，该队列只有一个队列头指针front，不设队列尾指针rear，而改置计数器count用以记录队列中结点的个数。1）编写实现队列的基本运算：判空、入队、出队（3分）2）队列中能容纳元素的最多个数是多少？（1分）2、设有对角矩阵a[1..n,1..n]把非零元素按列存储在向量b[1..3*n-2]中，使得b[k]=a[I,j].求：（1）用I,j表示k的下标变换公式（2分）（2）用k表示I,j的下标变换公式（2分）3、设二叉排序树中关键字由1到1000的整数组成，现要查找关键字为363的结点，下述评关键字序列哪一个不可能是在二叉排序树中找到的序列？说明原因。（4分）（1）51，250，501，390，320，340，382，363（2）24，877，125，342，501，623，421，3634、设有n个无序元素，按非递减次序排序，但只想得到前面长度为k的部分序列，其中n>>k，最好采用什么排序方法？为什么？（2分）如果有这样一个序列{59，11，26，34，17，91，25}，得到的部分序列是：{11，17，25}，对于该例使用所选择的方法实现时，共执行多少次比较？（3分）5、在B-树和B+树中查找关键字时有什么不同？（2分）6、写出对关键字序列{503，087，512，061，908，124，897，275，653，426}建立一棵平衡二叉树的过程，并写出调整平衡时的指针变化。（5分）二、解答下列问题：（10分）1、画出对长度为10的有序表进行二分查找的判定树并求其等概率时查找成功的平均查找长度（5分）。2、设有一组关键字{9，01，23，14，55，20，84，27}，采用哈希函数：H（key）=keymod7，表长为10，用开放地址法的二次探测再散列方法Hi=(H(key)+di)mod10(di=1*1,2*2,3*3….)解决冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度（5分）。三、已知L为没有头结点的的单链表中第一个结点的指针，每个结点数据域存放一个字符，该字符可能是英文字母字符或数字字符或其他字符，编写算法构造三个以带头结点的单循环链表表示的线性表，使每个表中只含同一类字符。（要求用最少的时间和最少的空间）（15分）四、对以二叉链表存储的非空二叉树，从右向左依次释放所有的叶子结点，释放的同时把结点值存放到一个向量中要求：（1）用文字写出实现上述过程的基本思想（3分）（2）写出算法（12分）五