吉大算法题汇总（C语言版）
以下为《吉大算法题汇总（C语言版）》的无排版文字预览，完整内容请下载
2000
设一棵二叉树的结点结构为(llink, info, rlink),root为指向该二叉树根结点的指针，p，q分别为指向该二叉树中任意两个结点的指针，试编写一算法ANCESTOR(root, p, q, r)，该算法找到p，q的最近相同祖先。（12‘）
算法思想：可先分别将root到p及root到q的路径分别存到两数组path1与path2中则p，q最近的祖宗存在
三种情况：1）若path1是path2的子集，则p的父节点是pq最近的祖宗
2）若path2是path1的子集，则q的父节点是pq最近的祖宗
3）若path1与path2不是包含与被包含的关系，则当数组元素不相同时，前一个相同的结点就为最近的祖宗。
typedef struct BTNode{
int info;
struct BTNode* llink, *rlink;
}BTNode;
void ANCESTOR( BTNode* root, BTNode* p, BTNode* q, BTNode*&r)
{
BTNode* path1[maxsize],path2[maxsize]; //path1与path2分别存储root到p与root 到q的路径
int top1, top2; //top1与top2对应path1，path2存储p与q的下标
top1 = findpath( root, p, path1,0 );
top2 = findpath( root, q, path2,0 );
if(top1>top2){ //p在以q为根结点的子树上
r = path2[top2-1];
retun;
}
if(top10)
r = path[i-1];
}
int findpath( BTNode*r, BTNode*p,BTNode* path[],int n)
{//该函数实现将r->p的路径存储到path，并返回存储p时的下标
if(r!=NULL){
path[n] = r;
if(r==p)
return r;
if(r->left!=p)
return findpath(r->left, p, path, n+1);
else
return findpath(r->right,p, path, n+1);
}
}
2001
编写一个算法来交换单某某中指针p所指结点与其后继结点，head是该链表的头指针，p指向该链表中某一结点。（7’）
算法思想：要交换p与其后继结点q，只要改变这两个结点的指针指向，先找到p的前驱s，已经q的后继r s->next=q,q->next=p,p->next=r;就相当于交换了pq的位置。
typedef struct LNode{
int data;
struct LNode* next;
}LNode;
void exchange( LNode* head, LNode* p )
{
LNode* s = head, q = p->next, r;
if( q==NULL ) //若p的后继为空,则错误
return;
r = q->next; //找到q的后继
while( s->next!=p )
s = s->next; //找到p的前驱
s->next = q, q->next = p, p->next = r; //交换p与p的后继q
}
2014-967
试给出二叉树自上而下，自左而右的层次遍历算法。
算法思想：定义一个队列，先将根结点入队，然后根结点出队同时遍历该元素并且判断出队结点的左右孩子是否为空，若不为空则按照自左向右依次将结点入队。反复执行直到所有元素出队。这就完成二叉树自上而下自左而右的层次遍历
typedef struct BTNode{
int data; //数据域
struct BTNode* left, *right; //左右孩子指针
}BTNode; //数据类型定义
void visit( BTNode* p){
printf("%d ", p->data);
}//遍历函数
void level( BTNode* r ) //r为根结点指针
{
if(r!=NULL){
BTNode* que[maxsize];
int front = -1, rear = -1;
que[++rear] = r; //根结点入队
while(front!=rear){
r = que[++front];
visit(r);
if(r->left!=NULL) //左子树不为空，则左孩子入队
que[++rear] = r->left;
if(r->right!=NULL) //右子树不为空，右孩子入队
que[++rear] = r->right;
}
}
}//层次遍历算法
20
冒泡排序算法是把最大元素向上移(气泡上浮)，也可以把小的元素下移(气泡下沉)，试给出上浮下沉过程交替的冒泡排序算法。（9’）
算法思想：根据冒泡排序的特征，每进行一次冒泡排序就能确定一个元素的位置，实现双冒泡排序关键是找到冒泡排序的截止点，可以设置两个指针l,r分别指向未确定位置的元素的左右边界位置，每进行一次冒泡排序，边界位置挪一次，直到两个边界位置相等，序列排序完成
void DouBubbleSort( int a[], int l, int r ) //l,r分别指向待排序数组的左右边界
{
int i, tmp;
while( lnextarc )
if(visit[p->adjvex]==0){ //未被访问过的邻接点入队
que[++rear].vex = p->adjvex;
que[rear].lno = Lno+1;
}
}
}
2008-895
已知一棵二叉树的先根和中根遍历结果，试设计一个递归算法，恢复该二叉树。（15’）
算法思路：假设先根遍历序列和后根遍历序列分别存放在一维数组pre[l1~r1]与in[l2~r2]中。先根遍历次序为DLR,中根遍历次序为LDR,D表示根节点，L表示左子，R表示右子树。可知先根遍历第一个节点把中根序列分为左右两棵子树。可在先根序列中找第一个节点，然后在中根序列中找到该点，然后递归构建左右子树。
typedef struct BTNode{
int data;
struct BTNode* left, *right;
}BTNode;
BTNode* restoreBiTree( int pre[],int l1, int r1, int in[], int l2, int r2 )
{//复原二叉树
if( l1>r1 ) //当l1>r1时，对应的左右子树为空
return NULL;
else{
int i, j;
for( i = l2; idata = pre[l1];
p->left = restoreBiTree( pre, l1+1, l1+i-l2, in, l2, i-1 );
p->right = restoreBiTree( pre, l1+i-l2+1, r1,in, i+1,r2 );
return p;
}
}
2012-488
已知非空线性链表第一个结点指针为list，写一个算法，找出链表中数据域值最小的那个结点，并将其链接到链表的最前面，要求：
1）描述算法基本思想；（3‘）
2）用算法描述语言描述算法（5‘）
3）给出算法的时间复杂性分析（2‘）
算法思路：要找出最小值的那个结点，得首结点开始遍历所有结点，定义一个变量min(初始值充分大)，当当前的的结点值大于min时，把结点内容赋值给min。题目要求将最小值结点放到链表最前面，则要改变指针指向，得找到最小值的前驱pre与后继post，使min->next typedef strust LNode{
int data;
struct LNode* next;
}LNode; //定义链表结点结构类型
BTNode* findMin(LNode* list) //返回最小值作为首结点的指针
{
LNode* post, *p, *pre; //pre为最小值结点前驱，post为它的后继
int min = list->data; //将首结点的值作为最小值
if(list->next==NULL)
return list;
for( p = list; p->next; p = p->next)
if( min>p->next>data ){ //更新最小值
pre = p;
min = p->next->data;
}
p = pre->next; //p为最小值结点
post = p->next;
p->next = list->next, pre->next = list, list->next = post; //交换首结点与最小值结点
return p;
}
确定最小值要遍历每个元素，则时间复杂度为链表的长度O(n).
2012-488
设计一个算法求链接存储的二叉树中非叶结点的个数。结点类型为BinTreeNode，结点结构为（left, data, right）,root为指向根结点的指针。要求：
1）描述算法基本思想；（4‘）
2）用算法描述语言描述算法（6‘）
3）给出算法的时间复杂性分析（3‘）
算法思想：统计二叉树中非叶子结点的个数，得遍历二叉树的每个结点，并在遍历每个结点
的同时判断它是否为叶子结点，若是叶子结点，计数器cnt++；
判断条件为(p->left!=NULL&&p->right!=NULL)p为当前遍历的结点,遍历次序可采用先根
次序遍历，先遍历根节点然后递归遍历左右子树
typedef struct BTNode{
int data;
struct BTNode* left, *right;
}BTNode; //结点结构类型定义
void countNoLeafNode( BTNode* r, int &cnt ){//初始化cnt为0
if(r!=NULL){
if( r->left!=NULL&&r->right!=NULL ) //是否为叶子结点的判断条件
cnt++;
countNoLeafNode(r->left, cnt); //左子树遍历
countNoLeafNode(r->right, cnt); //右子树遍历
}
}
2012-966
已知一个带有表头结点的单某某，结点结构为(data, link)。假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，找出链表中倒数第k个位置上的结点。若查找成功，算法输出结点data域的值，并返回1；否则，只返回0.要求：
1）描述算法基本思想；（3‘）
2）用算法描述语言描述算法（6‘）
3）给出算法的时间复杂性分析（3‘）
算法思想：先定义一个足够长大数组A[],数组类型与结点数据域类型一致，从首结点开始遍历链表，每遍历一个结点，同时将结点数据域的值存放到数组A中，直到链表遍历结束，存放链表最后一个结点p数据域部分值的数组A就能确定链表的长度。设链表的长度为len，若len>k, 则输出结点值并返回1，否则返回0
typedef 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; //查找失败
}
2013-941
设多项式
f(x)=a1*x^c1+a2*x^c2+... g(x)=b1*x^t1+b2*x^t2+...用链表表示且按照x的方幂递增有序，试给出算法。判定是否有g(x)=f’(x)。并给出算法的时间复杂度。设多项式中结点的结构定义为(coef, exp, next),其中coef表示x的系数，exp表示x的指数，next指向下个结点。
算法思想：要判断多项式f’(x)?=g(x),只需依次比较两链表对应结点是否系数与指数部分是都相等，若相等就都比较后一个，直到所有结点都相等，返回1，表示都匹配，多项式相等。否则返回0，多项式不等。根据求导公式，能很 内容过长，仅展示头部和尾部部分文字预览，全文请查看图片预览。 &k ){ //初始化父节点为NULL
//r为根结点，paren为r的父节点，level为计算器，n为当前层次，k记录二叉树的高 度
if( r!=NULL ){
if( parent==NULL ) //当父节点为空，二叉树只有一个结点且该结点显然为 独生叶子结点
level[n]++;
else if(p->left==NULL&&p->right==NULL){ //是否为叶子结点的判断条件
if(parent->left==NULL) //父节点只有右孩子
level[n]++;
else if(parent->right==NULL) //父节点只有左孩子
level[n]++;
}
parent = r; //更新父节点
if(kleft, parent, level, n+1);
preOrder( r->right,parent, level, n+1);
}
}
[文章尾部最后500字内容到此结束,中间部分内容请查看底下的图片预览]请点击下方选择您需要的文档下载。
- 仁爱英语八年级上 Unit1 Topic 3 Section C 教学设计
- 3.2-2 段落编号的应用
- 上机实验报告（五）
- 3.2-2 段落编号的应用
- “STOP 5秒”理论
- 硕士研究生入学考试自命题科目 考试大纲
- 动态路由选择算法实验报告4模板
- 工大834考试大纲
- c3-10基于反馈调整差分进化算法的人工智能教育系统1
- 《拔萝卜》教学反思
- 《数据结构(c语言版)》知识点概括
- 宋立业八年级上册Unit1 Topic1 Section A 教学设计
- 仁爱英语八年级上 Unit1 Topic 3 Section C 教学设计
- 实验12最小生成树***实验报告纸
以上为《吉大算法题汇总（C语言版）》的无排版文字预览，完整内容请下载
吉大算法题汇总（C语言版）由用户“huzi945525318”分享发布，转载请注明出处