数据结构C++考试题及答案.pdfVIP

乐民之乐者，民亦乐其乐；忧民之忧者，民亦忧其忧。——《孟子》

__________________________________________________

数据结构试题一

一、单项选择题（每小题3分，共30分）

1、在有n个叶子结点的哈夫曼树中，其结点总数为

（）。

A、不确定B、2nC、2n+1D、2n-1

2、下列序列中，（）是执行第一趟快速排序得到的

序列（排序的关键字类型是字符串）。

A、[da，ax，eb，de，bb]ff[ha，gc]

B、[cd，eb，ax，da]ff[ha，gc，bb]C、[gc，ax，

eb，cd，bb]ff[da，ha]D、[ax，

bb，cd，da]ff[eb，gc，ha]

3、若线性表最常用的操作是存取第i个元素及其前

驱的值，则采用（）存储方式节省时间。

A、单链表B、双链表C、单循环链表

D、顺序表

4、下列排序算法中，时间复杂度不受数据初始状态

影响，恒为O(nlogn)的是（）。

A、堆排序B、冒泡排序C、直接选择排序

D、快序排序

5、某二叉树的先序序列和后序序列正好相反，则该

二叉树一定是（）的二叉树。

A、空或只有一个结点

__________________________________________________

乐民之乐者，民亦乐其乐；忧民之忧者，民亦忧其忧。——《孟子》

__________________________________________________

B、高度等于其结点数

C、任意结点无左孩子

D、任意结点无右孩子

6、下列排序算法中，某一趟结束后未必能选出一个

元素放在其最终位置上的是（）。

A、堆排序B、冒泡排序C、直接

选择排序D、快序排序

7、快速排序算法在最好情况下的时间复杂度为（）。

A、O(n)B、O(n2)C、

O(nlogn)D、O(logn)

8、已知数据表A中每个元素距其最终位置不远，则

采用（）排序算法最省时间。

A、堆排序B、插入排序C、直接

选择排序D、快序排序

9、带权有向图G用邻接矩阵A存储，则顶点i的入

度为A中（）。