常州大学 数据结构 2012年硕士研究生考研真题

实用题库苏州大学2012年硕士研究生入学考试初试试题科目代码：872 科目名称：数据结构与操作系统满分：150分注意：①认真阅读答题纸上的注意事项；②所有答案必须写在答题纸上；③本试题纸须同答题纸一并交回。

一、数据结构部分注意：算法可以用类C、类C++、类JAVA或类PASCAL等语言编写，并请写出类型说明。

1、( 15分 )简答题。

(1)假定用两个栈模拟一个队列，如何实现入队、出队和判队空操作；(2)写出使用Floyd算法求各顶点之间最短路径的思想，并写出其时间复杂度；2、( 15 分 )请回答下列有关于图的问题：(1)有n个顶点的有向强连通图最多有多少条边？最少有多少条边?(2)表示有1000个顶点、1000条边的有向图的邻接矩阵有多少个矩阵元素？是否为稀疏矩阵？(3)对于一个有向图，不用拓扑排序，如何判断图中是否存在环？3、( 15 分)有n个结点的完全二叉树存放在一维数组A[1..n]中，试据此建立一棵用二叉链表表示的二叉树，根由tree指向。

4、( 15 分)已知两个单链表A和B，其头指针分别为heada和headb,编写一个过程从单链表A中删除自第i个元素起的共len个元素，然后将单链表A插入到单链表B的第j个元素之前。

5、( 15 分)编写一个算法，在基于单链表表示的待排序关键字序列上进行简单选择排序。

第 1 页共2 页二、操作系统部分6、( 20分)简答题。

(1) 若系统中没有运行进程，是否一定没有就绪进程？为什么？(2) 动态分区和固定分区分配方式相比，是否解决了碎片问题？7、( 15 分)对文件的目录结构回答以下问题：(1) 若一个共享文件可以被用户随意删除或修改，会有什么问题？(2) 若允许用户随意地读、写和修改目录项，会有什么问题？(3) 如何解决上述问题？8、( 20 分)在一个磁盘上，有1000个柱面，编号从0-999，用下面的算法计算为满足磁盘队列中的所有请求，磁盘臂必须移过的道的数目。

研考数据结构真题答案解析数据结构是计算机科学中重要的一门课程，它探索了在计算机内部存储、组织和操作数据的方法和技术。

研究数据结构的目的是设计出高效、稳定和可扩展的算法和数据存储方案。

在研究生招考中，数据结构也是一个常见的考点。

今天，我们将对一道数据结构的真题进行解析，帮助大家更好地理解和应用数据结构。

考题如下：给定一个整数数组nums，我们需要将数组中所有的零元素移动到数组的末尾，同时保持非零元素的相对顺序不变。

例如，给定输入数组nums=[0, 1, 0, 3, 12]，函数应该在不返回任何东西的情况下，修改输入数组为[1, 3, 12, 0, 0]。

要求：只能对输入数组进行直接的操作，不能使用额外的数组。

解析：这是一道经典的数组操作题，目标是将数组中的零移到末尾，同时保持非零元素的相对顺序不变。

题目要求不能使用额外的数组，因此我们需要在原数组上进行操作。

最简单的方法是遍历整个数组，在遇到零元素时，将其后面的所有元素向前移动一位，然后将零元素放在最后。

这个方法的时间复杂度为O(n^2)，其中n是数组长度。

但是这个方法显然不是最优解。

我们可以通过使用两个指针来解决这个问题，一个指针用来遍历整个数组，另一个指针用来指向下一个非零元素应该放置的位置。

我们可以称这两个指针为“当前指针”和“插入指针”。

我们从头开始遍历数组，如果遇到非零元素，则将其插入到插入指针的位置，并将插入指针右移一位。

遍历完整个数组后，我们将插入指针后面的位置都置零。

为了更好地理解这个过程，我们来模拟一下。

将输入数组nums=[0, 1, 0, 3, 12]分解为当前指针和插入指针两个变量，初始时都指向第一个元素0：当前指针：0 -> 1 -> 0 -> 3 -> 12插入指针：0 -> 0 -> 0 -> 0 -> 0遍历过程中，遇到第一个非零元素1，将其插入到插入指针的位置，同时插入指针右移一位：当前指针：0 -> 1 -> 0 -> 3 -> 12插入指针：1 -> 0 -> 0 -> 0 -> 0继续遍历，遇到第二个非零元素3，将其插入到插入指针的位置，插入指针右移一位：当前指针：0 -> 1 -> 0 -> 3 -> 12插入指针：1 -> 3 -> 0 -> 0 -> 0遍历完所有的元素后，将插入指针后面的位置都置零：当前指针：0 -> 1 -> 0 -> 3 -> 12插入指针：1 -> 3 -> 12 -> 0 -> 0最终得到的数组为[1, 3, 12, 0, 0]，与题目要求相符。

