南京林业大学信息科学技术学院884计算机软件基础历年考研真题汇编.docx

目录第一部分历年考研真题汇编2013年南京林业大学信息科学技术学院884计算机软件基础考研真题第二部分兄弟院校真题汇编2014年中国科学技术大学合肥智能机械研究所822计算机软件技术基础考研真题 2013年中国科学技术大学合肥智能机械研究所822计算机软件技术基础考研真题 2012年中国科学技术大学合肥智能机械研究所822计算机软件技术基础考研真题30201535151004.当一个进程完成了特定的任务后，系统收回这个进程所占的_7 和取消该进程的_8就撤消了该进程。5.在存储器管理中，页面是信息的_9_单位，分段是信息的_10_单位。6.实现SPOOL系统时必须在磁盘上辟出称为_11 和_12的专门区域， 以存放作业信息和作业执行结果。三/判断题(本大题共10小题，每小题1分，共10分)()1.在单链表中，要访问某个结点，只要知道结点的指针即可，因此，单 链表是一种随机存取结构。()2.线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序 上相邻。()3.程序在运行时需要很多系统资源，如内存、文件、设备等，因此操作 系统以程序为单位分配系统资源。()4.线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。1 )5.使用三元组顺序表表示稀疏矩阵的元素，有时并不能节省存储空间。()6.简单地说，进程是程序的执行过程。因而，一个进程就仅仅执行一个程序。()7.哈夫曼树是带权路径长度最短的树，路经上权值较大的结点离根较()8.连通分量是无向图中的极小连通子图。()9.操作系统提供了大量的服务，在最高层是系统调用，它允许正在运行的程序直接得到系统的服务。()10.在采用树型目录结构的文件系统中，各用户的文件名必须互不相四、应用解答题(本大题共8小题，每小题6分，共48分)2 .已知如图所示的有向图，请给出该图的：(1)每个顶点的入/出度；(2)邻接矩阵；(3)邻接表。3 .假设用于通信的电文由字符集abcdefg中的字母构成。它们在电文中出 现的频度分别为0,31。16010。080110.20。04。1)为这7个字母设计哈夫曼编码；2)对这7个字母进行等长编码，至少需要几位二进制数？哈夫曼编码比等长编 码使电文总长压缩多少？4 .设待排序的关键码为(12,25,8,7,53,75,61,87,4,17),进行快速排序，请给 出每一趟排序后的结果。5 .已知一棵树的先根遍历结点排列为：ABGHIDECF,后根遍历结点排列为： HIGBECDFA,试画出该树6 .简述下列程序的功能。# define ListSize maxsize+1typedef int DataType;typedef structDataType dataListSize;int length;jsqlist;Void pe3(sqlist datatype x /*L是非递减的有序顺序表*/if(L.last=maxsize)error(noverflown； elsei=L.list;while(i>O)&&(x<L.datai-l)(Ldatai=L.datai-l;i-；)L.datai=x;L.last+;)6 .设某作业占有7个页面，如果在主存中只允许装入4个工作页面(即工作集 为4),作业运行时，实际访问页面的顺序是1, 2, 3, 6, 4, 7, 3, 2, 1, 4, 7, 5, 6, 5, 2, 1。试用LRU页面调度算法，列出各自的页面淘汰顺序和缺 页中断次数，以及最后留驻主存4页的顺序。(假设开始的4个页面已装入主存)。7 .什么是死锁？死锁的必要条件什么？怎么防止死锁？8 .什么是进程？它的基本状态？状态之间转换的原因？五、算法设计题(本大题共5小题，每小题8分，共40分)1 .有一无向图以邻接矩阵存储结构的方式存储,给出创建该图的相应算法。2 .设LA和LB是两个递增有序的单链表，试编写一个算法，将LA和LB归并 为一个仍是递增有序的单链表LCo3 .假设有一组数据放在一棵二叉树中，找出其中最大值，并给出最大值所在结 点的指针。请设计相应算法。4 .利用信号量机制给出读者-写者的算法。5 .医院一门诊室，只允许10人进入室内等候，超过10人只能在外等候，门 诊只有一个医生看病，患者看完后即离开门诊室，利用信号量机制给出患者看病过 程。顶点123456入度出度第二部分兄弟院校真题汇编2014年中国科学技术大学合肥智能机械研究所822算机软件技术基础考研真题第一部分历年考研真题汇编2013年南京林业大学信息科学技术学院884计算机软件基础考研真题科目代码：884科目名称：计算机软件基础注意：认真阅读答题纸上的注意事项；所有答案必须写在答题纸上，写在本 试题纸或草稿纸上均无效；本试题纸须随答题纸一起装入试题袋中交回！一、选择题（本大题共40小题，每小题1分，共40分）1 .线性表是具有n个（）的有限序列（n>0）。A.表元素B.字符C.数据元素D.数据项2 .线性表是（）。A. 一个有限序列，可以为空B. 一个有限序列，不可以为空C. 一个无限序列，可以为空D. 一个无限序列，不可以为空3 .线性表采用链式存储时，其地址（）。A.必须是连续的8 .部分地址必须是连续的C. 一定是不连续的D.连续与否均可以4.链表是一种采用（）存储结构存储的线性表；A.顺序B.链式C.星式D.网状2川年肚学跚胜娉箱勰(计楙蜘)航馥赴,微驰端上球删腑熊 糊郦-、简馥海悔6"共3。分)1 .改A为娜,就空咻丽的娥,牖琳二籁脚三就蒯精髓瞅计的4的雕届|>|2 .淞根跚邮城后,邮猫靴胸帆理邮业雕画典 加?肺么?钟他的雕晌是龄姓姚?洲么？3 .隔腋件系弹盘触越加的瓯螂系.4 . OS廉酬嘟飙儿良瞩揉燃肿么？用也频耐妨法,其照鹏触？ 二应腌(每械15分，共90分)1.瞰以R肌州拓入肺雌雅,巡翻一个懒僻琳强 一系列同幡入前触。(1)籁糊肺黑作悯环令娜片雌螂。(2)肝胴板糅合,龄丽的合流如耕质豳照蝴 一一德胸?雌一，瞬触乳井轴植械醉# 列.1(1)微珈一极二期的前册卿中解丽虹航洲二叉机(2)展二照的解悯力ABDGECFH,中肺列为跚阳心谢端 以二%礼(3)峨始了一忙期辐肺解列就解帅能酬就此二 邓伽舸以,m.贼轲瓦般啦机».胡机棚擀殿3,疑一般髀 Jan, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec,皖蝙岫HOHi/服聊i力趟郛慨-伸睡字腺 中邮号将财于鼾地耿翻,聊肝酬那姆施 机踊球,并邠悚聘解饿做槿嬲躺聘魏娥.(I)射煤踊枷激救删I腔陋16)(2)觑辘4 .胡蟆麟制搬铀卜7加个溜斯聃,鞫4硼将肝翻行缈她机蒯明触。(2"轴-慎腌肝岫蜥喉机(3)槌桶肝雷斯勤批饿?谛娜触。(4)般上线神肝胸躺喊院. miwiBin必如版加淋wi» 中的妹傩虾,mn0234036789核号6432000000懒111000000贿三m曲魏触:id,帆576, 麒此雌懒,般出辘源,妍雌树蒯幅也.掰辨肿桃.咽虾麻:(I)糊脉繇彼舲(2)福&幽瞰娥系理微般系鲤。()前略住系胜队相船:地册麻栅三、算滤瞰15分，趟分）.曲机2镰力龄单麻服钻Jtt船,航种版蟠躺 触捌为孵& i僦卜律法,独例眄L2魏胴雌飕 由牖谴世嬲胧丽露（报摊需黜浦）1 .有-间赚1林2酬懒的螂01般幡燔厥削,H 仓钟D1触蒯哪i龊虾繇:Wl#02 冰 N聊M触岫鹰丸蝴,诵-蚀腑如1机2,歇喉1 N1箱个D2火螺帆3。训蝴的f聊曜喊跳D1、也的人 软D3般产跳.»计就棚楙娜2013年中国科学技术大学合肥智能机械研究所822计算机软件技术基础考研真题腑辆土学姗鞋人特就馥(计嬲慨柳)黜嬲匕寐兜谛上无依储蜥然不蝴雌-WM&幡明 43091.梆削圈鞠坏般脚罐肿,救磁船P舶藕备不 城好范解娥躺脑躺毓中轴,嫌硼，麟雌tt m撇鼬2嗦电嬲瓣觥槌撕深於聊腓2蝴*蟾糕而 穗抽勰削1悔脉即娴新&唧4脚U B、C琪IP触懈,榔I三嬲撤搦榔耿搬州枷丸5断捌御姗M助釉任提仪例概的跳削么?二、M侮脚5分,觥分)10 0 21 .辘啾工0 0 0 52 0 5 0 B(I)端加跳押搬蒯虾三航都照藤岫麟瞒毓 fist 懒金并黜伽胜任兀釉肝hi糊下 颓K网标麴S帽釉厮(I兆。触锦肮(2)牖械力僦麟，喊朦工麻腑麻断麻,蝴 斤觥哪捌I "£*骗撕褥眺勉虢懒脑力力打帏6 恍辅肌(I)哪歌搬搬懒微物渐哪嬲粮楣潮翱部楙躺¥频妇员(2) T肿贿纱轲就？0)钟躺的如牖加2, 3 J 6,避也-躺联礼并 计魁相大棚献腑娥WL3,翻秘枷侧的词儿雌刎加小踹虾关爵鹏。儿此乩1122),树皿渐懒极防切 球,挪黜瞬脚撕懈懒微ASL (I)蜩瓢娜；(2)舰股4 缺胛(5虱 87.512,61,骗 17。, 897, 275,653,462)(1)帕州,赫轴卧优i班憾一步搬战瓣则。(2)釉肺幅,始需帆TIIMH制脚螂.5,藏怖榔(A,B,C)蜘个跚乱御悔虾:册哪mm腕iOA B CA B CA B CPl-10 02 2 21 1 2P?5 111 0 2P)2 1 11 0 JP.I0 0 24 2 0瀛翩而盛瀛瀛瀛而(I)杆肃繇就能曾叔，湍腋的川(2面豳搬曝瞰臧(L。小藏臃腕螂何册J(携熠喊械鼠)6,伽下麻献系SCSNoC-NoC-NAMEI'-NAMETLOCAGRADE80152ClOSf泡DI70801”C2DBD285MI54ClOSf希DIi680154aCAD车ilD312MI55C4CAMA笈0292SNO播.GNO力懈GNAME般眈JNAME%枷4TLOCA 城删此 GRADEM(i)sc ma牍肱献滕蒲?林在岫脏蒯傩 肝胜胜版朋做？料楣:计姗螂林就如贝妇口(2)郴C储胞力献，姗郁繇腕救郦就碱?三、聪题瞰15分，共3。分).辆锦SI机2,聊项班旅,都好一竹岖0耐力 加82聊撇躺睡醐曲神血,淞和激麒I般2的 人肺雌蚱榭螂1 .PI肿2例强遍彼帼bu闸肋峋2轴髀ll,PI2Mh 也他犒辘川蒯2从b蒯槐蜘1麟感和P2I 神2Abu蒯顿凝P2雕&嵌龄皓欧楠林鲫 嬲时屿觥卜肤,胴糊嫌尹仰雄懒帼中解 椒喘乳硼PV解殷舰6州脱岫船皿底扁»郁喊脓木搬2012年中国科学技术大学合肥智能机械研究所822计算机软件技术基础考研真题藏情土学蒯鞋博粗微(计»赫蝌)写格嬲匕糕兜琳上班盛蝴需槌腑娼-、名腓(十分，共15分)胜般减U3,蝴I螂5.关系娥二计瓢触15儿共忧L都懂入2,3,4,5.6喊人M娜的旅喊B翻虾 胳个峨悯,殿服,般以撇喊般累嫄稠瓦M 鼬(1)0 (2)06 (3)125463 (4) 21 删2,鼬球微电灿8伸用脆储M B, CE, F. G, K 将脏蚊神嬲螂力;%隔热储孤乳湍儡 糊糊嬲翔峭大帆3.有一岐好;53, 17, 12,61,98,70, 87,25,队 114 曲 67, 75.胡肝祠防(1)勒其觥骗乐舰空岫18彼兀moo,冷桶螺 雕雕嬲般,蝴黯懒I顿硼研知(2)釉减鲫期酸僦机解林川蒯酬标跚Q贝后贝m催唱（i）鞠前髀姗撇啾帆皴帆枫储曼缈靴胸；（3）关嘛5,既-航融（瞅从的14,26,38,86,65,27.3八幡映 肝财法斯腑嗨避雌柳丸哪趟臃（2）雕搬（3）螭嘏6, HWfc己般翘神喉醐的躺;1.2,3. 4 % 1,5,6,2, b 2,3", 6,3,2. L 2,3,6,帏中版翻册和 仲麒弁牌嬲奸员酿耨渊娥聊聊,贼触遛.（1） F1F0IS （2） im三2勰触15分，共45分）1.鹏舞j触鞘歌上窿照散邮I赫脑,神钟鼾I篇歹恸翻雌科伽个萩舲林邮摘认蝴喇 腓丽槌岫I慎摊捌JH够翅觎麟帼钟解一 他炮瓶蝙“减版遵收物他跚融解瓯标龄 MW耻藏忡I储机耨做仙2, “即解虢窗I雌蚊" 岫狮I躅麟伟用聘喊嫦搬脚麻肋触林升if翻糊疝渊厕林默W财5.下面关于线性表的叙述中，错误的是哪一个？（）。A.线性表采用顺序存储，必须占用一片连续的存储单元。B.线性表采用顺序存储，便于进行插入和删除操作。C.线性表采用链接存储，不必占用一片连续的存储单元。D.线性表采用链接存储，便于插入和删除操作。6 .设单链表中指针p指向结点A,若要删除A之后的结点（若存在），则需修 改指针的操作为（）。A. p->next=p->next->nextB. p=p->nextC. p=p->next->nextD. p->next=p7 .设有三个元素X, Y, Z顺序进栈（进的过程中允许出栈），下列得不到的出 栈排列是（）。A. XYZB. YZXC. ZXYD. ZYX8 .以下那一个术语与数据的存储结构无关？（）。A.栈9 .哈希表C.线索树D.双向链表10 对于栈操作数据的原则是（）。A.先进先出11 后进先出C.后进后出D.不分顺序10 .深度为K的二叉数，结点数最多有（）。A. 2KB. 2K-1C. 2K-1D. 2K-1-111 .在带有头结点的单链表中插入一个新结点时不可能修改（）。A.头指针B.头结点指针域C.开始结点指针域D.其他结点指针域12 . 一个栈的输入序列为12345,则下列序列中不可能是栈的输出序列的是（）OA. 23415B. 54132C. 23145D. 1543213 .设有一个10阶的对称矩阵A,采用压缩存储方式，以行序为主存储，all为 第一元素，其存储地址为1,每个元素占一个地址空间，则a43的地址为（）。A. 35B. 34C. 9D. 1014 .以下数据结构中，（）是非线性数据结构A.树B.字符串C.队D.栈15 .若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删 除运算，则利用（）存储方式最节省时间。A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表16 .循环队列存储在数组A0. . m中，则入队时的操作为（）。A. rear=rear+lB. rear=（rear+l）%（m-1）C- rear=(rear+ l)%mD. rear=(rear+l)%(m+l)17 .广义表()的长度为()。A. 0B. 1C. 2D.不确定18 .将两个各有nl和n2个元素的有序表(递增)归并成一个有序表，仍保持其递 增顺序，则最少的比较次数是()。A. nlB. n2C. nl+n2-lD. min(nl;n2)19 .广义表 L=(a,b)，则为()°A. bB. (b)C.()D.空表20 .在有n个叶子结点的哈夫曼树中，其结点总数是()。A. nB. 2nC. 2n-lD. 2n+l21 .设二叉树的根结点层次为1,所有含有15个结点的二叉树中，最小高度是()OA. 6B. 5C. 4D. 322 .深度为4的三叉树至多有()个结点。A. 13B. 14C. 40D. 4123 .当一棵有n个结点的满二叉树按层次从上到下，同层次从左到右将数据存放 在一维数组Al. . n中时，数组中第i个结点的左孩子为（）。A. A2i（2i<=n）B. A2i+l2i+l<=n）C. Ai/2D.无法确定24 .在下述结论中，正确的是（）。只有一个结点的二叉树的度为0；二叉树的度为2；二叉树的左右子树可任 意交换；深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。A.B.C.D.25 .在二叉排序树中，关键字值最大的结点的（）。A.左指针一定为空B.右指针一定为空C.左右指针均为空D.左右指针均不为空26 . 一般情况下，将递归算法转换为等价的非递归算法应设置（）。A.数组B.队列C.二叉树D.栈27 .n个顶点的连通无向图用邻接矩阵表示时，该矩阵至少有（）个非零元素。A. 1B. n-1C. nD. n+128.下列哪一种图的邻接矩阵是对称矩阵？（）。A.有向图B.无向图C. AOV 网D. AOE 网29.下列关于AOE网的叙述中，不正确的是（）。A.关键活动不按期完成就会影响整个工程的完成时间B.任何一个关键活动提前完成，那么整个工程将会提前完成C.所有的关键活动提前完成，那么整个工程将会提前完成D.某些关键活动提前完成，那么整个工程将会提前完成30.要连通具有n个顶点的有向图，至少需要（）条弧。A. n-1B. nC. n+1D. 2n31 .进程控制块是描述进程状态和特征的数据结果，一个进程（）。A.可以有多个进程控制块B.只能有唯一的进程控制块C.可以没有进程控制块D.可以和其他进程公用一个进程控制块32 .虚拟储存器给用户提供了特大的地址空间。实际上它是（）。A.扩大物理内存容量B.扩大物理外存容量C.扩大逻辑内存容量D.扩大逻辑外存容量33 .进程的三个基本状态在一定的条件下可以互相转化，进程由就绪状态变为运行 状态的条件是（）。A.时间片用完B.等待某一件事C.等待的某一件事已经发生D.被进程调度程序选中34 .在下列文件的物理结构中，（）不利于文件长度动态增长。A.顺序结构B.链接结构C.索引结构D. Hash结构35 .如果I/O设备于存储设备进行数据交换不经过CPU来完成，这种数据交换方 式是（）。A.程序查询B.中断方式C. DMA方式D.无条件存取方式36 .在可变分区存储管理中，最优适应分配算法要求对空闲区表项按（）进行排列。A.地址从大到小B.地址从小到大C.尺寸从大到小D.尺寸从小到大37 .竞争计算机系统资源的基本单位是（）。A.进程B.作业C.程序D.过程38 .在可变分区分配方案中，为了实现主存的空间分配，采用（）进行管理。A.页表B.段表C.段表+页表D.分区分配表+空闲区表39.UNIX文件系统对盘空间的管理采用（）。A. FAT表法B.位示图法C.空闲块链接法D.空闲块成组链接法40.下列算法可用于磁盘移臂调度的是（）。A. LRU算法B.电梯调度算法C.时间片轮转法D.响应比高者优先算法。二、填空题（本大题共12填空，每填空1分，共12分）1.在线性表的两个元素a和b之间插入一个数据元素e,已知P为其单链表存储 结构中指向结点a的指针，S为指向e的指针，请按顺序写出指针修改的语句。nnnnP1） ）12） ） 23） 广义表的长度为-3,深度为4。4） Dijkstra最短路径算法从源点到其余各顶点的最短路径长度按5次序产 生，设有向图如下，则当源点取顶点1时，从顶点1到2的最短路径长度是5010