全国2010年1月高等教育自学考试
数据结构试题
课程代码：02331

一、单项选择题(本大题共15小题，每小题2分，共30分)
在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。
1．若一个算法的时间复杂度用T(n)表示，其中n的含义是（ ）
A．问题规模
B．语句条数
C．循环层数
D．函数数量

2．具有线性结构的数据结构是（ ）
A．树
B．图
C．栈和队列
D．广义表

3．将长度为n的单链表连接在长度为m的单链表之后，其算法的时间复杂度为（ ）
A．O(1)
B．O(m)
C．O(n)
D．O(m+n)

4．在带头结点的双向循环链表中插入一个新结点，需要修改的指针域数量是（ ）
A．2个
B．3个 ．
C．4个
D．6个
5．假设以数组A[60]存放循环队列的元素，其头指针是front=47，当前队列有50个元素，则队列的尾指针值为（ ）
A．3
B．37
C．50
D．97

6．若栈采用链式存储结构，则下列说法中正确的是（ ）
A．需要判断栈满且需要判断栈空
B．不需要判断栈满但需要判断栈空
C．需要判断栈满但不需要判断栈空
D．不需要判断栈满也不需要判断栈空

7．若串str=”Software”，其子串的数目是（ ）
A．8
B．9
C．36
D．37

8．设有一个10阶的下三角矩阵A，采用行优先压缩存储方式，a_ll为第一个元素，其存储地址为1000，每个元素占一个地址单元，则a₈₅的地址为 （ ）
A．1012
B．1017
C．1032
D．1039

9．允许结点共享的广义表称为（ ）
A．纯表
B．线性表
C．递归表
D．再入表

10．下列数据结构中，不属于二叉树的是（ ）
A．B树
B．AVL树
C．二叉排序树
D．哈夫曼树

11．对下面有向图给出了四种可能的拓扑序列，其中错误的是（ ）

A．1，5，2，6，3，4
B．1，5，6，2，3，4
C．5，1，6，3，4，2
D．5，1，2，6，4，3

12．以v1为起始结点对下图进行深度优先遍历，正确的遍历序列是（ ）

A．v1，v2，v3，v4，v5，v6，v7
B．v1，v2，v5，v4，v3，v7，v6
C．v1，v2，v3，v4，v7，v5，v6
D．v1，v2，v5，v6，v7，v3，v4

13．下列排序算法中不稳定的是（ ）
A．快速排序
B．归并排序
C．冒泡排序
D．直接插入排序

14．一个有序表为(1，3，9，12，32，41，45，62，75，77，82，95，100)，当采用折半查找方法查找值32时，查找成功需要的比较次数是（ ）
A．2
B．3
C．4
D．8

15．采用ISAM组织文件的方式属于（ ）
A．链组织
B．顺序组织
C．散列组织
D．索引组织