《初级程序员下午试题101》由会员分享，可在线阅读，更多相关《初级程序员下午试题101（8页珍藏版）》请在金锄头文库上搜索。
1、初级程序员下午试题-101(总分：150.00，做题时间：90分钟)、试题一(总题数：1,分数：15.00)流程图说明下列流程图用于从数组K中找出一切满足：K(I)+K(J)=M的元素对(K(I) ，K(J)(1 I J)解析：填空项1:(正确答案:V)解析：填空项1:(正确答案:1+1I)解析：填空项1:(正确答案:J-1J)解析：填空项1:(正确答案:N/2 )K的第一个元素和最后一;如果小于M则将指解析：解析本题算法的思路是：设置了两个变量 I和J，初始时分别指向数组 个元素。如果这两个元素之和等于 M时，输岀结果，并且这两个指针都向中间移动针I向中间移动(因为数组K已按由小到大的顺序排
2、列);如果大于M,则将指针J向中间移动(因为数组K 已按由小到大的顺序排列)。当I J时，说明所有的元素都搜索完毕，退岀循环。根据上面的分析，空(1)和空(2)要求填写循环结束条件，显然，空(1)处应填写“”，空(2)处应填写“V 这里主要要注意I=J的情况，当I=J时，说明两个指针指向同一元素，应当退岀循环。空在流程图中有两处，一处是当K(I)+K(J)=M 时，另一处是当 K(I)+K(J) V M时，根据上面分析这两种情况都要将指针I向中间移动，即“ I+1 -I”。同样的道理，空 (4)处应填写“J -1tJ”。比较“ K(I)+K(J):M ”最少执行次数发生在第1元素与第N个元素之
3、和等于 M第2元素与第N-1个元素之和等于M，这样每次比较，两种指针都向中间移动，因此最小执行次数约为“N/2”。、试题二(总题数：1，分数：15.00)1说明函数int circle(int n ，int d)判定正整数n的d进制表示形式是否是回文数。函数2.1int circle(int n,int d)int s=0,m=n;while (m)(1) ;m/=d;return (2 函数2.2说明函数int trans(unsigned n ，int d ，char s)将一个无符号整数转换为任意d进制数(2 d 16)s0=/0;return 0;(3) ;do(4) ;n/=d;wh
4、ile (n);for( (5) ); (s(j)=bufj!=/0;j+);return j;(分数：15.00 )填空项1:(正确答案：s=s*d+m%c)解析：填空项1:(正确答案：s=n)解析：填空项1:(正确答案：bufi=/0)解析：填空项1:(正确答案：buf-i=digitsn%d解析：填空项1:(正确答案：j=0 )解析：解析回文数就是顺着看和倒着看相同的数。例如，n=232，它的十进制表示回文数；n=27，它的二进制表示11011是回文数；n=851，它的十六进制表示 353是回文数。设判断是否为回文数的函数为 circle(int n，int d)，它有两个参数n和d。其
5、中n为要判定是否为回文数的整数，d指将n转成d进制表示。为判定n是否是d进制表示形式中的回文教，一种办法是：首先顺序译岀n的d进制的各位数字，然后把译岀的各位数字将低位当高位按d进制的转换方法译成一个整数，若n是回文数，则转换所得的整数应与n相等；否则，n不是回文数。求n整除d的余数，就能得到n的d进制数的最低位数字，重复上述步骤，直至n为0,依次得到n的d进制数表示的最低位至最高位数字。由各位数字取岀相应字符，就能得到n的d进制的字符串。三、试题三(总题数：1,分数：15.00)说明函数print (BinTreeNode *t; DateType&x)的功能是在二叉树中查找值为x的结点，并
6、打印该结点所有祖先结点。在此算法中，假设值为x的结点不多于一个。此算法采用后序的非递归遍历形式。函数中使用栈ST保存结点指针ptr以及标志tag，Top是栈顶指针。函数void print (BinTreeNode * t; DateType& x)stack ST;int i,top;top=0; /置空栈while (t ! =NULL & t- data ! =x | top ! =0)while (t!=NULL & t- data !=x)/寻找值为x的结点;ST top.ptr=t;STtop.tag=0;；if(t!=Null & t- data=x) / 找到值为 x 的结点
7、for(i=1; (3) ; i+)printf(%d, ST top.ptr- data);elsewhile( (4)top-;if(top 0)ST top .tag=1;(5) ;(分数：15.00 )填空项1:（正确答案：top+ )解析：填空项1:（正确答案：t=t- leftChild )解析：填空项1:（正确答案：i=top )解析：填空项1:（正确答案：top 0 & STtop.tag=1 )解析：填空项1:（正确答案：t=STtop.ptr- rightChild )解析：解析这个程序是一个典型二叉树后序遍历非递归算法的应用。算法的实现思路是：先扫描根结点的所有左结点并入
8、栈；当找到一个结点的值为 x时，则输入岀栈里存放的数据，这些数据就是该结点所有祖先结点；然后判断栈顶元素的右子树是否已经被后序遍历过，如果是，或者右子树为空，将栈顶元素退栈，该子树已经全部后序遍历过，如果不是，则对栈顶结点的右子树进行 后序遍历，此时应把栈顶结点的右子树的相应结点放入栈中。再重复上述过程，直至遍历过树中所有结点。空（1）和空（2）所在循环就是扫描根结点的所有左结点并入栈，根据程序中的栈的定义，栈空时top=0，因此在入栈时，先将栈顶指针加1，因此空 处应填写“ top+”或其等价形式，空（2）是取当前结点的左子树的根结点，因此应填写“ t=t - leftChild ”。空所在
9、循环是处理找到值为 x的结点，那么该结点的 所有祖先结点都存放在栈中，栈中的栈底是二叉树的根，而栈顶元素是该结点的父结点，因此，空（3）处应填写“i=top ”。空所在循环是判断栈顶元素的右子树是否已经被后序遍历过，如果是，或者右子树为 空，将栈顶元素退栈，这里要填写判断条件。tag=0表示左子树，tag=1表示右子树，因此，空（4）处应填写“top 0 & STtop.tag=1 ”。空（5）所在语句块是处理栈顶元素的右子树没有被后序遍历的情况，则将右子树入栈，因此空（5）处应填写“ t=STtop.ptr- rightChild ”。四、试题四（总题数：1,分数：15.00）说明下面的程序
10、是通过双链结构来查找学生的信息程序的一部分，即创建双向链表部分。函数#include #define N 10 typedef struct node char name 20;struct node *llink,*rlink;stud; /*双链表的结构定义*/*双链表的创建*/stud * creat (int n)stud *p,*h,*s;int i;if (h= (stud *) malloc (sizeof (stud) =NULL) printf (cannot find space! /n);exit (0);h- name0=/0;h- llink=NULL;h- rlin
11、k=NULL;p=h;for(i=0; i name);(2) ;(3) ;p=s ;；(5);return (h);（分数:15.00)填空项1:（正确答案：p- rlink=s)解析：填空项1:（正确答案：s- llink=p)解析：填空项1:（正确答案：s- rlink=NULL )解析：填空项1:（正确答案：h- llink=s)解析：填空项1:（正确答案：p- rlink=h)解析： 解析 双向链表有两条方向不同的链，即每个结点中除 next 域存放后继结点地址外，还增加一个 指向其直接前驱的指针域 prioro 这样在查找过程中， 当指针处在中间某个结点时不仅可以像单链表那样向 后
12、查找，而且可以返回之前找过的结点。本题考察双向链表的构造，程序中首先构造了一个头结点，并将 头结点的左右指针都设为空；然后构造新的结点，让头结点的右指针指向该结点，即空 填p- rlink=s ,该结点的左指针指向头结点，即空(2)填s- llink=p ，以此类推，最后将头结点的左指针指向最后一个结点，最后一个结点的右指针指向头结点，形成一个环，即空和空(5)分别填入h- llink=s 和p- rlink=h五、试题五 (总题数： 1，分数： 15.00) 说明 下面程序是一个小型公司工资管理的程序。该公司主要有 4 类人员：经理、兼职技术人员、销售员和销售 经理。基类为 employee，由它派生出 technician 类，manager类，salesman 类，最后由 manager类和 salesman 类派生出 salesmanager 类。月工资计算办法是：经理拿固定月薪 8000； 兼职技术人员按每小时 1 00元领取 月薪； 销售按当月销售额的 4%提成； 销售经理既拿固定月工资也领取销售提成，固定月工资 5000 元，销 售提成为所管辖部门当月销售总额的0.5%。C+程序#include #include cla
