全国2010年1月高等教育自学考试
数据结构试题
（课程代码：02331）
一、单项选择题(本大题共15小题，每小题2分，共30分)
在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。
1．若一个算法的时间复杂度用T(n)表示，其中n的含义是（ ） A．问题规模 C．循环层数
2．具有线性结构的数据结构是（ ） A．树 C．栈和队列
B．图 D．广义表 B．语句条数 D．函数数量
3．将长度为n的单链表连接在长度为m的单链表之后，其算法的时间复杂度为（ ） A．O(1) C．O(n)
B．O(m) D．O(m+n)
4．在带头结点的双向循环链表中插入一个新结点，需要修改的指针域数量是（ ） A．2个 C．4个
B．3个 ． D．6个
5．假设以数组A[60]存放循环队列的元素，其头指针是front=47，当前队列有50个元素，则队列的尾指针值为（ ） A．3 C．50
B．37 D．97
6．若栈采用链式存储结构，则下列说法中正确的是（ ） A．需要判断栈满且需要判断栈空 B．不需要判断栈满但需要判断栈空 C．需要判断栈满但不需要判断栈空 D．不需要判断栈满也不需要判断栈空
7．若串str=”Software”，其子串的数目是（ ） A．8 C．36
B．9 D．37
8．设有一个10阶的下三角矩阵A，采用行优先压缩存储方式，all为第一个元素，其存储地址为1000，每个元素占一个地址单元，则a85的地址为 （ ） A．1012
B．1017
C．1032
9．允许结点共享的广义表称为（ ） A．纯表 C．递归表
D．1039
B．线性表 D．再入表
10．下列数据结构中，不属于二叉树的是（ ） A．B树
B．AVL树
C．二叉排序树 D．哈夫曼树 11．对下面有向图给出了四种可能的拓扑序列，其中错误的是（ ） ．．
A．1，5，2，6，3，4 C．5，1，6，3，4，2
B．1，5，6，2，3，4 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．快速排序 C．冒泡排序
B．归并排序 D．直接插入排序
14．一个有序表为(1，3，9，12，32，41，45，62，75，77，82，95，100)，当采用折半查
找方法查找值32时，查找成功需要的比较次数是（ ） A．2 C．4
B．3 D．8
15．采用ISAM组织文件的方式属于（ ） A．链组织 C．散列组织
B．顺序组织 D．索引组织
二、填空题(本大题共10小题，每小题2分，共20分) 请在每小题的空格中填上正确答案。错填、不填均无分。 16．数据元素及其关系在计算机存储器内的表示称为_________。
17．长度为n的线性表采用单链表结构存储时，在等概率情况下查找第i个元素的时间复杂
度是_________。
18．下面是在顺序栈上实现的一个栈基本操作，该操作的功能是_________。 typedef struct{
DataType data[100]； int top； }SeqStack；
DataType f18(SeqStack*S) { if(StackEmpty(S))
Error(”Stack is empty”)； return S->data[S->top]； }
19．在串匹配中，一般将主串称为目标串，将子串称为_________。 20．已知广义表C=(a(b，c)，d)，则：tail(head(tail(C)))= _________。
21．用6个权值分别为6、13、18、30、7和16的结点构造一棵哈夫曼(Huffman)树，该树
的带权路径长度为_________。
22．已知有向图如下所示，其中顶点A到顶点C的最短路径长度是_________。
23．对序列{55，46，13，05，94，17，42}进行基数排序，第一趟排序后的结果是_________。 24．高度为3的3阶B-树最少的关键字总数是_________。
25．VSAM通常作为大型索引顺序文件的标准组织，其动态索引结构采用的是_________。 三、解答题(本大题共4小题，每小题5分，共20分) 26．假设二叉树的RNL遍历算法定义如下： 若二叉树非空，则依次执行如下操作： (1)遍历右子树； (2)访问根节点； (3)遍历左子树。
已知一棵二叉树如图所示，请给出其RNL遍历的结果序列。