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

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

ID:38283680

大小:193.74 KB

页数:5页

时间:2019-05-29

清华大学邓俊辉数据结构练习题1_第1页
清华大学邓俊辉数据结构练习题1_第2页
清华大学邓俊辉数据结构练习题1_第3页
清华大学邓俊辉数据结构练习题1_第4页
清华大学邓俊辉数据结构练习题1_第5页
资源描述:

《清华大学邓俊辉数据结构练习题1》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、清华大学计算机系数据结构与算法编程作业截止时间:2011年3月20日23:59《数据结构》作业1题目名称摇奖面试顺序记分牌地铁代号lotteryinterviewscoreboardsubway分数20302030第1/5页清华大学计算机系数据结构与算法编程作业截止时间:2011年3月20日23:59第1题摇奖(lottery)20分【题目描述】使用一家游戏厅的摇奖机,玩家可得到n个随机整数(3≤n≤20000)。这些整数无序但有可能重复,若其中存在三个整数A、B和C满足A+B=C,则参与摇奖的玩家就中奖,否则不中。请编写一个尽可能高效的程序,对于摇号机给出的任意n个数,判断摇奖玩家是

2、否中奖。【输入】包含两行:第一行为一个正整数n,代表本次摇奖所产生正整数的总数。第二行包含以空格分隔的n个正整数,为摇奖所产生的正整数随机序列。【输出】包含一行:如果中奖,则输出YES,否则输出NO【样例输入】【样例输出】3YES123【限制】3≤n≤20,000,随机序列中的数字范围为1~2,147,483,647第2/5页清华大学计算机系数据结构与算法编程作业截止时间:2011年3月20日23:59第2题面试顺序(interview)30分【题目描述】某公司在对应聘者做过一轮笔试后,从中选出成绩最高的N人继续进行面试。在笔试中,每位应聘者已被分配了一个32位整数的ID,面试时将沿用

3、这个ID。为公平起见,组织者决定利用会议室外的圆桌,按以下方法“随机”确定面试顺序:第一个到达的应聘者在圆桌周围任意选择一个位置坐下;此后到达的每位应聘者都从前一应聘者出发,沿逆时针方向围圆桌走过m人(前一应聘者算作走过的第1人,同一人可经过多次),并紧邻第m人右侧就座;所有应聘者到齐后,从最后到达者出发,绕圆桌以顺时针方向为序进行面试。图1.实例:N=5,m=3这里假定应聘者到达的时刻互异,且相对的就坐位置确定后,左、右两人之间总能插入一把椅子。请采用链表结构编写一个程序,对于任给m及N个应聘者ID,确定对应的面试顺序。【输入】共包含两行:第一行包含两个正整数,以空格分隔,依次表示N

4、和m。第二行包含N个正整数,以空格分隔,从左至右依次表示先后到达的N个应聘者的ID。【输出】共一行:包括以空格分隔的N个正整数,分别表示顺次进行面试的应聘者的ID。注意,最后一个ID后面不应该输出空格。【样例输入】【样例输出】3210898910【限制】1≤N≤1,000,1≤m≤2*N第3/5页清华大学计算机系数据结构与算法编程作业截止时间:2011年3月20日23:59第3题记分牌(scoreboard)20分【题目描述】比赛中记分牌上的得分数,由标有数字0~9的10类卡片组合而成,例如得分225由两张标有2的卡片和一张标有5的卡片组合而成。然而,在一场比赛前,粗心的记分员只拿了包

5、含0在内的m类卡片(假定每类卡片数目无限)。为了不延误比赛,记分员决定用这m类卡片表示比赛分数,表示规则为:按从小到大的顺序,用第i个能以这m类卡片表示的十进制数代表得分i,其中i≥0。例如,若所带卡片只有{0,2,4,5}四类,则可组合成的十进制数从小到大分别为{0,2,4,5,20,22,24,25,40,42,44,…},依次分别对应于得分{0,1,2,3,4,5,6,7,8,9,10,…}。当这m类卡片所组合成数字的位数很多时,记分员自己也不知道到底现在分数是多少,请你编写程序帮助他/她计算准确的得分。【输入】包含三行:第一行为正整数m,表示目前可用数字卡片的种类数。第二行为m

6、个各不相同的一位阿拉伯数字,从小到大排列,以空格分隔,且其中肯定包含0。表示m种可用的卡片。第三行为积分排上的一个非负整数X,其所有数位均取自第二行给定的m个数字,且最高位非0。【输出】包含一行:一个十进制非负整数,对应于X所表示的十进制得分。【样例输入】【样例输出】47024727【限制】2≤m≤10,0≤X≤2,147,483,647第4/5页清华大学计算机系数据结构与算法编程作业截止时间:2011年3月20日23:59第4题地铁(subway)30分【题目描述】某地铁沿线共设N站,可分为U(地面式)、D(地下式)和C(复合式)三种类型。为避免单调,相邻地铁站的类型不能重复。同时,

7、由于地铁站所处环境和地质条件有所差异,每个站点按不同类型的建设成本也不尽相同。现给定各站点的三种建设成本,请计算出该地铁线的最低总造价。【输入】包含N+1行:第1行为一个正整数,表示地铁站的总数N。第2行到第N+1行分别包含用空格分隔的三个正整数U,D和C。其中第i+1行表示第i个地铁站按U、D或C类型的建设成本,1≤i≤N。【输出】只有一行:包含一个正整数,表示建成这N个地铁站所需要的最低成本。【样例输入】【样例输出】331999999199

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。