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

　　數據結構練習題1

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

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

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

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

　　數據結構練習題2

　　1.編一C程序，它能讀入兩組整數（每組整數都是66個整數），它們分別是下三角矩陣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個數到a中：\n”）；

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

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

　　printf（“請輸入66個數到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程序，它能對輸入的一串整數（不多于1000個，以-9999為結束標記）到數組a中，再對a的元素進行直接插入排序（從小到大排序），輸出排序結果和所用關鍵字比較次數。（輸入時，兩個相鄰的整數用空格隔開）。

　?。ㄗⅲ撼绦虻目蓤?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個數到a中：\n”）；

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

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

　　printf（“請輸入66個數到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]）；

　　}

　　數據結構練習題3

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

　?。ㄗⅲ撼绦虻目蓤?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個）整數（以-9999為結束標記），并判斷第1個整數在后（n-1）個整數中出現的次數，再輸出該次數。（輸入時，兩個相鄰的整數用空格隔開）。

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