831-数据结构与操作系统

2015-17试题涉及内容2015年第一部分，数据结构一、选择题三对角矩阵排序稳定性(前中后序线索树哪种)遍历需要用到栈n顶点连通无向图，边数最少多少排序题:希尔排序，快速排序哈希表可能冲突情况哪种图的邻接矩阵是对称矩阵(有向图无向图 AOV AOE)二、简答题1. 网的最小生成树哪两种方式? 以及区别 ? 为什么 ?2. 给一个序列，构造二叉排序树。

再构造二叉平衡树，讨论二叉排序树与二叉平衡树的区别。

3.给一个序列，建立堆。

三、算法题两个单链表是从小到大顺序排列的。

合成一个链表，从大到小。

第二部分，操作系统重点: 设备管理，索引文件系统四、选择题1. 3级索引文件系统，仅有文件控制信息，每次访问文件时访问磁盘几次?2.文件物理结构，不利于长度动态增长的物理结构是?3.段页式访问内存几次?4.系统调用I/O设备时，通常使用的设备标示符是什么5.程序与实际使用的物理设备无关，由什么实现?6.文件的相对路径，从什么开始?五、简答题1. 预防死锁和避免死锁的区别 ?2. p1 p2 p3 p4四个进程并发执行，用PV操作表示。

3. 文件系统物理结构采用索引文件，一级二级三级4 .I/O控制中断功能,1/O进程实现方式有哪三种？六、大题轮转法和多级反馈轮转法2016年第一部分，数据结构一、选择那种排序算法占用空间大算法的时间复杂度二、简答1.给出了树的中序和后序，构造一个森林，并画出来。

2.给一个链接矩阵，写出深度和广度遍历序列3.哈希表的链地址法三、算法题删除数组中等于item的元素，用时间复杂度低的方并求时间法。

复杂度低的方法。

第二部分，操作系统四、简答题1.什么是进程?进程与程序的区别?2.什么是临界区?临界区为什么不能交叉运行?请举例说明。

3.什么是死锁?画一个死锁图，死锁产生的条件。

4.为什么使用缓冲?缓冲有哪几种?五、大题短进程优先和高响应比算法两个生产者一个消费者2017数据结构一、选择题1.N个节点，K条边。

远程教育网 ｗｗｗ．１９ｐｉｎｇ．ｃｏｍ831华南理工大学2008年攻读硕士学位研究生入学考试试卷（请在答题纸上做答，试卷上做答无效，试后本卷必须与答题纸一同交回）科目名称：计算机专业综合(数据结构、操作系统)适用专业：系统分析与集成，计算机系统结构，计算机软件与理论，计算机应用技术，生物医学工程共 5 页数据结构部分一． 选择题（每题只有一个答案正确，每题2分，共24分）1．带头结点的单链表head为空的判断条件是( )A．head= =NULL B．head—＞next= =NULLC．head—＞next= =head D．head!=NULL2．若进栈序列为a，b，c，则通过入、出栈操作可能得到的a，b，c的不同排列数是( )。

A．4 B．5 C．6 D．73．下列说法正确的是( )。

A．二叉树中任何一个结点的度都为2B．二叉树的度为2C．一棵二叉树的度可小于2D．任何一棵二叉树中至少有一个结点的度为24．一棵有124个叶子结点的完全二叉树，最多有( )个结点。

A．247 B． 124 C．248 D． 1255．以下说法错误的是( )。

A．存在这样的二叉树，对其采用任何次序的遍历其结点访问序列均相同。

B．二叉树是树的特殊情形。

C．由树转换成二叉树，其根结点的右子树总是空的。

D 在二又树只有一棵子树的情况下，也要指出是左子树还是右子树6．有拓扑排序的图—定是( )。

A 有环图B．无向图C．强连通图D．有向无环图7．在待排序的元素序列基本有序的前提下，效率最高的排序方法是( )。

A．插入排序B．选择排序C．快速排序D．归并排序8．从逻缉上可以把数据结构分为（）。

A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．内部结构和外部结构9．下面程序的时间复杂度为( )．for 〔i=0；i＜m；i++)for (j=0：j＜n；j++)A[i][j]＝i*j；22A．O(m) B．O(n) C．O(m×n) D．O(m+n)10. 三维数组A[4][5][6]按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素A[0][0][0]的存储地址为120，则元素A[3][4][5]存储地址为( )。

828《数据结构与操作系统》考试大纲一、考试的基本要求要求考生比较系统地理解数据结构的基本概念和基础知识，从逻辑结构、存储结构和数据操作（算法）等三个方面掌握线性表、树、图等常用的数据结构；掌握在各种常用数据结构上实现高效的查找和排序算法；能够正确分析算法的时间和空间复杂性；能够针对较复杂的应用问题，选择合适的数据结构，并设计有效的算法。

