首页 / 自考 / 数据结构介绍2015年4月真题(02142)

数据结构介绍2015年4月真题(02142)

数据结构介绍2015年4月真题及答案分析(02142)

Introduction to Data Structure 2015年4月真题与答案分析(02142),本文是前一年的真题论文Introduction to Data Structure自考,包括答案和详细分析。

一、选择题(这个大题有15个小题,每个小题2分,共30分),每个小题列出的四个选项中只有一个符合要求题,请发送 选择并涂黑答题卡上的相应代码。未涂漆、涂错或过度涂漆不计分。

1.假设一个算法的计算量是问题大小n的函数:T(n)=anc+blog2n+cn+d,那么算法的时间复杂度可以表示为()

AO(nC)

BO(log2 n)

一氧化碳(n)

做(1)

2.在一个长度为m的单链表之后再连接一个长度为n的单链表的算法时间复杂度为()

AO(n)

BO(米)

二氧化碳(n+m)

溶解氧(n×m)

3.为了解决电脑和打印机速度不匹配的问题,通常会设置一个打印数据缓冲区,主机将要输出的数据依次写入缓冲区,打印机从缓冲区依次。缓冲区的逻辑结构应该是()

A. 堆栈

B. 排队

C。树

D、图

4.对于一个由n(n≥0)个元素组成的线性表L,适合使用链式存储结构的操作是()

A.需要经常修改L中元素的值

B. L 的随机查找需要经常进行

C.需要频繁插入和删除L

D. 需要高存储密度

5.判断有头节点的链队列为空队列Q的条件为()

AQfront==NULL

BQfront==Q.后

CQfront!=Q.后

DQrear==NULL

6.在单链表中,已知指针q指向指针p所指向的节点的前驱节点,那么删除*p节点的操作语句为()

水=p;

Bq=p->下一个;

Cq->下一个=p;

Dq->下一个=p->下一个;

7.特殊矩阵A[10][10]的下三角矩阵被压缩存储在一维数组M中,然后A中元素a[4][3]对应的下标位置M是()

A.8

B.12

C.13

D.55

8.如果n(n>0)个节点的二叉树的前序序列和后序序列正好相反,那么二叉树一定是()

A. 所有节点都没有左孩子的二叉树

B. 所有节点都没有右孩子的二叉树

C. 具有度数为 2 的节点的二叉树

D. 高度为 n 的二叉树

9. 对关键字序列{0, 2, 4, 8, 16, 32, 64, 128}进行二分查找,则找到的第一个关键字为()

A.0

B.8

C.16

D.128

10. 知道一个图如问题10所示,如果从顶点a开始进行广度优先遍历,可能的广度优先搜索()

A.acefbd

B.acbdfe

数据结构介绍2015年4月真题(02142)

C.acbdef

D. acdbfe

11.如果后序遍历二叉树得到的结果是c、b、a,那么能得到结果的二叉树是()

A.1种

B.2种

C.3种

D.5种

12.以下关于霍夫曼树的描述不正确()

A. Huffman 树的树形是唯一的,它的 WPL 值最小

B、霍夫曼树的树形不一定唯一,但其WPL值最小且相等

C.霍夫曼字符编码不一定唯一,但总码长最短

D. 霍夫曼树不严格要求区分左右子树的权重顺序

13.能够使用二分查找算法进行查找的条件是必须以()开头

A.顺序存储,元素按key排序

B.链式存储,元素按key排序

C. 顺序存储,元素按关键字无序

D. 链式存储,元素按关键字无序

14.以下排序方式中不稳定的一种是()

A. 直接插入排序

B. 堆排序

C. 冒泡排序

D. 双向归并排序

15. 对于 n 个元素的键序列 {k1, k2…., kn),当且仅当关系 ki≤k2i 且 ki≤k2i+1(2i≤n, 2i+1≤n ) 满足称其为 min-heap,否则为 max-heap。以下哪个序列不符合 min-heap 或 max-heap 的定义是 ()

