北大“數(shù)據(jù)結構”上機考試復習題總結（1） -自考串講筆記

　　數(shù)據(jù)結構練習題1

　　1.編一C程序，它能根據(jù)讀入的數(shù)據(jù)構造有向圖G，并輸出G的鄰接矩陣和DFS遍歷序列（從V0開始），圖的輸入形式為n Vi0 Vj0 Vi1 Vj1 Vi2 Vj2……Vim Vjm -1 -1（-1，-1為輸入結束標記），它們都是整數(shù)，且100>n>0，其余的值都>=0且<n.

　　（注：程序的可執(zhí)行文件名必須是 e1.exe，存于你的賬號或其debug目錄下。）

　　2. 編一C程序，它能讀入兩組整數(shù)（每組整數(shù)都以-9999為結束標記，個數(shù)都不大于1000），并以從小到大的次序輸出既在第一組整數(shù)中而且不在第二組整數(shù)中的所有整數(shù)（同一個整數(shù)不能輸出兩次）。（輸入時，兩個相鄰的整數(shù)用空格隔開）。

　?。ㄗⅲ撼绦虻目蓤?zhí)行文件名必須是 e2.exe，存于你的賬號或其debug目錄下。）

　　數(shù)據(jù)結構練習題2

　　1.編一C程序，它能讀入兩組整數(shù)（每組整數(shù)都是66個整數(shù)），它們分別是下三角矩陣A和下三角矩陣B的按行優(yōu)先排列的元素（A和B的其它元素均為零）。計算并輸出矩陣A與B的乘積。

　?。ㄗⅲ撼绦虻目蓤?zhí)行文件名必須是 e1.exe，存于你的賬號或其debug目錄下。）

　　#include <stdio.h>

　　#include <stdlib.h>

　　void main（）

　　{

　　int i，j， k1，k2，c[66]，s，k，count=0，flag=0；

　　int a[66]；

　　int b[66]；

　　printf（“請輸入66個數(shù)到a中：\n”）；

　　for（i=0；i<66；i++）

　　scanf（“%d”，&a[i]）；

　　printf（“請輸入66個數(shù)到b中：\n”）；

　　for（i=0；i<66；i++）

　　scanf（“%d”，&b[i]）；

　　for（i=0；i<11；i++）{

　　for（k=0；k<11；k++）

　　{s=0；

　　for（j=0；j<11&&i>=j；j++）

　　k1=i*（i+1）/2+j；

　　if（j>=k）

　　k2=j*（j+1）/2+i；

　　else

　　continue；

　　s+=a[k1]*b[k2]；

　　flag=1；

　　}

　　if（flag）

　　{

　　c[count++]=s；

　　flag=0；

　　}

　　}

　　for（i=0；i<66；i++）

　　printf（“%d”，c[i]）；

　　}

　　2.編一C程序，它能對輸入的一串整數(shù)（不多于1000個，以-9999為結束標記）到數(shù)組a中，再對a的元素進行直接插入排序（從小到大排序），輸出排序結果和所用關鍵字比較次數(shù)。（輸入時，兩個相鄰的整數(shù)用空格隔開）。

　?。ㄗⅲ撼绦虻目蓤?zhí)行文件名必須是 e2.exe，存于你的賬號或其debug目錄下。）

　　#include <stdio.h>

　　#include <stdlib.h>

　　void main（）

　　{

　　int i，j， k1，k2，c[66]，s，k，count=0，flag=0；

　　int a[66]；

　　int b[66]；

　　printf（“請輸入66個數(shù)到a中：\n”）；

　　for（i=0；i<66；i++）

　　scanf（“%d”，&a[i]）；

　　printf（“請輸入66個數(shù)到b中：\n”）；

　　for（i=0；i<66；i++）

　　scanf（“%d”，&b[i]）；

　　for（i=0；i<11；i++）{

　　for（k=0；k<11；k++）

　　{s=0；

　　for（j=0；j<11&&i>=j；j++）

　　k1=i*（i+1）/2+j；

　　if（j>=k）

　　k2=j*（j+1）/2+i；

　　else

　　continue；

　　s+=a[k1]*b[k2]；

　　flag=1；

　　}

　　if（flag）

　　{

　　c[count++]=s；

　　flag=0；

　　}

　　}

　　for（i=0；i<66；i++）

　　printf（“%d”，c[i]）；

　　}

　　數(shù)據(jù)結構練習題3

　　1. 編一C程序，它能根據(jù)輸入的二叉樹前序和中序序列來構造該二叉樹，并能輸出該二叉樹的后序序列和該二叉樹葉的結點的個數(shù)以及該二叉樹高度。（輸入次序是：表示前序序列的字符串、表示中序序列的字符串）。

　?。ㄗⅲ撼绦虻目蓤?zhí)行文件名必須是 e1.exe，存于你的賬號或其debug目錄下。）

　　#include <stdio.h>

　　#include <malloc.h>

　　#include <string.h>

　　void exit（int）；

　　#define MAX 100

　　typedef struct node{

　　char d；

　　struct node *lchild，*rchild；

　　}Tnode；

　　void MKTree（char pre[]，int pres，int pree，char in[]，int is，int ie，Tnode **r）

　　{

　　int i；

　　if（pres>pree||is>ie）

　　*r=NULL；

　　else{

　　*r=malloc（sizeof（Tnode））；

　　for（i=is；i<=ie；i++）

　　if（pre[pres]==in[i]）

　　{

　　MKTree（pre，pres+1，pres+i-is，in，is，is+i-1，&（*r）->lchild）；

　　MKTree（pre，pres+i+is+1，pree，in，is+i+1，ie，&（*r）->rchild）；

　　break；

　　}

　　}

　　}

　　void postorder（Tnode *r）

　　{

　　if（r）

　　{

　　postorder（r->lchild）；

　　postorder（r->rchild）；

　　printf（“%c”，r->d）；

　　}

　　}

　　int num（Tnode *r）

　　{

　　if（r==NULL）

　　return 0；

　　else

　　if（r->lchild==NULL&&r->rchild==NULL）

　　return 1；

　　else

　　return num（r->lchild）+num（r->rchild）；

　　}

　　int height（Tnode *r）

　　{

　　int h1，h2；

　　if（r==NULL）

　　return 0；

　　else

　　{

　　h1=height（r->lchild）；

　　h2=height（r->rchild）；

　　return 1+（h1>h2）？h1：h2；

　　}

　　}

　　void main（）

　　{

　　Tnode *r；

　　char pre[MAX]，in[MAX]；

　　printf（“input preorder and inorder \n”）；

　　gets（pre）；

　　gets（in）；

　　MKTree（pre，0，strlen（pre）-1，in，0，strlen（in）-1，&r）；

　　printf（“The postorder is as follow：\n”）；

　　postorder（r）；

　　printf（“\n there are %d leaves in the tree\n”，num（r））；

　　printf（“h=%d\n”，height（r））；

　　}

　　2.編一C程序，它能讀入一串（n個）整數(shù)（以-9999為結束標記），并判斷第1個整數(shù)在后（n-1）個整數(shù)中出現(xiàn)的次數(shù)，再輸出該次數(shù)。（輸入時，兩個相鄰的整數(shù)用空格隔開）。

　　（注：程序的可執(zhí)行文件名必須是 e2.exe，存于你的賬號或其debug目錄下。）