10月自考数据结构02331试题及答案解析

全国2012年10月高等教育一、单项选择题(本大题共l5小题，每小题2分，共30分)1．一个算法的时间耗费的数量级称为该算法的( D ) D．时间复杂度2．顺序表便于( D ) D．按序号查找结点3．设带头结点的单循环链表的头指针为head，指针变量P指向尾结点的条件是( B ) B．p->next==head4．设以数组A[0..m-1]存放循环队列，front指向队头元素，rear指向队尾元素的下一个位置，则当前队列中的元素个数为( A ) A．(rear-front+m)％m5．下列关于顺序栈的叙述中，正确的是( A )A．入栈操作需要判断栈满，出栈操作需要判断栈空6．A是一个10×10的对称矩阵，若采用行优先的下三角压缩存储，第一个元素a0,0的存储地址为1，每个元素占一个存储单元，则a7,5的地址为( D ) D．347．树的后序遍历等价于该树对应二叉树的( C ) C．中序遍历8．使用二叉线索树的目的是便于( D ) D．查找一个结点的前趋和后继9．设无向图的顶点个数为n，则该图边的数目最多为( B) B．n(n-1)／2 10．可进行拓扑排序的图只能是（Ｃ）C．有向无环图11．下列排序方法中稳定的是（Ａ）A．直接插入排序12．下列序列不为．．堆的是（Ｃ）C．75,65,30,l5,25,4513．对线性表进行二分查找时，要求线性表必须是（Ｃ）C．顺序存储且按关键字有序14．分别用以下序列生成二叉排序树，其中三个序列生成的二叉排序树是相同的，不同．．的序列是（Ａ）A．(4,1,2,3,5)15．下列关于m阶B树的叙述中，错误．．的是（Ａ）A．每个结点至多有m个关键字二、填空题(本大题共10小题，每小题2分，共20分)16．数据元素之间的逻辑关系称为数据的__逻辑____结构。

17．在线性表中，表的长度定义为__数据元素的个数____。

18．用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1、2、3、4，为了得到1、3、4、2的出栈顺序，相应的S和X的操作序列为__ＳＸＳＳＸＳＸＸ____。

4月高等教育自学考试全国统一命题考试
数据构造试卷
(课程代码02331)
本试卷共8页，满分l00分，考试时间l50分钟。

考生答题注意事项：
1．本卷所有试题必须在答题卡上作答。

答在试卷上无效，试卷空白处和背面均可作草稿纸。

2．第一部分为选择题。

必须相应试卷上旳题号使用28铅笔将“答题卡”旳相应代码涂黑。

3．第二部分为非选择题。

必须注明大、小题号，使用0．5毫米黑色笔迹签字笔作答o 4．合理安排答题空间。

超过答题区域无效。

第一部分选择题
一、单选题：本大题共l5小题，每题2分，共30分。

在每题列出旳备选项中
只有一项是最符合题目规定旳，请将其选出。

1．数据构造不涉及旳内容是
A．数据旳元素来源 B．数据旳逻辑构造
C．数据旳存储构造 D．对数据施加旳操作
2．下列选项中，属于逻辑构造旳是
A．循环队列 B．二叉树 C．散列表 D．邻接表
3．下列选项中，属于顺序存储构造长处旳是
A．插入运算以便 B．删除运算以便
C．存储密度大 D．以便存储多种逻辑构造
4．某线性表中最常用旳操作是在最后一种元素之后插入一种元素和删除第一种元素，则下列存储构造中，最节省运算时间旳是
A．单链表 B．仅有头指针旳单循环链表
C．双向链表 D．仅有尾指针旳单循环链表
5．用不带头结点旳单链表存储队列，在进行删除运算时
A．仅修改头指针 B．仅修改尾指针
C．头、尾指针一定都要修改 D．头、尾指针也许都要修改。

⾃考数据结构历年试题及答案全国2001年10⽉⾼等教育⾃学考试数据结构试题课程代码：02331 第⼀部分选择题(30分)7．若⽬标串的长度为n ，模式串的长度为[n/3]，则执⾏模式匹配算法时，在最坏情况下的时间复杂度是（ C ） A ．O （n 3） B ．O （n ） C ．O （n 2） D ．O （n 3） 8．⼀个⾮空⼴义表的表头（ D ）A ．不可能是⼦表B ．只能是⼦表C ．只能是原⼦D ．可以是⼦表或原⼦ 9对应的稀疏矩阵是（ A ）A.08067000000050400000--B. 0806 7000 5040 0000 0300 --0000 --D. 0806 0000 7000 5040 0300 --10．在⼀棵度为3的树中,度为3的结点个数为2,度为2 的结点个数为1,则度为0的结点个数为( C )A．4 B．5 C．6 D．711．在含n个顶点和e条边的⽆向图的邻接矩阵中,零元素的个数为( D ) A．e B．2e C．n2－e D．n2－2e12．假设⼀个有n个顶点和e条弧的有向图⽤邻接表表⽰,则删除与某个顶点v i相关的所有弧的时间复杂度是( C )A．O(n) B．O(e) C．O(n+e) D．O(n*e)13．⽤某种排序⽅法对关键字序列（25，84，21，47，15，27，68，35，20）进⾏排序时，序列的变化情况如下：20，15，21，25，47，27，68，35，8415，20，21，25，35，27，47，68，8415，20，21，25，27，35，47，68，84则所采⽤的排序⽅法是（ D ）A．选择排序B．希尔排序C．归并排序D．快速排序14．适于对动态查找表进⾏⾼效率查找的组织结构是（C ）A．有序表B．分块有序表C．三叉排序树D．线性链表15．不定长⽂件是指（B ）A．⽂件的长度不固定B．记录的长度不固定C．字段的长度不固定D．关键字项的长度不固定第⼆部分⾮选择题（共70分）⼆、填空题（本⼤题共10⼩题，每⼩题2分，若有两个空格，每个空格1分，共20分）不写解答过程，将正确的答案写在每⼩题的空格内。

return ;
}
if ( L -> length >= ListSize ){
printf (" overflow ");
return ;
}
for ( j - L -> length -1; j >= i -1; j --)
L ->data [ j +1]= L -> data [ j ]; //从最后一个元素开始逐一后移
线性表的基本运算
上述运算仅仅是线性表的基本运算，不是其全部运 算。因为对不同问题的线性表，所需要的运算可能不同。 因此，对于实际问题中涉及其他更为复杂的运算，可用 基本运算的组合来实现。
线性表的基本运算
【例2.1】假设有两个线性表 LA 和 LB 分别表示两个 集合 A 和 B ，现要求一个新集合 A = A∪B 。
线性表的逻辑定义
数据元素“一个接一个的排列”的关系叫做 线性关系，线性关系的特点是“一对一”，在计 算机领域用“线性表”来描述这种关系。另外， 在一个线性表中数据元素的类型是相同的，或者 说线性表是由同一类型的数据元素构成的，如学 生情况信息表是一个线性表，表中数据元素的类 型为学生类型；一个字符串也是一个线性表：表 中数据元素的类型为字符型等等。
,
a2
i
,…,
ai-1
,
a．aii++1．1 , ．…,
an
)
an
线性表n的-1逻辑结an构和存储结构都发…生了相应的变化， 与插入运算相反，插…入是向后移动元素，而删除运算则
是向前移M动AX元-1 素，除非i=n 时直接删除终端元素，不需移
动元素。
删除前
删除后