吉林大学 考研真题答案 2015-2014-2013-2012年 966答案源码

吉林大学 考研真题答案 2015-2014-2013-2012年 966答案源码
所有的源码均可以上机运行！！
王道论坛 吉林大学板块 被某些人操控了 我发的所有关于答案部分全给我审核不通过。。。
咱也不知道为什么 哈哈 只能来这分享了！！
希望对考研的同学们有些帮助！

2015-966
int Stack[1000];
int Top = -1;
void Search(struct BTreeNode* root,struct BTreeNode* Target)
{  if(root == NULL)return;
Stack[++Top] = root->data;if(root->data == Target->data){for(int i = Top;i>=0;i--)printf("%d ",Stack[i]);return;}if(root->left!=NULL){Search(root->left, Target);Top--;}if(root->right!=NULL){Search(root->right,Target); Top--;}return;
}
时间复杂度O(n);2014-966给出二叉树的自下而上自右而左的层次遍历算法。
1）描述算法基本思想；（3‘）
2）设置二叉树的存储结构（2‘）
3）基于以上设计的存储结构，用算法描述语言描述算法，求要求对算法的关键步骤给出注释。
算法思想：只需设一个栈，自左向右自上而下将遍历的元素依次存放到栈中，出栈顺序就为自下而上    //自右而左了。typedef struct BTNode{int data;			//数据域struct BTNode* left, *right;	//左右孩子指针}BTNode;		//数据类型void level( BTNode* r ){BTNode* que[maxsize];		//定义队列,这里队列从队尾向前输出相当于栈int front = -1, rear = -1;	//队首与队尾指针if( r!=NULL ){que[++rear] = r;while( rear!=front ){r = que[++front];if( r->left!=NULL)	//左子树不为空，则左孩子入队que[++rear] = r->left;if( r->right!=NULL )//右子树不为空，右孩子入队que[++rear] = r->right;}for( int i = top; top>=0; i-- )printf("%d ", que[i]->data);	//自下而上自右向左遍历结点prinf("\n");	//换行}}给定连通图G和G中的一个结点，求G的支撑树T。并使其满足如下两个条件:
第一：T的根为v；第二：T的层次遍历次序恰好是以v为起点的G的某个广度优先遍历次序。要求
1）描述算法基本思想；（2‘）
2）设计图G和支撑树T的存储结构（4’）
3）基于以上的设计的存储结构，用算法描述语言描述算法。并要求对算法中的关键步骤给出注释。
算法思想：要得到的支撑树与连通图G的dfs遍历次序一样，只要按照dfs遍历次序建立支撑树就行了，定义一个队列存储dfs遍历的节点。同时为了依附同一一顶点的边作为顶点的子树，需设置一个标志数组Mark[]标记顶点是否为优先遍历顶点的子树。若是则标志数组置1，否则为0图G的存储结构：typedef struct ArcNode{int adjvex;struct ArcNode* nextarc;}ArcNode;		//边表结点类型typedef struct VNode{ArcNode* firstarc;	//指向第一条边}VNode;		//顶点表结点类型typedef struct {VNode adjlist[maxsize];	//邻接表int n, e;	//顶点及边数目}AGraph; 		//图的邻接表存储支撑树T的存储结构：typedef struct TNode{int childnum;		//孩子编号struct TNode* nextchild;	//顶点的子节点指针，采用邻接表存储}TNode;	//孩子结点类型typedef struct parent{TNode* firstchild;	//指向第一个孩子}parent;	//父亲节点类型typedf struct{parent pnode[maxsize];	int n;	//树结点的个数}Tree;	//树的单链表表示void bfsTree( AGraph* g, int v, Tree* root){int mark[maxsize] = {0};	//标志数组，初始化为0int que[maxsize], front = -1, rear = -1, i;ArcNode* p;que[++rear] = v;		//起始点v先入队while(front!=NULL){i = que[++front];	//v出队mark[i] = 1;	//表示顶点i被访问过TNode* s = NUll;	for( p = g->adjlist[i].firstarc; p; p = p->nextarc ){		//按照bfs遍历次序建立支撑树if(mark[p->adjvex]==0){s = createlist(s);		//后插法建立链表存储以父节点为顶点的孩子链表，并返回第一个孩子指针que[++rear] = p->adjvex;}pnode[i]->fistchild = s;		//父顶点指向第一个孩子}}}
2013-9664、int Stack[1000];
int Top = -1;
void Search(struct BTreeNode* root,struct BTreeNode* Target)
{if(root == NULL)return;Stack[++Top] = root->data;if(root->data == Target->data){for(int i = Top;i>=0;i--)printf("%d ",Stack[i]);return;}if(root->left!=NULL){Search(root->left, Target);Top--;}if(root->right!=NULL){Search(root->right,Target);Top--;}return;
}
时间复杂度O(n);
2012-966设计一个算法，以求出无向无权连通图G={V,E}中，距离顶点v最短路径长度为k的所有顶点，路径长
度以边数为单位计算，图G采用邻接表存储。
算法思想：以v为起点对图G进行bfs，同时并给每个顶点按相对起始点长度编号，对应的编号相当于到顶点v的路径长度。就得定义一个队列，该队列元素数据类型为(vex,lno),vex为顶点号，lno为层次号。
定义数据存储结构：typedef struct ArcNode{int adjvex;struct ArcNode* nextarc;}ArcNode;		//边结点typedef struct VNode{ArcNode* firstarc;	//指向第一条邻接边}VNode;typedef struct{VNode adjlist[maxsize];	//邻接表的顶点int n, e;	//n为顶点数目，e为边数}AGraph;	//图的邻接表存储typedef struct{int vex;	//顶点号int lno;	//层次号}St;	//队列数类型void bfs( AGraph* g, int v, int k)	//v为起始点,k为相对v长度为k{ ArcNode* p;St que[maxsize];int visit[maxsize] = {0},front = -1, rear = -1, i, Lno = 1;//visit为标记数组，为0表示为被访问过，为1表示已被访问过que[++rear].vex = v;que[rear].lno = Lno;	//起始点入队while( rear!=front ){i = que[++front].vex;	//元素出队visit[i] = 1;Lno = que[front].lno;if( Lno==k ){printf("%d ", i);	//输出离v最短路径为k的结点}for( p = g->adjlist[i].firstarc; p!=NULL; p = p->nextarc )if(visit[p->adjvex]==0){	//未被访问过的邻接点入队que[++rear].vex = p->adjvex;que[rear].lno = Lno+1;}}	}已知一个带有表头结点的单链表，结点结构为(data, link)。假设该链表只给出了头指针list。
在不改变链表的前提下，请设计一个尽可能高效的算法，找出链表中倒数第k个位置上的结点。若查找
成功，算法输出结点data域的值，并返回1；否则，只返回0.要求：
1）描述算法基本思想；（3‘）
2）用算法描述语言描述算法（6‘）
3）给出算法的时间复杂性分析（3‘）
算法思想：先定义一个足够长大数组A[],数组类型与结点数据域类型一致，从首结点开始遍历链表，每遍历一个结点，同时将结点数据域的值存放到数组A中，直到链表遍历结束，存放链表最后一个结点p数据域部分值的数组A就能确定链表的长度。设链表的长度为len，若len>k, 则输出结点值并返回1，否则返回0typedef struct LNode{int data;struct LNode* link;}LNode;		//链表结构定义int printNum( LNode* list, int k ){int A[maxsize], i = 0;for( LNode* p = list; p; p = p->link )A[i++] = p->data;if(i>k){				//此时的i为链表的长度printf("%d\n", A[i-k]);	return 1;			//查找成功}else return 0;			//查找失败}二叉树以链表形式(left, data, right)存储，给出求二叉树宽度的算法。二叉树的宽度是指二叉树
的各层上，具有结点数最多那一层上的结点总数。
算法思想：可定义一个计数数组levelnum(初始化为0)，对二叉树遍历的时候，每遍历同一层时，下边对应的levenum[]增1来记录同一层结点的数目。二叉树遍历采用先根遍历typedef struct BTNode{int data;BTNode* left, *right;}BTNode;		//数据类型定义int levelnum[maxsize] = {0};	//初始化计数器为0void preTraverse( BTNode *r, int n )	//先根遍历,r为根结点指针，n为r对应二叉树的层次号{if( r!=NULL ){levelnum[n]++；preTraverse( r->left, n+1 );	//遍历左子树preTraverse( r->right,n+1 );	//遍历右子树}}	int BiTreewidth( int levelnum[] ){int i = 0, max = 0; while(levelnum[i]!=0){if(max<levelnum[i])max = levelnum[i];i++;}return max;		//返回二叉树宽度}