江苏省白蒲高级中学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分） 试列出如下图中全部可能的拓扑排序序列