数据结构排序答案(数据结构课程设计排序综合)
导语：华文慕课-数据结构外排序题库
1、假设计算机系统有2048个字节的磁盘块，要存储的每一条记录为48字节，其中数据占了44个字节，关键码占4个字节。磁盘指针为4个字节。那么这个磁盘块上最多有多少条记录？
解析
2048/48=42.67，则最多42条记录
答案： 42
2、假设计算机系统有2048个字节的磁盘块，要存储的每一条记录为68字节，其中数据占了64个字节，关键码占4个字节。磁盘指针为4个字节。那么这个磁盘块上最多有多少条记录？
解析
2048/68=30.12，则最多30条记录
答案： 3
3、设输入的关键码满足k1>k2>…>kn，缓冲区大小为m，用最小值堆进行置换-选择排序方法可产生多少个初始归并段？n=100,m=5
解析
n/m=20，由于后面的关键码更小，所以每次的顺串大小均为m
答案： 20
4、有8个顺串，每个顺串的第一个记录的关键码分别为14，22，24，15，16，11，100，18，根据对顺串开始8路合并时的败者树。求问根节点是几号？（注意：顺串的编号从1开始，本题不是问根节点上面表示“冠军”的额外的节点）
解析：败者树的根结点记录的是败者，需要加一个结点来记录整个比赛的胜利者。
答案： 1
5、有8个顺串，每个顺串的第一个记录的关键码分别为14，22，24，15，16，11，100，18，第二个记录的关键码分别为26，38，30，26，50，28，110，40。从败者树输出—个全局优胜者(并有相应的一个记录进入败者树)后需对败者树进行重构，则重构后的败者树的根结点是几号？（注意：顺串的编号从1开始，本题不是问根结点上面表示“冠军”的额外的结点）
解析：败者树的根结点记录的是败者，需要加一个结点来记录整个比赛的胜利者。
答案： 5
6、从磁盘中随机选择的两个磁道的平均距离约是磁盘中磁道总数的多少？
A、1/2
B、1/3
C、2/3
D、1/4
解析
7、如图所示，进行六路归并的顺串的第一个记录的关键码分别是22,6,12,84,10,9。请构造赢者树填充其他节点，求该二叉树的广度优先周游序列。（注意：不包括已知的6个外部节点，各个数字之间用空格分隔，结尾没有空格）
解析：
一般来说，胜者树中胜出的是关键码较小的那个记录。
另外，要注意每个节点保存的是两个子节点中，胜出的记录的编号，而不是关键码。
答案： 2 2 6 2 3
8. 如图所示，进行五路归并的顺串的第一个记录的关键码分别是14, 18, 9, 23, 77。请构造赢者树填充其他节点，求该二叉树的广度优先周游序列。（注意：不包括已知的5个外部节点，各个数字之间用空格分隔，结尾没有空格）
解析：
一般来说，胜者树中胜出的是关键码较小的那个记录。
另外，要注意每个节点保存的是两个子节点中，胜出的记录的编号，而不是关键码。
答案： 3 3 4 1
免责声明:本站部份内容由优秀作者和原创用户编辑投稿，本站仅提供存储服务，不拥有所有权,不承担法律责任。若涉嫌侵权/违法的，请反馈，一经查实立刻删除内容。本文内容由快快网络小梓创作整理编辑！