中科院计算机技术研究所1999年硕士生入学试题数据结构和程序设计一、选择题(20 分每空2分)1.___ 的遍历仍需要栈的支持。
1.前序线索树2.中序线索树3.后序线索树2.若度为m的哈夫曼树中,其叶结点个数为n,则非叶结点的个数为___。
1.n-12.[n/m]-13.[(n-1)/(m-1)]4.[n/(m-1)]-15.[(n+1)/(m+1)]-13.最优二*树(哈夫曼树)、最优查找树均为平均查找路径长度∑wh最小的树,其中对最优二*树,n表示___,对最优查找树,n表示___; 构造这两种树均___。
1.结点数2.叶结点数3.非叶结点数4.度为二的结点数5.需要一张n各关键字的有序表6.需要对n个关键字进行动态插入7.需要n个关键字的查找概率表8.不许要任何前提4.对于前序遍历与中序遍历结果相同的二*树为___; 对于前序遍历与后序遍历结果相同的二*树为___。
1.一般二*树2.只有根结点的二*树3.根结点无左孩子的二*树4.根接点无右孩子的二*树5.所有结点只有左子树的二*树6所有结点只有右子树的二*树5.m路B+树是一棵___, 其结点中关键字最多为___个, 最少为___个。
1.m路平衡查找树2.m路平衡索引树3.m路trie树4.m路键树5.m-16.m7.m+18.[m/2]-1 9.[m/2] 10.[m/2]+1二、填空题(10 分,每空一分)1.对于给定的n个元素,可以构造出的逻辑结构有___,___,___,___四种。
2.具有n个关键字的B-树的查找路径长度不会大于___。
3.克鲁斯卡尔算法的时间复杂度为___, 他对___图较为适合。
4.深度为k(设根的层数为1)的完全二*树至少有___个结点, 至多有___个结点, k 和结点数n之间的关系是___。
三、问答题(10 分,每题5分)1.一棵非空的有向树中恰有一个顶点入度为0，其他顶点入度为1.但一个恰有一个顶点的入度为0，其他顶点入度为一的有向图却不一定是一棵有向树。
请举例说明之。
2.若有n个元素以构成一个小根堆，那么如果增加一个元素为K(n+1)，请用文字简要说明你如何在log2(n) 的时间内将其重新调整为一个堆？四、阅读下述程序,指出程序的输出。
(10 分)void g(int**);main(){int line[100],i;int *p=line;for(i=0;i<100;i++){*p=i;g(&p);}for(i=0;i<100;I++)printf("%d\n",line[i]);}void g(int**p){(**p)++;(*p)++;}五、编程题。
(共50分,要求写出设计思想和程序注解)1.设一单向链表的头指针为head,链表的记录中包含着整数类型的key域,试设计算法, 将此链表的记录按照key递增的次序进行就地排序.(10分)2.给定一个整数数组b[0..N-1], b中连续相等元素构成的子序列称为平台.试设计算法,求出b中最长平台的长度.(20分)3.自由树(即无环连通图) T=(V,E)的直径是树中所有点对间最短路径长度的最大值,即T的直径定义为MAX d(u,v) 这里d(u,v)表示顶点u 到顶点v的最短路径长度(路径长度为路径中所含的边数).试写一算法求T的直径,并分析算法的时间复杂度(时间复杂度越小得分越高)(20分)计算机原理及系统结构一填充题(每空1分,共30分)1.为了实现CPU对主存储器的读写访问,他们之间的连线按功能划分应当包括___,___,____.2.在浮点加法运算中,主要的操作内容及步骤是___,___,___.3.从计算机系统结构的发展和演变看,早期的计算机是以___为中心的系统结构,而近代的计算机是以___为中心的系统结构.4.一条微指令可划分为___字段和___字段;微指令的基本格式可分为___和___.5.从广义上讲,计算机中引入并行性有三种基本途径,分别是___,___,___.6.在多级存储体系中,Cache存储器的主要功能是______,虚拟存储器的主要功能是______.7.设阶码8位(最左一位为符号位),用移码表示,尾数为24位(最左一位为符号位),用规格化补码表示,则它所能表示的最大正数的阶码为___,尾数为___,;绝对值最小的负数的阶码为___,尾数为___.8.在下列常用术语后面,写出相应的中文名称:VLSI______MPP______RISC______DMA______9.外设接口的主要功能是______,______和______.10.在由n台计算机构成的并行计算机中,其运行程序的加速比一般都小于n,其主要原因是______和______.二.选择一个最恰当的答案(每题2分,共20分)1.在指令格式中,采用扩展操作码设计方案的目的是___.1.减少指令字长度;2.增加指令字长度;3.保持指令字长度不变而增加指令操作得数量;4.保持指令字长度不变而增加寻址空间.2.用于科学计算的计算机中,标志系统性能的主要参数是___.1.主时钟频率2.主存容量3.MFLOPS;4.MIPS3.当前设计高性能计算机的重要技术途径是___.1.提高CPU主频2.扩大主存容量3.采用非冯若依曼结构4.采用并行处理技术4.下列体系结构中，最适合多个任务并行执行的体系结构是___.1.流水线向量机结构;2.堆栈处理机结构;3.共享存储多处理机结构;4.分布存储多计算机结构5.对于低速输入输出设备,应当选用的通道是___.1.数组多路通道2.字节多路通道3.选择通道4.DMA专用通道6.在计算机系统中，表征系统运行状态的部件是___.1.程序计数器2.累加计数器3.中断计数器4.程序状态字7.为使虚存系统有效的发挥其预期的作用,所运行的程序应具有的特性是___. 1.该程序不应含有过多的I/O操作. 2.该程序的大小不应超过实际的内存容量;3.该程序应具有较好的局部性;4.该程序的指令间相关不应过多.8.某虚拟存储器采用页式内存管理,使用LRU页面替换算法,考虑下面的页面访问地址流(每次访问在一个时间单位中完成),1,8,1,7,8,2,7,2,1,8,3,8,2,1,3,1,7,1,3,7假定内存容量为4个页面,开始时是空的,则页面失效次数是___.1.42.53.64.79.某计算机系统中的软盘启动器以中断方式与处理机进行I/O通信,通信中以16bit为传输单位,传输率为50kB/s,每次传输的开销(包括中断)为100拍,处理器的主频为50 MHZ,则软盘使用时占处理器时间的比例是___.1. 0%2. 5%3. 1.5%4. 15%10.某一SRAM 芯片,其容量为1024*8位,除电源和接地端外,该芯片引脚的最小数目为___.1. 202. 223. 254. 30三.(10分)某计算机的字长为16位,存储器按字编址,访存指令如下:15 11 87 0┌───┬─┬──────┐M值寻址方式│OP │M│ A │0 立即寻址└───┴─┴──────┘ 1 直接寻址2 间接寻址3变址寻址4相对寻址其中OP是操作码,M定义寻址方式(见右表),A为形式地址设PC和Rx分别为程序计数器和变址寄存器,字长为16位问:1.该格式能定义多少种指令?2.各种寻址方式的寻址范围为多少字?3.写出各种寻址方式的有效地址EA的计算式.四.(8分)已知x=1.1011 , y=-0.1001 ,用补码一位乘法计算x*y.(要求过程)五.(12分)某计算机逻辑框图如下图所示,它有两条独立的总线BUS1,BUS2和两个独立的存储器IM和DM,IM为指令存储器,它的最大容量为16384字(字长18位),DM为数据存储器,它的最大容量为65536字(字长16位).图中控制信号及其意义见表.1.指出下列各存储器的位数程序计数器PC,指令寄存器IR,通用寄存器R1和R2,累加器AC0和AC1 ,指令存储器的数据寄存器IDR,数据寄存器的地址寄存器DAR 和数据寄存器的数据寄存器DDR;2.若减法指令格式为17 10 9 0OP A其功能是将寄存器R2的内容与数据存储器中某一单元内容相减,差存入累加器ACI中,该数据存储器单元地址为R1中内容与减法指令码中A相加之和。
而且,该指令码在IM中的地址已在PC中.试画出该指令的指令指令周期操作流程图,并写出实现每一步操作所需的控制信号.表:控制信号功能Xm 将寄存器X输入端的信息"打入"寄存器XCi(i=1,2,..12) 信息可流过该控制点R/W R/W=R时,读DM;R/W=W时,写DMRD 读IM+1 PC的内容加1+ ALU 进行BUS1+BUS2运算- ALU 进行BUS1- BUS2运算(附图见图四)六.(10分)如果采用下图所示的双输入端的加一乘双功能静态流水线,其每个功能段的经过时间均为一拍Δt,在加法时按1->2->3->5连接,乘法时按1->4->5连接,流水线的输出可以直接送到其输入端或存入缓冲器,不记期间的传送延迟,操作数可连续提供.对向量A=(a1,a2,a3,a4),B=(b1,b2,b3,b4),采用上述流水线完成点积A*B,则完成该计算所虚的最少拍数是多少?并画出此时的流水线的时空图,计算此时流水线的吞吐率,加速比和效率.(附图见图五)七.(10分)设一个按位编制的虚拟存储器,它可以满足1k个任务的需要,但在一段较长的时间内一般只有四个任务在使用,故用容量为四行的相连存储器组硬件来缩短被变换的虚地址中的用户位数,每个任务的程序空间最大可达4096个页,每页为512字节,实主存容量为2^20 位,设快表用按地址访问的存储器构成，行数位,快表的地址是经过散列技术形成的.为减少散列冲突,配有两套独立的相等比较器电路(这时,快表的每行包含两个单元,各存放一个进行地址交换的表目).请设计该地址变换机构,内容包括:1.画出其虚实地址经快表变换的逻辑示意图;2.相连存储器组中每个寄存器的相连比较位数;3.散列变换硬件的输入位数和输出位数;4.每个相等比较器的位数;5.快表的总位数.编译原理与操作系统一.(15分)有表达式如下:A+B*(C-D)**N (**为幂乘)(1)给出该表达式的逆波兰式表示(后缀式);(2)给出上述表达式的四元式和三元式序列.二.(15分)有C程序如下:main(){printf("%d,%d,%d\n",10);}(1)试着写出上述printf语句输出的结果;(2)从运行环境和printf的实现分析为什么会有这样的输出结果.三.(5分)构造一个DFA(确定的有限自动机),使之接受含偶数个"1"的0,1串集.四.(5分)有文法G,其产生式如下:S->S(S), S->ε/*空产生式*/试写出一个语法制导定义,它输出配对的括号个数.五.(10分)已知某语言L={a^(m)b^(n)|n>m>=0}.试写出产生该语言的两个文法G1和G2,其中G1是LR(1)文法,G2是非LR(1)和非二义性文法.六.填空(每空一分,共20分)1.现代操作系统的两个最基本的特征是___和___.2.进程控制块的初始化工作包括___,___和___.3.在操作系统中引入线程概念的主要目的是___.4.unix系统v中,系统向用户提供的用于创建新进程的系统调用是___;用于建立无名管道的系统调用是___;用于创建有名管道的系统调用是___.5.unix系统v中,引起进程调度的原因有___,___,___和___等.6.在分区分配算法中,首次适应算法倾向于优先利用内存中___部分的空闲分区,从而保留了___部分的大空闲区.7.进行设备分配时所需的数据表格主要有___,___,___和___等.8.利用符号链实现文件共享时,对文件主删除了共享文件后造成的指针悬空问题,解决的方法是___.七.(8分)在消息传递通信方式下,A.发送进程和接收进程在通信过程中可以采用那三种同步方式?B.试以下面给出的发送进程和接收进程(将接收到的数据存入S)为例,说明当接收进程执行到标号为L2的语句时,采用这三种同步方式,X的值可能各是多少?发送进程P: 接收进程Q:M=10;L1: send M to Q; L1: receive S from P;L2: M=20; L2: X:=S+1;goto L1;八.(8分)一系统具有150个存储单元,在T0时刻按下表所示分配给3个进程:进程Maximum demand Current allocationP1 70 25P2 6040P3 6045对下列请求应用银行家算法分析判定是否是安全的:A.第4个进程P4到达,最大需求60个存储单元,当前请求分配25个单元.B.第4个进程P4到达,最大需求50个存储单元,当前请求分配35个单元.如果是安全的请给出一个可能的进程安全执行序列.如果是不安全的,请说明原因.九、(14分)设正在处理器上执行的一个进程的页表如下.页表的虚页号和物理块号是十进制数,起始页号(块号)均为0.所有的地址均是存储器字节地址,页的大小为1024字节.A.详述在设有快表的请求分页存储管理系统中,一个虚地址转换成物理内存地址的过程.B.下列虚地址对应与什么物理地址: (1)5499; (2) 2221;虚页号状态位访问位修改位物理块号0 1 10 4111 1 72000---3 1 00 24 0 00---5 1 0 1 0注释:访问位---当某页被访问时,其访问位被置为1.人工智能1.什么是产生式知识表示?给出这种表示方法的优缺点(10分)2.什么是语义网络知识表示?给出这种表示方法的优缺点(10分)3.什么是启发式搜索?并以八数码难题为例,说明其原理.(15分)4.专家系统包括那些基本部件?每一部分的主要功能是什么?(15分)5.在MYCIN系统中采用可信度进行非精确推理.以知第一条规则的可信度CF[H,E1] =0.4 ,第二条规则的可行度CF[H,E2]=0.3,计算该结果H的可信度CF[H,E1&E2](15分)6.请给出学习系统的简单模型,并简要说明各部分的功能.(15分)7.任选一种归纳学习方法,说明实例学习过程.(20分)(主观题无参考答案)。