2020贵州大学数据结构测试题及答案.doc

1、贵州大学2020学年第二学期测试试卷 数据结构与算法分析学号： 姓名： 班级： 注意事项：1. 请考生按要求在试卷装订线内填写姓名、学号和年级专业。2. 请仔细阅读各种题目的回答要求，在规定的位置填写答案。3. 不要在试卷上乱写乱画，不要在装订线内填写无关的内容。4. 满分100分，考试时间为60分钟。题 号一二总 分统分人得 分得 分评分人一、数据操作题（共80分,16题10分,7题20分）1、用A0A7数组顺序存储一个循环队列，队首和队尾分别用front和rear表示。当前对中有34，13，23，16，70，其中34在队首，front=3，连续两次出队操作后，12,17,50依次入队，画出

2、最后队列的存储状态。2、已知一颗二叉搜索树的广义表表示为46（25（12,37（29），70（62,80），依次删除下列节点：37、25、62、46、12、29，画出每次删除后的二叉搜索树（需要平衡）。3、下图表示工程活动图，其中ai表示天数，画出该图的关键路径和求该工程关键路径长度。4、已知一组元素的排序码为（33，45，24，33，47，16，62，8），要求将该组数据排成升序表，分别画出直接插入排序第二趟排序的结果和二路归并排序第二趟排序的结果。5、有一份电文中共使用五个字符：a，b，c，d，e； 它们的出现频率依次为11，14，12，9，16；填写下表空白空格，求解哈夫曼树以及哈夫曼编

3、码序号权重父结点左孩子右孩子编码111-214-312-49-516-6-7-8-9-6、假定一组记录的关键字为30，25，29，22，11，7，28，33，88，72，采用Hash表存储，Hash表空间大小为13，Hash函数为H(key)=key mod 13，用链接法处理冲突，请画出最后得到的Hash表，求出平均查找长度。.7、使用链式基数排序在有些时候效率可以非常高，现有无序数组A = 350, 132, 123, 43, 5, 286, 465, 769, 520, 53需要排序，我们从个位到百位分别进行分配和收集，请分别画出第一趟分配后、第一、二、三趟收集后的元素逻辑关系。第一趟分

4、配后：e0 e1 e2 e3 e4 e5 e6 e7 e8 e9f0 f1 f2 f3 f4 f5 f6 f7 f8 f9收集情况记录表第一趟第二趟第三趟得 分评分人二、程序算法题（20分）1. 编写程序，根据下面数据结构，非递归方式实现二叉树的中序遍历 (10分)struct BTreeNodeint data;BTreeNode* left;BTreeNode* right;Void InOrder( BTreeNode * bt)2. 完成直接选择排序函数(升序排序)。（10分）void SelectSort(int a,int n) 41.答案：（数组中的数据和两指针每错一处扣一分）7

5、166front2354rear3502171120702.答案（每个图1分）以前的题不需要平衡， 答案与现在的题不对应，需要你们自己做3.答案（关键路径3分；该工程路径长度3分）工程最少需要18天4.答案（每个排序结果3分）直接插入排序第二趟排序：24，33，45，33，47，16，62，8二路归并排序第二趟排序：24，33，33，45，8，16，47，625.答案（每个编码1分，推导过程3分,答案不唯一）序号权重父结点左孩子右孩子编码1a116-1102b147-003c127-014d96-1115e168-10620814-726923-836956-962-78-6.答案（哈希表5分

6、，平均查找长度3分）01 23 4 56 7 8 910 11122511222878829303372Asl=(8*1+2*1+3*1)/10=13/107答案分配过程4分；每趟收集2分e0 e1 e2 e3 e4 e5 e6 e7 e8 e9 520 53 350 132 43 465 123 5 286 769f0 f1 f2 f3 f4 f5 f6 f7 f8 f9共7页，第6页收集情况记录表第一趟35052013212343535465286769第二趟55201231324335053465769286第三趟54353123132286350465520769一、 程序题1若使用其他思路，酌情考虑。Void InOrder( BTreeNode * bt)/栈的定义 1分/遍历扫描条件 1分/左孩子压栈 1分/出栈输出 1分/指向右孩子 1分2. 若使用其他思路，酌情考虑。（5分）void SelectSort(int a,int n) /控制进行n-1选择交换 1分/记录当前最小值的下标 1分/控制后序未排序数据的扫描 1分/比较找到最小值下标 1分/交换最小值 1分共7页，第7页