西北工业大学计算机学院81计算机专业基础历年考研真题汇编附答案59p

1、西北工业大学计算机学院801计算机专业基础历年考研真题汇编mTHROUGH TRFIIN最新资料，WORD式，可编辑修改!第一部分历年考研真题汇编 32004年西北工业大学计算机学院401计算机专业基础考研真题 3第二部分兄弟院校真题汇编 82014年电子科技大学820计算机专业基础考研真题 82013年电子科技大学820计算机专业基础考研真题 142013年电子科技大学820计算机专业基础考研真题及详解 222012年电子科技大学820计算机专业基础考研真题 312012年电子科技大学820计算机专业基础考研真题及详解 372011年电子科技大学820计算机专业基础考研真题 462011年电

2、子科技大学820计算机专业基础考研真题及详解 53说明：2004年西北工业大学计算机专业基础科目代码是 401, 2016年科目代码是 801,本书以此为准。止匕外，本书还收录了 4套兄弟院校计算机专业基础考研真题， 并提供详细答案。第一部分历年考研真题汇编2004年西北工业大学计算机学院401计算机专业基础考研真题试题编号：401第1页共3页西北工业大学2004年硕士研究生入学考试试题试题名称：计算机专业基础说明：所有答题一律写在答题答上;计算机组成原理共75分。丁、问答题（共10分）j 1.计算机系统的层次结构中，位于硬件之外的所有层次统称为什么？ （2分）! 2.冯诺依曼机工作方式的基本

3、特点是什么？ （2分）3 .将8个寄存器的内容送到一组输出线上，可使用八选一多路选择器，也可使 用三态门。问用八选一和用三态门实现，对开门信号的要求有什么不同。（4分）4 .在DMA的三种工作方式中，传送同样多的数据，哪种方式速度最快？（2分）匕简答题（共25分，每小题5分）1 .先行进位解决的问题及基本思想。2 .说明SRAM的组成结构，DRAM与SRAM在电路组成上有什么区别？3 .内存中存放着指令和数据，CPU如何从时间和空间上区分它们是指令还是数据？4 .分别从逻辑层和物理层说明提高总线性能的主要方法？5 .把外设接入计算机，必须解决哪些基本问题？通过什么手段来解决这些问 ：题？、计算

4、题（共40分，每小题10分，4和5小题任选一题）11.设CPU的主频为16MHZ,平均每条指令的执行时间为两个机器周期，每个机 ，周期由两个时钟脉冲组成。问：b存贮器为“o等待”，求机器速度。£假如每两个机器周期中有一个是访存周期，需插入1个时钟周期的等待时间,器速度。f/西/工业大学：200匹硕峋究,入学,试试题试蔻名称：计算机专业考6/试题编号：401巡明：所有答题一写在答题纸上,第2页共3页一£ 某机器采用两级流水线组织，第一级为取者、译码，需要200ns完成操作，j第二级为执行周期，大部分指令可在180ns内完成，但有两条指令要360ns才能 |完成。在程序运行时，

5、这类指令所占比例为510%。问：机器周期（一级流水线 |时间）应为多少？两条执行周期长的指令采用什么方法解决？I 3某流水线计算机有一个指令和数据合一的cache,已知cache的读/写时间为 20ns,主存的读/写时间为120ns,取指的命中率为98%,取数据的命中率为9册, |三执行程序时，约有1/5指令需要存/取一个操作数，假设指令流水线在任何时候 也不阻塞。问设置cache后，与无cache比较，运算速度可提高多少倍？ %.指令字长为16位，每个地址码为6位，采用扩展操作码的方式，设计15条 |二地址指令，100条一地址指令，110条零地址指令。请：I写出操作码的扩展过程。1画出指令译

6、码逻辑图。I算出操作码平均长度。f数值范围为1.0乂10±骂；有效数字为十进制七位；0的机器数为全 、据上述三条要求，设计一个尽可能短的浮点数格式（阶的底取2）。并写出十进 k-0.15625 的 IEEE754 编码。:据结构试题共75分。f简述题（25分）L什么是线性数据结构？有那些典型的线性数据结构？它们之间的共同点和不同 点有哪些？2.请简述在先序线索二叉树中查找指定节点直接前驱和在后序线索二叉树中试题编号：401第4页共3页/西北2004,年硕士彳款题名称：计算机专业基虬明：所有答题一律写在答题纸上1 查找指定节点直接后继的算法思想?3 .请简述算法、算法特征、算法复杂度以

