2015保研题答案(伊诺版)

2015保研题答案（伊诺版）以下代码均在VS2010平台下编译执行通过。由于本人水平有限，难免有疏漏之处，若有发现，欢迎指教！——伊诺2015年3月15日之前第一题贴成另外一道长得很像的一题的答案了，感谢有心人指出问题，虽然实现思路几乎一样，但本着我是处女座强迫症患者的优良作风，我还是改发一遍。欢迎大家指正！一、编程题（9道题，每道20分，共180分）1、编写一个完整的程序，使之能完成以下功能：从键盘中输入若干个整数，用链表储存这些输入的数，并要求存储的顺序与输入的顺序相反。structNode{intdata;structNode*next;};intmain(){structNodehead;intnum,n,i;head.next=0;scanf(%d,&n);for(i=0;in;i++){scanf(%d,&num);structNode*p=(structNode*)malloc(sizeof(structNode));p-data=num;p-next=head.next;head.next=p;}structNode*q=head.next;while(q){printf(%d,q-data);q=q-next;}system(pause);return0;}2、编写一个函数，把整数序列分成两个部分，使得左边部分都不大于右边部分，不需要排序。（考察的是快速排序的部分）intpartion(intarr[],intn){intpos=0;inti=0,j=n-1;inttemp;while(i!=j){while(arr[j]=arr[pos]&&ij)j--;while(arr[i]=arr[pos]&&ij)i++;if(ij){temp=arr[i];arr[i]=arr[j];arr[j]=temp;}}temp=arr[i];arr[i]=arr[pos];arr[pos]=temp;return0;}3、有两个整数数组A和B，它们分别有m、n个整数。并且都是按非递减序列，现将B数组插入A数组中，使得A数组中各元素不大于B数组中各元素，且还是非递减序列。如果去掉“使得A数组中各元素不大于B数组中各元素”，我还是可以愉快的写答案的4、两个递增有序整数数列链表La和Lb，将他们合并后，变成一个新的链表，要求该链表递减排序。（结点node由整型data和节点指针next构成）typedefstructnode{intdata;structnode*next;}node;node*Union(node*La,node*Lb){node*p=La-next;node*q=Lb-next;node*temp;La-next=0;while(p&&q){if(p-data=q-data){temp=p-next;p-next=La-next;La-next=p;p=temp;}else{temp=q-next;q-next=La-next;La-next=q;q=temp;}}if(q)p=q;while(p){temp=p-next;p-next=La-next;La-next=p;p=temp;}free(Lb);returnLa;}5、编写一个函数，删除链表中的最小值。（结点node由整型data和节点指针next构成）voiddelmin(node*L){node*p=L-next,*pre=L;node*min=p,*minpre=L;while(p){if(p-datamin-data){min=p;minpre=pre;}pre=p;p=p-next;}minpre-next=min-next;free(min);}6、编写函数判断小括号是否匹配。注：这道题由于限定了只有小括号，故不需要栈来实现intismarry(constchar*str){inttop=-1;charc;while(*str){if(*str=='(')++top;if(*str==')'){if(top==-1)return-1;top--;}str++;}if(top==-1)return0;return-1;}7、对多个字符串进行字典排序voidSort(char*parr[],intn){inti,j;char*str1,*str2;for(i=0;in-1;i++){for(j=i+1;j=n-1;j++){str1=parr[i];str2=parr[j];while(*str1&&*str2&&*str1==*str2)str1++,str2++;if(*str1-*str20){char*temp=parr[i];parr[i]=parr[j];parr[j]=temp;}}}}8、编写一个函数，使之能完成以下功能：利用递归方法找出一个数组中的最大值和最小值，要求递归调用函数的格式如下：MinMaxValue(arr,n,&max,&min)，其中arr是给定的数组，n是数组的个数，max、min分别是最大值和最小值。voidMinMaxValue(intarr[],intn,int*max,int*min){if(n==1){*max=arr[0];*min=arr[0];}else{int_max=arr[0],_min=arr[0];MinMaxValue(arr+1,n-1,max,min);if(*max_max)*max=_max;if(*min_min)*min=_min;}}9、有两字符数组s和t，求t在s中出现第一次的开始位置，如果没有则输出“No”，有则输出开始位置。intstart(chars[],chart[]){ints_length=strlen(s);inti;char*str1,*str2;for(i=0;is_length;i++){str1=s+i;str2=t;while(*str1&&*str2&&*str1==*str2)str1++,str2++;if(*str1-*str2==*str1)returni;}printf(NO!\n);return-1;}二、从程序执行效率来说，C语言采取的措施和原因（20分）1.使用指针：对于指针的理解简单点可以认为类似于汇编中的寻址方式，正是指针的存在使C语言威力无穷。有些程序用其他语言也可以实现，但C能够更有效地实现；有些程序无法用其它语言实现，如直接访问硬件，但C却可以。正因为指针可以拥有类似于汇编的寻址方式，所以可以使程序更高效。2.使用宏函数：函数和宏函数的区别就在于，宏函数占用了大量的空间，而函数占用了时间。函数调用是要使用系统的栈来保存数据的，如果编译器里有栈检查选项，一般在函数的头会嵌入一些汇编语句对当前栈进行检查；同时，CPU也要在函数调用时保存和恢复当前的现场，进行压栈和弹栈操作，所以，函数调用需要一些CPU时间。而宏函数不存在这个问题。宏函数仅仅作为预先写好的代码嵌入到当前程序，不会产生函数调用，所以仅仅是占用了空间，而使程序可以高效运行。在频繁调用同一个宏函数的时候，该现象尤其突出。3.使用位操作：位操作可以减少除法和取模的运算。在计算机程序中数据的位是可以操作的最小数据单位，理论上可以用位运算来完成所有的运算和操作。一般的位操作是用来控制硬件的，或者做数据变换使用，但是，灵活的位操作可以有效地提高程序运行的效率。4.循环嵌套中将较长循环设为内存循环，较短循环设为外置循环，以减少cpu跨切循环层的次数，提高程序的运行效率。让用户可以直接操作进程虚拟地址，给用户提供了高效的内存拷贝函数，变量类型是弱类型，可以各种强制转换。可以嵌入汇编,让代码效率贴近极限.1：指针，可以操作内存2：位移，可以作位运算3：API，可以调用系统API，接近底层4：宏define可以编译的时候替换1.指针；2.define;3.bit操作；4.API；5.循环嵌套转移；6.条件编译；7.嵌入汇编语言；8.（文件包含，这玩意算吗？）2014年10月17日写