《数据结构》上机考题.PDFVIP

《数据结构》上机考题 考试时间： 2011/12/22 晚上 6:30 到 8:30 注意事项：1. 所有题目均为从控制台输入，控制台输出。 2. 题目 2，3，4 都有多组测试数据。 3. system(pause)等让程序暂停的语句不要在程序中使用。 4. #include stdafx.h不要添加。 5. 按照题目要求提交规定命名的文件。 6. 评分规则：对一道 40 分，对两道 60 分，对三道 80 分，对四道 100 分。 7. 题目只有对错之分，没有步骤分。 8. 重复提交的前 2 次不扣分，第三次开始，提交错一次扣 5 分。扣完本题分数 为止。 Problem1 : top-k 问题 1）问题描述 期末考试结束了，助教开始统计同学们的分数，但是由于同学们人数实在太多，助教只想知 道分数排名前 30%的同学的分数，并从大到小进行排列。同学们人数总数为N ，30%人数往 下取整。 2 ）输入及示例 第一行输入总人数 N ，第二行输入N 个整型数值 控制台输入：(本题只有一个测试用例) 9 41 91 86 75 92 66 94 40 71 3 ）输出及示例 上传文件请命名为 problem1.cpp 或其他相应后缀：problem1.相应后缀  程序运行后，结果输出到屏幕上。输出前30%大的数值（往下取整），并从大到小排列。 整数之间用空格隔开，上例输出结果为： 94 92 4) 数据规模 0N1000，学生成绩=0=100 ，时间限制2s 。 1 Problem 2 ：子结构判断 1) 问题描述 二叉树的结点定义如下： struct TreeNode { char m_nValue; TreeNode* m_pLeft; TreeNode* m_pRight; }; 同一棵二叉树的每一个结点值互不相同。对于两棵二叉树T1 和 T2，如果 T1 有一部分子树 的结构与 T2 是一样的，则称 T2 是 T1 的子结构。如图2 所示的两棵二叉树，由于 T1 的一 部分子树与 T2 是一样的，因此称 T2 是 T1 的子结构。输入两棵二叉树 T1 和 T2，判断 T2 是否为 T1 的子结构。 A B B C D E T2 D E F G T1 图 2 2 2) 输入及示例 数据从屏幕输入，第一行为测试用例的个数，从第二行开始为每个测试用例的信息。每个测 试用例包括 8 行，包含两棵二叉树的信息，每棵二叉树 4 行。前 4 行为 T1 信息，其中，第 一行是二叉树的节点数；第二行是节点 n_mValue ，按照层次遍历排列；同时对于每个节点， 我们按照层次遍历的顺序给它们编号，第一个节点即根节点编号为 0 ，第二个节点编号为 1，……；第三行是各节点的左子节点指针，表示左子节点在层次遍历中的位置编号，如果 没有左子节点，则为-1 ；第四行是各节点的右子