数据结构习题解析第0章(2)

结果不唯一

(2) 关节点为 ①、②、③、⑦、⑧ 【分析】这是有关重连通图的问题。深度优先搜索是一个需要重点掌握的方法，包括实例分析和算法。它是一个带回溯的探索问题，需要用递归算法求解。另外，关节点的判断准则有两个：其一为根至少有两个或两个以上的子女；其二为除根和叶结点外，其他结点的子女或子孙有指向该结点祖先的“回边”。掌握了这些概念，此问题就迎刃而解了。还需要了解：重连通图中任意两个顶点之间至少有两条路径相通，这有助于将非重连通图改为重连通图。

2、设有13个初始归并段，其长度分别为28，16，37，42，5，9，13，14，20，17，30，12，18。试画出4路归并时的最佳归并树，并计算它的带权路径长度WPL。

【解答】因为 (13 - 1) % (4 - 1) = 12 % 3 = 0，所以不需要添加空段。最佳归并树为

WPL = ( 5 + 9 + 13 + 12 + 16 + 14 + 17 + 18 + 28 + 37 + 20 + 30 ) * 2 + 42 = 4 【分析】这是外排序中求最佳归并树问题，它是只有度为0和度为k的正则k叉树，满足条件n0 = (k-1)nk + 1，其中，n0是度为0的结点个数，nk是度为k的结点个数，k是归并路数。最佳归并树的构造仿照霍夫曼树，长度小的初始归并段离根远，长度大的初始归并段离根近。需要注意的是：当(n0-1) % (k-1) = m ? 0时，需要补充k-m-1个空的初始归并段，才能构成正则k叉树。

3、设散列表为HT[0..12]，即表的大小为m = 13。采用双散列法解决冲突。散列函数和再散列函数分别为： H0( key ) = key % 13; 注：%是求余数运算 Hi = ( Hi-1 + REV ( key + 1) % 11 + 1) ; i = 1, 2, 3, ?, m-1

其中，函数REV(x)表示颠倒10进制数x的各位，如REV(37) = 73，REV(7) = 7等。若插入的关键码序列为2, 8, 31, 20, 19, 18, 53, 27。试画出插入这8个关键码后的散列表。

【解答】散列表 HT[0..12]，散列函数与再散列函数为 H0( key ) = key % 13；

Hi = ( Hi-1 + REV ( key + 1 ) % 11 + 1 ) % 13;

插入关键码序列为 { 2, 8, 31, 20, 19, 18, 53, 27 }

6

H0( 2 ) = 2, 比较次数为1 H0( 8 ) = 8, 比较次数为1 H0( 31 ) = 5, 比较次数为1 H0( 20 ) = 7, 比较次数为1

H0( 19 ) = 6, 比较次数为1 H0( 18 ) = 5, 冲突，H1 = 9，比较次数为2

H0( 53 ) = 1，比较次数为1 H0( 27 ) = 1，冲突，H1 = 7，冲突，H2 = 0，比较次数为3

插入8个关键码后的散列表

0 27 1 53 2 2 3 4 5 31 6 19 7 20 8 8 9 18 10 11 12

【分析】散列表长度和再散列函数的选取是关键。由于要求再散列函数计算出来的结果，即发生冲突时向后跨多大距离找下一个“空位”，必须与表的长度互质。因此为简化问题求解的难度，一般设表的长度为质数，本题设为13。其次，再散列函数是待散列对象的关键码的函数，计算结果的取值范围在1 ? n-1之间，其中n是表的长度。因此选取REV ( key + 1 ) % 11 + 1，其取值范围在1 ? 11之间，除1退化为线性探查外，其他都与13互质。需要注意的是，双散列法对表长度的要求不如二次探查法严格，那里要求表的长度一定是满足4j+3的质数且表的装载因子不超过0.5。此题容易出错的地方是应用再散列函数处理冲突时发生简单计算错误，一处出错，会影响后面一连串出错，一定要仔细。

0.2.5 综合算法题

有一种简单的排序算法，叫做计数排序（count Sorting）。这种排序算法对一个待排序的表（用数组表示）进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键码互不相同。计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键码比该记录的关键码小。假设针对某一个记录，统计出的计数值为c，那么，这个记录在新的有序表中的合适的存放位置即为c。

(1) 给出适用于计数排序的数据表定义；

(2) 使用C++ 语言编写实现计数排序的算法；

(3) 对于有n个记录的表，关键码比较次数是多少？

【解答】

(1) 数据表定义

const int DefaultSize = 100; template class datalist template class Element { private: Type key; public:

Type getKey ( ) { return key; } }

template class datalist {

//用顺序表来存储待排序的元素，这些元素的类型是Type public:

7

//取当前结点的关键码 //将结点的关键码修改为x

void setKey ( const Type x ) { key = x; }

//关键码 //其它数据成员

field otherdata;

//数据表的前视声明 //数据表元素类的定义

datalist ( int MaxSz = DefaultSize ) : MaxSize ( Maxsz ), CurrentSize (0) { Vector = new Element [MaxSz]; } private:

Element * Vector; }

//存储待排序元素的向量 //最大元素个数与当前元素个数

int MaxSize, CurrentSize;

(2) 计数排序的算法 【方案1】

template

void countsort ( datalist& initList, datalist& resultList ) { int i, j, c; Type refer;

for ( i = 0; i < initList.CurrentSize; i++ ) { c = 0; }

resultList.CurrentSize = initList.CurrentSize; }

