数据结构复习题及参考答案(4)

广度优先搜索序列：a，b，c，f，d，e，h，g 9.计算机关键码得到的散列地址 关键码 散列地址 19 6 14 1 23 10 01 1 68 3 20 7 84 6 27 1 在散列表中散列结果

0 1 2 3 4 5 6 7 8 9 10 11 12 14 01 68 27 19 20 84 23 10.对n个关键自序列进行一趟快速排序，要进行n-1次比较，也就是基准和其他n-1个关键字比较。这里要求10次，而7 - 1 + 2 * ( 3 - 1 ) = 10，这就要求2趟快速排序后，算法结束。所以，列举出来的序列，要求在做partition的时候，正好将序列平分 (1)4 1 3 2 6 5 7 或 4 1 3 7 6 5 2 或 4 5 3 7 6 1 2

或 4 1 3 5 6 2 7 ....... (2)按自己序列完成

11.答案：(1)djbaechif (2)abdjcefhi (3)jdbeihfca 12.在这个AVL树中删除根结点时有两种方案:

【方案1】在根的左子树中沿右链走到底,用5递补根结点中原来的6,再删除5所在的结点。 【方案2】在根的右子树中沿左链走到底,用7递补根结点中原来的6,再删除7所在的结点。 13.

划分次序 划分结果 第一次 [38 24 40] 46 [56 80 95 79] 第二次 24 [38 40] 46 [56 80 95 79] 第三次 24 38 40 46 [56 80 95 79] 第四次 24 38 40 46 56 [80 95 79] 第五次 24 38 40 46 56 79 [80 95] 第六次 24 38 40 46 56 79 80 95 14.

0 1 2 3 4 5 6 7 8 9 10 11 12 78 15 03 57 45 20 31 23 36 12 查找成功的平均查找长度： ASL SUCC =14/10= 1.4 15.此二叉树的后序遍历结果是： EDCBIHJGFA 16.13／7 1l／7

四、阅读下列算法，分析它的作用

1.统计单链表中结点的值等于给定值x的结点数。 2.对数组A中的n个元素进行排序，称为起泡算法。 3.该算法的输入结果是：34 91 30 45 63 78

4.该算法的功能是：交换二叉树的左右子树的递归算法。

5.该算法是顺序栈类的进栈算法。 如果栈满返回“满”；否则X元素进栈。 6.该算法是将链表的数据元素输出算法。 输出结果：

a b

第16页共22页

c d Head a b c d e ^ 7.该算法是求链表结点个数的算法。 结果返回结点个数的总和值。

8.本算法要求二叉树中叶子结点的总数的算法。

用n值存储叶子结点的个数。

9.（15，30，48，50）

10.从初始点vi出发深度优先搜索遍历由邻接距阵GA所表示的图

11.该算法是顺序栈类的出栈算法。 如果栈空返回-999；否则返回出栈元素的值。 12.该算法是将链表逆置的算法。 链表逆置后，具体如下图：

Head e d c b a ^ 13.输出是“ 查找成功，找到：5 ” 比较3次得到结果。

14.向单链表的末尾添加一个元素。 15.删除线性表中所有重复的元素。 16.23 25 35 45 77 78

17. 1 2 3 4 5 6 7 8 9 10 五、算法设计题：

1.将算法实现函数声明为二叉树类的友元函数，可采用层次遍历的方式进行复制，将已复制的结点进入一个队列中即可。 具体算法实现如下：

// 文件路径名:exam5\\alg.h template

void CopyBitree(BinaryTree *fromBtPtr, BinaryTree *&toBtPtr) // 操作结果: 复制二叉树fromBt到toBt的非递归算法 { if (toBtPtr != NULL) delete toBtPtr; // 释放toBtPtr if (fromBtPtr->Empty()) { // 空二叉树 toBtPtr = NULL; // 空二叉树 } else { // 非空二叉树 LinkQueue *> fromQ, toQ; // 队列 BinTreeNode *fromPtr, *toPtr, *fromRoot, *toRoot; fromRoot = fromBtPtr->GetRoot(); // 取出fromBtPtr的根 toRoot = new BinTreeNode(fromRoot->data); // 复制根结点 fromQ.InQueue(fromRoot); toQ.InQueue(toRoot); // 入队 while (!fromQ.Empty()) { // fromQ非空 fromQ.OutQueue(fromPtr); // 出队 toQ.OutQueue(toPtr); // 出队 if (fromPtr->leftChild != NULL) { // 左子树非空 toPtr->leftChild = new BinTreeNode(fromPtr->leftChild->data); // 复制fromPtr左孩子

第17页共22页

} }

fromQ.InQueue(fromPtr->leftChild); toQ.InQueue(toPtr->leftChild); // 入队 } if (fromPtr->rightChild != NULL) { // 右子树非空 toPtr->rightChild = new BinTreeNode(fromPtr->rightChild->data); // 复制fromPtr左孩子 fromQ.InQueue(fromPtr->rightChild); toQ.InQueue(toPtr->rightChild); // 入队 } }

toBtPtr = new BinaryTree(toRoot); // 生成toBtPtr

2.从上图来看，二叉树的第一层显示在第一列，第二层显示在第二列，第三层显示在第三列；每行显示

