5 Câu Hỏi Ôn Tập Thi GIữa kỳ CTDL

Code:

#include<iostream.h>

typedef struct NODE *LIST;
struct NODE
{
  int k;
  LIST next;
};

LIST L;

typedef struct CELL *TREE;
struct CELL
{
  int key;
  TREE p, left, right;
};

TREE T;

void Listinit( LIST &L)
{
  L=NULL;
}

void ListInsert( LIST &L, int x)
{
  NODE *q;
  q = new(NODE);
  q->k=x;
  q->next=L;
  L=q;
}

void InputList(LIST &L, int n)
{
  int x,i;
  for(i=1;i<=n; i++)
  {
      cout<<"Nhap DS"<<i<<":";
      cin>>x;
      ListInsert(L,x);
  }
}

void OutputList(LIST L)
{
  if(L!=NULL)
  {
      cout<<L->k<<"\t";
      OutputList(L->next);
  }
}

void TreeInit(TREE &T)
{
  T=NULL;
}

void TreeInsert(TREE &T, TREE z)
{
  TREE x,y;
  y=NULL;
  x=T;
  while(x!=NULL)
  {
      y=x;
      if(z->key<x->key)
        x=x->left;
      else x=x->right;
  }
              z->p=y;
  if(y==NULL)
      T=z;
  else if(z->key<y->key)
      y->left=z;
  else y-> right=z;
}

void TREEINSERT(TREE &T, int k)
{
  TREE z;
  z=new(CELL);
  z->key=k;
  z->left=z->right=NULL;
  TreeInsert(T,z);
}

void InorderTreeWalk(TREE x)
{
  if(x!=NULL)
  {
      InorderTreeWalk(x->left);
      cout<<x->key<<"";
      InorderTreeWalk(x->right);
  }
}

void PostorderTreeWalk( TREE x)
{
  if(x!=NULL)
  {
      cout<<x->key<<"";
      PostorderTreeWalk(x->left);
      PostorderTreeWalk(x->right);
  }
}

void ListtoTree(LIST L, TREE &T)
{
  if(L!=NULL)
  {
      TREEINSERT(T,L->k);
      ListtoTree(L->next,T);
  }
}

void main()
{
 
  int n;
  TREE t;
  LIST l;
  Listinit(l);
  TreeInit(t);
  cout<<"Nhap so phan tu cua DSLK: ";
  cin>>n;
  InputList(l,n);
  cout<<"\n";
  OutputList(l);
  ListtoTree(l,t);
  cout<<"\n";
  InorderTreeWalk(t);
  cout<<"\n";
}

Code:

#include<iostream.h>

typedef struct NODE *LIST;
struct NODE
{
  int k;
  LIST next;
};

LIST L;

typedef struct CELL *TREE;
struct CELL
{
  int key;
  TREE p, left, right;
};

TREE T;

void Listinit( LIST &L)
{
  L=NULL;
}

void ListInsert( LIST &L, int x)
{
  NODE *q;
  q = new(NODE);
  q->k=x;
  q->next=L;
  L=q;
}

void InputList(LIST &L, int n)
{
  int x,i;
  for(i=1;i<=n; i++)
  {
      cout<<"Nhap DS"<<i<<":";
      cin>>x;
      ListInsert(L,x);
  }
}

void OutputList(LIST L)
{
  if(L!=NULL)
  {
      cout<<L->k<<"\t";
      OutputList(L->next);
  }
}

void TreeInit(TREE &T)
{
  T=NULL;
}

void TreeInsert(TREE &T, TREE z)
{
  TREE x,y;
  y=NULL;
  x=T;
  while(x!=NULL)
  {
      y=x;
      if(z->key<x->key)
        x=x->left;
      else x=x->right;
  }
              z->p=y;
  if(y==NULL)
      T=z;
  else if(z->key<y->key)
      y->left=z;
  else y-> right=z;
}

