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

数据结构试题课程代码:02331一、单项选择题(本大题共15小题,每小题2分,共30分)在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内.
错选、多选或未选均无分.

1.
若一个算法的时间复杂度用T(n)表示,其中n的含义是()A.
问题规模B.
语句条数C.
循环层数D.
函数数量2.
具有线性结构的数据结构是()A.
树B.
图C.
栈和队列D.
广义表3.
将长度为n的单链表连接在长度为m的单链表之后,其算法的时间复杂度为()A.
O(1)B.
O(m)C.
O(n)D.
O(m+n)4.
在带头结点的双向循环链表中插入一个新结点,需要修改的指针域数量是()A.
2个B.
3个.
C.
4个D.
6个5.
假设以数组A[60]存放循环队列的元素,其头指针是front=47,当前队列有50个元素,则队列的尾指针值为()A.
3B.
37C.
50D.
976.
若栈采用链式存储结构,则下列说法中正确的是()A.
需要判断栈满且需要判断栈空B.
不需要判断栈满但需要判断栈空C.
需要判断栈满但不需要判断栈空D.
不需要判断栈满也不需要判断栈空7.
若串str="Software",其子串的数目是()A.
8B.
9C.
36D.
378.
设有一个10阶的下三角矩阵A,采用行优先压缩存储方式,all为第一个元素,其存储地址为1000,每个元素占一个地址单元,则a85的地址为()A.
1012B.
1017C.
1032D.
10399.
允许结点共享的广义表称为()A.
纯表B.
线性表C.
递归表D.
再入表10.
下列数据结构中,不属于二叉树的是()A.
B树B.
AVL树C.
二叉排序树D.
哈夫曼树11.
对下面有向图给出了四种可能的拓扑序列,其中错误的是()A.
1,5,2,6,3,4B.
1,5,6,2,3,4C.
5,1,6,3,4,2D.
5,1,2,6,4,312.
以v1为起始结点对下图进行深度优先遍历,正确的遍历序列是()A.
v1,v2,v3,v4,v5,v6,v7B.
v1,v2,v5,v4,v3,v7,v6C.
v1,v2,v3,v4,v7,v5,v6D.
v1,v2,v5,v6,v7,v3,v413.
下列排序算法中不稳定的是()A.
快速排序B.
归并排序C.
冒泡排序D.
直接插入排序14.
一个有序表为(1,3,9,12,32,41,45,62,75,77,82,95,100),当采用折半查找方法查找值32时,查找成功需要的比较次数是()A.
2B.
3C.
4D.
815.
采用ISAM组织文件的方式属于()A.
链组织B.
顺序组织C.
散列组织D.
索引组织二、填空题(本大题共10小题,每小题2分,共20分)请在每小题的空格中填上正确答案.
错填、不填均无分.
16.
数据元素及其关系在计算机存储器内的表示称为_17.
长度为n的线性表采用单链表结构存储时,在等概率情况下查找第i个元素的时间复杂度是_18.
下面是在顺序栈上实现的一个栈基本操作,该操作的功能是_typedefstruct{DataTypedata[100];inttop;}SeqStack;DataTypef18(SeqStack*S){if(StackEmpty(S))Error("Stackisempty");returnS->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遍历的结果序列.
27.
已知一个无向图G=(V,E),其中V={A,B,C,D,E,F},邻接矩阵表示如下所示.
请回答下列问题:(1)请画出对应的图G.
(2)画出图G的邻接表存储结构.
28.
已知一组待排记录的关键字序列为(16,12,18,60,15,36,14,18,25,85),用堆排序方法建小根堆,请给出初始建堆后的序列.