苏州大学计算机学院数据结构及操作系统考研复试真题答案指南

苏州大学2018年硕士研究生入学考试初试试题（B卷）科目代码：872 科目名称：数据结构与操作系统满分：150分一、数据结构部分1、（15分）判断题，判断下列说法是否正确，如错误，指出错误之处。

（1）对于哈希（散列）查找，若采用线性探测法解决冲突，则装填因子α可以大于1。

（2）在A VL树上进行查找，平均查找长度为。

（3）一棵完全二叉树的高度为h，则该树至少有个结点。

（4）一个线性表，如果在对其进行操作的过程中表的长度经常发生变化，则采用顺序存储结构较合适。

（5）在使用后缀表达式计算表达式值时，应用队列存放操作数和操作符。

2、（15分）若要对一个序列进行排序，且需要对其进行次插入操作，以及次查找最大值的操作。

现有堆和二叉排序树两种数据结构，分别从平均情况和最坏情况下分析各数据结构的时间复杂度。

（1）若考虑平均情况，则应采用哪种数据结构，时间复杂度分别为多少，并进行分析。

（2）若考虑最坏情况，则应采用哪种数据结构，时间复杂度分别为多少，并进行分析。

3、（15分）一个线性表的元素均为正整数，使用带头指针的单链表实现。

编写算法：判断该线性表是否符合：所有奇数在前面，偶数在后面。

4、（15分）一棵用二叉链表实现的二叉树，其每个结点包括以下部分内容：结点值data，左孩子lchild和右孩子rchild，还有一个size存储该结点子树上的结点总数，现size还未赋值。

编写算法：为size赋值。

5、（15分）一棵采用孩子-兄弟表示法的树，编写算法：统计树中度为k的结点的个数。

二、操作系统部分1、（15分）简答题。

（1）什么是物理设备和逻辑设备，说明它们之间的关系。

（2）进程在CPU中执行时，操作系统有哪些操作模式，为什么要区分这些操作模式？（3）死锁解除的方法有哪些？请设计应用于手机操作系统的死锁解除方法。

2、（15分）采用动态优先级调度算法（优先数高的优先级低），根据运行时间和等待时间对优先数进行动态老化，具体老化算法如下：（a）处于等待状态的进程优先数p根据等待时间进行变化，每毫秒减一；（b）处于运行状态的进程优先数p根据运行时间进行变化，每毫秒加二；（c）优先数相同的进程按以下顺序调度：1）运行中的进程；2）先进入就绪队列的进程；（d）优先数p每隔1毫秒重新计算；（e）采用抢占式调度策略。

苏州大学计算机专业研究生复试上机题目苏州大学计算机科学与技术学院研究生复试C（上机）题目1、2009年上级复试题（1）用IE浏览器从FTP上下载org.dat，并保存在D盘的根目录下。

（2）此文件中按文本方式存放了一段其他文章，其中有若干长度小于15的十进制或八进制数字，数字之间用“,”分开，数字内部存在且仅存在空格。

（3）八进制数以起始位“0”作为标示与十进制数区分。

（4）顺序读取这些数字将他们转变为十进制数后按从大到小的顺序排序后，输出到D盘根目录下new.txt，每个数字一行。

eg：_235_,34__2,_043_1_,1_3 分别是：十进制235，十进制342.，八进制431，十进制13。

_代表空格。

2、2008年上级复试题（1）用IE从FTP上下载org.dat，并保存在D盘的根目录中。

（2）此文件中按文本方式存放了一段其他文章，其中有若干长度小于15的英文单词，单词之间用空格分开，无其他符号。

（3）顺序读取这段文章的不同的单词（大小写敏感），同时在读取的过程中排除所有的单词THE以及变形，即这些单词不能出现在读取的结果中。

（4）将读取的所有单词的首字母转大写后，输出D根目录下new.txt，每个单词一行。

------------------------那段文字可以点右键打开方式中用记事本打开，内容是：The constructor is used to initialize the object The destructor is used to delete the Object the calling seqence of constructor is opposite to the calling sequence of destructor个人感觉今年出题挺有水平的，苏大一个重要的方向就是信息处理，这个应该就是分词技术的基础把，我做的一般，不过听说好象有将近满分的，还当然也有很多兄弟没做出来。

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

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

