中国石油大学华东-859-2020-真题回忆版

2020 年中国石油大学（华东）859 真题-回忆版 题目结构改变：看到题我就笑了，删除了 50 分的单选题，改为了 30 分的简答题、70 分的应用题、50 分的算法题；题干条件记得不全，每年官方会给出历年试题，不用担心，回忆版就大概知道考点以及问法就行）一、简答题 1、简述常见的存储结构的优缺点。2、描述你对“算法的渐进复杂性”的理解。3、队列也是一种线性表，请简述其与线性表的共性以及其特性。二、应用题（一共 9 道题）1、画出某个图对应的广度优先遍历生成树 2、画出由邻接表表示的有向图 3、一棵二叉树只有度为 2 和度为 0 的结点，已知度为 0 的结点为 n 个，问你分支数为几个。4、Dijkstra 算法，写出起点到所有顶点的最短路径，注意写出 dist数组的变化。5、已知有红色、白色、蓝色的若干个球，每个球均独立地放在桶中，桶不透明，请你在只能观察一次桶中的球的颜色且只能用交换操作的情况下，描述如何使得交换完成后所有球的颜色排序是，红色居左，白色居中，蓝色居右。6、给你 9 个关键字，请你用 H（key）=key%7 画出链地址法解决冲突的哈希表，然后让你计算在等概率的情况下的平均查找长度。7、某五对角（100*100）矩阵按照行优先压缩存储到一维数组当中，请问你55,56元素在一维数组中的位置。8、告诉你二叉树利用队列实现的非递归广度优先遍历的思想（即入队、循环出队判断左右孩子是否存在，如果存在的话就入队，知道队空，循环结束），然后给出你整个过程中的队列变化，让你画出其对应的二叉树。9、求解一个程序的中 i=i+1 操作的执行次数以及算法时间复杂度(这道题印象深一点，这么简单竟然写错了，唉)While(in)For(j=0;jn;j+)i=i+1;i=i*2;三、算法题（一）运用你所熟悉的语言写出下列算法题的代码（二）每个算法题要给出数据的存储类型的定义1、已知带头结点的循环单链表有序，请你设计一个插入算法，使得元素 x 插入后链表仍然有序。2、写出求解中序表达式的算法。（其中栈的相关操作仅需简写，但要给出结构体变量的定义以及相应的注释）3、写出判定一颗二叉链表存储的二叉树是否是二叉排序树的算法。（王道书上原题，虽然我没看）4、已知一图使用邻接矩阵存储，请你写出求其度的算法。（注意：算法中要对图进行分类，如果是有向图则求其入度和出度，如果是无向图求其度）。各个学校计算机/软件专业考研真题 免费分享 h t t p s:/g i t h u b.co m/cs s e k y/cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研