中国科学院计算技术研究所 一九九二年招收硕士学位研究生入学考试试题 试题名称：软件基础 填空（每空1分） 线性表可采用的存储结构有 和 二种。 用于拓扑排序的图是 图。 操作系统的特征是 和 。 根据联接在文法符号上的属性之间的依赖关系，可把属性分为 和 两大类。 进程间存在的制约关系可以归结为 和 两种。 产生死锁的原因是 和 。 对逻辑表达式的计算可采用 和 方式。 有n个结点的完全二叉树的深度为 。 在串的模式匹配中，若主串长为m，子串长为n，则KMP算法的时间复杂度为 。 二叉树的遍历方式有 、 和 三种；图的遍历方式有 和 两种。 简答 （3分）什么是哈希（Hash）查找？ （4分）UNIX系统中设备管理的主要特点是什么？ （3分）树(A(B(E(K , L) , F) , (C(G) , D(H(M) , I , J)))所对应的二叉树表示是什么? （3分）已知初始关键字为[49，38，65，97，76，13，27，49]，现分别用直接插入排序和快速排序方法对之进行排序，请分别给出两种方法第二趟排序之后的结果。 （4分）什么是地址重定位？动态重定位的结果是什么？ （3分）什么是数据的逻辑结构和物理结构？ （5分）程序运行的所需的一片连续存储——活动记录有哪些域？它们各有什么作用？ （5分）有一C语言程序如下： main（） { int x； x = 25； printf（“%d\n”，x）； } 经过编译联接后，由符号调试器跟踪其执行，却无法检查变量x的值，因为调试器报告“无此变量”。试解释其原因。 问答题 （8分）试比较Pascal程序（语法结构位置任意，空格等空白字符作为单词分隔符）和Fortran程序（语法结构位置固定，空格无意义）对词法分析的影响。 （8分）下列文法是否为LR（1）文法？若是，给出分析表，若不是，是说明理由。 S AA A aA | a （8分）设一消息缓冲区由如下信息组成： Sptr 指向发送进程的指针 Nptr 指向下一个消息缓冲区的指针 Size 消息长度 Text 消息正文 请给出两个进程通过该类消息缓冲区进行通讯的过程。 （8分）Swap指令是一条可在一个存储周期内完成交换两个字节的内容的操作的硬件指令。其功能用Pascal语言描述如下： procedure Swap（var a，b：integer） var temp：integer； begin temp：= a； a ：= b： b ：= temp； end 请用该指令实现关锁原语Lock（w）和开锁原语Unlock（w）。 算法设计 （9分）二叉树的深度定义为由根结点到叶子结点的最长路径，设计一算法，计算二叉树的深度。 （9分）写出堆排序（heap sort）的算法，指出其最坏情况下的时间复杂度。