西南大学网络与继续教育学院课程考试试题卷类别： 网教 专业：计算机科学与技术 课程名称【编号】： 数据结构 【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. 4 C. 7 D. 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. 2 C. 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. 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[i][j]的地址是_______。5） 用顺序存储的方法，将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组R[1..N]中，若结点 R[i]有右孩子，则其右孩子是 。 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 分；- 1 - 第 2 大题必做，满分 30 分；第 3 大题选作 2 题，满分 40 分。答案：1、选择题 1) C 2) C 3) D 4) A 5) C 6) C 7) B 8) D 9) A 10) A 2、填空题1) l==l->next2) 栈顶3) 三元组顺序表 十字链表。4) LOC(A[0][0])+(n*i+j)*k5) R[2i+1]6) 先序遍历7)n-18)99) 数据元素 关系10) 时间效率 空间效率3、应用题 (1) (3)答：结果如下： 初始序列：15，18，60，41， 6，32，83，75，95 第一趟： 15，18，41， 6，32，60，75，83，95 第二趟： 15，18， 6，32，41，60，75，83，95 第三趟： 15， 6，18，32，41，60，75，83，95 第四趟： 6，15，18，32，41，60，75，83，95 第五趟： 6，15，18，32，41，60，75，83，95- 2 -