question 1

a) represent idea about sort descending use insertion algorithm

b) give a array A{25,67,34,15,42,7} illustrate step by step arrange array A descending by insertion sort

solution

void insertion_sort(int a[],int size)
{
for(int i=1;i<size;i++){
int temp=a[i];
int pos=i;
while(pos>0&&a[pos-1]>temp){
 a[pos]=a[pos-1];
 pos--;
}
a[pos]=temp;
}

question b:

question 2

a) represent this graph using adjacency matrix

b) use kruskal algorithm to find minimum spanning tree

c) with this graph choose another edge and change weight of this edge to make a new graph have different minimum spanning tree but still have same length of minimum spanning tree in question b

solution

represent graph using adj matrix

#include<iostream>
using namespace std;
int verticle;
int edge;
int adj[100][100];
void input(){
cin>>verticle;
cin>>edge;
for(int i=1;i<=edge;i++){
int x,y; // x,y is endpoint of this edge
cin>>x>>y;
a[x][y]=a[y][x]=1;
}
int main(){

minimum spanning tree

krukal
intalization every verticle on this graph like forest;
in each intalize  find save edge and put in minimum spanning tree
the question is what is save edge?
there are have two  critaria of save edge
edge have minimum weight;
and when put in minimum spanning tree don't create acyclic