东北大学计算机专业基础历年考研真题答案汇编55p

1、东北大学计算机专业基础历年考研真题答案汇编最新资料，WOR格式，可编辑修改!第一部分 历年考研真题汇编 32015 年东北大学 842计算机专业基础考研真题（回忆版） 3第二部分 兄弟院校真题汇编 42014 年电子科技大学 820 计算机专业基础考研真题 42013 年电子科技大学 820 计算机专业基础考研真题 102013 年电子科技大学 820 计算机专业基础考研真题及详解 172012 年电子科技大学 820 计算机专业基础考研真题 252012 年电子科技大学 820 计算机专业基础考研真题及详解 312011 年电子科技大学 820 计算机专业基础考研真题 402011 年电子科

2、技大学 820 计算机专业基础考研真题及详解 48第一部分历年考研真题汇编2015年东北大学842计算机专业基础考研真题(回忆版)真题】年东北犬学B42计算机专业基础匚语言论述题lcontinue break WIX2什么是关键*列举5个(：诸占中的黄儀字3整型数瞬的说明符是什么整莖 能进行哪些运林編程题1写一个递归西数tote(n)=l(n=l) total(n)=total(n-l)+n+l(n>l) 2输入年打日 计算是这一年中的笫几天 3将一个字苻串从第k位起耳制到忖一个字符串敷脳结构1檯与鏡性表的区别2 f 畏树的左右子树都有三个卩点其中坨于崗的前洋序列和屮序一样右子穩中序序列

3、和后序一样耐出这棉 树3已知邻接衣画出图丐出注度忧先、广度优先遍历庁列4祖据|2知序列眈出平葡二义树揷入过程5根戟已知序列写出第一超快排序列、建堆后的序列、两种排序嘟种疑坏情况下时间复杂度高算法1判斷单链表見否有序2求二史树的宽度3求阁屮到顶点呛的嵌短趾肉为k的全部顶点第二部分 兄弟院校真题汇编2014年电子科技大学 820 计算机专业基础考研真题电子科技大学2014年攻读硕士学位研究生入学考试试题考试科目：820计算机专业基础注所有答案必须写在答题纸上，写在试卷或草稿纸上均无效。计算机操作系统一.填空题（10分.每空2分）1.现有3个同时到达的作业J1、J2和J3它们的执行时间分别为TKT2

4、和T3且T1<T3<T2. 若这三个作业在同一台处理器上以单逍方式运行.则平均周转时间辰小的执行顺序是2. 若一个信号帚的初值是5,经过多次P. V操作以后，其值变为则此时等待进入临 界区的进程数目是e3某基本分页存储管理系统具有快表.内存访问时间为2戶检索快表的时何为0.5 若快表的命中率为80%,且忽略快表更新时间，则冇效访问时间是_4. 在段页式存储管理系统中，若不考电快表.为获得一条指令或数据，至少需耍访问次内存。5. 某虚拟存储器中的用户空间共有32个页面，毎页1KB.主存16KB。假设某时刻系统为用户的第0、1、2. 3页分别分配的物理块为5、10. 4、九 则虚拟地址

5、0A6F对应的物 理地址是 （请使用十六进制表示人:、选择题（14分，每题2分）1.现代操作系统中虽宰本的两个持征是（）。A.共亨和不确定C.并发和共享B.并发和虚拟D.虚拟和不确疋2.引入多道程序技术的前提条件之一是系统具有（）A.分时功能C.多CPU技术B中斷功能D. SPOOLing 技术3操作条统是根据（）來对并发执行的进程进行控制和管理的。A.进稈的基本状态C.进程的优先级B.进程调度算法D.进程控制块4在段页式存储管理系统中.地址映射丧足（） A.每个进程一张段表 一张页表。B 毎个进程一张段衣毎个段-张页农。C. 每个进程的每个段一张段表，一张页表.D. 每个进程的毎个段一报段衣

6、.多张页农。共4页第1页5为使虚拟存储竹理系统只冇良好的性能，应用程序应兵备的特征足（）.A.程序模块化程度髙.由许多小模块组成B程序应兵备良好的局部性特征C. 程序的1/0操作较少D. 程序实际大小应小于实际物理内存容最6. （）的基本含义是指应用程序独立于具体使用的物理设备人设备埶立性B.设备共亨性C.町扩展性D.SPOOLing技术7从用户的角度看.文件系统主寝是实現（）A.数据存储B.数据保护C.数据共享D.按名”取三、分析计算«（30分）1. 某操作系统的文件系统采用混合索引分配方式.索引节点中包含文件的物理结构数纽 iaddrtlOh其中前7项iaddr0-iaddr（6

7、为直接地址，讪idr7卜iaddr8为一次间接地址. iaddr9为二次何接地址。系统盘块的大小为4KB,磁盘的毎个扇区大小也为4KB。描述 逼盘块的数据项需曹4个字节其中1个字节标示磁盘分区.3个字节标示物理块.请冋 答一下问題：（1）该文件系统支持的单个文件的绘大程度是多少？（8分（2）若某文件A的索引节点信息己位亍内存，但其它信息均在磁盘现在需要访问文件 A中第i个字节的数据，列举出所令町能的磁盘访问次数.并说明原囚。（6分）2.3个进稈P0. PK P2互斥便用一个仅包含I个单元的缓冲区.P0每次用produceO牛成1 个止整数.并用pul（）送入缓冲区.对于煖冲区中的毎个数据.P1

8、用gctl（）取出一次并用 computelO计算其平方值.P2用get2（）取出一次井用coirpute2（）计算其立方值。请用信号 益机制实现进程P0、PH P2之间的同步纭互斥关系.并说明所定义信号童的含义.賀求 用伪代码描述。（16分）四、简答题（21分）1. 在存储器管理中.什么足重定位？为什么翌引入重定位技术？（5分）2. 在分页存编管理系统中.页表的主SftHIM什么？現代大多数计舒机系銃帮支持參常 大的逻糾地址空何（2264）.这给页衣设计帶來了什么样的新树题，应如何解决.（5 分）3. 以从I/O设各读入数拯为例.请用流用图方式说刖丹序I/O、DMA传输控制的处理过 程.（6

9、分）4. 在竹学家就餐问題中.如果将先余起左边筷子的诉学家成为左撇子.而将先余起右边 棋子的哲学家称为右撤子。在同时存在左撇子和右數子的前提下.我们安出裤学家融 盘就麻请创是否可能产生死锁.为什么？（5分）数据结构一.填空题(共w分.每空1分)1. 一个“好”的算法应考电达到以下H标：正确性.可读性、健壮性.2. 广义袤()(a)(b.(sd).f)的深度是3. 遍历二叉树实质上是对一个非线性结构进行操作.4. 对许n个顶点、e条边R使用邻接衣存储的令向图进行广度优先遍历其笫法复杂度是-5. 若一个具右n个顶点.e条边的无向图是一个森林.则该森林中必有棵树。6. 求图的珀小生成树冇两种并法.许

10、法适合于求边稀嫌的图的昴小生成树.7. 最販路径迪杰斯特拉(DijksMa)算法的复杂度8. 二叉树上有一个结点的平衞因子的绝对伯大于则该二叉树就是不平衡的.9. 哈希表的地址区何为08哈希函数为H (K) =K mod k采用找性探测法处理冲窠.并将关键字序列(12.21.43,5.39 )依次存储到哈希表中则元素39存放在哈希表中的地 址是." 排序算法不需婆进行记求关键字何的比较。二、炉选題(共20分，每题2分)1. 某线性衣中最陆用的探作足在显版个元素之后描入-个元素和IM除第个元素，则采 用()存储方式最节省运算时间.A. 单链衣B.仅有头指针的单循环績衣C.双链衣D.仅有

11、指针的单循坏链衣2. 下述哪-条是链式存储结构的优点？ <)A. 存储密度大 B.插入.別除运算方便C.存储单尤连续D. fifi机存取第I个元紊方伸3. 一个栈的输入序列为1 2 3 4 5 .则F列序列中不可能层栈的输出序列的足<)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. reirrontC. rear*12frontD. (r)ar-l) MOD nfront5. 若一棵二叉树具有20

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

