西南大学[0012]数据结构16年12月课程答案
西南大学网络与继续教育学院课程考试试题卷 类别： 网教 专业：计算机科学与技术 2016年12月课程名称【编号】：数据结构【0012】 A卷大作业 满分：100 分一、大作业题目 1、选择题1） 在算法分析中，主要分析的是（ ）A.正确性和简单性 B.数据复杂性和程序复杂性C.空间复杂度和时间复杂度 D.可用性和正确性2） 在一个单链表中，如果删除P结点所指向的后续结点，以下语句正确的是（） A. P=P->next B. =p->next->next C. p-next=p->next->next D. p=p-next, p-next=p->next->next3） 串与普通的线性表相比较，它的特殊性体现在（）。 A. 顺序的存储结构 B. 链式存储结构 C. 数据元素任意员 D. 数据元素是一个字符4） 广义表G=(a,b(c,d,(e,f)),g)的长度是（）。 A. 3 B. 4C. 7D. 85） 广义表运算式HEAD(TAIL((a,b,c),(x,y,z)))的结果是：A. (x,y,z) B. (a,b,c)C. xD. a 6）某二叉树的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为（ ）。 A. 3 B. 2C. 4 D. 57）表达式a*(b+c)-d的后缀表达式是（）。 A. abcd+- B. abc+*d- C. abc*+d- D. -+*abcd 8）按照二叉树的定义，具有3个结点的二叉树有（ ）种。A. 6 B. 4 C. 3 D. 59） 由权值为3，6，7，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ ）。 A. 51 B. 23C. 53 D. 74 10） 下面（ ）可以判断出一个有向图中是否有环（回路）。A. 广度优先遍历 B.拓扑排序 C. 求最短路径 D. 求关键路径2、填空题1）带有头结点的双向循环列表L为空的条件。2）栈的插入和删除操作在完成。3）稀疏矩阵的压缩方式有和。4）已知二维数组A采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是LOC(A)，则A的地址是_______。5） 用顺序存储的方法，将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组R中，若结点R有右孩子，则其右孩子是 。6）采用邻接表存储的图，其深度优先遍历类似于二叉树的。7） 当利用大小为N的数组存储循环队列时，该队列的最大长度是。8） 设哈希表长m=14,哈希函数H(key)=key MOD 11。表中已有4个结点：addr(15)=4,addr(38)=5,addr(61)=6,addr(84)=7其余地址为空，如用二次探测再散列处理冲突，则关键字为49的地址为 。9） 数据结构被形式地定义为（D, R），其中D是 的有限集合，R是D上的 有限集合。10）一个算法的效率分为效率 和效率。3、应用题(1)、已知一棵二叉树的先序序列是ABCDEFGHIJK，中序序列是CDBGFEAHJIK，请构造出该二叉树。(2)、请写出计算二叉树的深度的算法。(3)、已知序列{15,18,60,41,6,32,83,75,95}。请给出采用冒泡排序法对该序列作升序排序时的每一趟的结果。(4)、字符a, b, c,d, e出现的概率分别为：0.12, 0.40, 0.15, 0.08, 0.25，采用哈夫曼算法构造哈夫曼树进行编码。(5)、已知线性表的关键字集合{87,25, 310, 08, 27, 132, 68, 95, 187, 123, 70, 63, 47}，已知哈希函数为H(k)=k MOD 13，采用链地址法处理冲突，设计出该开哈希表的结构。二、大作业要求大作业共需要完成3道题：第1大题必做，满分30分；第2大题必做，满分30分；第3大题选作2题，满分40分。
页:
[1]