2008秋-数据结构(64学时)-计0705-A卷答案-刘立嘉、姚雄伟

1石家庄铁道学院石家庄铁道学院2008-2009学年第1学期第2007级本科班级期末考试试验试验试验试验试验试验试验试验试验试验试验试验试验试验试验试验试验试验试验试验试验试验试验试验试验试验试验试验试验试验试验试验试验姚雄壮试验时间： 120分学号：姓名：班级：试验性质(学生填写学生) :通常试验()补考()补考()预习()题目编号124567总分2110分答案请写在试卷上不要写在试卷或草稿纸上。 对于具有一、填空问题(每空2分，共20分)1.169个记录的文件，用块检索法进行检索，块间和块内按顺序进行检索。 假定块长度为13条记录，平均查找长度为14。 2 .起泡排序、直接插入排序、水蛭排序、基数排序、堆积排序5种排序方法中，水蛭排序、堆积排序、堆积排序不稳定，起泡排序、直接插入排序、基数排序起泡排序、直接插入排序、基数排序稳定，基数排序3 .如果后面扫描二叉树的结果是系列a，b，c的话，5根不同的二叉树就可以得到这个结果。 GetHead(a，b )、(c，d)=(a，b )； GetHeadGetTail(a，b )，(c，d)=(c，d )； 5 .词缀式A*B*C的词缀形式为AB*C*； 后缀表达式A B-C D的后缀形式为ab-c。 6 .根节点的层次为1时，拥有73个叶节点的完全二叉树的高度为8。 二、简单解答(每题5分，共20分)1.请给出以下有向图的十字链表的记忆结构。 2答案：答案：2.请给出以下稀疏矩阵的三元群记忆结构。 解答过程：解答过程：给定矩阵行是给定矩阵行row，假定列col的坐标从坐标1开始的给定矩阵的三元组表示如下，开始下标的给定矩阵的三元组表示如下，其中， 下标是000000230230000000000000000000000000070006000500301 abcdef6.5.2a bcde f60 0. 1的2345402503111223653小区存储矩阵的规模和矩阵中非零元素的数量非b元素的个数： row colvalue 0781 1233544下图为平衡二叉树，在该二叉树中插入节点20，给出插入的二叉序列树，判断是否不平衡，指出平衡类型，如果不平衡要求画出平衡的过程。 解答过程：节点节点20插入的二叉排序树，插入的二叉排序树不均衡，不均衡点为该二叉排序树不均衡，不均衡点为15，不均衡类型为RL类型，平衡化的二叉排序树为类型，平衡化的二叉排序树为5535754595153533 解答：算法设计的基本要求包括以下四个方面：算法设计的基本要求包括以下四个方面：准确性可读性健全性效率和低存储要求准确性可读性健全性效率和低存储要求三，已知序列 50，8，90，17，40，60，76，25 按升序对该序列进行排序(10分)解答过程： (也可以用树形表示)解答过程： (也可以用树形表示)原始系列：50、8、90、17、40、60、76、25初始建筑大顶炉：初始建筑大顶炉：90、40、76、25、8、60、50、17 )输出炉顶输出90 (与炉中最终元素交换)； 新建大顶炉：交换)，新建大顶炉： 76，40，60，25，8，17，50，90输出炉顶输出炉顶76 (与炉中最终元素交换)，新建大顶炉：交换)新建大顶炉：60，40，50，25，8，17，76， 90输出炉顶输出炉顶60 (与炉中最后要素17交换)，重新建设大顶炉：50，40，17，25，8，60，76， 90输出炉顶输出炉顶50 (与炉中最终要素8交换)，重建：重建： 40，25，17，8，50，60，76， 90输出炉顶输出炉顶40 (与炉中最终元素8交换)、重建： 25、8、17、40、50、60、76、90输出炉顶输出炉顶25 (与炉中最终元素17交换)、重建炉顶： 17、8、25、40、50、60、76、 90输出炉顶输出炉顶17 (与炉中最终要素8交换)，得到最终排序序列：交换)，得到最终排序序列： 8、17、25、40、50、60、76、90四，一线性表为l=(22，41，53，46，30，13，1，67，76， 10 )假设散列存储采用的混列函数为H(key)=(3*key) mod 11，发生冲突时的下一个地址计算式为d1=H(key )，即di=(di- 1 key)mod 11(i1)，混列表的地址为010，此混列表5535754595 用等概率求搜索成功的平均搜索长度。 对于(10点)结构的哈希列表，对于结构的哈希列表，如果哈希函数在H(k)=(3*key) mod 11发生冲突，则下一地址计算公式为d1=H(key )，即 di=(di- 1 key)mod 11(i1 )，在哈希显示结构过程中=(3* 22 ) mod11=0h (41 )=(3* 41 ) mod11=2h (53 )=(3* 53 ) mod11=5h (46 )=(3* 46 ) mod11=6h (30 )=(3* 30 ) mod11=2(冲突) h1(30 )=(230 ) mod11=10 h (13 )=(3* 13 ) mod11=6(6)=(6) mod11=8h (1)=(3*1) mod11=3h (67 )=(3* 67 ) mod11=3(冲突) h1(67 )=(367 ) mod11=4h (76 )=(3* 76 ) mod11=8(冲突) h1(76 )=(876 ) mod11=7h (10 )=(3* 10 ) mod11=8(冲突) h mod 11=7(冲突) H2(10)=(7 10) mod 11=6(冲突) H3(10)=(6 10) mod 11=5(冲突) H4(10)=(5 10) mod 11=4(冲突) H5(10)=(4 10) mod 11=3(冲突) H6(10)=(3 10) mod 11=2(冲突) H7(10)=(2 10 ) mod 11=1搜索成功时的平均搜索长度：搜索成功时的平均搜索长度为asl=(1*5*4*1)/10=2.15，对于下图的有向图，使用直盘算法求出从顶点a到其他顶点的最短路径，要求各步骤的执行状态，最后从a到其他各点的最短路径(10分) abcDFEG2151268956答案：从a到其馀顶点的d值、最短路径的求解过程值以及最短路径的求解过程终点步骤i=1步骤i=2步骤i=3步骤i=4步骤i=5步骤I=6b 15 ABC2ACD 12 a d 11 ACF de6 a CFG。 由于是选择顶点选择顶点vfeb最短路径apacacfaceacfdacfab，因此从a到b的最短路径为最短路径ab，最短路径长度为从15 ga到c的最短路径为AC，最短路径长度为AC，最短路径长度为 a到d 最短路径长度为：最短路径长度为11 gae的最短路径为ACE；最短路径长度为10 gaf的最短路径为ACF；最短路径长度为6 gag的最短路径为ACFDG 已知的字符及其权重： A(7)、B(5)、C(2)、D(4)、E(3)、F(1)、G(4)根据给定的权重构筑霍夫曼树，给各字符赋予霍夫曼编码，对字符串“AEGAACEDFFC”进行编码。 (10点)解答过程：解答过程：对于结构霍夫曼树，在结构的霍夫曼树中，7个采用的编码方案在左分支采用的编码方案在左分支为0，在右分支为1时，各文字的霍夫曼代码或各文字的霍夫曼编码， A 10 B 00 C 0111 D 110 E 010 F 0110 G 111字符串“字符串“AEGAACEDFFC”的代码串为1001100110011001100111，编程问题(每个问题10分钟合计20分钟)1.指定的字符串是否为“回语” 参数s表示给定字符串，len是字符串中的字符个数。 如果s字符串是回语，函数返回1；否则返回0。 提示：正读和反读都相同的字符串是“回文”，例如，“abba”和“abcba”是回文，“abcde”和“ababab”不是回文。 例程：例程： int Palindrome(char *s，intlen ) if (len1) return (s 0=s len-1 ) else return (1)； 2 .设计函数int getHeight(TNode *T )返回二叉树t的高度，参数t指向树根。 TNode结构表示二叉树的节点，包含两个指针字段TNode *left和TNode *right，分别指向左右的子树。 提示：根节点的级别为1，子节点的级别为父节点的级别1二叉树的高度为树中节点的最大层次