北理工《813计算机专业基础》考研真题(简单回忆版).pdf

《北理工《813计算机专业基础》考研真题(简单回忆版).pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2015年第三题问答题1给一个函数问这个函数的功能是什么，2给出一个中序遍历和后序遍历画出其二叉树3给出一串数，画平衡二叉树3给出一个853-/7+画出其在栈中的变化和运算过程4哈希函数以及解决冲突方法，并求平均查找长度5给出一个邻接表，画出他的图并且让你写出他的广度优先序列和深度优先序列6算法题1给出函数的功能，让你写出这些函数，总共是三个，一个是初始化循环队列，一个是向其中插入一个数，还有删除一个数2写出平衡二叉树在不平衡时的转变方法，LL，LR这些32016年数据结构部分（120分）一填空题（6*3）1.将n个结点的单链表插入到m个结点的单链表的第k

2、个结点后面，时间复杂度为____.2.一开始循环队列front=rear，后来已知rear和front，则队列中的元素个数为____.3.已知二叉树的后序遍历序列和中序序列，则先序遍历为_____.4.已知有向图(n个顶点，e条边）是用邻接表保存的，则拓扑排序的时间复杂度为_____.5.已知线性探测处理哈希表冲突，已知表的长度为100，装填因子为0.57，则哈希表中的元素有____个。6.已知初始序列(,,,,)，则堆排序初始建成的堆为______.二选择题(2*12)1.ADT是指（答案应该是抽象数据类型)2.Dijkstra可以求什么类型的最短路径A

3、.有向图B.有向网C.D.都可以3.已知B树的度为7，则每个节点最少的孩子节点个数为多少4.把已知关键字按照不递减进行推排序，则应该采用A.小顶堆B.大顶推C.都可以D.都不可以5.用数组来保存深度为4，节点数为11的二叉树，则数组的长度最少为多少6.准确的来说，哈夫曼树是一种什么树？A.最优树B.次优树C.每个节点度为2的树D....7.三简答题（12*4）1.给出归并排序的几个函数代码a.写出每个函数的功能是什么b.该算法对空间存储要求有什么不合理处，提出你的改进方法2.a.把表达式中缀表达式（不含有括号）改为后缀表达式，简要说明转换方法。b.给出一个

4、后缀表达式（很简单）,说明运算符栈的变化过程3.给出一个AOE网a.写出每个顶点的最早开始时间和最晚开始时间b.写出每个活动的最早开始时间和最晚开始时间c.写出图中所有的关键路径4.给出一个函数代码（关于单链表的）,写出该函数的功能。四算法设计题（15*2）1.给出栈的存储结构（顺序栈），写出栈的创建，出栈和入栈的函数。2.给出二叉树的存储结构（采用孩子兄弟村存储法）,按照先序遍历的顺序，求节点P所在树中的深度（根的深度为1）.2018年