数据结构设计与技巧

1、数据结构设计与技巧讲义【考查目标】1.理解数据结构的基本概念；掌握数据的逻辑结构、种基本操作的实现。结构及其差异，以及各2. 掌握基本的数据处理原理和方法的基础上，能够对算法进行设计与分析。3. 能够选择合适的数据结构和方法进行问题求解。一、线性表（一）线性表的定义和基本操作（二）线性表的实现1. 顺序2. 链式结构结构3.线性表的应用二、栈、队列和数组（一）栈和队列的基本概念（二）栈和队列的顺序结构（三）栈和队列的链式结构（四）栈和队列的应用（五）特殊矩阵的压缩三、树与二叉树（一）树的概念（二）二叉树1.二叉树的定义及其主要特征2. 二叉树的顺序3. 二叉树的遍历4. 线索二叉树的基本概念和

2、构造结构和链式结构5. 二叉排序树6. 平衡二叉树（三）树、森林1.书的结构2. 森林与二叉树的转换3. 树和森林的遍历（四）树的应用1. 等价类问题2. 哈夫曼（Huffman）树和哈夫曼编码四、图（一）图的概念（二）图的及基本操作1. 邻接矩阵法2. 邻接表法（三） 图的遍历1. 深度优先搜索2. 广度优先搜索（四） 图的基本应用及其复杂度分析1.2.3.4.最小（代价）生成树最短路径拓扑排序关键路径五、查找（一）查找的基本概念（二）顺序查找法（三）折半查找法（四）B-树散列（Hash）表及其查找查找算法的分析及应用（五）（六）六、内部排序（一）排序的基本概念（二）排序1.2.直接排序折半

3、排序（三）气泡排序（bubble sort）简单选择排序（四）希尔排序（shell sort）快速排序（五）（六）（七）堆排序（八）二路归并排序（merge sort）基数排序（九）（十）各种内部排序算法的比较（十一）内部排序算法的应用【知识点】1.线性表线性表是一种最简单的数据结构，性表方面，主要考查线性表的定义和基本操作、线性表的实现。性表实现方面，要掌握的是线性表的结构，包括顺序结构和链式结构，特别是链式结构，是考查的重点。另外，还要掌握线性表的基本应用。2.栈、队列和数组栈和队列是两种特殊的线性表，在这方面，要求我们掌握栈和队列的基本概念，以及他们之间的区别。对于栈和队列的结构(包括顺

4、序结构、链式结构)要有较深的理解，对于栈和队列的应用，例如，排队问题、子程序调用问题、表达式问题等，要搞清楚。一维数组属于线性表范畴，但数组不属于线性表。在这方面，主要掌握数组的结构，例如按行优先、按列优先等，某个元素存在的地址是什么。对于特殊矩阵(二维数组)的压缩原理也要搞清楚。3、树与二叉树二叉树和树是两种不同的概念，这一点是必须要搞清楚的。在这个部分，我们要掌握树的定义、二叉树的定义及主要特征(特殊的二叉树、二叉树的性质)。在二叉树的顺序结构和链式结构方面，特别是链式结构，因为很多应用都是建立在链式基础上，例如，二叉树的遍历(前序遍历、中序遍历、后序遍历)就是一种典型的应用。在特殊的二叉

5、树中，完全二叉树的概念是必须要搞清楚的，其次，线索二叉树的基本概念和构造、二叉排序树、平衡二叉树的基本概念和应用，特别是二叉排序树的基本性质和特点要能很好地理解。多棵的树就组成了森林，树的结构和遍历、森林的遍历、树和二叉树的转换、森林和二叉树的转换等知识，也要有了了解。最后就是树的应用，通常会作为综合应用类试题出现，包括等价类问题、哈夫曼(Huffman)树和哈夫曼编码等。4、图在数据结构中，图的结构是最复杂的，这里的概念也是最多的。我们要掌握图的基本概念(有向图、无向图、连通、路径、子图、出度、入度、生成树、最短路径、关键路径等)。图的及基本操作主要有邻接矩阵法和邻接表法，我们要掌握这有向图

