第1个回答 2011-05-25
三、 判断题（每小题1分，共10分，错误打×，正确打√）
1、线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。.......................( ×)
2、单链表从任何一个结点出发，都能访问到所有结点........( ×)
3、在只有度为0和度为k的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1 ( ×)
4、将一棵树转换成二叉树后，根结点没有左子树( ×)
5、邻接表表示无向图，邻接表中的结点个数是无向图中边数的2倍。(× )
6、 用邻接矩阵表示图所用的存储空间大小与图的边数成正比。（× ）
7、负载因子（装填因子）是散列表的一个重要参数，它反映散列表的装满程度。( √）
8、赫夫曼树一定是满二叉树。（× ）
9、高度为h的k叉树至多有kh-1 个结点。（k^h-1 ）
10、对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可访问到该图的每个顶点。（ × ）
2、键码序列（26，25，20，33，21，24， 42，37），要用散列法进行存储，规定负载因子α=0.5。
1) （2分）请给出除余法的散列函数。m=16，p<16的质数设p=13
hash(key)=key mod 13
2) （3分）用链接法解决碰撞，请画出插入所有的关键码后得到的散列表。
0 ——> 26
1
2
3——>42
4
5
6
7 ——>20——>33
8 ——>21
9
10
11——>24——>37
12 ——> 25
3、（6分）已知序列[10，18，4，3，6，12，l，9，15，8]，请给出采用希尔排序法（d1＝5、2、1）对该序列做升序排序时的每一趟的结果。
。第一趟：10 1 4 3 6 12 18 15 8
第二趟： 4 1 6 3 8 12 10 15 18
第三趟： 1 3 4 6 8 10 12 15 18
7、（6分）下图表示一个地区的通讯网，边表示城市间的通讯线路，边上的权表示架设线路花费的代价，选择能沟通每个城市且总代价最省的n-1条线路，画出选择的过程和最终结果。
看不见图，这是一个最小生成树问题