江苏省白蒲高级中学2020—2021学年信息技术竞赛数据结构与算法练习卷二(含答案与评分标准)

江苏省白蒲高级中学信息技术竞赛数据结构与算法练习卷二

一、单项选择题（每小题 2 分，共20分）

1．数据结构可形式地定义为(D,S)，其中S是D上（　　　）的有限集。

A）操作   B）存储映象      C）关系   D）数据元素

2. 对线性表进行二分法查找，其前提条件是（　　　）。

A）线性表以链接方式存储，并且按关键字值排好序

B）线性表以顺序方式存储，并且按关键字值的检索频率排好序

C）线性表以顺序方式存储，并且按关键字值排好序

D）线性表以链接方式存储，并且按关键字值的检索频率排好序

3.若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用（　　　）存储方式最节省时间。

A）单链表  B）非循环的双链表 C）带头结点的双循环链表  D）单循环链表

4. （　　　）不是队列的基本运算。

A）在队列第i个元素之后插入一个元素     B）从队头删除一个元素

C）判断一个队列是否为空                 D）读取队头元素的值

5. 若广义表A满足Head(A)==Tail(A)，则A为（　　　）。

A）()      B）(())   C）((),())   D）((),(),())

6. 字符A、B、C、D依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成（　　　）个不同的字符串？

A）15      B）14       C）16      D）21

7. 具有n个顶点的无向图，它可能具有的边的条数的最大值为（　　　）。

A）(n2+n)/2     B）n2       C）(n2-n)/2     D）n

8. 若数据元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是（　　　）。

  A）起泡排序       B）插入排序   C）选择排序   D）二路归并排序

9. 假定有K个关键字互为同义词，若用线性探测法把这K个关键字存入散列表中，至少要进行（　　　）次探测。

A）K-1       B）K           C）K+1       D）K(K+1)/2

10. 每一趟都能选出一个元素放在其最终位置上，并且不稳定的排序算法是（　　　）。

A）冒泡排序  B）简单选择排序C）希尔排序  D）直接插入排序

二、（本题10分）

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

三、（本题10分）

假设把n个元素的序列（a1,a2,…an）满足条件ak<max{at|1≤t≤k}的元素ak称为“逆序元素”。若在一个无序序列中有一对元素ai>aj(i<j)，试问，当ai与aj相互交换后，该序列中逆序元素的个数一定不会增加，这句话对不对？如果对，请说明为什么？如果不对，请举一例说明。

四、（本题10分）

一棵非空的有向树中恰有一个顶点入度为0，其他顶点入度为1。但一个恰有一个顶点入度为0、其他顶点入度为1的有向图却不一定是一棵有向树。请举例说明之。

五、（本题10分）

已知一棵度为m的树中有N1个度为1的结点，N2个度为2的结点，…，Nm个度为m的结点。试问该树中有多少个叶子结点？

六、（本题10分）

已知一个图的顶点集V为： V={1,2,3,4,5,6,7}，弧如下表所示。

试用克鲁斯卡尔算法依次求出该图的最小生成树中所得到的各条边及权值。

七、（本题10分）

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

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

（2）计算查找成功的平均查找次数。

八、（本题10分）

编写一棵二叉树的先序遍历的非递归算法。