北大“數(shù)據(jù)結(jié)構(gòu)”上機(jī)考試復(fù)習(xí)題總結(jié)（2）

數(shù)據(jù)結(jié)構(gòu)練習(xí)題4
    1. 編一C程序，它能根據(jù)輸入的二叉樹(shù)中序和后序序列來(lái)構(gòu)造該二叉樹(shù)，并能輸出該二叉樹(shù)的前序序列和該二叉樹(shù)的度為2的結(jié)點(diǎn)的個(gè)數(shù)并能判斷該二叉樹(shù)是否為二叉排序樹(shù)（若是輸出Yes；否則輸出No）。（輸入次序是：表示中序序列的字母串、表示后序序列的字母串）。
    （注：程序的可執(zhí)行文件名必須是 e1.exe，存于你的賬號(hào)或其debug目錄下。）
    #include
    #include
    #include
    void exit（int）；
    #define MAX 100
    typedef struct node{
    char d；
    struct node *lchild，*rchild；
    }Tnode；
    void MKTree（char in[]，int is，int ie，char post[]，int posts，int poste，Tnode **r）
    {
    int i；
    if（is    *r=NULL；
    else{
    *r=malloc（sizeof（Tnode））；
    （*r）->d=post[poste]；
    for（i=is；i<=ie；i++）
    if（post[poste]==in[i]）
    {
    MKTree（in，is，i-1，post，posts，posts+i-is-1，&（*r）->lchild）；
    MKTree（in，i+1，ie，post，posts+i-is，poste-1，&（*r）->rchild）；
    break；
    }
    if（i>ie）{
    printf（“Error：input contain an error ！\n”）；
    exit（9）；
    }
    }
    }
    void BST（char in[]，int is，int ie）
    {
    int i；
    if（is==ie）
    printf（“yes\n”）；
    else
    {
    for（i=is；i<=ie；i++）
    {
    if（in[i]    continue；
    else
    break；
    }
    if（i==ie）
    printf（“YES\n”）；
    else
    printf（“NO\n”）；
    }
    }
    void preorder（Tnode *r）
    {
    if（r）
    {
    printf（“%c”，r->d）；
    preorder（r->lchild）；
    preorder（r->rchild）；
    }
    }
    int seconde（Tnode *r）
    {
    if（r==NULL）
    return 0；
    else
    if（（r->lchild）！=NULL&&（r->rchild）！=NULL）
    return 1；
    else
    return seconde（r->lchild）+seconde（r->rchild）；
    }
    void main（）
    {
    Tnode *r；
    char post[MAX]，in[MAX]；
    printf（“input inorder and postorder ！\n”）；
    gets（in）；
    gets（post）；
    MKTree（in，0，strlen（in）-1，post，0，strlen（post）-1，&r）；
    printf（“the preorder is as follows：\n”）；
    preorder（r）；
    printf（“\n there are %d seconde in the tree \n”，seconde（r））；
    printf（“if the tree is BST：\n”）；
    BST（in，0，strlen（in）-1）；
    }
    2.編一C程序，它能讀入一串整數(shù)（以-9999為結(jié)束標(biāo)記），再以與輸入次序相反的次序輸出這串整數(shù)（輸入、出時(shí)，兩個(gè)相鄰的整數(shù)用空格隔開(kāi)）。
    （注：程序的可執(zhí)行文件名必須是 e2.exe，存于你的賬號(hào)或其debug目錄下。）
    #include
    #define max 10000
    main（）
    {
    int a[max]；
    int n=0，i，d；
    printf（“please enten tne number：\n”）；
    do{
    scanf（“%d”，&d）；
    if（d==-9999）
    break；
    n++；
    a[n]=d；
    }while（9）；
    for（i=n；i>0；i——）
    printf（“%4d”，a[i]）；
    printf（“\n”）；
    }
    數(shù)據(jù)結(jié)構(gòu)練習(xí)題5
    1. 編一C程序，它能讀入一個(gè)大寫(xiě)英文字母串（字母?jìng)€(gè)數(shù)不多于100，字母兩兩不同），并構(gòu)造以這些字母為關(guān)鍵字的二叉排序樹(shù)，再輸出該二叉排序樹(shù)的后序序列和頁(yè)結(jié)點(diǎn)個(gè)數(shù)。
    （注：程序的可執(zhí)行文件名必須是 e1.exe，存于你的賬號(hào)或其debug目錄下，否則無(wú)成績(jī)）
    2. 編一C程序，它能讀入兩組整數(shù)（每組整數(shù)都以-9999為結(jié)束標(biāo)記，-9999不算在內(nèi)。個(gè)數(shù)都不大于1000），并以從小到大的次序輸出既在第一組整數(shù)中也在第二組整數(shù)中的所有整數(shù)（同一個(gè)整數(shù)不能輸出兩次）。（輸入時(shí)，兩個(gè)相鄰的整數(shù)用空格隔開(kāi)）。
    （注：程序的可執(zhí)行文件名必須是 e2.exe，存于你的賬號(hào)或其debug目錄下，否則無(wú)成績(jī)）
    #include
    void paixu（int r[]，int n）
    {
    int i，j，k；
    int exchange；
    for（i=0；i<=n；i++）
    {
    exchange=0；
    for（j=n-1；j>=i；j——）
    if（r[j+1]    {
    k=r[j+1]；
    r[j+1]=r[j]；
    r[j]=k；
    exchange=1；
    }
    if（！exchange）
    break；
    }
    }
    int jiaoji（int m[]，int n[]，int l[]，int countaa，int countbb）
    {
    int w，x，y；
    int i=0，j=0，k=0；
    for（w=0；w<=countaa；w++）
    {
    for（x=w+1；x<=countaa；x++）
    {
    if（m[w]==m[x]）
    {
    countaa——；
    for（y=x；y<=countaa；y++）
    {
    m[y]=m[y+1]；
    }
    x——；
    }
    }
    }
    while（i<=countaa）
    {
    for（j=0；j<=countbb；j++）
    {
    if（m[i]==n[i]）
    {
    l[k]=m[i]；
    k++；
    break；
    }
    }
    i++；
    }
    return k；
    }
    void main（）
    {
    int a[1000]，b[1000]，c[2000]；
    int excange=0，i，countA，countB，countC；
    printf（“請(qǐng)輸入數(shù)組a： \n”）；
    for（i=0；i<=1000；i++）
    {
    scanf（“%d”，&a[i]）；
    if（a[i]==-9999）
    break；
    }
    countA=i-1；
    paixu（a，countA）；
    printf（“請(qǐng)輸入數(shù)組b： \n”）；
    for（i=0；i<=1000；i++）
    {
    scanf（“%d”，&b[i]）；
    if（b[i]==-9999）
    break；
    }
    countB=i-1；
    paixu（b，countB）；
    countC=jiaoji（a，b，c，countA，countB）；
    printf（“\n\n”）；
    for（i=0；i<=countC-1；i++）
    printf（“%d”，c[i]）；
    printf（“\n”）；