2013年沈阳工业大学考研真题808数据结构

《数据结构》考研真题及解答目录2009 年试题 (1)填空题 (1)解答题 (2)2010 年试题 (2)填空题 (2)解答题 (4)2011 年试题 (4)填空题 (4)解答题 (5)2012 年试题 (6)填空题 (6)解答题 (7)2013 年试题 (8)填空题 (8)解答题 (9)2014 年试题 (10)填空题 (10)解答题 (11)2015 年试题 (12)填空题 (12)解答题 (14)2009 年试题填空题1.为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。

该缓冲区的逻辑结构应该是A.栈B.队列C.树D.图2.设栈 S 和队列 Q 的初始状态均为空，元素 abcdefg 依次进入栈 S。

若每个元素出栈后立即进入队列 Q，且7 个元素出队的顺序是 bdcfeag，则栈 S 的容量至少是A．1 B.2 C.3 D.43.给定二叉树图所示。

设 N 代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。

若遍历后的结点序列为 3，1，7，5，6，2，4，则其遍历方式是A．LRN B.NRL C.RLN D.RNL4.下列二叉排序树中，满足平衡二叉树定义的是5.已知一棵完全二叉树的第 6 层（设根为第 1 层）有8 个叶结点，则完全二叉树的结点个数最多是A．39 B.52 C.111 D.1196.将森林转换为对应的二叉树，若在二叉树中，结点u 是结点v 的父结点的父结点，则在原来的森林中，u 和v 可能具有的关系是I．父子关系II.兄弟关系III.u 的父结点与v 的父结点是兄弟关系A.只有IIB.I 和IIC.I 和IIID.I、II 和III7.下列关于无向连通图特性的叙述中，正确的是I．所有顶点的度之和为偶数II.边数大于顶点个数减1 III.至少有一个顶点的度为1A.只有IB.只有IIC.I 和IID.I 和III8.下列叙述中，不符合 m 阶B 树定义要求的是A．根节点最多有m 棵子树 B.所有叶结点都在同一层上C．各结点内关键字均升序或降序排列 D.叶结点之间通过指针链接9.已知关键序列 5，8，12，19，28，20，15，22 是小根堆（最小堆），插入关键字 3，调整后得到的小根堆是A．3，5，12，8，28，20，15，22，19B.3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D.3，12，5，8，28，20，15，22，1910.若数据元素序列 11，12，13，7，8，9，23，4，5 是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是A．起泡排序 B.插入排序 C.选择排序 D.二路归并排序解答题41.（10 分）带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。

数据结构真题2013年10月(总分：100.01，做题时间：90分钟)一、{{B}}单项选择题{{/B}}(总题数：15，分数：30.00)1.算法的时间复杂度表征的是______∙ A.算法的可读性∙ B.算法的难易程度∙ C.执行算法所耗费的时间∙ D.执行算法所耗费的存储空间（分数：2.00）A.B.C. √D.解析：[考点] 算法的时间复杂度定义 [解析] (1)执行算法所耗费的时间，即时间复杂性；(2)执行算法所耗费的存储空间，主要是辅助空间，即空间复杂性；(3)算法应易于理解、易于编程、易于调试等，即可读性和可操作性。

因此表征算法时间复杂度的是执行算法耗费的时间，C正确。

2.对需要频繁插入和删除结点的线性表，适合的存储方式是______∙ A.顺序存储∙ B.链式存储∙ C.索引存储∙ D.散列存储（分数：2.00）A.B. √C.D.解析：[考点] 链式存储方式 [解析] 应该采用链式存储结构。

因为采用链式结构存储线性表，插入和删除操作需要从头结点起查找被插入或删除结点的前驱结点，并修改这些结点的指针域，查找过程平均移动指针域为表长的一半；而采用顺序结构存储线性表，插入和删除操作需要平均移动表中的一半元素。

但移动指针域操作比移动元素操作花费的时间少得多。

3.在头指针为head的循环链表中，判断指针变量P指向尾结点的条件是______∙ A.p-＞next-＞next==head∙ B.p-＞next==head∙ C.p-＞next-＞next==NULL∙ D.p-＞next==NULL（分数：2.00）A.B. √C.D.解析：[考点] 循环链表的特点 [解析] 循环链表的特点是单链表中最后一个结点(终端结点)的指针域不为空，而是指向链表的头结点，使整个链表构成一个环；循环结束的判断条件不再是P或P→next是否为空，而是他们是否等于头指针。

