初级程序员下午试题-56.pdf

初级程序员下午试题-56

(总分：90.00，做题时间：90分钟)

一、{{B}}试题一{{/B}}(总题数：1，分数：15.00)

1.【说明】已知头指针分别为La和lb的有序单链表，其数据元素都是按值非递减排列。现要归并La和

Lb得到单链表Lc，使得Lc中的元素按值非递减排列。程序流程图如下所示：

（分数：15.00）

__________________________________________________________________________________________

正确答案：()

解析：(1)pa-＞data＜=pb-＞data(2)pc-＞next=pa(3)pc=pb(4)pb=pb-＞next(5)pc-＞next=pa?pa:pb

[分析]本题考查程序流程图和有序链表的归并。题目要求我们归并头指针分别为La和Lb的有序单链表，

组成一个新的有序单链表Lc，而Lc又是指向La的。首先，我们来了解一下单链表的结构。单链表中一般

有两个域，一个是数据域，用来存放链表中的数据；另一个是指针域，用来存放指向下个结点的指针。其

归并的过程应该是先比较链表La和Lb中第一个元素，将较小的从其链表中取出放到k中，再取下一个结

点的值去比较，重复这个过程，直到一个链表被全部取完，再将另一个链表剩下的部分连接到Lc后面即可。

下面，我们来看程序流程图的内容。首先是用两个指针变量pa和pb分别指向La和Lb的当前待比较插入

的结点，而pc指向Lc表中当前最后一个结点。再下面是一个条件判断语句，其作用是判断链表La和Lb

是否为空，如果有一个为空，只要将另一个链表剩下的部分连接到Lc后面，程序应该就可以结束了。第

(1)空是条件判断语句的条件，根据我们上面的分析，再结合流程图下面的内容，我们可以知道，这个条件

语句的作用是比较当前待插入的两个值的大小，而指针变量pa和pb分别指向La和Lb的当前待比较插入

的结点，因此，此空的答案为pa-＞data＜=pb-＞data。第(2)空是在条件为真的情况下执行的语句，如

果条件判断为真，应该将pa所指结点连接到pc所指结点后面，因此，pc所指结点的指针域应该存放pa

所指结点的地址。所以，此空的答案为pc-＞next=pa。第(3)空和第(4)空都是在条件为假的情况下执行

的语句，如果条件为假，说明pb所指结点的值小于pa所指结点的值，应该将pb所指结点连接到pc所指

结点后面，图中已经实现这一功能，要我们完成的是在插入后的后继工作。由于pc指向的是Lc表中当前

最后一个结点，在插入一个结点后，要修改pc的值。在将pb所指结点插入后，链表中的最后一个结点就

是pb所指结点，第(3)空的答案应该为pc=pb。执行完这些功能后，指针pb应该要往后移动，即指向下一

个结点，第(4)用来完成这个功能，所以答案为pb=pb-＞next。在前面，我们已经讲到如果链表La和Lb

有一个为空，只要将另一个链表剩下的部分连接到Lc后面即可。第(5)空就是用来完成这个功能的，但我

们不知道具体是哪个链表为空，还需要判断，因此，此空答案为pc-＞next=pa?pa:pb。

二、{{B}}试题二{{/B}}(总题数：1，分数：15.00)

2.【程序2.1说明】已知一个排好序的数组，现输入一个数，要求按原来的顺序规律，将它插入到数组中。

【程序2.1】#include＜stdioh＞＞

输入输入已已经经排排好好序的数列：序的数列：＜＜输入输入输入要要要插入插入插入的数：的数：的数：

＜N;i++)if(x＜a[i]){{{U}}(1){{/U}}break;}for(i=N-1;i

＞=p;i--){{U}}(2){{/U}}{{U}}(3){{/U}}for(i=0;i＜＜【程

序2.2说明】本程序用变量count统计文件中字符的个数。【程序2.2】#include