山东科技大学813数据结构与操作系统

数据结构与操作系统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、对于堆排序法，快速排序法和归并排序法，若仅从节省存储空间考虑，则应该首先选取其中哪种方法？其次选取哪种方法？若

山东科技大学2012—2013学年第二学期

《操作系统》考试试卷（A卷）

班级 姓名 学号 题号 得分 1. 2.

一 二 三 四 总得分 评卷人 审核人 ( ) ( )

一、单项选择题（每小题1.5分，共30分）

系统出现死锁的原因是( )

A．计算机系统发生了重大故障 B．有多个封锁的进程同时存在

C．若干进程因竞争资源而无休止的等待着，它方释放已占有的资源

D．资源数大大少于进程数，或进程同时申请的资源数大大超过资源总数

在请求页式系统中，页表中应包括（ ）。

A．页长 B．页帧号 C．程序标识 D．段号

3． 操作系统中采用缓冲技术，能够减少对CPU的( )的次数，从而提高资源的

( ) 利用率。

A．中断 B．访问 C．控制 D．依赖 4． 下面关于设备属性的论述中正确的是（）

A．字符设备的一个基本特性是可寻址的，即能指定输入时的源地址和输出时的目标地址； ( ) B．共享设备必须是可寻址的

习题1

1．操作系统的基本功能是什么？

2．什么是批处理、分时操作系统、实时操作系统？各有什么特征？ 3．多道程序设计与多重处理有何区别？

4．讨论操作系统可以从哪些角度出发，如何把它们统一起来？ 5．现代操作系统对运行环境有何要求？1

习题2

1．有人说，一个进程是由伪处理机执行的一个程序，这话对吗？为什么？ 2．比较进程与程序的联系和区别。

3．我们说程序的并发执行将导致最终结果失去封闭性。这话对所有的程序都成立吗？试举例说明。

4．什么是临界区？举一临界区的例子。 5．什么是线程？线程和进程有何区别？

6．某高校计算机系开设网络课并安排上机实习，假设机房共有2m台机器，有2n名学生选该课，规定：

① 每2个学生组成一组，各占一台机器，协同完成上机实习；

② 只有一组2个学生到齐，并且此时机房有空闲机器时，该组学生才能进入机房； ③ 上机实习由一名教师检查，检查完毕，一组学生同时离开机房。 试用P、V操作模拟上机实习过程。

7．今有三个并发进程R，M，P，它们共享了一个可循环使用的缓冲区B，缓冲区B共有N个单元。进程R负责从输入设备读信息，每读一个字符后，把它存放在缓冲区B的一个单元中；进程M负责处理读入的字符，若发现读入的字

计算机操作系统

一．单项选择题（每小题2分，共30分）

1. 进程具有并发性和（ ）两大重要属性。

A. 动态性 B. 静态性 C. 易用性 D. 封闭性 2. 在分时操作系统中，（ ）是衡量一个分时系统的一项重要指标。

A. 响应时间 C. 吞吐量

B. 高可靠性 D. 时间片轮转

3. 进程所请求的一次打印输出结束后，将使进程状态从（ ）。

A. 运行态变为就绪态 B. 运行态变为等待态 C. 就绪态变为运行态 D. 等待态变为就绪态 4. 常用的文件存取方法有两种：顺序存取和（ ）存取。 A. 流式 B. 串联 C. 索引 D. 随机 5. 采用多道程序设计能（ ）。

A. 减少调度次数

C. 缩短每道作业的执行时间

B. 减少处理器空闲时间 D. 避免发生资源竞争现象

6. 临界区是指并发进程中涉及共享变量的（ ）。

A. 程序段 C. 公共数据区

B. 管理信息区 D. 信息保留区

7. 产生死锁的四个必要条件是：互斥使用、（ ）、不可抢占和循环等待资源。

A. 请求并阻塞 C. 请求并释放

B. 占有并等待 D. 释放并阻塞

目录

2017年辽宁科技大学软件学院813专业基础综合（数据结构与算法、数据库原理）考研强化模拟题（一） (2)

2017年辽宁科技大学软件学院813专业基础综合（数据结构与算法、数据库原理）考研强化模拟题（二） (14)

2017年辽宁科技大学软件学院813专业基础综合（数据结构与算法、数据库原理）考研强化模拟题（三） (22)

2017年辽宁科技大学软件学院813专业基础综合（数据结构与算法、数据库原理）考研强化模拟题（四） (30)

2017年辽宁科技大学软件学院813专业基础综合（数据结构与算法、数据库原理）考研强化模拟题（五） (38)

第1 页，共49 页

2017年辽宁科技大学软件学院813专业基础综合（数据结构与算法、数据库原理）考

研强化模拟题（一）

说明：①本资料为VIP学员内部使用，严格按照2017考研专业课大纲及历年常考题型出题。————————————————————————————————————————一、选择题

