2. 计算机
  3. 阅读以下说明和C函数，填补C函数中的空缺(1)～(5)，将解答写在答题纸的对应栏内。 【说明】 约瑟夫问题如下所述：有n个人(编号为1～n)围成一圈，从第一个人开始，按照顺时针方向从1开始计数到m(即数到第m个人)，让其出圈，然后再从其顺时

阅读以下说明和C函数，填补C函数中的空缺(1)～(5)，将解答写在答题纸的对应栏内。 【说明】 约瑟夫问题如下所述：有n个人(编号为1～n)围成一圈，从第一个人开始，按照顺时针方向从1开始计数到m(即数到第m个人)，让其出圈，然后再从其顺时

admin2013-07-03  40
问题 阅读以下说明和C函数，填补C函数中的空缺(1)～(5)，将解答写在答题纸的对应栏内。
    【说明】
    约瑟夫问题如下所述：有n个人(编号为1～n)围成一圈，从第一个人开始，按照顺时针方向从1开始计数到m(即数到第m个人)，让其出圈，然后再从其顺时针方向的下一个人开始，依次计数到m并让其出圈，重复这个过程，直到所有人都出圈，试给出出圈者的顺序。
    以n=5，m=3为例，其中圈顺序为3，1，5，2，4，过程如下图所示。
   
下面的函数Joseph()在单向循环链表表示的基础上输出出圈的过程。n为5时的单向循环链表结构如下图所示。
   
链表的结合类型定义如下：
Typedef struct Node
{    int no；
    struct Node*next：
}node，*LinkList；
函数Joseph(LinkList tail，int n，int m)的处理思路如下：
(1)用k计数，每次都从0开始，当计数到m一1时结束本次计数；
(2)通过指针p查找出圈者所对应的结点，当K的值等于m一1时，P应指向出圈者对应结点的前驱结点；
(3)通过删除结点表示出圈处理；
(4)当m大于圈中剩余人数时，为了避免重复计数，用模运算修改m的值；
(5)计数和删除操作完成后再恢复m的原值。
   【C函数】
    void Joseph(LinkList tail，int n，int m)
    {
    LinkList p，q；
    int k，i，old_m=m；
    p=tail；
    for(i=n；i＞l；i- -)    ／*i表示圈中剩余人数*／
    {
        m=m％i；           ／*避免重复计数*／
    if(0=m)  m=  (1)  ；
    k=0；
    while(k＜  (2)  )
    {  (3)  ；k++；}
    printf(”％d＼n”，  (4)  )；    ／*输出出圈者的编号*／
    q=p->next；
      (5)  =q->next；                ／*删除出圈者对应的结点*／
    free(q)；
    M=old_m；
    }
    printf(“％d＼n”，p->No)；
    }
选项
答案(1)i (2)m—1 (3)p=p->next (4)p->next->No (5)p->next
解析 本题考查数据结构中经典的约瑟夫问题。题目中涉及的考点主要有链表运算和程序逻辑，分析程序时首先要明确各个变量所其的作用和代表的含义，并按照语句组分析各段代码的功能，从而完成空缺处的代码填写。
    根据题目中Joseph函数处理思路(4)的描述，m=m％i语句可避免计数过程重复。但这里需要考虑一种特殊情况，即m为0的情况。此时对应的情况应该是正好要数到目前所在位置的前一个人。由于单向循环链表的指针特点，还需要逐个结点进行遍历，则当罔中还剩下i个人时，最多计数到i。因此，(1)处应填入i。
    程序段接下来的while循环用于在单循环链表中扫描结点并完成计数。由于计数器k从0开始计数，冈此while循环得循环条件应为k    (3)处用于实现链表各结点的遍历。由于在链表中利用指针p指向结点并进行遍历，因此，(3)处应填入p=p一≥>next。
    (4)处用于实现输出出圈者的编号。根据题目中Jo-seph函数处理思路(2)的描述，当k的值等于m一1时，p应指向出圈者对应结点的前驱结点。因此，p->next所指向的结点是要被删除的结点，其编号为p->next->No。因此，(4)处应填入p->next->No。
    (5)处用于实现删除出圈者对应的结点。删除p所指结点的后继结点的处理思路为：使指针q指向p所指结点的后继结点，即q=p->next，然后使p所指结点的next指针指向(1所指结点的后继结点，即p->next=q->next，这是典型的在链表中删除结点的方法。因此，(5)处应填入p->next。
转载请注明原文地址:https://kaotiyun.com/show/lnjZ777K
本试题收录于： 程序员下午应用技术考试题库软考初级分类
0

程序员下午应用技术考试

软考初级

相关试题推荐
随机试题
最新回复(0)