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

數(shù)據(jù)結(jié)構(gòu)練習題1

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

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

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

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

數(shù)據(jù)結(jié)構(gòu)練習題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為結(jié)束標記）到數(shù)組a中，再對a的元素進行直接插入排序（從小到大排序），輸出排序結(jié)果和所用關鍵字比較次數(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ù)結(jié)構(gòu)練習題3

1. 編一C程序，它能根據(jù)輸入的二叉樹前序和中序序列來構(gòu)造該二叉樹，并能輸出該二叉樹的后序序列和該二叉樹葉的結(jié)點的個數(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為結(jié)束標記），并判斷第1個整數(shù)在后（n-1）個整數(shù)中出現(xiàn)的次數(shù)，再輸出該次數(shù)。（輸入時，兩個相鄰的整數(shù)用空格隔開）。

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