đề thi và đáp án môn cấu trúc dữ liệu và giải thuật

đề thi và đáp án môn CTDL & GT cấu trúc dữ liệu và giải thuật , lập trình c/c++
1. tạo 2 danh sách liên kết đơn l1,l2 với giá trị của các node trong danh sách là số nguyên.việc nhập mỗi danh sách kêt thúc khi nhập vào số 0. in các giá trị l1, l2 ra màn hình
2. viết hàm merge thực hiện việc trộn luân phiên danh sách l2 vào l1 sao cho sau khi trộn l2 rỗng
3. viết hàm sắp xếp danh sách l1 giảm dần theo trường dữ liệu.
4. chèn 1 số nguyên vào danh sách sao cho vẫn đảm bảo tính giảm dần của l1.

code bài làm:

#include<iostream>
using namespace std;
typedef struct tagnode
{
    int x;
    struct tagnode *next;
}node;
typedef struct taglist
{
    node *dau;
    node *cuoi;
}list;
void khoitao(list &l)
{
    l.dau=l.cuoi=NULL;
}
node *taonode(int x)
{
    node *p=new node;
    if(p==NULL) exit(1);
    p->x=x;
    p->next=NULL;
    return p;
}
void themcuoi(list &l,node *p)
{
    if(l.dau==NULL) l.dau=l.cuoi=p;
    else
    {
        l.cuoi->next=p;
        l.cuoi=p;
    }
}
void nhap(list &l)
{
    int x;
    node *p;
    do{
        cin>>x;
        if(x!=0)
        {
            p=taonode(x);
            themcuoi(l,p);
        }
    }while(x!=0);
}
void xuat(list l)
{
    node *p=l.dau;
    while(p!=NULL)
    {
        cout<<p->x<<" ";
        p=p->next;
    }
}
void sapxep(list &l)
{
    node *p1=l.dau,*p2;
    while(p1!=NULL)
    {
        p2=p1->next;
        while(p2!=NULL)
        {
            if(p2->x > p1->x) swap(p1->x,p2->x);
            p2=p2->next;
        }
        p1=p1->next;
    }
}
void xoadau(list &l)
{
    if(l.dau!=NULL)
    {
        node *p=l.dau;
        if(l.dau==l.cuoi)
        {
            l.dau=l.cuoi=NULL;
            delete p;
        }
        else
        {
            l.dau=l.dau->next;
            delete p;
        }
    }
}
void themdau(list &l,node *p)
{
    if(l.dau==NULL) l.dau=l.cuoi=p;
    else
    {
        p->next=l.dau;
        l.dau=p;
    }
}
void themsauQ(list &l,node *Q,node *p)
{
    if(Q==NULL) themdau(l,p);
    else if(Q==l.cuoi) themcuoi(l,p);
    else
    {
        p->next=Q->next;
        Q->next=p;
    }
}
void merge(list &l1,list &l2)
{
    node *p=l1.dau,*p1;
    while(l2.dau!=NULL && p!=NULL)
    {
        p1=taonode(l2.dau->x);
        themsauQ(l1,p,p1);
        xoadau(l2);
        if(p!=l1.cuoi) p=p->next;
        if(p!=l1.cuoi) p=p->next;
    }
}
void insert(list &l,int a)
{
    node *p1=taonode(a);
    node *p=l.dau,*p2=NULL;
    while(p!=NULL)
    {
        if(a>p->x)
        {
            if(p2==NULL) themdau(l,p1);
            else themsauQ(l,p2,p1);
            break;
        }
        p2=p;
        p=p->next;
    }
}
void main()
{
    list l1,l2;
    khoitao(l1);khoitao(l2);
    cout<<"nhap l1:\n";
    nhap(l1);
    cout<<"nhap l2:\n";
    nhap(l2);
    cout<<"\nxuat cac gia tri:\nl1: ";
    xuat(l1);
    cout<<"\nl2: ";
    xuat(l2);
    cout<<"\ncac gia tri l1,l2 sau khi merge:\n";
    merge(l1,l2);
    cout<<"l1: ";xuat(l1);
    cout<<"\nl2: ";xuat(l2);
    cout<<"\nsau khi sap xep giam danh sach l1:\n";
    sapxep(l1);
    xuat(l1);
    cout<<"\nnhap X=";
    int x;cin>>x;
    insert(l1,x);
    cout<<"l1: ";xuat(l1);
    cout<<endl;
    system("pause");
}