7、及算法与数据结构之间的关系？4 .什么是拓扑序列？请简述拓扑排序的算法思想。5 .数据结构的存储方式有哪些？怎样描述？二、算法应用（20分）6 .已知关键字集合为310, 8, 27, 132, 6, 95, 18, 47）,请用快速排序和 堆排序的方法，对其进行升序排列，写出每趟的排序过程。I 7.已知二叉树的中序序列为BDCEAFHG、后序序列为DECBHCFA,请而出该叉I树并写出其先序序列。卜设计合理的数据结构并给出算法（30分）I 8.已知一个连通无向图，给出一个算法找出该图中一个哈密顿回路（回路中包I含该图的所有顶点一次且仅一次，除去首位顶点），并给出算法的时间复杂I度。2.编写一

8、个C语言的非递归程序实现判定两棵以二叉链表表示的二叉树是否相I等（相等是指结构相同并且对应节点的元素相等）。、第二部分兄弟院校真题汇编2014年电子科技大学820计算机专业基础考研真题共4页第1页电子科技大学2014年攻读硕士学位研究生入学考试试题考试科目：820计算机专业基础注：所有答案必须写在答题纸上，写在试卷或草稿纸上均无效。计算机操作系统、填空题（10分，每空2分）1 .现有3个同时到达的作业J1、J2和J3,它们的执行时间分别为T1、T2和T3,且T1 <T3<T2。若这三个作业在同一台处理器上以单道方式运行，则平均周转时间最小的执行顺序是2 .若一个信号量的初值是5,经

9、过多次P、V操作以后，其值变为3,则此时等待进入临 界区的进程数目是o3 .某基本分页存储管理系统具有快表，内存访问时间为2（15,检索快表的时间为0.5g5。 若快表的命中率为80%,且忽略快表更新时间，则有效访问时间是四。4 .在段页式存储管理系统中，若不考虑快表，为获得一条指令或数据，至少需要访问 次内存。5 .某虚拟存储器中的用户空间共有32个页面，每天1KB,主存16KBo假设某时刻系统为 用户的第0、1、2、3页分别分配的物理块为5、10、4、7,则虚拟地址0A6F对应的物 理地址是 （请使用十六进制表示）。:、选择题（14分，每题2分）I现代操作系统中最基木的两个特征是（）。A.

10、共享和不确定 B.并发和虚拟C.并发和共享D.虚拟和不确定2,引入多道程序技术的前提条件之,是系统具有（）oA.分时功能C.多CPU技术3.操作系统是根据（B.中断功能D. SPOOLing 技术）来对并发执行的进程进行控制和管理的。A.进程的基本状态B.进程调度算法C.进程的优先级D.进程控制块4,在段页式存储管理系统中，地址映射表是（）A.每个进程一张段表，一张页表。B.每个进程一张段表，每个段一张页表。C.每个进程的每个段,张段表，张贝衣。D.每个进程的每个段一张段表，多张页表。5.为使虚拟存储管理系统具有良好的性能，应用程序应具备的特征是（）oA.程序模块化程度高，由许多小模块组成B.

11、程序应具备良好的局部性特征C.程序的I/O操作较少D.程序实际大小应小于实际物理内存容量6 .（）的基本含义是指应用程序独立于具体使用的物理设备A.设备独立性B.设备共享性C.可扩展性D.SPOOLing技术7 .从用户的角度看，文件系统主要是实现（）A.数据存储B.数据保护C.数据共享D.按名存取三、分析计算题（30分）I.某操作系统的文件系统采用混合索引分配方式，索引节点中包含文件的物理结构数组 iaddr10o其中前7项iaddr0卜iaddr6为直接地址,iaddr7卜iaddr8为一次间接地址， iaddr9为二次间接地址。系统盘块的大小为4KB,磁盘的每个崩区大小也为4KB。描述

12、破盘块的数据项需要4个字节，其中1个字节标示磁盘分区，3个字节标示物理块。请【可 答一下问题：（1）该文件系统支持的单个文件的最大程度是多少？（8分）（2）若某文件A的索引节点信息已位了内存，但其它信息均在磁盘。现在需要访问文件 A中第i个字节的数据，列举出所有可能的磁盘访问次数，并说明原因。（6分）2. 3个进程P0、Pl、P2互斥使用一个仅包含1个单元的缓冲区。P0每次用produce。生成1 个正整数，并用put（）送入缓冲区。对于缓冲区中的每个数据，P1用getl（）取出一次并用 computed）计算其平方值，P2用get2（）取出一次并用compute2（）计算其立方值。请用信号