void TREEINSERT(TREE &T, int k)
{
  TREE z;
  z=new(CELL);
  z->key=k;
  z->left=z->right=NULL;
  TreeInsert(T,z);
}

void InorderTreeWalk(TREE x)
{
  if(x!=NULL)
  {
      InorderTreeWalk(x->right);
      cout<<x->key<<"";
      InorderTreeWalk(x->left);
  }
}

void PostorderTreeWalk( TREE x)
{
  if(x!=NULL)
  {
      cout<<x->key<<"";
      PostorderTreeWalk(x->right);
      PostorderTreeWalk(x->left);
  }
}

void ListtoTree(LIST L, TREE &T)
{
  if(L!=NULL)
  {
      TREEINSERT(T,L->k);
      ListtoTree(L->next,T);
  }
}

void main()
{
 
  int n;
  TREE t;
  LIST l;
  Listinit(l);
  TreeInit(t);
  cout<<"Nhap so phan tu cua DSLK: ";
  cin>>n;
  InputList(l,n);
  cout<<"\n";
  OutputList(l);
  ListtoTree(l,t);
  cout<<"\n";
  InorderTreeWalk(t);
  cout<<"\n";
}

Code:

#include<iostream.h>
#include<fstream.h>
#include<conio.h>
#define MAX 100
//----khai bao do thi//
struct GRAPH
{
   int sodinh;
   int a[MAX][MAX];
};

GRAPH G;

void nhap(GRAPH &G)
{
   cout<<"nhap so dinh";
   cin>>G.sodinh;
   for(int i=1; i<=G.sodinh; i++)
   {
      for(int j =i+1; j<=G.sodinh; j++)
      {
         cout<<"a["<<i<<","<<j<<"]=";
         cin>>G.a[i][j];
         G.a[j][i]=G.a[i][j];
      }
      G.a[i][i]=0;
   }
}

void xuat(GRAPH G)
{
   for(int i=1;i<=G.sodinh;i++)
   {
      for(int j=1;j<=G.sodinh;j++)
         cout<<" "<<G.a[i][j];
      cout<<"\n";
   }
}

int tinhbac (GRAPH G, int u)
{
   int bac =0;
   for(int j=1;j<=G.sodinh;j++)
      bac=bac+G.a[u][j];
   return bac;
}

int maxbac ( GRAPH G)
{
   int max=0;
   for( int u=1; u<=G.sodinh; u++) {
      //timh bac u
      int bac = tinhbac(G, u);
      if( bac > max)
         max = bac;
   }
   return max;

}

int minbac (GRAPH G)
{
   int min =G.sodinh;
   for( int u=1; u<=G.sodinh; u++)
   {
      int bac = tinhbac(G,u);
      if ( bac < min)
         min = bac;
   }
   return min;
}

void main()
{
   GRAPH G;
   int u,bac,max;
   nhap(G);
   xuat(G);
   cout<<"nhap dinh can tinh bac: ";
   cin>>u;
   bac=tinhbac(G,u);
   cout<<bac<<"\n";
   int m1= minbac(G);
   int m = maxbac(G);
   cout<<"bac lon nhat:"<<m<<"\n";
   cout<<"bac nho nhat:"<<m1<<"\n";
   
}

Code:

#include<iostream.h>
#include<conio.h>
#define MAX 30
typedef int GRAHP[MAX][MAX];
GRAHP G;
int n;
void init(GRAHP &g)
 {
   int i,j;
   cout<<"Given number of vertexs of the graph:"; cin>>n;
   cout<<"Enter data of adjacent matrix:\n";
   for(i=1;i<=n;i++)
      {
          for(j=i+1;j<=n;j++)
            {
                  cout<<"a["<<i<<","<<j<<"]="; cin>>g[i][j]; g[j][i]=g[i][j];
            }
    g[i][i]=0; cout<<"\n";
  }
 }

int Degree(GRAHP &g, int u)
 {
    int d=0;
    for(int i=1; i<=n; i++)
       d=d+g[u][i];
   
    return d;
   
 }

