阅读以下说明和流程图,将应填入(n)处的字句写在对应栏内。 【说明】 已知头指针分别为La和lb的有序单链表,其数据元素都是按值非递减排列。现要归并La和Lb得到单链表Lc,使得Lc中的元素按值非递减排列。程序流程图如下所示:

admin2010-01-15  30

问题 阅读以下说明和流程图,将应填入(n)处的字句写在对应栏内。
    【说明】
   已知头指针分别为La和lb的有序单链表,其数据元素都是按值非递减排列。现要归并La和Lb得到单链表Lc,使得Lc中的元素按值非递减排列。程序流程图如下所示:
  

选项

答案(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。
转载请注明原文地址:https://kaotiyun.com/show/JBjZ777K
0

最新回复(0)