6、和无向图的这 2 种方法，要清楚图的连通和方法之间的关系。例如，一个顶点的出度和临界矩阵中 1 的个数有什么关系，等等。图的遍历方法有深度优先搜索和广度优先搜索，我们要掌握这 2 种遍历方法的算法实现。给出一个具体的图，要能知道它的遍历次序。在数据结构课程中，图的基本应用是最多的，也是最复杂的，我们要掌握这些应用的复杂度分析。要掌握的具体应用主要包括最小(代价)生成树、最短路径、拓扑排序、关键路径。在给出的一个具体的图中，我们要会利用已知条件，求出上述应用的结果。5、查找在给定的数据集合中查找某个关键值就是查找，查找的基本方法主要有顺序查找法、折半查找法、B-树、散列(Hash)表及其查找。考

7、的比较多的是折半查找和散列表，我们要掌握它们的基本概念和方法，例如散列表的碰撞如何解决，装载因子的概念等。另外，我们要掌握各种查找算法的分析及应用，最好能把各种查找在查找成功、查找失败的情况下的最好、平均、最坏的平均查找次数的计算方法搞清楚。6、内部排序根据大纲，只考查内部排序。所谓内部排序，就是在内存中进行排序。在这一部分中，主要要掌握直接排序、折半排序、冒泡排序(bubble sort)、简单选择排序、希尔排序(shell sort)、快速排序、堆排序、二路归并排序(mergesort)、基数排序的基本概念和方法。搞清楚这些排序方法的流程，以及它们之间的区别。在这个知识点，一个很重要的考查

8、点就是各种内部排序算法的比较，一般的书上都会有这样的一个表格，列出了所有排序在各种情况下(最好、最坏、平均)的时间复杂度和空间复杂度，这个表是需要我们记下来的。当然，如果我们能掌握复杂度的计算方法，自己能推算出来，那就更好了。最后，就是要掌握内部排序算法的基本应用，以及算法的实现。【复习方法】1、的选择从大纲来看，所要求的知识在一般的大学数据结构中都已经包含，所以，选择哪本书并不是最重要的事情。不过，根据希赛教育推荐，对于数据结构的复习，可以选择的数据结构(第二版)(严蔚编)。这本书有多种语言的版本，建议选择 C 语言的版本，在复习的过程中，还可以配以相应的习题集。2、学习方法对于数据结构的学

9、习，难在其中的算法及实现。有条件的考生，可以在计算机上编写程序，自己实现上的算法(要注意，书上的算法通常都采用伪代码编写，需要我们自己用某种程序设计语言去具体实现)。如果没有条件，那就只有在心里进行推导了，可以使用实际的例子，手工“实现”算法。数据结构【考查目标】1. 理解数据结构的基本概念；掌握数据的逻辑结构、结构及其差异，以及各种基本操作的实现。2. 掌握基本的数据处理原理和方法的基础上，能够对算法进行设计与分析。3. 能够选择合适的数据结构和方法进行问题求解。一、线性表大纲要求：（一）线性表的定义和基本操作（二）线性表的实现1.顺序结构2. 链式结构3. 线性表的应用知识点：1深刻理解数

10、据结构的概念，掌握数据结构的“三要素”：逻辑结构、物理（存储）结构及在这种结构上所定义的操作“运算”。2时间复杂度和空间复杂度的定义，常用计算语句频度来估算算法的时间复杂度。以下六种计算算法时间的多项式是最常用的。其关系为：O(1)<O(logn)<O(n)<O(nlogn) <O(n2)<O(n3)指数时间的关系为： O(2n)<O(n!)<O(nn)3线性表的逻辑结构，是指线性表的数据元素间存在着线性关系。主要是指：除第一及最后一个元素外，每个结点都只有一个前趋和只有一个后继。在顺序结构中，元素的先后位置反映出这种逻辑关系，而在链式结构中，是靠指针

11、来反映这种逻辑关系的。4顺序结构用向量（一维数组）表示，给定下标，可以存取相应元素，属于随机存取的结构。5线性表的顺序方式及其在具体语言环境下的两种不同实现：表空间的静态分配和动态分配。掌握顺序表上实现、删除、等运算的算法。6尽管“只要知道某结点的指针就可以存取该元素”，但因链表的存取都需要从头指针开始，顺链而行，故链表不属于随机存取结构。要理解头指针、头结点、首元结点和元素结点的差别。头结点是在、删除等操作时，为了算法的统一而设立的（若无头结点，则在第一元素前元素或删除第一元素时，链表的头指针总在变化）。对链表（不包括循环链表）的任何操作，均要从头结点开始，头结点的指针具有标记作用，故头指针

