数据结构 练习题答案.doc

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

1、简答题参考答案1.答：逻辑结构反映数据元素之间的逻辑关系，而存储结构是数据结构在计算机中的表示，它包括数据元素的表示及其关系的表示。2.答：head称为头指针变量，该变量的值是指向链表的第一个结点的指针，称为头指针。头指针变量是用于存放头指针的变量。为了便于实现各种运算，通常在单链表的第一个结点之前增设一个类型相同的结点，称为头结点。其它结点称为表结点。表结点中和第一个和最后一个分别称为首结点和尾结点。　头指针变量的作用：对单链表中任一结点的访问，必须首先根据头指针变量中存放的头指针找到第一个结

2、点，再依次按各结点链域存放的指针顺序往下找，直到找到或找不到。头指针变量具有标识单链表的作用，故常用头指针变量为命名单链表。头结点的作用：头结点的数据域可以不存储任何信息，也可以存放一个特殊标志或表长。其作用是为了对链表进行操作时，将对第一个结点煌处理和对其它结点的处理统一起来。3．答：图形结构4.答：队列及其首、尾指针的变化情况如下图所示。在做（5）时，由于队满（假溢出），故操作停止。5.答：它所对应的三元组表如下。十字链表略6.答：由满二叉树与完全二叉树的定义可知，满二叉树一定是一棵完全二叉

3、树，但完全二叉树却不一定是一棵满二叉树。如果一棵二叉树不是完全二叉树，那么它绝对不可能是一棵满二叉树。这就是满二叉树与完全二叉树之间的关系。7.答：大小为3的不同的二叉树共有5种，如下图所示。其中，4棵树的高度为2，1棵树的高度为1。8.答：这棵二叉树如应用题2答案图所示。9.答：这棵二叉树如应用题3答案图所示。10.(1)（2）A110B10C111D01E001F000（3）WPL=0.16*3+0.25*2+0.18*3+0.21*2+0.14*3+0.06*3=2.5411.答：二叉树是

4、一种树，但是一种特殊的树。第一，二叉树的每个结点至多可以有两棵子树，但树的每个结点可以有多棵子树；第二，二叉树的子树有左、右之分（即是有序的），但树的子树通常是不分顺序的。12.答：对应的中序线索二叉树如下图所示转换成的森林如下图所示。13.答：14.答：对应的二叉树如下左图所示。15.答：对应的二叉树如上右图所示。16．答：图1（1）顶点集合V={V1、V2、V3、V4、V5、V6}（2）边集合E={（V1，V2），（V2，V3）（V2，V4），（V3，V4）（V3，V5），（V3，V6）（V

5、4，V5），（V4，V5）}（3）顶点V1的度D(V1)=2，顶点V2的度D(V2)=2，顶点V3的度D(V3)=4，顶点V4的度D(V4)=4，顶点V5的度D(V5)=2，顶点V6的度D(V6)=2(7)深度优先遍历序列V1、V2、V3、V5、V4、V6（8）广度优先遍历序列V1、V2、V3、V4、V5、V6(4)图的一个生成树图2略17.算法题（1）冒泡排序算法voidBubbleSort(){for(i=1;i=i+i；j--)if(R[j].key<

6、R[j-1].key){R[0].key=R[j].key；R[j].key=R[j-1].key；R[j-1].key=R[0].key；}}}（2）矩阵的转置算法Sparmatrixtrans(SpmatrixA）{SparmatrixB;B.rows=A.cols;B.cols=A.rows;B.terms=A.terms;for(intn=0;n<=A.terms-1;n++){B.data[n].i=A.data[n].j;B.data[n].j=A.data[n].i;B.data[

7、n].v=A.data[n].v;}returnB}