13、量机制实现进程P0、PI、P2之间的同步与互斥关系，并说明所定义信号量的含义，要求 用伪代码描述。（16分）四、简答题（21分）1 .在存储器管理中，什么是重定位？为什么要引入重定位技术？（5分）2 .在分页存储管理系统中，页表的主要作用是什么？现代大多数计算机系统都支持非常 大的逻辑地址空间（2322"）,这给页表设计带来了什么样的新问题，应如何解决。（5 分）3 .以从I/O设备读入数据为例，请用流程图方式说明程序I/O、DMA传输控制的处理过 程。（6分）4 .在哲学家就餐问题中，如果将先拿起左边筷子的哲学家成为左撇了，而将先拿起右边 筷子的哲学家称为右撇子。在同时存在左撇子和

14、后撇子的前提下，我们安排哲学家随 意就座。请问是否可能产生死锁，为什么？ （5分）数据结构一、填空题（共1Q分，每空1分）1 . 一个“好”的算法应考虑达到以下目标：正确性、可读性、健壮性、。2 .广义表（），（a）, （b,（c,d）,f）的深度是.3 .遍历二叉树实质上是对一个非线性结构进行 操作。4 .对有n个顶点、e条边且使用邻接表存储的有向图进行广度优先遍历，其算法复杂度 是 05 .若一个具有n个顶点，e条边的无向图是一个森林，则该森林中必有 棵树。6 .求图的最小生成树有两种算法，算法适合于求边稀疏的图的最小生成树。7 .最短路径迪杰斯特拉（Dijkstra）算法的复杂度。8 .

15、二义树上有一个结点的平衡因子的绝对值大于,则该二叉树就是不平衡的。9 .哈希表的地址区间为0为哈希函数为H （K） =K mod 9o采用线性探测法处理冲突,并 将关键字序列（12,21,43,5,39 ）依次存储到哈希表中，则元素39存放在哈希表中的地 址是 o10 . 排序算法不需要进行记录关键字间的比较。二、单选题（共2。分，每题2分）1 .某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采 用（）存储方式最节省运算时间。A.单链& B.仅有头指针的单循环链表C.双链表 D.仅有尾指针的单循环链表2 .下述哪一条是链式存储结构的优点？（）A.存储密度大

16、B.插入、删除运算方便C.存储单元连续D.随机存取第i个元素方便3 . 一个栈的输入序列为1 2 3 4 5 ,则下列序列中不可能是栈的输出序列的是（）oA. 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. （rear-1） MOD n=front5 .若一棵二叉树具有20个度为2的结点,10个度为1的结点，则度为0的结点个数是（）A. 10B. 1

17、1 C. 21 D. 306 .二叉树的第i层上最多有（）结点。A. 21B. 2I ,-1C. 2'-1D. 2"11. 一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定是（） A.完全二叉树B,只有一个节点C.高度等于其节点数D.二叉排序树8 .对图进行广度优先搜索遍历类似于二叉树的（）算法。A.先序遍历B.中序遍历C.后序遍历D,层次遍历共4页笫3页9 .对下图进行拓扑排序，可以得到不同拓扑序列的个数是(A. 6B.5C.4 D. 310 .有一组数据(43,21,52,60,1 2,1 5 )利用快速排序，以第一个元素为基准得到一次划分结 果为()

