2010年《数据结构》期终考试试卷(A)清华大学VIP免费

2010 年《数据结构》期终考试试卷（A） 班级 学号 姓名 一、简答题（每小题 6 分，共 30 分） (1) 假 设 一 个 线 性 链 表 的 类 名 为linkedList， 链 表 结 点 的 类 名 为ListNode，它 包 含 两 个 数 据 成 员data 和link。data 存储该结 点 的 数 据 ， link 是链 接指针。下面给定一 段递归打印一 个 链 表 中所有结 点 中数 据 的 算法： void PrintList (ListNode *L) { if ( L != NULL ) { cout << L->data << endl; PrintList ( L->link ); } } 试问此程序在什么情况下不实用？给出具体修改后的 可实用的 程序？ (1) 此程序在内存容量不足时不适用。因为需要一个递归工作栈。当链表越长，递归工作栈的深度越深，需要的存储越多。可采用非递归算法节省存储。 void PrintList (ListNode *L) { while ( L != NULL ) { cout << L->data << endl; L = L->link; } } (2) 如果每个 结 点 占用 2 个 磁盘块因而需要 2 次磁盘访问才能实现读写，那么在一 棵有 n 个 关键码的 2m 阶 B 树中， 每次搜索需要的 最大磁盘访问次数 是 多少？ (2) 在2m 阶B 树中关键码个数n与B 树高度h 之间的关系为 h≤log m ((n+1)/2)+1，那么每次搜索最大磁盘访问次数为2hmax = 2log m ((n+1)/2)+2。 (3) 给 定 一 棵 保 存 有n 个 关 键 码 的 m 阶 B 树 。从某一 非叶结点中删除一 个关 键 码 需要的 最大磁盘访问次数是多少？ (3) 在m 阶B 树中关键码个数n 与B 树最大高度h 的关系为h = logm/2((n+1)/2)+1。若设寻找被删关键码所在非叶结点读盘次数为h’，被删关键码是结点中的ki，则从该结点的pi 出发沿最左链到叶结点的读盘次数为h-h’。当把问题转化为删除叶结点的k0 时，可能会引起结点的调整或合并。极端情况是从叶结点到根结点的路径上所有结点都要调整，除根结点外每一层读入1 个兄弟结点，写出2 个结点，根结点写出1 个结点，假设内存有足够空间，搜索时读入的盘块仍然保存在内存，则结点调整时共读写盘3(h-1)+1。总共的磁盘访问次数为 h’+(h-h’)+3(h-1)+1 = 4h-2 = 4(logm/2((n+1)/2)+1)-2 = = 4logm/2((n+1)/2)+2 (4) 给 定 一 个 有n 个 数据元素的 序列，各元素的 值随机分布。若要将该序列的 数据调整成为一 个 堆，...