2018年山东工商学院数据结构考研真题B卷.doc

2018年山东工商学院数据结构考研真题B卷一、简答题（共4题，每题10分）1.解释顺序存储结构和链式存储结构的特点，并比较顺序存储结构和链式存储结构的优缺点。2.什么样问题的存储结构可以利用栈结构?请举例说明。3.什么是线索二叉树?为什么要线索化?4.对比分析直接插入排序和希尔排序两种算法的异同点。希尔排序为什么比直接插入排序快?二、应用题（共6题，每题15分）1.给定下列图 G1）求最小生成树，画出逻辑图;2）画出G的邻接矩阵。2依次输入元素10，6，8，3，42，25，7，30，27，60试生成一棵二叉排序树。（1）画出生成之后的二叉排序树;（2）写出中序遍历该二叉排序树的序列;（3）假定每个元素的查找概率相等，计算查找成功时的平均查找长度。3.已知一个无向图的顶点集为a，b，c，d，e，其邻接矩阵如下所示（1）画出该图的图形;（2）根据邻接矩阵从顶点 a 出发进行深度优先遍历和广度优先遍历，写出相应的遍历序列。4.简述哈夫曼编码的基本思想。假设用于通信的电文，由字符集a，b，c，d，e，f，g，h中的字母构成，这8个字母在电文中出现的概率分别为0.07，0.19,0.02, 0.06,0.32, 0.03,0.21,0.10. （1）为这8个字母设计哈夫曼编码。（2）哈夫曼编码的平均码长是多少?5.简述快速排序法的基本思想。已知序列503，87，512，61，908，170，897，275，652，462，采用快速排序法对该序列作升序排序时的前三趟的结果。6.什么是哈希表?什么是哈希冲突?设有12个数据25，40，33，47，12，66，72，87，94，22，5，58，将它们存储在哈希表中，哈希函数为H（key）=key mod 11，利用开放定址法中的线性探测再散列解决冲突。三、编程题（共2题，每题10分。先描述算法基本思想，然后给出代码。）1.简述算法基本思想，编写算法程序，在带头结点的单链表上删除其值等于x的所有元素。（假定x为int类型）函数声明void delete（LNode *head，int x）2.简述折半查找的基本思想，写出折半查找程序。其中数组 a 存放从小到大的int 类型数据。Key 为要查找的关键字，n为数组的长度。int Search_bin(int a, int key, int n)