pku_cs_计算机软件综合2001020405 (2)

《pku_cs_计算机软件综合2001020405 (2)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、启用前机密北京大学2001年硕士研究生入学考试试题考试科目：计算机软件基础（统考）考试时间：2001年1月14日下午招生专业：计算机科学技术研究方向：把各题的答案写在试卷后的答题纸上一、（35分）请简要回答下列问题。1、a.从空的二叉树开始，根据字典顺序（注意：‘tea’<‘teach’），严格按照二叉检索树（或称二叉排序树）插入算法，依次插入head、he、tea、teach、twin、hot、toss。请画出插入所有结点后的二叉检索树；b.请画出根据a中给出的7个单词所形成的（Briandais）字符树（树林）（提示：该字符树中的

2、每个叶结点对应于一个单词）。2、设散列表的地址空间为0~10（共10个存储单元），散列函数为h(k)=kmod11。用线性探测法解决碰撞，现依次插入关键码95，14，27，68，60，则最后一个元素60的插入位置下标是什么？3.将关键码195，14，527，68，121，46，57，575，60，89按最低位优先法进行基数排序，进行一次分配和收集后得到的序列是多少？4．初始关键码序列为E,D,X,K,H,L,M,C,P,用筛选法所建的最大值堆得到的序列是什么？5．一组含权值不同的字母已对应好Huffman编码，如果某一字母对应于编码0

3、01，请回答下列问题（可以用*，？等通配符描述）：a.什么形式的编码不可能是该编码集中的合法编码？b.什么形式的编码肯定对应于该字母集合中的字母？6．假设图1中顶点（即结点）在内存的以字母顺序存放。a.请画出它的最小支撑树（或称最小生成树）；b.请画出它的深度优先搜索树。7．图2是一棵4阶B-树（或称B树）（每个结点最多允许2~4个子结点，最底层的结点中只允许有1~3个关键码），a.请画出从该树中插入关键码113后相应的B-树;b.请画出从没有插入关键码113之前的原树上删除关键码150后的B-树。二、（15分）数据结构设计和算法分析

4、题1．请参考以下二叉树的ADT（抽象数据类型）定义，设计一个树（不必考虑树林的情况）的抽象数据类型（只需要用类Pascal、类C/C++语言或类Java给出其主要功能函数或过程的接口说明。不需要指定存储结构，也不需要写出函数或过程的实现方法）。抽象数据类型中的运算（即函数或过程）应该加足够的注释（最好用中文注释）。示例：二叉树的ADT逻辑定义：二叉树由结点的有限集合组成，这个集合或者为空，或者由一个根结点以及两棵不相交的，分别称作这个根的左子树和右子树的二叉树组成。这两棵子树的根称为此二叉树根结点的子结点。从一个结点到它的两个子结点都

5、有边相连，这个结点称为其子结点的父结点。运算：ClassBinNode{//BinarytreenodeclassPrivate://don’tgivetheinnerstorestructurePublic:BinNode*liftchild();//returnleft;BinNode*rightchild();//returnright;BELEMvalue();//returnelement;voidsetValue(BELEMval);//returnNodevalue;boolisLeaf();//ReturnTRUEif

6、isaleaf};classBinTree{Public:voidclear();//sendallnodestofreestoreBinNode*root();//Returntherootofthetreevoidnewroot(ELEM，BinNode*,BinNode*);//Mergetwotreesvoidinorder(BinNode*rt);//inordertraversal};2.利用树结点抽象数据类型所提供的函数或过程，按层次次序将结点的值打印出来。层次次序首先打印出根（高度为0的结点），接着从左到右打印第1层（

7、高度为1）的所有结点，再接着从左到右打印第2层（高度为2）的所有结点，依此类推。传入参数为树根的指针，函数的C++原型如下：Voidlevelprint_tree(GTNode*rt);3.请分析你所设计的层次周游算法的时间代价（或称时间复杂性），要给出分析过程。注意：算法不应该涉及具体的存储结构，也不允许不通过函数过程而直接引用树结构的私有数据成员。允许直接引用常见数据结构如栈、队列等。抽象数据类型和算法都应该加足够的注释。三、（10分）在一个虚拟页式存储管理系统中采用最近最少使用（LRU）页面淘汰算法，每个进程分配2个页框，初始时

8、页框为空。有如下两个程序：VARC:ARRAY[1…256,1…128]OFinteger;i,j;integer;A程序：FORi：=1to256DOFORj：=1to128DOC[i,j]：=0;B程序：FORj：=