1.判断，若错，改正。

15分(1) 在一个图中，所有顶点度数之和等于所有边的总数。

(2) 快排在被排序的数据已经基本有序的情况下最易发挥长处。

(3) 求子串的定位操作成为串的模式匹配。

2.Dijkstra用途，思想，验证其正确性，及图的数据结构。

3.将数的质因数分解并按递减顺序写成一个有序单链表。

如：2100->7.5.5.3.2.24.二叉链的二叉树，递归，验证是否严格二叉。

（无度为1的结点）5.顺序表，整数，长为n，尽可能高效求得第n/4个元素。

二、操作系统部分6、判断，若错，改正。

15分(1)任何操作系统中，系统资源分配最小单位为线程。

(2)死锁的进程必然至少一个互斥资源。

(3)虚拟存储器大小为内外存之和。

(4)文件访问效率有两个，物理结构和逻辑结构。

(5)spooling可以减少进程上下文切换次数。

7、从文件逻辑结构，物理结构和文件目录三方面入手，举实例说明如何提高存取速度（还是效率？就那个意思！）。

8、资源共享，创建和结束三方面说明进程和它创建的子进程，进程和他创建的线程之间的关系。

9、分页存储（二级页表），页表存于内存：(1) 一次访问内存200NS，求访问一个内存单元多少时间。

(2) 若三级页表，多少时间？(3) 引入联想寄存器，90%的页表项可在快表中命中，则一次访存时间？（假设一次快表10NS）(4) 若虚拟存储，页面命中率80%，缺页处理5万NS/次，则一个内存单元多少时间？(5) 采用虚拟存储，命中率80%，缺页时有10%需要置换(不用置换的缺页处理4万NS/次，否则8万NS/次)，同问。

苏州大学计算机学院数据结构与操作系统考研复试指南本文包含：具有苏大特色的《数据结构与操作系统》（872）备考指南、苏大特色的复试，分量绝对足。

本文不包含：不包含政治英语数学等内容。

一、简单介绍本人2013届考研，我是到大三下了才开始有考研的想法的，被两个关系很好的老师给“忽悠”的。

本科是一所内地普通的二本院校，一般来讲考苏大的本科背景都差不多。

我本科阶段的成绩并不好，挂科也有，60徘徊的科目也不少。

英语六级过了但是考了三次，软考过了软设也考了三次，然后就没有了，说这些主要是为了让学弟学妹们有所比较，说实在的讲到底考研最重要的还是坚持，很多的同学就是不能坚持，甚至考到最后了弃考的。

二、《数据结构与操作系统》（872）备考指南（一）时间安排我当时是最后两个月了才开始看的，并且只在下午看。

我的基础很一般，专业课的复习既要重视因为分数多好拿分，复试的同学除了跨专业的几乎没有低于120的，我考了136，所以说要重视。

同时又要轻视因为实在是很简单的，比起408难度降低了很多。

要记得东西稍微有点多，所以可以靠后点开始复习。

（二）全部书籍资料准备0．请忽略苏大所谓的参考教程，特别是那本板砖操作系统，如果是对付考研绝对没必要看。

1．我没有买任何专业课方面的书只在学校图书馆借了两本书《计算机专业考研辅导丛书：数据结构联考辅导教程(2010版)》、《计算机专业考研辅导丛书:计算机操作系统联考辅导教程(2011版)》，这两本书用来对付苏大的872非常好，并不要求最新的，要知道苏大的考纲都很多年没改了，试卷结构题型也比较稳定。

相信你们学校图书馆也肯定有借。

2．打印一份苏大872考纲，只要打印《数据结构与操作系统》的就可以了。

3．打印苏大99-2010年的872真题（某些年份可能缺失），论坛就有得下。

（三）复习过程1．首先要看一遍苏大的考纲和真题，了解苏大考什么、怎么考。

考纲更重要的作用是看不考什么，例如树的遍历，大纲上是没有层次遍历的，这个一直也没考过。

计算机考研复试题目及答案### 计算机考研复试题目及答案#### 题目一：数据结构问题：请解释什么是二叉搜索树，并说明其基本操作。

