后继有人近义词:数据结构试题

一、单项选择题（10）
1、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为( )。(1≤i≤n+1)
A．O(0) B．O(1) C.O(n) D．O(n2)
2、 若在线性表中采用折半查找法查找元素，该线性表应该( )。
A．元素按值有序
B．采用顺序存储结构“
C．元素按值有序，且采用顺序存储结构
D．元素按值有序，且采用链式存储结构
3、 已知一算术表达式的中缀形式为A＋B *C-D/E，后缀形式为ABC *+DE/-，其前缀形式为( )。
A. –A+B*C/DE B. –A+B*CD/E C.-+*ABC/DE D.-+A*BC/DE
4、下述图的遍历算法中正确的说法是：
A． BFS只适应于无向图 B. BFS只适应于有向图
C. 可能需要多次调用BFS算法或DFS算法，方可遍历一个无向图
D. 只需一次调用BFS算法或DFS算法，即可遍历一个无向图
5、 利用逐点插入法建立序列(50，72，43，85，75，20，35，45，65，30)对应的二叉排序树以后，查找元素35要进行( )元素间的比较。
A．4次 B．5次 C. 7次 D．10次
6、对二叉排序树进行( )遍历，可以得到该二叉树所有结点构成的排序序列。
A. 前序 B．中序 C．后序 D．按层次
7、 具有n个顶点的有向图最多有( )条边。
A．n B．n(n—1) C n(n+1) D. n2
8、算法的时间复杂度取决于
A. 问题的规模 B .待处理数据的初态
C. 待处理数据的初态 D. both a and b
9、设输入序列为A、B、C、D，借助一个栈得到的输出序列不可能是：
A. D、C、A、B B. D、C、B、A
C. B、C、D、A D. C、B、D、A
10、.假定有k个关键字互为同义词,若用线性探测法把这k个关键字存入散列表中,至少要进行多少次探测?
A .k-1 B . k
C .k=1 D. k(k+1)/2