《电子科技大学820计算机专业基础历年考研真题及详解附答案.docx》由会员分享，可在线阅读，更多相关《电子科技大学820计算机专业基础历年考研真题及详解附答案.docx（124页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、电子科技大学820计算机专业基础历年考研真题及详解邵THROUGH TRFUN最新资料，WORD格式，可编辑修改!2014年电子科技大学820计算机专业基础考研真题错误!未定义书签。2013年电子科技大学820计算机专业基础考研真题82013年电子科技大学820计算机专业基础考研真题及详解162012年电子科技大学820计算机专业基础考研真题252012年电子科技大学820计算机专业基础考研真题及详解312011年电子科技大学820计算机专业基础考研真题及详解402010年电子科技大学820计算机专业基础考研真题及详解522008年电子科技大学820计算机专业基础考研真题及详解642007年电
2、子科技大学413计算机专业基础考研真题及详解752006年电子科技大学413计算机专业基础考研真题及详解842005年电子科技大学计算机专业基础考研真题及详解922003年电子科技大学429计算机专业基础考研真题104说明：电子科技大学计算机专业基础专业的科目代码2003年是429,2005年不 详，2006年改为413,2008年改为820.电子科技大学信息与软件工程学院、计算机科学与工程学院、电子科学技术研究 院、自动化工程学院均考此科目。电子科技大学2014年攻读硕士学位研究生入学考试试题考试科目：820计算机专业基础注：所有答案必须写在答题纸上，写在试卷或草稿纸上均无效.计算机操作系统
3、一、填空题（10分，每空2分）1.现有3个同时到达的作业J1、J2和J3,它们的执行时间分别为Tl、T2和T3,且T1T3 P2之间的同步与互斥关系，并说明所定义信号般的含义，要求 用伪代码描述.（16分）四、简答题（21分）1 .在存储器管理中，什么是重定位？为什么要引入重定位技术？（5分）2 .在分页存储管理系统中，页表的主要作用是什么？现代大多数计修机系统都支持非常 大的逻辑地址空间（2”2），这给页衣设计带来了什么样的新问题，应如何解决。（5 分）3 .以从I/O设备读入数据为例，请用流程图方式说明程序I/O、DMA传输控制的处理过 程。（6分）4 .在哲学家就餐问题中，如果将先拿起左
4、边筷子的哲学家成为左撇子，而将先拿起右边 筷子的哲学家称为右撇户.在同时存在左撇子和右撇子的前提下，我们安排哲学家随 意就座.请问是否可能产生死锁，为什么？（5分）数据结构一、填空题（共10分，每空1分）1 . 一个“好”的算法应考虑达到以下目标：正确性、可读性、健壮性、.2 .广义表（），3），（!）,（：,（1）/）的深度是。3 .遍历二叉树实质上是对一个非线性结构进行 操作。4 .对有n个顶点、e条边且使用邻接表存储的有向图进行广度优先遍历，其算法复杂度 是.5 .若一个具有n个顶点，e条边的无向图是一个森林，则该森林中必有 棵树。6 .求图的最小生成树有两种克法，克法适合于求边稀疏的图
5、的最小生成树。7 .最短路径迪杰斯特拉（Di j kstra）律法的复杂度.8 .二叉树上有一个结点的平衡因子的绝对值大于.则该二叉树就是不平衡的。9 .哈希表的地址区间为0-8 ,哈希函数为H （K） =K mod 9。采用线性探测法处理冲突，并 将关键字序列（12,21,43,5,39 ）依次存储到哈希表中，则元素39存放在哈希表中的地 址是.10 . 排序律法不需要进行记录关键字间的比较。二、单选题（共2。分，每题2分）1 .某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采 用（）存储方式最节省运算时间。A.单链表 B.仅有头指针的单循环链表C.双链表 D.仅
6、有尾指针的单循环链表2 .下述哪一条是链式存储结构的优点？（）A.存储密度大 B.插入、删除运算方便C.存储单元连续D.随机存取第i个元索方便3 . 一个栈的输入序列为1 2 3 4 5 ,则下列序列中不可能是栈的输出序列的是（）。A. 2 3 4 1 5 B. 5 4 1 3 2 C, 2 3 1 4 5 D. 1 5 4 3 24 .最大容量为n的循环队列，队尾指针是rear,队头是front ,则队满的条件是（）。A. （rear+1） MOD n=frontB. rear:frontC. rear+1=frontD. （r ear -1） MOD n=front5 .若一棵二叉树具有2
7、0个度为2的结点，10个度为1的结点，则度为0的结点个数是（） A. 10B. 11C. 21 D. 306 .二叉树的第i层上最多有（）结点。A. 2B. 2-1C. 2-1D. 211. 一棵小空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树定是（）A.完全二叉树B.只有一个节点C.高度等于其节点数D.二叉排序树8 .对图进行广度优先搜索遍历类似尸二叉树的（）丸法.A.先序遍历 B,中序遍历C.后序遍历D.层次遍历9 .对下图进行拓扑排序，可以得到不同拓扑序列的个数是（A. 6 B. 5 C. 4 D. 310.有一组数据(43,21,52,60,1 2,1 5 )利用快速排序，
8、以第一个元素为基准得到一次划分结 果为().A. (1 5,21,12,43,52,60 )8.( 15,12,21,43,52,60)C. (1 2,1 5,21,43,60,52 )0.( 1 5,21, 1 2,43,60,52)三、简答题（30分，每题6分）1.2.3.画出算术表达式（2 + 1）*（0（1）-（6”+9）转换的二叉树。若通信系统中只可能出现5种字符A、B、C. D和E其概率分别为0.12、0.15、0.19、0.21和0.33, （1）试设计赫夫曼编码：（2）画出相应的赫夫夏树。给出下图G的（1）邻接表表示图：（2）并根据画出的邻接表，以顶点1为根，画出深 度优先生成
9、树。4 .输入一个正整数序列（45,14,11,52,63,32,56,24）, （1）按此次序构造一颗二叉排序树：（2） 如果删除52,画出删除后的二叉树结构。5 .堆排序的基本思想是什么？其优点是什么？四、算法题（15分，共2题）1.设计一个算法，逆序单链表中的数据。（5分）2,采用二叉链友的存储结构，分别写出统计二叉树的叶子结点个数和树高的函数，并分别 分析时间复杂度。（10分）2013年电子科技大学820计算机专业基础考研真题考试科目：820计算机专业基础注：所有答案必须写在答题纸上，写在试卷或草稿纸上均无效。计算机操作系统一、填空题（10分，每空2分）1 .文件目录是 的有序集合.2
10、 .某计算机系统中有11台打印机，由k个进程竞争使用，每个进程最多需要4台打印机* 该系统可能会发生死锁的k的最小值是一.3 . 一个简单分段存储管理系统中，地址长度为32位，其中段号占12位，则最大段长是一 字节.4 .操作系统提供给应用程序的接口是.5 .现代操作系统实现了设备无关性，应用程序使用 来请求使用某类设备.二、选择题（14分，每题2分）1 .进程调度时，下列进程状态的变化过程哪一项是不可能发生的？（）A.阻塞挂起-阻塞B.就绪挂起-就绪C.就绪挂起-阻塞挂起D.阻塞挂起-就绪挂起2 .关于线程和进程，下面说法正确的是（）A.终止一个进程比终止一个线程花费的时间少.B.进程切换比
11、同一进程内部的线程切换花费的时间少.C.线程提高了不同执行程序间的通信效率。D.进程和线程都是资源分配和调度的基本单位.3 .下列事件最可能导致系统产生死锁的是（）.A.进程释放资源B. 一个进程进入死循环C.多个进程竞争独占资源D.多个进程竞争共享资源4 .关于子进程和父进程的说法，下面哪一个是正确的？（）A. 一个父进程可以创建若干个子进程，一个子进程可以从属于若干个父进程B.父进程被撤销时，其所有子进程也被相应撤销。2013年士研究生入学考试试题汇编3C.子进程被撤销时，其从属的父进程也被撤销.D. 一个进程可以没有父进程或子进程.5 .文件系统采用二级文件目录可以（）.A.缩短访问存储
12、器的时间B.实现文件共享C.节省内存空间D.解决不同用户间的文件命名冲突6 . 一种既有利于短小作业又兼顾到长作业的作业调度算法是（）A.先来先服务B.轮转C.最高响应比优先D.均衡调度7 .设计批处理多道系统时，首先要考虑的是（）.A.灵活性和可适应性B.系统效率和吞吐量C.交互性和响应时间D.实时性和可靠性三、分析计算题（30分）1 .考虑一个使用32位地址和1KB大小的页的分页虚拟内存系统.每个页表项需要32 位，限制页表的大小为一个页，请回答：（1）页表一共需要几级？（5分）（2）请设计每一级的页表大小,使得所需的页数个数总和最小.（8分）2 .桌上有一空盘，允许存放最多两个水果.爸爸
13、可向盘中放苹果或橘子，儿子专等吃 盘中的橘子，女儿专等吃盘中的苹果。规定当盘子不满时,一次只能放一只水果：当盘子不 空时，一次只能取一只水果：父亲放水果时，儿子女儿不能取：儿子女儿取水果时，父亲不 能放.（1）请分析，本例中临界资源是什么？（1分）（2）下面是用P、V操作实现的爸爸、儿子、女儿三个进程的同步，请完成程序中的空行 部分.（每空1分）*Semaphore mutex=; 定义互斥信号量int empty二, apple=, orange=; 定义同步信号量 Father: 父亲进程While（l） （Put an apple or orange;If (fruit=apple)El
14、seDaughter: 女儿进程While(l) Fetch ari apple;Son: 儿子进程While(l) Fetch an orange;）四、简答题C21分）1 .操作系统中什么是虚拟存储器？为什么要引入虚拟存储技术？（5分）2 .考虑文件系统的外存分配，简述什么是连续分配方式和索引分配方式.（5分）3 .什么是DMA方式？它与中断方式的主要区别是什么？（6分）4 .简述利用位示图进行文件存储空间管理的思想.这种方法的优缺点是什么？（5分）数据结构一、填空题（共10分，每空1分）1 .一颗有n个结点的二叉树，叶子结点的数量为n0,度为2的结点数量为n2,则n0与n2 的关系是：如
15、果用二叉链表存储该二叉树，则空指针数量为.2 . 一个有向图的邻接表和逆邻接表中结点的个数 .3 .将101, 186,16, 163,752,334,61等7个数据存入长度为10的线性施.哈希函数 h（K）=K%7 ,解决冲突策略为线性探测再散列，则采用 存储结构存储数据，其中163存储在哈希表的第 个位置（H（k）=O为第1个位置）.4 .输入n个数据，2路归并排序的时间复杂度为 .5 .无向图G=（V,E）,有n个顶点，e条边，则邻接矩阵有 个0元素，其邻接矩阵是对称矩阵，只需用 空间可实现压缩存储.6 .对二叉排序树 可以得到线性有序序列.7 . 一个有向无环图的拓扑排序谆列 是唯一的
16、.二、单选题（共20分，每题2分）1 .从逻辑上可以把数据结构分为（）两大类.A.动态结构、静态结构B.顺序结构、链式结构C.线性结构、非线性结构- D.初等结构、构造型结构2 .以下数据结构中，（）是非线性数据结构.A.树 B.字符串 C.队D.栈3 .设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用（）最节省时间.A.单链表 B.单循环卷表C.带尾指针的单循环链表D.带头结点的双循环链表4 .对于血序存储的线性表，访问结点和增加结点的时间复杂度为（）.A. 0（n） 0（n） B. 0（n） 0（1） C. 0（1） 0（n） D. 0（1） 0（1）5 .对于队列操作数据的原则
17、是（）.A.先进先出B.后进先出C.先进后出D.不分顺序6 .要保证连通具有10个顶点的无向图，至少需要（）条边.A. 9B. 90C.37D.457 .设栈的初始状态为空，当字符序列a3一作为栈的输入时，输出长度为3的且可以用作C语 言标识符的字符序列有（）个A. 4B. 6C. 3D.58 .完全二叉树采用（）存储结构，满足存储空间少，方便的查找任意结点的双亲与孩子. A.顺序B.单链表C.二叉链表D.三叉链表9 .下面（）数据结构常用于函数调用.A.队列B.栈C.链表D.数组10 .下面（）排序算法在输入数据逆序情况下排序速度最快.A.归并排序 B.直接插入排序 C.冒泡排序 D.简单选
18、择排序 三、简答题（共30分,共5题）1 .已知4个字符A, B, C, D的宦夫曼编码分别是1. 01, 000, 001.下列01串是由以上4个字母 构成的一段文本的霍夫曼编码：1001000011011010011010011请将上述01串还原为编码前的文本。以字符在文本中出现的次数为权值，求出这棵树的 带权路径长度.（共5分）2 .输入元素序列32, 18.63,5, 1,11,44,33,78,请构造AVL树.假设所有元素的查找概率相 等，请分别求出这棵AVL树的查找成功的平均查找长度ASL（成功）与失败的平均查找长度 ASL（失败）.（共5分）3 .海量数据分布在100台电脑中,想
19、个办法高效统计出所有数据的前10个最大关键字数据， 并分析时间发杂度（共6分）.4 .若输入数据存储在带头结点的双向循环链表中，下面各种排序算法是否仍然适用？为什 么？（共6分）（1）快速排序（2）直接插入排序（3）简单选择排序（4）堆摔序5 .已知某工程各工序之间的优先关系和各工序所需的时间（其中“一”表示无先驱工序, 如下表所示.请根据工序表画出对应的A0E图，并指明完成该工程所需的最短时间和关 键路径.（共8分）工序代号ABCDEFGHI所需时间351466732先驱工序AAABBDG四、算法题（共15分，共2题）1 .线性表（al, a2,an）中元素递增有序且按顺序存储于计算机内的数
20、组a中.要求设计一 算法用函数实现下列功能：（共10分）-（1）用最少时间在表中查找值为x的元素：（2）若找到则将其与直接后继元素交换：（3）若找不到则将其插入表中使其表中元素仍然递增有序2 .假设Header指向如下循环单链表，请问执行下列2个程序段后各自的输出结果是什么？ （共5分）Header单链表结点定义如F： typedef struct node (int data;struct node *next;Node, *ptr, List;第一个程序段ptr p=Header;for(int i=0;idata);p=p-next;p=p-next ：)第二个程序段ptr p=Head
21、er;for(int i=0;idata);p=p-next;p=p-next;p=p-next：)第15页2013年电子科技大学820计算机专业基础考研真题及详解第16页参考答案：820计算机专业基础_计算机操作系统一、填空题1 .文件控制块2 . 43 . 2204 .系统调用5 .逻辑设备名称二、选择题C C C D D C Br三、分析计算题（30分）1 .考虑一个使用32位地址和1KB大小的页的分页虚拟内存系统，每个页表项需要32 位，限制页表的大小为一个页，请回答；（1）答：由于页面大小占用lObit,还剩22bit,即有24个页表项.一个页表项32bit,即 占用4个字节，一页最
22、多含2K74-28个页表项，所以需要3级页表.（5分）（2）答：若一线页表长度为6位，二级和三级页表长度各为8位，则需要的页数总数为 1+2+2”=16449：若一级页表长度为8位，二级页表长度为6位，三级页表长度为8位，则总 共需要页数为：1+2,2“=16641：若一级页表和二级页表长度分别为8位，三级页表为6位， 则总共需要1+2+2愀=65793页.因此，三级页表的长度分别为6, 8. 8时，总页数和最小.（9 分）*2.每格一分，共16分（1）临界资源是盘子（2） Semaphore mutcx=_1_; 定义互斥信号量int empty=_2_, apple=_0_, orange
23、=_0_; /定义同步信号量 Father 父架连程While（l）P(empty)_P(mutex);Put an apple or orange;If (fhiit=applc) _V(apple)_;Else _V(orange);)Daughter: 女儿进程While(l) ( _P(apple)_;P(mutex);Fetch an apple; _V(mutex)_; _V(empty)_;)Son: 儿子进程WhUe(l) P(orange)_;P(mutex);Fetch an orange; Wmutex); V(empty);) 四、简答题（21分）1 .答：在具有层次结
24、构存储器的计算机系统中，自动实现部分装入和部分替换功能，能 从逻辑上为用户提供一个比物理贮存容量大得多,可寻址的“主存储器乙虚拟存储区的容量 与物理主存大小无关，而受随于计算机的地址结构和可用磁盘容量。.计算机操作系统引入和使用虚拟存储技术的主要目的是提高系统的内存利用率和系统吞 吐量（5分）2 .答：连续分配方式：在创建文件时需要给文件分配一组连续的盘块。连续分配的优点 主要有两个，分别是顺序访问文件时比较容易，并且顺序访问时速度快.缺点是要求有连续 的存储空间，并且随着外存空间的分配和回收，会产生很多外存碎片.降低了外存空间的利 用率.索引分配方式：为文件的每个分区单独建立一张索引表。该索
25、引表记录了分配给该文件 的所有的块号。优点：直接访问和顺序访问的速度都比较快.缺点：存储索引表花费了较多 外存空间.（5分）3 .答：DMA是直接存储器存取.DMA传输将数据从一个地址空间复制到另外一个地址 空间.当CPU初始化这个传输动作，传输动作本身是由DMA控制器来实行和完成,在实现 DMA传输时，是由DMA控制器直接掌管总线，因此，存在着一个总线控制权转移问题。即DMA 传输前,CPU要把总线控制权交给DMA控制器，而在结束DMA传输后，DMA控制器应立即把总 线控制权再交回给CPU.它和中断的主要区别在于，DMA只需要CPU在开始和完成传输时进行 干预，其他时候不需要CPU干预.（6
26、分）4 .答：若磁盘块空闲，则用1表示，否则用0表示.从而得到一张位式图表，反映了所 有磁盘块的信息。其优点在于很容易找到一个连续的空闲块.缺点在于整个磁盘的位式图文 件比较大，另外，在磁盘空闲快较少时，搜索空闲块要花费一些时间.（5分）数据结构一、填空题（共10分，每空1分）1 . n0=n2+l ;n+12 .相同（一样）3 .顺序；64 . O（nlogn）5 . n-2e：n（n+l）/26 .中序遍历7 .不/不一定二、单选题（共20分，每题2分）1-5. CADCA 6-10. CCABA三、简答题（共30分，共5题）1 .答：霍夫曼编码是前缀编码，满足任意字符的编码都不会是另外一
27、个字符编码的前缀, 因此译码不会产生歧义.1001000011011010011010011还原出来的文本为：1 001 000 01 1 01 1 01 001 1 01 001 1AD CBABAB DABDA（2 分）其中A出现5次，B出现4次，C出现I次,D出现3次，（2分）带权路径长度为WPL=（l+3）*3+4*2+5=25（1分）2 .答：AVL树如下图所示.（3分）ASL （成功）=（1+2*2+4*3+2*4）/9=25/9（1 分）ALS （失败）=（3*6*4*4）/10=34/10=3.4（1 分）3 .答：先分别求出每台电脑的前10个最大关键字数据，再根据这100台电
28、脑的最大前 10个最大关键字数据，共1000个数据求出前10大关键字数据即可.具体分析如下：（1）先求出每台电脑的前10大数据,由于只需要求出部分数据，因此不需要对n不数据 全部排序，采用部分排序算法即可，比如简单选择排序、堆排序、桶排序.。分）（2）求n个数据的前k （这里k=10）大数据，当kn时，最佳的方法是将后面的n-k个 数据依次与前面的k个数据的最小直比较，如果比最小值逐小.则扔掉该数据，继续比较下 一个数据，否则扔掉更小的数据，把这个新数加入，直到余下的n-k个数据都处理完。由于 每次需要与存储的k个数据比较并可能删除最小元素，加入新的元素，最好的结构是小顶堆。 即将前k个元素调
29、整为小顶堆（时间复杂度为0（k】ogk）,余下元素依次与小顶堆根结点比较， 比根结点小则扔掉，比根结点大则用当前值替换根结点并调整为小顶堆,中剧复杂度为 O（Iogk）.所以总的最坏时间复杂度为O（klogk） +0（n-k） logk）=0（nlogk）（小顶堆1分，分析过程与时间复杂度分析共2分）（3）再从m（这里m=100）台电脑的共km（这里km=1000）个数据中选择所有数据的最大k个，采用(1)类似的方法即可求出。即将一台电脑的小顶堆作为初始小顶堆，余下mT台电脑的母 人k个元素依次与小顶堆的根结点元素比较，大于根结点则替换根结点元素并调整为小顶堆， 宜到余下的数据都处理完成，时间
30、爰杂度为。(加-Dklogk)(1分)(4)综合上面3步，最终选择小顶堆能够最快统计出所有数据的前k(k=IO)个最大关键 字数据,总的最坏时间复:杂度为O(nlogk) +0(m-1) klogk)=0(n+mk-k) logk).如果 kkmn,则 T(n)=0(n) (l分)4 .答：(1)快速排序适用(0.5分)，因为可以快速定位到第一个元素与最后一个元素结点(0.5 分)，然后通过1个指针从头部向后移动，另外一个指针从尾部向前移动，逐一与枢纽进行比 较并能够通过修改指针完成结点交换操作(0.5分)(2)插入排序适用(0.5分).因为可以方便的找前趋后维(0.5分)和通过修改指针完 成
31、结点交换操作(0.5分)(3)选择排序适用(0.5分)，因为只需要移动指针遍历链表(0.5分)并通过修改指针 完成结点交换(0.5分)(4)堆排序不适用(0.5分),因为双向循环链表无法方便的找完全_叉树的双亲与孩子 结点(1分)5.答：根据先序关系画出AOE图如下:(3分)V4VI则各个事件Vi(i=l,2,6)的最早开始时间VE(i)和最晚开始时间VL(i)如下嚷所示:事件iVIV2V3V4V5V6VE(i)03571214Vl(i)045111214各个活动的最早开始时间ae(i)与最晚开始时间al (i)如下表所示(3分):活动iABCDEFGHIae(i)0033355712al(i
32、)10478851112所以，完成该工程所需最短时间为14天.关键路径有：B,G,I(2分)四、算法题(共15分，共2题)1.解：顺序存储的线性表递增有序，可以顺序查找也可以折半查找，题目要求“最少时间查找值为x的元素”，选用折半查找(2分).算法如下：#define status intWefine true 14define false 0status SearchExchangelnsert (ElemType a int *n, ElemType x) (int low=0, high=*n-l, mid, i;status s=false;数组长度检查(1分)if(lowhigh)r
33、eturn s：if(*n=0)return s;折半查找(2分)while (low=high) (mid=(low+high) /2;if (a mid=x) break;)else if (amid=low：i)alov=x;(*n)+;)return s;)2.答：(1)程序输出结果为：13524(2)程序输出结果为：14253(3分)（2分）（2分）（3 分）-用ND贝第24页2012年电子科技大学820计算机专业基础考研真题考试科目：820计算机专业基础注：所有答案必须写在答题纸上，写在试卷或草稿纸上均无效。 计算机操作系统单项选择题（每小题2分，共14分） 页式存储管理系统中的页
34、面大小是由（）决定的。 A.用户B.系统C.系统和用户D.不确定下面哪一种表述不属于操作系统的主要功能？（）A.处理机管理B.存储器管理C.设备管理和文件管理D.可移植下面哪一种描述不是操作系统的主要目标？（） A.有效性 B.方便性 C.可扩充性D.多路复用文件目录是（）的有序集合。A、文件控制块B,文件信息C,文件名D、文件属性文件系统采用二级文件目录可以（）A.缩短访问存储器的时间B.节省存储空间C.节省内存空间D.解决不同用户间的文件命名冲突在一段时间内，只允许一个进程访问的资源被称为（） A.共享资源 B.临界区 C.临界资源 D.共享区 在单处理器系统中，如果同时存在有12个进程，
35、则处于就绪队列中的进程数量最多为（）A. 1B.9 C. 10 D. 11二、填空限（每空2分，共10分）1 .根据对截止时间的要求不同，实时任务可以划分为硬实时任务和（）.2 .重定位是指程序的虚地址到（）的转换，根据定位时机可一分为（）和（）两种.3 .文件的物理分配方法包括连续分配、链式分配和（）.三、简答题（共21分）1.什么是顺序文件？试说明顺序文件的优点和缺点.（4分）2,阐述什么是SPOOLING技术。（4分）3 .什么是死锁？如何预防死锁？ （4分）4 .阐述基本分页存储管理和请求分由存储管理的异同之处.（5分）5 .阐述计豫机系统中缓冲的作用和分类14分）四、计算踵（30分）
36、1 .在请求式分页管理系统中，某一作业有4个页面，分别被装入到内存的3, 4, 6, 8号页 框中，假设页面和页框的大小都为1024字节，当该作业在CPU上运行时，执行到其地址空间第500号处遇到一条传送指令MOV 2200 3100,请计算出MOV指令中两个操作数的物理地址， 并给出计算过程.（8分）2 .磁盘共有200个柱面，其编号为0T99,假定磁头正停在99号柱面上访问.现有一个请求 队列在等待访问柱面，该请求队列访问的柱面号分别为：190、97、54、30、87.若采用FCFS（先来先服务）和SSTF （最短寻道时间优先）的磁盘调度算法，请分别计算磁头移动的总磁 道数.（10分）3
37、.针对下面进程集合，考虑两种调度算法：先来先服务和最短进程优先.分别计算各个进程 的周转时间、带权周转时间以及平均周转时间和平均带权周转时间.请完成下列两个表格， 并说明哪种调度算法性能好？（12分）进程名到达时间处理时间P103P215P332P484P5105先来先服务:进程到达时间处理时间完成时间周转时间带权周转 时间平均周转 时间平均带权 周转时间P103P215P332P484P5105最短进程优先:进程到达时间处理时间完成时间周转时间带权周转 时间平均周转 时间平均带权 周转时间P103P215P332P484P5105数据结构一、单项选择题（20分,每题2分）：下面算法的时间复杂
38、度是（）.for （i=n;il; i-）for （j=i-l;jl： j）x+：A. 0（n）B. O（n）C. 0（n（n-D） D. O（nlogn）以下数据结构中，（）是非线性数据结构。A.图 B.字符串C.数组D.堆栈3、链表不具有的特点是（）.A.插入、删除不需要移动元素B.不必事先估计存储空间C.可随机访问任一元素D.所需空间与线性表长度成正比4. 一个枝的输入序列为123n,若输出序列的第一个元素是n,输出的第i （l=i=n）个 元素是（）.A.不确定 B. n-iC. iD. n-i+15、若一棵二叉树具有12个度为2的结点，6个度为1的结点，则度为0的结点个数是 （）.A
39、. 10 B. 11C. 13D.不确定6、下列哪种算法使用了队列作为辅助存储结构（）.A.二叉树的先根序遍历算法B.二叉树的层次遍历算法C.图的深度优先遍历算法D.图的拓扑排序算法7,以下哪种二叉树左右子树可以交换（）.A.二叉排序树B.线索二叉树C.平衡二叉树D.哈夫曼树8、下列哪种图的邻接矩阵是对称矩阵（）.A.有向图B.无向图C, AOV网D. AOE网9,在长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（假定 查找每个元素的概率均相等）为（）.A. nB. （n-I）/2C. n/2D. （n+l）/210.下列排序算法中，（）在某趟排序结束后不一定能选出一个元素放到其最终的位置