数据结构(大作业)

数据结构大作业只收手工纸面版，统一用学院的实验稿纸。

自留底稿，不退。

（已更新单选错误地方）单选题复习用1、数据结构除了研究数据本身如何表示和存储外，还需要重点研究数据___________D_____。

(A)的数量(B)的质量(C)的属性(D)之间的关系2、以下哪种逻辑结构重点表示数据之间的层次关系。

B(A)线性结构(B)树形结构(C)图形结构(D)集合结构3、以下哪种存储结构主要是通过增加新的管理数据来同时保证读取数据的高速和动态修改数据的高速。

C(A)顺序存储(B)链接存储(C)索引结构(D)哈希存储4、遍历操作是对某个数据结构中所有数据需要做到__A____的访问。

(A)至少一次且至多一次(B)可以多次(C)大部分一次，部分可以重复(D)二次5、下面哪一句话是正确的。

C(A)算法就是可以运行的程序(B)算法是程序的总结，只能用中文表示(C)算法是表示一种解决问题的思路(D)算法最好用英语表示，这样可以很快切换成程序。

6、一个满二叉树共有三层，问有几个结点？C(A)5 (B)6 (C)7 (D)87、结点个数为4个的无向完全图的边数是多少条？B(A)5 (B)6 (C)7 (D)88、实现函数调用返回点管理应该用数据结构__C_____。

(A)二叉树(B)图(C)栈(D)队列1、二分查找法适合__C____。

(A)适合顺序表和链表等结构(B)数据不需要排序，但是必须顺序存储(C)仅仅把数据排序后的顺序表(D)二叉树和图2、在字符串结构中，哪一个是进行查找操作？D(A)求子串(B)串比较(C)串遍历(D)子串定位3、在字符串的索引结构中，哪一个操作没有对原始数据区进行处理？C(A)插入字符(B)删除字符串(C)删除行(D)修改字符4、一个m*n的矩阵，用列优先存储，元素A(i，j)存储在位置k上，在横向关系上的直接前驱在一维数组中一般地址为（约定每一个元素仅仅占一个单元）：D(A)k+1 (B)k-1 (C)k+m (D)k-m5、用建立大根堆来进行排序，最后的结果是什么？A(A)升序(B)降序(C)逆序(D)不一定6、图结构的遍历操作中，一般采用什么机制可以最简单地避免再次访问已经被访问过的结点。

则关键字为49的地址为。

9）数据结构被形式地定义为（D, R），其中D是的有限集合，R是D上的有限集合。

10）一个算法的效率分为效率和效率。

3、应用题1）编写算法,将一个头指针为head不带头结点的单链表改造为一个单向循环链表，并分析算法的时间复杂度。

2）已知二叉树的先序遍历序列为ABCDEFGH，中序遍历序列为CBEDFAGH，画出二叉树。

然后写出该二叉树的后序遍历序列。

3）试用权集合{12,4,5,6,1,2}构造哈夫曼树，并计算哈夫曼树的带权路径长度。

4）已知图G如下所示，根据Prim算法，构造最小生成树。

（要求给出生成过程）5）设哈希表HT表长m为13，哈希函数为H(k)=k MOD m，给定的关键值序列为{19,14,23,10,68,20,84,27,55,11}。

试求出用线性探测法解决冲突时所构造的哈希表，并求出在等概率的情况下查找成功的平均查找长度ASL。

二、大作业要求大作业共需要完成22道题：第1大题必做，满分30分；第2大题必做，满分30分；第3大题选作2题，满分40分。

答卷提交要求：考试题提前公布，学生下载试题和答题卷后，在答题卷上答题。

完成后需网上提交答卷。

答卷于11月20日－－12月6日通过点击页面左侧导航栏内“我的考试”－“课程论文/大作业”提交。

1、选择题1) C 2) C 3) D 4) A 5) C6) C 7) B 8) D 9) A 10) A2、填空题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，中序遍历序列为CBEDFAGH，画出二叉树。

然后写出该二叉树的后序遍历序列。

答：后序遍历序列CEFDBHGA3）试用权集合{12,4,5,6,1,2}构造哈夫曼树，并计算哈夫曼树的带权路径长度。

