计算机考研自命题(6)

1、C语言–奇数求和

1、使用函数求奇数和：输入一批正整数（以零或负数为结束标志），求其中的奇数和。要求定义和调用函数 odd(n) 判断数的奇偶

性，当 n 为偶数时返回 0 ，否则返回 1 。试编写相应程序。

/*
解题思路：传入一个数字odd(n)判断 n 是奇数还是偶数，如果是奇数则进行求和
判断奇数是不是奇数 n%2 != 0 就是奇数
*/
# include <stdio.h>// 判断元素奇偶性
int odd(int n){if(n%2==0){  // n是偶数 return 0;}else{return 1;  // n 是奇数 } 
} int main(){int i = 0,len = 0,num,sum = 0;int arr[999]; printf("请输入数字:\n");scanf("%d",&num);while(num!=-1){arr[i] = num;len++;scanf("%d",&num);i++;}// 计算奇数和 for(i = 0;i<len;i++){if(odd(arr[i]) == 1){sum = sum+arr[i];}}printf("sum = %d\n",sum);return 0;
}

2、C语言–矩阵求和

2、矩阵运算：读入1 个正整数 n(1 ≤n≤6), 再读入n 阶方阵 a,计算该矩阵除副对角线、最后一列和最后一行以外的所有元素之和。

副对角线为从矩阵的右上角至左下角的连线。试编写相应程序。

/*
解题思路：用二维数组构建一个方阵，然后去除副对角线、最后一行最后一列,求和 
i,j为数组下标
副对角线: i+j = n-1
最后一行: i = n-1
最后一列: j = n-1
*/# include<stdio.h>
int main(){int arr[6][6];int n,i,j,sum = 0;scanf("%d",&n);printf("需要构成%d阶方阵\n",n); printf("请输入元素值\n");// 数入方阵for(i = 0;i<n;i++){for(j = 0;j<n;j++){scanf("%d ",arr[i][j]);}} // 去除副对角线、最后一行最后一列,求和 for(i = 0;i<n;i++){for(j = 0;j<n;j++){if(i!=n-1&&j!=n-1&&i+j!=n-1){sum = sum+arr[i][j];} }} printf("sum = %d\n",sum); return 0;
}

3、C语言-文件操作

3、将文件中的数据求和并写入文本文件尾: 文件Int_Data.dat 中存放了若干整数，将文件中所有数据相加，并把累加和写入该文件

的最后。试编写相应程序。

/*
解题思路：首先打开文件，利用fscanf()函数从文件中读入一个元素进行求和，feof()函数判断是否到达文件尾，然后将所有元素的和
用fprintf()函数从新写回文件中
*/#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>int main(void){int number, sum;sum = 0;FILE *fp1;fp1 = fopen("Int_Data.dat", "r+");if (fp1 == NULL) {printf("Open file error.\n");exit(0);}fscanf(fp1, "%d", &number);       // 从文件中读取一个数字 while (!feof(fp1)) {             // 是否读取到文件尾 sum += number;fscanf(fp1, "%d", &number);}fprintf(fp1, "%d\n", sum);		// 将文件中读取出来的数据和从新写入文件尾 fclose(fp1); return 0;}

4、C语言–寻找字符串

4、查找子串 : 输入两个字符串 s 和 t ，在字符串 s 中查找子串 t ，输出起始位置，若不存在，则输出 -1。要求自定义函

char*search(char *s,char *t)返回子串 t 的首地址，若未找到，则迟回NULL。试编写相应程序。

/*
解题思路：输入两个字符串，计算字符串的长度，如果子串 > 主串，那么毕竟失败，
如果子串 < 主串，则开始进行比较，将p指向主串s的首地址，将字串t中的每个字符串和p对比，如果找到一个相同字符则p和t同时向后移动，比较剩下的字符，如果相同的序列返回第一个地址
如果没有找到相同字符则将p向后移动一个，t从头开始，直到将整个s都查找完
*/# include<stdio.h>
# include<string.h>char* search(char*s,char*t)
{	int size_t=strlen(t),size_s=strlen(s),T,i,j;char *p=NULL;for(i=0;i<=(size_s-size_t);i++){p=s+i;T=1;for(j=0;j<size_t;j++){if(*p!=*(t+j)){T=0;break;}p++;}if(T==1)break;}if(T==0)return NULL;elsereturn s+i;
}int main(){char s[100];char t[100];char *p;printf("请输入主串:");scanf("%s", s);printf("请输入字串:");scanf("%s", t);p = search(s, t);if(p!=NULL){printf("匹配成功,起始位置为:%ld\n", p - s);	} else{printf("匹配失败!");}return  0;
}

5、程序填空

5、程序填空（注：<—>代表两个变量的数据交换）。

/*
第一趟将最小的元素放在r[1]中，最大的元素放在r[n]中，
第二趟将第二小的元素放在r[2]中，第二大的元素放在r[n-1]中
以此类推，直到所有序列递增有序
*/void sort(SqList &r,int n) {i=1;while((1)______i<n-i-1______________) {min=max=1;for (j=i+1;(2)__j<n-i-1___ ;++j){if((3)__r[j].key<r[min].key___) min=j; else if(r[j].key>r[max].key) max=j;}if((4)____min != i___) r[min] < ---- >r[j];if(max!=n-i+1){if ((5)___max == i___) r[min] < ---- > r[n-i+1]; else ((6)___r[max] < ---- > r[n-i+1]; ___);}i++;}
}

6、数据结构–共享栈

6、设有两个栈 s1、s2 都采用顺序栈方式，并共享一个存储区[0，……，maxsize-1]，为了尽量利用空间，减少溢出的可能，可采

用栈顶相向、迎面增长的存储方式，试设计s1、s2有关入栈和出栈的操作算法。

/*
解题思路：
共享栈的性质是让两个顺序栈共享一个数组空间，
top[0] 表示 S1 ,top[1] 表示 S2入栈操作：
当 S.top[1] - S.top[0] == 1时表示栈满
如果栈不满，则判断是在S1还是S2中插入元素，
如果是S1 则s.data[++s.top[0]] = x
如果是S2 则s.data[--s.top[1]] = x出栈操作：
先判断是S1元素出栈还是S2元素出栈
如果是S1，判断栈是不是为空s.top[0] == -1，不为空进行元素出栈操作s.data[s.top[0]--]
如果是S2,判断栈是不是为空s.top[1] == maxsize，不为空进行出栈操作s.data[s.top[1]++]
*/# include <stdio.h>
#define maxsize 100   //两个栈共享顺序存储空间所能达到的最多元素数，初识化为100
#define ElemType int       //假设元素类型为整型typedef struct Stack{ElemType data[maxsize];    //栈空间int top[2];     //top为两个栈顶指针
}Stack;
Stack s;
//入栈操作
int push(int i,ElemType x){//入栈操作，i为栈号，i=0表示左边的s1栈，i=1表示右边的s2栈，x是入栈元素//入栈成功返回1，否则返回0if(i<0||i>1){printf("栈号输入不对");exit(0);}if(s.top[1]-s.top[0]==1){printf("栈已满\n");return 0;}switch(i){case 0 : s.data[++s.top[0]] = x;return 1; break;case 1 : s.data[--s.top[1]] = x;return 1;}
}
//退栈操作
ElemType pop(int i){//退栈。i代表栈号，i=0时为s1栈，i=1时为s2栈//退栈成功返回退栈元素，否则返回-1if(i<0||i>1){printf("栈号输入错误\n");exit(0);}switch(i){case 0:if(s.top[0] == -1){printf("栈空\n");return -1;}else{return s.data[s.top[0]--];}break;case 1:if(s.top[1] == maxsize){printf("栈空\n");return -1;}else{return s.data[s.top[1]++];}break;}
}

