2017年北京邮电大学803计算机考研真题解析

"北京邮电大学803计算机考研2017年真题，包括考试科目计算机学科基础综合，涵盖算法时间复杂度、数据结构、操作系统、计算机网络等多个知识点。" 这篇文档是北京邮电大学2017年硕士研究生入学考试的计算机学科基础综合真题，主要涉及计算机科学的基础概念和理论。试卷包含了多项选择题，测试了考生对以下几个方面的理解： 1. 算法的时间复杂度：选择题中提到，时间复杂度与问题规模有关，与其他因素如硬件性能、编译程序质量和编程语言无关。这强调了分析算法效率时应关注的主要因素。 2. 数据结构操作的时间复杂度：对单链表归并操作的讨论指出，最佳情况下比较次数可以是n-1，这涉及到排序算法的比较效率。 3. 队列操作的时间复杂度：队列的插入和删除操作在理想数据结构实现下应该是常数时间复杂度O(1)，这对应于链式队列的特性。 4. 数组存储空间计算：计算三维数组所需存储空间，需要考虑数组的维度和元素大小。 5. 树的高度：一棵具有n个节点的树，高度最小可能为1（链式存储），最大可能是n（线性链表）。 6. 树的存储形式：孩子链表表示法、双亲表示法、按层次的顺序存储表示法都是常见的树的存储方式，但孩子兄弟表示法不是，可能是对树结构理解的考察。 7. 强连通图的边数：一个具有n个顶点的强连通图，边数最多是n(n-1)，这是完全图的情况。 8. 图的性质：在有向图中，各顶点的入度之和等于出度之和，这是有向图的性质。 9. 查找算法比较次数：在有序表中，折半查找通常比顺序查找比较次数少，但不是绝对的，具体情况取决于查找元素的位置。 10. 排序算法的稳定性：稳定排序算法能保持相等元素的相对顺序，而不稳定排序算法则可能改变它们的顺序。 这些题目覆盖了计算机科学的核心领域，包括算法分析、数据结构、图论和离散数学，是准备计算机科学研究生入学考试的重要参考资料。考生可以通过解答这些问题来检验和提升自己的知识水平。