戈严紆轧孝睨课程考核 参考答案及评分
标准
考试课程：数据结构与算法模拟试题 试卷类型：X
学年学期：20XX-20XX学年第1学期 考试用时：120分钟
层次：本科
适用专业：数学与计算机学院计算机科学与技术（软件）专业XXXX级
1 2 3 4 5 6 7 8 C 9 B 一、选择题（每小题2分，共30分） 10 11 12 13 14 16 D C B B D A C A C D B A B 二、判断题（每小题1?5分，共9分）
1
2 X 3 X 4 V 5 X 6 V X 三、填空题（每空1分，共25分）
1、 集合、线性结构、树型结构、图状结构 2、 时间复杂度、空问复杂度 3> p->next!=NULL 4> n-i+l > n-i 5、 2, 3、 1006H 6、 表屮的数据元素全部是字符，通常是一个串整体作为操作对彖 7、 串长相等、对应字符相等 8、 2叫（n+l）/2、（n-l）/2 9、 2n^ n-l > n+1
1O> n（n-l）/2> n（n-l） 11、 邻接矩阵、邻接链表
12、 {D,Q,F,X,A,P,B,N,M,YC,W}
、设有数据结构(D, R),其中 D={ 1, 2, 3, 4, 5, 6}, R= {< 1,2>,<2,3>,<2,4>,<3,4>,<3,5>,<3,6>,<4,5>,<4,6>}o
试iHiLUJl逻辑结构图并指出属于何种结构。（5分） 五、将下面图1所示的树转换为二叉树，图2所示的二叉树转换为树或森林。(6分) 解答: 解答:
属于图状结构
图2所示的二叉树转换成的森林
六、对给定的一组权值W= (5, 2, 9, 11, 8, 度，并数学与计算机学院 写出备个权对应的哈夫曼编码。 (6分) 解答：
3, 7), 试构造相应的哈夫曼树，并计算它的带权路径长 出题教师： XXXXX
图1转换成的二叉树树的带权路径长度为：
WPL=2x4+3x4+5x3+7x3+8x3+9x24- 11x2=120 各个权对应的哈夫曼编码：
5 (001), 2 (1111), 9 (10), 11 (11), 8 (101), 3 (1110), 7 (100)
七、图3所示是一个无向带权图，请分别按Prim算法求最小生成树，并计算生成树的代价。(5分) 解答：生成的最小生成树如图4,最小生成树的代价为：3+4+1+4+2=14
图4生成的最小生成树
八、设散列函数hashf (x)=x mod 11,散列表的地址空间为0-10,现要把数据：1, 13, 12, 34,38, 33, 27, 22
插入到散列表中。（6分）
（1）使用线性探测再散列法构造的散列表。
0123456789
10
33 （2）使川链地址法构造散列表。
1 13 12 34 38 27 22 0 1 2 3 4 5 6 7 8 9 10
九、设要将序列（12, 5, 9, 20, 6, 31, 24）中的关键码按升序排列（8分）
（1） 起泡排序一趟扫描的结果：（5, 9, 12, 6, 20, 24, 31）
（2） 是增量为4的希尔排序一趟扫描的结果：（6, 5, 9, 20, 12, 31, 24） （3） 二路归并排序一趟扫描的结果:（5, 12, 9, 20, 6, 31, 24） （4） 是堆排序初始建堆的结果:（31, 20, 24, 5, 6, 9, 12）
戈严纡轧孝睨课程考核 参考答案及评分标准.docx
