武汉大学考研数据结构
1.（5分）分析以下算法的时间复杂度（要求给出求解过程）。
void fun(int n)
{ int i,s=0;
while (s<n)< p="">
{
i++;
s+=i;
}
}
2.（5分）设b是二叉树（采用二叉链存储结构存储）的根结点指针，给出以下算法的递归模型并说明算法的功能：
int fun(BTNode *b)
{ if (b==NULL) return 0;
else if (b->lchild!=NULL && b->rchild!=NULL)
return fun(b->lchild)+fun(b->rchild)+1;
else
return fun(b->lchild)+fun(b->rchild);
}
3.（5分）有一个长度为12的有序表R[0..11]，按二分查法对该表进行查，在表内各元素等概率情况下查成功所需的平均比较次数是多少？（要求给出求解过程）
4.假设一个仅包含二元运算符的算术表达式以二叉链表形式存储在二叉树BT中，写出计算该算术表达式值的算法。
5.将关键码53，78，65，17，87，09，81，45，23依次插入到一棵初始为空的二叉搜索树中，画出每插入一个关键码后的二叉搜索树。
5.（4分）对于有n个顶点、e条边的图+
（1）若是无向图，采用邻接矩阵存储，其非零的元素有多少？
（2）若是有向图，采用邻接矩阵存储，其非零的元素有多少？
（3）若是无向图，采用邻接表存储，其表头结点和表结点个数是多少？
（3）若是有向图，采用邻接表存储，其表头结点和表结点个数是多少？
6．（3分）简要说明在执行快速排序算法时，若把栈换为队列会对最终排序结果有什么影响？
数据结构与算法考研真题三. 算法设计题（共25分）
1. （10分）设有一个带头结点的单链表hc，设计一个算法：
void split(LinkList *hc, LinkList *&ha, LinkList *&hb,ElemType x,ElemType y)
将hc拆分成两个带头结点的单链表ha和hb，其中ha的所有结点值均大于等于x且小于等于y，hb为其他结点。
2．（15分）假设一棵二叉树采用二叉链存储结构进行存储，每个结点的类型如下（每个结点值均为正整数且大小均不同）：
typedef struct node
{ int data;
struct node *lchild,*rchild; /*左、右孩子结点指针*/
} BSTNode;
（1）（10分）设计一个算法int isBST(BSTNode *bt)，判断二叉树bt是否是一棵二叉排序树；（2）（5分）说明你的算法的正确性。
</n)<>