2017中国人民大学计算机科学与技术(855)、软件工程(856)真题(回忆版)中国人民大学2017年硕士研究生入学考试真题(回忆版)计算机科学与技术(855)软件工程(856)2017中国人民大学计算机科学与技术(855)、软件工程(856)真题(回忆版)声明本真题包含学硕(855)计算机专业基础综合和专硕(856)软件工程基础综合两部分。因为是回忆版的真题，所以无法保证试题的准确性，仅供参考。由于整理者水平有限，难免出现一些错误，请谅解。本真题由2017年人大计算机科学与技术和软件工程考研研友共同贡献和整理，不许用于任何商业用途。鸣谢：分针、WELL、旺仔、韩雪冉、Less、Galson2017中国人民大学计算机科学与技术(855)、软件工程(856)真题(回忆版)学硕(855)计算机专业基础综合数据结构一、选择题(5个*3分)1、出栈顺序2、next数组3、2016个结点的八叉树，高度是多少4、顶点为n、边数为e的有向图，求拓扑排序的时间复杂度二、简答题(4个*5分)1、长度为2016的顺序表：(1)第i个位置删除和插入元素，需要移动多少个元素；(2)插入和删除，平均需要移动多少个元素。2、普里姆算法求最小生成树，按顺序写出边。3、给出a、b、c、d、e、f、g、h八个结点和每个结点的权值：(1)构造哈夫曼树，要求左子树根的权值小于等于右子树根的权值；(2)求出每个结点的哈夫曼编码。4、哈希表：除留余数法的Hash函数，冲突处理方法分别用线性探查法和链地址法，分别求出两种方法的平均查找长度三、算法题(15分)1)图以邻接矩阵形式存储，写出完整的图的定义；2)输出一条由顶点v到顶点u的简单路径；3)输出全部简单路径。离散数学一、自然推理系统两道1、命题逻辑：给出前提和结论。2、谓词逻辑：符号化下述语句，并进行推理证明。二、集合论1、偏序关系：告诉一个偏序关系，求最大元、最小元、极大元、极小元。2、等价关系：已知R是等价关系，关系S满足
∈{∃c|∈R∧∈R}，证明S也是等价关系。三、代数结构1、证明阶数小于6的群，都是交换群。2、a,b,c都是群G中的元素，证明|abc|=|bca|=|cab|。2017中国人民大学计算机科学与技术(855)、软件工程(856)真题(回忆版)数据库一、选择题(7个*2分)1、和层次模型、网状模型相比，以下哪个不是关系数据库的特点(查询效率高)2、并发控制：给出一个调度，问是否遵守两段锁协议；最高符合哪一级的封锁协议。3、(A,B)是第几范式4、安全性二、故障恢复(16分)给出一个带有检查点的日志记录(里面是事务对数据的修改操作)，问在某一步之前(只有最...
