发布时间 : 星期二 文章数据结构与算法期末练习题(含答案)更新完毕开始阅读5cb46c3d02d8ce2f0066f5335a8102d276a2612d
}//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).