2016年10月自考《2331数据结构》真题和答案 - 图文

更新时间:2023-11-22 19:08:01 阅读量: 教育文库 文档下载

说明:文章内容仅供预览,部分内容可能不全。下载后的文档,内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的,是否完整无缺。

2016年10月高等教育自学考试全国统一命题考试

数据结构 试卷

(课程代码02331)

本试卷共7页,满分l00分,考试时间l50分钟。 考生答题注意事项:

1.本卷所有试题必须在答题卡上作答。答在试卷上无效,试卷空白处和背面均可作草稿纸。 2.第一部分为选择题。必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑。 3.第二部分为非选择题。毖须注明大、小题号,使用0.5毫米黑色字迹签字笔作答。 4.合理安排答题空间,超出答题区域无效。

第一部分 选择题(共30分)

一、单项选择题(本大题共l5小题,每小题2分,共30分>

在每小题列出的四个备选项中只有一个是符合题目要求的,请将其选出并将“答题 卡”的相应代码涂黑。错涂、多涂或未涂均无分。 1.下列选项中,不属于线性结构特征的是

A.数据元素之间存在线性关系 B.结构中只有一个开始结点 C.结构中只有一个终端结点 D.每个结点都仅有一个直接前趋 2.设l7个元素的顺序表中,若将第

个元素e移动到第

个位置,

不改变除e外其他元素之间的相对次序,则需移动的表中元素个数是

3.若用一个大小为

7的数组作为循环队列的存储结构,且当前rew和盘0nt的值分别

为2和4,在此之前的操作是从队列中删除了一个元素及加入两个元素,请问这3 个操作之前rear和矗0nt的值分别是

A.0和l B.0和3 C.3和6 D.4和5 4.已知广义表LS=(((a)),((b,(c)),(d,(e,f))),0),LS的长度是 A.2 B.3 C.4 D. 5

5.一棵完全二叉树T的全部k个叶结点都在同一层中且每个分支结点都有两个孩子结点。于中包含的结点数是

2k

A.k B. 2k-1 C.k D.2-1

6.如果某二叉树的前序遍历序列为abced,中序遍历序列为cebda,则该二叉树的后序 遍历序列是

A.cedba B.decba C.ecdba D.ecbad 7.一个森林有m棵树,顶点总数为n,则森林中含有的总边数是

A.m B. n-l C.n-m D.n+m 8.设图的邻接矩阵A如下所示。各顶点的度依次是

A.1,2,1,2 B.2,2,1,l C.3,4,2,3 D.4,4,2,2 9.若对下厦无向图进行深度优先遍历,得到的正确遍历序列是

第 1 页 共 9 页

A.h,C,a,b,d,e,g,f B.e,a,f,g,b,h,c,d C. d,b,c,a,h,e,f,g D.a,b,C,d,h,e,f,g 10.己知有向图G如下所示,G的拓扑序列是

A.a,b,e,c,d,f,g B.a,c,b,f,d,e,g C. a,C,d,e,b,f,g D. a,c,d,f,b,e,g 11.下列排序算法中,在每一趟都能选出一个元素放到其最终位置上的是

A.插入排序 B.希尔排序 C.归并排序 D.直接选择排序 12.对一组数据(2,l2,16,88,5,10)进行排序,若前3趟排序结果如下: 第一趟:2,12,l6,5,10,88 第二趟:2,12,5,l0,16,88 第三趟:2,5,10,l2,l6,88 则采用的排序方法是

A.冒泡排序 B.希尔排序 C.归并排序 D.基数排序

13.设有序表为{9,l2,21,32,41,45,52},当二分查找值为52的结点时,元素之间的比较次数是 A.1 B.2 C.3 D.4 14.下列选项中,既熊捌回事存储结构也能在链式存储结构上进行查找的方法是 A.散列查找 B.顺序查找

C.二分查找 D.以上选项均不能 15.在一棵5阶B树中,每个非根结点中所含关键字的个数最少是

A.1 B.2 C.3 D.4

第二部分 非选择题(共70分)

二、填空题(本大题共l0小题,每小题2分,共20分)

16.两个栈S1和S2共用含100个元素的数组S[0一99],为充分利用存储空间,若S2的

栈底元素保存在S[99]中,则S1的栈底元素保存在_______中。

17.在一个单链表中,已知指针变量q所指结点不是表尾结点,若在q所指结点之后插

入指针变量S所指结点,则正确的执行语句是_______。

18.设顺序表第1个元素的存储地址是1000,每个数据元素占6个地址单元,则第11

个元素的存储地址是_______。

19.二叉树采用顺序存储方式保存,结点Z保存在数组A[7]中,若X有右孩子结点L

则Y保存在_______中。

20.一棵二叉树中,度数为l的结点个数为n1,度数为2的结点个数为n2,则叶结点的

个数为_______。

21.已知广义表LS=((≈b),c,d),head(LS)是_______。

第 2 页 共 9 页

22.在无向图G的邻接矩阵A中,=_______。

23. 已知大根堆中的所有关键字均不相同,最大元素在难项,第2大元素可能存在的位置有2个,第3大元素可

能存在的位置有_______个。

24.在有n个元素组成的顺序表上进行顺序查找。若查找每个元素的概率相等,则查找

成功时平均查找长度是__甘肃自考网www.gsks.cc_____。 25.线性探查法和拉链法解决的是散列存储中的_______问题。 三、解答题(本大题共4小题,每小题5分,共20分) 26.对题26图中所给的二叉排序树T回答下列问题。 (1)给出能生成r的2种关键字插入序列; (2)给出r的前序遍历序列。

27.对题27图所示的无向带权图G,回答下列问题。 (1)给出图G的邻接矩阵;

(2)给出图G的一棵最小生成树。

28.现有5个权值分别是20、31、16、7和l5的叶结点,用它们构造一棵哈夫曼树,画出该树。

29. 对于给定的一组关键字序列{26,l8,60,65,45,13,32},写出使用直接选择排序方法将其排成升序序列

的过程。

四、算法阅读题(本大题共4小题,每小题5分,共20分)

30.设非空双向循环链表L的头指针为head,表结点类型为DLNode,定义如下。

第 3 页 共 9 页

初始时,L中所有结点的prior域均为空(NULL),next域和data域中已经正确赋 值。如题30图a所示。

函数f30完成的功能是:将L中各结点的prior域正确赋值,使L成为双向循环链表。如题30图b所示。

将空白处应填写的内容答在答题卡上。

31.已知二叉树的二叉链表类型定义如下,阅读程序,并回答问题。

第 4 页 共 9 页

若二叉树如下所示,写出调用f31(T)的输出结果。

32.阅读下列程序,写出f32的输出结果。

33.阅读程序,回答下列问题。

五、算法设计题(本题l0分)

第 5 页 共 9 页

34.已知单链表类型定义如下:

单链表L中结点数不少于2。设计算法判断L中存储的全部n个数据是否是斐波那契序列的前n项。如果是,则

函数返回1,否则返回0。函数原型如下:

第 6 页 共 9 页

第 7 页 共 9 页

第 8 页 共 9 页

第 9 页 共 9 页

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

Top