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

发布时间：2022-09-16 发布人：admin 分类：说明书资料大小：0.16M 资料格式：doc 举报版权申诉

第1页 / 共4页

第2页 / 共4页

第3页 / 共4页

第4页 / 共4页

文本预览

2018 年山东工商学院数据结构考研真题 B 卷一、简答题（共 4 题，每题 10 分） 1.解释顺序存储结构和链式存储结构的特点，并比较顺序存储结构和链式存储结构的优缺点。 2.什么样问题的存储结构可以利用栈结构?请举例说明。 3.什么是线索二叉树?为什么要线索化? 4.对比分析直接插入排序和希尔排序两种算法的异同点。希尔排序为什么比直接插入排序快? 二、应用题（共 6 题，每题 15 分） 1.给定下列图 G∶ 1）求最小生成树，画出逻辑图; 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)

分享到：

赞收藏

资料库

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

相关推荐

考研

热门标签

最新资料