科目代码科目代码403
请在答题纸请在答题纸本上做题在此试卷及草入纸上做题无效上做题在此试卷及草入纸上做题无效
山东科技大学2005年招收硕士学位研究生入学考试
数据结构与操作系统试题
共4页说明1本试卷为数据结构和操作系统两部分数据结构部分共六题满分100分操作系统部分共三题满分50分全试卷共十题满分150分2答案一律写在答题纸上3答卷应字迹清楚语义确切数据结构部分注意事项1算法应说明基本思路应对主要数据类型变量给出说明所写算法应结构清晰简明易懂应加上必要的注释2算法可用类PASCAL语言类C语言等你所熟悉的高级语言编写但要注明语种一解答下列问题共30分15分根据数据元素之间关系的不同特性数据的逻辑结构通常有哪些基本结构数据元素之间的关系在计算机中有哪几种表示方式
第1页
25分将NN的上三角矩阵Aij时Aij0ij时Aij0的非零元存储在一维数组B下标k从0开始试给出Bk与Aij之间的元素对应关系35分写出后缀表达式abxcdefx的运算顺序45分画出广义表axyx的存储结构55分比较哈希表与其它查找表的不同之处65分利用两个栈S1和S2模拟一个队列写出入队算法和出队算法的算法思想二10分已知树T的先序访问序列为ABEFCDGHIK后序访问序列为EFBCHIKGDA1画出树T2将树T转换为对应的二叉树BT3将二叉树BT后序线索化三15分有一种简单的排序算法叫做计数排序cou
tsorti
g这种排序算法对一个待排序的表用数组表示进行排序并将排序结果存放到另一个新的表中必须注意的是表中所有待排序的关键码互不相同计数排序算法针对表中的每个记录扫描待排序的表一趟统计表中有多少个记录的关键码比该记录的关键码小假设针对某一个记录统计出的计数值为c那么这个记
第2页
f录在新的有序表中的合适的存放位置即为c如C0则当前元素存放在新表的号单元编程实现计数排序算法四15分编写一递归属算法删除单链表中所有值为x的结点五15分试写一算法求二叉树T中任意指定两个结点最近的共同祖先结点六分度写一算法15判断有向图G中任意指定两个结点之间是否存在路径
二名词角释每小题词分共15分1操作系统2周转时间3碎片4设备驱动程序5事务三综合题25分1分设有两个进程P1和P2的程序如下其信号量的初始值6S1S20试求P1P2并发执行结束后的xyz的值并对结果加以解释进程1Y1Yy2Sig
als1Zy1WaitS2Yyz进程2x1xx1wr