要求考生比较系统地掌握操作系统各要素的基本概念、基本原理和方法，对操作系统如何管理和控制计算机系统的所有硬件和软件资源以达到方便用户、提高资源的使用效率有较深入的了解。

要求考生具有较强的抽象思维能力、逻辑推理能力、软件设计和实现能力以及综合运用所学的知识分析问题和解决问题的能力。

二、考试方式和考试时间考试方式为闭卷考试，试卷总分为150分（其中，数据结构90分，操作系统60分），考试时间为3小时。

三、参考书目（仅供参考）《数据结构与算法》（第四版），廖明宏，郭福顺，张岩，李秀坤，高等教育出版社，2007年《计算机操作系统》(第三版)，汤小丹，梁红兵，哲凤屏，汤子瀛，西安电子科技大学出版社，2007年四、试题类型：主要包括编程题、计算题、综合题等类型，并根据每年的考试要求做相应调整。

五、考试内容及要求第一部分数据结构-线性表掌握：线性表的逻辑结构、存储结构及描述方式；顺序表的定义、插入、删除；单链表、双向链表和循环链表的定义、插入、删除；顺序栈、链栈的表示、入栈和出栈操作；顺序队列、链队列的表示、入队和出队操作；循环队列的队空和队满的判断；串的定义、逻辑结构和存储结构，串的KMP模式匹配算法；广义表的定义；矩阵的压缩存储的概念以及有关计算方法；稀疏矩阵的三元组表示方法。

熟悉：线性结构的定义和特点；顺序表和单链表的组织方法、特点、算法和性能分析；单链表、双向链表和循环链表之间的区别；栈和队列的定义；栈和队的特点；顺序栈和链栈上基本运算的实现和简单算法设计；链队上基本运算的实现和简单算法设计；串的基本运算，串的传统匹配方法；多维数组的定义以及逻辑结构；广义表的链表表示和算法；特殊矩阵的非零元下标与数组下标的对应关系。

河海838考研大纲
河海大学计算机自命题考试大纲（科目代码：838，科目名称：数据结构及程序设计）的考试内容主要包括以下部分：
1. 线性表：线性表的定义、逻辑结构、存储结构；线性表的顺序表示、链式表示；顺序表和链表的插入和删除等操作。

2. 栈和队列：栈的定义、栈的顺序表示和链式表示、顺序栈、链栈的入栈和出栈操作；队列的定义、队列的顺序表示和链式表示、顺序队列、链队列的入队和出队操作；循环队列的队空和队满的判断。

3. 串：串类型的定义、串的表示和实现、串的模式匹配算法、模式匹配的一种改进算法（KMP 方法)。

4. 数组和广义表：数组的定义、数组的顺序表示和实现；广义表的定义、存储结构。

5. 树和二叉树：树的定义和基本术语；二叉树的定义、性质、存储结构；遍历二叉树、线索二叉树；树的存储结构、森林与二叉树的转换、树和森林的遍历；最优二叉树（赫夫曼树）、赫夫曼编码。

以上信息仅供参考，具体考试内容请以河海大学发布的官方信息为准。

831华南理工大学2008年攻读硕士学位研究生入学考试试卷（请在答题纸上做答，试卷上做答无效，试后本卷必须与答题纸一同交回）科目名称：计算机专业综合(数据结构、操作系统)适用专业：系统分析与集成，计算机系统结构，计算机软件与理论，计算机应用技术，生物医学工程共 5 页数据结构部分一． 选择题（每题只有一个答案正确，每题2分，共24分）1．带头结点的单链表head 为空的判断条件是( )A ．head= =NULLB ．head —＞next= =NULLC ．head —＞next==head D ．head!=NULL 2．若进栈序列为a ，b ，c ，则通过入、出栈操作可能得到的a ，b ，c 的不同排列数是( )。

A ．4B ．5C ．6D ．7 3．下列说法正确的是( )。

A ．二叉树中任何一个结点的度都为2B ．二叉树的度为2C ．一棵二叉树的度可小于2D ．任何一棵二叉树中至少有一个结点的度为24．一棵有124个叶子结点的完全二叉树，最多有( )个结点。

A ．247 B ． 124 C ．248 D ． 1255．以下说法错误的是( )。

A ．存在这样的二叉树，对其采用任何次序的遍历其结点访问序列均相同。

B ．二叉树是树的特殊情形。

C ．由树转换成二叉树，其根结点的右子树总是空的。

D 在二又树只有一棵子树的情况下，也要指出是左子树还是右子树 6．有拓扑排序的图—定是( )。

A 有环图B ．无向图C ．强连通图D ．有向无环图供学习参考Q7．在待排序的元素序列基本有序的前提下，效率最高的排序方法是( )。

A ．插入排序 B ．选择排序 C ．快速排序 D ．归并排序8．从逻缉上可以把数据结构分为（ ）。

