浙江工商大学信息学院845计算机基础综合历年考研真题汇编p

1、浙江工商大学信息学院845 计算机基础综合历年考研真题汇编最新资料， WOR格D 式，可编辑修改！目录2015年浙江工商大学信息学院845 计算机基础综合考研真题 错误！未定义书签2014年浙江工商大学信息学院845 计算机基础综合考研真题 错误！未定义书签2013年浙江工商大学信息学院845 计算机基础综合考研真题 错误！未定义书签浙江工商大学2015年全国硕士研究生考试试卷（A）卷考试科目：845计算机基础综合（数据结构50%,操作系统50%） 总分：（150分）考试时间：3小时第一部分数据结构（75分）一、算法应用题：（共4小题,每小题10分，共40分）1、（10分已知二义树的先（前）序

2、遍历序列为ABCDEFGH,中序遍历序列为CBEDFAGH.画出此一叉 树，并给出其后序遍历序列。2、（10分）对关键子序列（712, 817. 611, 213, 904. 106. 45. 598）进行堆推序,谙给出调整厉的 初始最小堆。3、（10分）试用权集合12,4,5,6,1,2构造哈夫曼树，并计算哈夫曼树的带权路径氏度。4、（10分）AOE网如下所示，求关键路径。一、算法设计题：（共35分）1、（10分）设一棵二义树以_义链表为存储结构，结点结构为Ichild |data |rchild。设计一个算法，求在 前（先）序序列中处于第k个位置的结点。2、（10分）己知线性表中的元素以值

3、递增有序排列，并以单链表作存储结构。试锋一算法，删除表中所 有大Tx且小丁y的元索（若表中存在这样的元索）同时霽放被删除结点空间。3、（15分）请设计一个算法，求山给定字符串中最氏的对称字符串”，例如，“efghiihgfabc”，最长“对称字符串”是fghiihgf,opqrstww”，最氏对称字符串是“ww,abcdefghijk”，无“对称字符串”；第二部分操作系统（75分）一、填空题（每空2分，共20分）1、从结构上看，每个进稈由二部分纽成，它们是, 和。2、系统中存在多个进程时，这些进程对共享资源的使用存在着不同的相直制约关系，一种是关系，另一种是关系。3、地址映射是指将程序中的地址

4、转换为内存中的地址.在分页管理系统中.为实现地址转换设盘了控制寄存器，其中存放的是在内存中的起始地址。4、I/O设备按信息存取的单位进行分类，可分成块设备和字符设备.磁盘展丁设备，其I/O控制主要采用控制方式。答案写在答题纸上，弓在试卷上无效第1页（共2页）二、问答题（共3小题,每小题5分，共15分）1. （5分）在创建一个进程时，操作系统需耍完成的主要】作是什么？2. （5分）操作系统中存在着哪三级调度，它们各有何作用？3. （5分）文件物理结构中存在哪三种结构？各有何优劣？三、综合题（共3小题，共40分）1、（15分）若某系统采用分页式存储管理方式，页表放任内存中，系统中设有快表（TLB）

5、 o（1）画出该内存管理系统的逻辑地址到物理地址的转换示意图。（2）页面人小为4KB,逻辑地址空间为24KB,页表的内容如卜农：页号帧号01A50010002B20005C30006A40008F53FD00则逻辑地址0x3005转换成物理地址为多少？给出计算过程（Ox农示十六进制数，物理地址结果要求也 以十六进制表示）。（3）如果访问一次内存耍1.5ns,快表的命中率为85%,竇找快表的时间为0.5ns。计算该系统的有效i力问 时间。2、（15分）磁掀共有200个柱面（0、199）,它刚刚从92号磁道移到98号磁道完成渎吗，假设此时系统中 鄭待访问磁盘的磁道序列为:190,97,90,45,

