内容发布更新时间 : 2025/2/24 17:12:46星期一 下面是文章的全部内容请认真阅读。
数据结构平时作业
1．评价一个好的算法，应该从哪几方面来考虑的？
答：1、算法的正确性，2、算法的易读性，3、是算法的健壮性，4、是算法的时空效率（运行）。
2. 简述线性表的顺序和链式两种存储结构各自的主要特点。
答：1、顺序存储结构：存储单元地址连续，它以“物理位置相邻”来表示线性表中数据元
素间的逻辑关系，可随机存取表中任一元素。但它也使得插入和删除操作需移动大量的数据元素。由于顺序表需要一组地址连续的存储单元，对于长度可变的线性表就需要预分配足够的空间，有可能使一部分存储空间长期闲置不能充分利用。也可能由于估计不足，当表长超过预分配的空间而造成溢出，在这种情况下，又难于扩充连续的存储空间。 2、链式存储结构：存储单元地址为任意一组，它的存储单元可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。因此，链表中结点的逻辑次序和物理次序不一定相同。在表示数据元素之间的逻辑关系时，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置），这两部分信息组成数据元素的存储映像，称为结点（node）
3. 说明在线性表的链式存储结构中，试述头结点,首元结点,头指针这三个概念的区别. 答：头结点、首元结点、头指针区别为：性质不同、目的不同、存在情况不同。 一、性质不同
1）头结点：头结点是在链表的首元结点之前附设的一个结点。
2）首元结点：首元结点是指链表中存储线性表中第一个数据元素a1的结点。
3）头指针：头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。 二、目的不同
1）头结点：头结点为了方便操作链表而附设的。 2）首元结点：首元结点作为链表的开始结点。 3）头指针：头指针为了指向链表的基地址。 三、存在情况不同
1）头结点：头结点对于单链表来说，头结点可有可无，但为了操作方便，一般情况下单链
表都具有头结点。
2）首元结点：首元结点如果单链表有头结点，则首元结点为头结点的下一个结点，如果单
链表没有头结点，则首元结点就是单链表的第一个结点。
3）头指针：头指针如果单链表有头结点，则头指针指向头结点，如果单链表没有头结点，
则头指针指向第一个首元结点。
4. 设计一个算法，将元素x插入到一个有序（从小到大排序）顺序表的适当位置上，并保
持有序性。
答：通过比较在顺序表L中找到插入x的位置i，将该位置及后面的元素均后移一个位置，
将x插入到位置i中，最后将L的长度增加1。对应算法如下： Void Insert（SqList *&L,ElemType x） { int i=0,j;
while (i for (j=L->length-1;j>=i,j--) L->data[j+1]=L->data[j]; L->data[i]=x; L->length++; } 5．设双向循环链表中结点的数据域、前驱和后继指针域分别为data,pre和next,试写出在指 针p 所指结点之前插入一s结点的C++语言描述语句。 s->pre = p->pre; s->pre->next = s; s->next = p; p->pre = s; 6. 有5 个元素，其入栈次序为：A，B，C，D，E，在各种可能的出栈次序中，以元素C，D 最先出栈（即C第一个且D第二个出栈）的次序有哪几个？ 答：有3个：CDBAE,CDEBA,CDBEA 7.若某非空二叉树的先序序列和后序序列正好相同，则该二叉树的形态是什么？为什么？ 答：若某非空二叉树的先序序列和后序序列正好相同，则该二叉树的形态是空树或是只有根 结点的树。因为： 若：根-左-右 == 左-右-根 当且仅当：左子树与右子树都为空树。 8. 已知一棵二叉树的中序序列为cbedahgijf，后序序列为cedbhjigfa，给出该二叉树树形表 示。 a b f c e d h g i j 9. 给定5个字符a～f，它们的权值集合W={2，3，4，7，8，9}，试构造关于W的一棵哈夫 曼树，求其带权路径长度WPL和各个字符的哈夫曼树编码。 答： 33 0 1 18 15 0 1 0 1 7 9 8 9 e f d 1 0 5 0 2 a 1 3 b 4 c 路径长度WPL=(7+8+9)*2+4*3+(2+3)*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 （1）指出fun(a，n，k)算法的功能。 答：fun(a，n，k)算法的功能是在数组a[0..n-1]中查找元素值为k的元素。若找到了返回k 对应元素的下标；否则返回-1。算法先在奇数序号的元素中查找，如没有找到，再在偶数序号的元素中查找。 （2）当a={2，6，3，8，1，7，4，9}时，执行fun(a，n，1)后的返回结果是什么？一共进 行了几次比较。 答：返回结果是4，表示查找成功。一共进行了3次比较。 （3）当a={2，6，3，8，1，7，4，9}时，执行fun(a，n，5)后的返回结果是什么？一共进 行了几次比较。 答：返回结果是-1，表示查找不成功。一共进行了8次比较。