下载文档原格式
山东科技大学
2018年硕士研究生入学考试试题
考试科目：数据结构与操作系统 科目代码：823
《数据结构》部分
一、简答题（30分，每题5分）
1、串、数组、广义表从元素间关系上可以看成线性结构，它们与
一般意义上的线性表相比有何特殊性？
2、借助栈可以实现更复杂的操作，请简述如何利用栈实现对表达
式中括号是否匹配的检验。
3、基于关键字比较的查找算法所能达到最优时间复杂度是？能否
设计一种与问题规模无关的查找算法？请给出基本思路。
4、图的广度优先遍历与树的何种遍历策略相似？请给出简单解释。
5、《数据结构》中经常采用“树形化组织”的方式来整理数据，
比如折半查找表、二叉排序树、大顶堆/小顶堆等，请简述这样
做的优点。
6、何为稳定的排序方法？何为不稳定的排序方法？哪些排序算法
是不稳定的？
二、综合应用题（40分，每题10分）
1、假设用于通信的电文共有8个字母A,B,C,D,E,F,G,H组成，字
母在电文中出现的频率分别是{0.2，0.04，0.06，0.02，0.12，
0.24，0.25，0.07}。
①试为这8个字符设计哈夫曼编码；
②试设计另一种由二进制表示的等长编码方案；。
苏州大学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/次)，同问。
一、单项选择题1. 下列对顺序存储的有序表（长度为n）实现给定操作的算法中平均时间复杂度为O(1)的是（）。
A、查找包含指定值元素的值B、插入包含指定值元素的算法C、删除第i(1≤i≤n)个元素的算法D、获取第i(1≤i≤n)个值的算法2、现有非空双向链表L，其结点结构为，prev是指向直接前驱结点的指针，next是指向直接后继结点的指针。
若要在L中指针p 所指向的结点（非尾结点）之后插入指针s指向的新结点，则在执行了语句序列：“s->next=p->next;p->next=s;”，后，还要执行（）。
A、s->next->prev=p;s->prev=p;B、p->next->prev=s;s->prev=p;C、s->prev=s->next->prev; s->next->prev=s;D、p->next->prev=s->prev;s->next->prev=p;3、若采用三元组表存储结构存储稀疏矩阵M，则除三元组外，下列数据中还需要保存的是（）。
I. M的行数；II.M中包含非零元素的行数；III.M的列数；IV.M中包含非零元素的列数。
A、仅I、IIIB、仅I、IIC、仅III、IVD、I、II、III、IV4、在由6个字符组成的字符集S中，各个字符出现的频次分别为3，4，5，6，8，10，为S构造的哈夫曼树的加权平均长度为（）。
A、2.4B、2.5C、2.67D、2.75注：每个关键字的查找长度为：图片加权平均长度为：(3×3+3×4+3×5+3×6+2×8+2×10)/(3+4+5+6+8+10)=2.5。
如果不考虑权重，会错误计算为(3+3+3+3+2+2)/6≈2.67，从而误选C。
5、已知一棵二叉树的树形如下图所示，若其后序遍历为fdbeca，则其先序列为（）。
数据结构考研真题及其答案完整版数据结构是计算机科学与技术领域中的一门重要课程，也是计算机考研中必考的一门科目。
通过研究数据结构，可以帮助我们更好地理解和应用计算机算法，提高计算机程序的效率和性能。
为了帮助考生更好地备考数据结构，本文将分享一些数据结构考研真题及其答案，供考生参考。
一、选择题1. 下列关于栈的叙述中，错误的是（）A. 栈是一种线性数据结构，具有后进先出（LIFO）的特点B. 栈可以用数组实现，也可以用链表实现C. 栈的插入和删除操作都是在同一端进行的D. 栈的插入和删除操作的时间复杂度都是O(1)答案：C解析：栈的插入操作叫做入栈，删除操作叫做出栈。
入栈和出栈操作都是在栈顶进行的，而不是同一端。
2. 假设要对n个整数关键字进行排序，以下排序算法中，平均时间复杂度最小的是（）A. 冒泡排序B. 快速排序C. 归并排序D. 直接插入排序答案：C解析：归并排序的时间复杂度是O(nlogn)，平均时间复杂度最小。
二、填空题1. 下列关于图的遍历顺序的说法中，正确的是：深度优先搜索访问的顺序是________，广度优先搜索访问的顺序是________。
答案：前序遍历，层次遍历解析：深度优先搜索即前序遍历，广度优先搜索即层次遍历。
2. 给定一个最小堆，若删除堆顶元素后，需要对堆进行调整，所采用的操作是________。
答案：下滤解析：删除堆顶元素后，将最后一个叶子节点放到堆顶，然后进行下滤操作。
三、简答题1. 请简要说明动态规划算法的基本思想和应用场景。
答：动态规划算法的基本思想是将问题分解为多个子问题，通过求解子问题的最优解来得到原问题的最优解。
它通常适用于具有重叠子问题和最优子结构性质的问题。
动态规划算法可以大大减少问题的重复计算，提高算法的效率和性能。
它在求解最短路径、最长公共子序列、背包问题等具有广泛的应用。
2. 请简要介绍红黑树的特点和应用场景。
答：红黑树是一种自平衡的二叉查找树，它具有以下特点：1) 每个节点都有一个颜色，红色或黑色；2) 根节点是黑色的；3) 叶子节点（NIL节点）都是黑色的；4) 如果一个节点是红色的，则它的两个子节点都是黑色的；5) 从根节点到叶子节点的路径上，不同路径上黑节点的个数相同。
中国计量大学
2020年硕士研究生招生考试试题
考试科目代码：806考试科目名称：数据结构与操作系统所有答案必须写在报考点提供的答题纸上，答在试卷或草稿纸上无效。
一、单项选择题（共30题，每小题2分，共60分）
1.关于下面两个程序段，描述正确的是（ ）。
程序段1：
double fun1(int n)
{ if( n = = 1 )
return 1;
return n * fun( n - 1 );
}
程序段2：
double fun2(int n)
{ double s = 1;
for(int i=2; i<=n; i++)
s *= i;
return s;
}
A.两个程序段的时间复杂度相同 B．fun1的时间复杂度小于fun2
C．fun1的时间复杂度大于fun2 D．fun1的实际运行时间小于fun2
2.对一个已经有序的数据序列进行排序操作，下面的描述正确的是（ ）。
A.快速排序的时间复杂度是O(N)
B. 归并排序的时间复杂度是O(N)
C．选择排序的时间复杂度是O(N) D.插入排序的时间复杂度是O(N)
3.对于只在表的一端进行删除和插入操作的线性表，宜采用的存储结构为（ ）。
A. 队列
B. 顺序表
C. 栈
D. 双向链表
《数据结构与操作系统》试卷第1页共9 页。
山东科技大学2007年招收硕士学位研究生入学考试
数据结构与操作系统试卷
数据结构部分
注意事项：
1、算法应说明基本思路，应对主要数据类型、
变量给出说明，所写算法应结构清晰、简明易懂，
应加上必要的注释。
2、算法可用（类）PASCAL语言、（类）C语言等你
所熟悉的高级语言编写，但要注明语种。
一、解答下列问题[每小题4分，共16分]：
1、[4分]为什么要分析算法的时间复杂度？
2、[4分]简述代码区、全局数据区、栈区、堆区
在程序运行时的作用。
3、[4分]求模式串s＝’aaaabc’的next及nextval
函数。
4、[4分]证明根据森林的先序序列与中序序列
可以唯一确定一个森林。
二、综合应用题[每小题8分，共24分]：
1、[8分]推导满k叉树上的叶子结点数n0和非
叶子结点数n1之间的关系（即用k和n1表示n
0）。
数据结构部分
一、选择题（每题2分，共20分）
1、将线性表La和Lb头尾连接，要求时间复杂度为O(1)，且占用辅助空间尽量小，
应该使用哪种结构？()
A.单链表
B.单循环链表
C.带尾指针的单循环链表
D.带头结点的双循环链表
2、在一个链队列中，front和rear分别为头指针和尾指针，则插入一个结点s的操作
为（）。
A.front=front->next
B.s->next=rear;rear=s
C.rear->next=s;rear=s;
D.s->next=front;front=s;
3、设一个堆栈的入栈顺序是1、2、3、
4、5。
若第一个出栈的元素是4，则最后一个
出栈的元素必定是：()
A.1
B.3
C.5
D.1或者5
4、由分别带权为9、2、
5、7的四个叶子结点构成一棵哈夫曼树，该树的带权路径长
度为：()
A.23
B.37
C.44
D.46
5、如果AVL树的深度为5（空树的深度定义为0），则此树最少有多少个结点？()
A.12
B.20
C.33
D.64。
中国计量大学
2019年硕士研究生招生考试试题
考试科目代码：806 考试科目名称：数据结构与操作系统所有答案必须写在报考点提供的答题纸上，做在试卷或草稿纸上无效。
一、 单项选择题：1～30小题，每小题2分，共60分。
1.以下T(n)表示各算法中最耗时操作的执行次数，n表示数据量，请按照时间复
杂度从小到大排列，正确的是（）。
T1(n) = 100n + 200log
n
2
T2(n) = 3n2
T3(n) = 10000000
n
T4(n) = 300log
2
A.T1<T2<T3<T4 B．T2<T1<T4<T3
C．T3<T4<T1<T2 D．T3<T1<T4<T2
2.在一个无序数据序列上进行查找，分别采用以下算法，速度最快的是（ ）。
A．折半查找 B．顺序查找 C．二叉排序树查找 D．哈希表查找
3.下列关于线性表的描述，错误的是（ ）。
A.顺序表不能进行插入操作
B.顺序表可以进行插入操作
C.顺序表适宜于随机存取
D.链表适宜于顺序存取
4.往队列中依次输入序列{1,2,3,4}，经过若干入队与出队操作，队列中剩下的数
据可能是（ ）。
A．1 B．2 C．3 D．4
《数据结构与操作系统》试卷第1页共9 页。
燕山大学操作系统与数据结构历年考研真题答案附后最新资料，WORD格式，可编辑修改！目录说明：精选了16套名校操作系统历年考研真题1．燕山大学操作系统与数据结构历年考研真题2015年燕山大学810操作系统与数据结构考研真题2．中国计量学院数据结构与操作系统历年考研真题2015年中国计量学院806数据结构与操作系统考研真题3．广东工业大学操作系统历年考研真题2014年广东工业大学830操作系统考研真题2013年广东工业大学830操作系统考研真题4．沈阳航空航天大学操作系统历年考研真题2014年沈阳航空航天大学811操作系统考研真题2013年沈阳航空航天大学811操作系统考研真题5．沈阳工业大学计算机操作系统历年考研真题2014年沈阳工业大学837计算机操作系统考研真题6．山东科技大学数据结构与操作系统历年考研真题2014年山东科技大学830数据结构与操作系统考研真题2012年山东科技大学838数据结构与操作系统考研真题《数据结构》部分一、简答题（15分，每题5分）1．什么是原地工作？2．什么是完全二叉树？3．什么是稳定的排序方法？二、应用题（45分）1．设有一个顺序栈S，元素s1, s2, s3, s4, s5, s6依次进栈，如果6个元素的出栈顺序为s2, s3, s4, s6, s5, s1，则顺序栈的容量至少应为多少？画出具体进栈、出栈过程。
（10分）2．给定一棵二叉树如右图所示（1）写出该树的前序、中序、后序遍历结果；（2）画出该二叉树的中序线索树；（3）将它转换成等价的树或森林。
（15分）3．已知一个无向图如下图所示，要求用Kruskal算法生成最小树，试画出构造过程。
（10分）4．某整形数组A的数组元素分别是6，2，9，7，3，8，4，5，0，试用下例各排序方法将A中元素由小到大排序。
（10分）(1)用第一元素中的值6作为枢轴，试写出快速排序第一次分割后A中的结果。
(2)A中的元素是否为堆，如果不是，请将其调整为堆，写出将A 调整成堆后A中的结果。
《数据结构》部分
一、简答题（20分，每题5分）
1、什么是最优二叉树（Huffman 树）？
2、什么是哈希表？
3、什么是稳定的排序方法？
4、什么是AOE网中的关键路径？
二、应用题（45分）
1、给出使用两个栈模拟一个队列最高效的算法思想（只需使用图和必要的文字描述）。
（15分）
2、已知一个无向图如下图所示，要求用Kruskal算法生成最小树，试画出构造过程。
（10分）
3.一组关键字集合为(25，10，8，27，32，68)，设哈希函数H(k)=k mod 7，分别用线性探测和链地址法作解决冲突的方法构造长度为8的哈希表，要求画出具体的哈希表并求查找成功且等概率情况下各自的平均查找长度。
（10分）
4、画出向小顶堆中加入数据4, 2, 5, 8, 3, 6, 10, 1时，每加入一个数据后堆的变化。
（10分）
三、算法设计题（25分)
答题要求：
①用自然语言说明所采用算法的思想；②给出每个算法所需的数据结构定义，并做必要说明；③用C语言写出对应的算法程序，并做必要的注释。
1、已知一个带有表头结点的单链表，结点结构为 data link ,假设该链表只给出了头指针list。
在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点。
若查找成功，算法输出该结点的data域值，并返回1；否则只返回0。
（15分）
2、设计一个算法，判断无向图G是否连通。
若连通则返回1；否则返回0。
（10分）。
《数据结构》与操作系统考研历年考研真题南京航空航天大学南京航空航天大学计算机科学与技术学院922数据结构与操作系统（专业学位）考研真题试懸対：922 共3页第1页南京航空航天大学二O—O年硕士研究生入学考试试题考试科目：数拯结构（专业学位）说明：答案--律写在答麵妖上,筍崔试卷上无效一、单项选择题（共30分，15题，每题2分）1.一个算法具冇以下5个重要特性・（）A.有穷性、确定性、可行性、输入、输出B.可行性、可移植性、可扩充性、鹽入、输岀C确定性、有穷性、稳定性、输入、辙出D.易樓性' 稳定性、安全性、输入' 输出2.若长度为】】的线性表采用顺序存储结构，在其笫i个位置播入一个新■元素的算法的眄间复杂度为（）（1<"<=时1）・A. 0（0）B. 0（1）C. 0（n）D. 0（n2）3.—个栈的输入序列为L, 2, 3..., n,若输击序列的第一个元素是n,输出第i （ l<=i<=n）个元素是（）.A.不确定B. n-iC. iD. n-i+14.镭环队列A[0..m-l]存放其元素置，用front和rcai•分别麦示队头和队尾，当前队列的长度是（）。
A・ rear-front+1 B. rear-fronl C. （ rear-f ronl+ni） II （ rear-f ronl） %m5.数组A[1..5,1..6]的每个无素占4个字节，将其按行优先次序存储在起始地址为1000的内存单元申，则元素A[4, 4]的地址是（）.A. 1175 B, 1180 C. 1088 D, 10846.巳知一棵二叉树的先序遍历为A BCDEF,中序遍历为CBAEDF,则后序遍历为（）,A. CBEDFAB. FEDCBA C・ CBEFDA D.不定7.—棵具有H个结点的完全二叉樋的桥高度（除度）是（）A・ LlogziiJ B・ Log：n+1 C・ Llog2nJ +1 D. log：n-l8 .若一探二叉树具有15个度.为2的结点，10个度为1的结点，则度为0的结点个数是（）.A. 16B. 25C. 40D.不确定9. 一棵完全二叉树上有2001个结点，其中叶子结点的个数是（）・A. 500B. 501 U LOGO I）. 10011 5. Floyd 算法是用来求解（人.拓扑排序B.关健珞径C.某点到其余顶点间最短距离二、解答题（共分，8题，每题10分）16•应用栈换作求解翼术表达式：（1424/4）73+9）,画出栈的变化过程。
一、数据结构部分1、选择题（1）一个运算次数为n*n+nlog2n+n+1的程序时间复杂度为多少A.O(n*n)B.O(nlog2n)C.O(n)D.O(1)（2）下列哪个算法适合求稀疏图的最小生成树A.PrimB.KruskalC.DijkstraD.Floyd（3）.......2、判断题(5个）（1）栈和队列是双端队列的特殊情况（2）树的子结点可以有任意多个，二叉树的孩子节点至多有两个，所有二叉树是树的特殊情况（3）一个带有头结点的单链表，结点数据类型为整形（1）编写算法将结点元素为负整数的放到链表前面，将结点元素为正整数的放到链表后面（2）对于上述问题用何种物理结构实现较好（4）对于一颗二叉树，打印从根节点到先序遍历下最后一个节点的路径（5）图用邻接表实现，打印从顶点i 到顶点j 的所有简单路径二、操作系统部分一、判断题(5个）（1）最早的gui 界面是在window 系统上二、操作计算题1. 一个可抢占的动态优先级调度算法，优先数大的优先级高（1）等待状态下，进程优先级以a 速度变化（2）运行状态下，进程优先级以b 速度变化2. 进程优先级变化不同，会成为不同的调度算法问：（1）a>b>0 时是什么调度算法（2）a< b< 0 时是什么调度算法3. 一个含有一百万条记录的文件，每个文件16kb 到到32kb 不等，每个物理块4kb（1）如何设计文件目录，目录文件如何实现（2）（3）设计文件的物理结构（4）基于上述设计，访问某个文件的某个字节信息，最多访问几次磁盘，最少访问几次4. 磁盘16 年第七题原题有一个计算机的虚存系统采用请求式分页机制。
其中，从内存读/写-个单元需要花费100ms。
该虚存系统由内存和硬盘组成，硬盘具有以下参数:转速7200RPM,磁盘块大小4KB,平均寻道时间5ms,传输率16b/s,控制开销为0.1ms。
请回答以下问题:(1) 假如缺页率为0,则该虚存系统的有效访问时间是多少?(2) 从硬盘读入或写出一个磁盘块的平均时间是多少?(3)如果缺页率为1%，缺页时页面被修改的比例是20%，不考虑缺页时的系统开销，则该虚存系统的有效访问时间是多少?5. 2016pv 操作题稍作修改:有四个进程S1、S2、R1 和R2，其中S1、S2 向缓冲区BUFF 发送消息，R1 和R2 从缓冲区BUFF 接收消息。