一个结点，从上至下是先显示右子树，再显示根，最后最左子树，也就是以先遍历右子树，最后遍历左子树的中序遍历次序显示各结点。 具体算法实现如下：

// 文件路径名:exam1\\alg.h ss ElemType>

void DisplayHelp(BinTreeNode *r, int level)

// 操作结果：按树状形式显示以r为根的二叉树，level为层次数，可设根结点的层次数为1 { if(r != NULL) { // 空树不显式，只显式非空树 DisplayHelp(r->rightChild, level + 1); // 显示右子树 cout << endl; // 显示新行 for(int i = 0; i < level - 1; i++) cout << \ // 确保在第level列显示结点 cout << r->data; // 显示结点 DisplayHelp(r->leftChild, level + 1); // 显示左子树 } }

template

void Display(const BinaryTree &bt) // 操作结果：树状形式显示二叉树 { DisplayHelp(bt.GetRoot(), 1); // 树状显示以bt.GetRoot()为根的二叉树 cout << endl; // 换行 }

3.对于排列的解空间可构造一个虚拟的解空间树，比如n=5，k=3时的解空间树如下图所示，可采用对此树进行先序遍历方式进行遍历，并用递归法进行递归输出从n个数中挑选 k个进行排列所得序列。

具体算法实现如下：

// 文件路径名:exam7\\alg.h template

第18页共22页

void Arrage(ElemType a[],int k,int n, int outlen=0)

// 操作结果: 回溯法输出排列序列，a[0..k-1]为k个数的排列序列outlen为当前所求排列 // 序列的长度，其中outlen=k时的排列序列为所求；n为list数组长度 { if (k < 0 || k >= n) return; // 此时无排列 int i; // 临时变量 if (outlen == k + 1) { // 得到一个排列 for (i = 0; i < k; i++) { // 输出一个排列 cout << a[i]; // 输出a[i] } cout << \ // 用空格分隔不同排列 } else { // 对解空间进行前序遍历，a[outlen..n]有多个排列，递归的生成排列 for (i = outlen; i < n; i++) { // 处理a[i] Swap(a[outlen+1], a[i]); // 交换a[outlen+1]与a[i] Arrage(a, k, n, outlen + 1); // 对序列长度outlen+1递归 Swap(a[outlen+1], a[i]); // 交换a[outlen+1]与a[i] } } }

4.编写一个算法，交换单链表中p所指向的结点和其后续结点的两个结点，Head指向该链表的表头，P指向链表中的某一结点。 Head c e ^ a d b

void Link ::swap( NodeType *p) //0.5分

{ NodeType *q,*r,*s;

q=p->next; //0.5分 if(q!=NULL) //1分 { if(p==Head) //4分 {Head=Head->next; s=Head->next; Head->next=p; p->next=s; }

Else // 4分 { r=Head;

while(r->next!=p) r=r->next; r->next=q;

p->next=q->next; q->next=p; } } }

5.可按先遍历右子树，遍历根结点，再遍历左子树进行中序遍历，这样可实现由大到小遍历一棵二叉排序树。

具体算法实现如下：

// 文件路径名:exam4\\alg.h

第19页共22页

#include \ // 二叉排序树类 template

void InOrderHelp(BinTreeNode *r, const KeyType &key)

// 操作结果: 从大到小输出以r为根的二叉排序树中所有的关键字值不小于key的元素值 { if (r != NULL) { // 非空二叉排序树 InOrderHelp(r->leftChild, key); // 遍历左子树 if(r->data < key) cout << r->data << \ // 输出根结点 else return; InOrderHelp(r->rightChild, key); // 遍历右子树 } }

template

void InOrder(const BinarySortTree &t, const KeyType &key) // 操作结果: 从大到小输出二叉排序树中所有的关键字值不小于key的元素值 { InOrderHelp(t.GetRoot(), key); // 调用辅助函数实现从大到小输出二叉排序树中所有的关键字值不小于key的元素值 }

6. void Link ::Delnode( )

{ NodeType *p=Head->next, *q,*r=p;

while(p!=NULL&&p->data

p=p->next;

} q=p;

while( q!=NULL && p->data next; r->next=q->next; r=p->next; while(r!=q) { delete p;

p=r;r=r->next; }

delete q;

} // delpro

7.二叉树采取顺序结构存储，是按完全二叉树格式存储的。对非完全二叉树要补上“虚结点”。由于不是完全二叉树，在顺序结构存储中对叶子结点的判定是根据其左右子女为0。叶子和双亲结点下标间的关系满足完全二叉树的性质。

int Leaves(int h) //求深度为h以顺序结构存储的二叉树的叶子结点数

hh

{int BT[]; int len=2-1, count=0; //BT是二叉树结点值一维数组，容量为2 for (i=1;i<=len;i++) //数组元素从下标1开始存放 if (BT[i]!=0) //假定二叉树结点值是整数，“虚结点”用0填充

if(i*2)>len) count++; //第i个结点没子女，肯定是叶子

else if(BT[2*i]==0 && 2*i+1<=len && BT[2*i+1]==0)

count++; //无左右子女的结点是叶子

return (count)

第20页共22页