2015保研试题答案(七秒记忆).doc

1、 编程题（9道题，每道20分，共180分）1、 编写一个完整的程序，使之能完成以下功能：从键盘中输入若干个整数，用链表储存这些输入的数，并要求存储的顺序与输入的顺序相反。#include#includetypedef struct LNodeint data;struct LNode *next;LNode,*LinkList;int main()LinkList L;LNode *s;int x,n;L = (LinkList )malloc(sizeof(LNode);L-next = NULL;scanf(%d,&n);while(n-)scanf(%d,&x);s = (struct LNode *)malloc(sizeof(struct LNode);s-data = x;s-next = L-next;L-next = s;while(L-next)printf(%d ,L-next-data);L = L-next;printf(n);return 0;2、 编写一个函数，把整数序列分成两个部分，使得左边部分都不大于右边部分，不需要排序。 （ 考察的是快速排序的部分）#includeint partion(int arr,int n);int main()int a20,n,i;scanf(%d,&n);for(i = 0;i n;i +)scanf(%d,&ai);partion(a,n); printf(调整后序列为：n);for(i = 0;i n;i +)printf(%d ,ai);printf(n);/printf(%dn,partion(a,n);return 0;int partion(int arr,int n)int i = 0,j = n-1;int pivot = arr0;while(i j)while(i pivot) j-;arri = arrj;while(i j & arri pivot) i+;arrj = arri;arri = pivot;printf(首选数字现在是第%d个，是%dnn,i+1,arri);return i;3、 有两个整数数组A和B，它们分别有m、n个整数。并且都是按非递减序列，现将B数组插入A数组中，使得A数组中各元素不大于B数组中各元素，且还是非递减序列。#includevoid insert(int A,int B,int m, int n);int main()int a30,b30;int i,m,n;scanf(%d %d,&m,&n);for(i = 0;i m;i +)scanf(%d,&ai);for(i = 0;i n;i +)scanf(%d,&bi);insert(a,b,m,n);return 0;void insert(int a,int b,int m, int n)int i,j,k = m-1;int temp = am - 1;for(j=0;bjbj;i-)ai+1=ai;ai+1=bj;for(i = 0;ik+1;i +)printf(%d ,ai);printf(n);for(j = 0;jtemp)printf(%d ,bj);printf(n);4、 两个递增有序整数数列链表La和Lb，将他们合并后，变成一个新的链表，要求该链表递减排序。（结点node由整型data和节点指针next构成）#include#includetypedef struct LNodeint data;struct LNode *next;LNode,*LinkList;LinkList CreateList();LinkList MergeList(LinkList La,LinkList Lb);int main()LinkList La;LinkList Lb;La = (LinkList)malloc(sizeof(LNode);Lb = (LinkList)malloc(sizeof(LNode);La = CreateList();Lb = CreateList();LinkList L = MergeList(La,Lb);while(L-next) printf(%d ,L-next-data); L = L-next; return 0;LinkList CreateList()/创建链表，头插法LinkList L;LNode *s;int n; L = (LinkList)malloc(sizeof(LNode);L-next = NULL;while(scanf(%d,&n)!=EOF)s = (struct LNode *)malloc(sizeof(struct LNode);s-data = n;s-next = L-next;L-next = s;return L;LinkList MergeList(LinkList La,LinkList Lb)/头插法LNode *r,*pa = La-next,*pb = Lb-next;La-next = NULL;while(pa & pb)if(pa-data data)r = pa-next;pa-next = La-next;La-next = pa;pa = r;elser = pb-next;pb-next = La-next;La-next = pb;pb = r;if(pa)pb = pa;while(pb)r = pb-next;pb-next = La-next;La-next = pb;pb = r;free(Lb);return La; 5、编写一个函数，删除链表中的最小值。（结点node由整型data和节点指针next构成）#include#includetypedef struct LNodeint data;struct LNode *next;LNode,*LinkList;LinkList CreateList();LinkList DeleteMin(LinkList L);int main()LinkList L,Head;L = (LinkList)malloc(sizeof(LNode);L = CreateList();Head = DeleteMin(L);while(Head-next) printf(%d ,Head-next-data); Head = Head-next; return 0;LinkList CreateList()LinkList L;LNode *s;int n; L = (LinkList)malloc(sizeof(LNode);L-next = NULL;while(scanf(%d,&n)!=EOF)s = (struct LNode *)malloc(sizeof(struct LNode);s-data = n;s-next = L-next;L-next = s;return L;LinkList DeleteMin(LinkList L)LNode *pre = L,*p = pre-next;LNode *minpre = pre,*minp = p;while(p)if(p-data data)minp = p;minpre = pre;pre = p;p = p-next;minpre-next = minp-next;free(minp);return L;6、 编写函数判断小括号是否匹配。#include#includeint main()char a30,b30;int i,j = 0,flag = 0;scanf(%s,a);int n = strlen(a);if(a0 = ) & n%2 != 0)printf(NO!n);elsefor(i = 0;i n;i +)if(ai = ()bj+ = ai;if(ai = )j-;if(j=0 & i = n-1)flag = 1;if(flag = 1)printf(YES!n);elseprintf(NO!n);return 0;7、 对多个字符串进行字典排序#include#includevoid Sort(char *arr,int n);int main()char *str100,p100100;int i,n;scanf(%d,&n);for(i = 0;i n;i +)scanf(%s,pi);stri = pi;Sort(str,n);for(i = 0;i n;i +)puts(stri);return 0;void Sort(char *arr,int n)int i,j;char *temp;for(i = 1;i n;i +)for(j = 0;j 0)temp=arrj;arrj=arrj+1;arrj+1=temp;8、 编写一个函数，使之能完成以下功能：利用递归方法找出一个数组中的最大值和最小值，要求递归调用函数的格式如下：MinMaxValue(arr,n,&max,&min)，其中arr是给定的数组，n是数组的个数，max、min分别是最大值和最小值。#includevoid MinMaxValue(int arr,int n,int *max,int *min);int main()int a100,n,i;int Max,Min;scanf(%d,&n);for(i=0;in;i+)scanf(%d,&ai);MinMaxValue(a,n,&Max,&Min);printf(Max = %dn,Max);printf(Min = %dn,Min);return 0;void MinMaxValue(int arr,int n,int *max,int *min)if(n=1)*max = arr0;*min = arr0;elseint Max = arr0;int Min = arr0;MinMaxValue(arr+1,n-1,max,min);if(*maxMin) *min = Min;9、 有两字符数组s和t，求t在s中出现第一次的开始位置，如果没有则输出“No”，有则输出开始位置。法一#include#includeint start(char s,char t);int main()char a80,b80;scanf(%s,a);scanf(%s,b);int k = start(a,b);if(k = -1)printf(No!n);elseprintf(%dn,k+1);return 0;int start(char s,char t)int m = strlen(s),i;char *p,*q;for(i = 0;i m;i +)p = s + i;q = t;while(*p & *q & *p = *q)*p +;*q +;if(*p - *q = *p)return i;return -1;法二：#include#includeint start(char s,char t);int main()char a80,b80;scanf(%s,a);scanf(%s,b);int k = start(a,b);if(k = -1)printf(No!n);elseprintf(%dn,k+1);return 0;int start(char s,char t)/*int m = strlen(s),n = strlen(t),i,j=0,k;for(i = 0;i m;i +) k = 0;k = k+i;while(km & jn) if(sk = tj) k+;j+; else j = 0; continue; if(j = n-1) return i; break; */int m = strlen(s);int n = strlen(t);int i=0,j=0;while(im & jn) if(si = tj) i+;j+; else i = i - j + 1; j = 0; if(j = n) return i-j; else return -1;2、 从程序执行效率来说，C语言采取的措施和原因（20分） 1.使用指针：对于指针的理解简单点可以认为类似于汇编中的寻址方式，正是指针的存在使C语言威力无穷。有些程序用其他语言也可以实现，但C能够更有效地实现；有些程序无法用其它语言实现，如直接访问硬件，但C却可以。正因为指针可以拥有类似于汇编的寻址方式，所以可以使程序更高效。2.使用宏函数：函数和宏函数的区别就在于，宏函数占用了大量的空间，而函数占用了时间。函数调用是要使用系统的栈来保存数据的，如果编译器里有栈检查选项，一般在函数的头会嵌入一些汇编语句对当前栈进行检查；同时，CPU也要在函数调用时保存和恢复当前的现场，进行压栈和弹栈操作，所以，函数调