第1页 / 共18页
第2页 / 共18页
第3页 / 共18页
第4页 / 共18页
第5页 / 共18页
第6页 / 共18页
第7页 / 共18页
第8页 / 共18页
东北大学计算机专业考研强化辅导班试题.doc
数据结构算法习题（201312）
（一）线性表、查找、排序
1、用尽可能短的时间将链表表长 m 的 hb 接在表长 n 的链表 ha 后面，形成链表 hc。
void ListConcat(LinkList ha,LinkList hb,LinkList &hc)//把链表 hb 接在 ha 后面形成链表 hc
{ if(m<=n){ hc=ha;p=ha; }
else { hc=hb;p=hb; }
while(p->next) p=p->next;
if(m<=n) p->next=hb;
else p->next=ha;
}//ListConcat
2、删除元素递增排列的链表 L 中所有值相同的元素
Status Delete_Equal(Linklist &L)//删除元素递增排列的链表 L 中所有值相同的元素
{
p=L->next;q=p->next; //p,q 指向相邻两元素
while(p->next)
{
if(p->data!=q->data)
{
p=p->next;q=p->next; //当相邻两元素不相等时,p,q 都向后推一步
}
else
{
while(q->data==p->data)
{
t=q; q=q->next;
free(t);
}
p->next=q;p=q;q=p->next; //当相邻元素相等时删除多余元素
}//else
}//while
}//Delete_Equal
3、把元素递增排列的单链表链表 A 和 B 合并为 C,且 C 中元素非递增排列,使用原空间。
void reverse_merge(LinkList &A,LinkList &B,LinkList &C)//把元素递增排列的链表 A 和 B 合并为 C,且 C 中
元素递减排列,使用原空间
{
pa=A->next;pb=B->next;pre=NULL; //pa 和 pb 分别指向 A,B 的当前元素
while(pa||pb)
{
if(pa->datadata||!pb)
{
pc=pa;q=pa->next;pa->next=pre;pa=q; //将 A 的元素插入新表
}
else
{
1
pc=pb;q=pb->next;pb->next=pre;pb=q; //将 B 的元素插入新表
}
pre=pc;
}
C=A;A->next=pc; //构造新表头
}//reverse_merge
4、已知单链表 A、B、C 递增（非递减）有序，删除 A 表中的既在 B 中又在 C 中出现的元素。
void LinkList_Intersect_Delete(LinkList &A,LinkList B,LinkList C)
{
p=B->next;q=C->next;r=A;
while(p&&q&&r)
{
if(p->datadata) p=p->next;
else if(p->data>q->data) q=q->next;
else
{
u=p->data; //确定待删除元素 u
while(r->next->datanext; //确定最后一个小于 u 的元素指针 r
if(r->next->data==u)
{
s=r->next;
while(s->data==u)
{
t=s;s=s->next;free(t); //确定第一个大于 u 的元素指针 s
}//while
r->next=s; //删除 r 和 s 之间的元素
}//if
while(p->data=u) p=p->next;
while(q->data=u) q=q->next;
}//else
}//while
}//LinkList_Intersect_Delete
5、对 L=（a1,a2,a3……,.an）按 L=（a1,a3,a……an,an-1..a4,a2）的顺序重排双向循环链表 L 中的所有结点
void OEReform(DuLinkedList &L)//按规定顺序重排双向循环链表 L 中的所有结点
{
p=L.next;
while(p->next!=L&&p->next->next!=L)
{
p->next=p->next->next;
p=p->next;
} //此时 p 指向最后一个奇数结点
if(p->next==L) p->next=L->pre->pre;
else p->next=L->pre;
2
p=p->next; //此时 p 指向最后一个偶数结点
while(p->pre->pre!=L)
{
p->next=p->pre->pre;
p=p->next;
}
p->next=L; //按题目要求调整了 next 链的结构,此时 pre 链仍为原状
for(p=L;p->next!=L;p=p->next) p->next->pre=p;
L->pre=p; //调整 pre 链的结构
}//OEReform
6、带 freq 域的双向循环链表上的查找，双向链表按 freq 域非递增有序。
DuLNode * Locate_DuList(DuLinkedList &L,int x)//带 freq 域的双向循环链表上的查找
{
p=L.next;
while(p.data!=x&&p!=L) p=p->next;
if(p==L) return NULL; //没找到
p->freq++;q=p->pre;
while(q->freq<=p->freq) q=q->pre; //查找插入位置
if(q!=p->pre)
{
p->pre->next=p->next;p->next->pre=p->pre;
q->next->pre=p;p->next=q->next;
q->next=p;p->pre=q; //调整位置
}
return p;
}//Locate_DuList
7、不带头结点的单循环链表，按关键字递增有序。指针 h 和 t，h 指关键字最小的结点，t 指当前查找到的
结点，根据与给定值 K 的比较，从 h 或 t 的后继结点起查找。
typedef struct {
LNode *h; //h 指向最小元素
LNode *t; //t 指向上次查找的结点
} CSList;
LNode *Search_CSList(CSList &L,int key)//在有序单循环链表存储结构上的查找算法
SList &L,int key)//在有序单循环链表存储结构上的查找算法
,假定每次查找都成功
{
if(L.t->data==key) return L.t;
else if(L.t->data>key)
for(p=L.h,;p->data!=key;p=p->next);
else
for(p=L.t,;p->data!=key;p=p->next);
L.t=p; //更新 t 指针
return p;
}//Search_CSList
3
8、双向冒泡排序算法，即相邻两趟是反方向起泡的冒泡排序。
void Bubble_Sort2(int a[ ],int n)//相邻两趟是反方向起泡的冒泡排序算法
{
low=0;high=n-1; //冒泡的上下界
change=1;
while(lowa[i+1])
{
a[i]<->a[i+1];
change=1;
}
high--; //修改上界
for(i=high;i>low;i--) //从下向上起泡
if(a[i]a[i-1];
change=1;
}
low++; //修改下界
}//while
}//Bubble_Sort2
9、监视哨设在高下标端的插入排序算法。
void Insert_Sort1(SqList &L)//监视哨设在高下标端的插入排序算法
{
k=L.length;
for(i=k-1;i;--i) //从后向前逐个插入排序
if(L.r[i].key>L.r[i+1].key)
{
L.r[k+1].key=L.r[i].key; //监视哨
for(j=i+1;L.r[i].key>L.r[j].key;++j)
L.r[j-1].key=L.r[j].key; //前移
L.r[j-1].key=L.r[k+1].key; //插入
}
}//Insert_Sort1
10、输入一组关键字,建立 Hash 表,表长为 m,用链地址法处理冲突。
typedef *LNode[MAXSIZE] CHashTable; //链地址 Hash 表类型
Status Build_Hash(CHashTable &T,int m)//输入一组关键字,建立 Hash 表
{
if(m<1) return ERROR;
4
T=malloc(m*sizeof(WORD)); //建立表头指针向量
for(i=0;idata=key;q->next=NULL;
n=H(key);
if(!T[n]) T[n]=q; //作为链表的第一个结点
else
{
for(p=T[n];p->next;p=p->next);
p->next=q; //插入链表尾部.本算法不考虑排序问题.
}
}//while
return OK;
}//Build_Hash
5
（二）二叉树、线索树、排序树
1、判断两棵树是否相似。
int Bitree_Sim(Bitree B1,Bitree B2)//判断两棵树是否相似的递归算法
{
if(!B1&&!B2) return 1;
else if(B1&&B2&&Bitree_Sim(B1->lchild,B2->lchild)&&Bitree_Sim(B1->rchild,B
2->rchild))
return 1;
else return 0;
}//Bitree_Sim
2、后序遍历二叉树的非递归算法,不用栈。
typedef struct {
int data;
EBTNode *lchild;
EBTNode *rchild;
EBTNode *parent;
enum {0,1,2} mark;
} EBTNode,EBitree; //有 mark 域和双亲指针域的二叉树结点类型
void PostOrder_Nonrecursive(EBitree T)//后序遍历二叉树的非递归算法,不用栈
{
p=T;
while(p)
switch(p->mark)
{
case 0:
p->mark=1;
if(p->lchild) p=p->lchild; //访问左子树
break;
case 1:
p->mark=2;
if(p->rchild) p=p->rchild; //访问右子树
break;
case 2:
visit(p);
p->mark=0; //恢复 mark 值
p=p->parent; //返回双亲结点
}
}//PostOrder_Nonrecursive
3、不用栈非递归中序遍历有双亲指针的二叉树
typedef struct {
int data;
PBTNode *lchild;
PBTNode *rchild;
6
PBTNode *parent;
} PBTNode,PBitree; //有双亲指针域的二叉树结点类型
void Inorder_Nonrecursive(PBitree T)//不设栈非递归遍历有双亲指针的二叉树
{
p=T;
while(p->lchild) p=p->lchild; //向左走到尽头
while(p)
{
visit(p);
if(p->rchild) //寻找中序后继:当有右子树时
{
p=p->rchild;
while(p->lchild) p=p->lchild; //后继就是在右子树中向左走到尽头
}
else if(p->parent->lchild==p) p=p->parent; //当自己是双亲的左孩子时后继就是双亲
else
{
p=p->parent;
while(p->parent&&p->parent->rchild==p) p=p->parent;
p=p->parent;
} //当自己是双亲的右孩子时后继就是向上返回直到遇到自己是在其左子树中的祖先
}//while
}//Inorder_Nonrecursive
4、求先序遍历中第 k 个结点的值。
int c,k; //这里把 k 和计数器 c 作为全局变量处理
void Get_PreSeq(Bitree T)//求先序序列为 k 的结点的值
{
if(T)
{
c++; //每访问一个子树的根都会使前序序号计数器加 1
if(c==k)
{
printf("Value is %d\n",T->data);
exit (1);
}
else
{
Get_PreSeq(T->lchild); //在左子树中查找
Get_PreSeq(T->rchild); //在右子树中查找
}
}//if
}//Get_PreSeq
main()
{
7
...
scanf("%d",&k);
c=0; //在主函数中调用前,要给计数器赋初值 0
Get_PreSeq(T,k);
...
}//main
5、求二叉树中以值为 x 的结点为根的子树深度
int Get_Sub_Depth(Bitree T,int x)//求二叉树中以值为 x 的结点为根的子树深度
{
if(T->data==x)
{
printf("%d\n",Get_Depth(T)); //找到了值为 x 的结点,求其深度
exit 1;
}
}
else
{
if(T->lchild) Get_Sub_Depth(T->lchild,x);
if(T->rchild) Get_Sub_Depth(T->rchild,x); //在左右子树中继续寻找
}
}//Get_Sub_Depth
int Get_Depth(Bitree T)//求子树深度的递归算法
{
if(!T) return 0;
else
{
m=Get_Depth(T->lchild);
n=Get_Depth(T->rchild);
return (m>n?m:n)+1;
}
}//Get_Depth
6、删除所有以元素 x 为根的子树
void Del_Sub_x(Bitree T,int x)//删除所有以元素 x 为根的子树
{
if(T->data==x) Del_Sub(T); //删除该子树
else
{
if(T->lchild) Del_Sub_x(T->lchild,x);
if(T->rchild) Del_Sub_x(T->rchild,x); //在左右子树中继续查找
}//else
}//Del_Sub_x
void Del_Sub(Bitree T)//删除子树 T
{
if(T->lchild) Del_Sub(T->lchild);
8
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
