2017年山东大学数据结构考研真题.doc

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

第1页 / 共3页

第2页 / 共3页

第3页 / 共3页

文本预览

2017 年山东大学数据结构考研真题一、简答题（每小题 6 分，共 30 分） 1.设散列表长度为 11，散列函数 Hash（k）=k ，若输入序列为{22，41，53，46，30，13.1， 67}，解决溢出的方法为线性开型寻址散列（1）、请构造该散列表。（2）、搜索元素 30 和元素 67 所需要的比较次数是多少? 2.对关键字序列（10，718.31、15，9，22、26），用下列排序算法进行递增排序，写出第一趟结束后的序列（1）冒泡排序（2）快速排序（选第一个记录为支点）（3）基数排序（基数为 10）。 3.已知一棵度为 k 的树中有 n1 个度为 1 的结点，n2 个度为 2 的结点，……，nk 个度为 k 的结点，则该树中有多少个叶子结点? 4．含有 n 个内部节点的血序（阶）B 树至少包含多少个关键字?叙述 B-树的用途。 5.已知某图的邻接表如下图所示，画出该图的深度优先生成树。

二、应用题（每题 10 分，共 60 分） 1.个斑级有 15 个学生，使用 1、2、3、…、I4、15 作为学号。（i，j）表示学生 i 和学生 j 参加了同一个兴趣小组。对给出的集合 S={（1，2），（6，9），（15，7），（1，6），（10，8），（8，11）}，请慕于模拟指针设计数据结构表示集合 S 中的兴趣小组 i，并罗列 S 中所有的兴趣小组。 2.假定采用下述公式来描述一个线性表∶ location(i)-(location(1)+ i - 1)MaxSize 其中 MaxSize 是用来存储表元索的数组的大小。与专门保留一个表长的做法不同的是，用变量门 rst. 和 last 来指出表的第一个元素和最后一个元素的位置。试描述如何插入删除元素，并分析操作的时间复杂性。 3. 为什么使用堆描述优能队列比使用线性逻辑描述优先队列更好? 数组 A[1∶10]=[10，60， 32，45，25，36，40，72，66，22]是否是一最大堆的数组描述，若不是，.将其调整为最大堆，写出最大堆的数组描述。 4.给出按关键字序列（19，36，88，12、16，77，60）生成的二叉搜索树和 AVL 搜索树。 5.设 G-（V，E）是至少包含一个环路的连通图，边（i，j）至少出现在一个环路中。证明图（h={VE-（i，j）}）也是连通的。 6.已知一有问阁如下所示，按 Diikstra 算法计算得到的从顶点 A 到其它各个顶点的最短路径和最短路径长度，给出求解过程。

三、算法题（每题 20 分，共 60 分） 1. 设计算法实现将数组 rls∶t 中所有奇数移到所有偶数之前，要求算法复杂度为 O（n）。 n 为数组元紧的个数。 2.设二义树采用链式存储结构，定义结点结构为（eftchild、data.rightchild，其中 data 为元素的值，eftchild 和 rightchild 分别表示指向左子结点的指针和指向右子结点的指针，root 为指向根的指针，p 所指的节点为任一给定的节点，编写算法，求从根节点到 p 所指节点之间路径。叙述算法思想并给出算法实现，分析算法的时间复杂性。 3.假设有向图以邻接表存储，试编号算法朋除弧（i，j）。

分享到：

赞收藏

资料库

2017年山东大学数据结构考研真题.doc

相关推荐

考研

热门标签

最新资料