12、往往被称为链表的名字，如链表head是指链表头结点的指针是head。理解循环链表中设置尾指针而不设置头指针的好处。链表操作中应注意不要使链意外“断开”。因此，若在某结点前一个元素或删除某元素，必须知道该元素的前驱结点的指针。7链表是本部分学习的重点和难点。重点掌握以下几种常用链表的特点和运算：单链表、循环链表、双向链表、双向循环链表的生成、删除、遍历以及链表的分解和归并等操作。并能够设计出实现线性表其它运算的算法。8从时间复杂度和空间复杂度的角度综合比较线性表在顺序和链式两种结构下的特点，即其各自适用的场合。小结：顺序表和链表的比较通过对它们的讨论可知它们各有优缺点，顺序有三个优点：（1）方法

13、简单，各种高级语言中都有数组，容易实现。（2）不用为表示结点间的逻辑关系而增加额外的开销。（3）顺序表具有按元素序号随机的特点。但它也有两个缺点：（1）在顺序表中做删除操作时，平均移动大约表中一半的元素，因此对n较大的顺序表效率低。（2）需要预先分配足够大的空间，估计过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。链表的优缺点恰好与顺序表相反。在实际中怎样选取结构呢？（1）基于的考虑对线性表的长度或规模难以估计时，不宜采用顺序表；链表不用事先估计规模，但链表的密度较低，显然链式结构的密度是小于的。（2）基于运算的考虑在顺序表中按序号ai的时间性能时O(1)，而链表中按序号的时间

14、性能O(n)，所以如果经常做的运算是按序号数据元素，显然顺序表优于链表；而在顺序表中做、删除时平均移动表中一半的元素，当数据元素的信息量较大且表较长时，这一点是不应忽视的；在链表中作、删除，虽然也要找位置，但操作主要是比较操作，从这个角度考虑显然后者优于前者。（3）基于环境的考虑顺序表容易实现，任何高级语言中都有数组类型，链表的操作是基于指针的，相对来讲前者简单些，也是用户考虑的一个因素。总之，两种结构各有长短，选择那一种由实际问题中的主要因素决定。通常“较稳定”的线性表选择顺序，而频繁做删除的即动态性较强的线性表宜选择链式。练习题：（一）选择题：1以下那一个术语与数据的结构无关？（ A）A队

15、列B. 哈希表C. 线索树D.双向链表2、一个算法应该是（B）。A程序B问题求解步骤的描述C要满足五个基本特性DA 和 C.3、数据结构中，与所使用的计算机无关的是数据的（ C）A结构B物理结构C逻辑结构D物理结构和结构4. 算法的计算量的大小称为计算的（B）。A效率B复杂性C现实性D难度5下列说法，不正确的是（D）。A数据元素是数据的基本B数据项是数据中不可分割的最小可标识C数据可由若干个数据元素构成D数据项可由若干个数据元素构成6连续设计时，单元的地址（A）。A一定连续B一定不连续C不一定连续D部分连续，部分不连续7.线性表（ a1,a2,an）以方式时，第 i 位置元素的时间复杂性为（C

16、）。AO（i）BO（1）CO（n）DO（i-1）8.对于顺序的线性表，结点和增加、删除结点的时间复杂度为（ C）。AO(n)O(n)B. O(n)O(1)C. O(1)O(n)D. O(1)O(1)9.设单链表中结点的结构为（data，link）。已知指针 q 所指点是指针 p 所指结点的直接前驱，若在*q 与*p 之间结点*s，则应执行下列哪一个操作？（B）。As>link=p>link；p>link=sBq>link=s；s>link=pCp>link=s>link；s>link=pDp>link=s；s>link=q10. 在一