答案：二叉搜索树（Binary Search Tree，简称BST）是一种特殊的二叉树，它具有以下性质：1. 若任意节点的左子树不为空，则左子树上所有节点的值均小于它的节点值。

2. 若任意节点的右子树不为空，则右子树上所有节点的值均大于它的节点值。

3. 任意节点的左、右子树也分别为二叉搜索树。

4. 没有键值相等的节点。

二叉搜索树的基本操作包括：- 插入操作：将一个新值插入到树中，保持树的有序性。

- 查找操作：在树中查找一个给定值的节点。

- 删除操作：删除树中具有特定值的节点，并重新调整树以保持其性质。

#### 题目二：操作系统问题：请简述死锁的必要条件，并说明如何避免死锁。

答案：死锁是指多个进程在执行过程中因争夺资源而造成的一种互相等待的状态，若无外力作用，这些进程都无法继续执行。

死锁的必要条件包括：1. 互斥条件：至少有一个资源不能被共享，只能由一个进程使用。

2. 占有和等待条件：至少有一个进程至少占有一个资源，并且等待获取其他进程占有的资源。

3. 不可剥夺条件：已分配给一个进程的资源，在未使用完之前，不能被其他进程强行剥夺。

4. 循环等待条件：存在一个进程序列，使得每个进程都在等待下一个进程所占有的资源。

避免死锁的方法：- 资源分配策略：如银行家算法，确保分配资源时不会导致死锁。

- 资源有序分配：确保所有进程按照相同的顺序请求资源。

- 避免循环等待：通过资源的有序分配来打破循环等待的条件。

#### 题目三：计算机网络问题：描述TCP协议的主要特点。

答案：传输控制协议（TCP）是一种面向连接的、可靠的、基于字节流的传输层通信协议，其主要特点包括：1. 数据传输的可靠性：通过三次握手建立连接，确保数据传输的可靠性。

2. 数据传输的有序性：通过序列号和确认应答机制，保证数据按序到达。

苏州大学计算机技术专业硕士考研复试真题答案经验苏大虽然是211，但是统计结果的时候却是在学校中比较慢的，就拿楼主这一届来说吧：一、调剂系统3月18日开，苏大19日公布复试名单，于是如果你分数在复试线附近徘徊，想尝试调剂其他学校就会比较纠结，当然分高的可以忽略；二、复试完之后要过几天才能出结果，这会增加你调剂的风险，等拟录取名单出来的时候也许很多学校复试已经结束了，这时候再找学校调剂就会显得仓促，同样，复试厉害的人也可以忽略，然后再善意提醒一句，复试除了刷掉一部分人以外，最后几个会安排到常熟理工去读研，毕业后学位证书由苏大颁发。

进了复试那就是看你的综合能力了，我们这一届复试比去年增加了专业英语，分值比例是听力和口语（50分）、C语言+编程（75分+75分）、面试（200分）、专业英语（50分）。

首先是听力和口语，这方面最重要的是能说，70多个人在一个教室里，对着电脑说，没有老师，所以首先放下压力，你只要能说就行，别什么都不说，哪怕背一下自我介绍都比什么都不说强，这部分据说差距不大；第二个是C语言和编程，首先C语言是50*1.5=75分，50个选择题，难度是二级C，建议大家多看看指针和变量这块，楼主做的不太好，只对了32个，大家吸取我的教训吧，多看看，注意这里的题目禁止把代码复制到VC中运行！第二部分是编程，看过近几年的编程题就知道，除了13年，基本不考很复杂的算法（13年考了Floyed算法），但是每年都会考文件读取，各种读取文件的方式（普通读，二进制读），所以大家要仔细看一下文件读取，我们这一年考的是统计文本中单词的频数排序，并输出次数>5的单词，本来用C++的map 很方便存储，但是老师禁止用C++的STL，有个女生表示没学过C，直接不会做了，所以大家最好看一下C，C是肯定可以用的，因为文本大小未知，所以定义必须用动态数组，用静态数组明确指出会直接扣5分，还有C里面有个qsort头，排序很快，虽然不能用C++的sort，但qsort也是很强大的，能够掌握最好，编程允许带资料，事先准备一下吧。

