第一章 绪论
一、选择题
1.D 2.C 3.C 4.B 5.D 6.C 7.D 8.C 9.A 10.D 11.D 12.B 二、填空题
1. 逻辑结构 存储结构 运算
2. 集合结构 线性结构 树形结构 图状结构 3. 有穷性. 确定性. 可行性. 输入. 输出 4. 顺序存储. 链式存储 5. 数据元素
6. 线性结构 非线性结构 三、简答题
1. 尽管算法的含义与程序非常相似，但两者还是有区别的。首先，一个程序不一定满 有穷性，因为它不是一个算法。其次，程序中的指令必须是计算机可以执行的，而 算法中的指令却无此限制。如果一个算法采用机器可执行的语言来书写，那么它就 是一个程序。
2. 数据结构是指数据对象以及该数据对象集合中的数据元素之间的相互关系（数据元 素的组织形式）。例如：队列的逻辑结构是线性表（先进后出）；队列在计算机中 既可以采用顺序存储也可以采用链式存储；队列可进行删除数据元素. 插入数据元 素. 判断是否为空队列，以及队列置空等操作。 3. 数据元素之间的逻辑关系，也称为数据的逻辑结构。数据元素以及它们之间的相互 关系在计算机存储器内的表示（又称映像）称为数据的存储结构，也称数据的物理 结构。
4. 算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表 示一个或者多个操作。此外，一个算法还具有下列5个特性：
（1）有穷性：一个算法必须在执行有穷步之后结束，即算法必须在有限时间内完 成。
（2）确定性：算法中每一步必须有明确的含义，不会产生二义性。并且，在任何 条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。 （3）可行性：一个算法是能执行的，即算法中的每一步都可以通过已经实现的基 本运算执行有限次得以实现。
（4）输入：一个算法有零个或者多个输入，它们是算法开始时对算法给出的初始 量。
（5）输出：一个算法有一个或者多个输出，它们是与输入有特定关系的量 5. 举例说明四种基本结构的区别:
集合: 数据元素之间无任何关系,如集合A={x,5,t,&};
线性结构: 数据元素之间存在一个对一个的关系,如线性表L=（2,3，4,5,7,10）； 树形结构: 数据元素之间存在一个对多个的关系,如文件系统目录管理；
图状结构: 数据元素之间存在多个对多个的关系,如教学计划课程安排顺序图。 四. 算法设计题
1. 执行时间为O（n）
3
2. 执行时间为O（n）
3. 时间复杂度为O（log n）。
第二章 线性表
一、选择题
1.B 2.A 3.B 4.A 5.C 6.D 7.A 8.C 9.C 10.B 11.A 12.D 13.C 14.A 15.B 16.C 17.A 18.A 二、填空题
1. 没有，1，没有，1 2. 长度，空表 3. 移动
4. 顺序存储结构，链式存储结构 5. 顺序表，链表 6. 移动，指针域 7. 移动，前一个
8. 头指针，指针域（链域） 9. p->next->next 10. p->next，q 11. 链式 12. 不相同
13. 直接前驱，直接后继 14. 运算（或操作） 三、简答题
1. 非空线性表的结构特征为：
① 有且只有一个称“第一个结点” a1 ,它无前驱； ② 有且只有一个称“最后结点” an ,它无后继；
③ 除以上结点外，其余结点均有一个直接前驱和一个直接后继。 2. 线性表的顺序存储结构具有如下两个基本特点： ① 线性表中所有元素所占的存储空间是连续的；
② 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
3. 用一维数组存放线性表时，应注意数组的基本类型，要与线性表中数据元素的类 型相同，而且该一维数组的长度，通常要定义得比线性表的实际长度大一些，以 便对线性表进行各种运算。
4. 线性表顺序存储结构的优点是：简单，存储密度大，空间利用率高，对表中任意 元素可直接确定其存储地址，随机访问存取效率高。 线性表顺序存储结构的缺点是：在顺序表中进行插入与删除操作时，需大量移动数 据元素，时间开销大；再者，在顺序存储结构下，线性表的长度估计困难，并且当
有多个顺序表同时共享计算机的存储空间时，不便于对存储空间进行动态分配。 5. 假设数据结构中的每一个数据结点对应于一个存储单元，这种存储单元称为存储结 点，简称结点。若每个结点由两部分组成：一部分用于存放数据元素值，称为数据 域；另一部分用于存放指针，称为指针域。其中指针用于指向该结点的前一个或后 一个结点（即前驱或后继）。通过每个结点的指针域，将n个结点按其逻辑顺序连 接在一起而构成的数据存储结构，称为链式存储结构。
6.（1）开始结点（首结点）：是指链表中的存储线性表中第一个数据元素a1的结点。
（2）头结点：为了操作方便，通常在链表的开始结点之前附加上一个结点，
称为头结点。一般情况下，头结点的数据域中不存储信息。附设头结点的作用是为
了对链表进行操作时更方便，可以对空表，非空表的情况以及对开始结点进行统一 的处理。
（3）头指针：是指向链表中的第一个结点（可以是头结点，也可以是开始结点）的 指针。若链表中附设了头结点，则不管线性表是否为空，头指针均不为空；若链表 中不设头结点，则线性表为空时，链表的头指针为空。 以上三个概念，对于单链表，循环链表和双向链表都适用。
7. 在单循环链表中，设置尾指针，可以更方便地判断链表是否为空。 8. 算法的功能是把单链表的第一个结点变成末尾结点。返回的L指向原链表的第二个 结点。若原链表表示的线性表是（a1,a2,a3,a4......an），则操作后表示的线性表 为 （a2,a3,a4......an,a1）。
9. 由于向量中的元素按元素非递减有序排列，值相同的元素必为相邻的元素，因此依 次比较相邻两个元素，若值相等，则删除其中一个，否则继续向后查询。故算法功 能是删除向量中多余的值相同的元素。
10.（1）单链表：当知道指针p指向某结点时，能够根据该指针找到其直接后继， 但是不知道头指针，因此不能找到该结点的直接前驱，故无法删除该结点。 （2）双链表：根据指针p可以找到该结点的直接前驱和直接后继，因此，能够删 除该结点。
（3）单循环链表：和双链表类似，根据指针p也可以找到该结点的直接前驱和直 接后继，因此也可以删除该结点。 四、算法设计题
1.【算法】
void InsertInList(SequenList *L,DataType x) {
int i;
for(i=0;i Insert(L,i+1,x); /*调用顺序表插入算法*/ } 2.【算法】 LinkList *LinkTueList(LinkList *L1,LinkList *L2) { /*将两个单链表链接在一起*/ LinkList *p,*q; p=L1;q=L2; while(p->next)p=p->next; /*查找终端结点*/ p->next=q->next; free(q); return(L1); /*将L2的开始结点链接在L1之后*/