refer = initList.Vector[i].getKey ( ); for ( j = 0; j < initList.CurrentSize; j++ ) if (initList.Vector[j].getKey ( ) < refer ) c++; resultList.Vector[c] = initList.Vector[i]

【解答2】

template

void countsort ( datalist & initList, datalist & resultList ) { int *c = new int[initList.CurrentSize];

for ( int i = 0; i < initList.CurrentSize; i++ ) c[i] = 0; for ( i = 0; i < initList.CurrentSize-1; i++ ) }

for ( int j = i+1; j < initList.CurrentSize; j++ )

if (initList.Vector[j].getKey ( ) < initList.Vector[i].getKey ( )) c[i]++; else c[j]++;

resultList.Vector[ c[i] ] = initList.Vector[i];

for ( i = 0; i < initList.CurrentSize; i++ ) resultList.CurrentSize = initList.CurrentSize;

(3) 对于n个记录的表，解答1中关键码比较次数为n2，解答2中关键码比较次数为n(n-1)/2。

【分析】编写算法的题可能是学生比较棘手的问题，特别是在考试这样一个氛围，时间又短促，想编出一个好算法不太容易。一个建议是首先仔细阅读试题，了解它到底要你干什么。然后用一个简单的例子走一下，总结每一步向下走用什么语句，再做归纳。也可以按照结构化程序设计的方法，先搭框架，再根据例子填入细节。总之，要想又快又好地编写出算法，还要靠平时的基本训练，多做题，自主做题，各种题型都见过了，考试时自然文思泉涌，笔下就流畅了。

8

0.2.6 填空题

下面给出的是一个在二叉树中查找值为x的结点，并打印该结点所有祖先结点的算法。在此算法中，假设值为x的结点不多于一个。此算法采用后序的非递归遍历形式。因退栈时需要区分其左、右子树是否已经遍历，故在结点进栈时附带有一个标志，＝0，进入左子树，＝1，进入右子树。用栈ST保存结点指针ptr及其标志tag。top是栈顶指针。

void print ( BinTreeNode * t; Type &x ) { stack ST; int i, top; top = 0;

//置空栈

//寻找值为x的结点 ;

; //找到值为x的结点 ; i++ )

//进栈

while ( t != NULL && t->data != x || top != 0 ) {

while ( t != NULL && t->data != x ) { ① ST [top].ptr = t; ST [top].tag = 0; ② }

if ( t != NULL && t->data == x ) for ( i = 1;

else {

while ( top > 0 && ST [top].tag == 1 ) //未找到值为x的结点

top--; if ( top > 0 ) { ST [top].tag = 1; ④ }

} }

} /*print*/

//转向右子树 ; ③ cout << ST[i].ptr->data << endl;

(1) 请将缺失的语句补上 （8分）

①

② ③ ④

(2) 请给出对于右图所示的二叉树，使用上述算法搜索值为9的结点和值为10的结点的结果，以及在栈ST中的变化。（top是栈顶指针） 【解答】

(1) 请将缺失的语句补上

① top++

② t = t->leftChild ③ i <= top

9

④ t = ST[top].ptr->rightChild

(2) 搜索值为9的结点 → ④ ②

①

0 1 0 0

→ ⑦ ④ 0

② 0

① 0

ptr tag ptr tag

搜索值为10的结点 → ??0 → ??1 ⑦ 0 ⑦ 0 → ⑦ 1 ④ 1 ④ 1 ④ 1 → ④ 0 → ⑤ 0 ② 0 ② 0 ② 0 ② 0 → ② 1 ③ 0

① 0 ① 0 ① 0 ① 0 ① 0 ① 1

ptr tag ptr tag ptr tag ptr tag ptr tag ptr tag

→ ⑧ 0 → ⑧ 1 ⑤ 1 ⑤ 1 → ⑥ 0 → ⑥ 1 ③ 0 ③ 0 ③ 1 ③ 1 ① 1 ① 1 ① 1 ① 1 ptr tag ptr tag ptr tag ptr tag ptr tag

【分析】人们常说，读别人的程序不如自己重编。此话有一定道理。各人的思路不同，编程语言的运用和编程技巧的水平不同，编程风格不同，即使是几个人编写同一个功能的程序，可能面貌相差极大，读别人的程序自然困难很大。但现实是将来做技术支持必须读别人的程序。所以，必须有这方面的基本训练和要求。一个建议是：通过试题叙述阅读以了解思路，通过实例分析以了解程序结构，再通过实例跟踪以检验填空后的程序，从而得到最终的解答。

0.3 小结

数据结构课程是计算机专业的基础课程，是一门知识性、实践性都很强的课程。数据结构及算法编写与分析都是不容易的。学好它需要付出极大的劳动，在平时勤学多练。如果有碰运气或取巧的想法，十有八九通不过考试。有一次在中央电大直播课堂进行期末答疑，一位学员不问问题，在网上传来一句话：“救救我吧，我已经考了两次没通过了。”对此，只能为他遗憾。希望他能重新来过，把基础打扎实，考试才能顺利过关。就怕平时不看书，不做作业或抄别人的作业，到考试时照样不会，自然一次次通不过了。最后，祝愿同学们通过自己的勤奋努力，取得优良的成绩。 l

10