《数据结构》试卷A
一、选择题（20小题，每题2分）
1、三个函数f,g,h分别为f(n)=100n3+n2+1000 , g(n)=25n3+5000n2, h(n)=n1.5+5000nlgn ，则下列关系不成立的是：
A． f(n)=O(g(n)) B. g(n)=O(f(n))
C. h(n)=O(n1.5)
D. h(n)=O(nlgn)
2、线性表是：
A.一个有限序列，可以为空；
B. 一个有限序列，不能为空；
C. 一个无限序列，可以为空；
D. 一个无序序列，不能为空。
3、线性表采用链式存储时，其地址：
A.必须是连续的；
B. 部分地址必须是连续的；
C. 定是不连续的；
D. 连续与否均可以。
4、对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。
插
入一个元素时大约要移动表中的（）个元素。
A.n/2
B. n+1/2
C. n-1/2
D. n
5、设单链表中指针p指着结点A,若要删除A之后的结点(若存在),则需修改指针的操作为（）。
A.p->next=(p->next)->next
B. p=p->next
C. p=(p->next)->next
D. p->next=p
6、栈的特点是：
A.先进先出
B. 后进先出
C. 进优于出
D. 出优于进
7、栈与队列都是：
A.顺序存储的线性结构
B. 链式存储的线性结构
C. 限制存取点的线性结构
D. 限制存取点的非线性结构
8、若一个栈的输入序列是：1，2，3，...,n，输出序列的第一个元素是n，则第i个输出元素是：
A.不确定
B. n-i
C. n-i+1
D. i
9、设字符串s1='ABCDEFG'，s2='PQRST'，则运算
s=CONCAT(SUB(s1,2,LEN(s2)),SUB(s1,LEN(s2),2))后的串值为：
A.‘BCDEF’
B. ‘BCDEFG’
C. ‘BCPQRST’
D. ‘BCDEFEF’
10、串的联结运算满足：
A.分配律
B. 交换律
C. 结合律
11、设有两个串p 和q ,求q 在p 中首次出现的位置的运算：
A.连接
B. 模式匹配
C. 求子串
D. 求串长
12、设二维数组A5*6的每个元素占4个字节，已知Loc(a00)=1000，A的终端结点a45的
起始地位是
A．1126 B. 1116 C. 1000 D. 1030
13、如果结点A有3个兄弟,而且B是A的双亲,则B的度是:
A. 3
B. 4
C. 5
D. 1
14、中序遍历的顺序是：
A.根结点，左子树，右子树
B. 左子树，根结点，右子树
C. 右子树，根结点，左子树
D. 左子树，右子树，根结点
15、某二叉树T有n个结点,设按某种顺序对T中的每个结点进行编号，编号值为1,2,...n.
且有如下性质:T中任意结点v,其编号等于左子树上的最小编号减一,而v的右子树的结点
中,其最小编号等于v左子树上结点的最大编号加一，这时按( )编号的.
A.中序遍历序列
B. 层次顺序
C. 后序遍历序列
D. 前序遍历序列
16、在下图所示的各无向图中，哪个不是连通图：
17、静态查找表与动态查找表的根本区别在于( )。
A. 它们的逻辑结构不一样
B. 施加在其上的操作不一样
C. 所包含的数据元素类型不一样
D.存储实现不一样
18、与其它查找方法相比，散列查找法的特点是：( )
(A) 通过关键字的比较进行查找
(B) 通过关键字计算元素的存储地址进行查找
(C) 通过关键字计算元素的存储地址并进行一定的比较进行查找
(D) 以上都不是
19、二分法查找存储结构
A．只适合于顺序 B.只适合于链式
C. 既适合于顺序，也适合于链式
D. 既不适合于顺序，也不适合于链式
20、在排序算法中，两两比较待排序的记录，当发现不满足顺序要求时，变更它们的相对
位置，这就是排序。
A．插入 B. 归并 C. 交换 D. 选择
二、判断题（10小题，每题2分，对的打√，错的打×）
1、数据元素是数据的最小单位。
（）
2、在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。
（）
3、设一数列的顺序为1,2,3,4,5,6, 通过栈结构可以排成的顺序必须是3,2,5,6,4,1.
（）
4、做退栈运算时应先判别,栈是否为空。
（）
5、子串定位函数的时间复杂度在最坏情况下为O（n*m），因此子串定位函数没有实际
使用价值。
（）
6、稀疏矩阵压缩存储后会失去随机存取的功能。
（）
7、哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较
近。
( )
8、二叉树是树的特殊形式。
( )
9、邻接表法只能用于有向图的存储，而邻接矩阵法对于有向图和无向图的存储都适
用。
（）
10、对于给定的关键字集合，以不同的次序插入到初始为空的二叉排序树中，得到的二
叉排序树是相同的。
（）
三、分析题（4小题，共40分）
11、何时选用顺序表、何时选用链表作为线性表的存储结构为宜?（8分）
12、对二叉树中的结点进行按层次顺序(每一层自左至右)的访问操作称为二叉树
的层次遍历，遍历所得到的结点序列称为二叉树层次序列。
现已知一棵二叉树的层次序列为ABCDEFGHIJ,中序序列为DBGEHJACIF，请画出此二叉树。
并写出此树的前序遍历和后序遍历序列。
（12分）
13、如下无向图，如果从V1开始搜索，写出它们的深度优先搜索序列和广度优先
搜索序列。
（12分）
深度优先搜索顶点序列：
广度优先搜索顶点序列：
4、对关键字序列{49 38 65 97 76 13 27 49}按从小到大进行快速排序，经过完整的一趟以后，我们得到的序列是？（8分）。