2006年数据结构本科考试例.doc

2006年《数据结构》期终考试试卷（A）小题6分，共30分） (1) 假设一个线性链表的类名为linkedList，链表结点的类名为ListNode，它包含两个数据成员data和link。data存储该结点的数据，link是链接指针。下面给定一段递归打印一个链表中所有结点中数据的算法： void PrintList (ListNode *L) { if ( L != NULL ) { cout Ldata 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个数据元素的序列，各元素的值随机分布。若要将该序列的数据调整成为一个堆，那么需要执行的数据比较次数最多是多少？ (4) 设堆的高度为h = ?log2(n+1)?，当每次调用siftDown算法时都要从子树的根结点调整到叶结点，假设某子树的根在第i层（1≤i≤h-1），第h层的叶结点不参加比较。从子树根结点到叶结点需要比较h-i层，每层需要2次比较：横向在两个子女里选一个，再纵向做父子结点的比较。因此，在堆中总的比较次数为 因为 2h-1≤n≤2h-1，且，则 (5) 设有两个分别有n个数据元素的有序表，现要对它们进行两路归并，生成一个有2n个数据元素的有序表。试问最大数据比较次数是多少？最少数据比较次数是多少？(5) 两个长度为n的有序表，当其中一个有序表的数据全部都小于另一个有序表的数据时，关键码的比较次数达到最小（= n）。而当两个有序表的数据交错排列时，关键码的比较次数达到最大（= 2n-1）。 二、简作题（每小题5分，共分）针对如下的带权无向图 其中，每条边上所注的ei为该边的编号，冒号后面是该边所对应的权值。 (1) 使用Prim算法，从顶点A出发求出上图的最小生成树。要求给出生成树构造过程中依次选择出来的边的序列（用边的编号表示），权值相等时编号小的边优先。（不必画图） (2) 使用Kruskal算法求出上图的最小生成树。要求给出生成树构造过程中依次选择出来的边的序列（用边的编号表示），权值相等时编号小的边优先。（不必画图） (3) 上面求出的最小生成树是唯一的吗？试举理由说明。 (2) 使用Kruskal算法 e9 e13 e5 e7 e15 e1 e11 e2 e17 1 1 2 2 2 3 3 4 7 (3) 这样选取的最小生成树是唯一的。因为在边上的权值相等时先选编号小的，限定了选择的机会。假如不限定在具有相等权值的边中的选择次序，结果可能就可能不唯一了。 三、简作题（共10分） 假设一个散列表中已装入100个表项并采用线性探查法解决冲突，要求有哪些信誉好的足球投注网站到表中已有表项时的平均有哪些信誉好的足球投注网站次数不超过4，插入表中没有的表项时找到插入位置的平均探查次数不超过50.5。请根据上述要求确定散列表的容量，并设计相应