13、分结果为( )oA. (15,21,12,43, 52,60 ) B (1 5, 12,21,43,52,60)C. (12,15,21,43,60.52 )0.( 15.21. 12,43,60.52)三、简答题(30分.每题6分)1. 画出算术表达式(a*b)f(c-d).(e/f+g)转换的二叉树。2. 若通信系统中只可能出现5种字符A、B、G D和E其概率分别为0.12、0.15、0.19、0.21和0.33,(1)试设计赫夫曼编码：(2)個出相应的赫夫曼树。3. 给岀下图G的(1)邻接表表示图：(2)并根据画出的邻接表以顶点1为根.画出深度优先生成树。4 输入一个正整数序列(45,1

14、4,11,52,63,32,56,24), (1)按此次序构造一颗二叉排序树：(2) 如果删除52,画出删除后的二叉树结构。5. 堆排序的基本思想是什么？其优点是什么？四、算法题(15分，共2题1. 设计一个算法，逆序单链农中的数据。(5分)2. 釆用二叉链表的存储结构，分别写出统计二叉树的叶子结点个数和树高的函数，并分别 分析时间复杂度。(10分)2013年电子科技大学 820 计算机专业基础考研真题2013年歩士研充生入供孑试试SZ：* 3考试科目：820计算机专业基础i±：所有#茂必績写程茶战城上.写蛊试孚生草爲加均无欣，计算机操作系统一. 填空題“0分.每空2分）1. 文件目

15、录是的有学集合.2. 某计昇机系统中有11台打印机.由k个进程竟争使用.每个进程最多需嘤4台打印机. 该系统可能会发生死镇的k的艮小值是_3. 一个简草分段存储管理系统中，地址长度为32位.其中段号占12位.则最大段长是_ 字节.4. 樣作系统捉供给应用程序的接是5. 现代操作系统实现了设备无关性，应用丹序使用来请求使用某类设务.二、选择U “4分.A5I42分）I-进程调度时.下列进程状态的变化过釋哪一项是不可綻发生的？（）A.阻条拄越-阻塞B.就緒挂趕就结C.就绪挂起阻墓挂起D.殂塞挂起-就绪挂起2. 关于线程和进稈，下面说法正确的是（）A. 终止一个进稈比终止一个线程花费的时间少B. 进

16、程切换比同一进程内部的线程切换花费的时间少.C. 线程提高了不同执行程序何的通信效率.D进程和线軒都長资源分配和调度的雄本能位.3. 下列事件令可能导致系统产牛死锁的是）.A.进程释放资操B.丄个进程进入死桶环一c. g个进用竞争独占资源D.多个进桂竞争共孚资澹4. 关于子进程和父进稈的说法.下面曙一个是正确的？（）A. 一个父进程可以创建若干个子进程.一个子进杵1可以从风于若干个父进程B. 父进程被猱馆时.其所自了进桎也被相应撤81C. 子进程戡撤梢时.梵从属的父进程也披撤销D. 一个进程可以没有父进程或子进稈5. 文件系统采用二级文件目录可以（）.A.缩短访问存储器的时间B.实现文件典亨C

17、.节省内存空间D.解决不周用户司的文件命名冲突6. 科既有利于短小作业又兼聯到长作业的作业调度算法是（）A.先来先服务B.轮转C.竝高响应比优先D.均斷调度7. 设计批处理多道系统时，件先耍考虑的是（ ）A.灵活性和可适应性B.贏统效率和吞吐星C.交互性和响应时间D.实时性和可專性三.分析计翼题（30分1. 考虑一个使用32位地址和！KB大小的页的分页虚拟内存系统無个页表项需要32 位，限树页衷的大小为一个页，请回答：<1）页衆一共需要几级？5分）（2）请设计每一级的页表大小.使得所希的页数个数总和晁小（8分）2. 桌上有一空理.允许存放最多浙个水果.爸爸可间盘中放草果或縊子.儿子专等吃

18、 殂中的橘子.女儿专等吃盘中的苹果.规定当£子不满时.次只能放一只当盘子不 空时.一次只能取一只水果：父亲放水果时.儿子女儿不能取：儿子女儿取水果时，父亲不 能放.<1）4分析.丸例中临界资澹是什么？1分（2）下面崔用P、作实现的爸誉.儿了、女儿三个邊程的同步.请克成理序中的空行 部分.（每空1分）Semaphore mute “_; 定义互斥信号豪ini empty=t apple . orange=: 定义同步信兮H Father: 父亲进稈*hile（l）（Put nn apple or orange;If (fruitapple)Else2013年SI士耕兗主入学乌试试

19、遇X：編3Daughter: /女儿进程 Whil e(l)Fetch an apple;Son: 儿子进程While(l)Fetch an orange;0L荷答履（21分）1. 操作系统中什么是虚礼存储器？为什么费引入虔拟存储技术？（5分）2-考3文件系统的外存分配槪述什么是连续分配方式和索引分配方式.（5分）3. 什么ft DMA方式？它与中新方式的主婴区别是什么？（6分）4. 简述利用位示图进行文件存储空何行理的思想这种方法的优缺点处什么？5分）数据结构一、填空11 （共10分.毎空1分）I- 一颤有n个结点的二叉树叶子结点的敬世为no.度为2的箱直数凰为r>2則nO与n2 的关

20、索是:如果用二义链表疗储该二叉榊.刘亨指针数晁为2. 一个何向图的匏接茨和逆邻接表中结点的个敷 3. 将101.186N6. 163.752.334.61等7个散据存入长麼为10的线性麻哈希函数h（K>=K%7解决冲突後略为线件探测再散列，则采用存储給构存储数拡，其中163存储在哈希袁的第 个位暂（H（k）=O为第1个位誓儿4. 榆入n个数懐.2路归井搏序的时何复杂度为 5. 无E）.有n个顶点 e条边则邻接矩阵有 个0元秦，其耗接即阵2013年坎士研咒生入于芍试试崔汙雨385是対称拒阵，只需用 空伺可实现压编存储,&对二叉排序树可以得到线性冇序序列.7. 一个有向无环图的拓扑捋

21、斤床列是唯一的.二、单选題（其20分.毎懸2分）1. 从逻辑上可以把敎据结构分为（）两大类.A.动态结构、静态结掏B.顺库结构.轻式结构C.线性结掏、非线性结构 D.初等结构、构造型结构2. 以下数据结构中，（）是非线性数据结构.A搦B.字符申C队D.桟3. 设一个縫衣最常用的操作是在末尾描入结点和刪除尾结点，则选用（）最节省时简.A.单琏农 B.单林环桂衣 C.带尾抬针的单诵环铤农D.槽头结点的双卅环链农1.对于五序存储的线性表.访问结点和増加结点的时间复亲度为（）.A. O(n) O(n) B. O(n) 0(1) C 0(1) 0(n)D. 0(1) 0(1)5对于队列換作數据的原则是（

22、A.先进先岀B.后进先出 C.先进后岀 D.不分順序6.菖保证连通具有10个顶点的无向图.至少笳吧（）冬边。B. 90D. 457设挨的初始状态为空.当7符序列a3_作为找的输入时，楡出长度为3的XL可以用作C话 自标识符的字符序列何（）个A. 4B. 6C. 3D.58. 完全二叉树采用（）存储结构.满足存歸空间少，方便的査找任忌纳点的双亲与孩子.A.顺序B熄链表C.二叉链表D.三叉链表9下面（）数老结构常用于曲数调用。A.队列B.战C琏衣D數组10.下面（）拮序算広住输入数堀連序情况下It序速度最快.A.归并排序 B.自接捕入捋序 C.旨泡排序 D.简单选择丼序 一三. 简答题（共30分.

23、共5题】I.己知4个字符A. B, C, 0的缶夫曼编码分别是1.0L 000.00k下列01串是由以上4个字母构成的一段文本的芒夫宦编码：1001000011011010011010011请将上述01巾还原为編码前的文本以字符花文衣中出现的次数为权值.求出这棵钳的 帝权路徑长度（关5分）2. 愉入元盛序列32. 18635】.1144.33.7& 请沟這AVL树°假设所育元索的負找tftTM 零，诉分别求出这棵AVL树的茂找成功的平均奁找长度ASL（成功）与失败的平均査找长度 ASL（失败）.（5 分）3. 海便数据分布准100台电輔中想个办法高效统计岀所有数据的前10个最

24、人关键字数提. 并分析时间夏杂度（共6分）.4若愉入故抵存储在带头结点的双向循环说表中，下而*种排作黨法長否仍偵适用？为什 么?（共6分）（）快速川序（2）直接抽入排序（3）简单选择排序堆排序5. 已知某工程孑工序之何的优先关系和各工序所菸的时闾（具中“一”衷示无先驴丄洋） 妇下表所示.谐根据工序哀画出对应的A0E圈并指明完成该工程所需的0短时何和关 達路径.（共8分）工序代号ABCDEFGHI所需时间3514667321先駆工序AAABBDG四、算注题（共15分.共2题）1. 线性哀31山2,an）中元康递增有序II按顺序存储F计算机内的数组at-要求设计一算法用函数实现下列功能* （共10

25、分）（1）用址少时间在表中査找值为X的元素：（2）若找到则将其与宣接后维元素交换：（3）苦找不到则将其描入麦中使其表中元索仍紡逼增有序2. 假设Header指向如下循环单席农，请问执行下列2个程洋段后各自的时结果足什么？（共5分2013年碩上酬究生入学考试3单錢表结点定义如卜:lypedef struct nodeint data;struct node next; iNode. *p*tr,拿 List:/第一个程序段ptr p=Header：for(int i=0;i<5;i*)printf ( .p->data); p»p->next:p=p->next

26、;/第二个殍序段ptr p二Header：for(int i-0;i<5;i*)printf( "Wd" f p->data):p=p->next：p=p*>next;p=p->next：2013年电子科技大学 820 计算机专业基础考研真题及详解201J年硕士研穴生入学考试试厲汇3参考答案：820计算机专业基础计算机操作系统一. 填空晚1. 文件控制块2. 43. 2刀4. 系统调用5. 逻無设备名称二. 选择題C C C D D C B三. 分析计JT题(30分)1. 考建一个使用32位地址和1KB大小的页的分员庭拟内存系统.每个页表项馬妥

27、32 位.限制贡表的大小为一个页，请回答：(1) 答：由于页面大小占用10b血还剩22血 叩有严个页衰项.一个页表项32bh即 占用4个字节一页最多含2l0/42g个页表顶.所以需要J级贝表.6分)(2) 答：若一级页表长腹为6位，二级和三级页茨长度各为8位，则需要的页数总敷为1*22,4-16449；若一级页茨长度为8位.级页茨长度为6位三级页表长度为8位則总 共需曼页效为:H2s>2k-1664I：若一级页表和二级页哀长度分别为8位，三级员表为6位. 則总共需要ZW65793応因比三级页衣的K度分别为6. 8. 8时.总页數和爰小。 (9 分)-2.毎格一分，共16分(1) 临界蟄改