18、。A. (1 5,21,1 2,43,52,60 )8.( 1 5,1 2,21,43,52,60)C. (1 2,15,21,43,60,52 )0.( 15,21,12,43,60,52)三、简答题(30分，每题6分)1.画出算术表达式(2+1)1(。(1)(4八9)转换的二叉树。2,若通信系统中只可能出现5种字符A、B、C D和E其概率分别为统中、0.15、0.19、 0.21和0.33, (1)试设计赫夫曼编码：(2)画出相应的赫夫曼树。3,给出下图G的(1)邻接表表示图：(2)并根据而出的邻接表，以顶点1为根，画出深 度优先生成树。小4 .输入一个正整数序列(45,14,11,52,

19、63,32,56,24), (1)按此次序构造一颗二叉排序树：(2) 如果删除52,画出删除后的二叉树结构。5 .堆排序的基本思想是什么？其优点是什么？四、算法题(15分，共2题)1 .设计一个算法，逆序单链表中的数据。(5分)2 .采用二叉链表的存储结构，分别写出统计二叉树的叶子结点个数和树高的函数，并分别 分析时间及杂度。(10分)共4页第4页2013年电子科技大学820计算机专业基础考研真题2013年硕士研究生入学考试试题汇编3考试科目：820计算机专业基础注：所有答案必须写在答题纸上，写在试卷或草稿纸上均无效。计算机操作系统一、填空题（10分，每空2分）1 .文件目录是 的有序集合.2

20、 .某计算机系统中有11台打印机，由k个进程竞争使用,每个进程最多需要4台打印机。 该系统可能会发生死锁的k的最小值是.3 . 一个简单分段存储管理系统中，地址长度为32位，其中段号占12位，则最大段长是 字节.f4 .操作系统提供给应用程序的接口是5 .现代操作系统实现了设备无关性，应用程序使用 来请求使用某类设备。二、选择题（14分，每题2分）1 .进程调度时，下列进程状态的变化过程哪一项是不可能发生的？（）A.阻塞挂起-阻塞B.就绪挂起-就绪C.就绪挂起-阻塞挂起D.阻塞挂起-就绪挂起2 .关于线程和进程，下面说法正确的是（）A.终止一个进程比终止一个线程花费的时间少.B.进程切换比同一

21、进程内部的线程切换花费的时间少。.C.线程提高了不同执行程序间的通信效率。D.进程和线程都是资源分配和调度的基本单位.3 .下列事件最可能导致系统产生死锁的是（）.A.进程释放资源B. 一个进程进入死循环一C.多个进程竞争独占资源D.多个进程竞争共享资源4 .关于子进程和父进程的说法，下面哪一个是正确的？（）A. 一个父进程可以创建若干个子进程，一个子进程可以从属于若干个父进程B.父进程被撤销时，其所有子进程也被相应撤销cC.子进程被撤销时，其从属的父进程也被撤销.D. 一个进程可以没有父进程或子进程。5 .文件系统采用二级文件目录可以（）.A.缩短访问存储器的时间B.实现文件共享C.节省内存

22、空间D.解决不同用户间的文件命名冲突6 .一种既有利于短小作业又兼顾到长作业的作业调度算法是（）A.先来先服务,B.轮转C.最高响应比优先D.均衡调度7 .设计批处理多道系统时，首先要考虑的是（）.A.灵活性和可适应性B.系统效率和吞吐量C.交互性和响应时间D.实时性和可靠性三、分析计算题（30分）1 .考虑一个使用32位地址和1KB大小的页的分页虚拟内存系统，每个页表项需要32 , 位，限制页表的大小为一个页，请回答：（1）页表一共需要几级？（5分）（2）请设计每一级的页表大小，使得所需的页数个数总和最小。（8分）2 .桌上有一空盘，允许存放最多两个水果.爸爸可向盘中放草果或橘子，儿子专等吃

23、 盘中的橘子，女儿专等吃盘中的苹果e规定当盘子不满时，一次只能放一只水果；当盘子不 空时，一次只能取一只水果：父亲放水果时，儿子女儿不能取；儿子女儿取水果时，父亲不 能放。（1）请分析，本例中临界资源是什么？（1分）（2）下面是用P、V操作实现的爸爸、儿子、女儿三个进程的同步，请完成程序中的空行 部分（每空1分）.Semaphore mutex=_; 定义互斥信号量int empty=, apple=, orange=: 定义同步信号量 Father: 父亲进程 While（l）（Put an apple or orange;If (fruit=apple)Else80迎法期士研究生入学考试试

24、题汇编3Daughter: 女儿进程While(l)Fetch an apple;Son: 儿子进程Vhile(l) Fetch an orange;* ）四、简答题（21分）1 .操作系统中什么是虚拟存储器？为什么要引入虚拟存储技术？（5分）2 .考虑文件系统的外存分配，简述什么是连续分配方式和索引分配方式.（5分）3 .什么是DMA方式？它与中断方式的主要区别是什么？（6分）4 .简述利用位示图进行文件存储空间管理的思想.这种方法的优缺点是什么？ （5分）数据结构一、填空题（共10分，每空1分）.1 . 一颗有n个结点的二叉树，叶子结点的数所为nO,度为2的结点数限为n2,则nO与n2 的

25、关系是；如果用二叉链表存储该二叉树，则空指针数量为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条边，则邻接矩阵有 个。元素,其邻接矩阵812013年硕士研究生入学考试试题汇编3是对称矩阵，只需用 空间可实现压缩存储。6 .对二叉排序树 可以得到线性有序序列

26、.7 . 一个有向无环图的拓扑排序序列 是唯一的.二、单选题（共20分，每题2分）1 .从逻辑上可以把数据结构分为（）两大类.A.动态结构、静态结构B.顺序结构、链式结构C.线性结构、非线性结构 D.初等结构、构造型结构2 .以下数据结构中，（）是非线性数据结构A.树 B.字符串 C.队D.栈3 .设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用（）最节省时间.A.单链表 B.单循环链表C.带尾指针的单循环链表D.带头结点的双循环链表4 .对于旅序存储的线性表，访问结点和增加结点的时间复杂度为（）-A. 0（n） O（n） B. O（n） 0（1） C. 0（1） 0（n） D. 0

27、（1） 0（1）5 .对于队列操作数据的原则是（）.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.归并排序

28、B.直接插入排序 C.冒泡排序D.简单选择排序 一三、简答题（共30分，共5题）!已知4个字符A, B, C, D的霍夫曼编码分别是1, 01,000, 001 .下列01串是由以上4个字母构成的一段文本的霍夫曼编码:822013年硕士研究生入学考试试题汇编31001000011011010011010011请将上述01串还原为编码前的文本。以字符在文本中出现的次数为权值，求出这棵树的 带权路径长度。（共5分）2 .输入元素序列32, 18,63,5,1.11,44, 33, 78,请构造AVL树.假设所有元素的查找概率相 等，请分别求出这棵AVL树的查找成功的平均杳找长度ASL（成功）与失败

29、的平均查找长度 ASL（失败）.（共5分）3 .海量数据分布在100台电脑中，想个办法高效统计出所有数据的前10个最大关键字数据, 并分析时间复杂度（共6分）。4 .若输入数据存储在带头结点的双向循环链表中，下面各种排序算法是否仍然适用？为什 么？（共6分）（1）快速排序（2）直接插入排序（3）简单选择排序（4）堆排序5 .已知某工程各工序之间的优先关系和各工序所需的时间（其中“一”表示无先驱工序） 如下表所示.请根据工序表画出对应的A0E图，并指明完成该工程所需的最短时间和关 键路径.（共8分）工序代号ABCDEFGHI所需时间351466732先驱工序AAABBDG四、算法题（共15分，共

30、2题）1 .线性表（aLa2,an）中元素递增有序且按顺序存储于计算机内的数组a中.要求设计一 算法用函数实现下列功能：（共10分）（1）用最少时间在表中查找值为x的元素；（2）若找到则将其与直接后继元素交换；（3）若找不到则将其插入表中使其表中元素仍然递增有序2 .假设Header指向如下循环单锌表，请问执行下列2个程序段后各自的输出结果是什么？ （共5分）Header832013年硕士研究生入学考试试题汇编3单链表结点定义如下： typedef struct node ( .int data;"struct node *next;Node. ptr, *List;第一个程序段pt

31、r p=Header;for(int i=0;i<5;i)( printfC 4<%dw tp->data)： p=p->next;p=p->next;)第二个程序段ptr p:Header;for(int i=0;i<5;i+)(printfC u%dn tp->data);p=p->next;p=p->next;ppnext;842013年电子科技大学820计算机专业基础考研真题及详解2013年硕士研究生入学考试试题汇编3参考答案：820计算机专业基础计算机操作系统一、填空题1 .文件控制块2 . 43 . 2a4 .系统调用5 .逻辑

32、设备名称二、选择鹿C C C D D C B,三、分析计算题（30分）.1.考虑一个使用32位地址和IKB大小的页的分页虚拟内存系统，每个页表项需要32 位，限制页表的大小为一个页，请回答：（1）答：由于页面大小占用lObit,还剩22bit,即有2”个页表项.一个页表项32bit,即 占用4个字节，一页最多含2%4=28个页表项，所以需要3级页表.（5分）（2）答：若一级页表长度为6位，二级和三级页表长度各为8位，则需要的页数总数为 1+26+2,4=16449：若一级页表长度为8位，二级页表长度为6位，三级页表长度为8位，则总 共需要页数为：1+28+2“=16641：若一级页表和二板页表

33、长度分别为8位，三级页表为6位， 则总共需要1+2422=65793页.因此，三级页表的长度分别为6, 8. 8时,总页数和最小.（9分）2.每格一分，共16分（1）临界资源是盘子（2） Semaphore mutexlj 定义互斥信号量int empty=_2_, appe=_0_, orange=_0_; 定义同步信号重 Father: 父亲班箱While（l）_P(enW)_P(mutex)_；Put an apple or orange;If (fruit=apple)_V(apple)_;Else一V(orange)_;)Daughter: 女儿进程Whilefl)(_PQpple)

