计算机考研自命题(2)

1、C语言-字符串交替拼接

1、用C编程，将两个字符串数组存储实现交替连接如aaa和bbb两个字符连接成ababab 如aaa和baba 两个字符，连接成 abaaaba

#include<stdio.h>/*
解题思路：将两个字符串交替拼接，定义三个数组，
str1[]存放第一个字符串 
str2[]存放第二个字符串 
str3[]存放拼接的字符串
然后交替放入str3中，首先str3数组下标偶数位先放入str1中的字符，奇数位放入str2中的字符,实现交替连接
然后看谁的字符串更短将更长的字符串全部放入str3中 
*/ 
int main() {char str1[10],str2[10],str3[20];int i=0,j=0,k=0;           		// i记录str1的下标，j记录str2的下标，k记录str3的下标printf("输入第一个字符串：");scanf("%s",str1);printf("输入第二个字符串：");scanf("%s",str2);while(1) {if(k%2 == 0) {   // 依次把str1和str2中 的元素加入str3中 str3[k++] = str1[i++];   } else {str3[k++] = str2[j++];}if(str1[i] == '\0' || str2[j] == '\0') {   // 字符串的长度不一样，看str1和str2谁先到达末尾 if(str1[i] == '\0' ) {			// str1已经全部放入str3中， while(str2[j] != '\0') {	// 则依次将str2中的元素依次加入str3中 str3[k++] = str2[j++];}break;						// 所有元素加入str3 退出大循环 } else {while(str1[i] != '\0') {    //  str2全部放入str3中，加str1中剩余元素依次放入str3 str3[k++] = str1[i++];}break;}}}puts(str3);			// 将str3中的字符串输出 return 0;
}

2、C语言–最大公约数和最小公倍数

2、求最大公约数和最小公倍数

// 方法1、递归方法
#include <stdio.h>/*
解题思路：
最大公约数指的是两个或多个整数共有约数中最大的一个
采用的是欧几里得算法，也叫辗转相除法：就是将 a,b两个数取余数假设 t = a%b，然后将较小的元素 b 对t再取余数，直到最后余数为0,则最后依次取余数的 b就是最大公约数最小公倍数：两个或多个数公有的倍数 ，设a,b两个数  则 LCM = (x*y)/Gcd(x,y)
*/// 最大公约数 递归：辗转相除法 
int Gcd(int a,int b){if(b>0){return Gcd(b,a%b);}else{return a;}
} // 最小公倍数
int Lcm(int x,int y){return (x*y)/Gcd(x,y);
} // 主函数
int main()
{int a,b;scanf("%d %d",&a,&b);printf("最大公约数为:%d\n",Gcd(a,b));printf("最小公倍数为：%d",Lcm(a,b)); return 0;
}

3、数据结构-线索二叉树

3、将10个数字进行排序，二叉树给前序和中序序列，要求画出二叉树并求 后续线索二叉树（给了10个字母）

4、数据结构-哈希表

4、Hash(哈希)排序，6个数，mod7线性排列，并求出比较次数

5、数据结构-快速排序

5、快速排序，写出每趟结果（给了10个具体的数）

/*
解题思路：递归思想
快速排序的思想是取第一个元素作为数轴元素，
然后将原来的序列分为两个部分，左边比枢轴元素小，右边比枢轴元素大，然后将左边的元素再进行快速排序
右边的元素也再进行快速排序，直到序列递增有序*/// 寻找指定位置 ，将枢轴元素分成两个部分
int partition(int A[],int low,int high) {int pivot = A[low];while(low<high) {while(low<high && A[high]>=pivot) {--high;}A[low] = A[high];while(low<high && A[high]<=pivot) {++low;}A[high] = A[low];}A[low] = pivot;return low;
}void QuickSort(int A[],int low,int high) {if(low<high) {int pivotpos = partition(A,low,high);QuickSort(A,low,pivotpos-1);QuickSort(A,pivotpos+1,high);}
}

6、数据结构-二叉树

6、设计算法求二叉树的双亲结点

# include<stdio.h>/*
解题思路： 采用递归思想 
跟据树的先序遍历进行改造，
先看根节点是否有左右子树，并且左右子树是否为x，如果是，则是双亲结点，如果不是
则寻找T的整个左子树和T的整个右子树 
*/// 二叉树定义 
typedef struct BiNode{ELemType data;struct BiNode *lchild,*rchild
}BiNode,*BiTree;// 找双亲结点
BiNode * Findparent(BiTree T,ElemType x){if(T->lchile !=NULL && T->lchild == x){ // 如果存在左子树并且左子树就是x 则T就是x 的双亲结点 return T;}if(T->rchile !=NULL && T->rchild == x){ // 如果存在右子树 且右子树就是x 则T就是x 的双亲结点return T;}* Findparent(T->lchild,x);  * Findparent(T->rchild,x);
} 

7、数据结构-删除重复结点

7、删除链表中重复的结点

/*
解题思路：设置三个指针，p,q = p->next, pre(q的前趋指针),
通过q指针遍历链表，如果和p相同则删除，如果不同，则p后移，q还是从头遍历
直到找出所有相同的结点并删除 
*/// 单链表结构定义
typedef struct LNode{ElemType data;struct LNode *next;
}LNode,*LinkList;/*无序链表*/
void delete_same(LinkList &L){LNode *p = L->next;LNode *q = p->next;LNode *pre = p;		// q的前趋结点for(p,p!=NULL,p = p->next){for(q,q!=NULL;q=q->next,pre = pre->next){LNode *s;   // 待删除结点if(p->data = q->data){s = q;pre->next = q->next;q = pre->next;free(s);} }} 
}// 如果是有序链表的话
/*
定义两个指针p，q。q指针永远指向p的下一个结点，然后遍历链表
*/
void delete_same(LinkList &L){LNode *p = L->next;LNode *q;while(p!=NULL){q = p->next;if(p->data == q->data){p->next = q->next;free(q);}else{p = p->next;}}}