2019年山东大学计算机基础综合考研真题.doc

《2019年山东大学计算机基础综合考研真题.doc》由会员分享，可在线阅读，更多相关《2019年山东大学计算机基础综合考研真题.doc（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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个元素，kAC;即将B的内容所指主存单元的数据与AC 中的数据相加，并将结果送入 AC中保存。该指令字长为存储字长，存储器按字编址。写出完成该指令所需要的全部微操作流程和节拍安排（从取指令开始）。