34、_;_P(nmtex)_;Fetch an apple;_V(mutex)_;_V(empty)_;)Son: 儿子进程Whilst)P(orange)_;P(mutex);Fetch an orange; V(mutex);V(empty);四、筒答题（21分）1 .答：在具有层次结构存储器的计算机系统中，自动实现部分装入和部分替换功能，能 从违辑上为用户提供一个比物理贮存容量大得多，可寻址的“主存储器”,虚拟存储区的容量 与物理主存大小无关，而受限于计算机的地址结构和可用磁盘容量,.86 2013年硕士研生入学试试色汇编3计算机操作系统引入和使用虚拟存储技术的主要目的是提高系统的内存利用率

35、和系统吞 吐量（5分）2 .答：连续分配方式：在创建文件时需要给文件分配一组连续的盘块。连续分配的优点 主要有两个，分别是顺序访问文件时比较容易，并且喉序访问时速度快.缺点是要求有连续 的存储空间，并且随着外存空间的分配和回收，会产生很多外存碎片,降低了外存空间的利 用率.索引分配方式：为文件的每个分区单独建立一张索引表.该索引表记录了分配给该文件 的所有的块号。优点：直接访问和顺序访问的速度都比较快.缺点：存储索引表花费了较多 外存空间.（5分）3 .答：DMA是直接存储器存取.DMA传输将数据从一个地址空间更制到另外一个地址 空间.当CPU初始化这个传输动作，传输动作本身是由DMA控制器来