28、殳盘子(2) Semaphore mutexlj 定义互斥(S号虽im empty=_2apple=. orange® 0_; 定义同步信弓最 Father 父亲延程While(l)一P(empry)_;20门年磧士纽究生入学%'XiXS汇“ 3_P(mutex)_； Put an apple or orange;If (iniitapple)_V(apple)_;Else_V(orange)_:Daughter: 女儿进程Whilefl)P(pple)_; 一P(mutex)_: Fetch an apple;_V(mutex)_;_V(empty)_;Son: /JL子进

29、理While(l)P(orange)_;P(mutcx)Fetch an orange.V(mutex)V(emp(y)四、简答题21分）1. §：在具育址次结构存钱為的计算机系统中.自动实現部分袋入和部分替頼功堤.能 从逻输上为用户按供 个比协理r：存容盘大得多.可寻址的“主存緒襌"炼拟存储区的容童 与物理主存大小无关.而受限»机的地址结构和可用娥盘容垠计算机操作系统引入和使用虚拟存储技术的主要目的是提高系统的内存利用率和系统吞 吐SH5分2. 符：連续分配方式：在创建文件时帚燮给文件分IE组连续的盘块。连续分配的优点 主要育两个分别是顾序访何文件时比较容易.并

30、FI顾序访问时速度快.缺点足要求有连续 的存緒空何.井且随着外存空间的分配和回牧.会产生很多外存評片.降低了外存空间的利 用率.索引分配方式：为文件的毎个分区晅独連立-张寮引农该索引衷记录了分配给滾文件 的所有的块号.优点：直接访问和顺序访问的連度/比较快.缺点：疗转索引农花费了较名 外存空间.（5分）3. S： DMA是H接存紡签存取.DMA传辑将数撻从一个地址空间复制到另外一个地址空间当CPU初始化这个传输动作.传输动作本身是由DMA控制器采实行和龙成.在实现 DMA传输时.是由DMA控制器頁接拿管总线.因此.存在背一个总线控制权转移问即DMA 传输的 CPU嬰把总线控制权交给DMA控制器

31、.而在结臾加 传綸后.DMA控制祸应立即把总 线控制权再交回给CPU.它和中断的主要区别在于.DMA只需耍CPU住开始和完成传输时进行、 干預.梵他时候不需要CPI干横（6分）4若磁盘块空闲，則用1表示.否划用0注示从而得到一张位式图表.反映了所 有陋盘块的信恵.其优点在于很容易找到一个连续的空闲块.矽点在于整个磁盘的位式图文 件比较大：另外.在JKSL空闲快较少时.搜索空困块雯花労一些时两.（5分）数据结构一.填空U （共10分.毎空1分）1. nOn2*l ;n*l2. 相同（一样）3 颇洋；64. O（nlogn）5. n,-2e;n（n*l）/26. 中序逊历7. 不/不一定二（共20

32、分.每題2分）1-5. CADCA 6-10. CCABA8720139 t斫咒生入学考试试酗血3三、简答題（共30分.共5»）1.：霍夫雙堀岀於前块城码满足任总？符的城码祁不会址另外 个字符第码的前圾.閃此译码不会产牛歧义 1001 OOOOMOl 101001101001!还嫌出丘的文本为：（2分）2分）<1分）1 001 000 0! 1 01 1 01 001 1 01 001 1AD CBABAB DABDA其中A出现5次 B ill HE 4次 C出现1次.D出现3次.帝权路径长度为WPl(H3)*3M*225Q分）2答：AVL何如下图所示.ASL（成功）-（H2*

33、2-4*3*2*4） /9=25/9（1 分）ALS（失畋）珂 3*64*4）/10=34/1334“分）3. 先分别求出毎台电脑的前2个址大关键字歎据.再根据这100台电瞋的般大前 10亍/B人天厲子A 1000个数期求出刃1U大关使字敌席即町具休分析如下：（1）先求岀毎台电脑的前】0大数据.由于只務妥求出部分因此不需耍对“个数据 全部再序.采用却分排字算法即可，比如简单选择特序、堆拮序.補描序（】分）（2）求n个数据的前k（USk=10）大数据.当k«n时.W佳的方法是将后面的个 数据依次与前面的k个数据的煖小诲比较.片果比金小值还小.則扔忙讼数据.继续比较卜 一个数拆.舍则刃掉

34、史小的数据，把这个新数加入.亘到余下的n-k个薮抠都处理宪 U于 毎次需婴勾存储的k个救据比较并可能蒯除球小元素，加入新的元斎.帰好的结构是小頂堆. 即将前k个兀亲過空为小顶堆（时何复杂度为0（klogk）.余下元亲依次与小顶堆根结卢比较. 比根结点小則扔掉，比根结点大则用当前值卅换根结点井凋整为小矽堆.以勻复杂度为 O（logk）.所以总的址坏时佃复杂度为O（klogk） 0（rrk） logk）=0（nlogK）（小顶堆分.分析过穆与时闾复杂反分析共2分）（3）再从m（这里100）台电脑的共kxn（这里km-1000）个数据中迭弾所右垃虑旳集大k个，892013年事H研克生入学为试试ttL

35、tt 3采用类似的方法即可求；lh即将-台电脑的小Ififtfl为切冶小顶堆余下mT台电曲的虽 人k个元索依次与小顶宦的根络点元索比较人1根结点赠弱换楸结点元索外调整为小顶堆, 直到余卜的数他郝处理完成时间反朵反为O(l)ldogk)(I分)(4)综合I面3步.只终选杆小顶堆能够饭快统计岀衍有敎抵的曲k(k-10)个嚴人关谢 字薮据.总的昱坏时间复杂厦为0(nlosk)a*<0(irl) klogk)flO(n iok-k) logk) k<<kn«n则 T (n)*0(n)(1分)4.答：(1) 快速捋序适出(0.5分).囚为可以快速定位到號个元素鼓后-个元累细点

