《数据结构》上机考题

《《数据结构》上机考题》由会员分享，可在线阅读，更多相关《《数据结构》上机考题（7页珍藏版）》请在金锄头文库上搜索。

1、 1数据结构上机考题数据结构上机考题 考试时间：考试时间： 2011/12/22 晚上晚上 6:30 到到 8:30 注意事项：注意事项：1. 所有题目均为从控制台输入，控制台输出。所有题目均为从控制台输入，控制台输出。 2. 题目题目 2，3，4 都有多组测试数据。都有多组测试数据。 3. system(pause)等让程序暂停的语句不要在程序中使用。等让程序暂停的语句不要在程序中使用。 4. #include 不要添加。不要添加。 5. 按照题目要求提交规定命名的文件。按照题目要求提交规定命名的文件。 6. 评分规则：对一道评分规则：对一道 40 分，对两道分，对两道 60 分，对三道分，

2、对三道 80 分，对四道分，对四道 100 分。分。 7. 题目只有对错之分，没有步骤分。题目只有对错之分，没有步骤分。 8. 重复提交的前重复提交的前 2 次不扣分，第三次开始，提交错一次扣次不扣分，第三次开始，提交错一次扣 5 分。扣完本题分数 为止。分。扣完本题分数 为止。 Problem1 : top-k 问题问题 1） 问题描述问题描述 期末考试结束了，助教开始统计同学们的分数，但是由于同学们人数实在太多，助教只想知 道分数排名前 30%的同学的分数，并从大到小进行排列。同学们人数总数为 N，30%人数往 下取整。 2） 输入及示例输入及示例 第一行输入总人数 N，第二行输入 N 个

3、整型数值 控制台输入：(本题只有一个测试用例本题只有一个测试用例) 9 41 91 86 75 92 66 94 40 71 3）输出及示例）输出及示例 上传文件请命名为 problem1.cpp 或其他相应后缀：problem1.相应后缀 程序运行后，结果输出到屏幕上。输出前 30%大的数值（往下取整） ，并从大到小排列。 整数之间用空格隔开，上例输出结果为： 94 92 4) 数据规模数据规模 0=0&=0 & 1-3 0-2-3 0-1-3 5） 数据规模：数据规模： 顶点数=1000，边数=10000，时间限制为 20s。 6Problem 4：Hilbert 曲线转换曲线转换 1)

4、问题描述问题描述 Hilbert 曲线是德国数学家 David Hilbert 发明的一种连续的空间填充曲线，它能将高维空间 映射到一维空间，同时在一维空间上保留了原高位空间的良好局部性。目前 Hilbert 曲线被 广泛应用于图像存储和检索、空间数据库索引等领域。 对于二维空间，假设有 N*N 个方格（N= 2d，d 为正整数） ，Hilbert 曲线以某种顺序不自交 地通过每个方格的中心点一次且仅一次，填满 N*N 个方格。并从 1 开始，按照填充顺序依 次为每个方格分配一个 ID，称为 Hilbert 值。图 4-1 和 4-2 为 2*2 和 4*4 方格矩阵的 Hilbert 曲线以

5、及每个方格的Hilbert值， 图4-3和4-4为8*8和16*16方格矩阵的Hilbert曲线 （Hilbert 值未标出） 。 1234图 4-1 图 4-2 图 4-3 图 4-4 Hilbert 曲线的填充规律具体如下： （a） 对于 2*2 的方格矩阵，按 NWNESESW 的顺序填充四个方格得到 Hilbert 曲线，如 图 41 所示； 7（b） 假设当前已经知道 2i * 2i的方格矩阵的 Hilbert 曲线形状 Hi，那么对于 2i+1 * 2i+1的 方格矩阵，先将该方格矩阵看成四个 2i * 2i的方格矩阵，按照 NWNESESW 的顺序 填充这四个方格矩阵；其中，NW

6、、NE、SE、SW 方格矩阵的曲线形状分别为 2i * 2i 的方格矩阵的 Hilbert 曲线 Hi顺时针旋转 90，逆时针旋转 0、0、90得到。 现在给定一个 N*N 的二维矩阵，要求对矩阵进行 hilbert 转换，求出某个方格的 hilbert 值。 2) 输入及示例输入及示例 数据从屏幕输入，第一行为测试用例的个数，从第二行开始为每个测试用例的值。每个测试 用例包括 2 行，第一行为矩阵的边长 N，注意 N 一定是 2 的幂，第二行为需要输出 Hilbert 值的方格的坐标 i 和 j，i 和 j 分别表示方格的行数和列数。规定最上一行为第 0 行，最左一 列为第 0 列，即矩阵的左上角方格坐标为(0, 0)。如对于图 4-1 和 4-2 例子，屏幕输入内容如 下： 2 2 1 1 4 1 2 3）输出及示例）输出及示例 上传文件请命名为 problem4.cpp 或其他相应后缀：problem4.相应后缀。 程序运行后，结果输出到屏幕上。输出内容为方格矩阵的第 i 行第 j 列的方格的 Hilbert 值，每个测试用例的结果占一行。以上图为例，输出结果为： 3 8 4）数据规模）数据规模 矩阵边长 N=210，时间限制 20s。