苏州大学2003年硕士研究生入学考试试题考试科目：数据结构与操作系统数据结构部分：1、设以单向链表存储串，试编写判别给定串是否具有对称性的算法，并要求算法时间复杂度为O（length（s））。

可以设辅助空间，length（s）可以设为已知参数。

（10）2、设一有向环用邻接表表示，试设计递归算法，设计以V o出发最长路径的长度。

（15）3、简述表达式求值的基本思想，并对表达式6/（3-1）求值的操作过程，要求写出操作数栈和运算栈的变化情况。

（15）4、推导上三角阵在压缩存储时的地址计算公式。

（10）5、编写算法，求给定结点在给定的二叉排序树中解的层次。

（10）6、画出有序表（18、34、56、77、78、100、345、450、888）中进行折半查找的判定树，求等概率时查找成功时的平均查找长度。

（15）操作系统部分：1.1 操作系统及其功能1.2内存地址重定位1.3进程和线程2.4Spooling技术2、叙述操作系统提供系统调用的原因，并举例说明应用程序使用这些系统功能调用的两种方式。

（10）3、为了支持请求式分页内存管理，通常页表项内存有一标志位，用来记录相应的页是否被写过，请解释该标志位的操作者及其作用。

4、假设有一组任务序列{（x、y）}，x表示到达时间，y表示需要运行的时间，在FCFS和最短作业优先下的平均周转时间。

（10）5、给出一种文件目录结构的设计，并评价这种设计的优缺点。

6、超市可容纳500人同时购物，有6扇可供出入的门，既可进又可出，每扇门只允许一个人通过：6.1用PV操作及信号量描述进入和离开该超市的算法，使得该超市的购物容量得到最大发挥。

6.2如再加一个限制条件：同一个顾客进出必须通过同一扇门，那么相应算法如何写。

苏州大学二00七年攻读硕士学位研究生入学考试试题一．数据结构部分1名词解释（1）逆波兰式（2）自由树（3）外部排序（4）邻接表（5）占位程序2队列的实现方法有哪些？试比较各种实现方法的优缺点，并举例说明队列在计算机系统中有何应用。

3设L1和L2为单链表表示的有序表，试编写算法，求解L1∩L2，即求解既在L1中又在L2中的元素，结果放在L1中。

4试编写一个算法，将两棵二叉排序树合并为一棵二叉排序树。

5试设计一个求有向无环图中最长路径的算法，并估计时间复杂度。

二．操作系统部分6请判断下述说法的对错，并说明原因。

（1）分时操作系统必然建立在多道程序技术的基础之上。

（2）进程是指令的集合。

（3）存储保护的功能是限制内存存取。

（4）位示图可用于主存空间的共享。

7假设某个请求页式管理系统，具有16G的物理内存，48位的虚拟地址，每页大小为8K字节：（1）请以图示的形式给出虚拟地址向物理地址映射的过程，要求明确给出以下内容：逻辑地址和物理地址各部分的说明；λλ地址各部分的大小，以位（bit）为单位；每个页表的最多的表项数；λλ每个页表的最大尺寸，以字节（byte）为单位。

（2）对这样的系统，页表可能变得很大，特别是当它们被稀疏存放时。

请描述一种更有效的存储页表的技术，并解释为什么这个技术能够提高页表的存储效率。

8有三种文件分配方案：连续分配。

链接分配。

UNIX inode,请详细说明下列的文件访问需求，采用哪中分配方案最合适？（1）大文件顺序访问（2）大文件直接访问（3）小文件直接访问9什么是虚拟设备？为什么在操作系统中要引入虚拟设备？10设有五个哲学家，他们花费一生中的时光思考和吃饭。

这些哲学家共用一个圆桌，每个哲学家都有一把椅子。

桌子中央是一碗米饭。

桌子总共有6根筷子，在每个人两边分开各放一根，桌子中央还有一根。

当一个哲学家思考时，他与其他同事不交互，一个哲学家一次只能拿起一根筷子。

显然他不能从其他哲学家里抢走筷子，吃完后放下所有的筷子。

苏州大学计算机学院考研复试真题答案经验上午6点15分在东校区医院体检。

我特意起了个早，6点就到了那边，结果排队的人已经拐了两个弯了，没办法只得排到最后，不过前进的速度还蛮快，不过还是没有赶在7点40做完胸透：（因为8点钟还要在理工楼进行上机考试，胸透只能到下午去做了。