36、(05 分人然斤通il 1个把什从头都向斥移动.另外个抬什从尾部冋前移动逐一与枢纽进行比 较并能够通过修改指针左成紡点交換操作(0.5分(2) 插入排序适卅(0.5分).为为可以方便的找前追拆继(05分)和通过倏攻指计完 成结点交换操作(0.5分)(3) 选幷拮序适用(0.5分).因为只需要移动指针逋切链农<0.5分并逋过修改布针完成结点交换(0.5分)(4) 堪捋序不适用(0.5分九因为双向循环链农无法方便的找完全一义树的瑕亲与孩子 结点(1分人5答：根据先序关系做岀AOEffiSD b：V61-2VS(3分)則各个爭件Vi(m.2 6)的帚早开始时间VE(i)和最晚开始时间YL如 X

37、所示:事件iVIV2V3V4V5V6VE(i)035712>1Vl(i)0451112142013年硕士胡兗生入学弓识tfuax W J各个活动的最早开始时瓮&e（i）与只晚开始时间a）（ij妇下衣所示（3分）:iABcDEFGHIae(i)0033355712al(i)I0 .478851112所以.完成该工程所离最短时何为14天关谴路径有* B.GJ（2分）四.算法題（共15分.共2 Vi）1. X:甌序存储的线性表遥增有序.可以锁序査找也可以折半査找，题目鉴求“最少 时何査找值为x的元索”，选用折半査找（2分）.算法妇下：sdefine status intcdefine

38、true 1define false 0status SearchExchangelnsert（ElemType aL ini EleaType x）int lowO.highn-L nid» i：status s=false：数组长度检査（1分）i f（1ow>h i gh）return s:if（*n<»0）return s:折丰戏找（2分）while(low<=high)«id= (lourhigh) /2: if(anid=x)(break:Jelse if(a(mid<x)】ow 二 Hid"：else912013年硕上

39、研兖牛入字试试SSL® 393hishnuid-l;査找成功if (lowhigh)I/是否元素s=true;if(mid*n-l)return s;/不是最后一个元素.则与后逖交换atnid=8Bid*l)：afrid+lj=x;Ielse 査找失败Ifor( irnT：i>=io：i)allowjx：(*n)*;)return $)2.答：(1)程宇输出结果为：13524(2)程啊|出结果为：14253(3分)(2分;(2分)(3 分2012年电子科技大学 820 计算机专业基础考研真题电了科技丈学2012年硕士研究生入学考试试題汇2考试科目:820计算机专业基础注：所有答

40、案必须弓在答题纸上，弓在试卷或草稿纸上均无效。计鼻机操作系统一、单顶选择题每小感2分，共14分）页式存储管理系统中的页而大小是山 < ）决定的.A.用户B.系统C.系统和用户D不确定下血哪一种表述不用干操作系统的主要功能？（）A.处理机符理B.存储越管理C.设备骨理和文件青理D.可移植下面哪一种描述不是操作系统的主耍R标？（>A.有效性B.方便件C.可扩充性D.多路艮用文件H录足（）的有序集A.A.文件控制块B、文件信息C.文件名D.文件属性文件系统采用一级文件冃录可以()A.缔短访何疗储器的时间B.节省存储空间C.节省内存空间D.解决不同用户间的文件命名冲突在一段时间内，只允许一

41、个进程访问的资海被称为（）A.共寧资澹B.临界区 C.临界京添 ！）找孚区在单处理器系统中.如果同时疗在有12个进程.则处于就绪认列中的边程数审最多为<>A. IB. 9C. 10D. 11一.填空题（毎空2分，共10分）1. 根据对戴止时间的耍求不冋.实时任务可以划分为便实时任务和（ 人2. 币:定位是指程序的虐地址到（）的转换.根据定位时机町分为 <）和（）两种.3. 文件的物理分配方法包括连续分配.琏式分配M （>三、简答題（共21分）1. 什么是罰序文件？试说明顺序文件的优点和缺点.Z分）2. 園述什么是SPOOlJNG技术.（4分）3什么定死锁？如何预防死？

42、（4分）1 阐述基木分页存储骨珅和试求分口存储管刖的异同之处.（5分）5. 阐述计算机系统屮缓冲的作用和分类（4分）四计口题<30分）1.在请求式分页管理系统中，耳一杵业有4个貝面.分别波装入到内存的3,仏6, 8弓页框中.假设页面和贡框的大小都为1024字节，当该作业任CPU上运厅时.执厅到其地址空何 61电了科技大学2012年硕士研宛宅入学考试试訣汇编2笫500号处遇到一条传送折令MOV 2200 3100,请计再岀MOV指令中两个操作数的协理地址. 并给出计算过程.8分）2. 礎盘共有200个柱面.只编号为0-199.假定磴头正停在99号柱面上访问现冇一个请求 队列在尊侍访问柱面.

43、该请求队列访问的柱面号分别为:190. 97、54、30、87.若采用FCFS（先来先鞭务）和S£TF忌短寻道时间优先）的磁盘诉度算法.请分别计算磁头移动的总磁 道数.（10分）3. 针对卜湎进程奧仟.考虎曲科调度算法：先来先康务和最短进程优先.分别计隽各个进程 的网转时间.带权周转时间以及平均周转时间和甲均带权周转时间.请完成下列两个农格. 并说明哪种调建獵法件能好？（】2分）进程到达时问处理时间完成时问P103P215P332P484P5105周转対间带权周转 时间平均周转 时间平均带权 周转时间进程名到达时间处理时何P103P215P332P484P5105先来先眼务,进程到达

44、时问处理时间完成时问周转时何带权周转 时间平均周转 时何平均帯权 周转时何P103P215P332P484P5105最短进程优先,电子科技大孚2012年斫二斫究生入学考试试题7匚编2(数据结构一、单项选择理(20分，每題2分人 下面算法的时间复杂度足().for (i=n;i>l： i)for (j=i-l:j>l: j一)X*+：A. 0(n)B. 0(n)C. 0(n(n-l)以下数据结构中，()足井线性数挺结构。a. tab.字符串3、链衣不具有的特点是()A.插入、删除不需要移动元素C可锁机访问任一元素4、一个栈的输入序列为123m元素是().A.不織定D. O(nlogn

45、)B. n-iC.数细D.堆栈B.不必爭先估计存储空何D所需空间与线性表长度成正比若綸出序列的第一个兀素是m输出的第i (l<=i<=n)个CiD. n-i+15、若一棵二叉树具有12个度为2的结点.6个度为1的结点，则度为0的结点个数是A. 10B. 11C. 13D.不确定6、下列哪种算法使用了从列作为楠助仔储給构()A.二艾树的先根序遍历算法B.二叉树的层次遍历算法(1图的深反优先遍历算法D.图的拓扑择序篦法7、以下哪种二叉树左右子列可以交换(儿A.二义排序树B.线索二义树C.平衡二叉树D.呛夫曼树8、下列腆种图的邻接矩阵是对称矩阵().A.有向图B.无向图C. AOV MD

46、. A0E网9、布长度为n的顺序线件衣中顺序杏找值为x的元素时，杳找成功时的半均伶找长度(暇定 百找每个元素的槪率均相竽)为 < )A. nB(n-l)/2C. n/2D. (n+l)/210、卜列rt序算敢中，()在某硒排序结束后不一定能选出一个元索放幼其最终的位医上.A.选择扌丰序B.冒泡扌丰序C.希尔排序 0.堆梓序二. 填空邀(10分.每空2分hh判定循环队列的满与空.有三种方法.它们是 和2. 一颗第5檯有6个叶子节点的完全一叉14 垠多可能拥有的结血个数为3、在无权的无向图G的邻接矩阵A中.若(v,t v.)屈干国G的边集合.则对应元素Aij等于三. 简答理(30分九试揃述堆

47、栈和遞归的关系.(5分)2、已知二叉树的中序逊历序列为DEBAFCG.后序遢历序列为EDBFGCA,试画岀该二叉树(7分)63电了科技大学"12年斫研究牛入学考试试題汇编23、给定25个字符姐成的电文：(6分)DDDDAAABEEAAFCDAABCCCBADD试为字符A. B. C、D. E、F设计哈夫曼(Huffman)城码.(1) fli出相应的哈夫曼树：(2) 分别列出A.氏C、DE. F的哈夫显编码，(3) 计算该树的帯权賂径长度WPL<4、已知带权图G如图所示.试用Prim算法构ifi对应的最小牛成树.请给岀构造步骤.(7分)5、一个线性表为 B珂 14. 23, 4

48、3. 52, 20, 35, 79. 31, 17, 36),设散列茨为HT0>.20t 散列由数为H (key)-key % 11并用线性探测法解决冲突(增量山丸2),试写岀散列表。(5 分)四、算法设计题(15分L如果以二叉链表做为存储结构，试用类C语言编写统计二叉树非叶了结点个数的层次遏历鸭 法。(15分)2012年电子科技大学 820 计算机专业基础考研真题及详解瑕子科技大学2012年硕士研究牛入学考试试舷汇御2参考答案：820计算机专业基础计算机操作系统选抒题l.B 2.D3.D4. A 5.D6.C7.D填空题1. 软实时任务2. 物理地址，静态垂定位.动态重定位3索引分配简

49、答题顺序文件是指曲一系列记录按风某种顺序摊列所形成的文件.顺序文件的优点在于出带耍对 记录逬行批星存取时.它的存収效率虽高.其缺点在于当文件较人时，记录的检索效率牧低。 另一个決点杲记录的增加和删除比较囚难.SPOOLING技术是冋时联机外国操作技术的简祢。它是关于慢速字符设备如何与计煤机主机进 厅数据交换的一种技术，通常又称假脱机技术.在多道程序环境下.利用多道程序中的一道 或苦两道程序來模拟脱机输入/罡岀中的外II控制机的功能，以达到“股机”输入/输出的目 的.利用这种技术可把独占设备转变成共亨的虛拟设备.从而提奇独占设备的利用奉和进程 的推进速度.死锁是因进程竞争资游或推进顺序不当而引发

50、的一种胶着状态.死锁的只个必要条件分别是: 互斥.占有且等待.不可劃夺以及循环等待为了预防死锁必须破坏死锁的四个必要条件. 由于互斥条件不能改变.因此可以采取破味四个必要条件中的圧三个.住基本分页存储管理系统中.系统将每个程序按固定的大小分成若干页，每页对应一个物理 決号.程序的所有页面都被装入到内存当中.在请求分页存储管理系统中.程宇仍然被系统 分成若干页.但并不足所有的页面都被装入到系统中.而是仅仅装入程序运行所必须的页面- 当需要某一个页面时，再请求从外部调入。如果没令空闲的空何.则利用置换技术进行页面 的洶汰与賈换.为了级和CPU和外设Z间的矛盾.操作系统引入了单缓冲.双缓冲以及循环缓

51、冲.所谓单缓 冲.就是在CPU和外设之间设置了一个缓冲区.当育数掛交换时.先把数据发往缓冲区.再 从缓冲区中读数据.双缓冲就是具有两个缓冲，当一个进程正在往一个缓冲区读数据的时候, 操作系统可能正在读或写另外一个缓冲区.州环缓冲就兄貝冇多个缓冲区的组合，它更加能 侈缓和CPL和外设之间速度的不匹配。计算题L.肖先要为诊作业建立贝茨如下：电子料技大学2012年硕t硏究生入学可试试恁汇擄2每个页面的大小为UJ24字节则逻別地址2200的戻号应该为2.对应物理块号6.页内位移 量为162.实际物理为：6X1024T62托296.逻辑地址3100的页号为3,对应物理块号8,页内位移量为28,则吻理地址

52、为8X102442«=«220.2. FCFS访问顺序为.99. 190. 97. 54. 30. 87,因比砒头移动数为：(190-99) - (190-97) (97-54) * (54-30) (87-30) = 308SSTF访问顺序为，99、97. 87、54、30. 190,因此磁头移动数为,(99-97) t (97-87) + (87-54)亨(54-30) + (190-30) = 2293.先来先服务进程到达吋 何处理时 间完成时 何周转时 间带权周 转时间平均周 转时间平均带权 周转时间P1033316.41.84P215871.4P3321073.5P4841461.5P51051991.8鮫短进程优先进程到达时 间处理时 间完成时 间周转时 阖带权周 转时间平均周 转时何F均带权周转时何P1033315.81.42P2151091.8P332521