7、数据结构–链表合并

7、假设有两个按元素值递增排序的线性表，均已单链表项式存储，请编写算法将这两个单链表合并为一个按元素值递减排序的

单链表，并要求利用远来两个单链表的结点存放归并后的单链表。

# include<stdio.h>//单链表的定义
typedef struct LNode {ELemType data;LNode *next;
} LNode,*LinkList;/*解题思路：假设A,B带有头指针，定义pa,pb指针分别指向A,B的下一个结点，
在定义一个r指针，指向 pa/pb的下一个结点，防止断链
把从新排序的结点存放到A中，
运用头插法，先将A，B中较小的元素插入A中，实现整体按元素值递减有序；
因为A，B链表中的结点个数不一样，
所以当A中的结点数更少时 ，将B中的元素依次加入A中
反之，则将A中的元素依次加入C中
*/
LinkList Merge(LNode &A,LNode &B) {LNode *pa = A->next;LNode *pb = B->next;LNode *r;     		// 标记指针，防止断链，指向 pa/pb的下一个结点A->next == NULL;    // 将原来的A链表置空，用来存储从新组合的链表 Cwhile(pa&&pb) {   //if(pa->data <= pb->data) { // 运用头插法将大的元素率先加入C链表中r = pa->next;pa->next = A->next;A->next = pa;pa = r;} else {r = pb->next;pb->next = A->next;A->next = pb;pb = r;}}if(pa) {pb = pa;}while(pb) {r = pb->next;pb->next = A->next;A->next = pb;pb = r;}free(B);
}

8、数据结构–二叉树

8、假设一个仅包含二元运算符的算术表达式以链表形式存储在二叉树BT中，写出计算该算术表达式值的算法

/*
解题思路：利用递归思想
利用二叉树的后续遍历进行改造
先计算出左子树的值，然后再算出右子树的值，最后再根据根节点的符号求出最终值
树的结构体中添加运算符和运算值
*/typedef struct BiNode{int data;   // 数值int value;	// 运算值char opt;	// 操作符struct BiNode *lchild,*rchild;		// 左右子树
}*BiTree,BiNode;//对二叉链表树中的结点计算
int Calculate(BiTree Bt){    int val_l, val_r;        if(Bt!=NULL){val_l = Calculate(Bt->lchild);    //递归计算左、右子树val_r = Calculate(Bt->rchild);switch(Bt->opt){        //根据根节点的字符将左右子结果计算为当前这一层子树的结果case'+':Bt->value = val_l + val_r;break;case'-':Bt->value = val_l - val_r;break;case'*':Bt->value = val_l * val_r;break;case'/':Bt->value = val_l / val_r;break;default:break;}}return Bt->value;
}