清华计算机试卷

2001年数据结构与程序设计试题内容：一、试给出下列有关并查集(mfsets)的操作序列的运算结果：union(1,2),union(3,4),union(3,5),union(1,7),union(3,6),union(8,9),union(1,8),union(3,10),union(3,11),union(3,12),union(3,13),union(14,15),union(16,0),union(14,16),union(1,3),union(1,14)(union 是合并运算,在以前的书中命名为 merge)要求(1)对于union(ij),以i作为j的双 亲;(5分)(2)按i和j为根的树的高度实现union(i,j),高度大者为高度小者的双亲；(5分)(3)按i和j为根的树的结点个数实现union(ij),结点个数大者为结点个数小者的双亲；(5分)二、设在4地(A,B,C,D)之间架设有6座桥，如图所示：A要求从某一地出发,经过每座桥恰巧一次，最后仍回到原地(1)试就以上图形说明:此问题有解的条件是什么？(5分)(2)设图中的顶点数为n,试用C或Pascal描述与求解此问题有关的数据结构并编写一个算法，找出满足要求的 一 条 回 路.(10分)二、针对以下情况确定非递归的归并排序的运行时间(数据比较次数与移动次数)：(1)输入的n个数据全部有序；(5分)(2)输入的n个数据全部逆向有序；(5分)(3)随机地输入n个 数 据.(5分)四、简单回答有关AVL树的问题.(1)在有N个结点的AVL树中,为结点增加一个存放结点高度的数据成员，那么每一个结点需要增加多少个字位(bit)?(5分)(2)若每个结点中的高度计数器有8bit,那么这样的AVL树可以有多少层?最少有多少个关键码？(5分)五、设一个散列表包含hashSize=13个表项，.其下标从0到12,采用线性探杳法解决冲突.请按以卜要求,将下列关键码散列到表中.10 100 32 45 58 126 3 29 200 400 0(1)散列函数采用除留余数法，用hashSize(取余运算)将各关键码映像到表中.请指出每一个产生冲突的关键码可能产生多少次冲突.(7分)(2)散列函数采用先将关键码各位数字折叠相加，再用hashSize将相加的结果映像到表中的办法.请指出每一个产生冲突的关键码可能产生多少次冲突.(8分)六、设棵二叉树的结点定义为struct BinTreeNodeElemType data;BinTreeNode*left Child,*rightChild;)现采用输入广义表表示建立二叉树.具体规定如下：(1)树的根结点作为由子树构成的表的表名放在表的最前面；(2)每个结点的左子树和右子树用逗号隔开.若仅有右子树没有左子树，逗号不能省略.(3)在整个广义表表示输入的结尾加上一个特殊的符号(例如#)表示输入结果.例如,对于如右图所示的二叉树，其广义表表示为A(B(D,E(G,),C(,F)A/B C/D E F/G此算法的基本思路是:依次从保存广义表的字符串Is中输入每个字符.若遇到的是字母(假定以字母作为结点的值)，则表示是结点的值，应为它建立一个新的结点，并把该结点作为左子女(当k=1)或有子女(当k=2)链接到其双亲结点上.若遇到的是左括号”(“，则表明子表的开始，将k置为1；若遇到的是右括号)”,则表明子表结果.若遇到的是逗号“，“，则表示以左子女为根的子树处理完毕，应接着处理以右子女为根的子树，将k置为2.在算法中使用了一个栈s,在进入子表之前,将根结点指针进栈，以便括号内的子女链接之用.在子表处理结束时退栈.相关的栈操作如下：MakeEmpty(s)置空栈Push(s,p)元素p进栈Pop(s)进栈Top(s)存取栈顶元素的函数下面给出了建立二叉树的算法，其中有5个语句缺失.请阅读此算法并把缺失的语句补上.(每空3分)Void CreateBinTree(BinTreeNode*&BT,char ls)Stack s;MakeEmpty(s);BT=NULL;置二叉树BinTreeNode*p;int k;istream ins(ls);把串Is定义为输入字符串流对象insChar ch;ins ch;从ins顺序读入一个字符While(ch!=#)逐个字符处理，直到遇到#为止Switch(ch)case(J:(1)k=1;break;case):pop(s);break;case,:(2)_break;default:p=new BinTreeNode;_p-leftChild=NULL;p-rightChild=NULL;if(BT=NULL)_(4)_else if(k=1)top(s)-leftChild=p;else top(s)-rightChild=p;)_)七、下面是个用C编写的快速排序算法.为了避免最坏情况，取基准记录pivot采用从left,right和mid=(left+right)/2中取中间值，并交换到right位置的办法.数组a存放待排序的一组记录，数据类型为Type,left和right是呆排序子区间的最左端点和最右端点.Void quicksort(Type a&#;,int leftjnt right)Type temp;lf(leftright)Type pivot=median3(a,left,right);Int l=left,j=right-1;For(;)While(ij&aipivot)i+;While(ij&pivot pivot)temp=ai:ai=aright;aright=temp;quicksort(a,left,i-1);/递归排序左子区间quicksort(a,i+1 .right);递归排序右子区间)(1)用C或Pascal实现三者取中子程序median3(a,3ft,right);(5分)(2)改 写quicksort算法，不用栈消去第二个递归调用quicksorts,i+1,right);(5分)(3)继续改写quicksort算法，用栈消去剩下的递归调用.(5分)编译原理及操作系统试题内容:编译原理部分1.(5%)给出下述NFA M 的五元组表示，并将其确定化2(5%)构造一个不具有e-转移的NFA M，,使得L(M，)=L(M)3(10%)证明文法GA是 LR 文法.GA|:A-BAI eB-aBlb4(5%)证明合并不存在冲突(移进/归约、归约/归约)的LR(1)项目集的同心集不会产生新的移进/归约冲突.5.(5%)对目标代码运行时的存储空间采用基于过程活动记录的栈式分配方案，举例说明象PASCAL这样的语言如何实现对非局部变量的访问.6(15%)文法 GR:R-R+R I R-R I R*l(R)I a I b I e（1）证 明 文 法 G R 生 成 字 母 表=a,b 上的所有正规表达式（用+代替”1”，连接符 没有省略）（2）证明此文法是二义的（3）根据正规式的三个运算符（+,*）（或，连接，闭包）的优先性和结合性约定重新构造一个等价的LL（1）文法7（5%）找出下列流图中的回边和回边组成的循环.编译中利用流图完成什么工作?操作系统部分一、名次解释（10分）多道程序、多重处理、进程、线程、虚存二、画出NT操作系统的线程状态转移图（10分）三、UNIX系统与Linux系统等中都提供pipe文件功能，简述pipe。的工作原理。（10分）四、设周期性任务Pl,P2,P 3 的周期T l,T2,T 3 分别为100,150,350；执行时间分别为 20,40,100o试计算后回答是否可以用频率单调调度算法进行调度？（10分）五、I/O控制可用那几种方式实现？各有何优缺点？（10分）