精选文档
全国2011年1月自学考试数据结构导论试题
课程代码：02142
一、单项选择题本大题共15小题，每小题2分，共30分
在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未
选均无分。
1在顺序表中查找第i个元素，时间效率最高的算法的时间复杂度为

AO1
BO

COlog2

DO

2树形结构中，度为0的结点称为

A树根
B叶子
C路径
D二叉树
3已知有向图GVE，其中VV1V2V3V4V5V6V7，EV1V2，V1V3，V1V4，V2V5，
V3V5V3V6，V4V6，V5V7，V6V7，则图G的拓扑序列是


AV1V3V4V6V2V5V7
BV1V3V2V6V4V5V7
CV1V3V4V5V2V6V7
DV1V2V5V3V4V6V7
4有关图中路径的定义，表述正确的是

A路径是顶点和相邻顶点偶对构成的边所形成的序列
B路径是不同顶点所形成的序列
C路径是不同边所形成的序列
D路径是不同顶点和不同边所形成的集合
5串的长度是指

A串中所含不同字母的个数
B串中所含字符的个数
C串中所含不同字符的个数
D串中所含非空格字符的个数
6组成数据的基本单位是

A数据项
B数据类型
C数据元素
D数据变量
7程序段i
；x0；
doxx5i；i；while（i0）；
的时间复杂度为

AO（1）
BO（
）
CO（
2）
DO
3
8与串的逻辑结构不．同．的．数据结构是

A线性表
B栈
C队列
D树
可编辑
f精选文档
9二叉树的第i（i≥1）层上所拥有的结点个数最多为

A2i
B2i
C2i1
D2i1
10设单链表中指针p指向结点A，若要删除A的直接后继，则所需修改指针的操作为


Ap
extp
ext
ext
Bpp
ext
Cpp
ext
ext
Dp
extp
11下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是

A堆排序
B冒泡排序
C直接插入排序
D快速排序
12设字符串S1″ABCDEFG″，S2″PQRST″，则运算
SCONCATSUBSTRS12LENGTHS2SUBSTRS1LENGTHS22
后S的结果为

A″BCQR″
B″BCDEF″
C″BCDEFG″
D″BCDEFEF″
13在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并且A的左孩子的平衡因子为1，
右孩子的平衡因子为0，则使其平衡的调整方法为

ALL型
BLR型
CRL型
DRR型
14如果结点A有3个兄弟结点，而且B为A的双亲，则B的度为

A1
B3
C4
D5
15数据表A中每个元素距其最终位置较近，则最省时间的排序算法是

A堆排序
B插入排序
C直接选择排序
D快速排序
二、填空题本大题共13小题，每小题2分，共26分
r