6、150,32,162,108,112,80。试给出采用下列算法肩磁头移动的顺序并计算寻道距离。1） FCFS 算法;2SSTF 算法;3） SCAN 算法;4） C-SCAN 算法;5） LOOK 算法3. （10分）现有输入进程PA、计算进程PB、输出进程PC并发执行。三个进程共享两个缓冲区。如图 所示：PA每次读入一个数据，放入到Bufferl中，Bufferl人小为N1。PB每次从Bufferl中拿出一个数据计 算，然后将结果放入Buffer2中，Buffer2人小为N2 PC每次从Buffer2中拿出一个数据进行输出。要求 釆用wait,signal（或P, V）操作,设査合适的同步机

7、制,保证这三个进程的同步执行。对Bufferl Buffer2 要求直斥访问。答案写在答题纸上，耳在试卷上无效第2页（共2页）浙江工商大学2014年硕士研究生入学考试试巻（A）卷考试科目：845计算机基础综合 总分：（150分）第一部分数据结构（75分）考试时间：3小时一、简答题（共5个小题，每小题6分，共30分1. 分析下面代码段的复杂度。i = sum = 0;while（ sum n ）1+;sum += i:若a、b、c依次压入堆栈，请写出所有可能的出栈序列。已知一个二叉树的中序遍历结果是TFXIRAMLPK,后序遍历结果是TXFIALMKPR。请画出 该二叉树。请简述散列函数中解决冲

8、突的常用方法。请写出下面无向图的邻接矩阵和邻接表。二、综合分析题（共3个小题，每题15分，共45分）1. 请设i 一个函数int IsMatch（char *expr）,来判别表达式中括弧（包括圆括弧（）、 方括弧、花搖弧三种）是否正确配对。若正确配对，输出1,否则输出0。2. 请设计一个算法判定两棵二叉树是否相似。两棵二叉树相似，满足：（1）如果它们都为 空或都只有一个节点；（2）如果它们左子树相似并且右子树相似。3. 一物流公司设在不同城市的中转站Z间的拓扑结构可用图来表示。假定图用邻接矩阵表 示，请设计一个算法，输出中转站Si到中转站Sj的所有简单路径（简单路径是指路径上的 顶点不垂复）

9、。答案写在答题纸上，写在试卷上无效第1页（共3页）第二部分 操作系统（75分）一、简答题（共4个小题，每小题5分，共20分）1. 简述操作系统中进程的构成，它与程序的区别？2. 死锁发生的四个必要条件是什么？3. 简述文件在物理介质上的三种存放方式，并分析它们的优点及缺点。4. 简述CPU调度中可能出现的护航效应。二、综合分析题（共4个小题，共55分）1. （10分）若干个等待访问磁盘者依次要访问的磁道为20, 44, 40, 4, 80, 12, 76,假设 每移动一个磁道需要3毫秒时间，移动臂当前位于41号磁道，请按下列算法分别写出访问 序列，并计算为完成上述各次访问总共花费的寻逍时间。（

10、磁道编号从1到100）（1）先来先服务算法；（2）最短寻道时间优先算法。（3）扫描算法（当前磁头移动的方向为磁道递增）2. （15分）一个稈序具有460个字节，它的内存访问序列如下：1011104170 73 309185 245 246 434 458 364（1）若页面大小为100字节，请给岀正确的页号访问序列。（2）若物理内存具有200字节的有效空间，采用FIFO页面置换算法，请计算缺页次数， 并给出计算过程。（3）若物理内存貝有200字节的有效空间，采用LRU页面置换算法，请讨算缺页次数，并 给出计算过程。3. （15分）考虑系统中一组进稈，它们的CPU执行时间（CPU-burst t

11、ime单位：毫秒ms）和优先级（Priority）如下:ProcessBurst TimePriorityPl83P211P323P424P552假定0时刻进程按Pl, P2, P3, P4, P5的次序到达：（1）分别画出进程采用FCFS, SJF （最短作业时间优先），非抢占优先级（小的优先级数 表示具有髙的优先级），和RR （round robin, quantum=2ms）调度算法的甘特图。（2）计算每个迸程在（1）中各种调度算法的周转时间。（3）计算每个进程在（1）中各种调度算法的等待时间。（4）比较每个进程在（1）中各种调度算法中的平均周转时间，哪种调度算法最小？4. （15分）下

