数据结构c++模拟试题.doc

模拟试题3
一．选择题
，用直接插入算法进行排序，需要比较的次数为（ ）
-1 C. 2log2n
冒泡排序
n2
选择排序
n2
插入排序
n2
堆排序
nlog n
归并排序
nlog2n
快速排序
n2
希尔排序
n2
(n2)的排序方法是( )

3.．对采用二分查找法进行查找运算的查找表，要求按（ ）方式进行存储。
B 链式存储

{1，4，6，10，18，35，42，53，67，71，78，84，92，99}，当用二分查找法查找健值为84的结点时，经（ ）次比较后查找成功。
B. 3 C. 4 D. 12
( )…………………………………………….


6．用顺序查找法对具有n个结点的线性表查找的时间复杂性量级为
（n2） B. O(nlog2n) C. O（n） (log2n)
，该图至少应有（ ）条边能确保是一个连通图。
A. 5 B. 6 C. 7 D 8
，所有顶点的度数之和是所有边数的（ ）倍。
．5
( )个结点.

10．将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为41的双亲结点编号为 ( )

,中序遍历序列是deabc,它的前序遍历序列是（ ）

、中根序列和后根序列中，所有叶子结点的先后顺序( )

，而与后序不同 ，而与先序不同
13．如果以链表作为栈的存储结构，做退栈操作时( )


14．链栈与顺序栈相比，有一个比较明显的优点即（ ）
B. 通常不会出现栈满的情况
D. 删除操作更方便
（ ）
A. 数据元素 B. 数据项 C. 数据 D. 数据结构
二．填空题
，经过排序，这些记录的相对次序仍然保持不变，则称这种排序方法是________的，否则称为________的。
，排序可分为________排序和________排序。
，它的时间复杂性为________，空间复杂度为________。
，其最坏情况下所需的时间复杂度是________。
、增加了限制条件的二叉树，其限制条件是任一结点的键值________于其左孩子（及其子）的键值且________于其右孩子（及其子）的键值。