东南大学专业课

《东南大学专业课》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、东南大学］2000数据结构试题科冃名称：数据结构一：简耍回答下列问题（共40分）1•假设一棵二叉树的层序序列是ABCDEFGHIJ和中序序列是DBGEHJACIF,请画出该树.（6分）2.简单比较文件的多重表和倒排表组织方式各自的特点.（6分）3.曲出对算术表达式A-B*C/D+E"F求值时操作数栈和运算符栈的变化过程.（6分）4.找出所有满足下列条件的二叉树6分）R它们在先序遍历和中序遍历时，得到的结点访问序列相同；b）它们在后序遍历和中序遍历时，得到的结点访问序列相同；c）它们在先序遍历和后序遍历时，得到的结点访问序列相同.5.对一个由n个关键字不同的记录

2、构成的序列，能否用比2n-3少的次数选出该序列中关键字取最大值和关键字取最小值的记录？请说明如何实现？在最坏情况下至少进行多少次比较？（8分）6.已知某文件经过置换选择排序后，得到长度分别为47,9,31,18,4,12,23,7的8个初始归并段•试为3路平衡归并设计读写外存次数最少的归并方案，并求出读写外存的次数.（8分）二：已知L是无表头结点的单链表，其屮P结点既不是首元结点，也不是尾元结点，（10分）a）在P结点后插入S结点的语句序列是b）在P结点询插入S结点的语句序列是c）在表首插入S结点的语句序列是d）在表尾插入S结点的语句序列是(1)Pext:

3、=S;(2)Plnext:二P".nextInext;(3)Plnext:二S".next;(4)Sext:=Pext;(5)Sinext:二L;(6)Sext:=N1L;(7)Q:二P;(8)WHILEPextOQDOP:二Plnext;(9)WHILEPextONTLDOP:=Pext;(10)P:二Q;(11)P:二L;(12)L:=S;(13)L:二P;三：设计一个符号表的表示方法，编写算法使得在该表中进行查询，插入和删除任何一个标识符X的操作在0（1）的时间内•假设l<=x<=m,n为要插入的个数，所需空间为m+n.（10分）

4、四：试利用Dijkstra算法求下图中从顶点a到其它各顶点的最短路径，写出执行算法过程中各步的状态.仃0分）/4I6be915ff//2/8J/acg（和严蔚嫩习题集上题冃相同）\4tt12I5I10//df__///3五：以顺序存储结构表示串，设计算法，求串S屮出现的第一个最长重复了串及其位置并分析算法的时间复杂度.（15分）六：写出按后序序列遍历中序线索树的算法.（15分）东南大学］2000操作系统试题内。（1-7基木概念部分（65分）从供选择的答案选岀最确切的答案填入卜•而叙述中的“题）l.__A—以操作系统为支撑环境，也就是说，操作系统为__A_

5、_提供服务。操作系统紧贴__B__并把改造成功能更强大，使用更方便的_C__.操作系统本身的活动部分并发，部分顺序地执行，并发部分称为_D__,顺序部分称为_E__.供选择的答案：A：（1）系统软件（2）应用软件（3）非中断驱动软件（4）中断驱动软件B-E：（1）CPU（2）裸机（3）微核（4）外核（5）个人计算机（6）内核（7）虚拟计算机（8）网络计算机2.现代操作系统中屮请资源的基本单位是在CPU得到执行的基本单位是B一.A_是由C_组成的，它与B的区别之一是一D.供选择的答案：A-B：（1）模块（2）作业（3）线程（4）管程（5）进程（6）类程（7）例程

6、C：（1）入口，过程，岀口（2）正文，数据，堆栈（3）正文段，数据段,PCB（4）正文，数据，JCBD：（1）A的并发粒度比B的大（2）A的并发粒度比B的小（3）A是动态的，而B是静态的（4）A有后备状态，而B没有3.在操作系统中解决进程间的两种基本关系A,往往运用信号量进行_B—的例如为保证系统数据库的完整性，可以把信号量定义为对某个库文件或记录的锁，初值为1,任何进程存取库文件或记录之前先对它执行一个存取后再执行一个供选择的答案：A：（1）同步与异步（2）串行与并行（3）调度与控制（4）同步与互斥B：（1）消息操作（2）P-V操作（3）开关操作（4）读写操

7、作（5）锁C：（1）通信原语（2）调度算法（3）分配操作（4）检查操作（5）释放D,E：（1）联机操作（2）V操作（3）输出操作（4）读操作（5）P操作（6）写操作（7）输入操作（8）trap操作2.每个管程管理—A__临界资源，进程要进入管程，其方法是通过调用特定的__B__•管程内部任何时刻__C__进程处于活动状态。活动进程调用管程内的不活动的进程处在条件变量上，条件变量是与__E__相同的变量。供选择的答案：A：（1）一个（2）二个（3）若干（4）全部B：（1）入口命令（2）访管指令（3）特权指令（4）原语（5）trap指令C：（1）只允许一个（2）只

8、允许一对即二个（3）可允许若干个（4）