数据结构考研真题与答案解析【数据结构考研真题与答案解析】数据结构是计算机科学与技术中的重要学科，也是考研中不可或缺的一部分。

在考研中，掌握数据结构的相关知识对于顺利通过考试至关重要。

本文将为大家介绍一些历年考研真题，并对答案进行解析，希望对大家备考有所帮助。

一、堆排序相关问题1. 2014年考研真题（题目描述）给定n个整数的序列S，其中$n \leq 10^6$且没有相同元素，并且给定另外的一个元素x，输出S中小于x的最大的数，如果不存在则输出“-1”。

（解析）这是一道关于堆排序的问题。

我们可以利用大顶堆来解决这个问题。

首先建立一个大顶堆，然后依次将序列S中的元素插入到堆中。

在插入的过程中，我们可以通过比较当前元素和x的大小，找到小于x的最大的数。

最后输出即可。

若不存在小于x的元素，则输出“-1”。

二、图的遍历问题2. 2016年考研真题（题目描述）对于一个无向图G，设计一个算法，判断图G是否连通，并给出详细的算法描述和复杂度分析。

（解析）对于这个问题，我们可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来解决。

我们可以从图中的任意一个节点开始进行深度或广度遍历，然后标记遍历过的节点。

最后判断所有的节点是否都被遍历到，若是，则图G是连通的，否则不连通。

若使用邻接表表示图，则DFS和BFS的时间复杂度均为O(|V|+|E|)，其中|V|和|E|分别代表图中的节点数和边数。

三、二叉搜索树相关问题3. 2018年考研真题（题目描述）给定一个二叉搜索树，请设计一个算法，找出其中第k大的节点。

（解析）对于这个问题，我们可以利用二叉搜索树的性质。

由于二叉搜索树的中序遍历结果是有序的，我们可以进行中序遍历，并将遍历结果保存到一个有序数组中。

然后根据数组中第k个位置的元素找到对应的节点即可。

算法的时间复杂度为O(n)，其中n为二叉搜索树中节点的个数。

四、哈夫曼编码问题4. 2017年考研真题（题目描述）给定一段文字，编写一个算法，根据字符出现的频率构建哈夫曼编码。

数据结构考研真题与解析数据结构考研真题与解析数据结构是计算机科学中非常重要的一门课程，也是考研中的必考科目之一。

掌握好数据结构的知识，对于提高编程能力和解决实际问题具有重要意义。

在备考过程中，了解历年的考研真题并进行解析是很有帮助的。

本文将通过对数据结构考研真题的解析，帮助读者更好地理解数据结构的知识点和解题技巧。

第一道题目是关于树的遍历的。

题目要求给定一棵二叉树的前序遍历和中序遍历序列，求出该二叉树的后序遍历序列。

这是一道经典的树的遍历问题，解题的关键在于找到根节点的位置，并将问题划分为子问题进行递归求解。

通过观察前序遍历和中序遍历序列，我们可以发现前序遍历序列的第一个元素一定是根节点，而在中序遍历序列中，根节点的左边是其左子树的中序遍历序列，右边是其右子树的中序遍历序列。

因此，我们可以通过递归的方式求解左子树和右子树的后序遍历序列，然后将根节点放在最后，即可得到整棵树的后序遍历序列。

第二道题目是关于图的最短路径的。

题目给定一个有向带权图，要求从图中的一个顶点出发，找到到达其他所有顶点的最短路径。

这是一个经典的图算法问题，可以使用Dijkstra算法来解决。

Dijkstra算法的思想是从起点开始，依次找到离起点最近的顶点，并更新其他顶点的最短路径。

具体实现时，可以使用一个数组来记录每个顶点的最短路径长度，以及一个优先队列来选择最短路径最小的顶点进行扩展。

通过不断更新最短路径长度，直到所有顶点都被访问到，即可得到最短路径。

第三道题目是关于排序算法的。

题目给定一个整数数组，要求使用快速排序算法对其进行排序。

快速排序是一种高效的排序算法，其基本思想是通过一趟排序将待排序序列分割成独立的两部分，其中一部分的元素都比另一部分的元素小，然后再对这两部分分别进行排序。

具体实现时，可以选择一个基准元素，将小于基准元素的放在左边，大于基准元素的放在右边，然后递归地对左右两部分进行排序。

通过不断地划分和排序，最终整个序列就会有序。

数据结构考研真题及其答案一、协议关键信息1、真题及答案的来源：＿___________________________2、真题及答案的涵盖范围：＿___________________________3、真题及答案的使用限制：＿___________________________4、协议的有效期：＿___________________________5、保密条款的相关约定：＿___________________________6、违约责任的界定和处理方式：＿___________________________7、争议解决的途径和方式：＿___________________________二、协议具体内容11 定义和解释111 本协议中，“真题”指用于数据结构考研的相关试题。

