2010年《数据结构》期终考试试卷(A)-清华大学.pdf

2010年《数据结构》期终考试试卷(A)-清华大学--第1页 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 树中，每次搜索需要的最大磁盘访问次数 2010年《数据结构》期终考试试卷(A)-清华大学--第1页 2010年《数据结构》期终考试试卷(A)-清华大学--第2页 是多少？ (2) 在 2m B 树中关键码个数 n 与 B 树高度 h 之间的关系为 h≤logm ((n+1)/2)+1，那么每次搜索最大磁盘访问次数为2hmax = 2log m ((n+1)/2)+2 。 2010年《数据结构》期终考试试卷(A)-清华大学--第2页 2010年《数据结构》期终考试试卷(A)-清华大学--第3页 (3) 给定一棵保存有n 个关键码的m 阶B 树。从某一非叶结点中删除一个 关键码需要的最大磁盘访问次数是多少？ (3) 在 m 阶 B 树中关键码个数 n 与 B 树最大高度 h 的关系为 h = log ((n+1)/2)+1。若设寻找被删关键码所在非叶结点读盘次数为 h ’，被删关 m/2 键码是结点中的k ，则从该结点的p 出发沿最左链到叶结点的读盘次数为h h ’。 i i 当把问题转化为删除叶结点的k 时，可能会引起结点的调整或合并。极端情 0 是从叶结点到根结点的路径上所有结点都要调整，除根结点外每一层读入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 个数据元素的序列，各元素的值随机分布。若要将该序 列的数据调整成为一个堆，那么需要执行的数据比较次数最多是多少？ (4) 设堆的高度为h = l