全国2012年1月高等教育自学考试数据结构试题.docx

全国2012年1
87S
月高等教育自学考试
数据结构试题
课程代码：02331
、单项选择题（本大题共15小题，每小题
2分，共30分）
在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未
选均无分。
.每个结点有且仅有一个直接前趋和多个（或无）直接后继（第一个结点除外）的数据结构称为（ ）


.某线性表中最常用的操作是在最后一个元素之后插入元素和删除第一个元素，则最节省运算时间的存储结构是 （ ）


.已知一个栈的入栈序列是 1, 2, 3,

-i+l
.下面关于串的叙述中，正确的是（




♦, n,其输出序列为 pi, p2, p3…
-i

）


pn,若P1是n,则Pi是（ ）
.无向完全图G有n个结点，则它的边的总数为（ ）
（n-1）
D.(n-1)
(n-1)/2
.若一棵二叉树有10个度为2的结点，5个度为1的结点，则度为0的结点数是（ ）




.如图所示，在下面的 4个序列中，不狞深度优先遍历的序列是（ ）




.无论待排序列是否有序，排序算法时间复杂度都是 O（n2）的排序方法是（ ）
A. 快速排序 B. 归并排序
C. 冒泡排序 D. 直接选择排序
已知二叉排序树 G ，要输出其结点的有序序列，则采用的遍历方法是（ ）
A. 按层遍历 B. 前序遍历
C. 中序遍历 D. 后序遍历
用 ISAM 和 VSAM 组织的文件都属于（ ）
A. 散列文件 B. 索引顺序文件
C. 索引非顺序文件 D. 多关键字文件
（15， 9， 7， 8， 20， -1 ， 4）进行排序，第一趟排序后的序列变为 （4， 9， -1 ， 8， 20， 7， 15） ，则采用的排序
方法是（ ）
A. 选择 B. 快速
C. 希尔 D. 冒泡
. 当采用分块查找时，数据的组织方式为（ ）
数据分成若干块，每块内数据有序
数据分成若干块，每块中数据个数必须相同
数据分成若干块，每块内数据有序，块间是否有序均可
数据分成若干块，每块内数据不必有序，但块间必须有序
. 下述编码中不是前缀码的是（ ）
A.（00 ， 01， 10， 11） B.（0 ， 1， 00， 11）
C.（0， 10， 110， 111） D.（1 ， 01， 000， 001）
.若一个栈以向量 V[1..n] 存储，初始栈顶指针 top 为 n+l ，则 x 进栈的正确操作是（ ）
=top-1 ； V[top]=x [top]=x ； top=top+1
=top+1 ； V[top]=x [top]=x ； top=top-1
. 在一个以 head 为头结点