班级021051学号021050**数据结构大作业题目 Huffman的编码与译码学院电子工程学院专业智能科学与技术学生姓名****导师姓名朱虎明Huffman 编码与译码1.实验目的：在掌握相关基础知识的基础上，学会自己设计实验算法，熟练掌握Huffman 树的建立方法，Huffman 编码的方法，进而设计出Huffman 译码算法，并编程实现。

2.实验要求：制作出能够实现基于26个英文字母的任意字符串的编译码。

写出技术工作报告并附源程序。

3.实验内容及任务：3.1．设字符集为26个英文字母，其出现频度如下表所示。

3.2.建Huffman 树；3.3．利用所建Huffman 树对任一字符串文件进行编码——即设计一个Huffman 编码器；3.4.对任一字符串文件的编码进行译码——即设计一个Huffman 译码器。

实现步骤：（1）数据存储结构设计； （2）操作模块设计； （3）建树算法设计；51 48 1 15 63 57 20 32 5 1 频度z y x w v u t 字符11611882380频度p 21 f q15 g r 47 h s o n m l k j 字符 57 103 32 22 13 64 186 频度 i e d c b a 空格 字符（4）编码器设计；（5）译码器设计4.分析以及算法描述4.1.分析问题1)首先学习二叉树的知识，了解二叉树的路径、权数以及带权路径长度计算。

2)认识霍夫曼树，了解霍夫曼树的定义，构造霍夫曼树构造算法①又给定的n个权值{w1，w2，w3，……，w n}构造根节点的二叉树，从而得到一个二叉树森林F={T1，T2，T3，……T n}。

②在二叉树森里选取根节点全职最小和此最小的两棵二叉树作为左右节点构造新的二叉树，此时新的二叉树的根节点权值为左右子树权值之和。

③在二叉树森林中删除作为新二叉树的根节点左右子树的两棵二叉树，将新的二叉树加入到二叉树森林F中。

数据结构大作业一、大作业的性质和目的数据结构大作业是对软件设计的综合训练，包括问题分析、总体设计、用户界面设计、程序设计基本技能和技巧，以至一套软件工作规范的训练和科学作风的培养。

在数据结构实验中，完成的只是单一而“小”的算法，而本课程设计是对学生的整体编程能力的锻炼。

数据结构大作业的目的是训练学生对问题的抽象能力和算法的运用能力。

二、大作业安排每位同学独立完成，可自选题目或根据选择后面的一个参考题目来完成。

开学第一周统一提交到教学在线。

提交的内容包括：(1)设计报告文档。

该文档是评分的重要依据之一，请认真对待。

该文档包括如下内容：●需求分析： (陈述要解决的问题，要实现的功能),●详细设计：包括设计算法流程图、算法分析、使用的数据结构（要求详细论证）；●软件测试：包括测试数据和测试结果记录●总结：设计过程中遇到的问题及解决方法；尚未解决的问题及考虑应对的策略；收获和心得；(2)源代码。

要求注释清晰，编写规范，模块化。

(3)可运行的exe文件。

要求充分测试，在XP操作系统中能正常运行。

以上内容打包后提交到教学在线。

三、考核和成绩评定老师根据设计文档、源代码和可执行文件，进行判分。

对于出现以下情况的学生，要求统一进行答辩：●执行文件无法正常运行。

●源程序疑似抄袭。

如果有发现两个同学的代码相类似则需要共同出席答辩。

如果判定抄袭，则为不及格。

开发过程可以部分复用网上的开源代码，但必须体现自己的工作，如果没有自己工作的部分，同样判为抄袭。

五、题目（任选其中之一或自拟）1. 数字化校园（1）设计华南理工大学的校园平面图，至少包括10个以上的地点，每两个地点间可以有不同的路，且路长可能不同。

以图中顶点表示校内各地点，存放名称、代号、简介等信息；用边表示路径，存放路径长度等相关信息。

（2）提供图中任意地点相关信息的查询。

（3）提供图中任意地点的问路查询，即查询任意两个地点之间的一条最短路径。

（4）学校要新建一间超市，请为超市选址，实现总体最优。