全国自考数据结构2014-4

全国2014年4月自学考试数据结构试题

课程代码：02331

请考生按规定用笔将所有试题的答案涂、写在答题纸上。

选择题部分

注意事项：

1.答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。

2.每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。如需改动，用橡皮擦干净后，再选涂其他答案标号。不能答在试题卷上。

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

在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸”的相应代码涂黑。错涂、多涂或未涂均无分。 1. 与数据存储结构无关的概念是（ A ）P3-4 ．．A．栈 C．顺序表

B．链表 D．二叉链表

2. 顺序表中有10个数据元素，若第一个元素的存储地址是1000，则最后一个元素地址是1036，第5个元素的地址是（B） A．1010 C．1018

B．1016 D．1019

3．设栈的初始状态为空，元素1、2、3、4、5、6依次入栈，得到的出栈序列是（2,4,3,6,5,1）,则栈的容量至少是（B） A．2 C．4

4．下列关于队列的叙述中,错误的是（ D ）P37 ．．

A．队列是一种先进先出的线性表 B．队列是一种后进后出的线性表

C．循环队列中进行出队操作时要判断队列是否为空 D．在链队列中进行入队操作时要判断队列是否为满

B．3 D．6

5．对稀疏矩阵进行压缩存储的目的是（ B ）P63

A．便于运算 C．便于输入输出

B．节省存储空间 D．降低时间复杂度

6．一棵二叉树的第7层上最多含有的结点数为（B）P72

A．14 C．127

7．下列选项为完全二叉树的是（A）P73

B．64 D．128

8．用邻接表表示n个顶点e条边的无向图,其边表结点的总数是（ C ） A．n×e C．2e

B．e D．n+e

9．无向图中所有顶点的度数之和与所有边数之比是（ C ）P101 A．1/2 C．2

B．1 D．4

10．采用邻接矩阵存储图时,广度优先搜索遍历算法的时间复杂度为（ C ）P113 A．O（n） C．O（n2）

B．O（n+e） D．O（n3）

11．对序列（15,9,7,8,20,-1,4）进行排序,若一趟排序后的结果为（-1,15,9,7,8,20,4）,则采用的排序方法是（ D ） A．归并排序 C．直接选择排序

B．快速排序 D．冒泡排序

12．比较次数与待排序列初始状态无关的排序方法是（D）P151 A．快速排序 C．直接插入排序

B．冒泡排序 D．直接选择排序

13．查找较快,且插入和删除操作也比较方便的查找方法是（ A ）P174 A．分块查找 C．顺序查找

B．二分查找 D．折半查找

14．下列关于m阶B树的叙述中,错误的是（ D ）P182 ．．A．根结点至多有m棵子树 B．所有叶子都在同一层次上 C．每个非根内部结点至少有

棵子树

D．结点内部的关键字可以是无序的

15．在散列查找中处理冲突时,可以采用开放定址法。下列不是开放定址法的是（ D ）P196-197

A．线性探查法 C．双重散列法

B．二次探查法 D．拉链法

非选择题部分

注意事项：

用黑色字迹的签字笔或钢笔将答案写在答题纸上,不能答在试题卷上。

二、填空题（本大题共10小题,每小题2分,共20分） 16．数据结构研究的内容包括数据的逻辑结构、存储结构和数据的运算。P1

17．头指针为L的带头结点的双循环链表,结点的前趋指针域为prior,后继指针域为next,判断

该链表为空的条件是L->prior==L。P27

18．普里姆（Prim）算法完成的功能是求图的最小生成树。P116

19．若三维数组a［4］［5］［6］的基地址是100,每个元素占用2个存储单元,则数组a中最

后一个元素的存储地址是338。P60

20．二叉树的线索链表利用空指针域存放遍历时得到的前趋或后继结点的指针。P79 21．采用邻接矩阵存储n个顶点e条边的无向图,其邻接矩阵的大小为n*n。P103 22．若无向图中任意两个不同的顶点间都有路径,则称该图为连通图。P102 23．在直接插入排序、冒泡排序和快速排序中,平均时间性能最佳的是快速排序。P149 24．假设m个关键字互为同义词,若用线性探查法把这m个关键字存入散列表中,至少要进

行的探查次数是m(m+1)/2。P196

25．顺序查找算法的平均时间复杂度为O(n)。P170

三、解答题（本大题共4小题,每小题5分,共20分）

26．用X代表进栈操作,S代表出栈操作。给出利用栈将字符串\改变为\的操作

步骤。例如：将\改变为\则其操作步骤为XXSXSS。 解：XSXXSSXXSS

27.假定电文字符集为{A,B,C,D,E,F,G,H},它们在电文中出现的次数分别为{19,6,12,5,38,3,13,4）,为这8个字符设计哈夫曼编码。画出哈夫曼树并给出编码。要求在构造哈夫曼树的过程中,权值较小结点放在左侧,编码时左分支生成代码0,右分支生成代码1。 解：哈夫曼树如下，

90 38

E 25 12 C 13 G 18 A 11 52

37 19 7 F 3

哈夫曼编码：

H 4

D 5

B 6

A：111 C：100 E：0 G：101 B：11011 D：11010 F：11000 H：11001

28．设图以邻接表存储,如题28图所示。

（1）写出从顶点v1出发图的深度优先搜索遍历序列。 （2）写出从顶点v1出发图的广度优先搜索遍历序列。 解：1> V1→V2→V5→V3→V4→V6 2> V1→V2→V3→V4→V5→V6

29．（1）一个排序方法稳定的含义是什么？P136 （2）快速排序是稳定的吗？举例说明。P145

解：1>如果待排序的文件中，存在多个关键字相同的记录，经过排序后这些具有相同关键

字的记录之间的相对次序保持不变，则称这种排序方法是稳定的；

2>快速排序是不稳定的，例如序列[2,2,1]

四、算法阅读题（本大题共4小题,每小题5分,共20分） 30.阅读下列算法,并回答问题： voidf30（SeqStackS） { int k=0； CirQueue Q； SeqStack T；

InitQueue（&Q）； //初始化队列Q InitStack（&T）； //初始化栈T while（!StackEmpty（&S）） {k++;

if（k%2!=0）Push（&T,Pop（&S））; elseEnQueue（&Q,Pop（&S））; } //第一个循环

while （!QueueEmpty（&Q）） //第二个循环

Push（&S,DeQueue（&Q））;

while（!StackEmpty（&T）） //第三个循环

Push（&S,Pop（&T））； }

设栈S=（1,2,3,4,5,6,7）,其中7为栈顶元素。调用函数f30（S）后, （1）第一个循环结束后,栈T和队列Q中的内容各是什么？ （2）第三个循环语句结束后,栈S中的内容是什么？ 解：1>第一个循环结束后T与Q内容为 T：7 ,5,3,1 Q：6,4,2

2>第三个循环结束后栈S的内容为 S：6,4,2,1,3,5,7（7为栈顶元素）

31.二叉树的二叉链表类型定义如下： typedefstructnode{

DataType data；

struct node *lchild, *rchild; } BinNode;

typedef BinNode *BinTree； 阅读下列算法,并回答问题： voidf31（BinTreeBT） {BinNode*s;

if（BT）

本文来源：https://www.bwwdw.com/article/ju7v.html