全国2001年10月高等教育自学考试
数据结构试题
课程代码：02331第一部分选择题30分
一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个选项中只
有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。
1．算法指的是（）
A．计算机程序
B．解决问题的计算方法
C．排序算法
D．解决问题的有限运算序列
2．线性表采用链式存储时，结点的存储地址（）
A．必须是不连续的
B．连续与否均可
C．必须是连续的
D．和头结点的存储地址相连续
3．将长度为
的单链表链接在长度为m的单链表之后的算法的时间复杂度为（）
A．O（1）
B．O（
）C．O（m）D．O（m
）
4．由两个栈共享一个向量空间的好处是：（）
A．减少存取时间，降低下溢发生的机率
B．节省存储空间，降低上溢发生的机率
C．减少存取时间，降低上溢发生的机率
D．节省存储空间，降低下溢发生的机率
5．设数组datam作为循环队列SQ的存储空间，fro
t为队头指针，rear为队尾指针，则执
行出队操作后其头指针fro
t值为（）
A．fro
tfro
t1
B．fro
tfro
t1m1
C．fro
tfro
t1m
D．fro
tfro
t1m
6．如下陈述中正确的是（）
A．串是一种特殊的线性表
B．串的长度必须大于零
C．串中元素只能是字母
D．空串就是空白串
7．若目标串的长度为
，模式串的长度为
3，则执行模式匹配算法时，在最坏情况下的
时间复杂度是（）

A．O（）
3
B．O（
）
C．O（
2）
D．O（
3）
8．一个非空广义表的表头（）
A．不可能是子表
B．只能是子表
C．只能是原子
D．可以是子表或原子
9．假设以带行表的三元组表表示稀疏矩阵，则和下列行表
02335
f对应的稀疏矩阵是（
）
0806

7
000
A0000
5040
0000
0806

7
000
B5040

0
000
0300
0806

0
000
C0200
5040
0000
0806

0
000
D7000
5040
0300
10．在一棵度为3的树中度为3的结点个数为2度为2的结点个数为1则度为0的结点个
数为
A．4
B．5
C．6
D．7
11．在含
个顶点和e条边的无向图的邻接矩阵中零元素的个数为
A．e
B．2e
C．
2－e
D．
2－2e
12．假设一个有
个顶点和e条弧的有向图用邻接表表示则删除与某个顶点vi相关的所有弧的时间复杂度是
A．O

B．Oe
C．O
eD．O
e
13．用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，
序列的变化情况如下：
20，15，21，25，47，27，68，35，84
15，20，21，25，35，27，47，68，84
15，20，21，25，27，35，47，68，84
则所采用的r