山东大学2019年数据结构研究生入学考试试题.docx

新祥旭考研官网 http:/www.xxxedu.net/山东大学 2019 年数据结构研究生入学考试试题一、简答题(共 3题，共 26分)1. (8分)散列表长度为 13， 散列函数为 Hash(k) =k%13。 请分别写出序列(12, 8,16，27,21,17,3，28，47)的线性开型寻址散列存储结构和链表散列结构。2. (10 分)假设用于通信的电文由字符集a, b, c, d, e, f, g中的字母构成，它们在电文中出现的频率分别为31，16, 10, 8, 11, 20, 4.(1)画出霍夫曼树(霍夫曼树构造中，左子树权值小于等于右子树)，并求WPL;(2)为这 7个字母设计霍夫曼编码(分支编码左 0右 1);(3)对这 7个字母进行等长编码，至少需要几位二进制数?霍夫曼编码比等长编码使电文总长压缩多少?3. (8 分)如何判别以邻接表方式存储的无向图中是否存在由顶点 u到顶点v的路径(uv)，请描述出实现思路。二、算法题(共 2题，每小题 12分，共 24分)1. (12分)在包含 n个元素的单向链表中，找到链表中倒数第 k个元素，kn.要求时间复杂性为 0(n)。(1) 描述算法的设计思想(2) 根据设计思想,给出算法实现,关键之处请给出注释.2. (12分)设二叉树采用链表描述，t 为指向根节点的指针，节点结构为(1eftchi ld, data, rightchild),其中 data为元素的值，leftchild 和rightchild分别表示指向左孩子结点和右孩子结点的指针。设计算法，判断二叉树是否为最小堆。(1)描述算法的设计思想(2)根据设计思想,给出算法实现,关键之处请给出注释.(3)说明你所设计算法的时间复杂度。