北大自考数据结构上机考试复习总结[2]

北大自考数据结构上机考试复习总结[2]  

编一C程序 它能对输入的一串整数(不多于 个 以 为结束标记)到数组a中 再对a的元素进行直接插入排序(从小到大排序) 输出排序结果和所用关键字比较次数 (输入时 两个相邻的整数用空格隔开)

　　(注 程序的可执行文件名必须是 e exe 存于你的账号或其debug目录下 )

　　#include

　　#include

　　void main()

　　{

　　int i j k k c[ ] s k count= flag= ;

　　int a[ ];

　　int b[ ];

　　printf( 请输入 个数到a中 n );

　　for(i= ;i< ;i++)

　　scanf( %d &a[i]);

　　printf( 请输入 个数到b中 n );

　　for(i= ;i< ;i++)

　　scanf( %d &b[i]);

　　for(i= ;i< ;i++){

　　for(k= ;k< ;k++)

　　{s= ;

　　for(j= ;j< &&i>=j;j++)

　　k =i*(i+ )/ +j;

　　if(j>=k)

　　k =j*(j+ )/ +i;

　　else

　　continue;

　　s+=a[k ]*b[k ];

　　flag= ;

　　}

　　if(flag)

　　{

　　c[count++]=s;

　　flag= ;

　　}

　　}

　　for(i= ;i< ;i++)

　　printf( %d c[i]);

　　}

　　数据结构练习题

　　 编一C程序 它能根据输入的二叉树前序和中序序列来构造该二叉树 并能输出该二叉树的后序序列和该二叉树叶的结点的个数以及该二叉树高度 (输入次序是 表示前序序列的字符串 表示中序序列的字符串)

　　(注 程序的可执行文件名必须是 e exe 存于你的账号或其debug目录下 )

　　#include

　　#include

　　#include

　　void exit(int);

　　#define MAX

　　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+ pres+i is in is is+i &(*r) >lchild);

　　MKTree(pre pres+i+is+ pree in is+i+ 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 ;

　　else

　　if(r >lchild==NULL&&r >rchild==NULL)

　　return ;

　　else

　　return num(r >lchild)+num(r >rchild);

　　}

　　int height(Tnode *r)

　　{

　　int h h ;

　　if(r==NULL)

　　return ;

　　else

　　{

　　h =height(r >lchild);

　　h =height(r >rchild);

　　return +(h >h )?h h ;

　　}

　　}

　　void main()

　　{

　　Tnode *r;

　　char pre[MAX] in[MAX];

　　printf( input preorder and inorder n );

　　gets(pre);

　　gets(in);

　　MKTree(pre strlen(pre) in strlen(in) &r);

　　printf( The postorder is as follow n );

　　postorder(r);

　　printf( n there are %d leaves in the treen num(r));

　　printf( h=%dn height(r));

　　}

　　

lishixinzhi/Article/program/sjjg/201311/23801