中大计算机课程实践考核（二）数据结构上机考试答案

数据结构是计算机科学中的核心课程，它探讨了如何有效地存储和操作数据。在这个中大计算机本科课程实践考核中，有三个主要的知识点被涵盖：递归算法、Josephus问题的解决以及顺序表与单链表的操作。 递归算法在样题1中得到了体现。在计算a+b和a-b时，不允许直接使用加减运算符或循环语句，而是通过递归调用函数`succ()`和`pred()`来实现。递归是一种函数在其定义中调用自身的技术。在这个例子中，`add(a,b)`和`sub(a,b)`函数通过比较b是否为0来决定递归的终止条件。当b为0时，返回a（即a+b或a-b的结果）。否则，根据b的正负，递归调用自身并使用`succ()`或`pred()`来改变操作数。递归的关键在于理解和设定正确的基础情况以及递归步骤。 接下来，样题2涉及到了Josephus问题，这是一个经典的理论问题。Josephus问题考察的是在特定规则下，如何确定人的出列顺序。在这个问题中，n个人围坐一圈，从第s个人开始报数，每数到m的人就会出列。这个问题可以通过链表等数据结构来解决，因为链表可以方便地插入和删除元素。在这个程序中，数组A用于存储人，当某个人出列时，将对应的数组元素设为-1。通过循环和模运算，模拟报数过程，直到所有人出列。 样题3涉及了两种基本的数据结构：顺序表和单链表，并讨论了它们的操作，特别是逆置。顺序表通常是指数组，可以直接访问任意位置的元素，而单链表则由一系列节点组成，每个节点包含数据和指向下一个节点的指针。在程序中，先用顺序表存储10个输入的整数，然后用单链表实现相同的操作。单链表的逆置是链表操作的一个常见问题，通过遍历链表，交换相邻节点的顺序，可以达到逆置的效果。 这些实践考核题目涵盖了数据结构的基本概念，包括递归算法、链表操作和数组处理，这些都是编程和算法设计中的关键技能。理解并熟练掌握这些知识点对于任何IT专业的学生来说都是至关重要的，因为它们构成了许多复杂算法的基础。