A. {4, 10, 15, 72, 39, 23, 18}

B. {58, 27, 36, 12, 8, 23, 9}

C. {4, 10, 18, 72, 39, 23, 15}

D. {58, 36, 27, 12, 8, 23, 9}

二、填空题(这个大题有13个小题,每个小题2分,共26分)

11.数据结构研究的主要内容包括数据的逻辑结构、______、对数据的操作及其关系。

12.根据数据元素之间的关系数据结构导论,逻辑结构通常有四种基本类型:集合、线性结构、树形结构、______。

13.在长度为n的顺序表中插入一个数据元素,平均需要移动大约______个数据元素。

14. 有一个二维数组A[8][10],按行序先存储,每个元素占用2个存储单元。如果第一个元素的存储起始位置为b,则存储位置b+20处的元素为______。

15.栈的特点是先进先出或后进先出,队列的特点是______。

16.如果二叉树中1度和2度的节点数为3,则二叉树的节点数为_____。

17.高度(深度)为h的完全二叉树的最小节点数为______。

18.根据图的定义,图中的最小顶点数是______。

19. 一棵高度为3、的二叉树,包含5个节点(编号为1到5),其顺序存储结构为

,则编号为 4 的节点的父节点编号为______。

110. 对包含 3 棵树的森林进行前序遍历数据结构导论,如图 25 所示,得到的序列是______。

111.在关键字{30,22,42,7,25}的输入序列生成的二阶树中,左子树上的关键字是______。

112.在插入、选择、冒泡、堆等四种排序方式中,它们各自排序过程中键值比较的次数与数据元素的初始排序顺序无关,包括______和堆排序。

113.使用冒泡排序算法对n个具有键值的数据元素进行排序,排序后可能通过的最小次数为______。

三、应用题(共5个小题,每个小题6分,共30分)

21.字符ab、c、d依次经过一个栈,按照出栈的顺序组成字符串。最多可以组成多少个不同的字符串?并分别写出来。

22.已知二叉树的前序遍历和中序遍历的结果序列分别为ABCDEFGHI和BCAEDGHFI。尝试构造二叉树,并给出二叉树后序遍历的结果序列。

23.带权图的最短路径问题(权重为非负数,表示由一条边连接的两个顶点之间的距离)是求初始顶点到目标顶点的最短路径。假设从初始顶点到目标顶点有一条路径,有一个方法可以解决这个问题:①设置最短路径初始只包含初始顶点,设当前顶点u为初始顶点;②在最短路径中选择最接近u且尚未在最短路径中添加一个顶点v,并修改当前顶点u=v;③重复步骤②,直到u为目标顶点。现在问上面的方法能不能找到最短路径?如果方法可行,尝试证明;否则,举个例子。

24.将关键字序列{7,8,30,11,18,9,14}散列成散列表,设置散列表的存储空间为从0开始的下标,大小(HashSize)是10的一维数组,hash函数为H(key)=(key×3)MOD HashSize,使用线性检测方法处理冲突。现在需要:(1)@ >绘制构造好的哈希表;(2)计算等概率下搜索成功的平均搜索长度。

25.如果采用冒泡排序的方式对关键字序列{265, 301, 751, 129, 937, 863, 742, 694, 076, 438}进行升序排序,每次排序后写入结果。关键字序列。

四、算法设计题(本大题有2个小题,每个小题7分,共14分)

31.写一个算法,将线性表(数组a,表长度为n)的顺序表存储方式改为单链表存储方式(头节点由头指针head指向) . 让函数头为: Node * CreateLinkedList(DataType a[], int n)

32. 统计一棵二叉树中节点数据字段的值不小于m的所有节点的个数。设二叉树的存储结构为: typedef struct btnode{ int data; 结构 btnode *lchild, *rchile;}BTNode, *BTree;

本文来自网络,不代表无忧自考网立场,转载请注明出处:
上一篇
下一篇

为您推荐

发表评论

您的电子邮箱地址不会被公开。