|
类别： 网教 专业：计算机科学与技术 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->next 3） 串与普通的线性表相比较，它的特殊性体现在（ ）。 A. 顺序的存储结构 B. 链式存储结构 C. 数据元素任意员 D. 数据元素是一个字符 4） 广义表G=(a,b(c,d,(e,f)),g)的长度是（ ）。 A. 3 B. 4 C. 7 D. 8 5） 广义表运算式HEAD(TAIL((a,b,c),(x,y,z)))的结果是： A. (x,y,z) B. (a,b,c) C. x D. a 6）某二叉树的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为（ ）。 A. 3 B. 2 C. 4 D. 5 7）表达式a*(b+c)-d的后缀表达式是（ ）。 A. abcd+- B. abc+*d- C. abc*+d- D. -+*abcd 8）按照二叉树的定义，具有3个结点的二叉树有（ ）种。 A. 6 B. 4 C. 3 D. 5 9） 由权值为3，6，7，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ ）。 A. 51 B. 23 C. 53 D. 74 10） 下面（ ）可以判断出一个有向图中是否有环（回路）。 A. 广度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径
2、填空题 1）带有头结点的双向循环列表L为空的条件。 2）栈的插入和删除操作在完成。 3）稀疏矩阵的压缩方式有和。 4）已知二维数组A[m][n]采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是LOC(A[0][0])，则A[j]的地址是_______。 5） 用顺序存储的方法，将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组R[1..N]中，若结点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分。 | 
