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

by trannguyenkhoa26 (113A) Tue Sep 11, 2012 10:59 pm

1/ Dùng CTDL cây để
- sắp 1 mảng theo thứ tự giảm
- sắp 1 mảng theo thứ tự tăng
- sắp 1 DSLK theo thứ tự giảm
- sắp 1 DSLK theo thứ tự tăng

2/ Viết CT tính bậc của 1 đỉnh DT vô hướng

3/ Viết CT tính bán bậc ra ( vào) của 1 đỉnh của DT có hướng

4/ Viết CT tính bậc của đỉnh là bậc lớn nhất của DT vô hướng

5/ Viết CT tính bậc của đỉnh là bậc nhỏ nhất của DT vô hướng

6/ Viết CT tính bậc của đỉnh có bậc lẻ lớn nhất

7/ Viết CT tính bậc cúa đỉnh có bậc chẵn lớn nhất

8/ Viết CT tính tổng các bậc của các đỉnh của DT vô hướng

9/ Viết CT tính tổng bậc của các đỉnh có bậc lẻ của DT vô hướng

10/ Viết CT tính tổng bậc của các đỉnh có bậc chẳn của DT vô hướng

11/ Tính số thành phần liên thông của DT vô hướng

12/ Viết CT kiểm tra DT có liên thông hay không?

13/ Viết CT tính trọng số của cây bao trùm nhỏ nhất

14/ Viết CT tính tỷ số % của trọng số cây bao trùm nhỏ nhất với trọng số DT

by trannguyenkhoa26 (113A) Tue Sep 11, 2012 11:05 pm

Code:: #include<stdlib.h> #include<conio.h> #include<iostream.h> #define MAX 100 typedef struct CELL *TREE; struct CELL { int key; TREE p,left,right; }; TREE T; typedef int VECTOR[MAX]; VECTOR a; void init(TREE &T) { T=NULL; } void TREE_INSERT(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 INORDER_TREE_WALK(TREE x) { if(x!=NULL) { INORDER_TREE_WALK(x->left); cout<<(x->key)<<' '; INORDER_TREE_WALK(x->right); } } void INORDER_TREE_SORT(TREE x, VECTOR &a, int &l, int &u)// doan sap xep { if((x!=NULL)&&(l<=u)) { INORDER_TREE_SORT(x->left,a,l, u); a[l]=x->key; l=l+1; INORDER_TREE_SORT(x->right,a,l, u); } } void SORT(VECTOR &a, int l, int u) { TREE T, x; int i; init(T); for(i=l; i<=u; i++){ x=new(CELL); x->key=a[i]; //Chuyen cac phan tu trong mang vao cay x->left=x->right=NULL; TREE_INSERT(T,x); } INORDER_TREE_SORT(T,a,l,u); //Chuyen cac phan tu trong cay vao mang (mang duoc sap) } void inputarray(VECTOR &a, int l, int u) { for(int i=l; i<=u; i++) { cout<<"a["<<i<<"]="; cin>>a[i]; } } void outputarray(VECTOR &a, int l, int u) { for(int i=l; i<=u; i++) cout<<a[i]<<" "; } void main() { int n; cout<<"Given n: "; cin>>n; init(T); inputarray(a, 1, n); SORT(a, 1, n); outputarray(a, 1,n); }

by trannguyenkhoa26 (113A) Tue Sep 11, 2012 11:09 pm

Code:: #include<iostream.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; } void main() { GRAPH G; int u,bac; nhap(G); xuat(G); cout<<"nhap dinh can tinh bac: "; cin>>u; bac=tinhbac(G,u); cout<<bac<<"\n"; }

by trannguyenkhoa26 (113A) Tue Sep 11, 2012 11:11 pm

