程序员模拟试题下午试卷答案

程序员考试模拟试题2下午●试题一阅读下列说明和流程图，将应填入(n)处的语句写在答题纸的对应栏内。【说明】下列流程图用于从数组K中找出一切满足：K(I)+K(J)=M的元素对(K(I)，K(J))(1≤I≤J≤N)。假定数组K中的N个不同的整数已按从小到大的顺序排列，M是给定的常数。【流程图】此流程图1中，比较K(I)+K(J)∶M最少执行次数约为(5)。图1●试题一【答案】(1)≥(2)(3)I+l-I(4)J-1-J(5)「N／2」【解析】该算法的思路是：设置了两个变量I和J，初始时分别指向数组K的第一个元素和最后一个元素。如果这两个元素之和等于M时，输出结果，并这两个指针都向中间移动；如果小于M，则将指针I向中间移动(因为数组K已按从小到大的顺序排列)；如果大于M，则将指针J向中间移动(因为数组K已按从小到大的顺序排列)。当I≥J时，说明所有的元素都搜索完毕，退出循环。根据上面的分析，(1)、(2)空要求填写循环结束条件，显然，(1)空处应填写≥，(2)空处应填写。这里主要要注意I=J的情况，当I=J时，说明指两个指针指向同一元素，应当退出循环。(3)空在流程图有两处，一处是当K(I)+K(J)=M时，另一处是当K(I)+K(J)M时，根据上面分析这两种情况都要将指针I向中间移动，即I+1-I。同样的道理，(4)空处应填写J-1-J。比较K(I)+K(J)：M最少执行次数发生在第1元素与第N个元素之和等于M、第2元素与第N-1个元素之和等于M、……，这样每次比较，两种指针都向中间移动，因此最小执行次数约为N-2。●试题二阅读下列函数说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。【说明】函数print(BinTreeNode*t；DateType＆x)的功能是在二叉树中查找值为x的结点，并打印该结点所有祖先结点。在此算法中，假设值为x的结点不多于一个。此算法采用后序的非递归遍历形式。因为退栈时需要区分右子树。函数中使用栈ST保存结点指针ptr以及标志tag，Top是栈顶指针。【函数】voidprint(BinTreeNode*t；DateType＆x){stackST；inti，top；top=0；∥置空栈while(t!=NULL＆＆t-data!=x‖top!=0){while(t!=NULL＆＆t-data!=x){∥寻找值为x的结点(1)；ST［top］．ptr=t；ST［top］．tag=0；(2)；}if(t!=Null＆＆t-data==x){∥找到值为x的结点for(i=1；(3)；i＋＋)printf(％d，ST［top］．ptr-data)；}else{while((4))top--；if(top0){ST［top］．tag=1；(5)；}}}●试题二【答案】(1)top＋＋(2)t=t-leftChild(3)i=top(4)top0＆＆ST［top］．tag=1(5)t=ST［top］．ptr-rightChild【解析】这个程序是一个典型二叉树后序遍历非递归算法的应用。算法的实现思路是：先扫描根结点的所有左结点并入栈；当找到一个结点的值为x，则输入出栈里存放的数据，这些数据就是该结点所有祖先结点；然后判断栈顶元素的右子树是否已经被后序遍历过，如果是，或者右子树为空，将栈顶元素退栈，该子树已经全部后序遍历过；如果不是，则对栈顶结点的右子树进行后序遍历，此时应把栈顶结点的右子树的相结点放入栈中。再重复上述过程，直至遍历过树中所有结点。(1)、(2)空年在循环就是扫描根结点的所有左结点并入栈，根据程序中的栈的定义，栈空时top=0，因此在入栈时，先将栈顶指针加1，因此(1)空处应填写top＋＋或其等价形式，(2)空是取当前结点的左子树的根结点，因此应填写t=t-leftChild。(3)空所在循环是处理找到值为x的结点，那么该结点的所有祖先结点都存放在栈中，栈中的栈底是二叉树的根，而栈顶元素是该结点的父结点，因此，(3)空处应填写i=top。(4)空所在循环是判断栈顶元素的右子树是否已经被后序遍历过，如果是，或者右子树为空，将栈顶元素退栈，这里要填写判断条件。tag=0表示左子树，tag=1表示右子树，因此，(4)空处应填写top0&&ST［top］．tag=1。(5)空所在语句块是处理栈顶元素的右子树没有被后序遍历情况，则将右子树入栈，因此(5)空处应填写t=ST［top］．ptr-rightChild。●试题三阅读下列函数说明和C函数，将应填入(n)处的字句写在答题纸的对应栏内。【说明】函数DelA_InsB(LinkedListLa，LinkedListLb，intkey1，intkey2，intlen)的功能是：将线性表A中关键码为key1的结点开始的len个结点，按原顺序移至线性表B中关键码为key2的结点之前，若移动成功，则返回0；否则返回-1。线性表的存储结构为带头结点的单链表，La为表A的头指针，Lb为表B的头指针。单链表结点的类型定义为typedefstructnode{intkey；structnode*next；}*LinkedList；【函数】intDelA_InsB(LinkedListLa，LinkdeListLb，intkey1，intkey2，intlen){LinkedListp，q，s，prep，pres；intk；if(!La-＞next||!Lb-＞next||len＜=0)return-1；p=La-＞next；prep=La；while(p&&p-＞key!=key1){/*查找表A中键值为key1的结点*/prep=p；p=p-＞next；}if(!p)return-1；/*表A中不存在键值为key1的结点*/q=p；k=1；while(q&&(1)){/*在表A中找出待删除的len个结点*/(2)；k++；}if(!q)return-1；/*表A中不存在要被删除的len个结点*/s=Lb-＞next；(3)；while(s&&s-＞key!=key2){/*查找表B中键值为key2的结点*/pres=s；s=s-＞next；}if(!s)return-1；/*表B中不存在键值为key2的结点*/(4)=q-＞next；/*将表A中的len个结点删除*/q-＞next=(5)；pres-＞next=p；/*将len个结点移至表B*/return0；}●试题三【答案】(1)klen(2)q=q-next或q=(*q).next(3)pres=Lb(4)prep-next或(*prep).next(5)s或pres-next或(*pres).next【解析】(1)此处while循环应当循环至k等于len结束，所以应填入k1en。(2)此处语句表示链表前进一个结点，应填入q=q-next或q=(*q).next。(3)此处语句为指针pres赋初值，使他指向s的上一结点。(4)修改指针prep，使prep指向q的下一结点。(5)此处语句为修改指针q，q指向s或者pres的下一结点，达到将A中的len个结点删除的目的。●试题四阅读以下说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。【说明】将一正整数序列{K1，K2，…，K9}重新排列成一个新的序列，新序列中，比K1小的数都在K1的前面(左面)，比K1大的数都在K1的后面(右面)，最后调用writeDat()函数的新序列输出到文件out．dat中。在程序中已给出了10个序列，每个序列有9个正整数，并存入数组a［10］［9］中，分别求出这10个新序列。例：序列{6，8，9，1，2，5，4，7，3}经重排后成为{3，4，5，2，1，6，8，9，7}【函数】#includestdio．h#includeconio．hvoidjsValue(inta［10］［9］){inti，j，k，n，temp；intb［9］；for(i=0；i10；i＋＋){temp=a［i］［0］；k=8；n=0；for(j=8；j=0；j--){if(tempa［i］［j］)(1)=a［i］［j］；if(tempa［i］［j］)(2)=a［i］［j］；if(temp=a［i］［j］)(3)=temp；}for(j=0；j9；j＋＋)a［i］［j］=b［j］；}}voidmain(){inta［10］［9］={{6，8，9，1，2，5，4，7，3}，{3，5，8，9，1，2，6，4，7}，{8，2，1，9，3，5，4，6，7}，{3，5，1，2，9，8，6，7，4}，{4，7，8，9，1，2，5，3，6}，{4，7，3，5，1，2，6，8，9}，{9，1，3，5，8，6，2，4，7}，{2，6，1，9，8，3，5，7，4}，{5，3，7，9，1，8，2，6，4}，{7，1，3，2，5，8，9，4，6}}；inti，j；(4)；for(i=0；i10；i＋＋){for(j=0；j9；j＋＋){printf(％d，a［i］［j］)；if((5))printf(，)；}printf(＼n)；}getch()；}●试题四【答案】(1)b［k--］(2)b［n＋＋］(3)b［n］(4)jsValue(a)(5)j=7【解析】在主函数中先要调用函数jsValue()对数组a进行处理，所以(4)空应填入jsValue(a)。然后输出数组元素，同一行的元素之间用逗号分隔，所以(5)空应填入j=7。函数jsValue()是将数组按题目要求进行排序。通过观察发现处理后的数组中元素的顺序与原来的顺序相反，并且每一行中没有与第一个数相同的数，所以是从后往前处理，也就是将每组从最后往前倒序逐个同第一个数比较，比它大的就放到临时数组b中的最后，比它小的就放到临时数组b中的最前面，以次类推，所以(1)空应填入b［k--］，(2)空应填入b［n＋＋］，(3)空应填入b［n］。最后将b数组赋给a数组。●试题五阅读以下应用说明、属性设置及VisualBasic程序代码，将应填入(n)处在字句写在答题纸的对应栏内。【说明】本应用程序的运行窗口如图2所示。只要用户单击闪烁按钮，文字欢迎光临就会以0．3秒消失、0．3秒显示反复进行闪烁；单击停止按钮时，闪烁停止，恢复图示的初态。在开发过程中，需要设置的属性如表1所示。在开发过程中，需要编写的程序代码如下：【程序】PrivateSubCmdF_Click()Timer1．(3)=TrueLabe1．Visible=FalseEndSubPrivateSubTimer1_Timer()(4)=notLabel.VisibleEndSubPrivateSubCmdT_Click()Timer1．Enabled=(5)Labe1．Visible=trueEndSub●试题五【答案】(1)false(2)300(3)Enabled(4)Label.Visible(5)false【解析】单击闪烁按钮后，文字才开始闪烁，所以初始时定时器并未启动，(1)处应填false。定时器的时间间隔为0.3秒，即300毫秒，所以(2)处应填300(Interval属性的单位是毫秒)。(3)单击闪烁按钮后，应启动定时器，所以修改Timer1的Enable属性为True。(4)定时器到时的时候，应当使Label的是否可见属性(Visible)取反，所以(4)处应填Label.Visible。(5)单击停止按钮后，要停止定时器，所以应修改Timer1的Enable属性为false。●试题六阅读以下说明和C＋＋程序，将应填入(n)处的字句写在答题纸的对应栏内。【说明】设计一个类模板Sample用于对一个有序数组采用二分法查找元素下标。【C＋＋程序】#includeiostream．h#defineMax100∥最多元素个数templateclassTclassSample{TA［Max］：∥存放有序数序intn：∥实际元素个数publicSample(){}∥默