2013年真题
第四题：
问题描述：已知有两个带头结点的单链表A和B，元素值递增有序，编写函数调整删减链表，使A链表的元素值为A、B的交集，并成为一个递减有序的单链表，要求写出算法思想以及相应代码：
代码：
//2013数据结构第四题
#include<stdio.h>
#include<malloc.h>
typedef struct LNode{
int data;
struct LNode *next;
} *LinkList,LNode;
void GetCommon(LinkList A,LinkList B)
{
LinkList p=A->next,q=B->next,s=NULL;
A->next=NULL;
while(p&&q)
{
if(p->data<q->data)
{
s=p->next;
free(p);
p=s;
}
else if(p->data>q->data)
{
q=q->next;//B链表不进行删除
}
else{
s=p->next;
p->next=A->next;
A->next=p;
p=s;
}
}
while(p)
{
s=p->next;
free(p);
p=s;
}
}
int main()
{
LinkList A= (LinkList) malloc(sizeof(LNode) );
LinkList a1= (LinkList) malloc(sizeof(LNode) );
LinkList a2= (LinkList) malloc(sizeof(LNode) );
LinkList a3= (LinkList) malloc(sizeof(LNode) );
LinkList B= (LinkList) malloc(sizeof(LNode) );
LinkList b1= (LinkList) malloc(sizeof(LNode) );
LinkList b2= (LinkList) malloc(sizeof(LNode) );
A->next=a1;a1->next=a2;a2->next=a3;a3->next=NULL;
a1->data=2;a2->data=3;a3->data=5;
B->next=b1;b1->next=b2;b2->next=NULL;
b1->data=2;b2->data=3;
LinkList p=A->next,q=B->next;
printf("A中元素：");
while(p){
printf("%d ",p->data);p=p->next;
} printf("\nB中元素：");
while(q){
printf("%d ",q->data);q=q->next;
}printf("\n执行取交集操作之后：\n");
GetCommon(A,B);
p=A->next,q=B->next;
printf("A中元素：");
while(p){
printf("%d ",p->data);p=p->next;
} printf("\nB中元素：");
while(q){
printf("%d ",q->data);q=q->next;
}
}
第五题：
问题描述：编写函数，用非递归算法，求二叉链表表示的二叉树T的高度要求写出算法思想以及相应代码：
代码：
//2013数据结构第五题
#include<stdio.h>
#include<malloc.h>
#define maxsize 50
typedef struct BTNode{
int data;
struct BTNode* l;
struct BTNode* r;
}BTNode,*BiTree;
int BTDepth(BiTree T){
if(!T){return 0;}
BiTree Q[maxsize],p;
int front=-1,rear=-1;
int last=0,level=0;//一层中最后一个节点，level表示已经访问的层数
Q[++rear]=T;//根节点入队，开始处理
while(front<rear)
{
p=Q[++front];
if(p->l){Q[++rear]=p->l;}
if(p->r){Q[++rear]=p->r;}
if(last==front)//如果访问到某层的最后一个节点
{
level++;
last=rear;
}
}
return level;
}
int main()
{
//自己定义一些二叉树试一试
BiTree r= (BiTree)malloc(sizeof(BTNode));
r->l=NULL;r->r=NULL;
printf("该树有%d层\n",BTDepth(r));
BiTree a21= (BiTree)malloc(sizeof(BTNode));
a21->l=NULL;a21->r=NULL;
r->l=a21;
printf("该树有%d层\n",BTDepth(r));
BiTree a31= (BiTree)malloc(sizeof(BTNode));
BiTree a32= (BiTree)malloc(sizeof(BTNode));
a21->l=a31;a21->r=a32;
a31->l=NULL;a31->r=NULL;a32->l=NULL;a32->r=NULL;
printf("该树有%d层\n",BTDepth(r));
//其他情况自己去试吧
}
2014年真题
第四题
问题描述：设带头结点的单链表L，数据元素为（a1,a2,a3,a4,…,an），编写函数调整该链表，要求是的元素顺序为（a1,a3,…,an,…,a4,a2）,要求T(n)=n，给出算法思想并写出相关代码
代码：
//2014数据结构第四题
#include<stdio.h>
#include<malloc.h>
typedef struct LNode{
int data;
LNode *next;
} *LinkList,LNode;
void fun(LinkList A){
LinkList p = A->next;
if(!p->next){return;}
LinkList q = p->next; /* p 指向 A 的第一个结点 */
LinkList B= (LinkList) malloc(sizeof(LNode) );
B->next = NULL; /* 创建链表 B */
while (p&&q)
{
p->next = q->next;
q->next = B->next;
B->next = q;
if(p->next){
p=p->next;
q=p->next;
}else{break;}
}
p->next = B->next; /* A 后接 B */
free(B);
}
int main()
{
LinkList a= (LinkList) malloc(sizeof(LNode) );
LinkList b= (LinkList) malloc(sizeof(LNode) );
LinkList c= (LinkList) malloc(sizeof(LNode) );
LinkList d= (LinkList) malloc(sizeof(LNode) );
LinkList e= (LinkList) malloc(sizeof(LNode) );
LinkList A= (LinkList) malloc(sizeof(LNode) );
a->data=11;
b->data=22;
c->data=33;
d->data=44;
e->data=55;
A->next=a;
a->next=b;
b->next=c;
c->next=d;
d->next=e;
e->next=NULL;
for(LinkList p=A->next;p!=NULL;p=p->next)
{
printf("%d ",p->data);
}printf("\n");
fun(A);
for(LinkList p=A->next;p!=NULL;p=p->next)
{
printf("%d ",p->data);
}
}
第五题
问题描述：设有一家谱树，用二叉链表结构存储（孩子兄弟表示法），树的节点信息为成员名字，编写函数，输出家谱中共有多少代以及最后一代人的人数以及成员名字，要求先给出代码再写出相应代码。
代码：
//2014数据结构第五题
#include<stdio.h>
#include<malloc.h>
#define maxsize 50
typedef struct BTNode{//和13年有所不同
int data;
struct BTNode* l;//现在l是孩子
struct BTNode* r;//现在r是兄弟
}BTNode,*BiTree;
void BTDepth(BiTree T){
if(!T){return;}
BiTree Q[maxsize],p;
int front=-1,rear=-1,top=-1;
int last=0,level=0,count=1;
Q[++rear]=T;//根节点入队，开始处理
while(front<rear)
{ p=Q[++front];//出队、访问
++top;//入栈、保存 (逻辑栈)
if(p->l!=NULL){
p=p->l;Q[++rear]=p;//有孩子就把孩子入队
while(p->r!=NULL)
{p=p->r;Q[++rear]=p;}} //其他孩子也入队
if(last==front)//如果访问到某层的最后一个节点
{ level++;
last=rear;
if(rear>front){
count=last-front;//如果这不是最后一层，就更新一下即将出队的下一层的人数
}
}
}
printf("最后一代%d个人，共有%d代\n",count,level);
while(count>0){
printf("%d ",Q[top--]->data);
count--;
}printf("\n");
}
int main()
{
BiTree root= (BiTree)malloc(sizeof(BTNode));
BiTree r11= (BiTree)malloc(sizeof(BTNode));
BiTree r12= (BiTree)malloc(sizeof(BTNode));
BiTree r13= (BiTree)malloc(sizeof(BTNode));
BiTree r14= (BiTree)malloc(sizeof(BTNode));
root->data=100;
root->l=NULL;root->r=NULL;
BTDepth(root);
root->l=r11;root->r=NULL;
r11->data=101;
r11->l=NULL;r11->r=NULL;
BTDepth(root);
r11->r=r12;
r12->data=102;
r12->l=NULL;r12->r=NULL;
BTDepth(root);
r12->r=r13;
r13->data=103;
r13->l=NULL;r13->r=NULL;
BTDepth(root);
r13->l=r14;
r14->data=104;
r14->l=NULL;r14->r=NULL;
BTDepth(root);
}
2015年真题
第四题
问题描述：设有一个带头结点的单链表L，数据元素为整数，编写函数，通过调整该链表中的节点指针，对链表进行简单选择排序（元素值从小到大），先给出算法思想，然后写出相应代码。
代码：
//2015数据结构第四题
#include<stdio.h>
#include<malloc.h>
typedef struct LNode{
int data;
LNode *next;
} *LinkList,LNode;
void ListSort(LinkList A){
LinkList B= (LinkList) malloc(sizeof(LNode) );
B->next=NULL;
LinkList pre=A,maxpre=A,p=A->next,max=A->next;
while(A->next)
{
pre=A;maxpre=A;p=A->next;max=A->next;
while(p){
if(p->data>max->data){
maxpre=pre;max=p;
}
pre=pre->next;
p=p->next;
}
maxpre->next=max->next;
max->next=B->next;
B->next=max;
}
A->next=B->next;
free(B);
}
int main()
{
LinkList a= (LinkList) malloc(sizeof(LNode) );
LinkList b= (LinkList) malloc(sizeof(LNode) );
LinkList c= (LinkList) malloc(sizeof(LNode) );
LinkList d= (LinkList) malloc(sizeof(LNode) );
LinkList A= (LinkList) malloc(sizeof(LNode) );
a->data=4;
b->data=3;
c->data=5;
d->data=2;
A->next=a;
a->next=b;
b->next=c;
c->next=d;
d->next=NULL;
for(LinkList p=A->next;p!=NULL;p=p->next)
{
printf("%d ",p->data);
}printf("\n");
ListSort(A);
for(LinkList p=A->next;p!=NULL;p=p->next)
{
printf("%d ",p->data);
}
}
第五题
问题描述：设二叉树T，用二叉链表结构存储（孩子兄弟表示法），编写函数，输出最长的一枝（根到叶子）的所有节点，先给出算法思想，然后写出相应代码。
代码：
//2015DS第五题
#include<stdio.h>
#include<malloc.h>
#define maxsize 50
typedef struct BTNode{//和13年有所不同
int data;
struct BTNode* l;//现在l是孩子
struct BTNode* r;//现在r是兄弟
}BTNode,*BiTree;
void postTravel(BiTree T)
{
BiTree S[maxsize],Q[maxsize],p=T,r=NULL;//栈用于后序非递归访问二叉树
int top=-1,front=-1,rear=-1;//队列用于存储最长路径（持续更新）
while(p||top>-1)
{
while(p){//走到最左边
S[++top]=p;
p=p->l;
}
if(!p){
p=S[top];
if(p->r&&p->r!=r)//如果有右子树且未被访问
{
p=p->r;
S[++top]=p;
p=p->l;
}
else{//如果没有右子树、或者右子树已经被访问：弹出
p=S[top--];
if(!p->l&&!p->r)// 如果该节点是叶子
{//并且这条路径是当前最长的
if(top+2>rear-front)//这里原本有个小bug被改过来了：top应该+2表示当前栈中元素
{//更新路径
int t=-1;
rear=-1;
while(t<=top){
Q[++rear]=S[++t];
}
}
}
r=p;p=NULL;
}
}
}
while(front<rear){//打印一下
printf("%d ",Q[++front]->data);
}printf("\n");
}
int main()
{
BiTree root=(BiTree)malloc(sizeof(BTNode));
BiTree r1= (BiTree)malloc(sizeof(BTNode));
BiTree r2= (BiTree)malloc(sizeof(BTNode));
BiTree r3= (BiTree)malloc(sizeof(BTNode));
BiTree r4= (BiTree)malloc(sizeof(BTNode));
root->data=100;r1->data=101;r2->data=102;r3->data=103;r4->data=104;
root->l=r1;root->r=NULL;
r1->l=NULL;r1->r=NULL;
postTravel(root);
r1->r=r2;
r2->l=NULL;r2->r=NULL;
postTravel(root);
root->r=r3;
r3->l=NULL;r3->r=NULL;
postTravel(root);
root->r=NULL;
r1->l=r3;
postTravel(root);
r2->l=r4;
r4->l=NULL;r4->r=NULL;
postTravel(root);
}
2016年真题
第四题
问题描述：设L为带头结点的单链表，元素值为整数，编写函数，删除L中的重复节点（具有相同元素值的节点只保留一个），先给出算法思想，然后写出程序代码。
代码：
//2016数据结构第四题
#include<stdio.h>
#include<malloc.h>
typedef struct LNode{
int data;
LNode *next;
} *LinkList,LNode;
void del(LinkList L)
{
LinkList p=L->next,q=NULL,pre=NULL;
if(!p){return;}
while(p){
//对于每个节点p，都要将链表里的每个节点遍历一遍确保无重复
pre=p;q=p->next;//pre保存q的前驱
while(q)
{
if(p->data==q->data)
{ //摘下q，free掉
pre->next=q->next;
free(q);
q=pre->next;
}
else{
pre=pre->next;
q=q->next;
}
}
p=p->next;
}
}
int main()
{
LinkList a= (LinkList) malloc(sizeof(LNode) );
LinkList b= (LinkList) malloc(sizeof(LNode) );
LinkList c= (LinkList) malloc(sizeof(LNode) );
LinkList d= (LinkList) malloc(sizeof(LNode) );
LinkList A= (LinkList) malloc(sizeof(LNode) );
a->data=11;
b->data=22;
c->data=11;
d->data=33;
A->next=a;
a->next=b;
b->next=c;
c->next=d;
d->next=NULL;
for(LinkList p=A->next;p!=NULL;p=p->next)
{
printf("%d ",p->data);
}printf("\n");
del(A);
for(LinkList p=A->next;p!=NULL;p=p->next)
{
printf("%d ",p->data);
}
}
第五题
问题描述：已知一棵二叉链表表示的二叉树T，编写函数，判断T是否是完全二叉树，先给出算法思想，然后给出相关程序代码。
代码：
//2016数据结构第五题
#include<stdio.h>
#include<malloc.h>
#define maxsize 50
typedef struct BTNode{
int data;
struct BTNode* l;
struct BTNode* r;
}BTNode,*BiTree;
bool check(BiTree T){
if(!T){return false;}
BiTree Q[maxsize],p;
int front=-1,rear=-1;
Q[++rear]=T;//根节点入队，开始处理
while(front<rear)
{
p=Q[++front];
if(p->l&&p->r)//左右均不空，先入队
{
Q[++rear]=p->l;
Q[++rear]=p->r;
}
else if(p->r&&!p->l)
{//左空右不空，必非完全二叉树
return false;
}
else{//左不空有空或者左右均空，则必须确保其后面的所有节点都是叶子节点，否则非完全二叉树
if(p->l&&!p->r){
Q[++rear]=p->l;
}
while(front<rear)
{
p=Q[++front];
if(p->r||p->l)
{//找到非叶子节点
return false;
}
}
}
} return true;
}
void check_p(BiTree T)
{
if(check(T)){
printf("该树为完全二叉树\n");
}else{
printf("非完全二叉树\n");
}
}
int main()
{
BiTree root=(BiTree)malloc(sizeof(BTNode));
BiTree r1= (BiTree)malloc(sizeof(BTNode));
BiTree r2= (BiTree)malloc(sizeof(BTNode));
BiTree r3= (BiTree)malloc(sizeof(BTNode));
BiTree r4= (BiTree)malloc(sizeof(BTNode));
root->data=100;r1->data=101;r2->data=102;r3->data=103;r4->data=104;
root->l=NULL;root->r=NULL;
check_p(root);
r1->l=NULL;r1->r=NULL;
root->l=r1;
check_p(root);
r2->l=NULL;r2->r=NULL;
root->r=r2;
check_p(root);
r3->l=NULL;r3->r=NULL;
r2->l=r3;
check_p(root);
r4->l=NULL;r4->r=NULL;
r1->l=r4;
check_p(root);
r1->r=r3;r2->l=NULL;
check_p(root);
}
2017年真题
第四题
问题描述：设A、B为递减有序（元素值为整型）的单链表，编写函数，利用原节点将他们合并成为一个递增有序的单链表，相同元素值只保留一个节点，先给出算法思想再给出相应代码。
代码：
//2017数据结构第四题
#include<stdio.h>
#include<malloc.h>
typedef struct LNode{
int data;
LNode *next;
} *LinkList,LNode;
LinkList Merge(LinkList A,LinkList B)
{
LinkList p=A->next,q=B->next,s=NULL;
LinkList C=(LinkList)malloc(sizeof(LNode));
C->next=NULL;
while(p&&q){
if(p->data==q->data)
{
s=p;
p=p->next;
s->next=C->next;
C->next=s;
s=q;
q=q->next;
free(s);
}
else{
if(p->data>q->data)
{
s=p;p=p->next;
}
else{
s=q;q=q->next;
}
s->next=C->next;
C->next=s;
}
}
while(p){
s=p;p=p->next;
s->next=C->next;
C->next=s;
}
while(q){
s=q;q=q->next;
s->next=C->next;
C->next=s;
}
return C;
}
int main()
{
LinkList a1= (LinkList) malloc(sizeof(LNode) );
LinkList b1= (LinkList) malloc(sizeof(LNode) );
LinkList c1= (LinkList) malloc(sizeof(LNode) );
LinkList d1= (LinkList) malloc(sizeof(LNode) );
LinkList A= (LinkList) malloc(sizeof(LNode) );
a1->data=4;//递减有序
b1->data=3;
c1->data=2;
d1->data=1;
A->next=a1;
a1->next=b1;
b1->next=c1;
c1->next=d1;
d1->next=NULL;
LinkList a2= (LinkList) malloc(sizeof(LNode) );
LinkList b2= (LinkList) malloc(sizeof(LNode) );
LinkList c2= (LinkList) malloc(sizeof(LNode) );
LinkList d2= (LinkList) malloc(sizeof(LNode) );
LinkList B= (LinkList) malloc(sizeof(LNode) );
a2->data=9;//递减有序
b2->data=5;
c2->data=3;
d2->data=1;
B->next=a2;
a2->next=b2;
b2->next=c2;
c2->next=d2;
d2->next=NULL;
for(LinkList p=A->next;p!=NULL;p=p->next)
{
printf("%d\t",p->data);
}printf("\n");
for(LinkList p=B->next;p!=NULL;p=p->next)
{
printf("%d\t",p->data);
}printf("\n");
LinkList p=Merge(A,B);
for(p=p->next;p!=NULL;p=p->next)
{
printf("%d\t",p->data);
}printf("\n");
}
第五题
问题描述：设有n个学生成绩（0-100整数）的顺序结构线性表L，编写函数，将该线性表调整为成绩及格（大于等于60）在不及格之前，要求T(n)=O(n)，S(n)=O(1)，先给出算法思想，然后给出相应代码。
代码：
//2017数据结构第五题
#include<stdio.h>
void judge(int* a,int n)
{
//主体思路是这样的，两个指针分别从首尾向中间遍历,
//首指针遇到及格的就后移，遇到不及格的就将不及格的放到尾处并将原本的尾元素置换回来
//直到两指针相遇结束。时间复杂度O(n),空间复杂度O(1)
int i=0,j=n-1;
while(i<j){
if(a[i]>=60){i++;}
else{
int temp=a[i];
a[i]=a[j];
a[j]=temp;
j--;
}
}
}
int main()
{
int a[6]={41,99,62,38,70,55};
for(int i=0;i<6;i++)
{
printf("%d\t",a[i]);
}printf("\n");
judge(a,6);
for(int i=0;i<6;i++)
{
printf("%d\t",a[i]);
}printf("\n");
}
2018年真题
第四题
问题描述：设一个带头结点的单链表L，数据元素为整数，其中大部分为正数，少数为负数，要求编写函数，采用尽可能高效的算法调整链表，实现将负数节点转移到链表尾部，并返回调整后链表中的第一个负数节点位置。先给出算法思想，再给出相应代码。
代码：
//2018数据结构第四题
#include<stdio.h>
#include<malloc.h>
typedef struct LNode{
int data;
LNode *next;
} *LinkList,LNode;
LinkList func(LinkList L)
{
if(!L){return NULL;}
LinkList A=(LinkList)malloc(sizeof(LNode));
LinkList pre=L,p=L->next,rear=A;
while(p)
{
if(p->data<0)
{
pre->next=p->next;
rear->next=p;
rear=p;
p=pre->next;
}
else{
pre=pre->next;
p=p->next;
}
}
rear->next=NULL;
pre->next=A->next;
free(A);
return pre->next;
}
int main()
{
LinkList A= (LinkList) malloc(sizeof(LNode) );
LinkList a= (LinkList) malloc(sizeof(LNode) );
LinkList b= (LinkList) malloc(sizeof(LNode) );
LinkList c= (LinkList) malloc(sizeof(LNode) );
LinkList d= (LinkList) malloc(sizeof(LNode) );
A->next=a;a->next=b;b->next=c;c->next=d;d->next=NULL;
a->data=5;b->data=-3;c->data=6;d->data=-4;
printf("A中元素：");
LinkList p=A->next;
while(p){
printf("%d\t",p->data);p=p->next;
}printf("\n");
func(A);
printf("A中元素：");
p=A->next;
while(p){
printf("%d\t",p->data);p=p->next;
}printf("\n");
}
第五题
问题描述：设二叉树T，用二叉链表结构存储，元素值为整数且互不相同，编写非递归函数，对给定的2个整数，如两个都不是T的元素，输出-2，如1个都不是T的元素，输出-1，如都是T的元素，输出两者所在层数的间隔数，先给出算法思想，再给出相应代码。
代码：
//2018数据结构第五题
#include<stdio.h>
#include<malloc.h>
#define maxsize 50
typedef struct BTNode{
int data;
struct BTNode* l;
struct BTNode* r;
}BTNode,*BiTree;
int function(BiTree T,int x,int y)
{
if(!T)return -2;
int level=0,level1=-1,level2=-1;
int last=0,front=-1,rear=-1;
BiTree Q[maxsize],p;
Q[++rear]=T;
while(front<rear)
{
p=Q[++front];
if(p->l){
Q[++rear]=p->l;
}
if(p->r){
Q[++rear]=p->r;
}
if(p->data==x){
level1=level;
}
if(p->data==y){
level2=level;
}
if(last==front)
{
level++;last=rear;
}
}
if(level1==level2&&level1==-1)
{
return -2;
}
if(level1==-1||level2==-1)
{
return -1;
}
else return level2>level1?level2-level1:level1-level2;
}
int main()
{
BiTree root=(BiTree)malloc(sizeof(BTNode));
BiTree r1= (BiTree)malloc(sizeof(BTNode));
BiTree r2= (BiTree)malloc(sizeof(BTNode));
BiTree r3= (BiTree)malloc(sizeof(BTNode));
BiTree r4= (BiTree)malloc(sizeof(BTNode));
root->data=100;r1->data=101;r2->data=102;r3->data=103;r4->data=104;
root->l=r1;root->r=r2;
r1->l=r3;r1->r=NULL;
r2->l=NULL;r2->r=r4;
r3->l=NULL;r3->r=NULL;
r4->l=NULL;r4->r=NULL;
int a=100,b=101;
printf("%d与%d在树上的层次间隔为：%d\n",a,b,function(root,a,b));
a=100,b=5;
printf("%d与%d在树上的层次间隔为：%d\n",a,b,function(root,a,b));
a=103,b=104;
printf("%d与%d在树上的层次间隔为：%d\n",a,b,function(root,a,b));
a=103,b=100;
printf("%d与%d在树上的层次间隔为：%d\n",a,b,function(root,a,b));
a=10,b=5;
printf("%d与%d在树上的层次间隔为：%d\n",a,b,function(root,a,b));
}
2019年真题
第四题
问题描述：设A、B为递减有序（元素值为整型）的单链表，编写函数，利用原节点将他们合并成为一个递增有序的单链表，相同元素值只保留一个节点，先给出算法思想再给出相应代码。
代码：
//2017数据结构第四题
#include<stdio.h>
#include<malloc.h>
typedef struct LNode{
int data;
LNode *next;
} *LinkList,LNode;
LinkList Merge(LinkList A,LinkList B)
{
LinkList p=A->next,q=B->next,s=NULL;
LinkList C=(LinkList)malloc(sizeof(LNode));
C->next=NULL;
while(p&&q){
if(p->data==q->data)
{
s=p;
p=p->next;
s->next=C->next;
C->next=s;
s=q;
q=q->next;
free(s);
}
else{
if(p->data>q->data)
{
s=p;p=p->next;
}
else{
s=q;q=q->next;
}
s->next=C->next;
C->next=s;
}
}
while(p){
s=p;p=p->next;
s->next=C->next;
C->next=s;
}
while(q){
s=q;q=q->next;
s->next=C->next;
C->next=s;
}
return C;
}
int main()
{
LinkList a1= (LinkList) malloc(sizeof(LNode) );
LinkList b1= (LinkList) malloc(sizeof(LNode) );
LinkList c1= (LinkList) malloc(sizeof(LNode) );
LinkList d1= (LinkList) malloc(sizeof(LNode) );
LinkList A= (LinkList) malloc(sizeof(LNode) );
a1->data=4;//递减有序
b1->data=3;
c1->data=2;
d1->data=1;
A->next=a1;
a1->next=b1;
b1->next=c1;
c1->next=d1;
d1->next=NULL;
LinkList a2= (LinkList) malloc(sizeof(LNode) );
LinkList b2= (LinkList) malloc(sizeof(LNode) );
LinkList c2= (LinkList) malloc(sizeof(LNode) );
LinkList d2= (LinkList) malloc(sizeof(LNode) );
LinkList B= (LinkList) malloc(sizeof(LNode) );
a2->data=9;//递减有序
b2->data=5;
c2->data=3;
d2->data=1;
B->next=a2;
a2->next=b2;
b2->next=c2;
c2->next=d2;
d2->next=NULL;
for(LinkList p=A->next;p!=NULL;p=p->next)
{
printf("%d\t",p->data);
}printf("\n");
for(LinkList p=B->next;p!=NULL;p=p->next)
{
printf("%d\t",p->data);
}printf("\n");
LinkList p=Merge(A,B);
for(p=p->next;p!=NULL;p=p->next)
{
printf("%d\t",p->data);
}printf("\n");
}
第五题
问题描述：求二叉树的宽度，给出算法思想以及使用到的数据结构。
代码：
//2019数据结构第五题 求宽度
#include<stdio.h>
#include<malloc.h>
#define maxsize 50
typedef struct BTNode{
int data;
struct BTNode* l;
struct BTNode* r;
}BTNode,*BiTree;
int BTDepth(BiTree T){
if(!T){return 0;}
BiTree Q[maxsize],p;
int front=-1,rear=-1,width=1;
int last=0;//一层中最后一个节点
Q[++rear]=T;//根节点入队，开始处理
while(front<rear)
{
p=Q[++front];
if(p->l){Q[++rear]=p->l;}
if(p->r){Q[++rear]=p->r;}
if(last==front)//如果访问到某层的最后一个节点
{
if(rear-front>width){
width=rear-front;
}
last=rear;
}
}
return width;
}
int main()
{
//自己定义一些二叉树试一试
BiTree r= (BiTree)malloc(sizeof(BTNode));
r->l=NULL;r->r=NULL;
printf("该树宽%d\n",BTDepth(r));
BiTree a21= (BiTree)malloc(sizeof(BTNode));
a21->l=NULL;a21->r=NULL;
r->l=a21;
printf("该树宽%d\n",BTDepth(r));
BiTree a31= (BiTree)malloc(sizeof(BTNode));
BiTree a32= (BiTree)malloc(sizeof(BTNode));
a21->l=a31;a21->r=a32;
a31->l=NULL;a31->r=NULL;a32->l=NULL;a32->r=NULL;
printf("该树宽%d\n",BTDepth(r));
//其他情况自己去试吧
}
2020年真题
第四题
问题描述：设单链表L的元素都是整数，编写一个高效函数，查找链表的中位节点并删除该节点，先给出算法思想然后写出相应代码。
代码：
#include<stdio.h>
#include<malloc.h>
typedef struct LNode{
int data;
LNode *next;
} *LinkList,LNode;
bool deleteMid(LinkList L){
if(!L||!L->next){
return false;
}
LNode *slow=L,*fast=L->next->next,*p=NULL;
while(fast&&fast->next){
slow=slow->next;
fast=fast->next->next;
}
p=slow->next;
slow->next=slow->next->next;
free(p);
return true;
}
int main(){
LinkList a= (LinkList) malloc(sizeof(LNode) );
LinkList b= (LinkList) malloc(sizeof(LNode) );
LinkList c= (LinkList) malloc(sizeof(LNode) );
LinkList d= (LinkList) malloc(sizeof(LNode) );
LinkList e= (LinkList) malloc(sizeof(LNode) );
LinkList A= (LinkList) malloc(sizeof(LNode) );
a->data=11;
b->data=22;
c->data=33;
d->data=44;
e->data=55;
A->next=a;
a->next=b;
b->next=c;
c->next=d;
d->next=NULL;
//e->next=NULL;
for(LinkList p=A->next;p!=NULL;p=p->next)
{
printf("%d ",p->data);
}printf("\n");
deleteMid(A);
for(LinkList p=A->next;p!=NULL;p=p->next)
{
printf("%d ",p->data);
}
}
第五题
问题描述：设一棵树，用孩子兄弟二叉链表表示，编写函数，给定树中的节点p，求p的双亲节点，给出算法思想以及相应代码。
代码：
#include <malloc.h>
#include <stdio.h>
#define maxsize 50
typedef struct BTNode {
int data;
struct BTNode* l; //现在l是孩子
struct BTNode* r; //现在r是兄弟
} BTNode, *BiTree;
BiTree BTLevel(BiTree T, BiTree target) { // target是给出的待求节点
if (!T || T == target) {
return NULL;
} //如果target是根节点、或者树为空，就结束
BiTree Q[maxsize], p, father = NULL; // father用于标记
int front = -1, rear = -1;
Q[++rear] = T; //根节点入队，开始处理
while (front < rear) {
p = Q[++front]; //出队、访问
father = p; //暂存一下可能的father
if (p->l != NULL) {
p = p->l;
Q[++rear] = p; //有孩子就把孩子入队
if (p == target) {
return father;
}
while (p->r != NULL) {
p = p->r;
Q[++rear] = p;
if (p == target) {
return father;
}
}
} //其他孩子也入队
}
return NULL;
}
int main() {
BiTree root = (BiTree)malloc(sizeof(BTNode));
BiTree r1 = (BiTree)malloc(sizeof(BTNode));
BiTree r2 = (BiTree)malloc(sizeof(BTNode));
BiTree r3 = (BiTree)malloc(sizeof(BTNode));
BiTree r4 = (BiTree)malloc(sizeof(BTNode));
root->data = 100;
r1->data = 101;
r2->data = 102;
r3->data = 103;
r4->data = 104;
root->l = r1;
root->r = NULL;
r1->l = r3;
r1->r = r2;
r2->l = r4;
r2->r = NULL;
r3->l = NULL;
r3->r = NULL;
r4->l = NULL;
r4->r = NULL;
BiTree fa = BTLevel(root, r2);
if (!fa) {
printf("未找到！\n");
} else {
printf("\n%d\n", fa->data);
}
2021年真题
第一题
问题描述：孩子兄弟链表中指定节点p，要求得到其孩子、兄弟以及双亲节点。
代码：
#include<stdio.h>
#include<malloc.h>
#define maxsize 50
typedef struct BTNode{
int data;
struct BTNode* l;//现在l是孩子
struct BTNode* r;//现在r是兄弟
}BTNode,*BiTree;
BiTree findFather(BiTree T,BiTree target){
//层次遍历求target的父亲
if(!T||T==target){return NULL;}//如果target是根节点、或者树为空
BiTree Q[maxsize],p,father=NULL;//father用于标记
int front=-1,rear=-1;
Q[++rear]=T;//根节点入队，开始处理
while(front<rear)
{ p=Q[++front];//出队、访问
father=p; //暂存一下可能的father
if(p->l!=NULL){//第一个孩子入队
p=p->l;Q[++rear]=p;
if(p==target){return father;}
while(p->r!=NULL)
{ //其他孩子也入队
p=p->r;Q[++rear]=p;
if(p==target){return father;}
}
}
}
return NULL;
}
void findBro(BiTree father,BiTree target){
//输出所有兄弟
printf("\ntarget的所有兄弟：");
for(BiTree p=father->l;p!=NULL;p=p->r){
if(p!=target){
printf("%d ",p->data);
}
}
}
void findSon(BiTree target){
//输出所有孩子
printf("\ntarget的所有孩子：");
for(BiTree p=target->l;p!=NULL;p=p->r){
printf("%d ",p->data);
}
}
void findF_B_S(BiTree root,BiTree target){
if(root==NULL)return;
if(root==target){
printf("未找到父结点和兄弟节点\n");
findSon(target);
return;
}
BiTree f=findFather(root,target);
if(!f){printf("未找到父结点、兄弟节点和孩子节点\n"); return;}
printf("\n%d\n",f->data);
findBro(f,target);
findSon(target);
}
int main()
{
BiTree root=(BiTree)malloc(sizeof(BTNode));
BiTree r1= (BiTree)malloc(sizeof(BTNode));
BiTree r2= (BiTree)malloc(sizeof(BTNode));
BiTree r3= (BiTree)malloc(sizeof(BTNode));
BiTree r4= (BiTree)malloc(sizeof(BTNode));
root->data=100;
r1->data=101;
r2->data=102;
r3->data=103;
r4->data=104;
root->l=r1;
root->r=NULL;
r1->l=r3;
r1->r=r2;
r2->l=r4;
r2->r=NULL;
r3->l=NULL;
r3->r=NULL;
r4->l=NULL;
r4->r=NULL;
findF_B_S(root,r2);
}
第四题
问题描述：a链表递增，b链表递减，合并链表，要求相同节点保留一个，合并之后链表递增。
代码：
//2021数据结构第四题
// a链表递增 b链表递减 合并他们 相同节点保留一个 合并之后链表递增
// 思路：这一题和19年第四题类似，可以采取先将a链表原地逆置，后再将两个递减的链表归并的做法
// 可以算出时间复杂度为O(m+n)
#include<stdio.h>
#include<malloc.h>
typedef struct LNode{
int data;
LNode *next;
} *LinkList,LNode;
LinkList Reverse(LinkList A){
//本方法对链表A进行原地倒转
LinkList p=A->next;
A->next=NULL;
while(p!=NULL){
LinkList q=p->next;
p->next=A->next;
A->next=p;
p=q;
}
}
void Merge(LinkList A,LinkList B){
//本方法将AB两个递减有序的链表合并为递增有序；结果保存在A中
LinkList p=A->next,q=B->next,s=NULL;//从AB两链表的首个元素开始遍历
A->next=NULL;
while(p&&q){
if(p->data==q->data)
{
//把p头插法插入A链表
s=p->next;
p->next=A->next;
A->next=p;
p=s;
//删除q（因为重复）
s=q;
q=q->next;
free(s);
}
else{
if(p->data>q->data){s=p;p=p->next;}
else{s=q;q=q->next;}
s->next=A->next;
A->next=s;
}
}
//尾处理：考虑一个链表遍历完之后，剩余另一个链表未遍历
while(p){
s=p;p=p->next;
s->next=A->next;
A->next=s;
}
while(q){
s=q;q=q->next;
s->next=A->next;
A->next=s;
}
}
void fun(LinkList A,LinkList B){
Reverse(A);
Merge(A,B);
}
int main()
{
LinkList a1= (LinkList) malloc(sizeof(LNode) );
LinkList b1= (LinkList) malloc(sizeof(LNode) );
LinkList c1= (LinkList) malloc(sizeof(LNode) );
LinkList d1= (LinkList) malloc(sizeof(LNode) );
LinkList A= (LinkList) malloc(sizeof(LNode) );
a1->data=1;//递减有序
b1->data=2;
c1->data=3;
d1->data=4;
A->next=a1;
a1->next=b1;
b1->next=c1;
c1->next=d1;
d1->next=NULL;
LinkList a2= (LinkList) malloc(sizeof(LNode) );
LinkList b2= (LinkList) malloc(sizeof(LNode) );
LinkList c2= (LinkList) malloc(sizeof(LNode) );
LinkList d2= (LinkList) malloc(sizeof(LNode) );
LinkList B= (LinkList) malloc(sizeof(LNode) );
a2->data=9;//递减有序
b2->data=5;
c2->data=3;
d2->data=1;
B->next=a2;
a2->next=b2;
b2->next=c2;
c2->next=d2;
d2->next=NULL;
for(LinkList p=A->next;p!=NULL;p=p->next)
{
printf("%d\t",p->data);
}printf("\n");
for(LinkList p=B->next;p!=NULL;p=p->next)
{
printf("%d\t",p->data);
}printf("\n");
fun(A,B);
for(LinkList p=A->next;p!=NULL;p=p->next)
{
printf("%d\t",p->data);
}printf("\n");
}
第五题
问题描述：小顶堆编程，把a[i]的数值改为val，并重新调整成为小顶堆，要求算法的时间复杂度为log2n。
代码：
#include<stdio.h>
#include<malloc.h>
void swap(int* arr, int i, int j) {
int temp=arr[i];arr[i]=arr[j];arr[j]=temp;
}
void heapify(int* arr, int i,int len) {//小顶化
int left=i*2+1,right=i*2+2;//左右孩子
int minIndex=i;//找出最小的孩子
if (left<len && arr[left]<arr[minIndex]){
minIndex=left;//如果左孩子最小
}
if (right<len && arr[right]<arr[minIndex]){
minIndex=right;//如果右孩子最小
}
if (minIndex != i){//父亲节点比孩子大->不满足小顶堆->调整
//交换之后，父节点变成最小的了
swap(arr,minIndex,i);
//但是被交换的孩子此刻不一定符合小顶堆
heapify(arr,minIndex,len);//递归地heapify
//形象地理解为让大值继续往下沉淀直到沉不下去
}
}
void buildMaxHeap(int* arr,int len) {//建堆
for (int i=(len-2)/2;i>=0;i--){
//从最后一个非叶节点一直调整到根节点为止
heapify(arr,i,len);
}
}
void heapSort(int* arr,int len){
buildMaxHeap(arr,len);//建堆
for (int i=len-1;i>0;i--){
//输出对顶元素，把堆顶最小值放到堆末，堆顶变成一个较大值
swap(arr,0,i);
len--;
//调整堆：从新的对顶元素开始调整
heapify(arr,0,len);
}
}
void adjust(int* arr,int len,int index,int val){
//先讲arr[index]修改为val
arr[index]=val;
//再重新调整为小顶堆
for(int i=index;i>=0;i=(i-1)/2){
heapify(arr,i,len);
//如果父节点更小，则停止对父节点的调整
if(i==0||arr[i]>arr[(i-1)/2])break;
}
}
int main(){
int arr[]={1,3,5,7,9,2,4,6,8,10};
for(int i=0;i<10;i++){printf("%d ",arr[i]);}printf("\n");
buildMaxHeap(arr,10);//建堆
for(int i=0;i<10;i++){printf("%d ",arr[i]);}printf("\n");
adjust(arr,10,4,2);
for(int i=0;i<10;i++){printf("%d ",arr[i]);}printf("\n");
}
