清华大学 1995 年考研试题

《清华大学 1995 年考研试题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、清华大学1995年考研试题一、已知三个带头结的线性链表A。B和C中的结点均已元素值自小至大非递减排列可能存在两个值相同的结点），编写算法对A表进行如下操作：使操作后的链表A中仅留下三个表中均包含的数据元素的结点，且没有值相同的结点，并释放所有结点。限定算法的时间复杂度为O（m+n+p），其中m、n和p分别为三个表的长度。（15分）二、画出下列广义表的存储结构图，并利用取表头和表尾的操分离出原子e（a.（（）.ｂ），（（（ｅ））））。（10分）三、写出如何判别给定序列ｐ１，ｐ２，。。。。。。。ｐｎ能否由车厢１，２。。。。。

2、ｎ经调度得到的准则，并证明之。（其中ｐ１，ｐ２。。。。。。ｐｎ为１，２。。。。ｎ的一个排列）。（１０分）四、何谓ｔｒｉｅ树？试构造一棵对应关键字的ｔｒｉｅ树，请注意应该使树的深度尽可能小。｛program,programmer,programming,processor,or｝（１０分）五、假设串的存储结构如下所示，编写算法实现串的置换操作。（１５分）TYPEstrrp=RECORDch:ARRAY[1..maxlen]OFchar;curlen:0..maxlenEND;六、编写递归算法，依据树的双亲表示法及其根结点创

3、建树的孩子－兄弟链表存储结构。要求写算法以前先写出这两种存储结构的类型说明。（２０分）七、编写对有序表进行顺序查找的算法，并写出对有序表进行顺序查找的判定树。假设每次查找时的给定为随机值，又查找成功和不成功的概率也相等，试求进行每一次查时给定值进行比较的关键字个数的期望值。（２０分）清华大学1996年考研试题一、计算下列各程序中语句＠的频度。1.p:=1;k:=0;whilep

4、dobeginP:=2*p;﹫:k:=K+1endend;二、写出和下列递归过程等价的非递归过程PROCEDUREtest(VARsum:integer);VARa:integer,BEGINread(a);IFa=0THENsum=1ELSEBEGINtest(sum);sum:=sum*aEND;write(sum)END;ENDP;三、假设按低下标优先存储整形数组A（-3：8，3：5，-4：0，0：7）时，第一个元素的字节存储地址是100，每个整数占4个字节，问A（0，4，-2，5）的存储地址是什么？四、地址为（1

5、664）大小为（128）的存储块的伙伴地址是什么？地址为（2816）大小为（64）的存储块的伙伴地址是什么？五、试为下列关键字设计哈希表，要求所设计的表在查找成功时的平均查找长度不超过2.0。并请验证你造的哈希表的实际平均查找长度时否满足要求。（CHA，CAI，LAN，WEN，LONG，ZHAO，WU，LIU，CHEN，LI，WANG，CAO，YUN，CHANG，YANG）六、已知快速排序和归并排序的算法分别如下所示：PROCEDUREqksort(VARr:listtype;s,t:integer);BEGINIFs<

6、1THENBEGINqkpass(r,s,t,k);qksort(r,s,k-1);qksortd(r,k+1,t)ENDEND;PROCEDUREmergesort(VARr,r1:listtype;s,t:integer);BEGINIFs=tTHENr1[s]:=r[s]ELSEBEGINMERSEORT(r,r2,s,(s+t)DIV2);MERSEORT(R,R2,(S+T)DIV2+1,t);MERGE(r2,s,(s+t)DIV2,t,r,l)ENDEND;若对下列关键字序列进行快速排列和归并排列，分别写出

7、三次调用过程qkpass和过程merge后的结果。（98，36，77，42，23，65，84，10，59，37，61，180七、令G=（V，E）为一个有向图，编写一个给图G中每一个顶点赋以一个整型序号的算法，并满足以下条件：若从顶点I年顶点j有一条弧则应使I〈j。八、试利用下列栈和串的基本操作完成下述填空题。Initstack(s)置s为空栈；Push(s,x)元素x入栈;Pop(s)出栈操作;Gettop(s)返回栈顶元素；Sempty(s)判栈空函数；Setnull(st)置串st为空串；Length(st)返回串s

8、1的长度；Equal9s1,s2)判串s1和s2是否相等的函数；Concat(s1,s2)返回联接s1和s2之后的串；Sub(s,I,1)返回s中第i个字符；Empty(st)判串空函数FUNCinvert(pre:string;varexp:string):Boolean;{若给定的表达式的前缀式pre正确，本过程