数据结构
试卷二
一、选择题（本题共20分,每题2分）
1.下面程序段的时间复杂度为（ ）。
for(i=1;i<=n;i++) for(j=1;j<=n;j++) s++;
A. O(n) B. O(n) C. O(2*n) D. O（i*j）
2. 线性表采用链式存储时，结点的存储地址（ ）。
A．必须是不连续的 B．部分地址必须是连续的
C．连续与否均可 D．和头结点的存储地址相连续 3.若让元素1，2，3依次进栈，则出栈时的序列不可能出现的是（ ）。
A．3，2，1 B．1，2，3 C．3，1，2 D．2，1，3 4.下面说法不正确的是( )
A．串S1=“this_is_a_string”的长度是16。 B．串S2=“this”是串S1的子串。
C．串S3=“thisis”在串S1中的位置是1。 D．串S4=“a”在串S1中的位置是9。
5. 一个非空广义表的表头（ ）。
A．不可能是子表 B．只能是子表
C．只能是原子 D．可以是子表或原子 6.完全二叉树( )满二叉树
A． 不一定是 B．一定不是 C．一定是 D．不能确定关系 7. 用链表表示线性表的优点是（ ）
A. 便于随机存取
B. 便于插入和删除操作
C. 花费的存储空间较顺序存储少 D. 元素的物理顺序与逻辑顺序相同
8.在一个具有n个顶点的无向图中，要连通全部顶点至少需要多少条边( )。
A．n(n-1)/2 B．n-1 C．n D．n+1
9.下列查找方法中哪一种不适合元素的链式存储结构( )
A．顺序查找 B．分块查找 C．二分查找 D．散列查找 10.下面哪种排序方法稳定性最好( )。
A．希尔排序 B．冒泡排序 C．快速排序 D．堆排序
2
二、填空题（本题共 20分）
1. 数据的逻辑结构可以分为两大类：_________和________。 2. 在二叉树的第i层上最多有___________个结点。 3. 无向图中恰好有__________条边，才称为无向完全图。
数据结构-试卷二
