电子科技大学820计算机专业基础历年考研真题及详解附答案.pdf

电子科技大学820计算机专业基础历年考研真题及详解郃THROUGH TRFtIN最新资料，WORD格 式，可编辑修改!第1页目 录2014年电子科技大学820计算机专业基础考研真题.错误味定义书签。2013年电子科技大学820计算机专业基础考研真题.82013年电子科技大学820计算机专业基础考研真题及详解.162012年电子科技大学820计算机专业基础考研真题.252012年电子科技大学820计算机专业基础考研真题及详解.312011年电子科技大学820计算机专业基础考研真题及详解.402010年电子科技大学820计算机专业基础考研真题及详解.522008年电子科技大学820计算机专业基础考研真题及详解.642007年电子科技大学413计算机专业基础考研真题及详解.752006年电子科技大学413计算机专业基础考研真题及详解.842005年电子科技大学计算机专业基础考研真题及详解.922003年电子科技大学429计算机专业基础考研真题.104说 明：电子科技大学计算机专业基础专业的科目代码2003年是429,2005年不详,2006年改为413,2008年改为820.电子科技大学信息与软件工程学院、计算机科学与工程学院、电子科学技术研究院、自动化工程学院均考此科目。第2页电子科技大学2014年攻读硕士学位研究生入学考试试题考试科目：820计算机专业基础注：所有答案必须写在答题纸上，写在试卷或草稿纸上均无效。计算机操作系统一、填 空 题（10分，每空2分）1.现有3个同时到达的作业J1、J2和J3,它们的执行时间分别为T l、T2和T3,且T1 T3T2.若这三个作业在同一台处理器上以单道方式运行，则平均周转时间最小的执行顺序是_O2.看二个信号量的初值是5,经过多次P、V操作以后，其值变为-3,则此时等待进入临界区的进程数目是。3.某基本分页存储管理系统具有快表，内存访问时间为2,检索快表的时间为0.5 J15 若快表的命中率为8 0%,且忽略快表更新时间，则有效访问时间是_ _ _ _4.在段页式存储管理系统中，若不考虑快表，为获得一条指令或数据，至少需要访问次内存。5.某虚拟存储器中的用户空间共有32个页面，每 页1K B,主 存16KB。假设某时刻系统为用户的第0、1、2、3页分别分配的物理块为5、10、4、7,则虚拟地址0A6F对应的物理地址是（请使用十六进制表示）.二、选 择 题（14分，每题2分）1.现代操作系统中最基本的两个特征是（）.A.共享和不确定 B.并发和虚拟C.并发和共享 D.虚拟和不确定2.引入多道程序技术的前提条件之一是系统具有（）.A.分时功能C.多CPU技术3.操作系统是根据（A.进程的基本状态B.中断功能D.SPOOLing 技术来对并发执行的进程进行控制和管理的。B.进程调度算法C.进程的优先级D.进程控制块4.在段页式存储管理系统中，地址映射表是（）A.每 个 进 程 张 段 表，张页表。B.每个进程一张段表，每个段一张页表。C.每个进程的每个段一张段表，一张页表.D.每个进程的每个段-张段表，多张页表。共 4 页第 1页第3页5.为使虚拟存储管理系统具有良好的性能，应用程序应具备的特征是（）.A.程序模块化程度高，由许多小模块组成B.程序应具备良好的局部性特征C.程序的I/O操作较少D.程序实际大小应小于实际物理内存容量6.（）的基本含义是指应用程序独立于具体使用的物理设备A.设备独立性 B.设备共享性C.可扩展性 D.SPOOLing技术7.从用户的角度看，文件系统主要是实现（）A.数据存储 B.数据保护C.数据共享 D.按名存取三、分析计算题（30分）1.某操作系统的文件系统采用混合索引分配方式，索引节点中包含文件的物理结构数组iaddr10 其中前 7 项 iaddr0iaddr6为直接地址,iaddr7iaddr8为一次间接地址,iaddr9为二次间接地址。系统盘块的大小为4 K B,磁盘的每个扇区大小也为4KB。描述磁盘块的数据项需要4个字节，其 中1个字节标示磁盘分区，3个字节标示物理块。请回答一下问题：（1）该文件系统支持的单个文件的最大程度是多少？（8分）（2）若某文件A的索引节点信息已位于内存，但其它信息均在磁盘。现在需要访问文件A中第i个字节的数据，列举出所有可能的磁盘访问次数，并说明原因。（6分）2.3个进程P0、P l、P2互斥使用一个仅包含1个单元的缓冲区。P0每次用produce。生 成I个正整数，并 用put。送入缓冲区。对于缓冲区中的每个数据，P I用getl（）取出一次并用computed）计算其平方值,P 2用gct2（）取出一次并用compute2（）计算其立方值。请用信号量机制实现进程P0、P l、P2之间的同步与互斥关系，并说明所定义信号量的含义，要求用伪代码描述.（16分）四、简 答 题（21分）1.在存储器管理中，什么是重定位？为什么要引入重定位技术？（5分）2.在分页存储管理系统中，页表的主要作用是什么？现代大多数计兑机系统都支持非常大的逻辑地址空间（2322M）,这给页表设计带来了什么样的新问题，应如何解决。（5分）3.以从I/O设备读入数据为例，请用流程图方式说明程序1/0、D M A传输控制的处理过程。（6分）4.在哲学家就餐问题中，如果将先拿起左边筷子的哲学家成为左撇子，而将先拿起右边筷子的哲学家称为右撇子。在同时存在左撇子和右撇子的前提下，我们安排哲学家随意就座。请问是否可能产生死锁，为什么？（5分）共 4页第2页 数据结构一、填 空 题（共1 0分，每 空1分）1.一 个“好”的算法应考虑达到以下目标：正确性、可读性、健壮性、e2.广义表（），埼），（，（:,0）/）的深度是.3.遍历二叉树实质上是对一个非线性结构进行 操作。4.对有n个顶点、e条边且使用邻接表存储的有向图进行广度优先遍历，其算法复杂度是。5.若一个具有n个顶点，e条边的无向图是一个森林，则该森林中必有 棵树。6.求图的最小生成树有两种算法，算法适合于求边稀疏的图的最小生成树。7.最短路径迪杰斯特拉（D ijk stra）算法的复杂度。8.二叉树上有一个结点 的 平 衡 因 子 的 绝 对 值 大 于,则该二叉树就是不平衡的。9.哈希表的地址区间为0为 哈希函数为H（K）=K mod 9。采用线性探测法处理冲突,并将关键字序列（1 2,21,43,5,39）依次存储到哈希表中，则元素3 9存放在哈希表中的地址是.10.排序算法不需要进行记录关健字间的比较。二、单 选 题（共2 0分，每题2分）1.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。A.单链表 B.仅有头指针的单循环链表C.双链表 D.仅有尾指针的单循环链表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的循环队列，队尾指针是r e a r,队头是f r o n t,则队满的条件是（A.（rear+1）MOD n=front B.rear=frontC.rear+1=front D.（re a r-l）MOD n=front5.若一棵二叉树具有2 0个度为2的结点，1 0个度为1的结点，则度为0的结点个数是（）A.10 B.11 C.21 D.306.二叉树的第i层上最多有（）结点。A.2 B.2-1 C.2-1 D.27.一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定是（）A.完全二 叉 树B.只 有 一 个 节 点C.高度等于其节点数D.二叉排序树8.对图进行广度优先搜索遍历类似于二叉树的（）算法。A.先序遍历 B.中 序 遍 历C.后 序 遍 历D.层次遍历共 4 页第3页对下图进行拓扑排序，可以得到不同拓扑序列的个数是（A.6 B.5 C.4 D.31 0.有一组数据（43,21,52,60,1 2,1 5 ）利用快速排序，以第一个元素为基准得到一次划分结果为（）.A.（15,21,12,43,52,60）8.（15,12,21,43,52,60）C.（12,1 5,21,43,60,52）0.（15,21,12,43,60,52）三、简 答 题（30分，每题6分）1.画出算术表达式9+，（；-（1）（6+9）转换的二叉树。2,若通信系统中只可能出现5种字符A、B、C D和E其概率分别为0.12、0.15、0.19、0.21和0.33,（1）试设计赫夫曼编码；（2）画出相应的赫夫曼树。3,给出下图G的（1）邻接表表示图：（2）并根据画出的邻接表，以顶点1为根，画出深度优先生成树。小4.输入一个正整数序列（45,14,11,52,63,32,56,24）,（1）按此次序构造一颗二叉排序树：（2）如果删除5 2,画出删除后的二叉树结构。5.堆排序的基本思想是什么？其优点是什么？四、算 法 题（15分，共2题）1.设计一个算法，逆序单链表中的数据。（5分）2.采用二叉链表的存储结构，分别写出统计二叉树的叶子结点个数和树高的函数，并分别分析时间复杂度。（10分）共4页笫4页第7页2013年电子科技大学820计算机专业基础考研真题第8页2（H3 年硕士研究生入学考试试题汇编3考试科目：8 2 0 计算机专业基础注：所有答案必须写在答题纸上，写在试卷或草稿纸上均无效。计算机操作系统一、填 空 题（10分，每空2 分）1.文件目录是_ _ _ _ 有序集合.2.某计算机系统中有11台打印机，由 k 个进程竞争使用，每个进程最多需要4 台打印机。该系统可能会发生死锁的k 的最小值是.3.一个简单分段存储管理系统中，地址长度为32位，其中段号占12位，则最大段长是_字节.4.操作系 统提供给应用程序的接口是.5.现代操作系统实现了设备无关性，应用程序使用 来请求使用某类设备。二、选 择 期（14分，每题2 分）1.进程调度时，下列进程状态的变化过程哪一项是不可能发生的？（）A.阻塞挂起-阻塞 B.就绪挂起-就绪C.就绪挂起-阻塞挂起 D.阻塞挂起-就绪挂起2.关于线程和进程，下面说法正确的是（）A.终止一个进程比终止一个线程花费的时间少.B.进程切换比同一进程内部的线程切换花费的时间少.-C.线程提高了不同执行程序间的通信效率.D.进程和线程都是资源分配和调度的基本单位.3.下列事件最可能导致系统产生死锁的是（）.A.进程释放资源 B.一,个进程进入死循环 一C.多个进程竞争独占资源 D.多个进程竞争共享资源4.关于子进程和父进程的说法，下面哪一个是正确的？（）A.一个父进程可以创建若干个子进程，一个子进程可以从属于若干个父进程B.父进程被撤销时，其所有子进程也被相应撤销。792013年硕士研究生入学考试试题汇编3C.子进程被撤销时，其从属的父进程也被撤销.D.一个进程可以没有父进程或子进程.5 .文件系统采用二级文件目录可以（）.A.缩短访问存储器的时间 B.实现文件共享C.节省内存空间 D.解决不同用户间的文件命名冲突6 .一种既有利于短小作业又兼顾到长作业的作业调度算法是（）A.先来先服务 B.轮转C.最高响应比优先 D,均衡调度7 .设计批处理多道系统时，首先要考虑的是（）.A.灵活性和可适应性 B.系统效率和吞吐量C.交互性和响应时间 D.实时性和可靠性三、分析计 算 题（3 0 分）1 .考虑一个使用3 2 位地址和1 KB 大小的页的分页虚拟内存系统，每个页表项需要3 2位，限制页表的大小为一个页，请回答：（1）页表一共需要几级？（5 分）（2）请设计每一级的页表大小，使得所需的页数个数总和最小。（8分）2 .桌上有一空盘，允许存放最多两个水果.爸爸可向盘中放苹果或橘子，儿子专等吃盘中的橘子，女儿专等吃盘中的苹果,规定当盘子不满时，一次只能放一只水果；当盘子不空时，一次只能取一只水果：父亲放水果时，儿子女儿不能取：儿子女儿取水果时，父亲不能放。（1）请分析，本例中临界资源是什么？（1 分）（2）下面是用P、V 操作实现的爸爸、儿子、女儿三个进程的同步，请完成程序中的空行部 分.（每空1 分）*Semaphore mutex=_;定义互斥信号量int empty;_,apple=_,orange=_:定义同步信号量 F ather:父亲进程While（l）Put an apple or orange;If(fruit-apple)E lse802013年硕士研究生入学考试试题汇编3)D a u g h t e r:女儿进程W h i l e(l)F e t ch a n a p p l e;)S o n:儿子进程W h i l e(l)F e t ch a n o r a n g e：）四、简答题（2 1分）1 .操作系统中什么是虚拟存储器？为什么要引入虚拟存储技术？（5分）2 .考虑文件系统的外存分配，简述什么是连续分配方式和索引分配方式.（5分）3 .什么是D M A方式？它与中断方式的主要区别是什么？（6分）4 .简述利用位示图进行文件存储空间管理的思想。这种方法的优缺点是什么？（5分）数据结构一、填空题（共1。分，每空1分）“1 .一颗有n个结点的二叉树，叶子结点的数量为n 0.度为2的结点数量为n 2,则n 0与n 2的关系是：如果用二叉链表存储该二叉树，则空指针数量为.2.一个有 向 图 的 邻 接 表 和 逆 邻 接 表 中 结 点 的 个 数 .3.将101,18 6.16,16 3,7 5 2,334,6 1等7个数据存入长度为1 0的线性 施。哈希函数h（K）=K%7 ,解决冲突策略为线性探测再散列，则采用 存储结构存储数据，其中16 3存储在哈希表的第 个位置（H（k）=O为第1个位置）.4.输入n个数据，2路 归 并 排 序 的 时 间 复 杂 度 为 .5 .无向图G=（V,E）,有n个顶点，e条边，则邻 接矩阵有 个0元素，其邻接矩阵8)2013年硕士研究生入学考试试题汇编3是对称矩阵，只需用 空间可实现压缩存储。6.对二叉排序树 可以得到线性有序序列。7.一个有向无环图的拓扑排序序列 是唯一的.二、单选题(共2 0分，每题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.对于队列操作数据的原则是()。A.先进先出 B.后进先出 C.先进后出 D.不分顺序6.要保证连通具有10个顶点的无向图，至少需要()条边。A.9 B.90 C.37 D.457.设栈的初始状态为空，当字符序列a3一作为栈的输入时，输出长度为3的且可以用作C语言标识符的字符序列有()个A.4 B.6 C.3 D.58.完全二叉树采用()存储结构，满足存储空间少，方便的查找任意结点的双亲与孩子.A.顺序 B,单链表 C.二叉链表 D.三叉链表9.下面()数据结构常用于函数调用。A.队列 B.栈 C.链表 D.数组10.下 面()排序算法在输入数据逆序情况下排序速度最快。A.归并排序 B.直接插入排序 C.冒泡排序 D.简单选择排序 一 ,三、简答题(共3 0分，共5题)1.已知4个字符A,B,C,D的霍夫曼编码分别是1,01,000,0 0 1.下列0 1串是由以上4个字母构成的一段文本的霍夫曼编码:822013年硕士研究生入学考试试题汇编31001000011011010011010011请将上述01申还原为编码前的文本。以字符在文本中出现的次数为权值，求出这棵树的带权路径长度.（共5分）2.输入元素序列32,18.63.5,1,11,44,33,78,请构造AVL树.假设所有元素的查找概率相等，请分别求出这棵AVL树的查找成功的平均查找长度ASL（成功）与失败的平均查找长度ASL（失败）.（共5分）3.海量数据分布在100台电脑中，想个办法高效统计出所有数据的前10个最大关键字数据，并分析时间熨杂度（共6分）.4.若输入数据存储在带头结点的双向循环链表中，下面各种排序算法是否仍然适用？为什么？（共6分）（1）快速排序（2）直接插入排序（3）简单选择排序（4）堆排序5.已知某工程各工序之间的优先关系和各工序所需的时间（其中“一”表示无先驱工序）如下表所示.请根据工序表画出对应的A0E图，并指明完成该工程所需的最短时间和关键路径.（共8分）工序代号ABCDEFGHI所需时间351466732先驱工序 AAABBDG四、算法题（共15分，共2题）1.线性表（al,a2,an）中元素递增有序且按顺序存储于计算机内的数组a中.要求设计一算法用函数实现下列功能：（共10分）-（1）用最少时间在表中查找值为x的元素；（2）若找到则将其与直接后继元素交换；（3）若找不到则将其插入表中使其表中元素仍然递增有序2.假设Header指向如下循环单链表，请问执行下列2个程序段后各自的输出结果是什么？（共5分）Header832013年硕士研究生入学考试试题汇编3单链表结点定义如ty pedef struct node(int data;struct node*next;Node,*prr,*List;第一个程序段ptr p=H eader;for(int i=0;i data);p=p-next;p=p-next：)第二个程序段ptr p=H eader;for(int i=0;i data);p=p-next;p=p-next;p=p-next;)84加K第1 5页2013年电子科技大学820计算机专业基础考研真题及详解第 1 6 页2013年硕士研究生入学考试试题汇编3参考答案：820计算机专业基础_ 计算机操作系统一、填空题1.文件控制块2.43.24.系统调用5.逻辑设备名称二、选择题C C C D D C B三、分析计算题（30分）1.考虑一个使用3 2位地址和1KB大小的页的分页虚拟内存系统，每个页表项需要32位，限制页表的大小为一个页，请回答：（1）答：由于页面大小占用lO bit,还剩2 2b it,即 有 个 页 表 项.一个页表项32b it,即占用4个字节，一页最多含2忖/4=28个页表项，所以需要3级页表.（5分）（2）答：若一级页表长度为6位，二级和三级页表长度各为8位，则需要的页数总数为1+2S+2,4-1 6 4 4 9：若一级页表长度为8位，二级页表长度为6位，三级页表长度为8位，则总共需要页数为：1+28+21=16641；若一级页表和二级页表长度分别为8位，三级页表为6位，则总共需要1+28+2”=65793页.因此，三级页表的长度分别为6,8.8时，总页数和最小.（9 分）-2.每格一分，共16分（1）临界资源是盘子（2）Semaphore mutcx=_l_;定义互斥信号量int empty=_2_,apple=_0_,orange=_0_;定义同步信号量 Father 父亲母8While（l）P(erqty).852 0 1 3 年硕上研究生入学考试试题汇编3_ P(mutex)_;Put an apple or orange;If(fruit=apple)一V(apple)_;日se_ V(orange)_;)D aughter:女儿进程.While(l)(_P(apple)_；_ P(mutex)_;F etch an apple;_V(mutex)_;_V(empty)_;Son:儿子进程WhH e(l)(_ P(orange)_;_ P(mutex)_;F etch an orange;_ _V(mutex)_;_V(empty)_;)四、简答题(2 1分)1.答：在具有层次结构存储器的计算机系统中，自动实现部分装入和部分替换功能，能从逻辑上为用户提供一个比物理贮存容量大得多，可寻址的“主存储器-虚拟存储区的容量与物理主存大小无关，而受限于计算机的地址结构和可用磁盘容量。.8 62013年硕士研究生入学考试试题汇编3计算机操作系统引入和使用虚拟存储技术的主要目的是提高系统的内存利用率和系统吞吐 量（5 分）2.答：连续分配方式：在创建文件时需要给文件分配一组连续的盘块。连续分配的优点主要有两个，分别是顺序访问文件时比较容易，并且顺序访问时速度快.缺点是要求有连续的存储空间，并且随着外存空间的分配和回收，会产生很多外存碎片.降低了外存空间的利用率.索引分配方式：为文件的每个分区单独建立一张索引表。该索引表记录了分配给该文件的所有的块号。优点：直接访问和顺序访问的速度都比较快。缺点：存储索引表花费了较多外存空间。（5 分）3.答：D M A 是直接存储器存取,DMA传输将数据从一个地址空间复制到另外一个地址空 间.当 C P U 初始化这个传输动作，传输动作本身是由DMA控制器来实行和完成.在实现DMA传输时，是由DMA控制器直接掌管总线，因此，存在着一个总线控制权转移问题.即DMA传输前，CP U要把总线控制权交给DMA控制器，而在结束DMA传输后，DMA控制器应立即把总线控制权再交回给CP U.它和中断的主要区别在于，DMA只需要CP U在开始和完成传输时进行丁干预，其他时候不需要CP U干预.（6 分）4.答：若磁盘块空闲，则用1 表示，否则用0 表示.从而得到一张位式图表，反映了所有磁盘块的信息。其优点在于很容易找到一个连续的空闲块.缺点在于整个磁盘的位式图文件比较大；另外，在磁盘空闲快较少时，搜索空闲块要花费一些时间.（5 分）数据结构一、填空题（共 10分，每空1 分）1.n0=n2+l;n+12.相 同（一样）3.顺序；6-4.O（nlogn）5.n!-2e:n（n+l）/26.中序遍历7.不/不一定 二、单选题（共 20分，每题2 分）1-5.CADCA 6-10.CCABA872013年硕士研究生入学考试试题正编3三、简答题（共 3 0 分，共 5 题）1 .答：霍夫曼编码是前缀编码，满足任意字符的编码都不会是另外一个字符编码的前缀,因此译码不会产生歧义.1 0 0 1 0 0 0 0 1 1 0 1 1 0 1 0 0 1 1 0 1 0 0 1 1 还原出来的文本为：1 0 0 1 0 0 0 0 1 1 0 1 1 0 1 0 0 1 1 0 1 0 0 1 1AD CBABAB DABDA（2 分）其中A出现5次，B出现4 次，C出现1 次，D出现3次，（2分）带权路径长度为期L=（l+3）*3+4*2+5=2 5 （1 分）2 .答：A VL树如下图所示.（3 分）A SL（成功）=（1+2*2+4*3+2*4）/9=2 5/9（1 分）A LS（失败）=（3*6+4*4）/1 0=3 4/1 0=3.4 （1 分）3 .答：先分别求出每台电脑的前1 0 个最大关键字数据，再根据这1 0 0 台电脑的最大前1 0 个最大关键字数据，共 1 0 0 0 个数据求出前1 0 大关键字数据即可。具体分析如下：（1）先求出每台电脑的前1 0 大数据.由于只需要求出部分数据，因此不需要对n 不数据全部排序，采用部分排序算法即可，比如简单选择排序、堆排序、桶排序.（1 分）（2）求 n 个数据的前k（这里k=1 0）大数据，当k n 时，最佳的方法是将后面的n-k个数据依次与前面的k 个数据的最小直比较，如果比最小值还小.则扔掉该数据，继续比较下一个数据，否则扔掉更小的数据，把这个新数加入，直到余下的n-k 个数据都处理完。由于每次需要与存储的k个数据比较并可能删除最小元素，加入新的元素，最好的结构是小顶堆。即将前k个元素调整为小顶堆（时间复杂度为O（k log k）,余下元素依次与小顶堆根结点比较，比根结点小则扔掉，比根结点大则用当前值替换根结点并调整为小顶堆，啊 复 杂 度 为O（log k）.所以总的最坏时间复杂度为0 （k log k）+0 （n-k）1 og k）=0 （nlog k）（小顶堆1 分，分析过程与时间系杂度分析共2 分）（3）再从m（这里m=1 0 0）台电脑的共k m（这里k m=1 0 0 0）个数据中选择所有数据的最大k 个，882013年 硕I:研究生入学考试试题汇编3采用(1)类似的方法即可求出。即将一台电脑的小顶堆作为初始小顶堆，余下mT 台电脑的最人k个元素依次与小顶堆的根结点元素比较，大丁根结点则替换根结点元素并调整为小顶堆，直到余卜的数据都处理完成，时间且杂度为0(m T)k log k)(1 分)(4)综合上面3步，最终选择小顶堆能够最快统计出所有数据的前k(k=I 0)个最大关键字数据，总的最坏时间复杂度为0(nlog k)+0(m-1)k log k)=0(n+m k-k)log k).如果 k k m n,则 T(n)=0(n)(I 分)4 .答：(1)快速排序适用(0.5 分)，因为可以快速定位到第一个元素与最后一个元素结点(0.5分)，然后通过1 个指针从头部向后移动，另外一个指针从尾部向前移动，逐一与枢纽进行比较并能够通过修改指针完成结点交换操作(0.5 分)(2)插入排序适用(0.5 分)。因为可以方便的找前趋后继(0.5 分)和通过修改指针完成结点交换操作(0.5 分).f(3)选择排序适用(0.5 分)，因为只需要移动指针遍历链表(0.5 分)并通过修改指针完成结点交换(0.5 分)(4)堆排序不适用(0.5 分),因为双向循环链表无法方便的找完全一叉树的双亲与孩子结 点(1 分).5 .答：根据先序关系画出A0 E 图如下：(3 分)则各个事件Vi(i=l,2,6)的最早开始时间VE(i)和最晚开始时间VL(i)如下表所示:事件iVIV2V3V4V5V6VE(i)03571 21 4Vl(i)0451 11 21 4892013年硕士研究生入学考试试题汇编3各个活动的最早开始时间ae(i)与最晚开始时间al(i)如下表所示(3分):活动iABCDEFGHIae(i)0033355712al(i)10478851112所以，完成该工程所需最短时间为14天。关键路径有：B,G,I(2分)四、算法题(共15分，共2题)1.解：顺序存储的线性表递增有序.可以顺序查找也可以折半查找，题目要求“最少时间查找值为x的元素”，选用折半查找(2分)。算法如下：Me fine status int力define true 1define false 0status SearchExchangelnsert(ElemType a口，int*n,EleraType x)(int low=0f high=*n-l,mid i;status s=false：数组长度检查(1分)if(lowhigh)return s;if(*n=0)return s;折半查找(2分)while(low=high)(mid=(low+high)/2;if(a mid=x)(break;)else if(amidx)low=mid+l;else902013年硕士研究生入学考试试霆汇编3h i g h=m i d-l;)查找成功i f(low=low；i)a M =a(i ;a l o v =x;(*n)+;1r e t u r n s;)2.答：(1)程序输出结果为：1 3 5 2 4(2)程序输出结果为：1 4 2 5 3(3分)（2分）（2分）（3 分）-91夕5 7贝第 2 4 页2012年电子科技大学820计算机专业基础考研真题第 2 5 页电子科技大学2 01 2 年硕士研究生入学考试试题汇编2考试科目：820计算机专业基础注：所有答案必须写在答题纸上，写在试卷或草稿纸上均无效。计算机操作系统一、单项选择题（每小遢2 分，共 14分）页式存储管理系统中的页面大小是由（）决定的.A.用户 B.系统 C.系统和用户 D.不确定下面哪一种表述不属于操作系统的主要功能？（）A.处理机管理 B.存储器管理C.设备管理和文件管理 D.可移植下面哪一种描述不是操作系统的主要目标？（）A.有效性 B.方便性文件目录是（）的有序集合.A、文件控制块C、文件名文件系统采用二级文件目录可以（A.缩短访问存储器的时间 B.C.节省内存空间 D.C.可扩充性 D.多路亚用B、文件信息D、文件属性）节省存储空间解决不同用户间的文件命名冲突在一段时间内，只允许一个进程访问的资源被称为（）A.共享资源 B.临界区 C.临界资源 D.共享区在单处理器系统中，如果同时存在有12个进程，则处于就绪队列中的进程数量最多为（）A.1B.9C.10D.11二、填空题（每空2 分，共 10分）1.根据对截止时间的要求不同，实时任务可以划分为硬实时任务和（）.2.重定位是指程序的虚地址到（）的转换，根据定位时机可分为（）和（）两种.3.文件的物理分配方法包括连续分配、链式分配和（）.三、简答题（共 21分）I.什么是顺序文件？试说明腋序文件的优点和缺点.（4 分）2.阐述什么姑SP OOLING技术.（4 分）3.什么是死锁？如何预防死锁？（4 分）4.阐述基本分页存储管理和请求分页存储管理的异同之处.（5 分）5.阐述计算机系统中缓冲的作用和分类14分）四、计算题（30分）1.在请求式分页管理系统中，某一作业有4 个页面，分别被装入到内存的3,4,6,8 号页框中，假设页面和页框的大小都为1024字节，当该作业在CP U上运行时，执行到其地址空间电子科技大学2012年硕士研究生入学考试试题汇编2第 5 00号处遇到一条传送指令M O V 2 2 00 3 1 00,请计算出M O V 指令中两个操作数的物理地址，并给出计算过程.（8分）2 .磁盘共有2 00个柱面，其编号为0-1 9 9,假定磁头正停在9 9 号柱面上访问.现有一个请求队列在等待访问柱面，该请求队列访问的柱面号分别为：1 9 0、9 7、5 4、3 0、8 7.若采用F C F S（先来先服务）和 S S T F （最短寻道时间优先）的磁盘调度算法，请分别计算磁头移动的总磁道 数.（1 0分）3 .针对下面进程集合，考虑两种调度算法：先来先服务和最短进程优先.分别计算各个进程的周转时间、带权周转时间以及平均周转时间和平均带权周转时间.请完成下列两个表格，并说明哪种调度算法性能好？（1 2 分）进程名到达时间处理时间P 103P 215P 332P 484P 51 05先来先服务:进程到达时间处理时间完成时间周转时间带权周转时间平均周转时间平均带权周转时间P 103P 215P 332P 484P 51 05最短进程优先:进程到达时间处理时间完成时间周转时间带权周转时间平均周转时间平均带权周转时间P 103P 215P 332P 484P 51 05电子科技大学2 01 2年硕士研究生入学考试试题汇编2 数据结构一、单项选择题（2 0 分，每题2分）：下面算法的时间复杂度是（）.f o r （i=n;i l：i）f o r （j=i-l；j l：j）x+;A.0（n）B.0（n2）C.0（n（n-l）D.O（n l o g n）以下数据结构中，（）是非线性数据结构。A.图 B.字符串 C.数组 D.堆栈3、链表不具有的特点是（）.A.插入、删除不需要移动元素 B.不必事先估计存储空间C.可随机访问任一元素 D.所需空间与线性表长度成正比4、一个栈的输入序列为1 2 3 n,若输出序列的第一个元素是n,输出的第i （l l;i-)f o r j l;j )x+;A.0(n)B.0(n2)C.0(n(n-l)D.O(nl o g n)2、以下数据结构中，(A)是非线性数据结构。A.图 B.字符串 C.数组 D.堆栈3、链表不具有的特点是(C).A.插入、删除不需要移动元素B.不必事先估计存储空间C.可随机访问任一元素 D.所需空间与线性表长度成正比4、一个栈的输入序列为123n,若输出序列的第一个元素是n,输 出 第 i (l =i lchi1d!=NULL 1 1 Queuefront-rchiId!=NULL)-1分count-H-;/*统计非叶子节点个数-1分if(queuefront-lchild!二NULL)/*如果有左孩子，左孩子入队*/-1分rear+;-1 分Queuerear=Queuefron t-lchild;-1 分)if(queuefront-rchild!=NULL)/*如果有右孩子，右孩子入队*/-1 分rear+;-1 分Queuerear=Queuefront-rchiId;-1 分)Return count;)第 3 9 页2011年电子科技大学820计算机专业基础考研真题及详解第4 0页电子科技大学*2011年攻读硕士学位研究生入学试题考试科目：8 2 0计算机专业基础注：所有答案必须写在答题纸上，做在试卷或草稿纸上无效数 据 结 构75分一、选 择 题(每 小 题1分，共8分)1.若结点的存储地址与其关键字值之间存在某种对应关系，则称这种存储结构为()A.顺序存储结构 B.链式存储结构C.索引存储结构 D.散列存储结构2.能在0(1)时间内访问线性表的第i 个元素的结构是()A.顺序表 B.单链表 C.单向循环链表 D.双向链表3.一 个 n x n 的对称矩阵，如果以行主序存储，每个元素占一个单元，则其需要的最大存储空间为()A nxn Bnxn/2 C(n+l)*n/2 D(n+l)x(n+l)/24.已知一稀疏矩阵的三元组表为：(1,2,3),(1,6,1),(3,1,5),(3,2,-1),(4,5,4),(5,1,-3),则其转置矩阵的三元组表中第3 个三元组为()A.(2,1,3)B.(3,1,5)C.(3,2,-1)D.(2,3,-1)5.在 有 n 个结点的二叉链表中，值为空的链域的个数为()A.n-1 B.n+1 C.2n-l D.2n+l6.对于一个具有n 个顶点的无向图，若采用邻接表表示，则存放表头结点的数组的大小为()A.n B.n+1 C.n-1 D.n+1 边数7.下图所示的二叉树是()A.二叉 判定 树B.二叉排序树 C.二叉平衡树 D.堆277第4 1页8.用某种排序方法对关键字序列(25,8 4,行排序时，序列的变化情况如下：21,4 7,1 5,27,6 8,3 5,20）进20,1 5,21,25,4 7,27,6 8,1 5,20,21,25,3 5,27,4 7,1 5,20,21,25,27,3 5,4 7,则所采用的排序方法是（）A.选择排序 B.希尔排序3 5,8 46 8,8 46 8,8 4C.归并排序D.快速排序二、填 空 题(每 小 题 1 分，共 8分)1 .若一个算法中的语句频度之和为T(n)=3 7 20 n+4 n l o g n,则算法的时间复杂度为 o2.在长度为n的顺序表的第i(i g&i+l)个位置上插入一个元素，元素的移动次数为。3 .一个队列的入队序列是a、b、c、d,则队列的输出序列为 o4 .广义表人=(%8),0，(1 冉)的长度为。5 .在有n个结点的哈夫曼树中，其叶子结点数是 o6 .已知某二叉树的先序序列为A B D E C F,中序序列为D B E A F C,则其后序序列为.7 .在含n个顶点和e 条边的无向图的邻接矩阵中，零元素的个数为o8 .在以 4,5,6,7,8 作为叶子结点权值构造的二叉树中，其带权路径长度最小是.三、简 答 题(每 小 题 6分，共 3 6 分)1.已知一棵完全二叉树共有8 9 3 个结点，试求:(1)树的高度；(2)叶子结点数目。278第 4