第一章
1．在数据结构中，从逻辑上可以把数据结构分为（ C ）
A •动态结构和静态结构 B.紧凑结构和非紧凑结构
C.线性结构和非线性结构
D.内部结构和外部结构
2. 在数据结构中,与所使用的计算机无关的是（ A ）
A. 逻辑结构
B. 存储结构
C. 逻辑和存储结构
D. 物理结构
3. _________________________ 下面程序的时间复杂度为O（mn）。
for （int i=1; i<=m; i++）
for （int j=1; j<=n; j++ ）
S+=i
第二章线性表
链表不具备的特点是（A）
A 可以随机访问任一结点（顺序）
B 插入删除不需要移动元素
C 不必事先估计空间
D 所需空间与其长度成正比
2. 不带头结点的单链表head为空的判定条件为（A ）,带头结点的单链表head为空的判定条件为（ B ）
A head==null
B head->next==null
C head->next==head
D head!=null
3. 在线性表的下列存储结构中，读取元素花费时间最少的是（D）
A 单链表
B 双链表
C 循环链表
D 顺序表
4. 对于只在表的首、尾两端进行手稿操作的线性表，宜采用的存储结构为（C）
A 顺序表
B 用头指针表示的单循环链表
C 用尾指针表示的单循环链表
D 单链表
5. 在一个具有n 个结点的有序单链表中插入一个新的结点，并保持链表元素仍然有序，则操作
的时间复杂度为（ D ）
A O（1）
B O（log 2n）
C O（n2）
D O（n）
6. 在一个长度为n
（n>1）的单链表上，设有头和尾两个指针，执行（B）操作与链表的长度有关
A 删除单链表中第一个元素
B 删除单链表中最后一个元素
C 在第一个元素之前插入一个新元素
D 在最后一个元素之后插入一个新元素
7. 与单链表相比，双向链表的优点之一是（D）
A 插入删除操作更简单
B 可以进行随机访问
C 可以省略表头指针或表尾指针
D 顺序访问相邻结点更容易
8. 若list 是某带头结点的循环链表的头结点指针，则该链表最后那个链结点的指针域
（头
结点的地址）中存放的是（ B ）
A list 的地址
B list 的内容
C list 指的链结点的值
D 链表第一个链结点的地址
9. 若listl和Iist2分别为一个单链表与一个双向链表的第一个结点的指针，则（B ）
A Iist2比listl占用更多的存储单元
B listl与Iist2占用相同的存储单元
C list1 和list2 应该是相同类型的指针变量
D 双向链表比单链表占用更多的存储单元
10. 链表中的每个链结点占用的存储空间不必连续，这句话正确吗？（不正确）
11. 某线性表采用顺序存储结构，元素长度为4，首地址为100，则下标为12的（第13个）元素的存储地址为14& V 100+4*12=148
11. 在顺序表的（最后一个结点之后）插入一个新的数据元素不必移动任何元素。
12. 若对线性表进行的操作主要不是插入删除，则该线性表宜采用（顺序）存储结构，若
频繁地对线性表进行插入和删除操作，则该线性表宜采用（链）存储结构。
13、一个顺序表所占用存储空间的大小与（B）无关。
A •表的长度B•元素的存放顺序 C.元素的类型 D.元素中各的类型
14、设存储分配是从低地址到高地址进行的。若每个元素占用4个存储单元，则某元素
的地址是指它所占用的单元的（A）。
A. 第1 个单元的地址
B. 第2 个单元的地址
C. 第3个单元的地址
D. 第4个单元的地址
15、若线性表采用顺序存储结构，每个元素占用 4 个存储单元，第1 个元素的存储地址为100，则第12个元素的存储地址是（B）。
A. 112
B. 144
C.148
D. 412
16、若长度为n 的线性表采用顺序存储结构，在表的第i 个位置插入一个数据元素，i 的合法值
应该是（ D ）。
A. i>0
B.i<=n
C.1<=i<=n
D. 1<=i<=n+1
17、若长度为n的非空线性表采用顺序存储结构，删除表的第i个数据元素，i的合法值应
该是（ C ）。
A. i>0
B.y<=n
C.1<=i<=n
D. d<=i<=i+1
18、若长度为n的非空线性表采用顺序存储结构，删除表的第i个数据元素，首先需要
移动表中（ B ）个数据元素。
A. n-i
B.n+i
C. n-i+1
D. n-i-1
19、若长度为n的非空线性表采用顺序存储结构，在表的第i个位置插入一个数据元素，首先需要移动表中（ C ）个数据元素。
A. i
B. n+i
C.n-i+1
D.n-i-1
20、若频繁地对线性表进行插入和删除操作，该线性表应该采用（ C ）存储结构。
A.散列
B.顺序
C.链式
D.索引
21、链表中的每一个链结点所占用的存储单元（ B ）。
A.不必连续
B.—定连续
C.部分连续
D.连续与否无所谓
22、在一个具有n 个链结点的线性链表中查找某一个链结点，若查找成功，需要平均比较
（C）个链结点。
A. n
B. n/2
C.（n+1）/2
D. （n-1）/2
23、给定具有n 个元素的顺序表，建立一个有序线性链表的时间复杂度为（C）。
A. O（1）
B.O（n）
C.O（n2）
D. O（log 2 n）
24、在非空线性链表中由p所指的链结点后面插入一个由q所指的链结点的过程是依次执行
（ B ）。
A. q->next=p; p->next=q;
B. q->next=p->next; p->next=q;
C. q->next=p->next; p =q;
D. p->next=q; q->next=p;
25、若删除非空线性链表中由p 所指的链结点的直接后继链结点的过程过程是依次执行
（B）。
A. r=p->next; p->next=r; free（r）;
B. r=p->next; p->next=r->next; free（r）;
C. r=p->next; p->next=r->next; free（p）;
D. p->next=p->next->next; free（p）;
