2016人大计算机855真题（回忆版）数据结构一、选择题10×2串是线性表查链表第i个节点时间复杂度森林→二叉树25个结点的…Kmp算法的next数组有序情况下，快速冒泡等排序的时间比较9个顶点构成连通图，最少需要几条边，构成非连通图最多几条边2015个结点的完全二叉树的叶子节点个数可能是？A:503B504C：1007D1008二、4×51.哈希表的构造、再散列、拉链法平均查找长度2.大顶堆的构造，画出步骤3.给出二叉树中序遍历和后序遍历，画出所有可能的二叉树4．迪杰斯特拉最短路径三、10数组A[N]循环右移k位1.写算法，借助一个辅助单元2．简述算法思想加注释3.时间复杂度为O（n）呢离散数学一、10）自然推理系统P二、10）集合A‐B=B‐A的充要条件，并证明三、10）整除偏序关系最大最小极大极小元四、10）G是循环群，证明它的子群也是循环群五、10）对群有ac=ca|a|=m|c|=n证明|ac|=mn？操作系统一、选择题很脑残（10×3）二、先来先服务最高相应比循环（10）三、Linux读文件吧？（10）数据库一、简答题5×3=15分1.物理独立性逻辑独立性2.3.二、SQL语句4×5=20分感觉有点难度，4个表，连接操作比较复杂学生系社团参加社团信息考了简单的SQL查询、带全称量词的SQL、关系代数三、简答题5×3=15分1.查询过程2.（好像也跟物理存储有点关系）2.物理优化应该考虑哪些因素
