一、单项选择题
1 某算法的时间复杂度是    O(n2 ) ，表明该算法（    ）。
A 问题规模是    n2    B 问题规模与    n2 成正比
C 执行时间等于    n2    D 执行时间与    n2 成正比
2、关于数据结构的描述，不正确的是（    ）。
A数据结构相同，对应的存储结构也相同。
B数据结构涉及数据的逻辑结构、存储结构和施加其上的操作等三个方面。
C数据结构操作的实现与存储结构有关。
D定义逻辑结构时可不考虑存储结构。
3、按排序策略分来，起泡排序属于（    ）。
A    插入排序    B    选择排序    C    交换排序    D    归并排序
4、利用双向链表作线性表的存储结构的优点是（    ）。
A    便于进行插入和删除的操作    B  提高按关系查数据元素的速度
C    节省空间    D    便于销毁结构释放空间
5、一个队列的进队顺序为    1,2,3,4    ，则该队列可能的输出序列是（    ）。
A 1,2,3,4    B 1,3,2,4    C 1,4,2,3    D 4,3,2,1
6、 Dijkstra    算法是按（    ）方法求出图中从某顶点到其余顶点最短路径的。
A按长度递减的顺序求出图的某顶点到其余顶点的最短路径
B按长度递增的顺序求出图的某顶点到其余顶点的最短路径
C通过深度优先遍历求出图中从某顶点到其余顶点的所有路径
D通过广度优先遍历求出图的某顶点到其余顶点的最短路径
7、字符串可定义为    n（ n≥ 0）个字符的有限（    ）。其中， n 是字符串的长度，表明字符串
中字符的个数。
A    集合    B    数列    C    序列    D聚合
8、在二维数组    A[9][10]    中，每个数组元素占用    3 个存储单元，从首地址    SA 开始按行连续
存放。在这种情况下，元素    A[8][5]    的起始地址为（    ）。
A SA+141    B SA+144    C SA+222    D SA+255
9、已知广义表为    L(A(u,v,(x,y),z),C(m,(),(k,l,n),(())),((())),(e,(f,g),h))    ，则它
的长度是（    ）。
A2    B3    C4    D5
10.    对于具有  n(n>1) 个顶点的强连通图，其有向边条数至少有    _____。
完全二叉树算法A. n+1    B. n    C. n-1    D. n-2
11.一个递归算法必须包括  __________ 。
A.  递归部分  B .  结束条件和递归部分  C.  迭代部分  D.  结束条件和迭代部分
12.从逻辑上看可以把数据结构分为__________两大类。
A．动态结构、静态结构B．顺序结构、链式结构
C．线性结构、非线性结构    D    ．初等结构、构造型结构
13、若在长度为    n 的顺序表的表尾插入一个新元素的渐进时间复杂度为（    ）。
A O(n)    B O(1)    C O(n 2)    D O(log 2n)
14.采用顺序搜素方式搜索长度为 n 的线性表时，在等概率情况下，搜索成功时的平均搜索长度为 __________。
A. n    B. n/2    C . (n+1)/2    D. (n-1)/2
15、非空的循环单链表    first    的链尾结点（由    p 所指向）满足（    ）。
A p->link==NULL;    B P==NULL;

第1页，共 7页

C p->link==first;    D p==first;
16、用  S 表示进栈操作，用    X 表示出栈操作，若元素的进栈顺序是    1234，为了得到    1342
的出栈顺序，相应的    S 和 X 的操作序列为（    ）。
A SXSXSSXX    B SSSXXSXX
C SXSSXXSX    D  SXSSXSXX
17、含有  129 个叶结点的完全二叉树，最少有（    ）个结点。
A 254    B 255    C  257    D 258
18、一个有向图    G的邻接表存储如图    （ 1）所示，现按深度优先搜索方式从顶点    A 出发执行
一次遍历，所得的顶点序列是（    ）。
A 1,2,3,4,5
B  1,2,3,5,4
C 1,2,4,5,3
D 1,2,5,3,4
19、树最合适用来表示（
）。
A 有序数据元素
B 元素之间具有分支层次关系的数据
C 无序数据元素
D 元素之间无联系的数据
20、一棵有    124 个叶结点的完全二叉树最少有（    ）个结点。
A    247    B 248    C 249    D 250
21、图（ 1）给出的一棵二叉搜索树，对应的二叉判定树如图（    2）所示，它的搜索成功的平
均长度是（    ）。
A 21/7    B 28/7    C 15/6    D 16/6
图（ 1）二叉搜索树    图（ 2）二叉判定树
23、对 5 个不同的数据元素进行直接插入排序，最大需要进行（    ）次比较。
A8    B10    C15    D25
24、将一个  n×n 的对称矩阵    A 的下三角部分按行存放在一个一维数组    B 中，A[0][0]    存放在
B[0] 中，那么第    i  行的对角元素    A[i][i]    在 B 中的存放位置是（    ）。
A  (i+3)*i/2    B (i+1)*i/2    C (2n-i+1)*i/2    D (2n-i-1)*i/2
25、已知广义表为    L(A(u,v,(x,y),z),C(m,(),(k,l,n),(())),((())),(e,(f,g),h))    ，则
它的深度是（    ）。
A2    B3    C    4    D5
26、顺序搜索法适合于存储结构为（    ）的线性表。
A    散列存储    B    顺序存储或链式存储    C 压缩存储    D  索引存储
27、采用折半搜索方式搜索一个长度为    n 的有序顺序表时，其平均搜索长度为（    ）。
A O(n)    B O(log    2n)    C O(n 2)    D O(nlog    2n)
28、 n 个结点的线索二叉树中，线索的数目是（    ）。
A n-1    B n+1    C 2n    D 2n-1
29、若数据元素序列    {11,12,13,7,8,9,23,4,5}    是采用下列排序方法之一得到的第二趟排序
后的结果，则该排序方法只能是（    ）。
A    插入排序    B    选择排序    C    交换排序    D    归并排序