c笔试题大全

c语言编程笔试题大全2007年03月19日星期一00:151、线形表a、b为两个有序升序的线形表，编写一程序，使两个有序线形表合并成一个有序升序线形表答案在请化大学严锐敏《数据结构第二版》第二章例题，数据结构当中，这个叫做：两路归并排序Linklist*unio(Linklist*p,Linklist*q){linklist*R,*pa,*qa,*ra;pa=p;qa=q;R=ra=p;while(pa-next!=NULL&&qa-next!=NULL){if(pa-dataqa-data){ra-next=qa;qa=qa-next;}else{ra-next=pa;pa=pa-next;}}if(pa-next!=NULL)ra-next=pa;if(qa-next!=NULL)ra-next==qa;returnR;}2.单连表的建立，把'a'--'z'26个字母插入到连表中，还要打印！node*p=NULL;node*head=(node*)malloc(sizeof(node));head-next=NULL;p=head;intlongth='a'-'z';inti;while(i=longth){node*temp;temp=(node*)malloc(sizeof(node));temp-data=i+'a';temp-next=NULL;p=temp;p-next=p;i++;}returnhead;print(head);3、约瑟夫环：约瑟夫环问题的一种描述是：编号为1.2.3…….n的n个人按顺时针方向围坐一圈，每人手持一个密码（正整数），开始任意选一个整数作为报数上限值，从第一个人开始顺时针自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他顺时针下一个人开始重新从1开始报数，如此下去直到所有的人全部都出列为止。试设计程序实现。要求：利用循环链表存储结构模拟此过程，按照出列的顺序打印各人的编号。测试数据：m的值初始为20：密码3，1，7，2，4，8，4。正确的结果：6，1，4，7，2，3，5。提示：程序运行后首先要求用户指定初始报数上限。然后读取各人的密码。设n30******算法思想：利用循环链表*************问题的规模是n个人，每次杀掉第m******个人,n和m由用户输入,程序输出最后******一个活着的人的编号*************/#includeiostreamusingnamespacestd;/*****约瑟夫问题的节点*******/typedefstructnode{intnumber;node*next;}yuesefu_node;/**********建立n个人的循环链表*******/yuesefu_node*create_chink(intn){yuesefu_node*head;//头指针yuesefu_node*p=newyuesefu_node;//p是第一个约瑟夫节点head=p;p-number=1;p-next=NULL;inti=2;while(i=n){yuesefu_node*q=newyuesefu_node;//新增一个约瑟夫节点q-number=i;if(i==n){q-next=head;}else{q-next=NULL;}p-next=q;p=q;i++;}returnhead;}voidout_chink(yuesefu_node*head){yuesefu_node*p=head;while(p-next!=head){coutp-number;p=p-next;}coutp-numberendl;}voidkill_out(yuesefu_node*head,intn,intm){if(nm){cout************************endl;cout最后活着的人的编号为:;out_chink(head);return;}yuesefu_node*p=head;intcount=1;while(countm-1){p=p-next;count++;}yuesefu_node*p_pre=p;//记住要删除节点的前一个指针p=p-next;cout本次杀掉的人的编号为：p-numberendl;p_pre-next=p-next;delete(p);head=p_pre-next;//指定刚被杀的人的下一个人为下一轮的第一个cout本轮后活着的人的编号为:;out_chink(head);kill_out(head,n-1,m);}voidmain(){intn,m;coutpleaseinputn和m:endl;cinnm;yuesefu_node*head=create_chink(n);kill_out(head,n,m);}4、二叉树的遍历及实现所谓前根遍历，就是根结点最先遍历，其次左子树，最后右子树。1．递归遍历前根遍历二叉树的递归遍历算法描述为：若二叉树为空，则算法结束;否则（1）输出根结点；（2）前根遍历左子树;（3）前根遍历右子树;算法如下:voidpreorder(bitree*root){bitree*p;p=root;if(p!=NULL){coutp-data;preorder(p-lchild);preorder(p-rchild);}}2．非递归遍历利用一个一维数组作为栈，来存储二叉链表中结点，算法思想为：从二叉树根结点开始，沿左子树一直走到末端(左孩子为空)为止，在走的过程中，访问所遇结点，并依次把所遇结点进栈，当左子树为空时，从栈顶退出某结点，并将指针指向该结点的右孩子。如此重复，直到栈为空或指针为空止。算法如下：voidpreorder1(bitree*root){bitree*p,*s[100];inttop=0;//top为栈顶指针p=root;while((p!=NULL)||(top0)){while(p!=NULL){coutp-data;s[++top]=p;p=p-lchild;}p=s[top--];p=p-rchild;}}中根遍历所谓中根遍历，就是根在中间，先左子树，然后根结点，最后右子树。1．递归遍历中根遍历二叉树的递归遍历算法描述为：若二叉树为空，则算法结束；否则⑴中根遍历左子树;⑵输出根结点;⑶中根遍历右子树。算法如下:voidinorder(biteee*root){bitree*p;p=root;if(p!=NULL){inorder(p-lchild);coutp-data;inorder(p-rchild);}}2．非递归遍历同样利用一个一维数组作栈，来存贮二叉链表中结点，算法思想为：从二叉树根结点开始，沿左子树一直走到末端(左孩子为空)为止，在走的过程中，把依次遇到的结点进栈,待左子树为空时,从栈中退出结点并访问,然后再转向它的右子树。如此重复，直到栈空或指针为空止。算法如下:voidinorder1(bitree*root){bitree*p,*s[100];//s为一个栈inttop=0;p=root;while((p!=NULL)||(top0)){while(p!=NULL){s[++top]=p;p=p-lchild;}p=s[top--];coutp-data;p=p-rchild;}}后根遍历所谓后根遍历，就是根在最后，即先左子树，然后右子树，最后根结点。1．递归遍历后根遍历二叉树的递归遍历算法描述为：若二叉树为空，则算法结束;否则（1）后根遍历左子树:（2）后根遍历历子树;（3）访问根结点。算法如下:voidpostorder(bitree*root){bitree*p;p=root;if(p!=NULL){postorder(p-lchild);postorder(p-rchild);coutp-data;}}2．非递归遍历利用栈来实现二叉树的后序遍历要比前序和中序遍历复杂得多，在后序遍历中，当搜索指针指向某一个结点时，不能马上进行访问，而先要遍历左子树，所以此结点应先进栈保存，当遍历完它的左子树后，再次回到该结点，还不能访问它，还需先遍历其右子树,所以该结点还必须再次进栈，只有等它的右子树遍历完后，再次退栈时，才能访问该结点。为了区分同一结点的两次进栈，引入一个栈次数的标志，一个元素第一次进栈标志为0，第二次进标志为1，并将标志存入另一个栈中，当从标志栈中退出的元素为1时，访问结点。算法如下：voidpostorder1(bitree*root){bitree*p,*s1[100];ints2[100],top=0,b;p=root;//s1栈存放结点,s2栈存放进栈标志do{while(p!=NULL){s1[top]=p;s2[top++]=0;//第一次进栈标志为0p=p-lchild;}if(top0){b=s2[--top];p=s1[top];if(b==0){s1[top]=p;s2[top++]=1;//第二次进栈标志为1p=p-rchild;}else{coutp-data;p=NULL;}}}while(top0);}另外，在编译原理中，有用二叉树来表示一个算术表达式的情形。在一棵二叉树中，若用操作数代表树叶，运算符代表非叶子结点，则这样的树可以代表一个算术表达式。若按前序、中序、后序对该二叉树进行遍历，则得到的遍历序列分别称为前缀表达式(或称波兰式)、中缀表达式、后缀表达式(递波兰式)。具体参见图6-12。图6-12所对应的前缀表达式：-*abc。图6-12所对应的中缀表达式：a*b-c。图6-12所对应的后缀表达式：ab*c-。二叉树所对应的遍历序列可以通过递归算法得到，也可以通过非递归算法得到。但有时要求直接写出序列，故我们可以用右图表示图6-12的遍历序列。从二叉树的三种递归遍历算法可以知道，三种遍历算法不同之处在于访问根结点和遍历左、右子树的顺序不同，若递归算法中去掉与递归无关的语句--访问根结点，则三个遍历算法完全相同。于是对于二叉树的遍历，可以看成是从根结点出发，往左子树走，若左子树为空，返回，再进入右子树，右子树访问完后，再返回根结点。这样一来每个结点都被访问三次，若将按顺序第一次访问的结点排列起来，则得到该二叉树的先序序列，第二次访问的结点排列起来，则得到该二叉树的中序序列，第三次访问的结点排列起来，则得到该二叉树的后序序列。对于上图，第一次访问到的结点用△表示,第二次访问到的结点用○表示,第三次访问的结点用□表示,按虚线顺序将所有△排列,则得到先序序列为-*abc,将所有○排列起来则得到中序序列为a*b-c,将所有□排列起来则得到后序序列ab*c-。C语言面试笔试题(ZZ)1.用预处理指令#define声明一个常数，用以表明1年中有多少秒（忽略闰年问题）#defineSECONDS_PER_YEAR(60*60*24*365)UL我在这想看到几件事情：1).#define语法的基本知识（例如：不能以分号结束，括号的使用，等等）2).懂得预处理器将为你计算常数表达式的值，因此，直接写出你是如何计算一年中有多少秒而不是计算出实际的值，是更清晰而没有代价的。3).意识到这个表达式将使一个16位机的整型数溢出-因此要用到长整型符号L,告诉编译器这个常数是的长整型数。4).如果你在你的表达式中用到UL（表示无符号长整型），那么你有了一个好的起点。记住，第一印象很重要。2.写一个“标准”宏MIN，这个宏输入两个参数并返回较小的一个。#defineMIN(A,B)((A)=(B)(A):(B))这个测试是为下面的目的而设的：1).标识#define在宏中应用的基本知识。这是很重要的，因为直到嵌入(inline)操作符变为标准