12、图是一个从键盘输入到打印机输出的数据处理流程图，其中键盘输入进程P1 通过缓冲区bufl （大小为m）把输入数据传送给计算进程，计算进程P2把处理结果通过 缓冲buf2 （大小为n）传送给打印进程P3。若buf2已装满数据，则计算进程丢弃新生成 的数据o bufl和buf2为临界资源，试写出键盘输入进程、计算进程及打卬进程间的同步 算法。输入进程一bufl -计算进程一buf2 打卬进程答案写在答题纸上，写在试卷上无效第3页（共3帀）浙江工商大学2013年硕士研究生入学考试试卷（A）卷考试科H： 845计外机基础综介总分：150分考试时间：3小时一、数据结构（共60分1. （12分）已知一个二

13、叉树的中序遍历结果是12543,后序遍历结果是12345。请画出这课二叉树。2. （12分）从结节点1开始,用Prim算法画出F图的最小生成树的过程.3. （12分）已知一个电报包含的字符为和工，它们出现的频率次数分别为（25, 9, 12, & 11 请给出字符的Huffman编码。4. （12分）12知一个整数序列（20 17 22 12 60 32 16 15 ,请画出快速排序的过程和最后的结果.5. （12分）诘构造旳数int fulKbtree *bt）.判断一颗叉树是否为满二叉树，是返冋1,否返回0。二、计算机组成（共45分）1. （9分应岀典型的冯诺依曼计算机硕件系统组成框图,并

14、简述各功能部件的作用.2. （9分）某机器字长为16位，请写出卜列各种情况卜它能表示的I-进制数的范围（采用I位符号位: （I）无符弓整数；（2）用补码表示的定点整数：（3）用5位阶码（含1位阶符）、11位尼码（禽1位数符）表示的规格化浮点数。3. （9分）已知Cache存取周期为30ns,左存存取周期为120ns.执行某段程序共访何Cache 5000次, 访阿主存200次，求：（1） Cache命中率；（2）平均内存访何时间.4. （9分）举例说明中断处理流程.5. （9分某机器中釆用RAM芯片8KX8组成16KX8的RAM区域,起始地址为8000H.假设RAM 芯片仃CS和WE （；号控

15、制瑞,CPU的地址总线为AjlAo,数据总线DtDo,控制伯号为R W. MREQ,（I）请设计地址译码方案：2）烦出RAM和CPU连接图。三、操作系统（共45分1. （8分）描述进程的三个基本状态以及它们之间转换的典2. （9分）在单道程序环境F若有四道作业，其进入系统及所需的执行时间如卜表所示:表1四道作业的进入和执行时间作业进入时何（小时）执行时间（小时）18228.50.539049.50.2答峑勺打:答頤纸卜.写#试静卜皿分别按先进先出算法、短作业优先算法、晌应比高者优先的调度算法调度，则其平均周转时间分别为多 少（上述三种算法均为非抢占方式）？3. （10分）有 个阅览空.滋者进入

16、时必须先在一张登记表上进彳j登记.该表为每 座位列 衣II，包 括座号和姓名,读者离开时要撤消登记们息：阅览宅共有100个座位,T阅览宅满员后,读者不得进入, 只能在室外等待。试用P、V操作写出上述何題的同步算法.（动作部分可用文字描述） 、.物理页号0511024374. 9分）某虚拟1?贮器的用户编穆空何氏32个页面，每页1 KB.上存为16 KB.假定某时刻用户页 表中已调入主存的页面的页号和物理块号（页架号）对照表为：何：（I）虚拟存貯器的功能是怎么实2）逻辑地址0A5C （H）、 1A5C （H）对应的物理地址分别为多少?（如果上存中找不到,即为页失效）5. （9分）假定系统中有五个进程P0, Pl. P2, P3. P4和三种类型的资源A, B