数据结构期终复习

(1)画出该图的图形;

(2)根据邻接矩阵从顶点a出发进行深度优先遍历和广度优先遍历,写出相应的遍历序列。

四、(本题8分)

树有哪些遍历方法?它们分别对应于把树转变为二叉树的哪些遍历方法? 五、(本题8分)

将关键字序列(7、8、11、18、9、14, 30)散列存储到散列列表中,散列表的存储空

H(key)=% m间是一个下标从0开始的一个一维数组,散列函数为:(key * 3)(m为表长),

处理冲突采用线性探测再散列法,要求装填(载)因子为0.7,请画出所构造的散列表;计算查找成功的平均查找长度。

六、(本题8分)

试列出如下图中全部可能的拓扑排序序列。

123456 七、(本题8分)

请说明对一棵二叉树进行按照先遍左子树,后右子树的方式进行前序、中序和后序遍历,其叶结点的相对次序是否会发生改变?为什么?

八、(本题8分)

设有一个输入数据的序列是 { 46, 25, 78, 62, 12, 80 }, 试画出从空树起,逐个输入各个数据而生成的二叉排序树。

九、(本题9分)

试画出表达式(a+b/c)*(d-e*f)的二叉树表示,并写出此表达式的波兰式表示,中缀表示及逆波兰式表示。

十、(本题15分)

以二叉链表作存储结构,试编写计算二叉树中叶子结点数目的递归算法。

模拟试题(二)参考答案

一、单项选择题(每小题 2 分,共20分) (1)B (2)C.D (3)B (4)D (5)A (6)A (7)C (8)C (9)D (10)D 二、(本题8分)

D第二个出栈的次序有CDEBA 、CDBAE 和按照栈的特点可知以元素C第一个出栈,

CDBEA 3种。

三、(每小题4分,共8分)

【解答】

(1)该图的图形如下图所示:

(2)深度优先遍历序列为:abdce;广度优先遍历序列为:abedc。 四、(本题8分)

树的遍历方法有先根序遍历和后根序遍历,它们分别对应于把树转变为二叉树后的先序遍历与中序遍历方法。

五、(本题8分)

由装载因子0.7,由于有7个数据元素,可得7/m=0.7,从而m=10,所以,构造的散列表为:

下标 关键字 比较次数

0 30 1

1 7 1

2 14 1

3 11 1

4 8 1

5 18 2

6 .

7 9 1

8 .

9

H(7)=(7*3)% 10=1 H(8)=(8*3)% 10=4 H(11)=(11*3)% 10=3 H(18)=(18*3)% 10=4 H(9)=(9*3)% 10=7 H(14)=(14*3)% 10=2 H(30)=(30*3)% 10=2

(2)查找成功的ASL=(1+1+1+1+1+2+1)/7=8/7 六、(本题8分)

全部可能的拓扑排序序列为:1523634、152634、156234、561234、516234、512634、512364

七、(本题8分)

二叉树任两个中叶结点必在某结点的左/右子树中,三种遍历方法对左右子树的遍历都是按左子树在前、右子树在后的顺序进行遍历的。所以在三种遍历序列中叶结点的相对次序是不会发生改变的。

八、(本题8分)

九、(本题9分)

表达式的波兰式表示,中缀表示及逆波兰式表示分别是此表达式的二叉树表示的前序遍历、中序遍历及后序遍历序列。

二叉树表示如下图所示:

波兰式表示:*+a/bc-d*ef 中缀表示:a+b/c*d-e*f 逆波兰式表示:abc/+def*-* 十、(本题15分)

本题只要在遍历二叉树的过程序中对叶子结点进行记数即可。 具体算法实现如下:

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

long LeafCountHelp(BinTreeNode *r)

// 操作结果:按树状形式显示二叉树,level为层次数,可设根结点的层次数为1 { if (r == NULL) { // 空二叉树 return 0; // 空树返回0 } else if (r->leftChild == NULL && r->rightChild == NULL) { // 只有一个结点的树 return 1; // 只有一个结点的树返回1 } else { // 其他情况, 叶子结点数为左右子树的叶子结点数之和 return LeafCountHelp(r->leftChild) + LeafCountHelp(r->rightChild); } }

template

long LeafCount(const BinaryTree &bt) // 操作结果:计算二叉树中叶子结点数目 { return LeafCountHelp(bt.GetRoot()); // 调用辅助函数实现计算二叉树中叶子结点数目 }

模拟试题(三)

一、单项选择题(每小题 2 分,共20分)

(1)对一组数据(2,12,16,88,5,10)进行排序,若前三趟排序结果如下

第一趟:2,12,16,5,10,88 第二趟:2,12,5,10,16,88 第三趟:2,5,10,12,16,88 则采用的排序方法可能是( )。

A)起泡排序 B)希尔排序 C)归并排序 D)基数排序

(2)在带有头结点的单链表HL中,要向表头插入一个由指针p指向的结点,则执行( )。

A)p->next=HL->next; HL->next=p B)p->next=HL; HL=p C)p->next=HL; p=HL D)HL=p; p->next=HL (3)对线性表,在下列哪种情况下应当采用链表表示?( )

A)经常需要随机地存取元素 B)经常需要进行插入和删除操作 C)表中元素需要占据一片连续的存储空间 D)表中元素的个数不变

(4)一个栈的输入序列为1 2 3,则下列序列中不可能是栈的输出序列的是( )。

A)2 3 1 B)3 2 1 C)3 1 2 D)1 2 3

(5)每一趟都能选出一个元素放在其最终位置上,并且不稳定的排序算法是( )。

A)冒泡排序 B)简单选择排序C)希尔排序 D)直接插入排序 (6)采用开放定址法处理散列表的冲突时,其平均查找长度( )。

A)低于链接法处理冲突 B)高于链接法处理冲突 C)与链接法处理冲突相同 D)高于二分查找

(7)若需要利用形参直接访问实参时,应将形参变量说明为( )参数。

A)值 B)函数 C)指针 D)引用

(8)为解决计算机与打印机之间速度不匹配的问题,通常设置一个打印数据缓冲区,主机将要输出的数据依次写入该缓冲区,而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是( )。

A)栈 B)队列 C)树 D)图

在稀疏矩阵的带行指针向量的链接存储中,每个单链表中的结点都具有相同的( )。

A)行号 B)列号 C)元素值 D)非零元素个数

联系客服:779662525#qq.com(#替换为@)