山东科技大学823数据结构与操作系统2004—2018考研专业课真题试卷

42920041040123453Q1=0.25Q2=0.10Q3=0.15Q4=0.20,Q5=0.30F1=35F2=20F3=16F4=18F5=5202525120401224162005225110215153013K1={x1,x3}, K2={x2,x3}, K3={x3,x4}q1=0.01, q2=0.02, q3=0.03, q4=0.0424000830022018060003052.552.52012525501222006417(1210341550) 1234(1530)13K1={x1,x4}K2={x2,x4,x5}K3={x1,x5}q1=0.5q2=0.6q4=0.8q5=0.9240002160127FAFR201251 252007(12341051555)12345(1530)1300CL UCL LCL1 2 3 4 5 6 72317 15 15 0 41 318 9 10 11 1225 29 0 8 1624K1={x1,x2}K2={x1,x3}K3={ x4,x5, x6} K4={x4,x5,x7,x8}20q1=0.01, q2=0.8, q3=1.0, q4=0.5, q5=0.05, q6=0. 05,q7=0.0111021035 202008(12310451560) 12345(15)A B,,R A=0.99R B=0.98,(2550)1211234(25)12009(540)123HAZOP4PHA567FMEA KYT FMECA SCL ETA8(11522540)13K1={x1,x4}K2={x2,x4,x5}K3={x1,x5}q1=0.5q2=0.6q4=0.8q5=0.921041061031031022020 302011年研究生入学考试安全系统工程试题一、简答题(每小题6分，共30分)1．建立安全评价指标体系的原则是什么？2．什么是FMEA？它是如何分析的？3．如何制作鱼刺图？4．何为因果分析？说明其分析步骤。

2021年山东科技大学数据结构与操作系统--真题及参考答案数据结构与操作系统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 (可以参考下面这个题：【￥】铁路进行列车调度时，常把站台设计成栈式结构，若进站的六辆列车顺序为：1，2，3，4，5，6，那么是否能够得到435612， 325641， 154623和135426的出站序列，如果不能，说明为什么不能；如果能，说明如何得到(即写出\进栈\或\出栈\的序列)。

【解答】输入序列为123456，不能得出435612和154623。

不能得到435612的理由是，输出序列最后两元素是12，前面4个元素（4356）得到后，栈中元素剩12，且2在栈顶，不可能让栈底元素1在栈顶元素2之前出栈。

不能得到154623的理由类似，当栈中元素只剩23，且3在栈顶，2不可能先于3出栈。

得到325641的过程如下：1 2 3顺序入栈，32出栈，得到部分输出序列32；然后45入栈，5出栈，部分输出序列变为325；接着6入栈并退栈，部分输出序列变为3256；最后41退栈，得最终结果325641。

2012年山东科技大学数据结构与操作系统--真题及参考答案数据结构与操作系统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(可以参考下面这个题：【￥】铁路进行列车调度时，常把站台设计成栈式结构，若进站的六辆列车顺序为：1，2，3，4，5，6，那么是否能够得到435612，325641，154623和135426的出站序列，如果不能，说明为什么不能；如果能，说明如何得到(即写出"进栈"或"出栈"的序列)。

【解答】输入序列为123456，不能得出435612和154623。

不能得到435612的理由是，输出序列最后两元素是12，前面4个元素（4356）得到后，栈中元素剩12，且2在栈顶，不可能让栈底元素1在栈顶元素2之前出栈。

不能得到154623的理由类似，当栈中元素只剩23，且3在栈顶，2不可能先于3出栈。

得到325641的过程如下：123顺序入栈，32出栈，得到部分输出序列32；然后45入栈，5出栈，部分输出序列变为325；接着6入栈并退栈，部分输出序列变为3256；最后41退栈，得最终结果325641。

山东科技大学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。

山东科技大学——十套数据结构试题及答案数据结构试卷（一）1. 栈和队列的共同特点是( )。

A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2. 用链接方式存储的队列，在进行插入运算时( ).A. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改3. 以下数据结构中哪一个是非线性结构？( )A. 队列B. 栈C. 线性表D. 二叉树4. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。

A．688 B．678 C．692 D．6965. 树最适合用来表示( )。

A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6. 二叉树的第k层的结点数最多为( ).A．2k-1 B.2K+1 C.2K-1 D. 2k-17. 若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( )A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，38. 对n个记录的文件进行快速排序，所需要的辅助存储空间大致为A. O（1）B. O（n）C. O（1og2n）D. O （n2）9. 对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（）个，A．1 B．2 C．3 D．410. 设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。

A.5B.6C.7D.8二、填空题（每空1分，共26分）1. 通常从四个方面评价算法的质量：_________、_________、_________和_________。

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

科目代码：411 请在答题纸（本）上做题，在此试卷及草稿纸上做题无效！山东科技大学2004年招收硕士学位研究生入学考试微机原理试卷（共4页）一、简答题（每题3分，共30分）1、Pentium的内部数据总线为多少位，外部数据总线为多少位？2、中断矢量表的长度是多少？写出其物理首地址和末地址；3、画逻辑图表示出与、之间的逻辑关系；IOR/IO M RD4、写出8088的起始逻辑地址CS：IP；5、写出以下指令中内存操作数提供段地址的段寄存器；（1）ADD AL，－5[BX] （2）MOV CX，[BP+8]（3）INC BYTE PTR ES：[DI+3]6、给段间返回指令RET加注释，说明其操作过程；7、外部中断过程中，CPU何时从8259上获得中断类型号？8、写出8255方式1输出时，与外设联络的两条信号线、何时有效？OBF ACK9、写出现代PC机中，常见的几种系统总线标准；10、在8250中，哪个寄存器具控制异步数据格式？哪个寄存器控制波特率？二、汇编语言概念题（22分）已知数据段和程序：DATA SEGMENTSTR1 DW －64HSTR2 DB 2 DUP（5，’6’），12H，34HCOUNT =$-STR2STR3 DW STR2DATA ENDS1、画出该数据段的存储形式（8分）；2、指出下列指令源操作数的寻址方式，并给出目的（寄存器或存储器地址）及目的操作数据的数值（14分）。

（1）MOV BX，OFFSET STR2（2）MOV AL，COUNT（3）ADD AL，BYTE PTR [BX+2]（4）PUSH BXPOP DI（5）MOV WORD PTR [DI]，STR3第1页三、程序分析（33分）下列程序利用堆栈段传送数据，最适用段间调用一个过程：SCODE SEGMENTASSUME CS：SCODEBBCD PROC FARPUBLIC BBCDPUSH BPMOV BP，SPMOV CX，5MOV AX [BP+6]MOV SI，[BP+8]BBCD1：MOV DX， 0MOV BX，10DIV BXMOV [SI]，DLINC SILOOP BBCD1POP BPRET 4BBCD ENDPDCODE ENDS1、分析上述过程，确定该程序的功能；（6分）2、说明该过程的入口参数和出口参数；（6分）3、编写主模块调用该过程，主模块应包括堆栈段（2分）、数据段（4分）和主程序段（8分）；4、根据主程序、子程序的执行过程，画出堆栈区数据入栈过程的示意图，并指明BP +6、BP+8的位置。