数据结构模拟试题8.pdfVIP

数据结构模拟试题8

一．选择题（每小题1分，共8分）

1.设一数列的顺序为1，2，3，4，5，通过栈结构不可能排成的

顺序数列为（）。

（A）3，2，5，4，1（B）1，5，4，2，3

（C）2，4，3，5，1（D）4，5，3，2，1

2.二叉树的第3层最少有（）个结点。

（A）0（B）1（C）2（D）3

3.一个n个顶点的连通无向图，其边的个数至少为（）。

（A）n－１（B）n（C）n+1（D）nlogn

4.下列排序中，（）的比较次数与记录的初始排列状态无关。

（A）直接插入排序（B）起泡排序

（C）快速排序（D）直接选择排序

5.一棵Huffman树总共有11个结点，则叶子结点有（）个。

（A）5（B）6（C）7（D）9

6.已知某算法的执行时间为（n+n^2）+log2（n+2），n为问题

规模，则该算法的时间负责度为（）。

（A）O(n)（B）O(n^2)

（C）O(log2n)（D）O(nlog2n)

7.如果一棵树有10个叶子结点，则该树总共至少有（）个结点。

（A）10（B）11（C）19（D）21

8.一个100×100的三角矩阵a采用行优先压缩存储后，如果首元

素a[0][0]是第一个元素，那么a[4][2]是第（）个元素。

（A）13（B）401（C）402（D）403

二．判断题（每题1分，共8分。正确的打√，错误的打×）

1.如果某数据结构的每一个元素都最多只有一个直接前驱，则必

为线性表。（）

2.快速排序法在最好的情况下的时间复杂度是O（n）。（）

3.进栈、出栈操作的时间复杂度是O（n）。（）

4.进栈操作时，必须判断栈是否已满。（）

5.一个有序的单链表不能采用折半查找法进行查找。（）

6.二叉排序树采用先序遍历可以得到结点的有序序列。（）

7.对长度为100的有序线性表用折半查找时，最小比较次数为0。

（）

8.对于二叉排序树，根元素肯定是值最大的元素。（）

三．填空题（每题2分，共16分）

1.数据结构有和等两种物理结构。

2.某算法在求解一个10阶方程组时，运算次数是500，求解一个

30阶方程组时，运算次数是4500，则该算法的时间复杂度为。

3.在一个长度为n的顺序表中插入一个元素，最少需要移动个元

素，最多需要移动个元素。

4.如果某有向图的所有顶点可以构成一个拓扑排序序列，则说明

该有向图。

5.如果指针p指向一棵二叉树的一个结点，则判断p没有左孩子

的逻辑表达式为。

6.一个数组的长度为20，用于存放一个循环队列，则队列最多只

能有个元素。

7.无向图用邻接矩阵存储，其所有元素之和表示无向图的。

8.一个具有n个结点的线性表采用堆排序，在建堆之后还要进行次

堆调整。

四．简答题（共38分）

1.写出线性表（26，4，12，25，30，6，15，20，16，2，18）

采用二路归并排序算法排序后，第一趟和第二趟结束时的结果。（5分）

2.（1）给出右图所示树的后序遍历结果。（4）分A

（2）采用孩子-兄弟法将该树转换为一棵二叉树。（5分）

BCD

EFG

3.已知下图是一个有向图。

（1）画出该有向图的邻接链表。（4分）

（2）基于你给出的邻接链表，求从顶点F出发的广度优先遍历。

（4