全国1月高等教育自学考试数据结构试题及答案

全国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遍历的结果序列。

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4