2013年计算机专业基础综合考试习题详解II

章节摘录

版权页：   插图：   9.B。 图的邻接矩阵表示是唯一的，每条边的信息存放在矩阵中确定的位置。邻接表表示则不唯一，取决于各条边读入的先后次序，以及在边链表中采用前插法还是后插法来插入这些边。 10.A。 设图具有n个顶点和e条边，则用邻接表存储图需要建立至少有n个顶点信息的顶点向量，此外为每一条边创建边链结点，有向图有e个边链结点，无向图有2e个边链结点（对称情形），所以所需的存储空间为O（n+e），也就是说所用空间与图的顶点数和边数都有关。 11.①B，②D。 图的深度优先遍历类似于树的先根次序遍历，而树的先根次序遍历又与其二叉树表示的前序遍历结果相同，所以采用邻接表存储的图的深度优先搜索算法类似于二叉树的前序遍历。广度优先搜索算法则类似于二叉树的层次序遍历。 12.B。 对无向图作一次深度优先搜索，可遍历连通图的所有顶点。当然，通过深度优先搜索也可以遍历一棵树，不过遍历树通常被称为中序、前序、后序遍历；强连通图是有向图，与题意矛盾；有回路的无向图不一定是连通图，因为回路不一定包含图的所有结点。 13.A。 从图中一个顶点出发进行广度优先遍历，能够遍历到所有与该顶点连通的顶点，就是说可找到一个包含了该顶点的连通分量。然后再选择剩余未被访问过的顶点继续广度优先遍历，就可以遍历到其他的连通分量。 14.A。 一个连通图的生成树是具有为保证连通性的边最少的树，是图的极小连通子图。 15.A。 求解最小生成树的原则是要选择权值最小的n-1条边连通n个顶点，并要求选出的边不能构成回路。权值最小的边是第一个选择的边，它应在最小生成树的边集合中。 16.B。 如果一个无向连通图具有多条权值相同的边，在构造最小生成树的过程中选择具有最小权值的边时，会出现多种可能的选择，得到的最小生成树不止一棵：但如果无向连通图各边上具有的权值互不相同时，构造的最小生成树是唯一的。因此，可能有一棵或多棵最小生成树。

前言

欣看《2013版数据结构高分笔记》、《2013版计算机组成原理高分笔记》、《2013版操作系统高分笔记》、《2013版计算机网络高分笔记》、《2013年计算机专业基础综合考试习题详解Ⅰ（计算机组成原理+计算机网络）》、《2013年计算机专业基础综合考试习题详解Ⅱ（数据结构+操作系统）》等6本辅导教材问世了，这对于有志考研的同学是一大幸事。“它山之石，可以攻玉”，参考一下亲身经历过考研，并取得优秀成绩的师兄们的经验，必定有益于对考研知识点的复习和掌握。能够考上研究生，这是无数考生的追求，能够以优异的成绩考上名牌大学的全国数一数二的计算机或软件工程学科的研究生，更是许多考生的梦想。如何学习或复习相关课程，如何打好扎实的理论基础、练好过硬的实践本领，如何抓住要害，掌握主要的知识点并获得考试的经验，先行者已经给考生们带路了。“高分笔记”的作者们在认真总结了考研体会，整理了考研的备战经验，参考了多种考研专业教材后，精心编写了系列辅导书。“天勤计算机考研高分笔记系列”辅导教材的特点是：贴近考生。作者们都亲身经历了考研，他们的视角与以往辅导教材不同，是从复习考研的学生的立场理解教材的知识点——哪些地方理解有困难，哪些地方需要整理思路，叙述处处替考生着想，有很好的引导作用。重点突出。作者们在复习过程中做了大量习题，并经历了考研的严峻场面，对重要的知识点，考试出现频率高的题型都了如指掌。因此，在复习内容的取舍上进行了精细的考虑，使得读者可以抓住重点，有效地复习。分析透彻。作者们在复习过程中对主要辅导教材的许多习题都深入分析并实践过，对重要知识点做过相关实验并有总结。因此，解题思路明确，叙述条理清晰，对问题求解的步骤和结果的分析透彻，不但可以扩展考生思路，还有助于考生举一反三。计算机专业综合基础考试已经考过4年，今后考试的走向如何，这可能是考生最关心的问题了。我想，这要从考试命题的规则入手来讨论。以清华大学为例，学校把研究生入学考试定性为选拔性考试。研究生入学考试试题主要测试考生对本学科的专业基础知识、基本理论和基本技能掌握的程度。因此，出题范围不应超出本科教学大纲和硕士生培养目标，并尽可能覆盖一级学科的知识面，一般会使本学科、本专业本科毕业的优秀考生能取得及格以上的成绩。实际上，全国计算机专业研究生入学联考的命题原则也是如此，各学科的重点知识点都是命题的重点。一般知识要考，比较难的知识（较深难度的知识）也要考。从2009年以来几年的考试分析可知，考试的出题范围基本符合考试大纲，都覆盖到各大知识点，但题量有所侧重。因此，考试一开始不要抱侥幸的心理去押题，应踏踏实实读好书，认认真真做好复习题，仔仔细细归纳问题解决的思路，夯实基础，增长本事；然后再考虑重点复习，有几条规律可供参考：出过题的知识点还会有题，出题频率高的知识点，今后出题的可能性也大。选择题大部分题目涉及基本概念，主要考查各个知识点的定义、特点的理解，个别选择题会涉及相应延伸的概念。综合应用题分为两部分：简作题和设计题。简作题的重点在设计和计算；设计题的重点在算法、实验或综合应用。常言道：“学习不怕根基浅，只要迈步总不迟”，只要大家努力了，收获总会有的。