36、实行和完成,在实现 DMA传输时，是由DMA控制器直接掌管总线，因此，存在着一个总线控制权转移问题。即DMA 传输前，CPU要把总线控制权交给DMA控制器，而在结束DMA传输后，DMA控制器应立即把总 线控制权再交回给CPU.它和中断的主要区别在于，DMA只需要CPU在开始和完成传输时进行V 干预，其他时候不需要CPU干预.（6分）4 .答：若磁盘块空闲，则用1表示，否则用9表示.从而得到一张位式图表，反映了所 有磁盘块的信息。其优点在于很容易找到一个连续的空闲块.缺点在于整个磁盘的位式图文 件比较大；另外，在磁盘空闲快较少时，搜索空闲块要花费一些时间.15分）数据结构一、填空题（共10分，每

37、空1分）1 . n0=n2+l ;n+12 .相同（一样）3 .顺序；64 . O（nlogn）5 . n2-2e;n（n+l）/26 .中序遍历7 .不/不一定二、单选题（共20分，每题2分）1-5. CADCA 6-10.CCABA872QI3年硕I研究生入学考试试题汇编3三、简答题（共30分，共5题）L答：霍夫曼编码是前缀编码，满足任意字符的编码都不会是另外一个字符编码的前缀, 因此译码不会产生歧义。1001000011011010011010011还原出来的文本为：1 001 000 01 1 01 1 01 001 1 01 001 1AD CBABAB DABDA（2 分）其中A出

38、现5次.B出现4次，C出现1次，D出现3次，（2分）带权路径长度为WPL=（ 1+3） *3*4*2+5=25（1分）（3分）33782 .答：AVL树如下图所示.ASL（成功）=（1+2*2+4*3+2*4）/9=25/9（1 分）ALS（失败） = （3*6+4*4）/10=M/10=3.4（1 分）3 .答：先分别求出每台电脑的前10个最大关键字数据，再根据这100台电脑的最大前 10个最大关健字数据，共1000个数据求出前10大关度字数据即可。具体分析如下：（1）先求出每台电脑的前10大数据,由于只需要求出部分数据，因此不需要对n个数据 全部排序，采用部分排序算法即可，比如简单选择持序

39、、堆排序、桶排序.（1分）（2）求n个数据的前k （这里k=10）大数据，当K6时，最佳的方法是将后面的n-k个 数据依次与前面的k个数据的最小值比较，如果比最小值还小.则扔掉该数据，继续比较下 一个数据，否则扔掉更小的数据，把这个新数加入，支到余下的n-k个数据都处理完。由于 每次需要与存储的k个数据比较并可能删除城小元素，加入新的元素，最好的结构是小顶堆. 即将前k个元素调整为小顶堆（时间复杂度为0（khgk）,余下元素依次与小顶堆根结点比较, 比根结点小则扔掉，比根结点大则用当前值替换根结点并调整为小顶堆,或间曳杂度为 O（logk）.所以总的最坏时间复杂度为O（klogk）+O（nk）

40、 logk）=0（nlogk）（小顶堆1分，分析过程与时间复杂度分析共2分）（3）再从m（这里m=100）台电脑的共km（这里km=1000）个数据中选择所有数据的最大k个,采用类似的方法即可求出c即将一台电脑的小项堆作为初始小顶堆，余下nr1台电脑的最 大k个元素依次与小顶堆的根结点元素比较，大于根结点则替换根结点元素并调整为小项堆， 宜到余卜的数据都处理完成，时间且杂度为0(nH"logk) (1分)(4)综合上面3步，最终选择小项雄能够最快统计出所有数据的前k(k=10)个最大关键 字数据，总的最坏时间复杂度为、0(n 1 ogk) +0(nr 1)klogk) =0(n+mk

41、-k) 1 ogk).如果 k«km«n,则 T(n)=0(n)(1分)4. 9：(1)快速排序适用(0.5分)，因为可以快速定位到第一个元素与最后一个元素结点(0.5 分)，然后通过1个指针从头部向后移动，另外一个指针从尾部向前移动，逐一与枢纽进行比 较并能够通过修改指针完成结点交换操作(0.5分)(2)插入排序适用(0.5分)。因为可以方便的我前趋后继(0.5分)和通过修改指针完 成结点交换操作(0.5分)(3)选择排序适用(0.5分)，因为只需要移动指针遍历链表(0.5分)并通过修改指针 完成结点交换(0.5分)(4)堆排序不适用(0.5分)，因为双向循环错表无法方便

