計(jì)算機(jī)保研機(jī)試

1、2005年計(jì)算機(jī)學(xué)院研究生復(fù)試試題（機(jī)試部分）說(shuō)明：試題1，2必做，試題3，4中任選一個(gè)，考試時(shí)間14:30-18:00。1 歸并兩個(gè)有序的順序表，要求兩個(gè)有序順序表的數(shù)據(jù)從文件讀入，歸并后的數(shù)據(jù)輸出到結(jié)果文件中。（30分）順序表A的數(shù)據(jù)為：2，6，8，9，14，20，22順序表B的數(shù)據(jù)為：3，6，9，15#include <stdio.h>#define maxLen 100typedef struct _SeqListint DatamaxLen;int size;typedef struct _SeqList SeqList;typedef struct _SeqList*

2、pSeqList;LoadData(char *fname, pSeqList la)FILE *fp;int temp;int i=0;fp = fopen(fname, "rt");while (!feof(fp)fscanf(fp, "%dn", &temp);la->Datai+ = temp;la->size = i;fclose(fp);OutputData(char *fname, SeqList la)FILE *fp;int i;fp = fopen(fname, "wt");for (i=0;

3、i<la.size; i+)fprintf(fp, "%dn", la.Datai);fclose(fp);/*Implement the following parts as ToDo*/MergeList( SeqList la, SeqList lb, pSeqList lc)/* ToDo*/main()SeqList la, lb, lc;LoadData("a.txt", &la);LoadData("b.txt", &lb);MergeList(la, lb, &lc);OutputData

4、("c.txt", lc);2 閱讀下列函數(shù)說(shuō)明和C代碼，將應(yīng)填入其中 處的字句，寫(xiě)在答案的對(duì)應(yīng)欄內(nèi)。隨后上機(jī)調(diào)試程序，得到相應(yīng)結(jié)果。（30分）讀入一批以負(fù)數(shù)為結(jié)束的正整數(shù)，數(shù)據(jù)為5，7，2，4，9，1，建立一個(gè)帶頭結(jié)點(diǎn)的鏈表，鏈表的每個(gè)結(jié)點(diǎn)中包含有兩個(gè)指針：一個(gè)用于鏈接輸入的先后順序，另一個(gè)用于鏈接輸入整數(shù)從小到大的順序。并分別按兩個(gè)指針?lè)较蜻M(jìn)行遍歷輸出。#include <stdio.h>#include<stdlib.h>typedef struct NODEint val ;struct NODE *order;struct NODE *so

5、rt;NODE;void main( )NODE *h,*u,*v,*p,*tail;int d;h=(NODE *)malloc(sizeof(NODE);tail=h;tail->sort=NULL;printf("Please input data:");doscanf("%d",&d);if(d>0)p=(NODE *)malloc(sizeof(NODE);p->val=d; （1） ;tail=p;for(u=h,v=u->sort;v&&v->val<d; （2） ;);p->

6、;sort=v; （3） ;while(d>0); （4） ;p=h->sort;while(p)printf("%d,",p->val);p=p->sort;printf("nn");for (p=h->order;p;p=p->order)printf("%d,",p->val);printf("nn");3 已給定先序構(gòu)造一棵二叉樹(shù)的算法，請(qǐng)你完成其余部分，包括先序、中序、后序遍歷二叉樹(shù)并打印出來(lái)。先序序列建立二叉樹(shù)的順序讀入字符為A B C D E G F ，注意輸

7、入時(shí)用空格代替。（40分）#include <stdio.h>typedef struct BiTNode char e; struct BiTNode *lchild,*rchild;BiTNode;/*Implement the following parts as ToDo*/void preOrderTraverse(BiTNode *T1)/* ToDo*/void inOrderTraverse(BiTNode *T1)/* ToDo*/void postOrderTraverse(BiTNode *T1)/* ToDo*/int CreateBiTree(BiTNod

8、e *T1) char ch, a; scanf("%c%c", &ch, &a); if (ch = ' ') /* ToDo*/ else/* ToDo*/CreateBiTree(&(*T1)->lchild);CreateBiTree(&(*T1)->rchild); return 1;main()/*Call CreateBiTree() function*/CreateBiTree();/*Call three different Traverse functions*/preOrderTraverse

9、();inOrderTraverse();postOrderTraverse();4 根據(jù)二叉樹(shù)的先序和中序序列，設(shè)計(jì)算法重構(gòu)出這棵二叉樹(shù)。（40分）已知一棵二叉樹(shù)的先序遍歷序列是ABECDFGHIJ，中序遍歷序列是EBCDAFHIGJ，請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法，將這棵二叉樹(shù)的結(jié)構(gòu)重構(gòu)出來(lái)，并且輸出它的三種深度優(yōu)先遍歷的結(jié)果（即先序、中序和后序序列）。#include <stdio.h>typedef struct BiTNode char e; struct BiTNode *lchild,*rchild;BiTNode;/*Implement the following parts as

10、 ToDo*/void preOrderTravse(BiTNode *T1)/* ToDo*/void inOrderTravse(BiTNode *T1)/* ToDo*/void postOrderTravse(BiTNode *T1)/* ToDo*/int CreateBiTree(BiTNode *T1, char *preString, char *inString, int start, int end) if (start = end) /* ToDo*/ else/* ToDo*/CreateBiTree(&(*T1)->lchild), preString, inString, start, middle);CreateBiTree(&(*T1)->rchild) , preString, inString, middle+1