北大“数据结构”上机考试复习题总结（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.

　　（注：程序的可执行文件名必须是 e1.exe，存于你的账号或其debug目录下。）

　　2. 编一C程序，它能读入两组整数（每组整数都以-9999为结束标记，个数都不大于1000），并以从小到大的次序输出既在第一组整数中而且不在第二组整数中的所有整数（同一个整数不能输出两次）。（输入时，两个相邻的整数用空格隔开）。

　　（注：程序的可执行文件名必须是 e2.exe，存于你的账号或其debug目录下。）

　　数据结构练习题2

　　1.编一C程序，它能读入两组整数（每组整数都是66个整数），它们分别是下三角矩阵A和下三角矩阵B的按行优先排列的元素（A和B的其它元素均为零）。计算并输出矩阵A与B的乘积。

　　（注：程序的可执行文件名必须是 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的元素进行直接插入排序（从小到大排序），输出排序结果和所用关键字比较次数。（输入时，两个相邻的整数用空格隔开）。

　　（注：程序的可执行文件名必须是 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程序，它能根据输入的二叉树前序和中序序列来构造该二叉树，并能输出该二叉树的后序序列和该二叉树叶的结点的个数以及该二叉树高度。（输入次序是：表示前序序列的字符串、表示中序序列的字符串）。

　　（注：程序的可执行文件名必须是 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）个整数中出现的次数，再输出该次数。（输入时，两个相邻的整数用空格隔开）。

　　（注：程序的可执行文件名必须是 e2.exe，存于你的账号或其debug目录下。）