Code:: #include <iostream.h> #include <conio.h> #define MAX 100 #define indef 32665 struct GRAPH { int sodinh; int a[MAX][MAX]; }; GRAPH g; void nhap(GRAPH &g) { cout<<"nhap so dinh do thi co huong:"; cin>>g.sodinh; cout<<"1:bac vao; 0: khong co duong di \n"; for (int i=1;i<=g.sodinh;i++) for (int j=1;j<=g.sodinh;j++) { cout<<"a["<<i<<","<<j<<"]="; cin>>g.a[i][j]; } } 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 tinhbacra (GRAPH g, int u) { int bacra=0; for(int i=1;i<=g.sodinh;i++) if(g.a[u][i]==1) bacra++; return bacra; } int tinhbacvao (GRAPH g, int u) { int bacvao=0; for(int j=1;j<=g.sodinh;j++) if(g.a[j][u]==1) bacvao++; return bacvao; } void main() { int bacvao,bacra,u; GRAPH g; nhap(g); xuat(g); cout<<"nhap dinh can tinh bac:"; cin>>u; bacvao=tinhbacvao(g,u); cout<<"bac vao :"<<bacvao<<"\n"; bacra=tinhbacra(g,u); cout<<"bac ra :"<<bacra<<"\n"; //cout<<bac<<"\n"; }

by trannguyenkhoa26 (113A) Tue Sep 11, 2012 11:16 pm

Code:: #include<iostream.h> // Kiem tra do thi co lien thong khong #include<conio.h> #define MAX 30 typedef int GRAHP[MAX][MAX]; GRAHP G; int unvisited[20], 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"; } for(j=1;j<=n;j++) unvisited[j]=1; } void DFS(int v,GRAHP g) // tim kiem theo chieu sau bat dau tu dinh v { int u; unvisited[v]=0; for(u=1;u<=n;u++) if((g[v][u]==1)&&(unvisited[u]==1)) DFS(u,g); } int Conect_Comp(GRAHP G) // Tim so thanh phan lien thong { int i,numc=0; for(i=1;i<=n;i++) if(unvisited[i]==1) { numc=numc+1; DFS(i,G); } return numc; } void main() { init(G); if(Conect_Comp(G)==1) cout<<"The graph is connected\n"; else cout<<"The graph is not connected"; }

by trannguyenkhoa26 (113A) Tue Sep 11, 2012 11:17 pm

Code:: #include<iostream.h> // tinh thanh phan lien thong #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 v) { int d=0; for(int j=1; j<=n; j++) d=d+g[v][j]; return d; } void main() { int v; init(G); cout<<"Given vertex v="; cin>>v; cout<<"Degree of "<<v<<" is: "<<Degree(G, v)<<"\n"; }

by hongkongk Wed Sep 12, 2012 12:07 am

thanks bạn nhiều.

by **Admin** Wed Sep 12, 2012 9:17 am

Cám ơn bạn hongkongk đã post câu hỏi.

Cám ơn bạn trannguyenkhoa26 (113A) đã trả lời.
Bạn ơi còn bài nào nữa post lên cho mọi người học với nha.

by trannguyenkhoa26 (113A) Wed Sep 12, 2012 8:11 pm

Mọi người cùng giải nào mình ko thể sưu tap hết dc.

by trannguyenkhoa26 (113A) Wed Sep 12, 2012 8:14 pm

Code:: #include<stdlib.h> #include<conio.h> #include<iostream.h> #define MAX 100 typedef struct CELL *TREE; struct CELL { int key; TREE p,left,right; }; TREE T; typedef int VECTOR[MAX]; VECTOR a; void init(TREE &T) { T=NULL; } void TREE_INSERT(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 INORDER_TREE_WALK(TREE x) { if(x!=NULL) { INORDER_TREE_WALK(x->left); cout<<(x->key)<<' '; INORDER_TREE_WALK(x->right); } } void INORDER_TREE_SORT(TREE x, VECTOR &a, int &l, int &u)// doan sap xep { if((x!=NULL)&&(l<=u)) { INORDER_TREE_SORT(x->right,a,l, u); a[l]=x->key; l=l+1; INORDER_TREE_SORT(x->left,a,l, u); } } void SORT(VECTOR &a, int l, int u) { TREE T, x; int i; init(T); for(i=l; i<=u; i++){ x=new(CELL); x->key=a[i]; //Chuyen cac phan tu trong mang vao cay x->left=x->right=NULL; TREE_INSERT(T,x); } INORDER_TREE_SORT(T,a,l,u); //Chuyen cac phan tu trong cay vao mang (mang duoc sap) } void inputarray(VECTOR &a, int l, int u) { for(int i=l; i<=u; i++) { cout<<"a["<<i<<"]="; cin>>a[i]; } } void outputarray(VECTOR &a, int l, int u) { for(int i=l; i<=u; i++) cout<<a[i]<<" "; } void main() { int n; cout<<"Given n: "; cin>>n; init(T); inputarray(a, 1, n); SORT(a, 1, n); outputarray(a, 1,n); }