int DinhBacChan(GRAHP &g)
{
  int tong=0;
   for(int i=1; i<=n; i++)
      if(Degree(g,i)%2==0)
         tong=tong+Degree(g,i);
      return tong;
         
}
int DinhBacLe(GRAHP &g)
{
  int le=0;
   for(int i=1; i<=n; i++)
      if(Degree(g,i)%2!=0)
         le=le+Degree(g,i);
      return le;
         
}

void main()
{
   init(G);
   cout <<"Tong dinh Chan : "<<   DinhBacChan(G)"\n";
   cout <<"Tong dinh Le : "<<   DinhBacLe(G)"\n";
   
}


Code:

// Input must be a connected undirect graph
 #include<iostream.h>
 #define MAX 30
 #define MAXINT 32560
 #define NIL -1
typedef int GRAPH[MAX][MAX];
typedef struct NODE *LIST;
    struct NODE{
              int v;
              LIST next;
        };
 typedef LIST VSET;
 GRAPH G;
 VSET V;
 int key[MAX], MST[MAX];
 int n, w=0, W=0;
 void VSET_init(VSET &S)
 {
  S=NULL;
 }
 void Insert_VSET(int x, VSET &S)
 {
  VSET q;
  q=new(NODE);
  q->v=x;
  q->next=S;
  S=q;
 }
void Delete(int x,VSET &l)
{
  VSET p;
  if(l!=NULL)
    if(x==(l->v)){ p=l;l=l->next; delete p;}
    else Delete(x,l->next);
}

 void init(GRAPH &c)
 {
  int i,j;
  cout<<"Given number of vertices of graph:"; cin>>n;
  cout<<"Input weight matrix for graph:\n";
  for(i=1;i<=n;i++)
  {
      for(j=i+1;j<=n;j++)
      {
        cout<<"c["<<i<<","<<j<<"]="; cin>>c[i][j]; W = W + c[i][j]; c[j][i]=c[i][j];
      }
  }
  for(i=1;i<=n;i++)
      for(j=1;j<=n;j++) if(c[i][j]==0) c[i][j]=MAXINT;
  VSET_init(V);
  for(i=1;i<=n;i++) Insert_VSET(i,V);
 }

 void print_data(GRAPH c)
{
  int  i,j;
  cout<<"weight matrix\n";
  for(i=1;i<=n;i++)
  {
  for(j=1;j<=n;j++) if (c[i][j]==MAXINT) cout<<char(236)<<"  "; else cout<<c[i][j]<<" ";
  cout<<"\n";
  }
}
 
void result(int MST[MAX])
{
  int u;
  cout<<"Minimal spanning tree:\n";
  cout<<"{";
  for(u=1;u<=n; u++) if(MST[u]!=NIL)
  {
    cout<<"("<<u<<"."<<MST[u]<<"), ";
  }
 cout<<endl;
}

int Extract_Min(VSET &Q)
{
  int min, u, k;
  Q=V; min=MAXINT;
  while(Q!=NULL)
  {
      k=Q->v;
      if(key[k]<min){min=key[k]; u=k;}
      Q=Q->next;
  }
  return u;
}

float Prim(GRAPH G)
{
 int u, s=1;
 VSET Q;
 key[s]=0; MST[s]=NIL;
 Delete(s,V);
 Q=V;
 while(Q!=NULL)
 {
  key[Q->v]=G[s][Q->v]; MST[Q->v]=s;
  Q=Q->next;
 }
 while(V!=NULL)
 {
  u= Extract_Min(Q); w=w+key[u];
  Delete(u,V);
  Q=V;
  while(Q!=NULL)
  {
          if(key[Q->v]>G[u][Q->v])
          {
            key[Q->v]=G[u][Q->v];
            MST[Q->v]=u;
          }
          Q=Q->next;
  }
  }
return float((w*100)/W);
 }

