西南大学网教 (0012)《数据结构》大作业A 答案

西南大学网教(0012)《数据结构》大作业A答案西南大学网教(0012)《数据结构》大作业A答案西南大学网教(0012)《数据结构》大作业A答案资料仅供参考文件编号：2022年4月西南大学网教(0012)《数据结构》大作业A答案版本号：A修改号：1页次：1.0审核：批准:发布日期：西南大学网络与继续教育学院课程考试试题卷类别：网教专业：软件工程2015年12月课程名称【编号】：数据结构【0012】A卷大作业满分：100分一、大作业题目1、选择题1） 在算法分析中，主要分析的是（）A.正确性和简单性B.数据复杂性和程序复杂性C.空间复杂度和时间复杂度 D.可用性和正确性2）在一个单链表中，如果删除P结点所指向的后续结点，以下语句正确的是（）A.P=P->nextB.=p->next->nextC.p-next=p->next->nextD.p=p-next,p-next=p->next->next3）串与普通的线性表相比较，它的特殊性体现在（）。A.顺序的存储结构B.链式存储结构C.数据元素任意员D.数据元素是一个字符4）广义表G=(a,b(c,d,(e,f)),g)的长度是（）。A.3B.4C.7D.85）广义表运算式HEAD(TAIL((a,b,c),(x,y,z)))的结果是：A.(x,y,z)B.(a,b,c)C.xD.a6）某二叉树的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为（）。A.3B.2C.4D.57）表达式a*(b+c)-d的后缀表达式是（）。A.abcd+-B.abc+*d-C.abc*+d-D.-+*abcd8）按照二叉树的定义，具有3个结点的二叉树有（）种。A.6B.4C.3D.59）由权值为3，6，7，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）。A.51B.23C.53D.7410）下面（）可以判断出一个有向图中是否有环（回路）。A.广度优先遍历B.拓扑排序C.求最短路径D.求关键路径2、填空题1）带有头结点的双向循环列表L为空的条件。2）栈的插入和删除操作在完成。3）稀疏矩阵的压缩方式有和。4）已知二维数组A[m][n]采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是LOC(A[0][0])，则A[i][j]的地址是_______。5）用顺序存储的方法，将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组R[1..N]中，若结点R[i]有右孩子，则其右孩子是。6）采用邻接表存储的图，其深度优先遍历类似于二叉树的。7）当利用大小为N的数组存储循环队列时，该队列的最大长度是。8）设哈希表长m=14,哈希函数H(key)=keyMOD11。表中已有4个结点：addr(15)=4,addr(38)=5,addr(61)=6,addr(84)=7其余地址为空，如用二次探测再散列处理冲突，则关键字为49的地址为。9）数据结构被形式地定义为（D,R），其中D是的有限集合，R是D上的有限集合。10）一个算法的效率分为效率和效率。3、应用题1）编写算法,将一个头指针为head不带头结点的单链表改造为一个单向循环链表，并分析算法的时间复杂度。2）已知二叉树的先序遍历序列为ABCDEFGH，中序遍历序列为CBEDFAGH，画出二叉树。然后写出该二叉树的后序遍历序列。试用权集合{12,4,5,6,1,2}构造哈夫曼树，并计算哈夫曼树的带权路径长度。已知图G如下所示，根据Prim算法，构造最小生成树。（要求给出生成过程）5）设哈希表HT表长m为13，哈希函数为H(k)=kMODm，给定的关键值序列为{19,14,23,10,68,20,84,27,55,11}。试求出用线性探测法解决冲突时所构造的哈希表，并求出在等概率的情况下查找成功的平均查找长度ASL。二、大作业要求大作业共需要完成22道题：第1大题必做，满分30分；第2大题必做，满分30分；第3大题选作2题，满分40分。答卷提交要求：考试题提前公布，学生下载试题和答题卷后，在答题卷上答题。完成后需网上提交答卷。答卷于11月20日－－12月6日通过点击页面左侧导航栏内“我的考试”－“课程论文/大作业”提交。选择题1)C2)C3)D4)A5)C6)C7)B8)D9)A10)A填空题1)l==l->next2)栈顶3)三元组顺序表十字链表。4)LOC

(A[0][0])+(n*i+j)*k5)

R[2i+1]6)先序遍历7)n-18)99)数据元素关系10)时间效率空间效率3、应用题2）已知二叉树的先序遍历序列为ABCDEFGH，中序遍历序列为CB