for (i=1;i<=e;i++) { scanf(beg,end); g.data[beg][end]=1; } return g; }
4、设计函数，将不带表头结点的单链表清除。 lklist clear ( lklist head) { while (head) { p=head ;
head=head->next ;
free(p); }
return head;
}
5、设计递归函数，求一棵非空的二叉树的深度。 int depth (bitreptr root) { if (!root) return 0;
else { dl=depth(root->lc);
dr=depth(root->rc);
return 1+(dl>dr?dl:dr); } }
6、设线性表A=(a1,a2,a3,?,an)以带头结点的单链表作为存储结构。编写一个函数，删去A中序号为奇数的结点。
7、试编写一个算法，能由大到小遍历一棵二叉树。
void ShowTree ( TreeNode* current ) {
if (current == NULL) {
return; }
ShowTree(current->right);
cout << endl << current->data; ShowTree(current->left); }
8、对于二叉树的链接实现,完成非递归的中序遍历过程。
void InOrder(BiTree bt)
{BiTree s[],p=bt; //s是元素为二叉树结点指针的栈，容量足够大
int top=0;
while(p || top>0)
{while(p) {s[++top]=p; bt=p->lchild;} //中序遍历左子树 if(top>0){p=s[top--]; printf(p->data); p=p->rchild;} //退栈，访问，转右子树
} }
9、利用直接插入排序的方法对一组记录按关键字从小到大的顺序排序。
10、给出一棵表示表达式的二叉树，其中运算符和运算对象都用一个字符表示，求该表达式的值。设二叉树用二叉链表表示，表达式中仅包含二元运算，函数operate(a, b, op)可求任何一种二元运算的值，其中参数op表示运算符，a和b分别表示左右两个运算对象。算法中允许直接引用函数operate (函数operate 不必定义)，如果需要还允许引用栈和队列的基本操作。
11、编写算法，将一单链表逆转。要求逆转在原链表上进行，不允许重新构造一个链表（可以申明临时变量、指针）。
该链表带头节点、头节点和数据节点的结构定义如下 typedef struct LNode {
ElemType data; Struct LNode* next; }List, LNode;
函数定义：void invert(List & L)
12、编写算法计算给定二叉树中叶结点的个数。 其中树节点定义如下 typedef struct BiTNode{ DataType data;
Struct BiTNode *LChild, * RChild; }BiTNode, *BiTree;
函数定义：CountLeaf (BiTree T, int & LeafNum) void CountLeaf (BiTree T, int & LeafNum) {
if(T) {
if(!T->lchild&&!T->rchild)
LeafNum++; else {
CountLeaf(T->lchild, LeafNum); CountLeaf(T->rchild, LeafNum);
}
}
}
13、写出二叉树前根遍历的递归算法
已知二叉树结点定义为： struct node{
elemtp data;
struct node *lc,*rc; );
Typedef struct node * bitreptr(指向根),*tpointer(指向一般结点);
void preorder(bitreptr P) //P指向树根节点
void preorder(bitreptr P) {
If(P!=0) {
printf(P->data); preorder(P->lc); preorder(P->rc);
}
}
14、在邻接矩阵存储结构上实现图的基本操作： InsertVex(G,v)//插入顶点
Status Insert_Vex(MGraph &G, char v)//在邻接矩阵表示的图G上插入顶点v {
if(G.vexnum+1)>MAX_VERTEX_NUM return INFEASIBLE; G.vexs[++G.vexnum]=v; return OK; }//Insert_Vex
15、已知某哈希表的装载因子小于1，哈希函数H（key）为关键字（标识符）的第一个字母在字母表中的序号，处理冲突的方法为线性探测开放定址法，请编写一个按第一个字母的顺序输出哈希表中所有关键字的算法。
void Print_Hash(HashTable H)//按第一个字母顺序输出Hash表中的所有关键字,
void Print_Hash(HashTable H)//按第一个字母顺序输出Hash表中的所有关键字,其中处理冲突采用线性探测开放定址法 {
for(i=1;i<=26;i++)
for(j=i;H.elem[j].key;j=(j+1)%hashsize[sizeindex]) //线性探测 if(H(H.elem[j].key)==i) printf(\}//Print_Hash
int H(char *s)//求Hash函数
{
if(s) return s[0]-96; //求关键字第一个字母的字母序号(小写) else return 0; }//H
16、写出二叉树后根遍历的递归算法 已知二叉树结点定义为： struct node{
elemtp data;
struct node *lc,*rc;
);
Typedef struct node * bitreptr(指向根),*tpointer(指向一般结点);
void aftorder(bitreptr P) {
If(P!=0) {
aftorder(P->lc); aftorder(P->rc);
printf(P->data); }
}
17、在邻接矩阵存储结构上实现图的基本操作：DeleteArc(G,v.w)//删除边（v,w）
Status Delete_Arc(MGraph &G,char v,char w)//在邻接矩阵表示的图G上删除边(v,w) {
if((i=LocateVex(G,v))<0) return ERROR; if((j=LocateVex(G,w))<0) return ERROR; if(G.arcs[i][j].adj) {
G.arcs[i][j].adj=0; G.arcnum--; } return OK; }//Delete_Arc
18、编写一个函数或过程判定两棵二叉树是否相似，所谓两棵二叉树s和t相似，即是要么它们都 为空或都只有一个结点，要么它们的左右子树都相似。
[题目分析]两棵空二叉树或仅有根结点的二叉树相似；对非空二叉树，可判左右子树是否相似，采用递归算法。
int Similar(BiTree p,q) //判断二叉树p和q是否相似
{if(p==null && q==null) return (1);
else if(!p && q || p && !q) return (0); else return(Similar(p->lchild,q->lchild) Similar(p->rchild,q->rchild))
}//结束Similar
19、在邻接矩阵存储结构上实现图的基本操作：InsertArc(G,v,w)//插入边（v,w）
Status Insert_Arc(MGraph &G,char v,char w)//在邻接矩阵表示的图G上插入边(v,w) {
if((i=LocateVex(G,v))<0) return ERROR; if((j=LocateVex(G,w))<0) return ERROR; if(i==j) return ERROR; if(!G.arcs[i][j].adj) {
G.arcs[i][j].adj=1;
G.arcnum++; }
return OK; }//Insert_Arc
20、假设有一个1000*1000的稀疏矩阵，其中1%的元素为非零元素，现要求哈希表作存储结构。试设计一个哈希表并编写相应算法，对给定的行值和列值确定矩阵元素在哈希表上的位置。
Status Locate_Hash(HashTable H,int row,int col,KeyType key,int &k)//根据行列值在Hash表表示的稀疏矩阵中确定元素key的位置k {
h=2*(100*(row/10)+col/10); //作者设计的Hash函数 while(H.elem[h].key&&!EQ(H.elem[h].key,key)) h=(h+1) 000; if(EQ(H.elem[h].key,key)) k=h; else k=NULL; }//Locate_Hash
&&
分析:本算法所使用的Hash表长20000,装填因子为50%,Hash函数为行数前两位和列数前两位所组成的四位数再乘以二,用线性探测法处理冲突.当矩阵的元素是随机分布时,查找的时间复杂度为O(1).