数据结构(C 版)课后答案 (王红梅)第2章 线性表

《数据结构(C 版)课后答案 (王红梅)第2章 线性表》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构(C++版)课后答案(王红梅)第2章线性表导读：就爱阅读网友为您分享以下“数据结构(C++版)课后答案(王红梅)第2章线性表”的资讯，希望对您有所帮助，感谢您对92to.com的支持!⑷试分别以顺序表和单链表作存储结构，各写一实现线性表就地逆置的算法。【解答】顺序表的逆置，即是将对称元素交换，设顺序表的长度为length，则将表中第i个元素与第length-i-1个元素相交换。具体算法如下：单链表的逆置请参见2.2.4算法2-4和算法2-6。⑸假设在长度大于1的循环链表中，即无头结点也无头指针，s为指向链表中某个结点的指针，试编写算法删除结点s的前趋结点。13【解答】利

2、用单循环链表的特点，通过指针s可找到其前驱结点r以及r的前驱结点p，然后将结点r删除，如图2-11所示，具体算法如下：⑹已知一单链表中的数据元素含有三类字符：字母、数字和其他字符。试编写算法，构造三个循环链表，使每个循环链表中只含同一类字符。【解答】在单链表A中依次取元素，若取出的元素是字母，把它插入到字母链表B中，若取出的元素是数字，则把它插入到数字链表D中，直到链表的尾部，这样表B，D，A中分别存放字母、数字和其他字符。具体算法如下：⑺设单链表以非递减有序排列，设计算法实现在单链表中删去值相同的多余结点。【解答】从头到尾扫描单链表，若当前结点的元素值与后继结点的元素值不相等

3、，则指针后移；否则删除该后继结点。具体算法如下：⑻判断带头结点的双循环链表是否对称。13【解答】设工作指针p和q分别指向循环双链表的开始结点和终端结点，若结点p和结点q的数据域相等，则工作指针p后移，工作指针q前移，直到指针p和指针q指向同一结点（循环双链表中结点个数为奇数），或结点q成为结点p的前驱（循环双链表中结点个数为偶数）。如图2-12所示。学习自测及答案1.已知一维数组A采用顺序存储结构，每个元素占用4个存储单元，第9个元素的地址为144，则第一个元素的地址是（）。A108B180C176D112【解答】D2．在长度为n的线性表中查找值为x的数据元素的时间复杂度为：（

4、）。AO(0)BO(1)CO(n)DO(n2)【解答】C3．在一个长度为n的顺序表的第i（1≤i≤n+1）个元素之前插入一个元素，需向后移动（）个元素，删除第i（1≤i≤n）个元素时，需向前移动（）个元素。【解答】n-i+1，n-i4．在单链表中，除了头结点以外，任一结点的存储位置由（）指示。【解答】其前趋结点的指针域5．当线性表采用顺序存储结构时，其主要特点是（）。【解答】逻辑结构中相邻的结点在存储结构中仍相邻6．在双链表中，每个结点设置了两个指针域，其中一个指向（）结点，另一个指向（）结点。【解答】前驱，后继137．设A是一个线性表（a1,a2,…,an），采用顺序存储结构

5、，则在等概率的前提下，平均每插入一个元素需要移动的元素个数为多少？若元素插在ai与ai+1之间（1≤i≤n）的概率为入一个元素所要移动的元素个数又是多少？【解答】，则平均每插，。8．线性表存放在整型数组A[arrsize]的前elenum个单元中，且递增有序。编写算法，将元素x插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂度。【解答】本题是在一个递增有序表中插入元素x，基本思路是从有序表的尾部开始依次取元素与x比较，若大于x，此元素后移一位，再取它前面一个元素重复上述步骤；否则，找到插入位置，将x插入。具体算法如下：9.已知单链表中各结点的元素值为整型且

6、递增有序，设计算法删除链表中所有大于mink且小于maxk的所有元素，并释放被删结点的存储空间。13【解答】因为是在有序单链表上的操作，所以，要充分利用其有序性。在单链表中查找第一个大于mink的结点和第一个小于maxk的结点，再将二者间的所有结点删除。10．设单循环链表L1，对其遍历的结果是：x1,x2,x3,…,xn-1,xn。请将该循环链表拆成两个单循环链表L1和L2，使得L1中含有原L1表中序号为奇数的结点且遍历结果为：x1,x3,…；L2中含有原L1表中序号为偶数的结点且遍历结果为：…,x4,x2。【解答】算法如下：第2章线性表课后习题讲解1.填空⑴在顺序表中，等概率

7、情况下，插入和删除一个元素平均需移动（）个元素，具体移动元素的个数与（）和（）有关。【解答】表长的一半，表长，该元素在表中的位置⑵顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的存储地址是（）。【解答】108【分析】第5个元素的存储地址=第1个元素的存储地址＋(5－1)×2=108⑶设单链表中指针p13指向结点A，若要删除A的后继结点（假设A存在后继结点），则需修改指针的操作为（）。【解答】p->next=(p->next)->next⑷单链表中设置头结点的作用是（）