《数据结构第二章习题课 .pdf》由会员分享，可在线阅读，更多相关《数据结构第二章习题课 .pdf（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1、 试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。答：开始结点是指链表中的第一个结点，也就是没有直接前趋的那个结点。链表的头指针是一指向链表开始结点的指针(没有头结点时)，单链表由头指针唯一确定，因此单链表可以用头指针的名字来命名。头结点是我们人为地在链表的开始结点之前附加的一个结点。有了头结点之后，头指针指向头结点，不管链表否为空，头指针总是非空。而且头指针的设置使得对链表的第一个位置上的操作与在表其他位置上的操作一致(都是在某一结点之后)。2、 何时选用顺序表、何时选用链表作为线性表的存储结构为宜? 答：在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线
2、性表的存储结构，通常有以下几方面的考虑：1) 基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。2) 基于时间的考虑。假设线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之，假设需要对线性表进行频繁地插入或删除等操作时，宜采用链表做存储结构。并且，假设链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。3、 在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素 ? 答：在等概率情况下，
3、顺序表中插入一个结点需平均移动n/2 个结点， 删除一个结点需平均移动 (n-1)/2 个结点。具体的移动次数取决于顺序表的长度n 以及需插入或删除的位置i。i越接近 n 则所需移动的结点数越少。4、 为什么在单循环链表中设置尾指针比设置头指针更好? 答：尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear ，则开始结点和终端结点的位置分别是rear-next-next 和 rear, 查找时间都是O(1) 。假设用头指针来表示该链表，则查找终端结点的时间为O(n) 。5、 在单链表、双链表和单循环链表中，假
4、设仅知道指针p 指向某结点，不知道头指针，能否将结点 *p 从相应的链表中删去?假设可以，其时间复杂度各为多少? 答：我们分别讨论三种链表的情况。1) 单链表。当我们知道指针p 指向某结点时，能够根据该指针找到其直接后继，但是由于不知道其头指针，所以无法访问到p 指针指向的结点的直接前趋。因此无法删去该结点。2) 双链表。由于这样的链表提供双向链接，因此根据已知结点可以查找到其直接前趋和直接后继，从而可以删除该结点。其时间复杂度为O(1) 。3) 单循环链表。根据已知结点位置，我们可以直接得到其后相邻的结点位置(直接后继)，又因为是循环链表，所以我们可以通过查找，得到p 结点的直接前趋。因此可
5、以删去p 所指结点。其时间复杂度应为O(n) 。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 6 页6、下述算法的功能是什么? LinkList Demo(LinkList L) / L 是无头结点单链表 ListNode *Q,*P; if(L&L-next) Q=L;L=L-next;P=L; while (P-next) P=P-next; P-next=Q; Q-next=NULL; return L; / Demo 答：该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回
6、新链表的头指针。7、不带头结点的单链表head 为空的判定条件是 。A、 head=NULL B、head-next=NULL C、 head-next=head D、head!=NULL 8、在一单链表中，已知q 所指的结点是p 所指结点的前驱结点，假设在q 和 p 之间插入s结点，则执行 。A、 s-next=p-next;p-next=s; B、p-next=s-next;s-next=p; C、 q-next=s;s-next=p; D、p-next=s;s-next=q; 9、在一个单链表中，假设p 所指的结点不是最后结点，在p 之后插入 s 结点，则执行 。A、 s-next=p;
7、p-next=s; B、s-next=p-next;p-next=s; C、 s-next=p-next;p=s; D、p-next=s;s-next=p; 10、在一个单链表中，假设删除p 所指结点的后续结点，则执行 。A、p-next=p-next-next; B、p=p-next;p-next=p-next-next; C、p-next=p-next; D、 p=p-next-next; 11、从一个具有n 个结点的单链表中查找其值等于x 结点时，在查找成功的情况下，需要平均比较个结点？A、 n B、n/2 C、(n-1)/2 D、(n+1)/2 12、在一个具有n 个结点的有序单链表中
8、插入一个新结点并仍然有序的时间复杂度是 。A、 O(1) B、O(n) C、O(n2) D、O(nlog2n) 13、给定有n 个元素的向量，建立一个有序单链表的时间复杂度是 。A、 O(1) B、O(n) C、O(n2) D、O(nlog2n) 14、带有一个头结点的单链表head 为空的条件是. 15、对于一个具有n 个结点的单链表，在已知p 所指结点之后插入一个新结点的时间复杂度为；在给定值为x 的结点后插入一个新结点的时间复杂度是。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 6 页16、设顺序表L 是一个非递减有序表，试写一
9、算法，将x 插入 L 中，并使L 仍是一个有序表。解：因已知顺序表L 是递增有序表，所以只要从头找起找到第一个比它大(或相等 )的结点数据，把x 插入到这个结点所在的位置就是了。算法如下：void InsertIncreaseList(Sqlist *L,Datatype x) int i; for( i=0;ilength & L-dataix;i+);/查找并比较 ,分号不能少ListInsert (*L,i,x); / 调用顺序表插入函数/ InsertIncreaseList 17、设顺序表L 是一个递减有序表，试写一算法，将x 插入其后仍保持L 的有序性。解：与上题相类似，只要从头找
10、到第一个比x 小(或相等 )的结点数据，在这个位置插入就可以了。算法如下：void InsertDecreaseList(Sqlist *L,Datatype x) int i; for (i=0;ilength & L-dataix;i+); /查找ListInsert(*L,i,x); / 调用顺序表插入函数/ InsertDecreaseList 18、写一算法在单链表上实现线性表的ListLength(L)运算。解：求单链表长只能用遍历的方法了，从头数到尾。算法如下：int ListLength( LinkList L ) int len=0; ListNode *p; p=L; /设
11、该表有头结点while (p-next) p=p-next; len+; return len; / ListLength 19、已知 L1 和 L2 分别指向两个单链表的头结点，且已知其长度分别为m 和 n。试写一算法将这两个链表连接在一起，请分析你的算法的时间复杂度。解：算法如下: LinkList Link( LinkList L1 , LinkList L2 ) /将两个单链表连接在一起ListNode *p, *q; p=L1; q=L2; while ( p-next ) p=p-next; /查找终端结点p-next = q-next ; /将 L2 的开始结点链接在L1 之后r
12、eturn L1 ; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 6 页/ LinkList Link 分析：本算法的主要操作时间花费在查找L1 的终端结点上，与L2 的长度无关，所以本算的法时间复杂度为：m+1=O(m) 20、删除带头结点单链表L 中的元素x。解：算法如下: Void delete(LinkList &L,ElemType x) p=L-next; pre=L; while(p) if(p-data=x) pre-next=p-next; free(p); p=pre-next; else pre=p; p=p-
13、next; /delete 21、已知： A=(a1,a2, ,an-1,an) B=(b1,b2, ,bn-1,bn)均为顺序表，试编写一个比较A、B大小的算法。解：算法目标是分析两表的大小，所以不应破坏原表。表的大小指的是“ 词典顺序 ” ，而非表的长度。基本操作为：同步比较两个表中相应的数据元素。假设： int compare(SqList La,SqList Lb) 循环条件： (i=La.Length)&( i=Lb.Length) 主要操作为：if (La.elemi=Lb.elemi) i+; else if (La.elemi La.Length)&( iLb.Length)
14、return 0; (iLb.Length) return 1; (iLa.Length)&(idatanext; if (p) while (p&p-datanext; q=pre-next; pre-next=p; while(q!=p) /q=p 时，删除的为一个元素 s=q; q=q-next; free(s); /释放中间结点23、写一算法将单链表中值重复的结点删除，使所得结果表中各结点值均不相同。解：此题可以这样考虑，先取开始结点中的值，将它与其后的所有结点值一一比较，发现相同的就删除掉，然后再取第二结点的值，重复上述过程直到最后一个结点。第二种算法是将单链表按值的大小排序，排好后
15、的结点按相同的删除。具体算法略。24、试编写在带头结点的单链表中删除一个最小值结点的高效算法。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 6 页void deleteLinklist &L 题目分析 此题要求在单链表中删除最小值结点。单链表中删除结点，为使结点删除后不出现 “ 断链 ” ，应知道被删结点的前驱。而“ 最小值结点 ” 是在遍历整个链表后才能知道。所以算法应首先遍历链表，求得最小值结点及其前驱。遍历结束后再执行删除操作。LinkList DeleteLinkList LL 是带头结点的单链表，本算法删除其最小值结点。 p
16、=L-next ；p 为工作指针，指向待处理结点。假定链表非空。pre=L ；pre 指向最小值结点的前驱。q=p；q 指向最小值结点，初始假定第一元素结点是最小值结点。while p-next!=nullif p-next-datadatapre=p ；q=p-next ；查最小值结点p=p-next ；指针后移。 pre-next=q-next；从链表上删除最小值结点freeq ；释放最小值结点空间算法结束算法讨论 算法中函数头是按本教材类C 描述语言书写的。原题中void deletelinklist &L ，是按 C+的“ 引用 ” 来写的，目的是实现变量的“ 传址 ” ，克服了C 语
17、言函数传递只是 “ 值传递 ” 的缺点。25、已知非空线性链表由list 指出，链结点的构造为data,link 。请写一算法，将链表中数据域值最小的那个链结点移到链表的最前面。要求：不得额外申请新的链结点。题目分析 此题要求将链表中数据域值最小的结点移到链表的最前面。首先要查找最小值结点。 将其移到链表最前面，实质上是将该结点从链表上摘下不是删除并回收空间，再插入到链表的最前面。LinkList delinsert LinkList list list 是非空线性链表，链结点结构是data，link ， data 是数据域， link 是链域。本算法将链表中数据域值最小的那个结点移到链表的最
18、前面。p=list-link； p 是链表的工作指针pre=list ； pre 指向链表中数据域最小值结点的前驱q=p ； q 指向数据域最小值结点，初始假定是第一结点while p-link!=nullif p-link-datadata pre=p ； q=p-link ； 找到新的最小值结点p=p-link ； if (q!=list-link) 假设最小值是第一元素结点，则不需再操作pre-link=q-link；将最小值结点从链表上摘下；q-link= list-link；将 q 结点插到链表最前面。list-link=q ； 算法结束算法讨论 算法中假定list 带有头结点，否则
19、，插入操作变为q-link=list；list=q 。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 6 页26、 已知递增有序的单链表A,B 分别存储了一个集合， 请设计算法以求出两个集合A 和 B 的差集 A-B 即仅由在A 中出现而不在B 中出现的元素所构成的集合， 并以同样的形式存储，同时返回该集合的元素个数。题目分析 求两个集合A 和 B 的差集 A-B ，即在 A 中删除 A 和 B 中共有的元素。由于集合用单链表存储，问题变成删除链表中的结点问题。因此，要记住被删除结点的前驱，以便顺利删除被删结点。两链表均从第一元素结点开
20、始，直到其中一个链表到尾为止。void Difference LinkList A， B，*n A 和 B 均是带头结点的递增有序的单链表，分别存储了一个集合，本算法求两集合的差集，存储于单链表A 中， *n 是结果集合中元素个数，调用时为0 p=A-next ；p 和 q 分别是链表A 和 B 的工作指针q=B-next ； pre=A ； pre 为 A 中 p 所指结点的前驱结点的指针while p!=null & q!=nullifp-datadata pre=p ；p=p-next ；*n+ ； A 链表中当前结点指针后移else ifp-dataq-data q=q-next ；
21、B 链表中当前结点指针后移else pre-next=p-next；处理 A，B 中元素值相同的结点，应删除u=p ； p=p-next ； freeu ； 删除结点 Difference 27、请写一个算法将顺序存储结构的线性表a1.an逆置为 (an.a1)。类似此题的另外表达有：(1) 设有一带头结点的单链表,编程将链表颠倒过来.要求不用另外的数组或结点完成. (2) 设有一个带头结点的单向链表，数据项递减有序。写一算法，重新排列链表，使数据项递增有序，要求算法时间复杂度为On 。 注：用程序实现(3) 试编写求倒排循环链表元素的算法。(4) 请设计算法将不带头结点的单链表就地逆置。(5
22、) 试编写算法，将不设表头结点的、不循环的单向链表就地逆转。(6) 有一个单链表L至少有1 个结点，其头结点指针为head，编写一个过程将L 逆置，即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。题目分析 顺序存储结构的线性表的逆置，只需一个变量辅助空间。算法核心是选择循环控制变量的初值和终值。void SeqInvert ElemType a ，int n a 是具有 n 个元素用一维数组存储的线性表，本算法将其逆置。for i=0；i= n-1/2；i+ t=ai ； ai= an-1-i ；an-1-i=t ； SeqInvert 算法讨论 算法中循环控制变量的
23、初值和终值是关键。C 中数组从下标0 开始，第n个元素的下标是n-1。因为首尾对称交换，所以控制变量的终值是线性表长度的一半。当n为偶数， “ 一半 ” 恰好是线性表长度的二分之一；假设 n 是奇数， “ 一半 ” 是小于 n/2 的最大整数，这时取大于1/2 的最小整数的位置上的元素，恰是线性表中间位置的元素，不需要逆置。类似此题的其它题的解答：这一组选了6个题，都是单链表包括单循环链表的逆置。链表逆置的通常作法是：将工作指针指向第一个元素结点，将头结点的指针域置空。然后将链表各结点从第一结点开始直至最后一个结点，依次前插至头结点后，使最后插入的结点成为链表的第一结点，第一个插入的结点成为链表的最后结点。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 6 页