1. 简述单链表设置头结点的主要作用
答：设置头结点是为了保证处理第一个节点和后面的节点的时候设计的算法相同，实现程序的高效性
2. 简述线性表的顺序和链式两种存储结构各自的主要特点。 答：
顺序存储结构的主要特点是：
（1）结点中只有自身的信息域，没有关联信息域。因此，顺序存储结构的存储密度大、存储空间利用率高。
（2）通过计算地址直接访问任何数据元素，即可以随机访问。 （3）插入和删除操作会引起大量元素的移动。
链式存储结构的主要特点是：
（1）结点除自身的信息域外，还有表示关联信息的指针域。因此，链式存储结构的存储密度小、存储空间利用率低。 （2）在逻辑上相邻的结点在物理上不必相邻，因此，不可以随机存取，只能顺序存取。 （3）插入和删除操作方便灵活，不必移动结点只需修改结点中的指针域即可。
3. 说明在线性表的链式存储结构中，试述头结点,首元结点,头指针这三个概念的区别. 答：
在线性表的链式存储结构中，头指针指链表的指针，若链表有头结点则是链表的头结点的指针，头指针具有标识作用，故常用头指针冠以链表的名字。头结点是为了操作的统一、方便而设立的，放在第一元素结点之前，其数据域一般无意义（也可存放链表的长度、用做监视哨等），有头结点后，对在第一元素结点前插入结点和删除第一结点，其操作与对其它结点的操作统一了。而且无论链表是否为空，头指针均不为空。首元结点也就是第一元素结点，它是头结点后边的第一个结点。
4. 设计一个算法，将元素x插入到一个有序（从小到大排序）顺序表的适当位置上，并保持有序性。
解：通过比较在顺序表L中找到插入x的位置i,将该位置及后面的元素均后移一个位置，将x插入到位置i中，最后将L的长度增1. 算法如下：
void Insert(SqList *&L,ElemType x) {
int i=0,j;
while (i
L->data[j+1] = L->data[j]; L->data[i]=x; L->length++; }
5．设双向循环链表中结点的数据域、前驱和后继指针域分别为data,pre和next,试写出在指针p 所指结点之前插入一s结点的C++语言描述语句。 答：
{p=A; ∥p为A链表的工作指针，本题假定A和B均无头结点。 pre=p; ∥pre记住每趟比较中A链表的开始结点。 q=B； ∥q是B链表的工作指针。 while(p && q)
if(p->data==q->data){p=p->next;q=q->next;}
else{pre=pre->next;p=pre; //A链表新的开始比较结点 q=B;} //q从B链表第一个结点开始。 if(q==numll)return (1); //B是A的子序列 else return (0) //B不是A的子序列 }
6. 有5 个元素，其入栈次序为：A，B，C，D，E，在各种可能的出栈次序中，以元素C，D最先出栈（即C第一个且D第二个出栈）的次序有哪几个？ 答：
CDBAE, CDEBA, CDBEA
7.若某非空二叉树的先序序列和后序序列正好相同，则该二叉树的形态是什么？为什么？ 答：
该二叉树只有一个根结点。
前序遍历的遍历顺序是：根->孩子； 后序遍历的遍历顺序是：孩子->根；
由于非空那么根一定是存在的；遍历结果相同那么孩子一定是不存在的。
8. 已知一棵二叉树的中序序列为cbedahgijf，后序序列为cedbhjigfa，给出该二叉树树形表示。
答：二叉树如图：
9. 给定5个字符a～f，它们的权值集合W={2，3，4，7，8，9}，试构造关于W的一棵哈夫曼树，求其带权路径长度WPL和各个字符的哈夫曼树编码。
答：由权值集合W构建的哈夫曼树如图
其带权路径长度WPL=（9+7+8）x 2 + 4x3 + (2+3) x 4=80
各个字符的哈夫曼树编码：a:0000，b:0001，c:001，d:10，e:11，f:01
10. 有以下查找算法：
int fun(int a,int n,int k) { int i;
for (i=0;i
相关推荐：
loading