2016计算机考研试题及答案解析：数据结构、算法与图论

本资源提供了2016年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题及部分解答。以下是部分题目和知识点详解： 1. **单链表操作**： - 题目涉及到单链表的插入操作，给出了节点f在逻辑上的位置和内存存储情况。若f需要插入到a和e之间，链接地址的顺序取决于新节点的位置。根据链表结构，如果f在a和e之间，那么a、e和f的链接地址可能分别是：A. a->next（1010H），f->link（1014H），e->prev（1004H）。 2. **双向循环链表删除操作**： - 题目要求删除双向循环链表中指针p所指的结点。正确操作应先断开p节点前后节点的连接，然后释放p节点的内存。选项A正确：p->next->prev=p->prev; p->prev->next=p->prev; free(p)。 3. **火车车轨问题**： - 这是一个图论问题，描述了火车按照指定顺序驶入和驶出轨道的情况。对于9列列车按给定顺序驶入，要确保驶出顺序与驶入顺序一致，需要考虑最少的轨道数。由于列车可以任意进入一条轨道，n至少需要保证每次列车都能找到空闲的路径，所以n至少需要9（即每个列车都有自己的轨道）。因此，答案是C. 4，这表示至少需要4条轨道来满足条件，即使有些轨道可能空闲。 4. **三对角矩阵**： - 题目涉及矩阵压缩存储，要求确定100阶三对角矩阵中m30,30元素在压缩数组N中的下标。由于按行优先顺序存储，主对角线和副对角线的元素存储在数组的前半部分，中间元素在后面。对于100阶矩阵，主对角线和副对角线的长度之和为100，加上对角线外的元素，共199个元素。m30,30位于倒数第二行和倒数第二列，所以它的下标计算为：(30-1)*100 + (30-1) - 1 = 88。 5. **森林的树的数量**： - 森林由多个树组成，一个森林的边数总是比结点数少1（因为每棵树的结点数至少为1，而边数等于树的总数减去1）。题目中给出森林有15条边，25个结点，所以包含的树的个数为25 - 15 = 10。 6. **深度优先搜索序列**： - 深度优先搜索（DFS）是一种遍历图的算法，给出的选项中，需要找出不符合DFS遍历顺序的序列。在DFS中，一般会先访问最近的未访问节点，选项C V1,V2,V5,V4,V3不符合这个顺序，因为它没有遵循从最近的未访问节点开始的原则。 以上是一部分关键知识点，完整的解答还包括其他多项选择题的答案解析，以及深度优先搜索的具体应用分析等。对于准备考研计算机专业的考生来说，这些题目有助于复习数据结构、算法、链表、图论等核心概念。