软件所笔试题：巧解谜题与数据结构优化

2009年的软件所笔试题涉及到了两个有趣的逻辑和算法问题，让我们逐一解析： 1. **数字与字母对应关系确定问题** 这是一道考察空间思维和推理能力的问题。在一座100层的大楼中，有21根电线线头，线头编号1到21，与楼顶的字母A到U相对应，但具体对应关系未知。考生需要使用一个灯泡、电池和短电线，在一次上下楼的行动中找出这个对应。解题策略是采用分组和逐步排除的方法： - 首先，将楼下的线头两两配对，形成如(1,2)(3,4)…(19,20)。 - 然后上楼检查，根据灯泡状态确定哪些组合是存在的，比如假设A对应BC…U。 - 接着，确定21对应的字母，例如如果21对应U，那么将剩下的线头重新排列，形成AB-CD-E…T-U。 - 再次下楼测试，通过线头之间的相互关系，可以逐步确定每条线头的具体对应。例如，如果18与21相连，那么根据已知的对应关系，可以推断出T的值。 2. **考试通过人数计算问题** 第二题考察概率和组合数学的应用。有100人参加考试，5道题的正确率分别为80人、92人、86人、78人、74人。题目要求答对3道或更多的题才能通过。通过最优化假设法求解： - 假设所有人都答对5题，未通过的人只答对2题。设通过人数为x，未通过人数为100-x。 - 根据题面条件列出等式：5x + 2(100-x) = 80 + 92 + 86 + 78 + 74。 - 解得x = 70，这意味着至少有70人通过了考试，即使是最少的情况。 3. **改进栈数据结构添加min()功能** 对于Stack（栈）数据结构，要求在常数时间复杂度O(1)内实现min()功能，并保持push()和pop()操作的时间复杂度也都是O(1)。这通常需要使用辅助数据结构。一种可能的解决方案是使用两个栈： - s: 主栈，用于存储元素，遵循栈的先进后出原则。 - smin: 辅助栈，专门存储当前主栈中的最小值。 - push(x)操作： - 如果主栈为空，直接push x到s和smin； - 否则，push x到s，比较x与smin顶部元素的大小，如果x更小，同时将x压入smin。 - pop()操作： - 主栈弹出元素的同时，检查smin是否为空。若为空，说明smin始终包含主栈的最小值；若不为空，判断被弹出元素是否小于smin.top，小于则将smin.pop()。 - min()操作：直接返回smin栈顶元素，时间复杂度为O(1)。 通过这两个问题，可以看出2009年软件所的笔试题不仅考察基础的编程技能，还强调逻辑分析、空间思维以及算法优化的能力。