2008-B数据结构答案

《2008-B数据结构答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2008学年第一学期数据结构（B）卷试题答案一、简述术语(20分)1、（10分）数据结构是相互之间存在一种或多种特定关系的数据元素的集合。算法的时间复杂度：一个算法执行所需的平均时间长度，其描述了算法效率的高低。2、（10分）栈与队列的异同：栈是先进后出，只能在栈顶插入元素或删除元素；队列是先进先出，在队头删除元素，队尾插入元素。3、（5分）具有3个结点的二叉树的形态如下：二、（10分）编程：StatusListDelete_L(linklist&L,inti){P=L;j=0;While(p->next&&jnext;

2、++j;}If(!(p->next)//j>i-1)returnerror;q1=p->next;q2=q1->next;p->next=q2->next;free(q1);free(q2)}三、（10分）所构造的哈夫曼树如下:10.42560.5823230.33330.1518180.18150.10.0808080.2544440.1222220.1322220.06130.0709090.0304040.0405050.42560.4256对左子树路径赋为0，右子树赋为1，则a,b,c,d,e,f,g,h,i的哈夫曼编码为：a:001

3、10b:00111c:0010d:0111e:0110f:000g:010h:10i：11带权路径长度:WPL==2.96四、（10分）二叉排序树各结点的值:67324518五、（10分）构造的散列表如下:0123456789六、（12分,每题6分）（1）选取46为枢轴，具体步骤如下：4632558165112543初始序列4332558165112546进行一次交换之后4332468165112555进行两次交换之后4332258165114655进行三次交换之后4332254665118155进行四次交换之后433225116546815

4、5进行五次交换之后4332251146658155进行六次交换之后（2）直接插入排序算法:（46）32558165112543i=2(32)(3246)558165112543i=3（55）（324655）8165112543i=4(81)(32465581)65112543i=5(65)(3246556581)112543i=6(11)(113246556581)2543i=7(25)(11253246556581)43i=8(43)(1125324346556581)七、（10分）森林转化成对应的二叉树形式，中序遍历的结果DEBCAGHF

5、AABCEDFGH八、（12分）1）邻接表(6分)A142^B043^C043^D142^E0213^416ABDC2E2)最小生成树九、（6分）intLeaf_Count(BitreeT){if(!T)return0;//空树没有叶子elseif(!T->lchild&&!T->rchild)return1;elsereturnLeaf_Count(T-lchild)+Leaf_Count(T-rchild);//左子树的叶子数加上右子树的叶子数}