基本概念题 2-1什么叫线性表? 2-2什么叫顺序存储结构?什么叫链式存储结构? 2-3给出线性表的抽象数据类型定义 2-4什么叫指针?什么叫头指针?什么叫头结点? 2-5什么叫单链表?什么叫循环单链表?什么叫循环双向链表? 2-6在链表设计中,为什么通常采用带头结点的链表结构? 2-7写出C语言动态申请和动态释放内存空间的 malloc(函数和fee函数的函数原型, 并说明函数中参数的含义 2-8说明在顺序表中实现插入操作和删除操作时为什么必须移动数据元素,以及插入 操作和删除操作各自移动数据元素的方向? 29对比顺序表和单链表,说明顺序表和单链表的主要优点和主要缺点 2-10什么叫线性结构?线性表是线性结构吗?为什么? 算法设计题: 2-11编写一个逐个输出顺序表中所有数据元素的算法 2-12编写一个逐个输出单链表中所有数据元素的算法 2-13线性表定位操作 ListFind(L,x)的功能是:在线性表L中查找是否存在数据元素 x,如果存在,返回线性表中和x值相等的第1个数据元素的序号(序号编号从0开始);如 果不存在,返回-1。要求编写顺序表的定位操作算法 2-14在有些应用中,允许线性表中存在值相同的数据元素。线性表的另一个删除操作 ListDeleteMore ( L,x)的功能是:删除线性表L中所有等于x的数据元素。要求编写单链表 的删除操作算法 2-15编写算法实现顺序表的逆置,即要求把顺序表A中的数据元素序列(ao,a1,an1) 逆置为(an-1,au,ao),并把逆置后的数据元素存储到顺序表B中。 2-16编写算法实现顺序表的就地逆置,即要求利用原顺序表的存储单元,把数据元素 序列(a,a,la1)逆置为(an1,a,a0) 2-17编写算法实现单链表的逆置,即要求把单链表la中的数据元素序列(a,a,,an1) 写面、,并把逆置后的数据元素存储到单链表b中 2-18编写算法实现单链表的就地逆置,即要求利用原单链表的结点空间,把数据元素 序列(a,a,an1)逆置为(an1,ax,ao) 2-19编写循环双向链表的求数据元素个数操作算法和取数据元素操作算法 *2-20编写不带头结点单链表的插入操作和删除操作算法 提示:要考虑在第一个数据元素结点前插入和删除第一个数据元素结点时与在其他 位置插入和删除其他位置结点时的不同情况。) 上机实习题 2-21设计单循环链表,要求: 1)单循环链表抽象数据类型包括初始化操作、求数据元素个数操作、插入操作、删 除操作、取数据元素操作和判非空操作。 (2)设计一个测试主函数实际运行验证所设计单循环链表的正确性 2-22设计一个有序顺序表,要求 (1)有序顺序表的操作集合有如下操作:初始化、求数据元素个数、插入、删除和取 数据元素。有序顺序表和顺序表的主要区别是有序顺序表中的数据元素按数据元素值非递减
基本概念题： 2-1 什么叫线性表？ 2-2 什么叫顺序存储结构？什么叫链式存储结构？ 2-3 给出线性表的抽象数据类型定义。 2-4 什么叫指针？什么叫头指针？什么叫头结点？ 2-5 什么叫单链表？什么叫循环单链表？什么叫循环双向链表？ 2-6 在链表设计中，为什么通常采用带头结点的链表结构？ 2-7 写出C语言动态申请和动态释放内存空间的malloc()函数和free()函数的函数原型， 并说明函数中参数的含义。 2-8 说明在顺序表中实现插入操作和删除操作时为什么必须移动数据元素，以及插入 操作和删除操作各自移动数据元素的方向？ 2-9 对比顺序表和单链表，说明顺序表和单链表的主要优点和主要缺点。 2-10 什么叫线性结构？线性表是线性结构吗？为什么？ 算法设计题： 2-11 编写一个逐个输出顺序表中所有数据元素的算法。 2-12 编写一个逐个输出单链表中所有数据元素的算法。 2-13 线性表定位操作 ListFind(L, x)的功能是：在线性表 L 中查找是否存在数据元素 x，如果存在，返回线性表中和 x 值相等的第 1 个数据元素的序号（序号编号从 0 开始）；如 果不存在，返回-1。要求编写顺序表的定位操作算法。 2-14 在有些应用中，允许线性表中存在值相同的数据元素。线性表的另一个删除操作 ListDeleteMore(L, x)的功能是：删除线性表 L 中所有等于 x 的数据元素。要求编写单链表 的删除操作算法。 2-15 编写算法实现顺序表的逆置，即要求把顺序表 A 中的数据元素序列（a0,a1,…,an-1） 逆置为（an-1,…,a1,a0），并把逆置后的数据元素存储到顺序表 B 中。 2-16 编写算法实现顺序表的就地逆置，即要求利用原顺序表的存储单元，把数据元素 序列（a0,a1,…,an-1）逆置为（an-1,…,a1,a0）。 2-17 编写算法实现单链表的逆置，即要求把单链表 la 中的数据元素序列（a0,a1,…,an-1） 逆置为（an-1,…,a1,a0），并把逆置后的数据元素存储到单链表 lb 中。 2-18 编写算法实现单链表的就地逆置，即要求利用原单链表的结点空间，把数据元素 序列（a0,a1,…,an-1）逆置为（an-1,…,a1,a0）。 2-19 编写循环双向链表的求数据元素个数操作算法和取数据元素操作算法。 *2-20 编写不带头结点单链表的插入操作和删除操作算法。 （提示：要考虑在第一个数据元素结点前插入和删除第一个数据元素结点时与在其他 位置插入和删除其他位置结点时的不同情况。） 上机实习题： 2-21 设计单循环链表，要求： （1）单循环链表抽象数据类型包括初始化操作、求数据元素个数操作、插入操作、删 除操作、取数据元素操作和判非空操作。 （2）设计一个测试主函数实际运行验证所设计单循环链表的正确性。 2-22 设计一个有序顺序表，要求： （1）有序顺序表的操作集合有如下操作：初始化、求数据元素个数、插入、删除和取 数据元素。有序顺序表和顺序表的主要区别是有序顺序表中的数据元素按数据元素值非递减
有序(参见24节的例2-4)。 (2)设计一个测试主函数实际运行验证所设计有序顺序表的正确性。 *(3)设计合并函数 ListMerge(L1,L2,L3),功能是把有序顺序表Ll和L2中的数据元 素合并到L3中,要求L3中的数据元素依然保持有序。并设计一个主函数验证该合并函数 的正确性 *2-23约瑟夫环问题。 问题描述:设编号为1,2,…,n(n>0)个人按顺时针方向围坐一圈,每人持有一个正整数 密码。开始时任意给出一个报数上限值m,从第一个人开始顺时针方向自1起顺序报数,报 到m时停止报数,抱m的人出列,将他的密码作为新的m值,从他在顺时针方向上的下一个 人起重新自1起顺序报数:如此下去,直到所有人全部出列为止。要求设计一个程序模拟此 过程,并给出出列人的编号序列。 基本要求 (1)初始报数上限值m和测试数据在程序中确定 (2)用带头结点的单循环链表作数据元素的存储结构 (3)把带头结点的单循环链表作为抽象数据类型设计。 测试数据 n=7,七个人的密码依次为3,1,7,2,4,8,4 初始报数上限值m=20
有序（参见 2.4 节的例 2-4）。 （2）设计一个测试主函数实际运行验证所设计有序顺序表的正确性。 *（3）设计合并函数 ListMerge(L1, L2, L3)，功能是把有序顺序表 L1 和 L2 中的数据元 素合并到 L3 中，要求 L3 中的数据元素依然保持有序。并设计一个主函数验证该合并函数 的正确性。 *2-23 约瑟夫环问题。 问题描述：设编号为 1,2,…,n(n>0)个人按顺时针方向围坐一圈，每人持有一个正整数 密码。开始时任意给出一个报数上限值 m，从第一个人开始顺时针方向自 1 起顺序报数，报 到 m 时停止报数，抱 m 的人出列，将他的密码作为新的 m 值，从他在顺时针方向上的下一个 人起重新自 1 起顺序报数；如此下去，直到所有人全部出列为止。要求设计一个程序模拟此 过程，并给出出列人的编号序列。 基本要求： （1）初始报数上限值 m 和测试数据在程序中确定； （2）用带头结点的单循环链表作数据元素的存储结构； （3）把带头结点的单循环链表作为抽象数据类型设计。 测试数据： n = 7，七个人的密码依次为 3,1,7,2,4,8,4 初始报数上限值 m = 20