全国2008年1月高等教育自学考试

数据结构试题

课程代码：02331

一、单项选择题（本大题共15小题，每小题2分，共30分）

在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。

1.逻辑上通常可以将数据结构分为（　　　）

A.动态结构和静态结构                               B.顺序结构和链式结构

C.线性结构和非线性结构                            D.初等结构和组合结构

2.在下列对顺序表进行的操作中，算法时间复杂度为O(1)的是（　　　）

A.访问第i个元素的前驱（1< ）

B.在第i个元素之后插入一个新元素( )

C.删除第i个元素( )

D.对顺序表中元素进行排序

3.假设带头结点的单向循环链表的头指针为head,则该链表为空的判定条件是（　　　）

A.head= =NULL                                           B.head–>next= =NULL

C.head!=NULL                                            D.head–>next= =head

4.已知栈的最大容量为4。若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行,则可能出现的出栈序列为（　　　）

A.5，4，3，2，1，6                                   B.2，3，5，6，1，4

C.3，2，5，4，1，6                                   D.1，4，6，5，2，3

5.与线性表相比，串的插入和删除操作的特点是（　　　）

A.通常以串整体作为操作对象                     B.需要更多的辅助空间

C.算法的时间复杂度较高                            D.涉及移动的元素更多

6.假设以三元组表表示稀疏矩阵，则与如图所示三元组表对应的4×5的稀疏矩阵是（注：矩阵的行列下标均从1开始）（　　　）

A.                                 B.

C.                                 D.

7.以下有关广义表的表述中，正确的是（　　　）

A.由0个或多个原子或子表构成的有限序列

B.至少有一个元素是子表

C.不能递归定义

D.不能为空表

8.树的先根序列等同于与该树对应的二叉树的（　　　）

A.先序序列                                                 B.中序序列

C.后序序列