发布时间 : 星期六 文章数据结构(含课程设计)·平时作业2020春华南理工大学网络教育答案更新完毕开始阅读de4f675f846fb84ae45c3b3567ec102de2bddfd2
平时作业：
1． 简述单链表设置头结点的主要作用。
答：1、防止单链表是空的而设的。当链表为空的时候，带头结点的头指针就指向头结点，如果当链表为空的时候，头结点的指针域的数值为NULL。
2、为了方便单链表的特殊操作，插入在表头或者删除第一个结点。这样就保持了单链表操作的统一性。
3、单链表加上头结点之后，无论单链表是否为空，头指针始终指向头结点，因此空表和非空表的处理统一，方便了单链表的操作，也减少了程序的复杂性和出现bug的机会。
4、对单链表的多数操作应明确对哪个结点以及该结点的前驱。不带头结点的链表对首元结点、中间结点分别处理等；而带头结点的链表因为有头结点，首元结点、中间结点的操作相同,从而减少分支，使算法变得简单，流程清晰。
2. 简述线性表的顺序和链式两种存储结构各自的主要特点。
答:线性表的两种存储结构分别是顺序存储结构和链式存储结枃。顺序存储结构的主要特点如下:
①数据元素中只有自身的数据域，没有关联指针域。因此，顺序存储结构的存储密度较大。 ②顺序存储结构需要分配一整块比较大存储空间，所以存储空间利用率较低。③逻辑上相邻的两个元素在物理上也是相邻的，通过元素的逻辑序号可以直接其元素值，即具有随机存取特性
④插入和删除操作会引起大量元素的移动。链式存储结构的主要特点如下
①数据结点中除自身的数据域，还有表示逻辑关系的指针域。因此，链式存储结构比顺序存储结构的存储密度小。
②链式存储结构的每个结点是单独分配的，每个结点的存储空间相对较小，所以存储空间利用率较高。
③在逻辑上相邻的结点在物理上不一定相邻，因此不具有随机存取特性。④插入和刚除操作方便灵活，不必移动结点，只需修改结点中的指针域即可
3. 说明在线性表的链式存储结构中，试述头结点,首元结点,头指针这三个概念的区别.
答：在线性表的链式存储结构中，头指针指链表的指针，若链表有头结点则是链表的头结点的指针，头指针具有标识作用，故常用头指针冠以链表的名字。头结点是为了操作的统一、方便而设立的，放在第一元素结点之前，其数据域一般无意义（也可存放链表的长度、用做监视哨等），有头结点后，对在第一元素结点前插入结点和删除第一结点，其操作与对其它结点的操作统一了。而且无论链表是否为空，头指针均不为空。首元结点也就是第一元素结点，它是头结点后边的第一个结点。
4. 设计一个算法，将元素x插入到一个有序（从小到大排序）顺序表的适当位置上，并保持有序性。
解：通过比较在顺序表工中找到插入x的位置i，将该位置及后面的元素均后移一个位置，将x插入到位置i中，最后将L的长度增1对应的算法如下 ypeD
id Insert (Alist * L, Elemty int i=0, j,
while (i(l-)length &k L->data[i](x)i++for G=L->Length-1 j>=i: j-- 1-data【j+1]=Lー>data[j L->datalil=x L-)length++
5．设双向循环链表中结点的数据域、前驱和后继指针域分别为data,pre和next,试写出在指针p 所指结点之前插入一s结点的C++语言描述语句。
6. 有5 个元素，其入栈次序为：A，B，C，D，E，在各种可能的出栈次序中，以元素C，D最先出栈（即C第一个且D第二个出栈）的次序有哪几个？
答：要使得C，D作为第一、二个元素出栈，应是A，B，C先入栈，C出栈，D入栈，D出栈；接着就剩下A，B在栈中，E未入栈，共3个元素，此三者序列为BAE，BEA，EBA。
7.若某非空二叉树的先序序列和后序序列正好相同，则该二叉树的形态是什么？为什么？
答：若某非空二叉树的先序序列和后序序列正好相同，则该二叉树的形态是空树或是只有根结点的树。因为：若：根-左-右 == 左-右-根 当且仅当：左子树与右子树都为空树。
8. 已知一棵二叉树的中序序列为cbedahgijf，后序序列为cedbhjigfa，给出该二叉树树形表示。
9. 给定5个字符a～f，它们的权值集合W={2，3，4，7，8，9}，试构造关于W的一棵哈夫曼树，求其带权路径长度WPL和各个字符的哈夫曼树编码。