112 “答案”指对应真题的正确解答和分析。

12 真题及答案的提供121 提供方应确保所提供的真题及答案真实、准确、完整，且符合考研的相关要求和标准。

122 真题及答案应涵盖指定的数据结构知识点和考点。

13 真题及答案的质量131 提供的真题应具有代表性、典型性和一定的难度梯度。

132 答案应详细、清晰，逻辑严谨，便于理解和学习。

14 真题及答案的使用限制141 接收方仅可将真题及答案用于个人考研复习使用，不得用于商业目的、传播给第三方或进行任何非法活动。

142 不得对真题及答案进行修改、篡改、复制、分发或公开发表。

15 协议的有效期151 本协议自双方签署之日起生效，有效期至具体日期。

152 在有效期内，双方应遵守协议的各项条款。

16 保密条款161 双方应对真题及答案的内容严格保密，不得向任何无关人员透露。

162 若因一方泄露导致不良后果，泄露方应承担相应的法律责任。

17 违约责任171 若提供方提供的真题及答案存在质量问题或不符合约定，应负责及时更正或补充。

172 若接收方违反使用限制或保密条款，应承担相应的赔偿责任，并停止违约行为。

2012数据结构_习题及程序设计整理疯狂记忆力数据结构是计算机科学中非常重要的一个领域，它主要研究数据的组织、存储和管理方式。

在学习数据结构的过程中，习题和程序设计是提高理解和应用的重要手段。

下面将整理一些2012年的数据结构习题及程序设计内容，帮助读者巩固和深入理解这一领域的知识。

一、线性结构1. 线性表是数据结构中最基本的一种结构，它的特点是元素之间存在一对一的关系，先后次序唯一确定。

请写一个C语言程序，实现线性表的基本操作，包括插入、删除、查找等。

2. 栈是一种特殊的线性表，具有“先进后出”的特点。

设计一个栈，支持判断栈是否为空、入栈和出栈操作，并实现一个简单应用情境，例如操作系统任务的进出栈操作。

3. 队列也是一种特殊的线性表，具有“先进先出”的特点。

设计一个队列，支持判断队列是否为空、入队和出队操作，并实现一个简单应用情境，例如模拟排队等待的场景。

二、非线性结构1. 树是一种重要的非线性结构，它以分层的方式存储数据。

定义一个树的基本数据结构，包括节点的定义、插入节点、删除节点等操作。

2. 图是由节点和边组成的数据结构，用于表示多对多的关系。

请设计一个简单的图结构，实现图的初始化、添加节点、添加边以及遍历等基本操作。

三、查找与排序1. 二分查找是一种常见的查找算法，适用于有序数组。

请编写一个二分查找算法的Java程序，并验证其正确性。

2. 快速排序是一种常见的排序算法，通过分治法实现。

请实现一个快速排序算法的Python程序，并对随机生成的一组数据进行排序。

四、高级数据结构1. 堆是一种完全二叉树，主要用于实现高效的优先队列。

设计一个堆的数据结构，并实现堆排序算法。

2. 哈希表是一种以键值对存储数据的数据结构，通过哈希函数实现高效的数据查找。

请实现一个简单的哈希表，包括哈希函数的设计、数据的插入和查找等操作。

以上是一些2012年的数据结构习题及程序设计内容，涵盖线性结构、非线性结构、查找与排序以及高级数据结构等方面的内容。

考研数据结构试题（含答案）我以⼀名⼤学⽣的⼈格尊严保证，在本场考试中，⾃觉遵守考试纪律，服从考试管理，决不作弊或帮助别⼈作弊！签名：学院专业学号级班··················密···················封·····················线··················命题⼈签字：系主任签字：审核院长签字：共印份数：第1页共6页聊城⼤学计算机学院2012—2013学年第1学期期末考试2011级《数据结构》试题（闭卷B卷）⼀、单项选择题（共15题，每题2分，共30分）1.研究数据结构就是研究（D ）。

A．数据的逻辑结构B．数据的存储结构C．数据的逻辑结构和存储结构D．数据的逻辑结构、存储结构及其基本操作2.在数据结构中，从逻辑上可以把数据结构分为（C ）。

A．动态结构和静态结构B．紧凑结构和⾮紧凑结构C．线性结构和⾮线性结构D．内部结构和外部结构3.算法分析的两个主要⽅⾯是（A ）。

A．空间复杂度和时间复杂度B．正确性和简单性C．可读性和⽂档性D．数据复杂性和程序复杂性4.下⾯程序段的时间复杂度是（ C ）。