清华大学 2011 年考博题 回忆版 Y
x eOI#L
&<UM
BAS
数据结构及算法设计 op6CA "w
m"o ;L3
1. 设有字母1,2,3,S,P,A按顺序进栈。问：（1） 出栈的字母组合有多少种。（2）设高级语言的变量是以字母开始的字母和数字的组合，那么出栈的组合中变量名有哪些。 qU#BJON]BR
V( -mD
2. （1） 一个8层得AVL树，其最多，最少有多少个节点。 p\JfFfC
（2）设以AVL树为动态查找树，在查找元素K的过程中，搜索路径上的所有节点的平衡因子都是0，若查找K失败，在插入元素K之后，树T的高度时候一定会增加1，为什么？ sf OHarww
XwlbJ=mf
3．设图G=（V,E）顶点个数为n，有下列算法： k&. Jk
B"
E = { 所有的边，权值按从大到小的顺序排列}； &9"-`-[e:
Len = E中边的数目 kn>$lTHQ
i=1 |j VM&R2s
While（ Len >n-1） e{v=MxO= S
{ QC X8IIHG
If( 去除E条边后，图还是连通的) 删除E; hYM@?/(q
Else W~p/,H
cM
保留边E; cg*)0U-
_(
} .?!N^_ Ez3
证明上面的算法最终得到的是最小生成树 d\FJFMW*9
h<SQL97N
4. 设置换选择排序可用的内存大小为M， 待排序的数列长度为n， 设有数列{100 51 9 17 61 101 71 。。。} ?zsB6B?;
（1） 置换选择排序得到的归并段的平均长度是多少 hQDTS>U
（2） '8T=~R6
（3） 求置换选择排序的初始败者树和 排序得到的各个归并段 X0M1(BJgGo
mUz\ra;z
5. 数组A中顺序存放着N个元素，编写算法将这个元素存放在带头结点的循环链表中，要求算法的时间复杂度为O（nlogn），空间复杂度为1。
$LLA,?;!
K%Rj8J7|u?
6. 设有n*n整数元素的矩阵，现作如下行变换，计算各行元素的平均值，将矩阵各行按其平均值从小到大的顺序进行行变换。 f4guz
Q]w&N30
7. 定义树的每层节点个数为该层的宽度，树的宽度为各层宽度的最大值。试编写算法求以T为根节点的数的宽度 (Gw,2 -A
o, !T2&}
计算机控制理论 （部分） 3:f[gV9K
0`I-2M4F*Q
一 选择题 （5*2） aKd+CO:
二 判断题 （10*1） Cc, `}SP
]wWPXx[>/
三 连续传递函数与离散传递函数的转换 fS"Hr 0
@j4 U^"_QB
四 有限拍控制器的设计问题 A?o Xq b
D Kw*~0
五 xGG,2W+z
|K^"3`SJ
六 计算最优控制器和Kalman滤波 A;O~#Chvd
\^V`ds*.
七 最小方差控制器计算 {"
4e+y
CY&
hIh~S@
八 简要说明 Smith 控制器和 极点配置控制的异同点 d.2mT?`#