1．在需求分析阶段，结构化分析和建模方法是一种较为有效的需求分析方法，下列不属于结构化分析和建模方法优点的是（）。

A.用图形化的模型能直观表示系统功能

B.可避免过早陷入具体细节

C.图形对象不涉及太多技术术语，便于用户理解模

计算机——《数据结构》

第1页 共13页

1．简述栈的基本操作

2．给定权值组W={1，3，78，14，20，28}，建立哈夫曼树。 3．试求下面的网络的最小生成树

10 1?C10

69 ?B15?E5 613 6?A?D

84.对一组关键字49，7，50，5，94，16，90，29，71，使用希尔排序，写出对d1?3时的一趟排序的结果。 1-4题答案：

1、栈的基本操作有：

栈的建立，判栈满，判栈空，压栈，退栈和取栈顶元素等。 2、

144

66

7838

28 1820 414

3 13、 41 96 536 625 84、

4950594169029717

1649295090947175

5．写出队列的基本操作。

a 6．对下面的二叉树

（１） 其中序遍历序列为

b

c （２）其后序遍历序列为 d e

5

g

h 7．给定一组关键字序列12，7，51，32，23，试构造一棵查找树。

8．对一组关键字49，7，50，5，94，16，90，29，71，使用快速排序，试给出第一次划分过程。

5-8题答案：

5．队列的基本操作有：

队列的建立，判队空，

西安电子科技大学试卷

考试时间 120 分钟 试卷编号 参考答案

班级 学号 姓名 任课老师姓名 题号 得分

一 二 三 四 五 总 分

请按下述要求正确答题：

1. 在试卷指定位置上正确写入你的班级、学号、姓名和任课老师姓名。 2．全部试卷共 11 页。试卷必须交回，否则以零分计。

3．试题解答必须写在试卷上，若试卷上写不下可以写在试卷的背面，写在草稿纸上的解答一律无效。

4．本试卷的试题共有五道大题，需要全部解答。

5．解答前务必阅读清楚题意，及解答要求，否则导致不能正确评分概由自己负责。

一、 单项选择题（每小题1分，共10分）

１． 访管指令所引起的中断属于（ C ）中断。

A．外中断 B．I/O中断 C．软中断 D．程序中断 ２． 资源静态分配法破坏了死锁产生的（ B ）条件来预防死锁的发生。 A．互斥控制 B．保持和等待 C．不可剥夺控制 D．循环等待

３． 虚拟存储的基础是程序局部性理论，它的

西安电子科技大学考试试卷

一、 单项选择题（每小题1分，共10分）

１． 访管指令所引起的中断属于（ C ）中断。

A．外中断 B．I/O中断 C．软中断 D．程序中断 ２． 资源静态分配法破坏了死锁产生的（ B ）条件来预防死锁的发生。

A．互斥控制 B．保持和等待 C．不可剥夺控制 D．循环等待

３． 虚拟存储的基础是程序局部性理论，它的基本含义是（ B ）。

A．代码的顺序执行 B．程序执行时对内存访问的不均匀性 C．变量的连续访问 D．指令的局部性 ４． 关于SPOOLING系统（ D ）的描述是错误的。

A．不需要独占设备 B．加快了作业执行的速度 C．使独占设备变成了共享设备 D．利用了处理器与通道并行工作的能力

５． 设系统中有m个同类资源数，n为系统中的并发进程数，当n个进程共享m个互斥资源时，每个进程的最大需求数是w，试问下列情况下系统会死锁的是（ D ）。

A．m=4，n=3，w=2 B．m=2，n=2，w=1 C．m=5，n=2，

操作系统实验指导书

课 程 号：1002060106

适用专业：计算机各专业

制 定 人：吴江红

教 研 室：计算机科学与技术教研室

计算机科学与信息工程学院

2012 年5 月

前言

操作系统是计算机的核心和灵魂。操作系统软件的设计对整个计算机的功能和性能起着至关重要的作用，所以此门课也是必不可少的，是面向计算机科学与技术、网络工程、软件工程等大多数计算机专业本科生和研究生开设的一门计算机专业课程。

操作系统是计算机系统的核心，《操作系统》课程是计算机科学与技术专业的重要必修课。本课程的目的是使学生掌握现代计算机操作系统的基本原理、基本设计方法及实现技术，具有分析现行操作系统和设计、开发实际操作系统的基本能力。

本课程的理论性强，内容抽象，特别是进程管理，需要通过严密的逻辑思维来想象微观时间世界中的处理机调度与运行。

通过学习使学生掌握计算机操作系统的基本原理及组成；计算机操作系统的基本概念和相关的新概念、名词及术语；了解计算机操作系统的发展特点、设计技巧和方法；对常用计算机操作系统(Dos、Windows和Unix或 Linux) 会进行基本的操作使用。

实验要求

为了顺利完成编译原理课程实验，学生应做到： （1） 熟练掌握一种高级程序