一、单项选择题：1～40小题，每小题2分，共80分。在每小题给出的四
个选项中，请选出一项最符合题目要求的。
1.在下面的程序段中，时间复杂度为（）。
int fun( int n)
{ if( n = = 1 )
return 1;
return n * fun( n - 1 );
}
A．O( 2n ) B．0(nlogn) C．0(n2) D．O(n)
2.下列排序算法中，平均时间复杂度最小的是（）。
A．归并排序B．起泡排序 C．简单选择排序 D．直接插入排序
3.关于线性表的描述正确的是（）。
A. 采用顺序存储时，随机存取的时间复杂度是O(1)
B. 采用链式存储时，随机存取的时间复杂度是O(1)
C. 采用顺序存储时，其存储地址一定是不连续的
D. 采用链式存储时，其存储地址一定是不连续的
4.往队列中输入序列{1,2,3,4}，然后出队1个数字，则出队的数字是
（）。
A．4 B．3 C．1 D．不确定
5.往栈中输入序列{1,2,3,4}，然后出栈1个数字，则出栈的数字是
（）。
A．4 B．3 C．1 D．不确定
6.假设二叉排序（查找）树上有n个节点，树的高度为h，则查找的平均
时间复杂度是（）。
A．O( n ) B．0(nlogn) C．0(logn) D．O(h)
7.有10个节点的无向图，至少需要多少条边才能成为一个连通图（）。
A．5 B．45 C．9 D．10
8.关于邻接矩阵，下列说法中错误的是（）。
A．有向图的邻接矩阵不一定是对称矩阵
B. 无向图的邻接矩阵不一定是对称矩阵
C．若图G的邻接矩阵是对称的，则G不一定是无向图
D．若图G的邻接矩阵是对称的，则G不一定是有向图
9.折半查找算法中查找的时间复杂度是（）。
A．O( n ) B．0(nlogn) C．0(logn) D．O(n2) 10.一个有序数据序列中有15个数据，采用折半查找法在其中查找一个数
据，最多需要比较几次就能得到结果（）。
A.4 B．5 C. 7 D. 15
11.图1所示这棵二叉树的先（前）序遍历结果是（）。
A．ABDCEF B. ABCDEF C. DBAECF D. DBEFCA
图1.二叉树
12.设有一个顺序栈，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素的
出栈顺序为s2, s3, s4, s5, s6, s1，则顺序栈的容量至少为 ( )。
A．5 B．4 C．3 D．2
13.在有16个节点的AVL树中查找一个数据，下列表述正确的是（）。
A．最多只要比较5次就可以得到结果
B．可能要比较16次才能得到结果
C．最多只要比较4次就可以得到结果
D．必须比较8次以上才能得到结果
14.关于宽度优先搜索描述正确的是（）。
A．结果唯一 B．结果不唯一 C．无法遍历所有顶点 D．先访问具有较多边的顶点
15.对数据7，3，9，2，5进行排序时，第一趟的排序结果如下：
3，7，9，2，5；
则采用的排序算法是（）。
A．冒泡排序 B．直接插入排序 C．快速排序 D．归并排序
16.把数据1，2，3，4，5，6，7通过插入操作构造一棵二叉查找树时，下
列描述正确的是（）。
A．按照1，2，3，4，5，6，7的插入顺序构造的查找树，查找效率最高B．按照7，6，5，4，3，2，1的插入顺序构造的查找树，查找效率最高C．按照4, 2, 1, 3, 6, 5, 7的插入顺序构造的查找树的查找效率最高D．查找效率与构造查找树时插入数据的顺序无关
17.已知有n个数据已经存储在必要的数据结构中，若采用最快的查找算
法，在n个数据中要查找一个数据元素，平均时间复杂度是（）。
A．O( n ) B．0(nlogn) C．0(logn) D．O(1)
18.一棵满二叉树共有5层（树根为第一层），则叶子节点个数为（）。
A. 15
B. 16
C. 8
D. 7
19.计算两个多项式相加时，宜采用的数据结构是（）。
A．图 B.树 C. 集合 D. 链表
20.假设某快递公司每天要用1辆车去100个地方送货，为尽量减少行车里
程，节省汽油，需要事先规划好送货路线，请问该选用什么样的数据结构（）。
A．线性表 B. 图 C.队列 D. 二叉树
21.早期操作系统主要追求的是（）。
A．系统的效率B．用户的方便性C．可移植性D．可扩充性22.以下软件中，与计算机硬件关系最紧密的是（）：
A．编译程序B．数据库管理程序C．游戏程序D．操作系统23.现代操作系统具有并发性和共享性，是由( )的引入而导致的。
A．单道程序B．磁盘C．对象D．多道程序24.单处理器计算机系统中，（）是并行操作的。
A．处理机操作和通道操作；
B．程序与程序；
C．主程序与子程序；
D．用户程序与操作系统程序；
25.操作系统的主要功能有（）。
A．进程管理、存储器管理、设备管理、处理机管理；
B．虚拟存储管理、处理机管理、进程调度、文件系统；
C．处理机管理、存储器管理、设备管理、文件系统；
D．进程管理、中断管理、设备管理、文件系统；
26.在下面关于并发性的叙述中正确的是（）。
A．并发性是指若干事件在同一时刻发生；
B．并发性是指若干事件在不同时刻发生；
C．并发性是指若干事件在同一时间间隔发生；
D．并发性是指若干事件在不同时间间隔发生；
27.当（）时，进程从执行状态转变为就绪状态。
A．进程被调度程序选中B．时间片用完
C．等待某一事件D．等待的事件发生
28.有m个进程共享同一临界资源，若是用信号量机制实现对临界资源的互
斥访问，则信号量的变化范围为（）。
A．1至-(m-1) B．1至m-1 C．1至-m D．1至m
29.在下列选项中，属于解除死锁的方法是（）。
A．剥夺资源法B．资源分配图简化法
C．银行家算法D．资源静态分配法
30.在下面关于虚拟存储器的叙述中，正确的是( )。
A．要求程序运行前必须全部装入内存且在运行过程中一直驻留在内存；
B．要求程序运行前不必全部装入内存且在运行过程中不必一直驻留在内存；
C．要求程序运行前不必全部装入内存但是在运行过程中必须一直驻留在内存；
D．要求程序运行前必须全部装入内存但在运行过程中不必一直驻留在内存；
31.在页式存储管理系统中，页表内容如下表所列：
页号块号
0 2
1 1
2 6
3 3
4 7
若页的大小为4KB，这地址转换机构将逻辑地址0转换为物理地址（）。
A．8192 B．4096 C．2048 D．1024
32.下列有可能导致以进程从运行态转变为就绪态的事件是（）。
A．一次I/O操作结束
B．运行进程需启动I/O操作
C．进程结束运行
D．出现了比运行进程优先权更高的进程
33.位示图用于（）。
A．页面置换B．磁盘空间管理C．文件目录查找D．磁盘驱动调度34.假设两个进程共用一个临界资源的保护互斥量mutex，当mutex=1时表
示（）。
A．一个进程进入了临界区，另一个进程等待
B．没有一个进程进入临界区
C．两个进程都进入临界区
D．两个进程都在等待
35.在采用动态优先权的优先权调度算法中，如果所有的进程都具有相同的
优先权初始值，则此时的优先权调度算法实际上和（）相同。
A．先来先服务调度算法
B．短作业优先调度算法
C．时间片轮转调度算法
D．长作业优先调度算法
36.采用动态重定位方式装入作业，在执行中允许（）将其移走。
A．用户有条件的B．用户无条件的
C．操作系统有条件的D．操作系统无条件的
37.在虚拟存储系统中，若进程在内存中占3块（开始都为空），采用先进
先出的页面淘汰算法，当执行访问页号顺序为1、2、3、4、1、2、5、
1、2、3、4、5、6时，将产生（）次缺页中断。
A．7 B．8 C．9 D．10
38.在下面的I/O控制方式中，需要CPU干预最少的是（）。
A．程序I/O方式
B．中断驱动I/O方式
C．直接存储器访问DMA方式
D．I/O通道控制方式
39.以下描述中正确的是（）。
A．顺序文件适合于建立在顺序存储设备上，而不适合建立在磁盘上；
B．显式链接文件将分配给文件的下一个物理盘块的地址登记在该文件的前一个物理盘块中；
C．顺序文件必须采用连续分配方式，而链接文件和索引文件则可采用离散分配方式；
D．在MS-DOS中采用的FAT文件系统是隐式链接文件结构；
40.下面描述中错误的是（）。
A．一个文件在同一个文件系统中、不同的存储介质上的拷贝，应采用同一种物理结构；
B．文件的物理结构不仅与外存的分配方式相关，还与存储介质的特性相关，通常在磁带上只适合使用顺序结构；
C．采用顺序结构的文件既适合进行顺序访问，也适合进行随机访问；
D．虽然磁盘是随机访问的设备，但其中的文件也可以采用顺序结构；
二、综合应用题：41～45小题，共70分。
41. 有向图如图2 所示，请完成以下问题。
（1）（5分）请画出邻接矩阵
（2）（5分）请画出邻接表
（3）（5分）请写出以A为起点的深度优先搜索结果
（4）（5分）请写出A到D的最短路径及其长度
图2
42. 把数据序列{89,18,49,58,69}放入表长为10的散列（哈希）表中，散列函
数h(x)=x % 10,请完成以下问题。
（1）（10分）用分离链接法，请画出最终的散列表。
（2）（10分）用开放定址法和二次探测法，探测函数为f(i)= i*i，请画出最终的散列表。
43. (10分)在银行家算法中，若出现下述资源分配情况(5个进程，3类资源)：
请问：
（1）(7分) 该状态是否安全？若是，请给出安全序列,要求写出详细推导
过程。若不是，也请详细说明原因。
（2）（3分）若进程P2提出请求Request(1，2 ，2，2)后，系统能否将资
源分配给它？为什么？（能与不能都要求详细写出理由）
44.(10分)在一个请求分页系统中，采用LRU页面置换算法时，假如一个作业
的页面走向为4、3、2、1、4、3、5、4、3、2、1、5，开始时页面都不在内存中，当分配给该作业的物理内存块数M分别为3和4时：
（1）（7分）给出页面置换过程，分别计算在访问那过程中所发生的缺页
次数和缺页率。
（2）（3分）根据两种情况下的页面缺页率，能够得到什么结论？
45.（10分）假设有4位哲学家围坐在一张圆形餐桌旁，做以下事情：吃饭或
者思考。吃东西时他们就会停止思考，思考的时候停止吃东西。每两位哲学家
之间有一根筷子，哲学家想要吃饭必须要同时拿到左右两根筷子。请利用纪录
型信号量写出一个不会出现死锁的哲学家进餐问题求解算法。
【完】
第一章： 1. 什么是操作系统？OS的基本特性是？主要功能是什么 OS是控制和管理计算机硬件和软件资源，合理组织计算机工作原理以及方程用户的功能的集合。特性是：具有并发，共享，虚拟，异步的功能，其中最基本的是并发和共享。主要功能：处理机管理，存储器管理，设备管理，文件管理，提供用户接口。 2. 操作系统的目标是什么？作用是什么？ 目标是：有效性、方便性、可扩充性、开放性 作用是：提供用户和计算机硬件之间的接口，提供对计算机系统资源的管理，提供扩充机器 3. 什么是单道批处理系统？什么是多道批处理系统？ 系统对作业的处理是成批的进行的，且在内存中始终保持一道作业称此系统为单道批处理系统。 用户所提交的作业都先存放在外存上并排成一个队列，然后，由作业调度程序按一定的算法从后备队列中选择若干个调入作业内存，使他们共享CPU和系统中的各种资源。 4 ?多道批处理系统的优缺点各是什么？ 优点：资源利用率高，系统吞吐量大。缺点：平均周转时间长，无交互能力。 引入多道程序技术的前提条件之一是系统具有终端功能，只有有中断功能才能并发。 5. 什么是分时系统？特征是什么？ 分时系统是指，在一台主机上连接了多个带有显示器和键盘的终端，同时允许多个用户通过自己的终端，以交互的方式使用计算机，共享主机中的资源。 特征：多路性、独立性、及时性、交互性 *有交互性的一般是分时操作系用，成批处理无交互性是批处理操作系统，用于实时控制或实时信息服务的是实时操作系统，对于分布式操作系统与网络操作系统，如计算机之间无主次之分就是分布式操作系统，因为网络一般有客户-服务器之分。 6. 什么是实时操作系统？ 实时系统：系统能及时响应外部事件的请求，在规定的时间内处理完。按照截止时间可以分为1硬实时任务（必须在截止时间内完成）2软实时任务（不太严格要求截止时间） 7用户与操作系统的接口有哪三种？ 分为两大类：分别是用户接口、程序接口。 用户接口又分为：联机用户接口、脱机用户接口、图形用户接口。 8. 理解并发和并行？并行（同一时刻）并发（同一时间间隔） 9. 操作系统的结构设计 1 ?无结构操作系统，又称为整体系统结构，结构混乱难以一节，调试困难，难以维护 2?模块化os结构，将os按功能划分为一定独立性和大小的模块。是os容易设计，维护, 增强os的可适应性，加速开发工程 3?分层式os结构，分层次实现，每层都仅使用它的底层所提供的功能 4. 微内核os结构，所有非基本部分从内核中移走，将它们当做系统程序或用户程序来实现，剩下的部分是实现os核心功能的小内核，便于扩张操作系统，拥有很好的可移植性。 第二章： 1 ?什么叫程序？程序顺序执行时的特点是什么？ 程序：为实现特殊目标或解决问题而用计算机语言编写的命令序列的集合特点：顺序性、封闭性、可再现性 2. 什么是前趋图？（要求会画前趋图）P35图2-2 前趋图是一个有向无循环图，记为DAG ,用于描述进程之间执行的前后关系。 3?程序并发执行时的特征是什么？ 特征：间断性、失去封闭性、不可再现性
谢谢阅读一、单项选择题：1～40小题，每小题2分，共80分。在每小题给出的四 个选项中，请选出一项最符合题目要求的。 1.在下面的程序段中，时间复杂度为（）。 int fun( int n) { if( n = = 1 ) return 1; return n * fun( n - 1 ); } A．O( 2n ) B．0(nlogn) C．0(n2) D．O(n) 2.下列排序算法中，平均时间复杂度最小的是（）。 A．归并排序B．起泡排序 C．简单选择排序 D．直接插入排序 3.关于线性表的描述正确的是（）。 A. 采用顺序存储时，随机存取的时间复杂度是O(1) B. 采用链式存储时，随机存取的时间复杂度是O(1) C. 采用顺序存储时，其存储地址一定是不连续的 D. 采用链式存储时，其存储地址一定是不连续的 4.往队列中输入序列{1,2,3,4}，然后出队1个数字，则出队的数字是（）。 A．4 B．3 C．1 D．不确定 5.往栈中输入序列{1,2,3,4}，然后出栈1个数字，则出栈的数字是（）。 A．4 B．3 C．1 D．不确定 6.假设二叉排序（查找）树上有n个节点，树的高度为h，则查找的平均 时间复杂度是（）。 A．O( n ) B．0(nlogn) C．0(logn) D．O(h) 7.有10个节点的无向图，至少需要多少条边才能成为一个连通图（）。 A．5 B．45 C．9 D．10 8.关于邻接矩阵，下列说法中错误的是（）。 A．有向图的邻接矩阵不一定是对称矩阵 B. 无向图的邻接矩阵不一定是对称矩阵 C．若图G的邻接矩阵是对称的，则G不一定是无向图 D．若图G的邻接矩阵是对称的，则G不一定是有向图 9.折半查找算法中查找的时间复杂度是（）。 A．O( n ) B．0(nlogn) C．0(logn) D．O(n2) 谢谢阅读
数据结构和操作系统试题 姓名________ 学号_________ 得分__________ 数据结构部分 一、判断题。（正确的在括号里打√，错误的打×） ①数据元素是数据的最小单位。（） ②完全二叉树中，若一个结点没有左孩子，则必是树叶。（） ③关键路径是AOE网络中从源点到汇点的最长路径。（） ④顺序存储法适用于存储结构为顺序或链式存储的线性表。（） ⑤对任何一棵二叉树，如果叶子结点数为n0，度为2的结点数为n2，则n2 = n0 - 1。（） ⑥快速排序是一种属于选择排序类的方法，时间效率较高。（） ⑦数组的常见操作有存取、修改、删除、插入。（） ⑧若非空二叉树中每个结点有两个子结点，且左子树的根小于根结点，右子树的根不小于根结点，则是二叉排序树。（） ⑨将一棵树转换为二叉树后，根结点没有左子树。（） ⑩在一般情况下，处理冲突方法相同的哈希表，其平均查找长度依赖于哈希表的装填因子。（） 二、选择和填空 1.在一个长度为n的顺序表（即顺序存储的线性表）中，向第i个元素（1<=i<=n+1）之前插入 一个新元素时，需向后移动______个元素。 A. n-i B. n-i+1 C. n-i-1 D. i 2.在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为__________。 3.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用 ________存储方式最节省运算时间。 A.单链表 B.仅有头指针的单循环链表 C. 双向循环链表 D.仅有尾指针的单循环链表 4.若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不会超过________。 A．n/2 B．n C．(n+1)/2 D．n+1 5. 对有18个元素的有序表A[1]～A[18]作二分查找，则查找A[3]的比较序列的下标为______。 A．1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 6. 下面程序段的时间复杂度是______________。 for (i=0; i 《数据结构与操作系统》考试大纲 一、考查目标 数据结构和操作系统是计算机类专业的核心课程。《数据结构和操作系统》科目考察的内容包括《数据结构》和《操作系统》的基本内容，要求考生掌握相关的概念、方法和技术，并具备较强的程序设计能力，能够灵活应用相关的方法和技术解决实际问题。 二、考试形式与试卷结构 （一）试卷成绩及考试时间 本试卷满分为150分，考试时间为180分钟。 （二）答题方式 答题方式为闭卷、笔试。 （三）试卷内容结构 各部分内容所占分值为： 数据结构75分 操作系统75分 （四）试卷题型结构 1．数据结构 选择题：15小题，每小题2分，共30分 简答题：3小题，每小题10分，共30分 算法题：1小题，每小题15分，共15分 2.操作系统 三、考查范围 数据结构 一、考查目标 1、掌握数据结构的基本概念、方法和技术。 2、掌握程序设计的基本方法和技巧。 3、能够应用相关知识解决一些有实际背景的问题。 二、考查内容 1. 绪论 数据结构的概念；基本概念与术语；算法的概念，算法的特性，以及算法设计的要求，算法效率的度量。 2. 线性表 线性表相关的基本概念和结构特点；线性表的顺序存储方式以及两种不同的实现方法：表空间的静态分配和动态分配；线性表的链式存储方式的实现；链表与顺序表的相似及不同之处，优缺点比较，各自适用的场合；线性表的各种实现方式能够实现指定的操作。 3.栈和队 栈、队列的定义及其相关数据结构的概念，包括：顺序栈，链栈，共享栈，循环队列，链队列等；栈与队列插入删除操作的特点；栈和递归的关系；栈和队列各种实现方式。 4. 串 串的基本概念，朴素的模式匹配算法。 5.数组 数组的定义；数组的存储，行序和列序；特殊矩阵的定义；特殊矩阵的压缩存储。 6.树和二叉树 1.2操作系统结构设计 操作系统是一种大型、复杂的并发系统，为了研制操作系统，首先必须研究它的结构，力求设计出结构良好的程序。操作系统的结构设计有两层含义：一是研究操作系统的整体结构，由程序的构成成分组成操作系统程序的构造过程和方法；二是研究操作系统程序的局部结构，包括数据结构和控制结构。采用不同的构件和构造方法可组成不同结构的操作系统。本节将在讨论操作系统构件之后，全面介绍各种操作系统的构造方法。 操作系统的组件 通常把组成操作系统程序的基本单位称作操作系统的构件。剖析现代操作系统，构成操作系统的基本单位除内核之外，主要还有进程、线程、类程和管程。 1．内核 现代操作系统中xx采用了进程的概念，为了解决系统的并发性、共享性和随机性，并使进程能协调地工作，单靠计算机硬件提供的功能是十分不够的。例如，进程调度工作目前就不能用硬件来实现；而进程自己调度自己也是困难的。所以，系统必须有一个软件部分能对硬件处理器及有关资源进行首次改造，以便给进程的执行提供良好运行环境，这个部分就是操作系统的内核。 由于操作系统设计的目标和环境不同，内核的大小和功能有很大差别。有些设计希望把内核做得尽量小仅具有极少的必需功能，称为微内核（microkernel），其他功能都在核外实现，通过微内核提供 的消息传递机制完成其余功能模块间的联系；有些设计则希望内核具有较多的功能，虽然其内部也可划分成层次或模块，但运行时是一个大二进制映像，模块间的联系可通过函数或过程调用实现，称为单内核（monolithic kernel）。操作系统的一个基本问题就是内核的功能设计。微内核结构是现代操作系统的特征之一，这种方法把内核和核外服务程序的开发分离，可为特定应用程序或运行环境要求定制服务程序，具有较好的可伸缩性，简化了实现，提供了灵活性，很适合分布式系统的构造。 一般而言，内核必须提供以下3个方面的功能。 （1）xx处理。xx处理是内核中最基本的功能，也是操作系统赖以活动的基础，为了缩短屏蔽xx的时间，增加系统内的并发性，通常它仅仅进行有限的、简短的处理，其余任务交给在内核之外的特殊用户态进程完成。当xx事件产生时，先由内核截获并转向xx处理例行程序进行原则处理，它分析xx事件的类型和性质，进行必要的状态修改，然后交给内核之外的进程去处理。例如，产生外围设备结束xx事件时，内核首先分析是否正常结束，如果是正常结束，那么，就应释放等待该外围传输的进程；否则启动相应设备管理进程进行出错或异常处理。又如当操作员请求从控制台输入命令时，内核将把这一任务转交给命令管理进程去处理，以接收和执行命令。 （2）短程调度。主要职能是分配处理器。当系统中发生了一个事件之后，可能一个进程要让出处理器，而另一个进程又要获得处理器。短程调度按照一定的策略管理处理器的转让，以及完成保护和恢 数据结构： 一、重点知识点 1.了解算法的时间复杂度的概念，会求一个算法的时间复杂度； 2.了解线性表的概念，掌握线性表的顺序表示与链式表示； 3.掌握链表的增、删、查、改等基本操作； 4.理解栈和队列的基本概念； 5.掌握循环队列的判空等基本操作； 6.掌握栈在括号匹配和递归中的应用； 7.了解数组的概念； 8.理解矩阵的压缩存储； 9.了解树和二叉树的基本概念； 10.掌握二叉树的遍历、线索二叉树等相关算法； 11.掌握二叉排序树、平衡二叉树以及Huffman树； 12.了解图的基本概念； 13.理解图的的邻接矩阵法存储与邻接表法存储的类型定义； 14.掌握图的遍历算法； 15.掌握图的最小生成树算法、最短路径以及拓扑排序应用及算法； 16.了解查找的基本概念； 17.理解顺序查找方法与折半查找方法； 18.理解B树的概念与基本操作； 19.掌握散列表的概念、构造以及处理冲突的方法； 20.了解排序的基本概念； 21.掌握几种排序算法； 22.理解几种排序算法性能优劣的比较； 二、重要概念 一、概述 1.数据：信息的载体，是描述客观事物属性的数、字符以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。 2.数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 3.数据项：构成数据元素的不可分割的最小单位。 4.数据对象：性质相同的数据元素的集合，是数据的一个子集。 5.数据类型：一个值的集合和定义在此集合上一组操作的总称。、 6.时间复杂度：算法中所有语句在算法中重复执行的次数。 二、线性表 1.线性表：具有相同数据类型的n个数据元素的有限序列。 2.顺序表：用一组地址连续的存储单元，依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。 3.单链表：通过一组任意的存储单元来存储线性表中的数据元素。 三、栈和队列 1.栈：只允许在一端进行插入或删除操作的线性表。 2.顺序栈：利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针指示当前栈顶的位置。 3.共享栈：利用栈底位置相对不变的特性，可以让两个顺序栈共享一个一维数据空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸。 4.队列：只允许在表的一端进行插入，而在表的另一端进行删除，这种操作受限的线性表。 5.循环队列：将顺序队列假想为一个环状的空间，即把存储队列元素的表从逻辑上看成一个环。 6.数组:是由n(n>1)个相同类型的数据元素构成的有限序列。 7.压缩存储：为多个值相同的元素只分配一个存储空间，对零元素不分配存储空 操作系统结构设计 操作系统是一种大型、复杂的并发系统，为了研制操作系统，首先必须研究它的结构，力求设计出结构良好的程序。操作系统的结构设计 有两层含义：一是研究操作系统的整体结构，由程序的构成成分组成操作系统程序的构造过程和方法；二是研究操作系统程序的局部结构，包括数据结构和控制结构。采用不同的构件和构造方法可组成不同结构的操作系统。本节将在讨论操作系统构件之后，全面介绍各种操作系统的构造方法。 1.2.1 操作系统的组件 通常把组成操作系统程序的基本单位称作操作系统的构件。剖析现代操作系统，构成操作系统的基本单位除内核之外，主要还有进程、线程、类程和管程。 1．内核现代操作系统中大都采用了进程的概念，为了解决系统的并发性、共享性和随机性，并使进程能协调地工作，单靠计算机硬件提供的功能是十分不够的。例如，进程调度工作目前就不能用硬件来实现；而进程自己调度自己也是困难的。所以，系统必须有一个软件部分能对硬件处理器及有关资源进行首次改造，以便给进程的执行提供良好运行环境，这个部分就是操作系统的内核。 由于操作系统设计的目标和环境不同，内核的大小和功能有很大差别。有些设计希望把内核做得尽量小仅具有极少的必需功能，称为微内 核（microkernel ），其他功能都在核外实现，通过微内核提供的消息传递机制完成其余功能模块间的联系；有些设计则希望内核具有较多的功能，虽然其内部也可划分成层次或模块，但运行时是一个大二进制映像，模块间的联系可通过函数或过程调用实现，称为单内核 （monolithickernel ）。操作系统的一个基本问题就是内核的功能设计。微内核结构是现代操作系统的特征之一，这种方法把内核和核外服务程序的开发分离，可为特定应用程序或运行环境要求定制服务程序，具有较好的可伸缩性，简化了实现，提供了灵活性，很适合分布式系统的构造。 一般而言，内核必须提供以下 3 个方面的功能。 （1）中断处理。中断处理是内核中最基本的功能，也是操作系统赖以活动的基础，为了缩短屏蔽中断的时间，增加系统内的并发性，通常它仅仅进行有限的、简短的处理，其余任务交给在内核之外的特殊用户态进程完成。当中断事件产生时，先由内核截获并转向中断处理例行程序进行原则处理，它分析中断事件的类型和性质，进行必要的状态修改，然后交给内核之外的进程去处理。例如，产生外围设备结束中断事件时，内核首先分析是否正常结束，如果是正常结束，那么，就应释放等待该外围传输的进程；否则启动相应设备管理进程进行出错或异常处理。又如当操作员请求从控制台输入命令时，内核将把这一任务转交给命令管理进程去处理，以接收和执行命令。 （2）短程调度。主要职能是分配处理器。当系统中发生了一个事件之后，可能一个进程要让出处理器，而另一个进程又要获得处理器。短程调度按照一定的策略管理处理器的转让，以及完成保护和恢复现场的工作。由于它是协调进程竞争处理器资源的程序，所以它不是进程而是内核中的一个程序。 （3）原语管理。原语是内核中实现某一功能的不可中断过程。为了协调进程完成通信、并发执行和共享资源，各种原语是必不可少的。通信原语为进程相互传递消息，同步原语能协调并发进程之间的种种制约关系。此外，还有其他原语，如启动外围设备工作的启动原语，若启动不成功则请求启动者应等待，显然，这个启动过程应该是完整的，否则在成为等待状态时，可能外围设备已经空闲。由于设备的操作与硬件密切相关，故通常设备驱动程序等功能都放在内核中完成。 内核是操作系统对裸机的首次改造，内核和裸机组成了一台虚拟机，进程就在这台虚拟机上运行，它比裸机的功能更强大，具有以下特性： （1）虚拟机没有中断，因而，进程的设计者不再需要有硬件中断的概念，用户进程执行中无须处理中断； （2）虚拟机为每个进程提供了一台虚拟处理器，每个进程就好像在各自的私有处理器上顺序地推进，实现了多个进程的并发执行； （3）虚拟机为进程提供了功能较强的指令系统，即它们能够使用机器非特权指令、系统调用和原语所组成的新的指令系统。 为了保证系统的有效性和灵活性，设计内核应遵循少而精的原则。如果内核功能过强，则一方面在修改系统时可能牵动内核；另一方面它占用的内存容量和执行时间都会增大，且屏蔽中断的时间过长也会影响系统效率。因而，设计内核时应注意：中断处理要简单；调度算法要有效；原语应灵活有力、数量适当。这样就可以做到下次修改系统时，尽量少改动内核，执行时中断屏蔽时间缩短。 2．进程管理 程序本身并不能做什么，只有在CPL执行它的指令时才能有所作为；因此，可以把进程看做是正在运行的程序。但是当我们进一步研究时，对进程的定义将更为普遍。例如：一个分时用户程序（如编译器）是一个进程，个人用户在PC上运行的字处理程序是一个进程，一个系统任务（如输出到打印机）也是一个进程，并可以提供允许进程创建与其并发执行的子进程的系统调用。 进程需要特定的资源（包括CPU寸间、内存、文件和I/O设备）来完成工作。这些资源或者在进程创建时分配给它，或者在其运行时分配。除了在进程创建时所获得的各种物理资源和逻辑资源以外，各种各样的初始化数据（或输入）也可能一同传送给进程。例如，考虑一个能够在终端的显示屏上显示一 数据结构与操作系统 科目代码：830 科目名称：数据结构与操作系统 I.考查目标 计算机科学与技术专业课程考试包括数据结构和操作系统两科专业基础课程。要求考生系统地掌握上述专业基础课程的概念、基本原理和方法，能够运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。 II.考试形式和试卷结构 1、试卷满分及考试时间:本试卷满分为150分，考试时间为180分钟 2、答题方式:答题方式为闭卷、笔试 3、试卷内容结构:数据结构80分,操作系统70分 III.考试大纲 第一部分 数据结构 考查目标： 1、熟悉线性表、栈、队列、串、、树和二叉树以及图等基本类型的数据结构及其特点，学会根据实际问题要求选用及设计数据结构； 2、理解数据的逻辑结构、存储结构以及各种基本操作的实现； 3、掌握基本的算法分析和设计方法； 4、掌握数据结构在排序和查找等常用算法中的应用，学会一般问题的算法设计。 考查内容： （一）线性表 （1）线性表的定义和基本操作 （2）线性表的实现 顺序存储 链式存储 线性表的应用 （二）栈和队列 （1）栈和队列的基本概念。 （2）栈和队列两种存储结构表示（顺序存储和链式存储）中基本操作的实现算法。 （3）栈和队列的应用。 （三）字符串 （1）字符串的基本概念。 （2）字符串在顺序存储表示中基本操作的实现算法。 （3）字符串匹配的KMP算法，字符串特征向量的计算方法。 （四）树和二叉树 （1）二叉树的定义及其主要性质。 （2）二叉树的顺序存储结构和链式存储结构。 （3）二叉树的遍历。 （4）二叉树线索化的实质和线索化的过程。 （5）树和森林与二叉树的转换。 （6）树和森林的遍历。 （7）二叉树的应用：二叉搜索树、堆、Huffman树和Huffman编码。 （五）图 （1）图的基本概念。 （2）图的存储（相邻矩阵表示和邻接表表示）及基本操作。 （3）图的两种遍历策略：深度优先搜索和广度优先搜索。 2、《数据结构与操作系统》科目考查的内容范围 一、数据结构 （一）概述 1、数据、数据对象、数据结构、数据类型 2、算法及算法描述 3、算法的时间复杂度和空间复杂度 （二）线性表 1、线性表的概念和基本操作 2、线性表类的定义和实现 3、线性表的应用及算法 （三）栈 1、栈的概念和基本操作 2、栈类的定义和实现 3、栈的应用及算法 （四）队列 1、队列的概念和基本操作 2、队列类的定义和实现 3、队列的应用及算法 （五）递归 1、理解递归的概念以及与栈的关系 2、理解递归的工作原理 3、递归算法的设计 （六）字符串 1、串的概念、术语和基本操作 2、串类的定义和实现 3、朴素模式匹配算法 （七）数组 1、数组的定义和运算 2、数组的按行、按列存储 3、特殊矩阵的压缩存储 （八）二叉树 1、二叉树的概念和相关术语 2、二叉树的先序、中序、后序三种遍历方法 3、线索二叉树 4、哈夫曼树的概念和建立方法 （九）树 1、有关树、森林的概念和术语 2、森林、树与二叉树的转换方法 3、森林、树的遍历方法 （十）图 1、图的定义和相关术语 2、计算机表示 3、图的遍历及算法 4、拓扑排序概念及算法 5、最短路径求解算法 6、最小生成树求解算法 （十一）查找 1、有关查找的基本概念 2、顺序查找算法实现及性能分析 3、二分查找算法实现及性能分析 4、二叉查找树的基本概念 5、二叉查找树下的查找、插入、删除算法 6、二叉查找树建立算法 7、AVL树定义 8、哈希查找的概念、哈希函数的选择及冲突解决方法 9、哈希查找算法实现及性能分析 10、不同查找算法的性能比较 （十二）排序 1、掌握有关排序的基本概念 2、插入排序算法实现及性能分析 3、选择排序算法实现及性能分析 4、希尔排序算法基本原理 5、归并排序算法实现及性能分析 6、快速排序算法实现及性能分析 7、堆和堆排序算法实现及性能分析 8、基数排序算法的基本原理 9、各种排序算法在时间、空间、程序效率等方面的比较 二、操作系统 （一）操作系统及其相关概念 1、操作系统的概念、发展、类型； 2、操作系统的功能、结构。 （二）进程管理 操作系统是一种大型、复杂的并发系统，为了研制操作系统，首先必须研究它的结构，力求设计出结构良好的程序。操作系统的结构设计有两层含义：一是研究操作系统的整体结构，由程序的构成成分组成操作系统程序的构造过程和方法；二是研究操作系统程序的局部结构，包括数据结构和控制结构。采用不同的构件和构造方法可组成不同结构的操作系统。本节将在讨论操作系统构件之后，全面介绍各种操作系统的构造方法。 1.2.1 操作系统的组件 通常把组成操作系统程序的基本单位称作操作系统的构件。剖析现代操作系统，构成操作系统的基本单位除内核之外，主要还有进程、线程、类程和管程。 1．内核 现代操作系统中大都采用了进程的概念，为了解决系统的并发性、共享性和随机性，并使进程能协调地工作，单靠计算机硬件提供的功能是十分不够的。例如，进程调度工作目前就不能用硬件来实现；而进程自己调度自己也是困难的。所以，系统必须有一个软件部分能对硬件处理器及有关资源进行首次改造，以便给进程的执行提供良好运行环境，这个部分就是操作系统的内核。 由于操作系统设计的目标和环境不同，内核的大小和功能有很大差别。有些设计希望把内核做得尽量小仅具有极少的必需功能，称为微内核（microkernel），其他功能都在核外实现，通过微内核提供的消息传递机制完成其余功能模块间的联系；有些设计则希望内核具有较多的功能，虽然其内部也可划分成层次或模块，但运行时是一个大二进制映像，模块间的联系可通过函数或过程调用实现，称为单内核（monolithic kernel）。操作系统的一个基本问题就是内核的功能设计。微内核结构是现代操作系统的特征之一，这种方法把内核和核外服务程序的开发分离，可为特定应用程序或运行环境要求定制服务程序，具有较好的可伸缩性，简化了实现，提供了灵活性，很适合分布式系统的构造。 一般而言，内核必须提供以下3个方面的功能。 （1）中断处理。中断处理是内核中最基本的功能，也是操作系统赖以活动的基础，为了缩短屏蔽中断的时间，增加系统内的并发性，通常它仅仅进行有限的、简短的处理，其余任务交给在内核之外的特殊用户态进程完成。当中断事件产生时，先由内核截获并转向中断处理例行程序进行原则处理，它分析中断事件的类型和性质，进行必要的状态修改，然后交给内核之外的进程去处理。例如，产生外围设备结束中断事件时，内核首先分析是否正常结束，如果是正常结束，那么，就应释放等待该外围传输的进程；否则启动相应设备管理进程进行出错或异常处理。又如当操作员请求从控制台输入命令时，内核将把这一任务转交给命令管理进程去处理，以接收和执行命令。 （2）短程调度。主要职能是分配处理器。当系统中发生了一个事件之后，可能一个进程要让出处理器，而另一个进程又要获得处理器。短程调度按照一定的策略管理处理器的转让，以及完成保护和恢复现场的工作。由于它是协调进程竞争处理器资源的程序，所以它不是进程而是内核中的一个程序。 （3）原语管理。原语是内核中实现某一功能的不可中断过程。为了协调进程完成通信、并发执行和共享资源，各种原语是必不可少的。通信原语为进程相互传递消息，同步原语能协调并发进程之间的种种制约关系。此外，还有其他原语，如启动外围设备工作的启动原语，若启动不成功则请求启动者应等待，显然，这个启动过程应该是完整的，否则在成为等待状态时，可能外围设备已经空闲。由于设备的操作与硬件密切相关，故通常设备驱动程序等功能都放在内核中完成。 内核是操作系统对裸机的首次改造，内核和裸机组成了一台虚拟机，进程就在这台虚拟机上运行，它比裸机的功能更强大，具有以下特性： （1）虚拟机没有中断，因而，进程的设计者不再需要有硬件中断的概念，用户进程执行中无须处理中断； （2）虚拟机为每个进程提供了一台虚拟处理器，每个进程就好像在各自的私有处理器上顺序地推进，实现了多个进程的并发执行； （3）虚拟机为进程提供了功能较强的指令系统，即它们能够使用机器非特权指令、系统调用和原语所组成的新的指令系统。 为了保证系统的有效性和灵活性，设计内核应遵循少而精的原则。如果内核功能过强，则一方面在修改系统时可能牵动内核；另一方面它占用的内存容量和执行时间都会增大，且屏蔽中断的时间过长也会影响系统效率。因而，设计内核时应注意： 数据结构部分 一、单项选择题（每小题2分，共20分） 1.下面关于线性表的叙述中，错误的是哪一个？（）A． 线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单 元。D．线性表采用链接存储，便于插入和删除操作。 2.设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用()最节省时间。 A.单链表 B.单循环链表 C.带尾指针的单循环链表 D.带头结点的双循环链表 3.设栈的输入序列是1，2，3，4，则（）不可能是其出栈序列。 A.1，2，4，3 B.2，1，3，4 C.1，4，3，2 D.4，3，1，2 4.循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则 当前队列中的元素数是()。 A.(rear-front+m)%m B.rear-front+1 C.rear-front-1 D.rear-front 5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是 （）。 A．9B．11C．15D．不确定 6.已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结 果为（）。 A．CBEFDA B．FEDCBA C．CBEDFA D．不定 7.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为（）。 A.11 B.35 C.19 D.53 8.快速排序在最坏情况下的时间复杂度为（）。 A.O(log2n) B.O(nlog2n) C.O(n) D.O(n2) 9.下面关于二分查找的叙述正确的是()。 操作系统实验报告 实验目的： 随着操作系统应用领域的扩大，以及操作系统硬件平台的多样化，操作系统的体系结构和开发方式都在不断更新，目前通用机上常见操作系统的体系结构有如下几种:模块组合结构、层次结构、虚拟机结构和微内核结构。为了更好的了解计算机操作系统体系结构，以及linux 的体系结构，特作此报告。 实验内容： 计算机操作系统体系结构 一、模块组合结构 操作系统刚开始发展时是以建立一个简单的小系统为目标来实现的，但是为了满足其他需求又陆续加入一些新的功能，其结构渐渐变得复杂而无法掌握。以前我们使用的MS-DOS 就是这种结构最典型的例子。这种操作系统是一个有多种功能的系统程序，也可以看成是一个大的可执行体，即整个操作系统是一些过程的集合。系统中的每一个过程模块根据它们要完成的功能进行划分，然后按照一定的结构方式组合起来，协同完成整个系统的功能。如图1所示: 在模块组合结构中，没有一致的系统调用界面，模块之间通过对外提供的接口传递信息，模块内部实现隐藏的程序单元，使其对其它过程模块来说是透明的。但是，随着功能的增加，模块组合结构变得越来越复杂而难以控制，模块间不加控制地相互调用和转移，以及信息传递方式的随意性，使系统存在一定隐患。 二、层次结构 为了弥补模块组合结构中模块间调用存在的固有不足之处，就必须减少模块间毫无规则的相互调用、相互依赖的关系，尤其要清除模块间的循环调用。从这一点出发，层次结构的设计采用了高层建筑结构的理念，将操作系统或软件系统中的全部构成模块进行分类:将基础的模块放在基层(或称底层、一层)，在此基础上，再将某些模块放在二层，二层的模块在基础模块提供的环境中工作;它只能调用基层的模块为其工作，反之不行。严格的层次结构，第N+l层只能在N层模块提供的基础上建立，只能在N层提供的环境中工作，也只能向N 层的模块发调用请求。 在采用层次结构的操作系统中，各个模块都有相对固定的位置、相对固定的层次。处在同一层次的各模块，其相对位置的概念可以不非常明确。处于不同层次的各模块，一般而言，不可以互相交换位置，只存在单向调用和单向依赖。Unix/Linux系统采用的就是这种体系结构。 在层次结构中，强调的是系统中各组成部分所处的位置，但是想要让系统正常运作，不得不协调两种关系，即依赖关系和调用关系。 依赖关系是指处于上层(或外层)的软件成分依赖下层软件的存在、依赖下层软件的运行而运行。例如，浏览器这部分软件就依赖GUI的存在和运行，GUI又依赖操作系统的存在和运行。在操作系统内部，外围部分依赖内核的存在而存在，依赖内核的运行而运行，内核又依赖HAL而运行。处在同层之内的软件成分可以是相对独立的，相互之间一般不存在相互依赖关系。 三、虚拟机结构 虚拟机的基本思想是系统能提供两个功能:①多道程序处理能力;②提供一个比裸机有更方便扩展界面的计算机。操作系统是覆盖在硬件裸机上的一层软件，它通过系统调用向位于 操作系统结构 集团文件发布号：（9816-UATWW-MWUB-WUNN-INNUL-DQQTY- 1.2操作系统结构设计 操作系统是一种大型、复杂的并发系统，为了研制操作系统，首先必须研究它的结构，力求设计出结构良好的程序。操作系统的结构设计有两层含义：一是研究操作系统的整体结构，由程序的构成成分组成操作系统程序的构造过程和方法；二是研究操作系统程序的局部结构，包括数据结构和控制结构。采用不同的构件和构造方法可组成不同结构的操作系统。本节将在讨论操作系统构件之后，全面介绍各种操作系统的构造方法。 1.2.1操作系统的组件 通常把组成操作系统程序的基本单位称作操作系统的构件。剖析现代操作系统，构成操作系统的基本单位除内核之外，主要还有进程、线程、类程和管程。 1．内核 现代操作系统中大都采用了进程的概念，为了解决系统的并发性、共享性和随机性，并使进程能协调地工作，单靠计算机硬件提供的功能是十分不够的。例如，进程调度工作目前就不能用硬件来实现；而进程自己调度自己也是困难的。所以，系统必须有一个软件部分能对硬件处理器及有关资源进行首次改造，以便给进程的执行提供良好运行环境，这个部分就是操作系统的内核。 由于操作系统设计的目标和环境不同，内核的大小和功能有很大差别。有些设计希望把内核做得尽量小仅具有极少的必需功能，称为微内核（microkernel），其他功能都在核外实现，通过微内核提供的消息传递机制完成其余功能模块间的联系；有些设计则希望内核具有较多的功能，虽然其内部也可划分成层次或模块，但运行时是一个大二进制映像，模块间的联系可通过函数或 过程调用实现，称为单内核（monolithickernel）。操作系统的一个基本问题就是内核的功能设计。微内核结构是现代操作系统的特征之一，这种方法把内核和核外服务程序的开发分离，可为特定应用程序或运行环境要求定制服务程序，具有较好的可伸缩性，简化了实现，提供了灵活性，很适合分布式系统的构造。 一般而言，内核必须提供以下3个方面的功能。 （1）中断处理。中断处理是内核中最基本的功能，也是操作系统赖以活动的基础，为了缩短屏蔽中断的时间，增加系统内的并发性，通常它仅仅进行有限的、简短的处理，其余任务交给在内核之外的特殊用户态进程完成。当中断事件产生时，先由内核截获并转向中断处理例行程序进行原则处理，它分析中断事件的类型和性质，进行必要的状态修改，然后交给内核之外的进程去处理。例如，产生外围设备结束中断事件时，内核首先分析是否正常结束，如果是正常结束，那么，就应释放等待该外围传输的进程；否则启动相应设备管理进程进行出错或异常处理。又如当操作员请求从控制台输入命令时，内核将把这一任务转交给命令管理进程去处理，以接收和执行命令。 （2）短程调度。主要职能是分配处理器。当系统中发生了一个事件之后，可能一个进程要让出处理器，而另一个进程又要获得处理器。短程调度按照一定的策略管理处理器的转让，以及完成保护和恢复现场的工作。由于它是协调进程竞争处理器资源的程序，所以它不是进程而是内核中的一个程序。 （3）原语管理。原语是内核中实现某一功能的不可中断过程。为了协调进程完成通信、并发执行和共享资源，各种原语是必不可少的。通信原语为进程相互传递消息，同步原语能协调并发进程之间的种种制约关系。此外，还有其他原语，如启动外围设备工作的启动原语，若启动不成功则请求启动者应等待，显 一、单项选择题：1～40小题，每小题2分，共80分。在每小题给出的四 个选项中，请选出一项最符合题目要求的。 1.在下面的程序段中，时间复杂度为（）。 int fun( int n) { if( n = = 1 ) return 1; return n * fun( n - 1 ); } A．O( 2n ) B．0(nlogn) C．0(n2) D．O(n) 2.下列排序算法中，平均时间复杂度最小的是（）。 A．归并排序B．起泡排序 C．简单选择排序 D．直接插入排序 3.关于线性表的描述正确的是（）。 A. 采用顺序存储时，随机存取的时间复杂度是O(1) B. 采用链式存储时，随机存取的时间复杂度是O(1) C. 采用顺序存储时，其存储地址一定是不连续的 D. 采用链式存储时，其存储地址一定是不连续的 4.往队列中输入序列{1,2,3,4}，然后出队1个数字，则出队的数字是 （）。 A．4 B．3 C．1 D．不确定 5.往栈中输入序列{1,2,3,4}，然后出栈1个数字，则出栈的数字是 （）。 A．4 B．3 C．1 D．不确定 6.假设二叉排序（查找）树上有n个节点，树的高度为h，则查找的平均 时间复杂度是（）。 A．O( n ) B．0(nlogn) C．0(logn) D．O(h) 7.有10个节点的无向图，至少需要多少条边才能成为一个连通图（）。 A．5 B．45 C．9 D．10 8.关于邻接矩阵，下列说法中错误的是（）。 A．有向图的邻接矩阵不一定是对称矩阵 B. 无向图的邻接矩阵不一定是对称矩阵 C．若图G的邻接矩阵是对称的，则G不一定是无向图 D．若图G的邻接矩阵是对称的，则G不一定是有向图 单项选择题：1?40小题，每小题2分，共80分。在每小题给出的四个选项中，请选出一项最符合题目要求的。 1.在下面的程序段中，时间复杂度为 int fun( int n) { if( n = = 1 ) return 1; return n * fun( n - 1 ); } A. 0( 2n ) B . 0(nlogn)( )。 C . 0( n2) D.0( n) 2.下列排序算法中，平均时间复杂度最小的是（）。 A.归并排序B?起泡排序C.简单选择排序 D . 直接插入排序 3.关于线性表的描述正确的是（）。 A. 采用顺序存储时，随机存取的时间复杂度是0（1） B. 采用链式存储时，随机存取的时间复杂度是0（1） C. 采用顺序存储时，其存储地址一定是不连续的 D. 采用链式存储时，其存储地址一定是不连续的 4.往队列中输入序列 （ \{123,4}，然后出队1个数子，则出队的数子是 )0 A. 4 B. 3 C. 1 D.不确定 5.往栈中输入序列 （ \ {1,2,3,4}，然后出栈1个数字，则出栈的数字是)0 A. 4 B. 3 C. 1 D.不确定 6.假设二叉排序（查找）树上有n个节点，树的高度为h，则查找的平均 时间复杂度是（)0 A. 0( n ) B.0(nlogn) C . 0(log n) D.0(h) 7. 有10个节点的无向图，至少需要多少条边才能成为一个连通图（） A. 5 B. 45 C. 9 D. 10 8. 关于邻接矩阵，下列说法中错误的是（）。 A .有向图的邻接矩阵不一定是对称矩阵 B. 无向图的邻接矩阵不一定是对称矩阵 C .若图G的邻接矩阵是对称的，则G不一定是无向图 上海理工大学2017年《数据结构及操作系统》考试大纲第一部分：数据结构 一、参考书目 数据结构（第二版），严蔚敏主编，2006，清华大学出版社。 二、考试内容要求 1、了解数据结构及其分类、数据结构与算法的密切关系。 2、熟悉各种基本数据结构及其操作，学会根据实际问题要求来选择数据结构。 3、掌握设计算法的步骤和算法分析方法。 4、掌握数据结构在排序和查找等常用算法中的应用。 5、初步掌握文件组织方法和索引技术。 三、考试内容 1、数据结构基本概念及简单的算法分析 1)什么是数据结构 2)抽象数据类型及面向对象概念：数据类型；数据抽象与抽象数据类型；面向对象的概念；用于描述数据结构的语言 3)数据结构的抽象层次 4)算法定义 5)性能分析与度量：算法的性能标准；算法的后期测试；算法的事前估计；空间复杂度度量；时间复杂度度量；时间复杂度的渐进表示法；渐进的空间复杂. 2、数组 1)作为抽象数据类型的数组：数组的定义和初始化；作为抽象数据类型的数组；数组的顺序存储方式 2)顺序表：顺序表的定义和特点；顺序表的类定义；顺序表的查找、插入和删除；使用顺序表的事例 3)字符串：字符串的抽象数据类型；字符串操作的实现；字符串的模式匹配 3、链表 1)单链表：单链表的结构；单链表的类定义；单链表中的插入与删除；带表头结点的单链表；用模板定义的单链表类；单链表的游标类；静态链表 2)循环链表：循环链表的类定义；用循环链表解约瑟夫问题；多项式及其相加：多项式的类定义；多项式的加法 3)双向链表 4、栈和队列 1)栈：栈的抽象数据类型；栈的顺序存储表示；栈的链接存储表示 2)队列：队列的抽象数据类型；队列的顺序存储表示；队列的链接存储表示；3)队列的应用举例 4)优先级队列：优先级队列的定义；优先级队列的存储表示 5、递归 1)递归的概念 2)迷宫问题 3)递归过程与递归工作栈 4)利用栈实现的迷宫问题非递归解法 5)广义表：广义表的概念；广义表的表示及操作；广义表存储结构的实现；广6)义表的访问算法；广义表的递归算法 6、树与森林 1)树和森林的概念：树的定义；树的术语；树的抽象数据类型 谢谢分享一、单项选择题：1～40小题，每小题2分，共80分。 在每小题给出的四个选项中，请选出一项最符合题目要求的。 1.在下面的程序段中，时间复杂度为（）。 int fun( int n) { if( n = = 1 ) return 1; return n * fun( n - 1 ); } A．O( 2n ) B．0(nlogn) C．0(n2) D．O(n) 2.下列排序算法中，平均时间复杂度最小的是（）。 A．归并排序B．起泡排序C．简单选择排序D．直接插入排序 3.关于线性表的描述正确的是（）。 A. 采用顺序存储时，随机存取的时间复杂度是O(1) B. 采用链式存储时，随机存取的时间复杂度是O(1) C. 采用顺序存储时，其存储地址一定是不连续的 D. 采用链式存储时，其存储地址一定是不连续的 4.往队列中输入序列{1,2,3,4}，然后出队1个数字，则出队的数字是 （）。 A．4 B．3 C．1 D．不确定 5.往栈中输入序列{1,2,3,4}，然后出栈1个数字，则出栈的数字是 （）。 A．4 B．3 C．1 D．不确定 6.假设二叉排序（查找）树上有n个节点，树的高度为h，则查找的平均 时间复杂度是（）。 A．O( n ) B．0(nlogn) C．0(logn) D．O(h) 7.有10个节点的无向图，至少需要多少条边才能成为一个连通图 （）。 A．5 B．45 C．9 D．10 8.关于邻接矩阵，下列说法中错误的是（）。 A．有向图的邻接矩阵不一定是对称矩阵 B. 无向图的邻接矩阵不一定是对称矩阵 C．若图G的邻接矩阵是对称的，则G不一定是无向图 谢谢分享831-数据结构与操作系统
操作系统结构
数据结构,操作系统重要概念整理
操作系统结构
数据结构与操作系统 - 中国民航大学
苏州大学数据结构与操作系统
操作系统结构 (1)
2014年山东科技大学数据结构与操作系统真题.pdf
计算机操作系统体系结构实验报告
操作系统结构
数据结构与操作系统
(完整版)数据结构与操作系统
上海理工大学2017年《数据结构及操作系统》考试大纲
《数据结构与操作系统》试题.doc
相关主题
文本预览