42、的找完全二叉树的双亲与孩子 结点(1分).则各个事件Vi(i=l, 2,6)的最早开始时间VE(i)和最晚开始时间VL(i)如我所示:事件iVIV2V3V4V5V6VE03571214VI045111214902013年硕士研究生入学考试试整汇编3各个活动的最早开始时间ae(i)与最晚开始时间al(i)如下表所示(3分):活动iABcDEFGHIae0033355712al10478851112所以，完成该工程所需最短时间为14天。关键羁径有：B,G,I(2分)四、算法题(共15分，共2题)1 .解：顺序存储的线性表递增有序，可以顺序查找也可以折半查找，题目要求“最少 时间查找值为X的元素”，

43、选用折半查找(2分).算法如下：*define status intttdefine true 1口define false 0status SearchExchangelnsert(ElemType a口，int *n» EleroType x) (int low=0,high=*n-l,nid, i;(1分)(2分)status sfalse： /数组长度检查 if(low>high)return s; if(*n<=0)return s;折半查找while(low<=high)(mid=(low+high) /2; if (a mid =x) (break：1

44、 else if(anid<x) (low=mid*l：else high:midT;) ) 查找成功(3分)if(low<=high)是否最后一个元素s=true;if (mid=*n-l) return s;不是最后一个元素，则与后继交换 araid=aniid+l：amid+l=x;I i else 查找失败(2分)(for( i=*n-l;i>=low；i) ai+l=ai;alov=x;(*n)+；)return s;）2 .答：（1）程序输出结果为：13524（2 分）（2）程序输出结果为：14253（3 分）922012年电子科技大学820计算机专业基础考研真题

45、电子科技大学2012年硕士研究生入学考试试跳汇编260考试科目：820计算机专业基础注：所有答案必须写在答题纸上，写在试卷或草稿纸上均无效。计算机操作系统 一、单项选择题（每小题2分，共14分） 页式存储管理系统中的页面大小是由（）决定的。A.用户 B.系统 C.系统和用户D.不确定下面哪一种表述不属于操作系统的主要功能？（）A.处理机管理B.存储器管理C.设备忏理和文件管理D,可移植下面哪一种描述不是操作系统的主要目标？（）A.有效性 B.方便性 C.可扩充性D.多路复用文件目录是（）的有序集合。B、文件信息D、文件属性A、文件控制块C、文件名文件系统采用二级文件目录可以（）A.缩短访问存储

46、器的时间B.节省存储空间C.节省内存空间D.解决不同用户间的文件命名冲突在一段时间内，只允许一个进程访问的资源被称为（）A.共享资源B.临界区 C.临界资源 D.共享区在单处理器系统中，如果同时存在有12个进程，则处于就绪队列中的进程数量最多为（）B.9 C. 10 D. 11二、填空邈（每空2分，共10分）1 .根据对截止时间的要求不同，实时任务可以划分为硬实时任务和（）.2 .重定位是指程序的虚地址到（）的转换，根据定位时机可分为（）和（）两种.3 .文件的物理分配方法包括连续分配、链式分配和（）.三、简答题（共21分）L什么是顺序文件？试说明顺序文件的优点和缺点.（4分）2 .阐述什么是

47、SPOOLING技术.（4分）3 .什么是死锁？如何预防死锁？（4分）4 .阐述基本分虫存储管理和请求分贝存储管理的异同之处。（5分）5 .阐述计算机系统中缓冲的作用和分类（4分）四、计算题（30分）1 .在请求式分页管理系统中，某一作业有4个页面，分别被装入到内存的3, 4, 6, 8号页 框中，假设页面和页框的大小都为1024字节，当该作业在CPU上运行时，执行到其地址空间电子科技大学2012年硕士研究生入学考试试题汇编2第500号处遇到一条传送指令MOV 2200 3100,请计算出MOV指令中两个操作数的物理地址， 并给出计算过程.（8分）2 .磁盘共有200个柱面，其编号为0-199

48、,假定磁头正停在99号柱面上访问.现有一个请求 队列在等待访问柱面，该请求队列访问的柱面号分别为：190、97、54、30、87.若采用FCFS（先来先服务）和SSTF （最短寻道时间优先）的磁盘调度算法，清分别计算破头移动的总磁 道数.（10分）3 .针对下面进程集合，考虑两种调度算法：先来先服务和最短进程优先。分别计算各个进程 的周转时间、带权周转时间以及平均周转时间和平均带权周转时间。请完成下列两个表格， 并说明哪种调度算法性能好？ （12分）进程名到达时间处理时间P103P215P332P484P5105先来先服务:进程到达时间处理时间完成时间周转时间带权周转 时间平均周转 时间平均带

49、权周转时间P103P215P332P484P5105最短进程优先:进程到达时间处理时间完成时间周转时间带权周转 时间平均周转 时间平均带权 周转时间P103P215P332P484P5105数据结构一、单项选择题（20分，每题2分）:下面算法的时间豆杂度是（）ofor （i=n：i>l; i-）for （j=i-l;j>l; j-）x+;A. 0（n）B. 0（n2） C. 0（n （n-1） D. O（nlogn）以下数据结构中，（）是非线性数据结构。A.图 B.字符串 3、链表不具有的特点是（）. A.插入、删除不需要移动元素 C.可随机访问任一元素C.数组D.堆栈B.不必事先

50、估计存储空间D.所需空间与线性表长度成正比4、一个栈的输入序列为123n,若输出序列的第一个元素是n,输出的第i （K=i=n）个 元素是（）0A.不确定 B. n-iC. iD. n-i+15、若一棵二叉树具有12个度为2的结点，6个度为1的结点，则度为0的结点个数是（）。A. 10 B. 11C. 13D,不确定.6、下列哪种算法使用了队列作为辅助存储结构（）oA.二叉树的先根序遍历算法 B.二叉树的层次遍历算法C.图的深度优先遍历算法D.图的拓扑排序算法7、以下哪种二叉树左右子树可以交换（）oA.二叉排序树B.线索二叉树C.平衡二叉树D.哈夫曼树8、下列哪种图的邻接矩阵是对称矩阵（）。A

51、.有向图B.无向图C.AOV网D. AOE网9、在长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（假定 查找每个元素的概率均相等）为（）oA. nB. （n-1 ）/2C. n/2D. （n+l）/210、下列排序算法中，（）在某趟排序结束后不一定能选出一个元素放到其最终的位置上。A.选择排序B.冒泡排序 C.希尔排序 D.堆排序二、填空题（10分，每空2分）：1、判定循环队列的满与空，有三种方法，它们是，和。2、一颗第5层有6个叶子节点的完全二叉树，最多可能拥有的结点个数为。3、在无权的无向图G的邻接矩阵A中，若（%,%）属于图G的边集合，则对应元素 等于。三、简答题

52、（30分）：试描述堆栈和递归的关系。（5分）2、己知二叉树的中序遍历序列为DEBAFCG,后序遍历序列为EDBFGCA,试画出该二叉树（7分）电子科技大学2012年硕士研究生入学考试试题汇编23、给定25个字符组成的电文：(6分)DDDDAAABEEAAFCDAABCCCBADD试为字符A、B、C、D、E、F设计哈夫曼(Huffman)编码.(1)画出相应的哈夫曼树；(2)分别列出A、B、C、D、E、F的哈夫蛀编码；(3)计算该树的带权路径长度WPL.4、已知带权图G如图所示，试用Prim算法构造对应的蚊小生成树，请给出构造步骤。(7分)5、一个线性表为 B=( 14, 23, 43, 52,

53、 20, 35, 79, 31, 17, 36),设散列表为 HT0. 20, 散列曲数为H(key);key % 11并用线性探测法解决冲突(增量&=1, 2)，试写出散列表。(5分)四、算法设计题(15分)：如果以二叉链表做为存储结构，试用类C语言编写统计二叉树非叶子结点个数的层次遍历算 法。(15分)632012年电子科技大学820计算机专业基础考研真题及详解电子科技大学2012年硕士研究生入学考试试题汇编2参考答案：820计算机专业基产计算机操作系统 选择题l.B 2.D3.D4. A 5.D6.C7. D填空题1 .软实时任务2 .物理地址，静态重定位，动态重定位3 .索引分配 简答题 顺序文件是指由一系列记录按照某种顺序排列所形成的文件.顺序文件的优点在于当需要对 记录进行批量存取时，它的存取效率最高。其缺点在于当文件较大时，记录的检索效率较低。 另一个缺点是记录的增加和删除比较困难。SPOOLING技术是同时联机外围操作技术的简称。它是关于慢速字符设备如何与计算机主机进 行数据交换的一种技术，通常又称假脱机技术。在多道程序环境下，利用多道程序中的一道 或者两道程序来模拟脱机输