17、个长度为n 的顺序表的表尾一个新元素的渐进时间复杂度为（ B ）。AO（n）BO（1）CO（n2）DO（log2n）11. 表长为n 的顺序的线性表，当在任何位置上一个元素的概率相等时，一个元素所需移动元素的平均个数为（ B ）AnB. n/2C. (n-1)/2D. (n+1)/212. 循环链表的主要优点是（D ）A不再需要头指针了。B已知某个结点的位置后，能很容易找到它的直接前驱结点。C在进行删除操作后，能保证链表不断开。D从表中任一结点出发都能遍历整个链表。（二）应用题1、按增长率由小至大排列以下 7 个函数。log nn2n223（ ）n、（ ）n、2100、log)2、log、(l

18、og、n2322log nnn2232答：（ ）n、2100、log3)2）n、log、(log、n、（2222、数据的结构由哪四种基本的方法实现，并做以简要说明？答：四种表示方法（1）顺序方式。数据元素顺序存放，每个结点只含一个元素。位置反映数据元素间的逻辑关系。密度大，但有些操作（如、删除）效率较差。（2）链式方式。每个结点除包含数据元素信息外还包含一组（至少一个）指针。指针反映数据元素间的逻辑关系。这种方式不要求空间连续，便于动态操作（如、删除等），但空间开销大（用于指针），另外不能折半查找等。（3）索引方式。除数据元素在一地址连续的内存空间外，尚需建立一个索引表，索引表中索引指示结点的

19、位置（下标）或区间端点（下标），兼有静态和动态特性。（4）散列方式。通过散列函数和解决的方法，将关键字散列在连续的有限的地址空间内，并将散列函数的值解释成关键字所在元素的地址，这种方式称为散列。其特点是存取速度快，只能按关键字随机存取，不能顺序存取，也不能折半存取。3. 线性表有两种结构：一是顺序表，二是链表。试问：（1）如果有 n 个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种结构？ 为什么？（2）若线性表的总数基本稳定，且很少进行和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种结构？为什么？答：（1）选链式结构。它可动

20、态申请内存空间，不受表长度（即表中元素个数）的影响，、删除时间复杂度为 O（1）。（2）选顺序结构。顺序表可以随机存取，时间复杂度为 O（1）。（三）算法设计题1设计算法，求带表头的单循环链表的表长。解：int length(Linklist L)int I;listnode *p;I=0;P=L;while (p->next!=L)p=p->next;I+;return I;2.已知单链表 L，写一算法，删除其重复结点。算法思路：用指针 p 指向第一个数据结点，从它的后继结点开始到表的结束，找与其值相同的结点并删除之；p 指向下一个；依此类推，p 指向最后结点时算法结束。算法如下

21、：解：void pur_LinkList(LinkList H) LNode*p,*q,*r;p=H->next;/*p 指向第一个结点*/if(p=NULL) return;while (p->next)q=p;while (q->next)/* 从*p 的后继开始找重复结点*/ if(q->next->data=p->data)r=q->next;/*找到重复结点，用 r 指向，删除*r*/q->next=r->next;free(r);/*if*/else->next; /*while(q->next)*/p=p->

22、next;/*p 指向下一个，继续*/*while(p->next)*/该算法的时间性能为 O(n2)。3.已知指针 la 和 lb 分别指向两个无头结点的单链表中的首结点。请编写函数完成从表 la 中删除自第i 个元素开始的共 len 个元素并将它们到表 lb 中第j个元前，若 lb 中只有 j-1 个元素，则插在表尾。函数原型如下：int DeleteAndInsertSub(LinkList &la,LinkList &lb,int i,int j,int len)；答：int DeleteAndInsertSub(LinkList &la,LinkList

23、 &lb,int i,int j,int len)int k;LinkList p,q,prev,s;if(i<0|j<0|len<0)return -1;p=la;k=1;prev=NULL;while(p&&k<i)prev=p;p=p->next;k+;if(!p)return -1;q=p;k=1;while(q&&k<len)->next;k+;if(!q)return -1;if(!prev)la=q->next;elseprev->next=q->next;if(j=1)q->

24、;next=lb;lb=q;elses=lb;k=1;while(s&&k<j-1)s=s->next;k+;if(!s)return -1;q->next=s->next;s->next=p;return 1;4写一算法，将一带有头结点的单链表就地逆置，即要求逆置在原链表上进行，不允许重新构造新链表。(a)L(b)L图单链表的倒置29761845252545187629函数原型如下：void LinkList_reverse(LinkList &L)；答：void LinkList_reverse(LinkList &L)Link

25、List p,q,s;p=L->next;q=p->next;s=q->next;p->next=NULL;while(s->next)q->next=p;p=q;q=s;s=s->next;q->next=p;s->next=q;L->next=s;5写一算法，将带有头结点的非空单链表中数据域值最小的那个结点移到链表的最前面。要求：不得额外申请新的链结点。函数原型如下：void delinsert(LinkList &L)；答：void delinsert(LinkList &L)p=L->next; /p 是

26、链表的工作指针pre=L; /pre 指向链表中数据域最小值结点的前驱q=p;/q 指向数据域最小值结点，初始假定是第一结点while(p->next!=NULL)if(p->next->data<q->data)/找到新的最小值结点pre=p; q=p->next; p=p->next;if(q!=L->next)/若最小值是第一元素结点，则不需再操作pre->next=q->next;/将最小值结点从链表上摘下q->next=L->next;/将 q 结点插到链表最前面L->next=q;6编写一个算法来交换单链

27、表中指针 P 所指结点与其后继结点，HEAD 是该链表的头指针，P 指向该链表中某一结点。答：单链表中查找任何结点，都必须从头指针开始。本题要求将指针 p 所指结点与其后继结点交换，这不仅要求知道 p 结点，还应知道 p 的前驱结点。这样才能在 p 与其后继结点交换后，由原 p 结点的前驱来指向原 p 结点的后继结点。LinkedList Exchange（LinkedList HEAD，p）HEAD 是单链表头结点的指针，p 是链表中的一个结点。本算法将 p 所指结点与其后继结点交换。q=head->next；q 是工作指针，指向链表中当前待处理结点。pre=head；pre 是前驱结

28、点指针，指向 q 的前驱。while（q!=null &&q!=p）pre=q->next；未找到 p 结点，后移指针。if（p->next=null）printf（“p 无后继结点n”）;p 是链表中最后一个结点，无后继。Else处理 p 和后继结点交换q=p->next；暂存 p 的后继。pre->next=q；p 前驱结点的后继指向 p 的后继。p->next=q->next；p 的后继指向原 p 后继的后继。q->next=p；原 p 后继的后继指针指向 p。算法结束。7已知线性链表第一个链结点指针为 list，请写一算法，将该

29、链表分解为两个带有头结点的循环链表，并将两个循环链表的长度分别存放在各自头结点的数据域中。其中,线性表中序号为偶数的元素分解到第一个循环链表中,序号为奇数的元素分解到第二个循环链表中。答：算法如下：void split(ListNode *List, ListNode *&list1, ListNode*&list2)list1=(ListNode *)malloc(sizeof(ListNode )；list2=(ListNode *)malloc(sizeof(ListNode)；p=list;；q=list1；r=list2；len1=0；len2=0；mark=1；wh

30、ile (p!=null)if(mark=1)q->next=p;->next;len1+;mark=2;elser->next=p;r=r->next;len2+;mark=1;list1->data=len1;list2->data=len2;q->next=list1;r->next=list2;8. 设 A 和 B 是两个单链表，其表中元素递增有序。试写一算法将 A 和 B 归并成一个按元素值递减有序的单链表 C，并要求辅助空间为 O(1)。答：Linklist merge(Linklist A,Linklist B)Linklist C

31、;Listnode *p;C=null;while (A&&B)if(A->data<=B->data)p=A->next;A->next=C;C=A;A=p;elsep=B->next;B->next=C;C=B;B=p;if (A)while(A) p=A->next;A->next=C;C=A;A=p;elsewhile(B) p=B->next;B->next=C;C=B;B=p;return C;二、栈、队列和数组大纲要求：（一）栈和队列的基本概念（二）栈和队列的顺序结构（三）栈和队列的链式结构（四）栈

32、和队列的应用（五）特殊矩阵的压缩知识点：1栈、队列的定义及其相关数据结构的概念，包括：顺序栈、链栈、循环队列、链队列等。栈与队列存取数据（请注意包括：存和取两部分）的特点。2掌握顺序栈和链栈上的进栈和退栈的算法，并弄清栈空和栈满的条件。注意因栈在一端操作，故通常链栈不设头结点。3如何将中缀表达式转换成前缀、后缀表达式，了解对两种表达式求值的方法。4栈与递归的关系。用递归解决的几类问题：问题的定义是递归的，数据结构是递归的，以及问题的解法是递归的。掌握典型问题的算法以及将递归算法转换为非递归算法，如n!阶乘问题，fib数列问题，hanoi问题。了解在数值表达式的求解、括号的配对等问题中应用栈的工

33、作原理。5掌握在链队列上实现入队和出队的算法。注意对仅剩一个元素的链队列删除元素时的处理（令队尾指针指向队头）。还需特别注意仅设尾指针的循环链队列的的实现。6循环队列队空及队满的条件。队空定义为队头指针等于队尾指针，队满则可用牺牲一个单元或是设标记的方法，这里特别注意取模运算。掌握循环队列中入队与出队算法。7在后续章节中多处有栈和队列的应用，如二叉树遍历的递归和非递归算法、图的深度优先遍历等都用到栈，而树的层次遍历、图的广度优先遍历等则用到队列。这些方面的应用应重点掌握。8数组在（内存）级上采用顺序结构。掌握数组（主要是二维）在以行序为主和列序为主的中的地址计算方法。9特殊矩阵（对称矩阵、对角

34、矩阵、三角矩阵）在压缩是的下标变换公式。练习题：（一）选择题：1. 一个栈的输入序列为 1 2 3 4，则（D ）不可能是其出栈序列。A. 1 2 4 3B. 2 1 34C.143 2D. 4 3 1 22. 一个递归算法必须包括（B）。A. 递归部分B. 终止条件和递归部分C. 迭代部分D.终止条件和迭代部分3.一个递归的定义可以用递归过程求解，也可以用非递归过程求解，但单从运行时间来看，通常递归过程比非递归过程（B）。A较快B较慢C相同D以上都不对4.栈和队列都是（C）A顺序的线性表B链式的线性表C限制的线性表D限制的非线性结构5.二维数组 N 的元素是 4 个字符（每个字符占一个单元）

35、组成的串，行下标 i 的范围从 0 到 4，列下标 j 的范围从 0 到 5，N 按行时元素 N35的起始地址与 N 按列时元素（B）的起始地址相同。A. N24B. N34C. N35D. N446.设有数组 Ai,j，数组的每个元素长度为 3 字节，i 的值为 1 到 8，j 的值为 1 到 10，数组从内存首地址 BA 开始顺序存放，当以列为主序存放时，元素 A5,8的首地址是（B）A. BA+141B. BA+180C. BA+222D. BA+2257.递归过程或函数调用时，处理参数及返回地址，要用一种称为（ C ）的数据结构。A队列B数组C栈D. 线性表8.对于单链表形式的队列，队

36、空的条件是（ A ）AFRnilBFRCFnil 且 RnilDRF19.若循环队列以数组 Q0.m-1作为其结构，变量 rear 表示循环队列中的队尾元素的实际位置，其移动按 rear=(rear+1) Mod m 进行，变量 length表示当前循环队列中的元素个数，则循环队列的队首元素的实际位置是（ C ）Arear-lengthB(rear-length+m) Mod mC(1+rear+m-length) Mod mDM-length（二）应用题1、（10 分）假设一个准对角矩阵éa11ùúúúúúú&#

37、250;úúúa2m-1,2m úa12êaaêêêêêêêêêê2122a33a34aa4344.ai, j.a2m-1,2m-1êúaaëû2m,2m-12m,2m按以下方式于一维数组 B4m中：01234k4m24m1写出由一对下标（i，j）表示的 k 的转换公式。答：i 为奇数时 k=i+j-2i 为偶数时 k=i+j-1合并后可写成 k=i+j-(i%2)-1或k=2(i/2)+j-12、特殊矩阵

38、和稀疏矩阵哪一种压缩后失去随机存取的功能？为什么？答：特殊矩阵指值相同的元素或零元素在矩阵中的分布有一定规律，因此可以对非零元素分配单元（对值相同元素只分配一个单元），将非零元素在向量中，元素的下标 i 和 j 和该元素在向量中的下标有一定规律，可以用简单公式表示，仍具有随机存取功能。a1,1a1,2a2,1a2,2a3,3.ai, j.a2m,2m-1a2m,2m而稀疏矩阵是指非零元素和矩阵容量相比很小（t<<m*n），且分布没有规律。用十字链表作结构自然失去了随机存取的功能。即使用三元组表的顺序结构，存取下标为 i 和 j 的元素时，要扫描三元组表，下标不同的元素，存取时间也不

39、同，最好情况下存取时间为 O(1)，情况下是 O(n)，因此也失去了随机存取的功能。3、有人说，采用循环链表作为结构的队列就是循环队列，你认为这种说法对吗？说明你的理由。答：这种说法是错误的。队列（包括循环队列）是一个逻辑概念，而链表是一个概念，一个队列是否是循环队列。不取决于它将采用何种结构。根据实际的需要，循环队列可以采用顺序结构，也可以采用链式结构，包括采用循环链表作为结构。4、指出下列程序段的功能是什么？(1) void demo1(seqstack *s)int I;arr64;n=0;while (!stackempty(s) arrn+=pop(s);for(I=0;<n;

40、I+) push(s,arrI);(2) void demo2(seqstack *s,int m)seqstack t; int i;initstack(t);while(! Stackempty(s)if(I=pop(s)!=m) push(t,I);while(! Stackempty(t) i=pop(t);push(s,I);（三）算法设计题1 试利用循环队列编写求 k 阶斐波那契序列中前 n+1 项（ f0 , f1 ,fn ）的算法，要求满足 f n £ max 且> max ，其中 max 为某个约定的常数。循环队列的容量f n+1为 k，因此，在算法执行结束时

41、，留在循环队列中的元素应是所求 k 阶斐波那契序列中的最后 k 项 f n-k +1 ,fn 。答：void GetFib(int k,int n)InitQueue(Q);for(i=0;k<k-1;i+)Q.basei=0;Q.basek-1=1;for(i=0;i<k;i+)printf(“%d”,Q.basei);for(i=k;i<=n;i+)m=i%k;sum=0;for(j=0;j<k;j+)sum+=Q.base(m+j)%k;Q.basem=sum;printf(“%d”,sum);2. 已知 num 为无符号十进制整数，请写一非递归算法，该算法输出

42、num 对应的r 进制的各位数字。要求算法中用到的栈采用线性链表结构（1<r<10）。解：typedef struct nodeint data;struct node *next;link;void trans(int num,int r)link *head=NULL,*s;int n;while (num>0)n=num%r;s=(link *)malloc(sizeof(link);s->data=n;s->next=head;head=s;num=num/r;printf(“输出 r 进制的各位数字：”)；s=head;while (s!=NULL)pr

43、intf(“%d”,s->data);s=s->next;三、树与二叉树大纲要求：（一） 树的概念（二） 二叉树1.二叉树的定义及其主要特征2.二叉树的顺序结构和链式结构3.二叉树的遍历4.线索二叉树的基本概念和构造5.二叉排序树6.平衡二叉树（三）树、森林1.树的结构2.森林与二叉树的转换3.树和森林的遍历（四）树的应用1.等价类问题2.哈夫曼（Huffman）树和哈夫曼编码知识点：1.二叉树的概念、性质（1）掌握树和二叉树的定义。（2）理解二叉树与普通双分支树的区别。二叉树是一种特殊的树，这种特殊不仅仅在于其分支最多为2以及其它特征，一个最重要的特殊之处是在于：二叉树是有序的。

44、即二叉树的左右孩子是不可交换的，如果交换了就成了另外一棵二叉树，这样交换之后的二叉树与原二叉树是不相同的两棵二叉树。但是，对于普通的双分支树而言，不具有这种性质。（3）满二叉树和完全二叉树的概念。（4）重点掌握二叉树的五个性质及证明方法，并把这种方法推广到K叉树。普通二叉树的五个性质：第i层的最多结点数，深度为k的二叉树的最多结点数，n0=n2+1的性质，n个结点的完全二叉树的深度，顺序二叉树时孩子结点与父结点之间的换算关系（序号i结点的左孩子为：2*i，右孩子为：2*i+1）。2.掌握二叉树的顺序结构和二叉链表、三叉链表结构的各自优缺点及适用场合，以及二叉树的顺序结构和二叉链表结构的相互转换

45、的算法。3.熟练掌握二叉树的先序，中序和后序遍历算法以及按层次遍历二叉树的先序、中序和后序三种遍历算法，划分的依据是视其每个算法中对根结点数据的顺序而定。不仅要熟练掌握这三种遍历的递归算法，理解其执行的实际步骤，并且应该熟练掌握三种遍历的非递归算法。按层次遍历二叉树void LayerOrder(Bitree T)/层序遍历二叉树InitQueue(Q); /建立工作队列EnQueue(Q,T);while(!QueueEmpty(Q)DeQueue(Q,p);visit(p);if(p->lchild) EnQueue(Q,p->lchild);if(p->rchild)

46、EnQueue(Q,p->rchild);/LayerOrder4.遍历是基础，重点掌握在三种基本遍历算法的基础上实现二叉树的其它算法如求二叉树叶子结点总数，求二叉树结点总数，求度为1或度为2的结点总数，二叉树，建立二叉树，交换左右子树，查找值为n的某个指定结点，删除值为n的某个指定结点等等。5.线索二叉树的引出，是为避免如二叉树遍历时的递归求解。递归虽然形式上比较好理解，但是消耗了大量的内存，如果递归层次一多，势必带来资源耗尽的。二叉树线索化的实质是建立结点在相应序列中与其前驱和后继之间的直接。对于线索二叉树，应该掌握：线索化的实质，三种线索化的算法，线索化后二叉树的遍历算法，基本线索

47、二叉树的其它算法问题（如：查找某一类线索二叉树中指定结点的前驱或后继结点）。6.二叉排序树的中序遍历结果是一个递增的有序序列。二叉排序树的形态取决于元素的输入顺序，二叉排序树在情况下形成单支树。熟练掌握其建立、查找、和删除算法，以及判断某棵二叉树是否二叉排序树这一问题的递归与非递归算法。7.平衡二叉树是二叉排序树的优化，平衡二叉树对左右子树的深度有了限定：深度之差的绝对值不得大于1。掌握平衡二叉树的四种调整算法。8.树与森林的遍历，只有两种遍历算法：先根与后根（对于森林而言称作：先序与中序遍历）。二者的先根与后根遍历与二叉树中的遍历算法是有对应关系的：先根遍历对应二叉树的先序遍历，而后根遍历对

48、应二叉树的中序遍历。二叉树使用二叉链表分别存放它的左右孩子，树利用二叉链表孩子及兄弟（称孩子兄弟链表），而森林也是利用二叉链表孩子及兄弟。掌握树、森林和二叉树间的相互转换。9.简单掌握等价类的生成算法。10. 哈夫曼树为了解决特定问题引出的特殊二叉树结构，它的前提是给二叉树的每条边赋予了权值，这样形成的二叉树按权相加之和是最小的，一般来说，哈夫曼树的形态不是唯一的。理解哈夫曼编码的基本原理，掌握基于哈夫曼树生成哈夫曼编码的方法。练习题：（一）选择题：1. 一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为 CBAEDF，则后序遍历结果为（ A）A. CBEFDAB. FEDCBAC. CB

49、EDFAD. 不确定2. 某二叉树的后序遍历序列为dabec，中序遍历序列为 debac，则前序遍历序列为（D）。AacbedBdecabCdeabcDcedba3.具有 10 个叶子结点的二叉树中有（ B）个度为 2 的结点。A. 8B. 9C. 10D. 114.树中所有结点的度等于所有结点数加（ C）。A0B1C1D25.设 n，m 为一棵二叉树的两个结点，在中序遍历时，n 在 m 前的条件是（ C ）A. n 在 m 的右方B. n 是 m 的祖先C. n 在 m 的左方D. n 是 m 的子孙6.利用逐点建立序列（50，72，43，85，75，20，35，45，65，30）对应的二叉

50、排序树以后，要查找元素 30 要进行（ B ）次元素间的比较。A4B. 5C6D. 77.在平衡二叉树中，（C ）。A任意结点的左、右子树结点数目相同B任意结点的左、右子树高度相同C任意结点的左右子树高度之差的绝对值不大于 1D不存在度为 1 的结点8.由元素序列（27，16，75，38，51）构造平衡二叉树，则首次出现的最小不平衡子树的根（即离结点最近且平衡因子的绝对值为 2 的结点）为（ D ）A27B38C51D. 759.在二叉树的顺序中，每个结点的位置与其父结点、左右子树结点的位置都存在一个简单的关系，因此可与三叉链表对应。若某二叉树共有n 个结点，采用三叉链表时，每个结点的数据域需

51、要 d 个字节，每个指针域占用 4 个字节，若采用顺序，则最后一个结点下标为 k（起始下标为 1），那么（ A）时采用顺序更节省空间。Ad<12n/(k-n)B. d>12n/(k-n)C. d<12n/(k+n)D. d>12n/(k+n)10. 在常用的描述二叉排序树的结构中，关键字值最大的结点（ B ）A左指针一定为空B. 右指针一定为空C左右指针均为空D. 左右指针均不为空（二）应用题1、一棵满 k 叉树，按层次遍历（从 1 开始对全部结点进行编号）在一维数组中，试计算编号为 u 的结点的第 i 个孩子（若存在）的下标以及编号为 v 的结点的双亲结点（若存在）的

52、下标。答：结点下标为 u 的结点的第 i 个孩子的下标： k(u -1) + 1 + i结点下标为 v 的结点的父母结点的下标： ë(v - 2) / k û + 12、试求有 n 个叶结点的非满的完全二叉树的高度.答：完全二叉树中叶子结点数为 n，则根据完全二叉树的性质，度为 2 的结点数是 n-1，而完全二叉树中，度为 1 的结点数至多为 1，所以具有 n 个叶子结点的完全二叉树结点数是 n+(n-1)+1=2n 或 2n-1（有或无度为 1 的结点）。由于具有 2n( 或 2n-1) 个结点的完全二叉树的深度是ëlog2(2n)û+1( 或ëlog2(2n-1)û+1)，即élog2nù+1,故 n 个叶结点的非满的完全二