专升本数据结构数据结构 试卷B.doc
141 浏览量
2024-01-14
13:33:37
上传
评论
收藏 46KB DOC 举报
《数据结构》 试卷 B 第 1 页 共 3 页
《数据结构》试卷 B
一、单项选择题(在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号填在
题干的括号内。每小题 2 分，共 38 分)
1.某二叉树的先序序列和后序序列正好相同，则该二叉树一定是( )的二叉树。
A.空或只有一个结点 B.高度等于其结点数
C.任一结点无左孩子 D.任一结点无右孩子
2.下列排序算法中，时间复杂度不受数据初始状态影响，恒为 O(log
2
n)的是( )
A.堆排序 B.冒泡排序
C.直接选择排序 D.快速排序
3.下列排序算法中，( )算法可能会出现下面情况：初始数据有序时，花费的时间反而最
多。
A.堆排序 B.冒泡排序
C.快速排序 D.SHELL 排序
4.一个栈的输入序列为 1 2 3 4 5，则下列序列中不可能是栈的输出序列的是( )
A. 2 3 4 1 5 B. 5 4 1 3 2
C. 2 3 1 4 5 D. 1 5 4 3 2
5.设循环队列中数组的下标范围是 1～n，其头尾指针分别为 f 和 r，则其元素个数为( )
A. r-f B. r-f+1
C. (r-f) mod n+1 D. (r-f+n) mod n
6.若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用
( )存储方式最节省时间。
A.单链表 B.双链表
C.带头结点的双循环链表 D.单循环链表
7.在有 n 个结点的二叉链表中，值为非空的链域的个数为( )
A. n-1 B. 2n-1
C. n+1 D. 2n+1
8.一棵左右子树均不空的二叉树在先序线索化后，其空指针域数为( )
A. 0 B. 1
C. 2 D.不确定
9.数组 A［５］［６］的每个元素占 5 个单元，将其按行优先次序存储在起始地址为 1000 的
连续的内存单元中，则元素 A［５，５］的地址为( )
A. 1140 B. 1145
C. 1120 D. 1125
10.求最短路径的 DIJKSTRA 算法的时间复杂度为( )
A. O(n) B. O(n+e)
C. O(n
2
) D. O(n×e)
11.对有 18 个元素的有序表作二分查找，则查找 A［3］的比较序列的下标依次为( )
A. 1，2，3 B. 9，5，2，3
C. 9，5，3 D. 9，4，2，3
12.快速排序算法在最好情况下的时间复杂度为( )
A. O(n) B. O(nlog
2
n)
C. O(n
2
) D. O(log
2
n)
13.下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是( )
资源评论
