2013年中国人民大学(数据结构)考博试题回忆版

时间：2023-02-10 11:21:16 阅读：最新文章文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

一、单项选择10分：一个5分。一个是森林化为树，算结点的选择。一个忘记了。。

二、填空10分。内容大概是关于哈弗曼树的最少和最多结点数5分。一个是13个结点煌图

最少有几条边可联通，最多有几条边不可联通。5分

三、图。PRIM图，和深度两种。条件一定得看清。从D结点开始。妈的，开始没看请，写

满了才看错了。。又重写。弄的脏乱差。。

四、如何判定一二叉树是排序树。写算法。并求(O)时和O(空间).10分

五、哈希表。给出几个数据，我记得有两个冲突，用线性探测法和链表法处理。分别求平均

查找长度10分

六、堆排序。构建及排序算法。要高效并举例。15分七、串的匹配。也要高效。10分

八、图的邻接矩阵，定义，写算法。求路径。求从一个结点到指点结点长度为K的路径。

写算法。要求时空高效。15分