A ．动态结构和静态结构 B ．紧凑结构和非紧凑结构 C ．线性结构和非线性结构 D ．内部结构和外部结构9．下面程序的时间复杂度为( )． for 〔i=0；i ＜m ；i++)for (j=0：j ＜n ；j++) A[i][j]＝i*j ；A ．O(m )B ．O(n )C ．O(m ×n)D ．O(m+n)2210. 三维数组A[4][5][6]按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素A[0][0][0]的存储地址为120，则元素A[3][4][5]存储地址为( )。

2016年山东科技大学__831数据结构与操作系统_考研专业课真题／研究生入学考试试题数据结构部分一、简答题（共30分，每题5分）1、试举一个数据结构的实例，说明其逻辑结构和存储结构两个层次的含义及其相互关系。

2、简述以下三个概念的区别：头指针、头结点、表头结点。

3、在单循环链表中设置尾指针比设置头指针好吗？为什么?4、设输入序列为a,b,c,d,试写出借助一个栈可得到的两个输出序列和两个不能得到的输出序列。

5、什么是递归程序？递归程序的优、缺点是什么？递归程序在执行时，应借助于何种数据结构来完成？6、简要叙述循环队列的数据结构，并写出其初始状态、队列空、队列满时的队首指针与队尾指针的值。

二、应用题（共40分，每题10分）1、设一棵二叉树的先序、中序遍历序列分别为：ABDFCEGH及BFDAGEHC，完成以下问题：（1）画出这棵二叉树；（2）画出这棵二叉树的后序线索树；（3）将这棵二叉树转换成对应的树（或森林）。

2、已知待排序的序列为（503，87，512，61，908，170，897，275，653，462），试完成下列各题：（1）根据以上序列建立一个堆，画出第一步和最后堆的结果图，要求先输出最小值。

（2）输出最小值后，如何得到次小值，并画出相应结果图。

3、设哈希(Hash)表的地址范围为0～17，哈希函数为：H(K)=K MOD16,K为关键字，用线性探测再散列法处理冲突，输入关键字序列(10,24,32,17,31,30,46,47,40,63,49) 构造哈希表，试回答下列问题：（1）画出哈希表示意图；（2）若查找关键字63，需要依次与哪些关键字比较?（3）若查找关键字60，需要依次与哪些关键字比较?（4）假定每个关键字的查找概率相等，求查找成功时的平均查找长度。

4、已知一个图的顶点集V={1,2,3,4,5,6,7}，共有10条边，该图用如下边集数组存储：起点 1 2 2 5 5 2 2 6 1 3终点 6 4 5 4 7 6 7 7 7 5权 1 1 2 2 2 3 3 4 5 7 试用克鲁斯卡尔算法依次求出该图的最小生成树中所得到的各条边及权值。

《数据结构与操作系统》考试大纲一、考查目标数据结构和操作系统是计算机类专业的核心课程。

《数据结构和操作系统》科目考察的内容包括《数据结构》和《操作系统》的基本内容，要求考生掌握相关的概念、方法和技术，并具备较强的程序设计能力，能够灵活应用相关的方法和技术解决实际问题。

二、考试形式与试卷结构（一）试卷成绩及考试时间本试卷满分为150分，考试时间为180分钟。

（二）答题方式答题方式为闭卷、笔试。

（三）试卷内容结构各部分内容所占分值为：数据结构 75分操作系统 75分（四）试卷题型结构1．数据结构选择题：15小题，每小题2分，共30分简答题：3小题，每小题10分，共30分算法题：1小题，每小题 15分，共15分2.操作系统三、考查范围数据结构一、考查目标1、掌握数据结构的基本概念、方法和技术。

2、掌握程序设计的基本方法和技巧。

3、能够应用相关知识解决一些有实际背景的问题。

二、考查内容1. 绪论数据结构的概念；基本概念与术语；算法的概念，算法的特性，以及算法设计的要求，算法效率的度量。

2. 线性表线性表相关的基本概念和结构特点；线性表的顺序存储方式以及两种不同的实现方法：表空间的静态分配和动态分配；线性表的链式存储方式的实现；链表与顺序表的相似及不同之处，优缺点比较，各自适用的场合；线性表的各种实现方式能够实现指定的操作。

3.栈和队栈、队列的定义及其相关数据结构的概念，包括：顺序栈，链栈，共享栈，循环队列，链队列等；栈与队列插入删除操作的特点；栈和递归的关系；栈和队列各种实现方式。

4. 串串的基本概念，朴素的模式匹配算法。

5.数组数组的定义；数组的存储，行序和列序；特殊矩阵的定义；特殊矩阵的压缩存储。

6.树和二叉树二叉树的概念；二叉树的五个性质；二叉树的存储结构：顺序存储和二叉链表存储的各自优缺点及适用场合；二叉树的三种遍历方法：先序，中序和后序；线索二叉树，线索化后二叉树的遍历方法；哈夫曼树概念，哈夫曼树的构造方法，前缀码概念，哈夫曼编码。