void main()
{
 init(G);
 print_data(G);
 cout<<Prim(G)<<"\n";
}

Code:

// Input must be a connected undirect graph
 #include<iostream.h>
 #define MAX 30
 #define MAXINT 32560
 #define NIL -1
typedef int GRAPH[MAX][MAX];
typedef struct NODE *LIST;
    struct NODE{
              int v;
              LIST next;
        };
 typedef LIST VSET;
 GRAPH G;
 VSET V;
 int key[MAX], MST[MAX];
 int n, w=0, W=0;
 void VSET_init(VSET &S)
 {
  S=NULL;
 }
 void Insert_VSET(int x, VSET &S)
 {
  VSET q;
  q=new(NODE);
  q->v=x;
  q->next=S;
  S=q;
 }
void Delete(int x,VSET &l)
{
  VSET p;
  if(l!=NULL)
    if(x==(l->v)){ p=l;l=l->next; delete p;}
    else Delete(x,l->next);
}

 void init(GRAPH &c)
 {
  int i,j;
  cout<<"Given number of vertices of graph:"; cin>>n;
  cout<<"Input weight matrix for graph:\n";
  for(i=1;i<=n;i++)
  {
      for(j=i+1;j<=n;j++)
      {
        cout<<"c["<<i<<","<<j<<"]="; cin>>c[i][j]; W = W + c[i][j]; c[j][i]=c[i][j];
      }
  }
  for(i=1;i<=n;i++)
      for(j=1;j<=n;j++) if(c[i][j]==0) c[i][j]=MAXINT;
  VSET_init(V);
  for(i=1;i<=n;i++) Insert_VSET(i,V);
 }

 void print_data(GRAPH c)
{
  int  i,j;
  cout<<"weight matrix\n";
  for(i=1;i<=n;i++)
  {
  for(j=1;j<=n;j++) if (c[i][j]==MAXINT) cout<<char(236)<<"  "; else cout<<c[i][j]<<" ";
  cout<<"\n";
  }
}
 
void result(int MST[MAX])
{
  int u;
  cout<<"Minimal spanning tree:\n";
  cout<<"{";
  for(u=1;u<=n; u++) if(MST[u]!=NIL)
  {
    cout<<"("<<u<<"."<<MST[u]<<"), ";
  }
 cout<<endl;
}

int Extract_Min(VSET &Q)
{
  int min, u, k;
  Q=V; min=MAXINT;
  while(Q!=NULL)
  {
      k=Q->v;
      if(key[k]<min){min=key[k]; u=k;}
      Q=Q->next;
  }
  return u;
}

int Prim(GRAPH G)
{
 int u, s=1;
 VSET Q;
 key[s]=0; MST[s]=NIL;
 Delete(s,V);
 Q=V;
 while(Q!=NULL)
 {
  key[Q->v]=G[s][Q->v]; MST[Q->v]=s;
  Q=Q->next;
 }
 while(V!=NULL)
 {
  u= Extract_Min(Q); w=w+key[u];
  Delete(u,V);
  Q=V;
  while(Q!=NULL)
  {
          if(key[Q->v]>G[u][Q->v])
          {
            key[Q->v]=G[u][Q->v];
            MST[Q->v]=u;
          }
          Q=Q->next;
  }
  }
return int(W-w);
 }

void main()
{
 init(G);
 print_data(G);
 cout<<Prim(G)<<"\n";
}

Admin đã viết:Cám ơn Khoa nhiều nhiều nha.

Hi vọng các bạn lớp hc11th3a và các bạn học lại đều pass môn này và pass với điểm cao.

Chúc các bạn thi tốt.
Hôm nào gặp cho mình xin chữ ký đi bạn Khoa, hii. Bạn thật giỏi.
Mình biết lớp mình còn có nhiều bạn giỏi lắm nhưng chưa xuất hiện thôi.
Các bạn cùng nhau trao đổi, chia sẻ bí quyết học tập nhé.