大工20春《数据结构》在线作业2答卷

大连理工大学网络教育学院2020年春《数据结构》期末考试复习题☆注意事项：本复习题满分共：200分。

一、单项选择题1、在队列中存取数据的原则是（）。

A．先进先出B．后进先出C．先进后出D．随意进出2、在下列链表中，不能从当前结点出发访问到其余各结点的是（）。

A．单链表B．单循环链表C．双向链表D．双向循环链表3、在一棵二叉树上第5层的结点数最多为（）设树根为第1层。

A．16 B．15 C．8 D．324、一棵有124叶子结点的完全二叉树，最多有（）个结点。

A．247 B．249 C．248 D．1255、具有10个叶子结点的二叉树中有（）个度为2的结点。

A．8 B．9 C．10 D．116、若一棵二叉树的先序遍历序列为abdgcefh，中序遍历的序列为dgbaechf，则后序遍历的结果为（）。

A．gdbehfca B．bdgaechfC．gdbecfha D．gcefhabd7、对线性表进行顺序查找时，要求线性表的存储结构是（）。

A．倒排表B．索引表C．顺序表或链表D．散列表8、对于顺序存储的有序表(5,12,20,26,37,42,46,50,64),若采用折半查找，则查找元素26的查找长度为（）。

A．2 B．3 C．4 D．59、在所有排序方法中，关键字比较的次数与记录的初始排序次序无关的是（）。

A．希尔排序B．起泡排序C．插入排序D．选择排序10、堆的形状是一棵（）。

A．二叉排序树B．满二叉树C．完全二叉树D．平衡二叉树11、线性表采用顺序存储结构时，其地址（）。

A．必须是连续的B．部分地址必须是连续的C．一定是不连续的D．连续与否均可以12、在栈中存取数据的原则是（）。

A．先进先出B．后进先出C．后进后出D．随意进出13、插入和删除只能在一端进行的线性表，称为（）。

A．队列B．循环队列C．栈D．数组14、一个基本线性表的第一个元素的存储地址是100，每个元素的长度是2，则第5个元素的地址是（）。

1.顺序查找法适合于存储结构为（）的线性表。

A.散列表B.顺序存储或链接存储C.压缩存储D.索引存储【参考答案】: B2.算法分析的两个主要方面是（）。

A.空间复杂度和时间复杂度B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性【参考答案】: A3.对下面四个序列用快速排序的方法进行排序，以序列的第一个元素为基础进行划分。

在第一趟划分过程中，元素移动次数最多的序列是()。

A.82，75，70，16，10，90，68，23B.23，10，16，70，82，75，68，90C.70，75，68，23，10，16，90，82D.70，75，82，90，23，16，10，68【参考答案】: D4.邻接表是图的一种（）。

A.顺序存储结构B.链式存储结构C.索引存储结构D.列存储结构【参考答案】: B5.链表不具有的特点是（）。

A.不必事先估计存储空间B.可随机访问任一元素C.插入删除不需要移动元素 D.所需空间与线性表长度成正比【参考答案】: B6.若由森林转化得到的二叉树是非空的二叉树，则二叉树形状是（）。

A.根结点无右子树的二叉树B.根结点无左子树的二叉树C.根结点可能有左二叉树和右二叉树D.各结点只有一个儿子的二叉树【参考答案】: C7.具有2000个节点的二叉树，其高度至少为（）。

A.9B.10C.11D.12【参考答案】: C8.线索化二叉树中某结点D，没有左孩子的主要条件是（）。

A.D-Lchild=NullB.D-ltag=1C.D-Rchild=NullD.D-ltag=0【参考答案】: B9.一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是（）。

A.edcbaB.decbaC.abcdeD.dceab【参考答案】: D10.向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素。

A.8B.63.5C.64D.7【参考答案】: B11.以下数据结构中不属于线性数据结构的是（）。

{Lnode*p；p=head；
if（!p）returnERROR；
while（p->next!=NULL）
p=p->next；
p->next=head；
}
设单链表的长度（数据结点数）为N，则该算法的时间主要花费在查找链表最后一个结点上（算法中的while循环），所以该算法的时间复杂度为O（N）。
2）已知二叉树的先序遍历序列为ABCDEFGH，中序遍历序列为CBEDFAGH，画出二叉树。然后写出该二叉树的后序遍历序列。
答：（1）表形态：
(2)平均查找长度：ASL(10)=(1*5+2*4+3*1)/10=1.6
二、大作业要求
大作业共需要完成3道题：
第1大题必做，满分30分；
第2-3大题选做1题，满分30分；
第4-5大题选作1题，满分40分。
西南大学网络与继续教育学院课程考试试题卷
类别：网教专业：计算机科学与技术2020年 5月
课程名称【编号】：数据结构【0012】B卷
大作业满分,将一个头指针为head不带头结点的单链表改造为一个单向循环链表，并分析算法的时间复杂度。
voidlinklist_c（Lnode*heaD.
答：二叉树形态
3）试用权集合{12,4,5,6,1,2}构造哈夫曼树，并计算哈夫曼树的带权路径长度。
答：
WPL=12*1+(4+5+6)*3+(1+2)*4=12+45+12=69
4）已知图G如下所示，根据Prim算法，构造最小生成树。（要求给出生成过程）
答：
5）设哈希表HT表长m为13，哈希函数为H(k)=k MOD m，给定的关键值序列为{19,14,23,10,68,20,84,27,55,11}。试求出用线性探测法解决冲突时所构造的哈希表，并求出在等概率的情况下查找成功的平均查找长度ASL。

试卷代号：1 252国家开放大学2 0 2 0年春季学期期末统一考试数据结构（本）试题2020年7月一.单项选择题（每小题3分，共30分）1.设主串为“DBcCDABcdEFdBc”，以下模式串能与主串成功匹配的是（）。

A.dBcB.BCdC.DBCD.Abc2.顺序表所具备的特点之一是（）。

A.可以随机访问任一结点B.不用占用连续的存储空间C.插入删除操作不需要移动元素D.必须要有头指针3.在一个链队中，假设f和r分别为队头和队尾指针，p指向一个已生成的结点，现要为该结点的数据域赋值e，并使结点入队的运算为p->data=e;p->next一NULL;和（）。

A. f->next=p; f=pB.r->next=p;r=pC. p->next=r;r=pD.p->next=f; f=p4.在一个头指针为head的带头结点的单向循环链表中，p指向尾结点，要使该链表成为不带头结点的单向链表，可执行（）。

A. head= head->next;p=NULLB.head—head- >next; P- >next= headC.head- >next= p- >nextD. head- head->next;p->next=NULL5。

元素212，214，216，218按顺序依次进栈，则该栈的不可能输出序列是（）（进栈出栈可以交替进行）。

A.212, 214, 216, 218B.216, 214, 212,218C.214 ,212, 218, 216D.218, 216, 212, 2146.设有一个25阶的对称矩阵A(第一个元素为ai，，，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中(数组下标从1开始)，则矩阵中元素a4，s在一维数组B 中的下标是（）。

A.10B.9C.7D.87.在一棵二叉树中，编号为19的结点的双亲结点的顺序编号为（）。