by hongkongk Wed Sep 12, 2012 11:41 pm

Mong các bạn có thể giải cùng Khoa.khó kiếm điểm lý thuyet lam,nên các bạn phải gán lấy điểm thực hành

by NguyenPhanDaThao(113A) Thu Sep 13, 2012 10:23 pm

rất cảm ơn các bạn đã post bài cho lớp, nếu có nút thanks mình nhấn chục lần rồi. Các bạn vào tham khảo góp ý vài câu cho gọi là cảm ơn các bạn ấy với.

by trannguyenkhoa26 (113A) Thu Sep 13, 2012 11:06 pm

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; 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]; 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, sum=0; 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); sum=sum+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 sum; } void main() { init(G); print_data(G); cout<<Prim(G)<<"\n"; }

by trannguyenkhoa26 (113A) Thu Sep 13, 2012 11:12 pm

Mọi người luu ý. 2 câu này thầy chỉ yêu cầu xuất ra dc bậc lớn nhất và nhỏ nhất thôi. Không cần tính bậc của nó

4/ Viết CT tính bậc của đỉnh là bậc lớn nhất của DT vô hướng

5/ Viết CT tính bậc của đỉnh là bậc nhỏ nhất của DT vô hướng

Còn 2 câu này cũng vậy

6/ Viết CT tính bậc của đỉnh có bậc lẻ lớn nhất

7/ Viết CT tính bậc cúa đỉnh có bậc chẵn lớn nhất

by trannguyenkhoa26 (113A) Thu Sep 13, 2012 11:32 pm

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"; }

by **Admin** Fri Sep 14, 2012 7:58 am

Cám ơn bạn khoa nhiều nhiều nha,
Môn cấu trúc dữ liệu đối với nhiều bạn là rất khó, Bạn nào hiểu bài post lên cho các bạn cùng tham khảo.
Môn thực hành thầy cho các câu hỏi để ôn thi bạn nào giải được post lên cho cả lớp tham khảo.

by trannguyenkhoa26 (113A) Fri Sep 14, 2012 11:34 pm

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"; }

by trannguyenkhoa26 (113A) Fri Sep 14, 2012 11:35 pm

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"; }

by Sponsored content

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

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

Sắp mảng tăng

2/ Viết CT tính bậc của 1 đỉnh DT vô hướng

3/ Viết CT tính bán bậc ra ( vào) của 1 đỉnh của DT có hướng

12/ Viết CT kiểm tra DT có liên thông hay không?

11/ Tính số thành phần liên thông của DT vô hướng

Re: Các Câu Hỏi Ôn Tập Thi GIữa kỳ CTDL

Re: Các Câu Hỏi Ôn Tập Thi GIữa kỳ CTDL

Re: Các Câu Hỏi Ôn Tập Thi GIữa kỳ CTDL

sắp 1 mảng theo thứ tự giảm

Re: Các Câu Hỏi Ôn Tập Thi GIữa kỳ CTDL

Re: Các Câu Hỏi Ôn Tập Thi GIữa kỳ CTDL

13/ Viết CT tính trọng số của cây bao trùm nhỏ nhất

Re: Các Câu Hỏi Ôn Tập Thi GIữa kỳ CTDL

14/ Viết CT tính tỷ số % của trọng số cây bao trùm nhỏ nhất với trọng số DT

Re: Các Câu Hỏi Ôn Tập Thi GIữa kỳ CTDL

sắp 1 DSLK theo thứ tự tăng

sắp 1 DSLK theo thứ tự giảm

Re: Các Câu Hỏi Ôn Tập Thi GIữa kỳ CTDL

Mon	Tue	Wed	Thu	Fri	Sat	Sun
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30	31