师大数据结构历年真题-创新互联
//2014数据结构865
//1.单链表结点的删除
LNode Delete(LinkList &L,int K){LNode p=L->next;
LNode pre=L;
while(p!=NULL){if(p->data>K){ pre->next=p->next;
Delete(p);
return p;
}
pre=p;
p=p->next;
}
return -1;
}
//2.求邻接表存储有向图顶点的出度
typedef struct ArcNode{int adjvex;
struct ArcNode *nextarc;
}ArcNode;
typedef struct{VertexType data;
struct ArcNode *firstArc;
}VNode;
typedef struct{VNode adjlist[MAX_NUM];
int v,e;
}ALGraph;
void OutDu(ALGraph G,int h){int n=0;
ArcNode *e;
while(G.adjlist[h].firstArc!=0)
n++;
e=G.adjlist[h].firstArc->nextarc;
G.adjlist[h].firstArc=e;
}
print("%d",n);
}
//3.快速排序
void QuickSort(ElemType A[],int low,int high){if(lowint pivotpos=Partition(A,low,high);
QuickSort(A,low,pivotpos-1);
QuickSort(A,pivotpos+1,high);
}
}
int Partition(ElemType A[],int low,int high){int pivot=A[low];
while(lowwhile(low=pivot) j--;
A[low]=A[high];
while(lowif(T!=NULL){visit(T);
L_Order(T->lchild);
R_Order(T->rchild);
}
}
void L_Order(BiTree T){if(T!=NULL){L_Order(T->lchild);
visit(T);
L_Order(T->rchild);
}
}
void R_Order(BiTree T){if(T!=NULL){R_Order(T->rchild);
visit(T);
R_Order(T->lchild);
}
}
//2015数据结构865
//1.单链表结点的删除
void Delete(LinkList &L,int k){LNode p=L->next;
LNode pre=L;
while(p!=NULL){if(p->data pre->next=p->next;
free(p);
p=pre->next;
}
pre=p;
p=p->next;
}
}
//2.求有向图顶点的入度和出度
typedef struct ArcNode{int adjvex;
ArcNode *nextarc;
}ArcNode;
typedef struct{VertexType data;
ArcNode *firstarc;
}VNode;
typedef struct{VNode adjlist[MAX_NUM];
int v,e;
}ALGraph;
void OutDu(ALGraph G){int n=0,i=0;
ArcNode *e;
for(i=0;iwhile(G.adjlist[i].firstarc!=NULL){ n++;
e=G.adjlist[i].firstarc->nextarc;
G.adjlist[i].firstarc=e;
}
printf("%d",n);
n=0;
}
}
void InDu(ALGraph G){int i,j,n=0;
int A[G.v];
ArcNode *e;
for(i=0;iA[i]=0;
}
for(j=0;jwhile(G.adjlist[j].firstarc!=NULL){ A[G.adjlist[j].firstarc->adjvex]++;
e=G.adjlist[j].firstarc->nextarc;
G.adjlist[j].firstarc=e;
}
}
for(i=0;iprintf("%d",A[i]);
}
}
//3.快速排序-略
//4.将二叉树叶子结点形成一个单链表
typedef struct BiTree{char data;
struct BiTree *lchild;
struct BiTree *rchild;
};
struct BiTree *pre=NULL;
struct BiTree *h=(struct BiTree *)malloc(sizeof(struct BiTree));
BiTree *LeafLink(BiTree *b){if(b){LeafLink(b->lchild);
if(!b->lchild && !b->rchild){//链表加入条件
if(pre==NULL){//处理第一个结点
h=b;
pre=b;
}else{//使用尾插法不断插入叶子节点，使用pre指针指向最后一个结点
pre->rchild=b;
pre=b;
}
}
LeafLink(b->rchild);
pre->rchild=NULL;
}
return h;
}
//2016数据结构865
//1.单向链表结点的删除 略
//2.求二叉树树高
int Tree_Height(BiTree *T){int h=0,h1=0,hr=0;
if(T==NULL){return 0;
}else{h1=Tree_Height(T->lchild);
hr=Tree_Height(T->rchild);
h=((h1>hr)?h1:hr)+1;
return h;
}
}
//3.有向图邻接表表示增加一条边
typedef struct VNode{int data;
struct VNode *next;
}VNode, *NodeList;
typedef struct{NodeList V[MAX_NUM];
int vexnum,arcnum;
}ALGraph;
void InsertArc(ALGraph G){int c1,c2;
cin>>c1>>c2;
NodeList p1=new VNode;
p1->data=c2;
p1->next=G.V[c1]->next;
G.V[c1]->next=p1;
}
//4.求一维数组递归
int Sum(int A[],int len){if(len==1){return A[len-1];
}else{return A[len-1]+Sum(A,len-1);
}
}
//2017数据结构865
//1.递归计算平均值
int Average(int A[],int i){if(i==0) return A[0];
else return (Average(A[i-1],i-1)*(i-1)+A[i-1])/i;
}
//2.判断括号匹配函数
void ExpIsCorrect(char exp[],int n){SeqStack mystack;
int i;
char c;
StackInitiate(&mystack);
for(i=0; iif(exp[i] == "(") StackPush(&mystack, exp[i]);
else if(exp[i] == ")" && StackNotEmpty(mystack)){ StackTop(mystack,&c);
if(c == "("){ StackPop(&mystack,&c);
}else{ printf("左右括号不匹配\n");
return;
}
}
else if(exp[i] == ")" && !StackNotEmpty(mystack)){ printf("右括号多于左括号\n");
return;
}
}
if(StackNotEmpty(mystack)){printf("左括号多于右括号\n");
}else{printf("括号完全匹配\n");
}
}
//3.邻接表存储图的顶点出度统计
void InDegree(AdjGraph G){Node *p;
int i,inD;
for(i=0;iinD=0;
p=G.adj[i].first;
while(p){ inD++;
p=p->next;
}
printf("顶点%d的出度为%d\n",i,inD);
}
}
//4.二叉树的层序遍历
void LevelOrder(BiTree T){InitQueue(Q);
BiTree p;
EnQueue(Q,T);
while(!IsEmpty(Q)){DeQueue(Q,p);
visit(p);
if(p->lchild!=NULL)
EnQueue(Q,p->lchild);
if(p->rchild!=NULL)
EnQueue(Q,p->rchild);
}
}
//2018数据结构865
//1.折半查找
int Binary_Search(SeqList L,ElemType key){int low=0,high=L.len-1,mid;
while(lowmid = (low+high)/2;
if(L.Elem[mid]==key){ return mid;
else if(L.Elem[mid] low=mid+1;
}else{ high=mid-1;
}
}
return -1;
}
//2.苹果问题 略
//3.求树高
int Height(BiTree T){if(T==NULL) return 0;
int lh=Height(T->lchild);
int rh=Height(T->rchild);
if(lhreturn rh+1;
}else{return lh+1;
}
}
//4.二叉树层序遍历 略
//2019数据结构865
//1.二叉树先序遍历 略
//2.希尔排序
void ShellSort(ElemType A[],int n){for(int dk=n/2;dk>=1;dk=dk/2){for(int i=dk+1;i<=n;i++){ if(A[i] A[0]=A[i];
for(int j=i-dk;j>0 && A[0]A[j+dk]=A[j];
}
A[j+dk]=A[0];
}
}
}
}
//3.邻接表建图
int MaxNum=2010;
int n=0;
vectoradj[MaxNum];
void CreatMap(){scanf("%d",&n);
for(int i=1;i<=n;i++){int m=0;
scanf("%d",&m);
for(int j=1;j<=m;j++){ int next;
scanf("%d",&next);
adj[next].push_back(i);
}
}
}
//4.十字链表的输出
//十字链表存储表示
typedef struct OLNode{int i,j;//该非零元的行标和列标
ElemType e;//非零元元素值
OLNode *right,*down;//该非零元所在行表和列表
}OLNode, *OLink;
typedef struct{OLNode *rhead,*chead;//行表和列表头指针
int mu,nu,tu;//稀疏矩阵的行数、列数和非零元数
}CrossList;
void OutCSM(CrossList M,void(*Out3)(int,int,int)){int i;
OLink p;
for(i=1;i<=M.mu;i++){p=M.rhead[i];//p指向每一行的基址
while(p){ Out3(p->i,p->j,p->e);
p=p->right;
}
}
}
//2020数据结构865
//1.非递归实现二叉树中序遍历
void InOrder2(BiTree T){InitStack(S);
BiTree p=T;
while(p||!IsEmpty(S)){if(p){ Push(S,p);
p=p->lchild;
}else{ Pop(S,p);
visit(p);
p=p->rchild;
}
}
}
//2.拓扑排序
vectorG[MAXV];
int n,InDegree[MAXV];
bool ToPo_Logical_Sort(){int num=0;
queueq;
for(int i=0;iif(InDegree[i]==0){ q.push(i);
}
}
while(!q.empty()){int u=q.front();
q.pop();
for(int j=0;j int v=G[u][j];
InDegree[v]--;
if(InDegree[v]==0)
q.push(v);
}
G[u].clear();
num++;
}
if(num==n) return true;
else return false;
}
//3.改进的快速排序算法 略
//2021数据结构865
//1.递归实现折半查找
int Binary_Search(SeqList L,ElemType key,int low,int high){if(lowmid=(low+high)/2;
if(L.elem[mid]==key)
return mid;
else if(L.elem[mid]for(int v=0;vvisit(v);
visited[v]=true;
for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){if(!visited[w])
DFS(G,w);
}
}
//3.二叉排序树进行排序
void Creat_BST(BiTree &T,KeyType str[],int i){T=NULL;
int i=0;
while(iBST_Insert(T,str[i]);
i++;
}
}
int BST_Insert(BiTree &T,KeyType k){if(T==NULL){T=(BiTree)malloc(sizeof(BSTNode));
T->data=k
T->lchild=T->rchild=NULL;
return 1;
}
else if(k==T->data)
return 0;
else if(kdata)
return BST_Insert(T->lchild,k);
else
return BST_Insert(T->rchild,k);
}
//2021数据结构885
//1.BFS算法
bool visited[MAX_NUM];
void BFSTraverse(Graph G){for(int i=0;ivisit(v);
visited[v]=true;
EnQueue(Q,v);
while(!IsEmpty(Q)){DeQueue(Q,v);
for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){ if(!visited[w]){ visit(w);
visited[w]=true;
EnQueue(Q,w);
}
}
}
}
//2.BFS求单源最短路径问题
void BFS_MIN_Distance(Graph G,int u){for(int i=0;id[i]=9999;
}
visited[u]=true;
d[u]=0;
EnQueue(Q,u);
while(!IsEmpty(Q)){DeQueue(Q,u);
for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){ if(!visited[w]){ visited[w]=true;
d[w]=d[u]+1;
EnQueue(Q,w);
}
}
}
} 你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
标题名称：师大数据结构历年真题-创新互联
网站地址：http://scyanting.com/article/pgepg.html