匆匆赶到理工楼已经快8点了，连忙花了5毛钱买个鞋套进入机房。

上机题目很简单，是从100到1000内找出不带9的素数，然后存放到D盘下的result.txt文件中，可以自由选择语言：TC 或VC++。

时间是一个半小时，很充裕。

苏大可真有钱，清一色DELL品牌机，40G/512MB/17'LCD/...告别了上机，接着就是笔试。

真的是喘气的机会都没有。

笔试的内容就是《计算机组成原理》，《软件工程导论》，《数据库系统教程》。

从理工楼，到鸿远楼，再到理工楼，我兜了半个苏大，终于落地生根，总共有111个战友一起参加考试，安排了5-6个老师来监考，反正是看不到别人的，都要靠自己。

今年是第一年增加笔试，题目出的比较偏，但是指定教材上都有！题目记得的有：（1）计算机组成原理（30分）：从计算机体系结构角度，分析单核CPU和双核（多核）CPU的区别；FLASH和ROM，RAM，EPROM在组成，性能，应用方面的区别；还有一个指令方面的题目。

（2）软件工程（30分）：JAKSON图，数据流图作用及符号表示，指令复用。

（3）数据库（40分）：第一题是5个选择，1分/个，题目不难，比如X锁等。

第二题简答，数据库中为什么要有并发机制，还有一小题忘了。

第三题是使用SELECT语句实现某些检索。

如果有其他同学记得的话可以补充一下。

笔试完毕，已经是中午了，饥肠辘辘的我连忙冲到第一食堂，菜的味道不咋样，价钱却不便宜。

由于下午1点还有英语口试，吃完饭休息了一会就又赶到了理工楼。

口试是在语音室里进行的，这跟其他学院的口试好象不太一样，不用面对着老师。

戴着耳机，跟着指示进行录音。

计算机考研面试题及答案计算机考研面试是考生进入研究生院深造的重要环节，而面试中的问题则是考生需要重点准备的内容。

在面试中，考官通常会涉及考生对计算机原理、算法、编程语言等方面的知识进行提问。

为了帮助考生更好地应对考研面试，本文将介绍一些常见的计算机考研面试题及其答案。

一、计算机原理1. 什么是冯·诺依曼计算机体系结构？冯·诺依曼计算机体系结构是一种描述计算机组织和工作原理的模型。

它依据“存储程序”原则，将数据和指令存储在同一内存中，以及使用存储器、运算器、控制器和输入输出设备等组成。

2. 分别介绍存储器的层次？存储器层次结构从高到低分为：寄存器、高速缓存、主存储器和辅助存储器。

层次结构的设计主要是为了解决速度和容量之间的矛盾。

3. 解释什么是指令级并行性？指令级并行性是指在计算机执行一条指令的过程中，通过重叠执行不同的指令或指令的不同部分，提高指令的执行效率。

这包括超标量、超长指令字和动态流水线等技术。

二、算法与数据结构1. 请解释什么是时间复杂度和空间复杂度？时间复杂度是衡量算法运行时间的度量，表示算法执行步数（时间）和输入规模之间的关系。

空间复杂度是衡量算法所需存储空间的度量，表示算法使用的额外空间和输入规模之间的关系。

2. 请给出常见排序算法的时间复杂度和空间复杂度。

- 冒泡排序的时间复杂度为O(n^2)，空间复杂度为O(1)。

- 快速排序的时间复杂度为O(nlogn)，空间复杂度为O(logn)。

- 归并排序的时间复杂度为O(nlogn)，空间复杂度为O(n)。

- 堆排序的时间复杂度为O(nlogn)，空间复杂度为O(1)。

3. 什么是二叉查找树？二叉查找树是一种特殊的二叉树结构，它满足以下条件：左子树上的节点值都小于根节点的值，右子树上的节点值都大于根节点的值。

通过这种结构，可以实现高效的查找、插入和删除操作。

三、编程语言1. 解释面向对象编程的概念。

面向对象编程是一种编程范式，它将对象作为程序的基本单元，通过封装、继承和多态等机制，构建一个具有状态和行为的系统。