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