中国科学院计算所一九九二年软件基础试题

中国科学院计算所一九九二年软件基础 一．填空（每空1分）1．线性表可采用的存储结构有_______________和_______________二种。2．用于拓扑排序的图是_______________图。3．操作系统的特征是_______________和_______________。4．根据联接在文法符号上的属性之间的依

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

[1] [2]  下一页