405数据结构与操作系统山东科技大学2007年硕士研究生入学考试试卷.doc

数据结构部分 注意事项： 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表示n0）。 2、[8分]设有正文AADBAACACCDACACAAD，字符集为A、B、C、D，设计一套二进制编码，使得上述正文的编码最短。 3、[8分]画出对长度为10的有序表进行二分查找时的判定树，并计算在等概率情况下查找成功的平均查找长度。 三、[15分]某超市有一批水果，按其价格从低到高的顺序构成一个单链表，每个结点有价格、数量和指针三个域，现新进m公斤价格为h的水果，编写一个函数修改原单链表。 四、[15分]采用链表作存储结构，编写一个采用选择排序方法进行升序排序的函数。 五、[15分]采用二叉链表存储树，试写一算法，实现对树的层次遍历。 六、[15分]设计一个算法，判断无向图G是否一棵树。 操作系统部分（50分） 一：名词解释（每题3分，总计12分） 1：线程 2：死锁 3：虚拟存储器 4：中断 二：简单题（每题5分，总计20分） 1：什么是微内核OS结构？ 2：进程控制块PCB的主要作用是什么？ 3：在I/O控制中，为什么引入DMA(Direct Memory Access)控制方式？DMA控制方式有何特点？ 4：在请求分页系统中，每当所要访问的页面不在内存时，就产生一个缺页中断。请描述操作系统处理缺页中断的流程。 三：综合题（总计18分） 1：设有5个哲学家，共享一张放有五把椅子的桌子，每人分得一把椅子。但是桌子上总共只有五只筷子，在每人两边分开各放一只。他们的生活方式是交替的进行思考和进餐。哲学家在肚子饥饿时才试图分两次从两边拾起筷子就餐；进餐完毕，放下筷子继续思考。 条件：1）只有拿到两只筷子时，哲学家才能吃饭。2）如果筷子已在他人手上，则该哲学家必须等到他人吃完之后才能拿到筷子。3）必须分两次从两边拿起筷子。 请在满足上述约束条件的情况下，使用信号量机制，描述一个不会有哲学家饿死的算法。(本题8分) 2： 在磁盘存储管理中，经常采用混合分配方式。如下图，是UNIX V采用的混合索引分配方式，共设有13个地址项。其中iaddr(0)~iaddr(9) 为direct blocks，即直接地址，single indirect、double indirect 和triple indirect分别代表一次间接地址、二次间接地址和三次间接地址，地址项分别为iaddr(10)，iaddr(11)和iaddr(12)。假设每个磁盘块大小为4KByte，地址位为32bits。请问UNIX V采用这种分配方式有何好处？允许的文件最大长度为多大？（本题5分） 3：在内存管理中，不能被利用的小分区称为“外碎片”，分区内部不能被使用的空间称为“内碎片”。碎片的存在影响了内存空间的利用率。请描述，在操作系统中处理碎片的策略。（本题5分）