因此答案选B。

4.迪杰斯特拉(Dijkstra)算法的功能是______∙ A.求图中某顶点到其他顶点的最短路径∙ B.求图中所有顶点之间的最短路径∙ C.求图的最小生成树∙ D.求图的拓扑排序序列（分数：2.00）A. √B.C.D.解析：[考点] 迪杰斯特拉(Dijkstra)算法的功能[解析] Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法，用于计算从某个源点到其余各定点的最短路径。

808数据结构考研大纲（原创实用版）目录1.引言2.考试内容3.考试形式和难度4.考试样题5.结语正文一、引言808数据结构考研大纲是考研计算机学科基础综合考试科目之一，旨在考查考生对数据结构的基本概念、原理和方法的理解和应用能力。

该大纲主要内容包括数据结构的基本概念、线性表、栈、队列、数组、树、图、查找和排序等。

二、考试内容1.数据结构的基本概念：包括数据类型、抽象数据类型、数据结构、算法等基本概念。

2.线性表：包括顺序表、链表、数组等线性结构。

3.栈、队列：包括栈和队列的基本原理和应用。

4.数组：包括数组的存储方式和基本操作。

5.树：包括二叉树、二叉搜索树、平衡树等树结构。

6.图：包括邻接表、深度优先遍历、广度优先遍历等图结构。

7.查找：包括二分查找、哈希查找等查找算法。

8.排序：包括冒泡排序、插入排序、快速排序等排序算法。

三、考试形式和难度1.考试形式：考试时间为150分钟，试卷满分为150分。

2.考试难度：考试难度适中，要求考生能够理解和应用数据结构的基本原理和方法，能够解决实际问题。

四、考试样题1.单项选择题：20道，每题2分，共40分。

2.填空题：10道，每题3分，共30分。

3.综合应用题：2道，每题15分，共30分。

4.算法分析题：1道，每题10分，共10分。

5.算法设计题：1道，每题15分，共15分。

五、结语808数据结构考研大纲是考研计算机学科基础综合考试的重要科目之一，对于考生来说非常重要。

考生应该认真学习和理解大纲中的内容，掌握数据结构的基本原理和方法，注重实践和应用能力的培养和提高。

808数据结构考研大纲【实用版】目录一、考研大纲概述二、数据结构的重要性三、数据结构的基础知识四、数据结构的实际应用五、备考策略与建议正文一、考研大纲概述本文主要针对 808 数据结构与程序设计考研大纲进行解析。

该考研大纲主要涉及计算机科学与技术类硕士生的选拔，考察的内容主要包括数据结构和 C/C++编程。

通过这份大纲，我们可以了解到考研对于数据结构的要求和重视程度。

二、数据结构的重要性数据结构是计算机科学与技术领域的基础知识，它在软件开发、系统设计等方面具有重要的应用价值。

掌握数据结构的原理和方法，可以更好地解决实际问题，提高程序的效率和可读性。

因此，在考研中，数据结构是一个重要的考察内容。

三、数据结构的基础知识数据结构的基础知识主要包括线性表、栈与队列、树与二叉树、图等。

其中，线性表是数据结构的基本概念，需要掌握其基本原理和常见操作。

栈与队列是线性表的扩展，需要了解其特点和应用场景。

树与二叉树是数据结构的重要组成部分，要深入理解其结构和遍历方法。

图是数据结构的另一个重要领域，要掌握图的基本概念和图算法。

四、数据结构的实际应用数据结构在实际应用中具有广泛的应用，例如在操作系统、编译原理、数据库等领域。

在考研中，可能会涉及到一些与实际应用相关的问题，需要我们结合实际场景进行分析和解决。

因此，在备考过程中，要注重理论联系实际，提高解决问题的能力。

五、备考策略与建议针对 808 数据结构与程序设计考研大纲，我们可以从以下几个方面进行备考：1.认真阅读教材，掌握基本概念和原理。

2.多做练习题，加深对知识点的理解。

3.结合实际场景进行分析，提高解决问题的能力。

4.关注历年真题，了解考试趋势和题型。

5.合理安排时间，保持良好的心态。

总之，通过对 808 数据结构与程序设计考研大纲的分析，我们可以了解到考研对数据结构的要求和重视程度。