内容概要

　　天勤论坛，取名自古训“天道酬勤”，意为考研路上，困苦实多，然而天自有道，勤恳付出者，必有应得之酬劳。天勤论坛由浙大、北航等多所计算机专业名校的研究生创办，团队所有成员皆亲身经历过计算机专业考研的磨炼，于是本着为考生服务的热情，共同搭建了此交流平台。
　　由天勤论坛组编的高分笔记系列计算机考研辅导书，融入了论坛答疑的精华内容，论坛组织了高分考生进行勘误，不断完善此套书籍。考生在书中遇到疑问，也可在线与作者进行交流。
　　为提高考生算法设计能力，团队搭建了专门针对计算机考研学子的在线算法测试平台——ACM俱乐部，希望能借此帮助考生提高复习效率。

书籍目录

序
前言
上篇 数据结构
第1章 算法复杂度相关问题专练
算法复杂度综合题目专练
算法复杂度综合题目专练答案
第2章 线性表
本章复习建议
建议重点复习
历年考题分布
考题大预测（仅供参考）
基础题部分
拔高题部分
基础题部分参考答案
拔高题部分参考答案
第3章 栈、队列和多维数组
本章复习建议
建议重点复习
历年考题分布
考题大预测（仅供参考）
基础题部分
拔高题部分
基础题部分参考答案
拔高题部分参考答案
第4章 树与二叉树
本章复习建议
建议重点复习
历年考题分布
考题大预测（仅供参考）
基础题部分
拔高题部分
基础题部分参考答案
拔高题部分参考答案
第5章 图
本章复习建议
建议重点复习
历年考题分布
考题大预测（仅供参考）
基础题部分
拔高题部分
基础题部分参考答案
拔高题部分参考答案
第6章 排 序
本章复习建议
建议重点复习
历年考题分布
考题大预测（仅供参考）
基础题部分
拔高题部分
基础题部分参考答案
拔高题部分参考答案
第7章 查 找
本章复习建议
建议重点复习
历年考题分布
考题大预测（仅供参考）
基础题部分
拔高题部分
基础题部分参考答案
拔高题部分参考答案
下篇 操作系统
第1章 绪 论
本章复习建议
建议重点复习
历年考题分布
考题大预测（仅供参考）
基础题部分
拔高题部分
基础题部分参考答案
拔高题部分参考答案
第2章 进程管理
本章复习建议
建议重点复习
历年考题分布
考题大预测（仅供参考）
基础题部分
拔高题部分
基础题部分参考答案
拔高题部分参考答案
第3章 内存管理
本章复习建议
建议重点复习
历年考题分布
考题大预测（仅供参考）
基础题部分
拔高题部分
基础题部分参考答案
拔高题部分参考答案
第4章 文件管理
本章复习建议
建议重点复习
历年考题分布
考题大预测（仅供参考）
基础题部分
拔高题部分
基础题部分参考答案
拔高题部分参考答案
第5章 输入输出（I/O）管理
本章复习建议
建议重点复习
历年考题分布
考题大预测（仅供参考）
基础题部分
拔高题部分
基础题部分参考答案
拔高题部分参考答案
参考文献

编辑推荐

《2013年计算机专业基础综合考试习题详解2(数据结构+操作系统)》给考生带来更高效、更明确、更轻松、更愉快的复习过程。

作者简介

《2013年计算机专业基础综合考试习题详解2(数据结构+操作系统)》分为Ⅰ、Ⅱ两册，第Ⅰ册包括计算机组成原理和计算机网络两个科目；第Ⅱ册包含数据结构和操作系统两个科目。《2013年计算机专业基础综合考试习题详解2(数据结构+操作系统)》所选习题，紧密围绕教育部考试中心发布的考试大纲，并以梯度的形式呈现给读者（从基础题进阶到拔高题），使考生的学习更具有针对性。

另外，作者对统考近四年来的真题所考查的知识点进行了深入剖析，在每章的最前面都给出了本章节的考点大预测，使得考生可以有重点地进行复习，提高复习效率。

考生对此书有任何疑问都可以通过天勤论坛与作者进行在线交流，最大化地提高复习效率。

图书封面

---

 2013年计算机专业基础综合考试习题详解II下载

---