清华大学1999计算机专业考研真题.pdfVIP

清华大学1999计算机专业考研真题

清华大学99计算机专业考研试题

一、请回答下列问题。（10分）

1）快速排序的最大递归深度是多少？最小递归深度是多少？

2）八皇后问题的最大递归深度是多少？

3）对列表设制表头结点的作用是什么？（至少说出版发行

条好处）。

4）在分析二叉查找数性能时常加入失败结点，即外结点，

从而行成扩充的二叉数。若设失败点i所在层次为Li，那么查找

失败到达失败点时所作的比较次数是多少？

5）如何对有向图中的顶点号重新按排可使得该图的临接矩

阵中到所有的确都集中到对角线上？

二、设有本质区别个数据do，for，repet，while，它们

排在一个有序表中，其查找概率分

别为p0=0.2,p=0.15，p3=0.03，p4=0。02，p5=0。01。

doforifrepetwhile

q0p1q1p2q2p3q3p4q4p5q5

1）试画出对该有序表采纳顺序查找时的判定，树和采纳折

半查找时的判定树。（6分）2）分别计算顺序查找时的查找成功

和不成功的平均查找长度。（4分）

3）判定是顺序查找好？是折半查找好？（2分）

三、下面的数据表给出了在一篇有19710个词的英文词文

1

中出现最普遍的确15个词的出现

频度

1）假设一个英文字符等价于log26=4.7010bits,那么这些

词按bits计的平均长度是多少？

（5分）

2）假定一篇正文仅由上述数据表中的词组成，那么它们的

最佳编码是什么？平均长度是多少？（5分）

四、设有12个数据{25，40，33，47，12，66，72，87，

94，22，5，58}，它们存储在散列

表中，利用双散列解决冲突，要求为插入新数据的平均查找

次数不超过三次。

1）该散列表的大小M应设计多大？（4分）

2）该散列表设计相应的散列函数（用除留余数法）和计算

寻找下一个“空位”时向前垮步步长的再散列函数。（6分）

3）顺次将各个数据散列到表中。（6分）

4）计算查找成功的平均查找次数。（2分）

五、向式(+b)n

展开式的系数

C（n，0）=1，C（n，n）=1，对于n=0

C（n，k）=C（n—1，k）+C（n-1，k-1），对于0kn形

成著名的杨辉三角形，如图所示。

1

1）试写一个递归算法，跟据一上公试生成C（n,k）。（6分）

2）试画出算法C（6，4）的递归树。（4分）

3）试写一个非递归算法，既不用数助也不用栈，对于任意

的0=k=n计算C（n，k）。

（6分）

六、一个双端队列deque是限定在两端end1，end2都可

进行插入和删除的线性表。队空条

件是end1=end2。若用顺序方式来组织双端队列，试根据

下列要求，定义双端队列的结构，并给出在指定端i（i=1，2）

的插入enq和删除deq操作地实现。（12分）

1）当队满时，最多只能有一个元素可以是空的。

2）在做两端的插入和删除时，队列中其它元素一律不动。