中科院计算机技术研究所1998年硕士生入学考试试题.doc_第1页
中科院计算机技术研究所1998年硕士生入学考试试题.doc_第2页
中科院计算机技术研究所1998年硕士生入学考试试题.doc_第3页
中科院计算机技术研究所1998年硕士生入学考试试题.doc_第4页
中科院计算机技术研究所1998年硕士生入学考试试题.doc_第5页
全文预览已结束

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

中科院计算机技术研究所1998年硕士生入学试题数据结构和程序设计(要求:算法题目写注解 )一.填空(15分,每空一分)1.用循环链表表示的队列长度为n,若只设头指针,则出队和入队的时间复杂度分别是_和_; 若只设尾指针,则出队和入队的时间复杂度分别是_和_.2.设广义表L=( (),() ) ,则head(L)是_;tail(L)是_;L的长度是_;深度是_.3.深度为h的完全二*树至少有_个结点;至多有_个结点;h和结点总数n之间的关系是_.4.在n个记录的有序顺序表中进行折半查找,最大的比较次数是_.5.在一棵m阶B+树中,若在某结点中插入一个新关键字而引起该结点分裂,则此结点中原有的关键字的个数是_.6.n个顶点的连通图用邻接矩阵表示时,该矩阵至少有_个非零元素. 二.请在下列各题中选择一个正确的答案(20分 ,每题2分)1.算法的时间复杂度取决于a.问题的规模 b.待处理数据的初态 c.both a and b 2.消除递归不一定需要使用栈,此说法a.true b.false 3.假定有k个关键字互为同义词,若用线性探测法把这k个关键字存入散列表中,至少要进行多少次探测?a.k-1 b.k c.k=1 d.k(k+1)/2 4.若需要在O(nlog2(n)的时间内完成对数组的排序,且要求排序是稳定的,则可选择的排序方法是:a.快速排序 b.堆排序 c.归并排序 d.直接插入排序 5.用ISAM和VSAM组织文件属于:a.顺序文件 b.索引文件 c.散列文件 6.若一个有向图的邻接矩阵中,主对角线以下的元素均为零,则该图的拓扑有序序列a.存在 b.不存在 7.将两个各有n个元素的有序表归并成一个有序表,其最少的比较次数是a.n b.2n-1 c.2n d.n-1 8下述二*树中,那一种满足性质:从任意结点出发到根的路径上所经过的结点序列按其关键字有序:a.二*排序树 b.哈夫曼树 c.AVL树 d.堆 9.以知待排序的n个元素可分为n/k个组,每个组包含k个元素,且任一组内的个元素均分别大于前一组内的所有元素和小于后一组内的所有元素,若采用基于比较的排序,其时间下限应为:a.O(klog2(k) b.O(klog2(n) c.O(nlog2(k) d.O(nlog2(n) 10.在叶子数目和权值相同的所有二*树中,最优二*树定是完全二*树,该说法:a.正确 b.错误 三.设二*排序树T中各结点关键字互不相同,x是T的叶子,y是x的双亲.证明y.key是T中大于x.key的所有关键字中的最小者,或是小于x.key的所有关键字的最大者.(10分) 四.(共15分)设数组A的长度为2N,前N个元素A1.N递减有序,后N个元素AN+1.2N递增有序,且2N是2的整数次幂,即k=log2(2N) 为整数.例如A1.8=90,85,50,10,30,65,80,100 满足上述要求,这里N=4,k=3,A的前4个元素和后4个元素分别递减和递增有序.用次例调用如下的Demo过程,并要求:(1).给出for循环中每次执行 PerfectShuffle(A,N)和CompareExchange(A,N)的结果.(10分) (2)解释Demo的功能.(2分) (3)给出Demo的时间复杂度.(3分)Procedure PerfectShuffle (Var A:arraytype; N:integer)i:=1; j:=1;while i=N do Bj:=Ai;Bj+1:=Ai+N;i:=i+1;j:=j+2;A1.2N:=B1.2N;/B copy to A Procedure CompareExchange(Var A:arraytype; N:integer)j:=1;while jAj+1 thenAjAj+1;/exchange Aj and Aj+1j:=j+2; Procedure Demo(Var A:arraytype; N:integer)/the length of A is 2N,k=log2(N) is integerfor i:=1 to log2(2N) do PerfectShuffle(A,N);CompareExchange(A,N); 五.(共20分)(1).设二*排序中关键字由1至1000的整数构成,现要检索关键字为363的结点,下述关键字序列中那些可能是二*排序树上搜索到的序列,那些不可能是二*排序树上搜索到的序列?(5分)(a)2,252,401,393,330,344,397,363 (b)924,220,911,244,898,258,362,363(c)925,202,911,240,912,245,363 (d)2,399,387,219,266,382,381,278,363(2).通过对(1)的分析,写一个算法判定给定的关键字序列(假定关键字互不相同)是否可能是二*排序树的搜索序列.若可能是返回真,否则返回假.可假定被判定的序列已存入数组中.(15分) 六.(共20分)图的D-搜索类似于BFS,不同之处在于使用栈代替BFS中的队列,入出队列的操作改为入出栈的操作.即当一个顶点的所有邻接点被搜索后,下一个搜索的出发点应该是最近入栈(栈顶)的顶点.(1)用邻接表做存储结构,写一个D-搜索算法(15分)(2)用 D-搜索方法搜索右图,设初始出发点为1,写出顶点的访问次序和响应的生成树,当从某顶点出发搜索他的邻接点是,请按邻接点序号递增序搜索,以使答案唯一.(5分)编译原理和操作系统一.(10分)某操作系统下合法的文件名为device:name.extension其中第一部分(device:)和第三部分(.extension)可缺省,若device,name和extension都是字母串,长度不限,但至少为1,画出实现这种文件名的确定有限自动机. 二.(10分)下面的二义文法描述命题演算公式,为他写一个等价的非二义文法.S-S and S|S or S|not S|p|q|(S) 三.(10分)把表达式- (a+b)*(c+d)+(a+b+c)翻译成四元式. 四.(10分)由于文法二义引起的LR(1)分析动作冲突,可以根据消除二义的规则而得到LR(1)分析表,根据此表可以正确识别输入串是否为响应语言的句子.对于非二义非LR(1)文法引起的LR(1)分析动作的冲突,是否也可以根据什么规则来消除LR(1)分析动作的冲突而得到LR(1)分析表,并且根据此表识别相应语言的句子?若可以,你是否可以给出这样的规则? 五.(10分)下面程序的结果是120.但是如果把第5行的abs(1)改成1的话,则程序结果为1.试分析为什么会有这不同的结果. int fact()static int i=5;if(i=0) return(1); else i=i-1; return( i+abs(1)*fact(); main()printf(factor or 5=%dn,fact(); 六.名词解释(每小题2分,共10分)1) 线程 2)管程 3)管道 4)I/O重定向 5)动态地址重定位 七.填空(每空0.5分, 共10分)1.为了赋予操作系统以某些特权,使得操作系统更加安全可靠地工作,实际操作系统中区分程序执行的两种不同的运行状态是_;_态程序不能执行特权指令.2.引起进程调度的原因有:_,_和_.3.在一个请求式页式存储系统中,一个程序的页面走向为1,2,1,4,3,2,3,5,1,2,1,3.假定分配给该程序的存储块数为4,则采用FIFO,LRU和LFU 页面置换算法时,访向过程中的缺页次数分别为_,_和_.4.通道技术的引入,实现了_与_的并行;_与_的并行;_与_的并行.5.设备分配程序除了向提出I/O请求的进程分配设备外,还要为他分配_,_,_6.文件系统通常向用户提供的接口有_接口和_接口.7.UNIX文件系统中通过引入_索引结点来提高文件的检索效率. 八.简答题(共10分)1.(5分)试述缺页中断的处理

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论