2003南航数据结构真题.docVIP

PAGE PAGE 2 南 京 航 空 航 天 大 学 二 ○ ○ 三 年 硕 士 研 究 生 入 学 考 试 试 题 考试科目:数据结构与操作系统 说 明:答案一律写在答题纸上,数据结构部分编程语言不限 第一部分 数据结构(75分) 已知n*n的矩阵a，反对角线的左上角元素非0，其余为0。用行序压缩0元素方法储存，求元素a[i][j]所对应的位置k。 问答题（10分） 解释几种常用的哈希函数的构造方法和解决冲突的方法。 解释B+树的特点。 试用Floyed算法，求出下图中各对顶点之间的对短路径，并写出在执行算法过程中，所得的最短路径长度矩阵序列和最短路径矩阵序列。（10分） 编写程序，对单链表结构的线性表进行排序，并详细说明排序算法。分析时间复杂度。（10分） 设有一个线性表，存放在一维数组a[0…n-1]中，编程将数组中每一个元素循环右移k位，要求只用一个辅助单元，时间复杂度为O（n）。（10分） 设二叉排序树中的结点值为整型，最大值为MAX，给出任意整型值x（x=MAX），编写程序，求二叉排序树中大于x的最小一个数。（10分） 编写程序，实现用拓扑排序方法求最长路径的算法。（10分） 假设一棵平衡二叉树的每个结点都称为平衡因子，试设计一个非递归算法，利用平衡因子，求平衡二叉树的高度。（10分） 第二部分 操作系统(75分) 填空（每小题4分，共20分，答案要写在答题纸上，并且要给出解题过程） 如下程序在页试虚存系统中执行，程序代码位于虚空间0页，A为128*128的数组，在虚空间以行为主秩序存放（A（1，1），A（1，2）..）,每页存放128个数组元素。工作集大小为2个页框（开始时程序代码已在内存，占1个页框），用LRU算法，下面两种对A初始化的程序引起的页故障数分别为____和____。 for j:=1 to 128 do for i:=1 to 128 do A(i,j):=0 (2) for i:=1 to 128 do for j:=1 to 128 do A(i,j):=0 一个使用32位虚地址的计算机使用两级页表，虚地址被分为10位的顶级页表域、10位的二级页表域、12位偏移。则页面长度是______,在虚地址空间中共有____个页。 在DOS和WINDOW操作系统中都支持FAT16文件系统，该文件系统中一个文件的物理结构（即该文件占用磁盘上那些块号，通常称块号为族号），是用文件分配表FAT来表示，文件分配表FAT的每个表项占16位。 如果某分区为FAT16磁盘文件系统，每族64扇区，扇区的大小为512字节，则：该分区最大可为___字节，每个FAT表占用的储存空间是____字节。 如果FAT表不在内存，读2M字节大小的文件的最后一个字节，最多要读___扇区，最少要读___扇区。 为了实现3个进程互斥进入临界区，可设置一个公用信号量，其初值为1，取值范围是_______。 一台计算机有10台磁带机被m个进程竞争，每个进程最多需要3台磁带机，那么m______时，系统没有死锁的危险。 回答下列问题（每小题5分，共25分） 在支持请求调页的操作系统（如UNIX、LINUX等）中，为了减少页面的换出换入，常采用页面缓冲技术（该页面缓冲也称为交换缓冲）。请具体说明如何使用交换缓存来减少I/O操作（需图示）。 一个分时系统中，以当前进程的时间片用完而引起进程切换为例，描述进程切换的实现过程。请以一个实际芯片（如Intel80386）为例，讨论如何利用时钟中断处理程序，实现进程切换，硬件做哪些工作，操作系统做哪些工作？ 解释临界资源和临界区的概念。有哪些方法能使多个进程互斥地访问临界资源。 举例说明，在应用程序中是如何使用操作系统提供的服务的？ 请说明原语与过程、系统调用与过程、系统调用与原语的区别，如果操作系统把绝大多数的系统调用定义为原语，会产生什么问题？ 三、（10分）在一个盒子里，混装了数量相等的围棋黑白字。现用自动分拣系统把白字和黑子分开，该系统设两个进程P1和P2，P1拣白字，P2拣黑子。规定每个进程每次只拣一子，当一个进程正在拣子时，不允许另一个进程去拣子，当一个进程拣了一个子后，必须让另一个进程去拣子。试用P、V操作控制这两个正确运行。 四、（20分） 设每类资源数量为1，N个进程，写出算法复杂度为O（N）的死锁检测算法，并指出下图中是否有死琐。 提示：因为每类资源数量为1，如R1，它已分配给P3，P1又请求它，可将这种资源从图中去掉，直接从P1画一条有向边到P3。要求：画出该图修改后的邻接距阵，并说明在修改图中存在环必定存在死琐的道理。P1 P1 P3 R3 R2 P1 P2 R4