华中科技大学2011年研究生入学考试试题
数据结构与算法
一．术语解释：（25'）
1线性表
2树的结点的层次
3排序
4完全图
5最小生成树
二．单项选择：（25'）
1在数组｛1，2，3，4，5，6，7，8，9，10｝中折半查5，需要的比较次数是（）A1B2C3D4
2假定问题规模为N时，某递归算法的时间复杂度记为T（N），已知T(1)=1，
T(N)=2T(N/2)+N/2，用O表示的时间复杂度为（）
A O(N)
B O(NlogN)
C O(N²)
D O(N²logN)
3一棵二叉树的先序便利输出为ABCDEFGH，中序遍历为CBEDAFHG，则其先序遍历输出为（）【此题的确问的是先序遍历】
A CBDEAFGH
B CBEDAFHG
C BCEDFAHG D以上都不对
4栈和队列的共同点是（）
A先进先出B后进先出
C插入删除只能在端点进行D没有共同点
5起泡排序的时间复杂度是（C）【此题原试卷将答案附上了】
A O(N)
B O(NlogN)
C O(N²)
D O(N²logN)
三．简答（60'）
1用一个数组实现两个栈，尽可能利用存储空间，写出两个栈的插入、删除操作算法。2已知一组关键字为｛27、25、23、37、35、33、77、75、73、97、95、93、103｝，按哈希函数H(key)=key Mod11（表长11），用连地址法处理冲突，画出哈希表。
3一个递归函数具有如下形式
Void func(int n)
{
if(n>0)
{
func(n/2);
printf("d%",n*n);
func(n/2);
}
return;
}
请依次写出fun(1)，fun(2)，fun(3)，fun(5)执行的结果，其时间复杂度为多少？
4一个通信网络中共有九中字符，其概率分别为0.14、0.23、0.15、0.03、0.18、0.1、0.02、
0.11、0.04，画出相应的赫夫曼树来设计其赫夫曼编码。
5V₁→V₂→V₃→∧；V₂→V₄→V5→∧；V3→V5→V6→∧；V4→∧；
V5→V7→V8→∧；V6→V8→∧；V7→∧；V8→V9→∧；V9→∧，
画出这个逻辑结构的图示，分别写出从V₁出发的深度优先和广度优先搜索序列。
数据结构与算法考研真题四．应用编程题：（40'）
1在一个整形数组a中既有负数又有正数，编写一个算法将a中所有负数移到整数之前，要求其时间复杂度为O(n)，n为数组长度，并且只使用常数个辅助空间。
例如：a[]={1,2,3,4,-1,1,-2,-1,-4}执行算法后的输出为a[]={-4,-1,-2,-1,1,4,3,2,1}
2编写一个C函数，输入一个二叉树的根节点，返回这棵树中所有值大于0的节点值之和，如果根为空，返回0。
二叉树的链式存储结构对应的C语言的结点类型定义如下：
typedef struct node{
ElemType data;
struct node*lchild;
struct node*rchild;
}BTree;
说明：1.本试题为回忆版试题，某些题目的数值或者语言表述可能与原版不一致；
2.本试题仅供大家学习交流使用，严禁用于各类商业用途。