2019北京计算机专硕844专业课真题回忆

todayswork · 发表于 2019-2-15 16:19

[芒果]综合应用题（55分）
给一组数，用的是取余的求关键字方法，分别用线性探测法，除留余数法，链地址法，求查找成功ASL（15分）

给一组数，分别用二叉排序树和二叉平衡树求查找成功ASL给一组数，用小根堆法排序，写出每一步步骤。(7分)

给一个图分别用普里姆算法，克鲁斯卡尔算法求最小生成树，写出每步步骤。

给一个无向图，第一问写出邻接矩阵，第二问根据邻接矩阵写出深度优先搜索，第三问写广度优先搜索。

[芒果]算法题一共45分，三个大题每个15分。

写出顺序表和链表的定义类型，数据类型（3分好像），设计一个算法将含有n个元素的顺序表转换为带头结点的单链表（12分）

一共三问，第一问写出孩子链表表示法定义类型，数据类型用户自己定义；第二问，写出求二叉树上一个已知的结点的度的算法；第三问，设计一个算法求二叉树的度。

给出二叉排序树的结构体定义，设计一个算法实现二叉排序树的插入，已知几个指针（好像有父结点指针，指向当前结点的指针）

[芒果]选择题有求时间复杂度，已知出栈第一个数i求第j个数什么时候出栈，

[芒果]填空题求栈的最小容量，算法的五个特性（什么输入输出正确性什么的），给了三个填两个空。程序填空题，填三个空（折半查找的算法），带头结点的双循环单链表为空的条件是什么，插入类排序除了有直接插入排序还有什么，哈夫曼树的前缀码已知已经有0，10问还可以表示几个数，迪杰斯特拉算法是根据什么次序求最短路径的，构建哈希表的三要素除了函数，表长还有什么。

其他的不知道了

来自Android客户端