2015年04月自学考试02142《数据结构概论》真题和答案.pdf

2 0 1 5 年 4 月高等教育自学考试全国统一命题考试数据结构导论试卷(课程代码0 2 1 42)本试卷共4 页，满 分 1 0 0 分，考试时间1 5 0 分钟考生答题注意事项：1 .本卷所有试题必须在答题卡上作答答在试卷上无效，试卷空白处和背面均可作草稿纸2 .第一部分为选择题必须对应试卷上的题号使用2 B 铅笔将“答题卡”的相应代码涂黑3.第二部分为非选择题必须注明大、小题号，使用0.5 毫米黑色字迹签字笔作答4.合理安排答题空间，超出答题区域无效第一部分 选择题一、单项选择题(本大题共1 5 小题，每小题2 分，共 30 分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题卡”的相应代码涂黑未涂、错涂或多涂均无分1.设某个算法的计算量是问题规模n的函数：T(n)=a n +b l o g 2 n+c n+d,则该算法的时问复度可表示成A.O(n)B.0(l o g2 n)C.0(n)D.0(1)2 .将长度为n的单链表链接在长度为m的单链表之后的算法时间复杂度为A.0(n)B.0(m)C.0(n+m)D.O(n X m)3.为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。

该缓冲区的逻辑结构应该是A.栈 B.队列 C.树 D.图4.对于n(n 2 O)个元素构成的线性表L,适合采用链式存储结构的操作是A.需要频繁修改L中元素的值 B.需要频繁地对L 进行随机查找C.需要频繁地对L进行插入和删除操作 D.要求L存储密度高5 .判断一个带有头结点的链队列为空队列Q的条件是A.Q.f r o n t=N U L L B.Q.f r o n t =Q.r e a rC.Q.f r o n t !=Q.r e a r D.Q.r e a r =NU LL6 .在一个单链表中，已知指针q指向指针p 所指结点的前驱结点，则删除*p 结点的操作语句是A.q=p；B.q=p-n e x t；C.q ne x t=pj D.q ne x t=p ne x t j7.把特殊矩阵A 1 0 1 0 的下三角矩阵压缩存储到一个一维数组M中，刚 A 中元素a 4 3 在 M中所对应的下标位置是A.8 B.1 2 C.1 3 D.5 58.若一棵具有n(n 0)个结点的二叉树的先序序列与后序序列正好相反，则该二叉树一定是A.结点均无左孩子的二叉树 B.结点均无右孩子的二叉树C.存在度为2的结点的二叉树 D.高度为n 的二叉树9.对关键字序列 0,2,4,8,1 6,3 2,6 4,1 2 8 进行二分查找，则第一个被查找到的关键字是A.0 B.8 C.1 6 D.1 2 81 0.已知一个图如题1 0 图所示，若从顶点a出发进行广度优先遍历，则可能得到的广度优先搜索的结果序列为A.acefbdB.acbdfeC.acbdefD.acdbfe1 1 .若某二叉树按后序遍历得到的结果为c、b、a,则可以得到该结果的二叉树有A.1 种 B.2 种 C.3 种 D.5 种1 2 .下列有关哈夫曼（H u f f m a n）树的描述，不正确的是A.哈夫曼树的树形唯一，且其W P L值最小B.哈夫曼树的树形不一定唯一，但其W P L值最小且相等C.哈夫曼字符编码不一定唯一，但总码长最短D.哈夫曼树没有严格要求区别左右子树权重次序1 3.能够使用二分查找算法进行查找的条件是必须以A.顺序方式存储，且元素按关键字有序C.顺序方式存储，且元素按关键字无序1 4 .下列排序方法中不稳定的是A.直接插入排序C.冒泡排序1 5 .对于n 个元素的关键字序列 k i,k,.，k）2 i+l W n）称其为最小堆，反之则为最大堆。

A.4,1 0,1 5,7 2,3 9,2 3,1 8 C.4,1 0,1 8,7 2,3 9,2 3,1 5 第二部分B.链式方式存储，且元素按关键字有序D.链式方式存储，且元素按关键字无序B.堆排序D.二路归并排序,当且仅当满足关系k i W k z,且 k i W k 2 H （2 i W n,以下序列中不符合最小堆或最大堆定义的是B.5 8,2 7,3 6,1 2,8,2 3,9）D.5 8,3 6,2 7,1 2,8,2 3,9 非选择题二、填空题（本大题共1 3 小题，每小题2 分共 2 6 分）请在答题卡上作答1 6 .数据结构研究的主要内容包括数据的逻辑结构、以及对数据及其关系的操作运算1 7 .根据数据元素之间的关系，通常有四类基本的逻辑结构：集合、线性结构、树形结构、1 8 .在表长为n的顺序表中插入一个数据元素，平均需要移动约 个数据元素1 9 .设有二维数组A 8 1 0,按行序优先存储，且每个元素占用2个存储单元，若第一个元素的存储起始位置为b,则存储位置为b+2 0处 的 元 素 为2 0.栈的特点是先进后出或后进先出，队 列 的 特 点 是2 1 .若一棵二叉树中度为1 和度为2的结点个数均是3,则 该 二 叉 树 叶 子 结 点 的 个 数 是.2 2 .高度（深度）为 h的 完 全 二 叉 树 最 少 的 结 点 个 数 是。

2 3 .根据图的定义，图中顶点的最少数目是_ _ _ _2 4 .高 度 为 3、含 有 5 个 结 点（编 号 1 5）的 二 叉 树，其 顺 序 存 储 结 构 为川2|3|0回4叵则编号为4的 结 点 的 双 亲 结 点 的 编 号 为2 5 .对如题2 5 图所示的含有3棵树的森林进行先序遍历，得到的结果序列是一2 6 .按关键字的输入序列 3 0,2 2,4 2,7,2 5 所生成的二又排序树中，其左子树上的关键字有2 7 .插入、选择、冒泡及堆等四种排序方法在各自排序过程中其键值比较的次数与数据元素的初始排列次序无关的有 和堆排序2 8 .用冒泡排序算法对n 个带有键值的数据元素进行排序，排序结束后所可能历经的最少趟数为_ _ _ _ _ _三、应用题（本大题共5 小题，每小题6 分，共 3 0分）请在答题卡上作答2 9 .字符a.b、c、d依次通过一个栈，按出栈的先后次序组成字符串，至多可以组成多少个不同的字符串？并分别写出它们3 0.已知某棵二叉树的先序遍历和中序遍历的结果序列分别为A B C DEFGHI 和B C A EDGHFK 试构造出该二叉树，并给出该二叉树的后序遍历结果序列。

3 1 .带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径假定从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：设最短路径初始时仅包含初始顶点，令当前顶点u 为初始顶点；选择离u 最近且尚未在最短路径中的一个顶点v,加入到最短路径中，修改当前顶点 v v；重复步骤，直到u 是目标顶点时为止现问上述方法能否求得最短路径？若该方法可行，试证明之；否则，举例说明3 2 .将关键字序列 7,8,3 0,1 1,1 8,9,1 4 散列存储到一个散列表中，设该散列表的存储 空 间 是 一 个 下 标 从 0 开 始、大 小（Ha shSize）为 10的 一 维 数 组，散列函数为I l （key）=（key X 3）M O D Ha shSize,处理冲突采用线性探测法现要求：（1）画出所构造的散列表；（2）计算出等概率情况下查找成功的平均查找长度3 3 .若采用冒泡排序方法对关键字序列 2 6 5,3 0 1,7 5 1,1 2 9,9 3 7,8 6 3,7 4 2,6 9 4,0 7 6,4 3 8 进行升序排序，写出其每趟排序结束后的关键字序列。

四、算法设计题（本大题共2小题，每小题7 分，共 1 4 分）请在答题卡上作答3 4 .写出一个将线性表的顺序表存储方式（数组a、表长为n）改成单链表存储方式（其头结点由头指针 hea d 指向）的算法设函数头为：N o d e*C rea teL in ked L i st（D a ta Typ e a ,in tn）3 5 .统计出一棵二叉树中结点数据域的值不小于m的所有结点个数设二叉树的存储结构为：typedef struct btnode jint data；struct btnode*Ichild,*rchild；BTNode,*BTree；承2 r 禧 二续变启用前 二 啰2015年4月高等教育自学考试全国统一命题雪盒数1导论试题答案及评分参承忑 产（课程 代 码02142）一、单笔选择题（木大是共1 5小惹，每 小 三：.公,1.A6.Du.r2.B7.C1 2.A3.B8.D1 3.A二、填空题（本大题共1 3小题,每小屋2分 泮3 6分）1 6 .（数据的）存储结构 1 7.图续枷,1 9.a L l E 0 J 受/后 繇 出22.2 12 5.E BACD F H G2 8.1三、应用题（本大题共5小邈，每小题6分，共3 0分）2 9 .共1 4个。

2 2 7 2 5分别是：d c b a,c b a d,c b d a,c d b a,b a ud,b a c i c,b e a d,b e d a,b d c a,a b e d,a b a c,a e b d,a e d b.,a d e b o3 0.门料层出的相应的二叉树为：（3分）等3图（3分）n e x t=N U L L；（1分）（1分）（1分）（1分）l or (i=n；i L 0；i )p=(N od e *m a l l oc C s i z e of(N od )d a t a=a i-1 ；p-n e x t =h e a d n c x i;h e a d-n e x t=p;/r e t ur n h e a d；3 5.i n t Coun t(BTN od e *(i f !t r e t ur n 0 ；e l s e i f (L)r e t ur n 1 +Coun：(t -l c h i l d)-our n Coun t y t -L I c h i I d)4-Coun t(：-（1分）（3分）（1分）Q分)n t f t r c h i!d)：(3分)(3分)数据结构导论试题答案及评分参考第共2页）。