1. 评价一个好的算法，应该从哪几方面来考虑的？
答：1、算法的正确性，2、算法的易读性，3、是算法的健壮性，4、是算法的时空效率 （运行）。
2. 简述线性表的顺序和链式两种存储结构各自的主要特点。
答:1、顺序存储结构:存储单元地址连续，它以“物理位置相邻”来表示线性表中数据元 素间的逻辑关系，可随机存取表中任一元素。但它也使得插入和删除操作需移动大量的 数据元素。由于顺序表需要一组地址连续的存储单元，对于长度可变的线性表就需要预 分配足够的空间，有可能使一部分存储空间长期闲置不能充分利用。也可能由于估计不 足，当表长超过预分配的空间而造成溢出，在这种情况下，又难于扩充连续的存储空间。 2、链式存储结构:存储单元地址为任意一组，它的存储单元可以是连续的，也可以是 不连续的，甚至是零散分布在内存中的任意位置上的。因此，链表中结点的逻辑次序和 物理次序不一定相同。在表示数据元素之间的逻辑关系时，除了存储其本身的信息之外， 还需存储一个指示其直接后继的信息（即直接后继的存储位置)，这两部分信息组成数 据元素的存储映像，称为结点（node）
3. 有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,99}，如果采用折半查找法查找关键字为82 的元素时，请分析其比较次数和每次进行比较的元素。
答：4次比较后查找成功，分别和45、77、95、82进行比较 首先和中间值45比较，82比45大选择右边，右边六个数和中间值77比较，82比77大选择右边，右边3个数选择中间值95进行比较，82比95小选择左边，左边1个数和82比较相等。
4. 有 5 个元素，其入栈次序为：A，B，C，D，E，在各种可能的出栈次序中，以元素 C，D最先出栈（即 C 第一个且 D 第二个出栈）的次序有哪几个？ 答:有 3 个: CDBAE, CDEBA, CDBEA
5. 一棵二叉树的先序遍历序列为 ABCDEF，中序遍历序列为 CBAEDF，则后序遍历序列为什么？
答：CDBAE；CDBEA；CDEBA
6. 将整数序列（4，5，7，2，1，3，6）中的元素依次插入到一棵空的二叉排序树中， 试 构造相应的二叉排序树，要求用图形给出构造过程。
7. 对于稠密图和稀疏图，采用邻接矩阵和邻接表哪个更好些？为什么？
答：邻接矩形适合稠密图，因为邻接矩形占用的存储空间与边数无关；邻接表适合于稀疏图，因为邻接表占用的存储空间与边数有关
8. 设双向循环链表中结点的数据域、前驱和后继指针域分别为 data,pre 和 next,试写出
在指针 p 所指结点之前插入一 s 结点的 C 语言描述语句。
答：在指针p所指结点前插入结点s的语句如下：s一>pre=p一>pre； s一>next=p； p一>pre一>next=s； p一>pre=s；
在指针p所指结点前插入结点s的语句如下：s一>pre=p一>pre；s一>next=p；p一>pre一>next=s；p一>pre=s；
9. 编写一个在顺序表 L 中按元素值进行顺序查找的 LocateElem(L，e)算法，该顺序查找第 1个值域与 e 相等的元素的逻辑位序。若这样的元素不存在，则返回值为 0。并为每条语句添加一个注释，解释该语句的功能和作用。 int LocateElem(SqList *L, ElemType e) { int i=0; while (i
10. 编写一个链式队列进队算法 enQueue(q，e)，并为每条语句添加一个注释，解释该语句的功能和作用。
QNode* enQueue(QNode * rear,int data){ QNode * enElem=(QNode*)malloc(sizeof(QNode)); enElem->data=data; enElem->next=NULL; //使用尾插法向链队列中添加数据元素 rear->next=enElem; rear=enElem;
数据结构(含课程设计)平时作业2020秋华南理工大学网络教育答案
