计算机考研自命题(5)

1、C语言–求和

1、展开式求和。输入一个实数x，计算并输出下式的和，直到最后一项的绝对值小于0.00001.计算结果保留2位小数，试编程。

S = x + x²/2！+ x³/3！+ …

/*
算法思想：定义一个求阶乘的函数fact(),
头文件调用math.h函数库：pow()函数求次幂，fabs()函数取绝对值
直到最后一项的绝对值小于0.00001，则输出求和结果，结果保留两位小数
*/
#include
#include


// 求阶乘 
int fact(int n){
    int i,sum=1;
    for(i=1;i<=n;i++){
        sum=sum*i;
    }
    return sum;
}

int main(){
    int a,n,i;
    double x,result,s=0;
    scanf("%lf",&x);
    for(i=1;(pow(fabs(x),i)/fact(i))>=0.00001;i++){
        result=pow(x,i)/fact(i);
        s+=result;
    }
    printf("s=%.2lf",s);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

2、C语言–元素移动

2、有n个整数，使前面各数顺序向后移动m个位置，移出的数再从头移入，编得一个函数实现以上功能，在主函数中输入n个整数

并输出调整后的n个数。

# include

/*
解题思路：
定义一个数组t存放传入的数组A,然后跟据移动的情况从t中取出元素从新放回A中
remove(*A,5,3)假设有5个元素，向后移动3位
A={1,2,3,4,5}  ==>  A={3,4,5,1,2}
首先就是将t中下标为 5-3 = 2 的元素一次存放到A中，
然后将剩余的元素放入A中 
*/

// 元素移动的方法
void remove(int *A,int n,int m) { // n表示元素个数，m表示移动几位
	int t[100];   // 用于存储A[]中的元素 
	int i;
	for(i=0; i<n; i++) { // 将A中的元素全部存储到t中 
		t[i] = A[i];
	}
	for(i = 0 ; i<m; i++) { // 将t 中 下标>=n-m的元素存放到A中 
		A[i] = t[n-m+i];
	}
	for(i = m; i<n; i++) { // 将剩余的元素存放到A中 
		A[i] = t[i-m];
	}
	for(i = 0; i<n; i++) { // 遍历 
		printf("%d ",A[i]);
	}
}

int main() {
	int i,x,num;
	scanf("%d",&num);
	int A[num];
	for(i = 0; i<num; i++) {
		printf("请输入第%d个元素",i+1);
		scanf("%d",&x);
		A[i] = x;
	}
	printf("移动后的元素序列");
	remove(A,num,3);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

3、C语言-文件操作

3、将C盘根目录下文件from.txt的内容复制到to.txt文件中，to.txt与from.txt在同一目录。

/*
解题思路：首先以只读的方式打开文件from.txt,然后以写的方式打开文件to.txt，
使用fgetc()函数将文件from.txt里面的字符一个一个读取出来，然后用fputc()函数将读取出的文件写入to.txt中
*/


# include 
int main()
{
	// 文件复制
	FILE *fp1,*fp2;
	char ch;
	// 打开文件 
	fp1 = fopen("from.txt","r");
	if(fp1 == NULL){
		printf("文件打开失败！\n"); 
	} 
	fp2 = fopen("to.txt","w");
	if(fp2 == NULL){
		printf("文件打开失败:\n"); 
	}
	// 将读取出来的文件写入 to.txt 中 
	while((ch = fgetc(fp1)) != EOF){
		fputc(ch,fp2);
	}
	// 文件关闭 
	fclose(fp1);
	fclose(fp2); 
	return 0; 
 } 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

4、C语言–复数计算

4、要求设计函数完成两个复数相乘的算法。在主函数中输入两个复数，计算后输出乘积结果

/*
解题思路：
复数的运算   i*i = -1
（a+bi）* (c+di) = a*c + a*di- b*d +b*ci
*/
//复数的结构体定义如下：
struct Complex{
	float real;
	float imag;
}Complex;
//要求设计函数完成两个复数相乘的算法。在主函数中输入两个复数，计算后输出乘积结果。

Complex Mul(Complex c1,Complex c2){
    Complex product;
    product.real = c1.real*c2.real - c1.imag*c2.imag;  // 乘积以后的虚部   i*i = -1
    product.imag = c1.imag*c2.real + c1.real*c2.iamg;  // 虚部
    return product;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

5、数据结构

5、下面程序段的功能是建立二叉树的算法，请在下划线处填上正确的内容。

typedef struct node{
int data;
struct node *lchild;
____struct node *rchild____;
}bitree; 
void createbitree(bitree *&bt) {
scanf( “%c”,&ch); 
if(ch=='#')
____bt->data = ch_______;
else { 
bt=(bitree*)malloc(sizeof(bitree)); 
bt->data=ch; 
___createbitree(bt->lchild)_____;
createbitree(bt->rchild);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

6、数据结构

6、建立链表

typedef struct node {
int data; 
struct node *next;
} lklist; 
void lklistcreate(_____lklist___ *&head ) { 
for (i=1;i<=n;i++) { 
p=(lklist *)malloc(sizeof(lklist));
scanf( “%d”,&(p ->data));
p->next=0;
 	if(i==1)
head=q=p;
else {
q->next=p;
______q = p______;
} 
}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

7、数据结构–链表合并

7、实现链式结构上合并排序的算法

# include

//单链表的定义
typedef struct LNode {
	ELemType data;
	LNode *next;
} LNode,*LinkList;

/*
将两个递增有序的链表A,B合并成一个递增有序的链表C

解题思路：假设A,B带有头指针，定义pa,pb指针分别指向A,B的下一个结点，
运用尾插法，先将A，B中较小的元素插入C中，实现整体按元素值递增有序；
因为A，B链表中的结点个数不一样，
所以当A中的结点数更少时 ，将B中的元素依次加入C中
反之，则将A中的元素依次加入C中 
*/
void Merge(LNode A,LNode B,LNode &C) {
	LNode *pa = A->next;
	LNode *pb = B->next;  
	LNode *pc = C;

	while(pa&&pb) {  
		if(pa->data <= pb->data) { // 运用尾插法将小的元素率先加入C链表中
			pc->next = pa;
            pc = pa;
            pa = pa->next;

		} else {
			pc->next = pb;
            pc = pb;
            pb = pb->next;
		}
	}

	while(pa) {
		pc->next = pa;
        pc = pa;
        pa = pa->next;
	}
	while(pb) {
		pc->next = pb;
        pc = pb;
        pb = pb->next;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

8、数据结构–二叉树查找

8、实现在二叉树中查找结点x的算法

# include

/*
解题思路：跟据二叉树的先序遍历进行改造，传入该二叉树和要查找的值
先比较根节点是不是寻找的目标结点，如果是就返回结点，不是就寻找递归寻找左子树和右子树
直到二叉树全部查找完 
*/

// 二叉树的结构定义
typedef struct BiNode{
	ELemType data;
	struct BiNode *lchild;
	struct BiNode *rchild;
}BiNode,*BiTree; 

BiNode *find_x(BiTree Bt,ELemType x){
	while(Bt){
		if(Bt->data == x){
			return Bt;
		}
		*find_x(Bt->lchild,x);
		*find_x(Bt->lchild,x);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

9、数据结构–堆排序

9、关键字序列（k1,k2,k3,…,kn-1）是堆，写出将（k1,k2,k3,…,kn-1,x）调整为堆的算法

# include
/*
解题思路：堆排序的思路
以大根堆为例：把关键字看成一颗完全二叉树，根节点(堆顶元素)就是整个序列的最大值，输出堆顶元素
堆结构被破坏，然后进行调整，将最大的元素交换到堆顶
从n/2开始依次交换 
*/ 
void adjustHeap(ELemType A[],int len,int k) {
	int i;
	A[0] = A[k];// A[0] 暂存子树的根节点
	for(i = 2*k; i<=len; i*=2) { // 沿K较大的子结点向下筛选
		if(i<len && A[i]<A[i+1]){
			i++;       			// 取K较大的子节点下标 
		}
		if(A[0]>=A[i]){			// 筛选结束 
			break;
		}
		else{
			A[k] = A[i];		// 将A[i] 调整到双亲结点上 
			k = i;				// 修改 k 值，以便继续向下筛选 
		} 
	}
	A[k] = A[0];				// 筛选结点放入最终位置 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

10、数据结构–最小生成树

10、给一组数，画邻接矩阵和邻接表，写出prim和克鲁斯卡尔的最小生成树