苏州大学数据结构与操作系统

南 京 航 空 航 天 大 学

二 ○ ○ 四 年 硕 士 研 究 生 入 学 考 试 试 题

考试科目:数据结构与操作系统

说 明:答案一律写在答题纸上,数据结构部分编程语言不限

第一部分:数据结构部分（75分）

1、（5分）判别以下序列是否为堆（小顶堆），如不是，将其调整为堆，画出调整过程。（29，51，63，39，24，55，50，13，49，39） 2、（10分）设一单链表，结点由整型数据和指针项组成，计算链表中数据只出现1次的结点个数，要求空间复杂度为O(1)。编写程序，并写出算法思想。 3、（10分）设一信号灯，产生的颜色有（RED，GREEN，BLUE，YELLOW，BLACK，BROWN，WHITE）出现的概率分别为（0.04，0.12，0.3，0.14，0.25，0.1，0.05），试用二进制对其编码，使产生的数据量最少。 4、（10分）设有存放整型数据的一维数组A[0…n-1],编写程序，将数组中的所有奇数调整到所有的偶数前面，要求时间复杂度为O（1），时间复杂度为O（n），并写出算法思想。 5、（10分）设有向无环图G：顶点集合为{v1,v2,v3,v4,v5,v6,v7},弧的集合为{,,,, ,

数据结构与操作系统Z试卷 《数据结构》部分 （90分）

一、简答题（20分，每题5分）

1、请给出四种数据结构基本类型。

答：根据数据元素之间关系的不同特征，通常有下列4类的基本结构： （1）集合。。。 （2）线性结构。。。 （3）树形结构。。。

（4）图状结构或网状结构。。。

2、简述栈和队列的区别。（P44;P58）

区别和联系：

从数据结构上看，栈和队列也是线性表，不过是两种特殊的线性表。 栈只允许在表的一端进行插入或删除操作，

队列只允许在表的一端进行插入操作、而在另一端进行删除操作。 因而，栈和队列也可以被称作为操作受限的线性表。 3、什么是关键路径？(P183)

在AOE网中，有些活动可以并行地运行，最短完成时间应是从源点到汇点的最长路径长度（指路径上所有权值之和），称这样的路径为关键路径。

4、插入类排序有哪几种？其中，哪些是不稳定的排序算法？(P265)

二、应用题（40分）

1、如果进栈的序列是12345，请给出所有3、4先出栈的序列（3在4之前出栈）。（5分）(P)

【解答】34215 ，34251， 34521 (可以参考下面这个题：

【￥】铁路进行列车调度时，常把站台设计成栈式结构，若进站

《数据结构》部分

一、简答题（10分，每题5分）

1、数据元素之间的关系在计算机中的存储有几种表示方法？各有什么特点？（P6） 解：数据元素之间的关系在计算机中有四种不同的表示方法：

(1)顺序存储方法。数据元素顺序存放，每个结点只含有一个元素。存储位置反映数据元素间的逻辑关系。存储密度大，但有些操作(如插入、删除)效率较差。

(2)链式存储方法。每个结点除包含数据元素信息外还包含一组指针。指针反映数据元素间的逻辑关系。这种操作不要求存储空间连续，便于进行插入和删除等操作，但存储空间利用率较低。另外，由于逻辑上相邻的数据元素在存储空间上不一定相邻，所以不能对其进行随机存取。

(3)索引存储方法。除数据元素存储在一地址连续的内存空间外，尚需建立一个索引表。索引表中的索引指示结点的存储位置，兼有动态和静态特性。

(4)哈希(或散列)存储方法。通过哈希函数和解决冲突的方法，将关键字散列在连续的有限的地址空间内，并将哈希函数的值作为该数据元素的存储地址。其特点是存取速度快，只能按关键字随机存取，不能顺序存储，也不能折半存取。

2、对于堆排序法，快速排序法和归并排序法，若仅从节省存储空间考虑，则应该首先选取其中哪种方法？其次选取哪种方法？若

苏州大学 操作系统原理 期中考试试卷 共6页

学院 专业 成绩 年级 学号 姓名 日期 考试形式： 闭卷 时间： 120分钟 一、 填空题（10分，每空1分）

1、在有m个进程的系统中出现死锁时，死锁进程的个数k应该满足的条件是 。

2、操作系统的结构有多种，其中采用微内核结构的有 等；采用模块化结构有 等。

3、操作系统的最基本的设计目标是 ，在此基础上，还需要考虑 （面向系统）和 （面向用户）。

4、互斥资源是 ；共享资源则是 。 5、周转时间等于运行时间加 。一般情况下响应时间 等待时间。

二、选择题（20分

专注考研专业课13年，提供海量考研优质文档！

第 1 页，共 17 页

目录

2018年南京航空航天大学922数据结构与操作系统[专硕]之计算机操作系统考研仿真模拟五套

题（一） .................................................................................................................................. 2 2018年南京航空航天大学922数据结构与操作系统[专硕]之计算机操作系统考研仿真模拟五套

题（二） .................................................................................................................................. 5 2018年南京航空航天大学922数据结构与操作系统[专硕]之计算机操作系统考研仿真模拟五套

题（三） .............................................................................

目录

2017年云南大学信息学院831数据结构与操作系统考研强化模拟题（一） (2)

2017年云南大学信息学院831数据结构与操作系统考研强化模拟题（二） (8)

2017年云南大学信息学院831数据结构与操作系统考研强化模拟题（三） (13)

2017年云南大学信息学院831数据结构与操作系统考研强化模拟题（四） (18)

2017年云南大学信息学院831数据结构与操作系统考研强化模拟题（五） (24)

第1 页，共29 页

第 2 页，共 29 页 2017年云南大学信息学院831数据结构与操作系统考研强化模拟题（一） 说明：①本资料为VIP 学员内部使用，严格按照2017考研专业课大纲及历年常考题型出题。 ————————————————————————————————————————

一、填空题

1． —个字符串中_____称为该串的子串。

【答案】任意个连续的字符组成的子序列

2． 执行顺序查找时，存储方式可以是_____，折半查找时，要求线性表_____，分块查找时要求线性表_____，而哈希表的查找，要求线性表的存储方式是_____。

【答案】顺序存储或链式存储；顺序存储且有序；块内顺序存储，块间有序；散列存储

3． 文件可按其记录的类型不同而分成两类

苏州大学 操作系统原理 期中考试试卷 共6页

学院 专业 成绩 年级 学号 姓名 日期 考试形式： 闭卷 时间： 120分钟 一、 填空题（10分，每空1分）

1、在有m个进程的系统中出现死锁时，死锁进程的个数k应该满足的条件是 1

2、操作系统的结构有多种，其中采用微内核结构的有 Windows XP Mach QNX 等；采用模块化结构有 Solaris Linux Mac 等。

3、操作系统的最基本的设计目标是 使应用程序能够顺利运行 ，在此基础上，还需要考虑 高效 （面向系统）和 易用 （面向用户）。 4、互斥资源是 多个进程不能同时使用的资源 ；共享资源则是多个进程可以同时使用的资源 。

5、周转时间等于运行时间加 等待时间 。一般情况下响应时间不大于等待时间。

二、选择题（20分，每题2分）

1、以下不属于操作系统部件的是 B

专注考研专业课13年，提供海量考研优质文档！

第 1 页，共 74 页

目录

2018年山东财经大学809计算机专业基础综合（数据结构、操作系统）之数据结构考研基础五

套测试题（一） ....................................................................................................................... 2 2018年山东财经大学809计算机专业基础综合（数据结构、操作系统）之数据结构考研基础五

套测试题（二） ..................................................................................................................... 17 2018年山东财经大学809计算机专业基础综合（数据结构、操作系统）之数据结构考研基础五

套测试题（三） ..............................................................................................

苏州大学简介

苏州大学坐落于素有"人间天堂"之称的古城苏州，是国家"211工程"重点建设高校和江苏省属重点综合性大学，其主要前身为创建于1900年的东吴大学。一百多年来，一代代苏大人始终秉承"养天地正气，法古今完人"的校训精神；坚守"学术至上，学以致用，培养模范公民"的办学理念；传承和弘扬"自由开放，包容并蓄，追求卓越"的优良校风和"博学笃行，止于至善"的优良学风；努力培育兼具"自由之精神、卓越之能力、独立之人格、社会之责任"的"完人"。作为全国最早创建的现代高等学府之一，苏州大学曾创造了中国近代高等教育史上的若干个第一：第一家以西式办学体制举办大学、第一家开展研究生教育并最早授予硕士学位、第一家开设法学专业教育、第一家创办大学学报等等。1952年全国院系调整时，东吴大学文理学院与苏南文化教育学院（建国初由省立教育学院、国立社会教育学院和无锡国学专修学校合并组建而成）、江南大学数理系合并为苏南师范学院，同年定名为江苏师范学院，在原东吴大学校址办学。1982年，经国务院批准改办为苏州大学。后经教育部和江苏省人民政府批准，1995年苏州蚕桑专科学校、1997年苏州丝绸工学院、2000年苏州医学院先后并入苏州大学。目前，苏州大学已发展成为一所拥有哲学

数据结构与算法

一 选择题

1．算法的计算量的大小称为计算的（ B ）。

A．效率 B. 复杂性 C. 现实性 D. 难度

2．下面说法正确的是（ C ）

(1）算法原地工作的含义是指不需要任何额外的辅助空间

（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2)的算法 （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低

A．(1) B.(1),(2) C.(1),(4) D.(3)

3. 连续存储设计时，存储单元的地址（ A ）。

A．一定连续 B．一定不连续 C．不一定连续 D．部分连续，部分不连续

4. 下述哪一条是顺序存储结构的优点？（A ）

A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示

5．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。

A．顺序表 B．双链表 C．带头结点的双循环链表