《数据结构》四川大学 - 期终复习试题+答案

的结点即可。

C++语言版采用教材所提供的二叉排序树的存储结构，并使用友元方式共享二叉排序的根指针，测试程序见exam4\\10c++，具体算当如下：

template

void display_key(const Binary_tree &T,Record K) // 从小到大输出该二又排序树中所有关键字值≥K的结点的关键字的值 { aux_display_key(T.get_root(),K); }

template

void aux_display_key(Binary_node *sub_root,Record K) // 从小到大输出该二又排序树中所有关键字值≥K的结点的关键字的值的辅助函数 { if(sub_root) { aux_display_key(sub_root->left,K); //输出左子树 if(sub_root->data>=K) cout<data<<\ \ //输出满足条件的关键值 aux_display_key(sub_root->right,K); //输出右子树 } }

C语言版测试程序见exam4\\10c，具体算当如下：

void DisplayKey(BiTree T,KeyType K) // 从小到大输出该二叉排序树中所有关键字值≥K的结点的关键字的值 { if(T) { DisplayKey(T->lchild,K); //输出左子树 if(T->data.key>=K) cout<data.key<<\ \//输出满足条件的关键值 DisplayKey(T->rchild,K); //输出右子树 } }

模拟试题（五）

一、单项选择题（每小题 2 分，共20分） （1）队列的特点是（ ）。

A）先进后出 B）先进先出 C）任意位置进出 D）前面都不正确 （2）有n个记录的文件，如关键字位数为d，基数为r，则基数排序共要进行（ ）遍分配与收集。

A）n B）d C）r D）n - d

（3）在二叉树结点的先序序列、中序序列和后序序列中，所有叶子结点的先后顺序（ ）。

A）都不相同 B）完全相同 C）先序和中序相同，而与后序不同 D）中序和后序相同，而与先序不同 （4）限定在一端加入和删除元素的线性表称为（ ）。

A）双向链表 B）单向链表 C）栈 D）队列 （5）快速排序执行一遍之后，已经到位的元素个数是（ ）。

A）1 B）3 C）n D）n

42（6）设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树上的结点个数为n，森林F中第一棵树的结点个数是（ ）。

A）m-n-1 B）n+1 C）m-n+1 D）m-n

（7）设有198个初始归并段，如采用K-路平衡归并三遍完成排序，则K值最大为（ ）。

A）12 B）13 C）14 D）15 （8）下面关于广义表的叙述中，不正确的是（ ）。

A）广义表可以是一个多层次的结构 B）广义表至少有一个元素 C）广义表可以被其他广义表所共享 D）广义表可以是一个递归表

（9）设二叉树根结点的层次为0，一棵深度（高度）为k的满二叉树和同样深度完全二叉树各有f个结点和c个结点，下列关系式不正确的是（ ）。

A）f>=c B）c>f C）f=2k+1-a D）c>sk-1

（10）从L=((apple,pear),(orange,banana))中，取出banana元素的表达式为（ ）。

A）head(tail(L)) B）head(head(tail(L))) C）tail(head(tail(L))) D）head(tail(head(tail(L)))) 二、（每小题4分，共8分）

写出下列中缀表达式的后缀形式： （1）3X/(Y-2)+1 （2）2+X*(Y+3) 三、（每小题4分，共8分） 试对如下图中的二叉树画出其：

（1）顺序存储表示；

（2）二叉链表存储表示的示意图。

四、（每小题4分，共8分）

判断以下序列是否是小根堆? 如果不是，将它调整为小根堆。 （1）{ 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 }

（2）{ 05, 23, 20, 28, 40, 38, 29, 61, 35, 76, 47, 100 } 五、（本题8分）

已知一个图的顶点集V和边集E分别为： V={1,2,3,4,5,6,7};

E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25}; 按照普里姆算法从顶点1出发得到最小生成树，试写出在最小生成树中依次得到的各条边。

六、（每小题2分，共8分）

设有12个数据25,40,33,47,12,66,72,87,94,22,5,58，它们存储在散列表中，利用线性探测再散列处理冲突，取散列函数为H(key)=key % 13。

（1）顺次将各个数据散列到表中，并同时列出各元素的比较次数。 （2）计算查找成功的平均查找次数。 七、（第1小题2分，第2、3小题每小题3分，本题8分） 对于如下图所示的图G，邻接点按从小到大的次序。

（1）图G有几个连通分量？

（2）按深度优先搜索所得的树是什么？

（3）按深度优先搜索所得的顶点序列是什么？ 八、（本题8分）

已知一棵树边的结点为：

{(I,M),(I,N),(E,I),(B,E),(B,D),(C,B),(G,J),(G,K),(A,G),(A,F),(H,L),(A,H),(C,A)} 试画出这棵树，并回答下列问题： （1）哪个是根结点？ （2）哪些是叶子结点？ （3）树的深度是多少？ 九、（本题9分）

给出一组关键字T=(12,2,16,30,8,28,4,10,20,6,18)。写出用下列算法从小到大排序时第一趟结束时的序列。

（1）希尔排序（第一趟排序的增量为5） （2）快速排序（选第一个记录为枢轴） 十、（本题15分）

编写复制一棵二叉树的非递归算法。

模拟试题（五）参考答案

一、单项选择题（每小题 2 分，共20分） （1）B （2）B （3）B （4）C （6）D （7）C （8）B （9）B 二、（每小题4分，共8分）

（1）3 X * Y 2 - / 1 + （2）2 X Y 3 + * + 三、（每小题4分，共8分）

（1）二叉树的顺序存储表示如下所示：

0 1 1 2 2 3 3 4 4 5 6 5 7 6 8 9 7 10 11 12 （5）A （10）D

13 8 14 15 16 17 18 9 （2）二叉树的二叉链表存储表示的示意图如下图所示：

四、（每小题4分，共8分）

（1）不是小根堆。调整为：{12,24,33,65,33,56,48,92,86,70} （2）是小根堆。 五、（本题8分）

普里姆算法从顶点1出发得到最小生成树为： (1,2)3, (1,3)5, (1,4)8, (4,6)4, (2,5)10, (4,7)20 六、（每小题2分，共8分）

（1）取散列函数为H(key)=key % 13。

（2）顺次将各个数据散列到表中，并同时列出各元素的比较次数如下表所示。

各元素的比较次数

地址 关键字 比较 0 1 40 1 2 66 2 3 94 1 4 5 5 1 6 58 1 7 33 1 8 47 1 9 72 3 10 87 2 11 22 3 12 25 1 13 12 2 14