山东科技大学2019年《823数据结构与操作系统》考研专业课真题试卷

数据结构部分一、简答题（共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 试用克鲁斯卡尔算法依次求出该图的最小生成树中所得到的各条边及权值。

山东科技大学
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个字符设计哈夫曼编码；
②试设计另一种由二进制表示的等长编码方案；。

山东科技大学2012—2013学年第二学期《操作系统》考试试卷（A卷）班级姓名学号一、单项选择题（每小题2分，共20分）1、现代OS具有并发性和共享性，是由（）的引入而导致的。

A．单道程序B．多道程序C．对象D．磁盘2、在进程状态转换时，下列( )转换是不可能发生的。

A．就绪态→运行态B．运行态→就绪态C．运行态→阻塞态D．阻塞态→运行态3、从资源管理的角度看，进程调度属于( )。

A．I/O管理B．文件管理C．处理机管理D．存储器管理4、下面关于线程的叙述中，正确的是( )。

A．在引入线程的系统中，进程仍是资源分配和调度分派的基本单位B．线程是资源的分配单位，进程是调度和分配的单位C．不管系统中是否有线程，进程都是拥有资源的独立单位D．不论是系统支持线程还是用户级线程，其切换都需要内核的支持5、临界资源是（）的资源。

A．非共享B．任意共享C．互斥共享D．同时共享6、在采用动态优先权的优先权调度算法中，如果所有进程都具有相同优先权初值，则此时的优先权调度算法实际上和（）相同。

A．先来先服务调度算法B．短作业优先调度算法C．时间片轮转调度算法D．长作业优先调度算法7、把逻辑地址转换程物理地址称为（）。

A．地址分配B．地址映射C．地址保护D．地址越界8、在内存分配的"最佳适应法"中，空闲块是按（）。

A．始地址从小到大排序B．始地址从大到小排序C．块的大小从小到大排序D．块的大小从大到小排序9、设主存容量为1MB，辅存容量为400MB，计算机系统的地址寄存器有24位，那么虚存的最大容量是（）。

A．1MB B．401MB C．1MB+224B D．224B10、从下面描述中正确的一条描述是（）。

A．顺序文件必须采用连续分配方式，而链接文件和索引文件则可采用离散分配方式。

B．显式链接文件将分配给文件的下一个盘块的地址登记在该文件的前一个物理盘块中。

C．顺序文件适合于建立在顺序存储设备上，而不适合建立在磁盘上。

山东科技大学2019年期末考试试题单项选择题（每题1分，共20分）1．操作系统的发展过程是( C )A、原始操作系统，管理程序，操作系统B、原始操作系统，操作系统，管理程序C、管理程序，原始操作系统，操作系统D、管理程序，操作系统，原始操作系统2．用户程序中的输入、输出操作实际上是由( B )完成。

A、程序设计语言B、操作系统C、编译系统D、标准库程序3．进程调度的对象和任务分别是( C )。

A、作业，从就绪队列中按一定的调度策略选择一个进程占用CPUB、进程，从后备作业队列中按调度策略选择一个作业占用CPUC、进程，从就绪队列中按一定的调度策略选择一个进程占用CPUD、作业，从后备作业队列中调度策略选择一个作业占用CPU4．支持程序浮动的地址转换机制是( A、动态重定位 )A、动态重定位B、段式地址转换C、页式地址转换D、静态重定位5．在可变分区存储管理中，最优适应分配算法要求对空闲区表项按( C )进行排列。

A、地址从大到小B、地址从小到大C、尺寸从小到大D、尺寸从大到小6．设计批处理多道系统时，首先要考虑的是( 系统效率和吞吐量 )。

A、灵活性和可适应性B、系统效率和吞吐量C、交互性和响应时间D、实时性和可靠性7．当进程因时间片用完而让出处理机时，该进程应转变为( )状态。

A、等待B、就绪C、运行D、完成8．文件的保密是指防止文件被( )。

A、篡改B、破坏C、窃取D、删除9．若系统中有五个并发进程涉及某个相同的变量A，则变量A的相关临界区是由( )临界区构成。

A、2个B、3个C、4个D、5个10．按逻辑结构划分，文件主要有两类：（记录式文件）和流式文件。

A、记录式文件B、网状文件C、索引文件D、流式文件11．UNIX中的文件系统采用（、流式文件）。

A、网状文件B、记录式文件C、索引文件D、流式文件12．文件系统的主要目的是（）。

A、实现对文件的按名存取B、实现虚拟存贮器C、提高外围设备的输入输出速度D、用于存贮系统文档13．文件系统中用（）管理文件。

数据结构部分
一、选择题（每题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。