清华大学邓俊辉数据结构练习题1.pdfVIP

清华大学计算机系 数据结构与算法编程作业 截止时间：2011 年3 月20 日23:59 《数据结构》作业1 题目名称 摇奖 面试顺序 记分牌 地铁 代号 lottery interview scoreboard subway 分数 20 30 20 30 1 5 第 / 页 清华大学计算机系 数据结构与算法编程作业 截止时间：2011 年3 月20 日23:59 1 (lottery) 20 1 (lottery) 20 第11 题 摇奖((llootttteerryy)) 2200 分 【题目描述】 使用一家游戏厅的摇奖机，玩家可得到n 个随机整数（3 ≤ n ≤ 20000）。这些整数无序但有可能重 复，若其中存在三个整数A、B 和C 满足A + B = C，则参与摇奖的玩家就中奖，否则不中。请编写一 个尽可能高效的程序，对于摇号机给出的任意n 个数，判断摇奖玩家是否中奖。 【输入】 包含两行： 第一行为一个正整数n，代表本次摇奖所产生正整数的总数。 第二行包含以空格分隔的n 个正整数，为摇奖所产生的正整数随机序列。 【输出】 包含一行：如果中奖，则输出YES，否则输出NO 【样例输入】 【样例输出】 3 YES 1 2 3 【限制】 3 ≤ n ≤ 20,000，随机序列中的数字范围为1～2,147,483,647 2 5 第 / 页 清华大学计算机系 数据结构与算法编程作业 截止时间：2011 年3 月20 日23:59 2 (interview) 30 2 (interview) 30 第22 题 面试顺序((iinntteerrvviieeww)) 3300 分 【题目描述】 某公司在对应聘者做过一轮笔试后，从中选出成绩最高的N 人继续进行面试。在笔试中，每位应 聘者已被分配了一个32 位整数的ID，面试时将沿用这个ID。 为公平起见，组织者决定利用会议室外的圆桌，按以下方法“随机”确定面试顺序：第一个到达 的应聘者在圆桌周围任意选择一个位置坐下；此后到达的每位应聘者都从前一应聘者出发，沿逆时针 方向围圆桌走过m 人（前一应聘者算作走过的第1 人，同一人可经过多次），并紧邻第m 人右侧就座； 所有应聘者到齐后，从最后到达者出发，绕圆桌以顺时针方向为序进行面试。 图 实例： ， 1. N = 5 m = 3 这里假定应聘者到达的时刻互异，且相对的就坐位置确定后，左、右两人之间总能插入一把