1、第 1 章 概论 习题参考答案一、基础知识题1. 简述下列概念数据，数据元素，数据类型，数据结构，逻辑结构，存储结构，算法。【解答】数据是信息的载体，是描述客观事物的数、字符，以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据元素是数据的基本单位。在不同的条件下，数据元素又可称为元素、结点、顶点、记录等。数据类型是对数据的取值范围、数据元素之间的结构以及允许施加操作的一种总体描述。每一种计算机程序设计语言都定义有自己的数据类型。“数据结构”这一术语有两种含义，一是作为一门课程的名称；二是作为一个科学的概念。作为科学概念，目前尚无公认定义，一般认为，讨论数据结构要包括三个方面，一
2、是数据的逻辑结构，二是数据的存储结构，三是对数据进行的操作（运算）。而数据类型是值的集合和操作的集合，可以看作是已实现了的数据结构，后者是前者的一种简化情况。数据的逻辑结构反映数据元素之间的逻辑关系（即数据元素之间的关联方式或“邻接关系”），数据的存储结构是数据结构在计算机中的表示，包括数据元素的表示及其关系的表示。数据的运算是对数据定义的一组操作，运算是定义在逻辑结构上的，和存储结构无关，而运算的实现则依赖于存储结构。数据结构在计算机中的表示称为物理结构，又称存储结构。是逻辑结构在存储器中的映像，包括数据元素的表示和关系的表示。逻辑结构与计算机无关。算法是对特定问题求解步骤的一种描述，是指令
3、的有限序列。其中每一条指令表示一个或多个操作。一个算法应该具有下列特性：有穷性、确定性、可行性、输入和输出。2. 数据的逻辑结构分哪几种，为什么说逻辑结构是数据组织的主要方面？【解答】数据的逻辑结构分为线性结构和非线性结构。（也可以分为集合、线性结构、树形结构和图形即网状结构）。逻辑结构是数据组织的某种“本质性”的东西：（1）逻辑结构与数据元素本身的形式、内容无关。（2）逻辑结构与数据元素的相对位置无关。（3）逻辑结构与所含数据元素的个数无关。3. 试举一个数据结构的例子，叙述其逻辑结构、存储结构、运算三方面的内容。【解答】如学生成绩表，逻辑结构是线性结构，可以顺序存储（也可以链式存储），运算
4、可以有插入、删除、查询、等等。4. 简述算法的五个特性，对算法设计的要求。【解答】算法的五个特性是：有穷性、确定性、可行性、零至多个输入和一至多个输出。对算法设计的要求：正确性，易读性，健壮性，和高的时空间效率（运算速度快，存储空间小）。5. 设 n 是正整数，求下列程序段中带记号的语句的执行次数。(1)i=1;k=0; (2) i=1;j=0;while(ij)j+; else i+; (3)x=y=0; (4)x=91;y=100;for(i=0;i0)for(j=0;j100)x+; x=x-10; y-; for(k=0;k4时，算法 A2 好于 A1。7. 选择题：算法分析的目的是（
5、 ）A、找出数据结构的合理性 B、研究算法中的输入和输出的关系C、分析算法的效率以求改进 D、分析算法的易懂性和文档特点【解答】C二、算法设计题8. 已知输入 x，y，z 三个不相等的整数，设计一个“高效”算法，使得这三个数按从小到大输出。 “高效”的含义是用最少的元素比较次数、元素移动次数和输出次数。void Best() /按序输出三个整数的优化算法int a,b,c,t;scanf(“%d%d%d”,if(ab)t=a; a=b; b=t: /a 和 b 已正序if(bc)t=c; c=b; /c 已到位if(at) b=a; a=t; /a 和 b 已正序else b=t;/ifpri
6、ntf(“%d,%d,%dn”,a,b,c);/最佳 2 次比较，无移动；最差 3 次比较，7 个赋值9在数组 An中查找值为 k 的元素，若找到则输出其位置 i(1in)，否则输出 0 作为标志。设计算法求解此问题，并分析在最坏情况下的时间复杂度【题目分析】 从后向前查找，若找到与 k 值相同的元素则返回其位置，否则返回 0。int Search(ElemType An+1, ElemType k)i=n;wile(i=1)if(i=1) return i;else return 0;当查找不成功时，总的比较次数为 n+1 次，所以最坏情况下时间复杂度为 O(n)。第 2 章 线性表 习题参
7、考答案一、基础知识题2.1 试述头指针、头结点、元素结点、首元结点的区别，说明头指针和头结点的作【解答】指向链表第一个结点（或为头结点或为首元结点）的指针称为头指针。 “头指针”具有标识一个链表的作用，所以经常用头指针代表链表的名字，如链表 L 既是指链表的名字是 L，也是指链表的第一个结点的地址存储在指针变量 L 中，头指针为“NULL”则表示一个空表。有时，我们在整个线性链表的第一个元素结点之前加入一个结点，称为头结点，它的数据域可以不存储任何信息（也可以做监视哨或存放线性表的长度等附加信息） ，指针域中存放的是第一个数据结点的地址，空表时为空。 “头结点”的加入，使插入和删除等操作方便统
8、一。元素结点即是数据结点，至少包括元素自身信息和其后继元素的地址两个域。首元结点是指链表中第一个数据元素的结点；为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点。2.2 分析顺序存储结构和链式存储结构的优缺点，说明何时应该利用何种结构。【解答】从空间上来看，当线性表的长度变化较大，难以估计其规模时，选用动态的链表作为存储结构比较合适，但链表除了需要设置数据域外，还要额外设置指针域，因此当线性表长度变化不大，易于事先确定规模时，为了节约存储空间，宜采用顺序存储结构。从时间上看，顺序表具有按元素序号随机访问的特点，在顺序表中按序号访问数据元素的时间复杂度为 O(1)；而链表中按序号访
9、问的时间复杂度为 O(n)。所以如果经常按序号访问数据元素，使用顺序表优于链表。在顺序表中做插入删除操作时，平均移动大约表中一半的元素，因此 n 较大时顺序表的插入和删除效率低。在链表中作插入、删除，虽然也要找插入位置，但操作主要是比较操作。从这个角度考虑显然链表优于顺序表。总之，两种存储结构各有长短，选择那一种存储结构，由实际问题中的主要因素决定。2.3 分析在顺序存储结构下插入和删除结点时平均需要移动多少个结点。【解答】平均移动表中大约一半的结点，插入操作平均移动 个结点，删除操作平均移动 个结点。具体移动的次数取决于表长和插入、删除的结点的位置。2.4 为什么在单循环链表中常使用尾指针，
10、若只设头指针，插入元素的时间复杂度如何？【解答】单循环链表中无论设置尾指针还是头指针都可以遍历表中任一个结点。设置尾指针时，若在表尾进行插入元素或删除第一元素，操作可在 O(1)时间内完成；若只设置头指针，表尾进行插入或删除操作，需要遍历整个链表，时间复杂度为 O(n)。2.5 在单链表、双链表、单循环链表中，若知道指针 p 指向某结点，能否删除该结点，时间复杂度如何？【解答：】以上三种链表中，若知道指针 p 指向某结点，都能删除该结点。双链表删除 p所指向的结点的时间复杂度为 O(1)，而单链表和单循环链表上删除 p 所指向的结点的时间复杂度均为 O(n)。2.6 下面算法的功能是什么？Li
11、nkedList Unknown(LinkedList la)LNode *q，*p;if(la la=la-next; p=la;while(p-next) p=p-next;p-next=q; q-next=null;return la;【解答】将首元结点删除并插入到表尾（设链表长度大于 1） 。2.7 选择题：在循环双链表的*p 结点之后插入*s 结点的操作是（ ）la、p-next=s; s-prior=p; p-next-prior=s; s-next=p-next;B、p-next=s; p-next-prior=s; s-prior=p; s-next=p-next;lc、s-p
12、rior=p; s-next=p-next; p-next:=s; p-next-prior=s; D、s-prior=p; snext=pnext; pnext-prior =s; p-next=s; 【解答】D2.8 选择题：若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。la顺序表 B双链表 lc带头结点的双循环链表 D单循环链表【解答】la二、算法设计题2.9 设 ha 和 hb 分别是两个带头结点的非递减有序单链表的头指针，试设计算法， 将这两个有序链表合并成一个非递增有序的单链表。要求使用原链表空间，表中无重复数据。【题目分
13、析】因为两链表已按元素值非递减次序排列，将其合并时，均从第一个结点起进行比较，将小的链入链表中，同时后移链表工作指针，若遇值相同的元素，则删除之。该问题要求结果链表按元素值非递增次序排列，故在合并的同时，将链表结点逆置。LinkedList Union(LinkedList ha,hb)ha,hb 分别是带头结点的两个单链表的头指针，链表中的元素值按递增序排列本算法将两链表合并成一个按元素值递减次序排列的单链表,并删除重复元素 pa=ha-next; pa 是链表 ha 的工作指针pb=hb-next; pb 是链表 hb 的工作指针ha-next=null; ha 作结果链表的头指针，先将结
14、果链表初始化为空while(pa!=null pa-next=u-next; free(u)删除 pa 链表中的重复元素while(pb-next pb-next=u-next; free(u)删除 pb 链表中的重复元素if(pa-datadata)r=pa-next; 将 pa 的后继结点暂存于 rpa-next=ha-next; 将 pa 结点链于结果表中，同时逆置ha-next=pa;pa=r; 恢复 pa 为当前待比较结点else if(pb-datadata)r=pb-next; 将 pb 的后继结点暂存于 rpb-next=ha-next; 将 pb 结点链于结果表中，同时逆置h
15、a-next=pb;pb=r; 恢复 pb 为当前待比较结点elseu=pb;pb=pb-next;free(u)删除链表 pb 和 pa 中的重复元素/ while(pa!=null 避免再对 pa 写下面的 while 语句while(pb!=null) 将尚未到尾的表逆置到结果表中r=pb-next; pb-next=ha-next; ha-next=pb; pb=r; return ha算法 Union 结束2.10 设 la 是一个双向循环链表，其表中元素递增有序。试写一算法插入元素 x，使表中元素依然递增有序。【问题分析】双向链表的插入与单链表类似，但需修改双向指针。DLinked
16、List DInsert(DLinkedList la, ElemType x)在递增有序的双向循环链表 la 中插入元素 x，使表中元素依然递增有序p=la-next; p 指向第一元素la-data=MaxElemType;MaxElemType 是和 x 同类型的机器最大值，用做监视哨while(p-datanext ;s=(DLNode *)malloc(sizeof(DLNode);申请结点空间s-data=x;s-prior=p-prior; s-next=p; 将插入结点链入链表p-prior-next=s; p-prior=s;2.11 设 p 指向头指针为 la 的单链表中某
17、结点，试编写算法，删除结点*p 的直接前驱结点。【题目分析】设*p 是单链表中某结点，删除结点*p 的直接前驱结点，要找到*p 的前驱结点的前驱*pre 。进行如下操作：u=pre-next; pre-next=u-next;free(u);LinkedList LinkedListDel(LinkedList la，LNode *p)删除单链表 la 上的结点*p 的直接前驱结点,假定*p 存在pre=la; if(pre-next=p) printf(“*p 是链表第一结点，无前驱n”) ; exit(0) ; while(pre-next-next !=p)pre=pre-next;u=
18、pre-next; pre-next=u-next; free(u);return(la); 2.12 设计一算法，将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式各自仅有奇次幂或偶次幂项，并要求利用原链表中的结点空间来构造这两个链表。【题目分析】设循环链表表示的多项式的结点结构为：typedef struct nodeint power; 幂float coef; 系数ElemType other; 其他信息struct node *next; 指向后继的指针PNode,*PolyLinkedList;则可以从第一个结点开始，根据结点的幂是奇数或偶数而将其插入到奇次幂或偶次幂
19、项的链表中。假定用原链表保存偶次幂，要为奇次幂的链表生成一个表头，为了保持链表中结点的原来顺序，用一个指针指向奇次幂链表的表尾，注意链表分解时不能“断链” 。void PolyDis(PolyLinkedList poly)将 poly 表示的多项式链表分解为各含奇次幂或偶次幂项的两个循环链表PolyLinkedList poly2=(PolyLinkedList)malloc(sizeof(PNode);poly2 表示只含奇次幂的多项式r2=poly2; r2 是只含奇次幂的多项式链表的尾指针r1=poly; r1 是只含偶次幂的多项式链表当前结点的前驱结点的指针p=poly-next;
20、链表带头结点，p 指向第一个元素while(p!=poly)if(p-power % 2)处理奇次幂r=p-next; 暂存后继r2-next=p; 结点链入奇次幂链表r2=p; 尾指针后移p=r; 恢复当前待处理结点else 处理偶次幂r1-next=p; r1=p; p=p-next;r-next=poly2; r1-next=poly; 构成循环链表PolyDis2.13 以带头结点的双向链表表示的线性表 L=(a1，a2 ， ，an) ，试写一时间复杂度为 O(n)的算法，将 L 改造为 L=(a1，a3，an，a4，a2)。【题目分析】分析结果链表，易见链表中位置是奇数的结点保持原顺
21、序，而位置是偶数的结点移到奇数结点之后，且以与原来相反的顺序存放。因此，可从链表第一个结点开始处理，位置是奇数的结点保留不动，位置是偶数的结点插入到链表尾部，并用一指针指向链表尾，以便对偶数结点“尾插入” 。DLinkedList DInvert(DLinkedList L)将双向循环链表 L 位置是偶数的结点逆置插入到链表尾部p=L-next; p 指向第一元素Q=p-prior; Q 指向最后一个元素pre=L ; pre 指向链表中位置为奇数的结点的前驱r=L ; r 指向链表中偶数结点的尾结点i=0 ; i 记录结点序号while(p != Q) 寻找插入位置i+ ;if(i%2) 处
22、理序号为奇数的结点p-prior=pre ;pre-next=p ;pre=p; p=p-next;else 处理序号为偶数的结点u=p ; 记住当前结点p=p-next ;p 指向下个待处理结点u-prior=r-prior; 以下 4 个语句将结点插入链表尾u-next=r;r-prior-next=u;r-prior=u;r=u; 指向新的表尾2.14 设单向链表的头指针为 head，试设计算法，将链表按递增的顺序就地排序。【题目分析】本题中的“就地排序” ，可理解为不另辟空间，这里利用直接插入原则把链表整理成递增有序链表。LinkedList LinkListInsertSort(Li
23、nkedList head)head 是带头结点的单链表，本算法利用直接插入原则将链表整理成递增的有序链表if(head-next!=null) 链表不为空表p=head-next-next; p 指向第一结点的后继head-next-next=null;直接插入原则认为第一元素有序，然后从第二元素起依次插入while(p!=null)r=p-next; 暂存 p 的后继q=head;while(q-next 查找插入位置p-next=q-next; 将 p 结点链入链表q-next=p;p=r; 2.15 已知递增有序的三个单链表分别代表集合 A，B 和 C，设计算法实现 A=A（BC ）
24、，并使结果链表仍保持递增。要求算法的时间复杂度为 O(|A|+|B|+|C|)。其中，|A|为集合 A 的元素个数。【题目分析】本题首先求 B 和 C 的交集，即求 B 和 C 中共有元素，再与 A 求并集，同时删除重复元素，以保持结果 A 递增。LinkedList union(LinkedList A,B,C)A、B 和 C 均是带头结点的递增有序的单链表,本算法实现 A=A(BC)使结果表 A 保持递增有序pa=A-next;pb=B-next;pc=C-next;设置三个工作指针pre=A; pre 指向结果链表中当前待合并结点的前驱A-data=MaxElemType;同类型元素最大
25、值，起监视哨作用while(pa | pb else if(pb-datapc-data) pc=pc-next;else break; B 表和 C 表有公共元素if(pb pre=pa;pa=pa-next;if(pre-data!=pb-data)pre-next=pb;pre=pb;pb=pb-next;pc=pc-next;elsepb=pb-next;pc=pc-next; 若 A 中已有 B，C 公共元素，则不再存入结果表 while(pa|pbelse pre-next=null; 当 B，C 无公共元素，将 A 中剩余链入算法 Union 结束2.16 顺序表 la 与 lb
26、 非递减有序，顺序表空间足够大。试设计一种高效算法，将 lb 中元素合到 la 中，使新的 la 的元素仍保持非递减有序。高效指最大限度地避免移动元素。【题目分析】顺序存储结构的线性表的插入，其时间复杂度为 O(n)，平均移动近一半的元素。线性表 la 和 lb 合并时，若从第一个元素开始，一定会造成元素后移，这不符合本题“高效算法”的要求。应从线性表的最后一个元素开始比较，大者放到最终位置上。设两线性表的长度各为 m 和 n ，则结果表的最后一个元素应在 m+n 位置上。这样从后向前，直到第一个元素为止。SeqList Union(SeqList la, SeqList lb)la 和 lb
27、 是顺序存储的非递减有序线性表，本算法将 lb 合并到 la 中，元素仍非递减有序 m=la.last;n=lb.last; m，n 分别为线性表 la 和 lb 的长度k=m+n-1; k 为结果线性表的工作指针（下标）i=m-1;j=n-1; i，j 分别为线性表 la 和 lb 的工作指针（下标）while(i=0 else la.datak-=lb.dataj-;while(j=0) la.datak-=lb.dataj-;la.last=m+n;return la;【算法讨论】算法中数据移动是主要操作。在最佳情况下（lb 的最小元素大于 la 的最大元素） ，仅将 lb 的 n 个元
28、素移（拷贝）到 la 中，时间复杂度为 O（n） ，最差情况，la 的所有元素都要移动，时间复杂度为 O（m+n） 。因数据合并到 la 中，所以在退出第一个 while循环后，只需要一个 while 循环，处理 lb 中剩余元素。第二个循环只有在 lb 有剩余元素时才执行，而在 la 有剩余元素时不执行。本算法 “最大限度的避免移动元素” ，是“一种高效算法” 。2.17 已知非空线性链表由 head 指出，试写一算法，将链表中数据域值最小的那个结点移到链表的最前面。要求：不得额外申请新的链结点。【题目分析】 本题要求将链表中数据域值最小的结点移到链表的最前面。首先要查找最小值结点。将其移到
29、链表最前面，实质上是将该结点从链表上摘下（不是删除并回收空间） ，再插入到链表的最前面。LinkedList Delinsert(LinkedList head）本算法将非空线性链表 head 中数据域值最小的那个结点移到链表的最前面p=head-next；p 是链表的工作指针pre=head； pre 指向链表中数据域最小值结点的前驱q=p； q 指向数据域最小值结点，初始假定是第一结点while （p-next）if（ p-next-datadata）pre=p；q=p-next； 找到新的最小值结点p=p-next；if(q!=head-next) 若最小值是第一元素结点，则不需再操作p
30、re-next=q-next； 将最小值结点从链表上摘下q-next=head-next； 将 q 结点插到链表最前面head-next=q；Delinsert2.18 设 la 是带头结点的非循环双向链表的指针，其结点中除有 prior，data 和 next 外，还有一访问频度域 freq，其值在链表初始使用时为 0。当在链表中进行 ListLocate(la，x)运算时，若查找失败，则在表尾插入值为 x 的结点；若查找成功，值为 x 的结点的 freq 值增1，并要求链表按 freq 域值非增（递减）的顺序排列，且最近访问的结点排在频度相同的结点的后面，使频繁访问的结点总是靠近表头。试编
31、写符合上述要求的 ListLocate(la，x) 运算的算法，返回找到结点的指针。【题目分析】首先在双向链表中查找数据值为 x 的结点，查到后，将结点从链表上摘下，然后再顺结点的前驱链查找该结点的位置。DLinkList ListLocate(DLinkedList L，ElemType x) L 是带头结点的按访问频度递减的双向链表,本算法先查找数据 x查找成功时结点的访问频度域增 1，最后将该结点按频度递减插入链表中DLinkList p=L-next,q; p 为 L 表的工作指针，q 为 p 的前驱，用于查找插入位置while(p 查找值为 x 的结点 if(!p) printf(“
32、不存在所查结点n”); exit(0);else p-freq+; 令元素值为 x 的结点的 freq 域加 1p-next-prior=p-prior; 将 p 结点从链表上摘下 p-prior-next=p-next;q=p-prior; 以下查找 p 结点的插入位置 while(q !=L p-next=q-next; q-next-prior=p; 将 p 结点插入 p-prior=q; q-next=p；return(p); 返回值为 x 的结点的指针 算法结束 2.19 三个带头结点的线性链表 la、lb 和 lc 中的结点均依元素值自小至大非递减排列（可能存在两个以上值相同的结点） ，编写算法对 la 表进行如下操作：使操作后的 la 中仅留下三个表中均包含的数据元素的结点，且没有值相同的结点，并释放所有无用结点。限定算法的时间复杂度为 O（m+n+p） ，其中 m、n 和 p 分别为三个表的长度。【题目分析】 留下三个链表中公共数据，首先查找两表 la 和 B 中公共数据，再去 lc 中找有无该数据。要消除重复元素，应记住前驱，要求时间复杂度 O（m+n+p ） ，在查找每个链表时，指针不能回溯。
