《数据结构讲义》由会员分享，可在线阅读，更多相关《数据结构讲义（34页珍藏版）》请在金锄头文库上搜索。
1、1【考查目标】 1. 理解数据结构的基本概念；掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现。 2. 掌握基本的数据处理原理和方法的基础上，能够对算法进行设计与分析。 3. 能够选择合适的数据结构和方法进行问题求解。 一、线性表大纲要求：（一） 线性表的定义和基本操作 （二） 线性表的实现 1. 顺序存储结构 2. 链式存储结构 3. 线性表的应用 知识点：1 深刻理解数据结构的概念，掌握数据结构的“三要素”：逻辑结构、物理（存储）结构及在这种结构上所定义的操作“运算”。2 时间复杂度和空间复杂度的定义，常用计算语句频度来估算算法的时间复杂度。以下六种计算算法时间的多项式是最常用
2、的。其关系为：O(1)link=plink；plink=sBqlink=s；slink=pCplink=slink；slink=pDplink=s；slink=q10. 在一个长度为 n 的顺序表的表尾插入一个新元素的渐进时间复杂度为（ B ） 。AO（n） BO（1） CO（n 2） DO（log 2n）11. 表长为 n 的顺序存储的线性表，当在任何位置上插入一个元素的概率相等时，插入一个元素所需移动元素的平均个数为（ B ）An B. n/2C. (n-1)/2 D. (n+1)/212. 循环链表的主要优点是（ D ）A不再需要头指针了。B已知某个结点的位置后，能很容易找到它的直接前驱
3、结点。C在进行删除操作后，能保证链表不断开。D从表中任一结点出发都能遍历整个链表。（二）应用题1、按增长率由小至大排列以下 7 个函数。 nnnn 、）、 （）（ 210 )(logl2log23答： nn ）、 （、）（ 3)(lll3 2102、数据的存储结构由哪四种基本的存储方法实现，并做以简要说明？答：四种表示方法（1）顺序存储方式。数据元素顺序存放，每个存储结点只含一个元素。存储位置反映数据元素间的逻辑关系。存储密度大，但有些操作（如插入、删除）效率较差。（2）链式存储方式。每个存储结点除包含数据元素信息外还包含一组（至少一个）指针。指针反映数据元素间的逻辑关系。这种方式不要求存储空
4、间连续，便于动态操作（如插入、删除等） ，但存储空间开销大（用于指针） ，另外不能折半查找等。（3）索引存储方式。除数据元素存储在一地址连续的内存空间外，尚需建立一个索引表，索引表中索引指示存储结点的存储位置（下标）或存储区间端点（下标） ，兼有静态和动态特性。（4）散列存储方式。通过散列函数和解决冲突的方法，将关键字散列在连续的有限的地址空间内，并将散列函数的值解释成关键字所在元素的存储地址，这种存储方式称为散列存储。其特点是存取速度快，只能按关键字随机存取，不能顺序存取，也不能折半存取。3. 线性表有两种存储结构：一是顺序表，二是链表。试问：（1）如果有 n 个线性表同时并存，并且在处理过
5、程中各表的长度会动态变化，线性表的总数也4会自动地改变。在此情况下，应选用哪种存储结构？ 为什么？（2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？ 答：（1）选链式存储结构。它可动态申请内存空间，不受表长度（即表中元素个数）的影响，插入、删除时间复杂度为 O（1） 。（2）选顺序存储结构。顺序表可以随机存取，时间复杂度为 O（1） 。（三）算法设计题1设计算法，求带表头的单循环链表的表长。解：int length(Linklist L)int I;listnode *p;I=0;P=L;while (p-next!=L)
6、p=p-next;I+;return I;2.已知单链表 L，写一算法，删除其重复结点。算法思路：用指针 p 指向第一个数据结点，从它的后继结点开始到表的结束，找与其值相同的结点并删除之；p 指向下一个；依此类推，p 指向最后结点时算法结束。算法如下：解：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-nex
7、t; /*找到重复结点，用 r 指向，删除*r */q-next=r-next; free(r); /*if*/else q=q-next; /*while(q-next)*/p=p-next; /*p 指向下一个，继续*/ /*while(p-next)*/该算法的时间性能为 O(n2)。3.已知指针 la 和 lb 分别指向两个无头结点的单链表中的首结点。请编写函数完成从表 la 中删除自第 i 个元素开始的共 len 个元素并将它们插入到表 lb 中第 j 个元素之前，若 lb 中只有 j-1 个元素，5则插在表尾。函数原型如下：int DeleteAndInsertSub(LinkLi
8、st &la,LinkList &lb,int i,int j,int len)；答：int DeleteAndInsertSub(LinkList &la,LinkList &lb,int i,int j,int len)int k; LinkList p,q,prev,s;if(inext;k+;if(!p)return -1;q=p;k=1;while(q&knext;k+;if(!q)return -1;if(!prev)la=q-next;elseprev-next=q-next;if(j=1)q-next=lb;lb=q;elses=lb;k=1;while(s&knext;k+;
9、if(!s)return -1;q-next=s-next;6s-next=p;return 1;4写一算法，将一带有头结点的单链表就地逆置，即要求逆置在原链表上进行，不允许重新构造新链表。函数原型如下：void LinkList_reverse(LinkList &L)；答：void LinkList_reverse(LinkList &L)LinkList 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写一算法，将
10、带有头结点的非空单链表中数据域值最小的那个结点移到链表的最前面。要求：不得额外申请新的链结点。函数原型如下：void delinsert(LinkList &L)；答：void delinsert(LinkList &L)p=L-next; /p 是链表的工作指针pre=L; /pre 指向链表中数据域最小值结点的前驱q=p; /q 指向数据域最小值结点，初始假定是第一结点while(p-next!=NULL)if(p-next-datadata) /找到新的最小值结点 pre=p; q=p-next; p=p-next;if(q!=L-next) /若最小值是第一元素结点，则不需再操作pre
11、-next=q-next; /将最小值结点从链表上摘下q-next=L-next; /将 q 结点插到链表最前面L-next=q;图 单链表的倒置25 4525187629L29 7625184525L(a)(b)76编写一个算法来交换单链表中指针 P 所指结点与其后继结点，HEAD 是该链表的头指针，P 指向该链表中某一结点。答：单链表中查找任何结点，都必须从头指针开始。本题要求将指针 p 所指结点与其后继结点交换，这不仅要求知道 p 结点，还应知道 p 的前驱结点。这样才能在 p 与其后继结点交换后，由原 p 结点的前驱来指向原 p 结点的后继结点。LinkedList Exchange（
12、LinkedList HEAD，p）HEAD 是单链表头结点的指针，p 是链表中的一个结点。本算法将 p 所指结点与其后继结点交换。q=head-next； q 是工作指针，指向链表中当前待处理结点。pre=head； pre 是前驱结点指针，指向 q 的前驱。while（q!=null & q!=p）pre=q；q=q-next； 未找到 p 结点，后移指针。if（p-next=null）printf（“p 无后继结点n” ）; p 是链表中最后一个结点，无后继。Else 处理 p 和后继结点交换q=p-next； 暂存 p 的后继。pre-next=q； p 前驱结点的后继指向 p 的后继
13、。p-next=q-next；p 的后继指向原 p 后继的后继。q-next=p ；原 p 后继的后继指针指向 p。算法结束。7已知线性链表第一个链结点指针为 list，请写一算法，将该链表分解为两个带有头结点的循环链表，并将两个循环链表的长度分别存放在各自头结点的数据域中。其中,线性表中序号为偶数的元素分解到第一个循环链表中,序号为奇数的元素分解到第二个循环链表中。答：算法如下：void split(ListNode *List, ListNode *&list1, ListNode *&list2)list1=(ListNode *)malloc(sizeof(ListNode )；lis
14、t2=(ListNode *)malloc(sizeof(ListNode )；p=list;；q=list1；r=list2；len1=0；len2=0；mark=1；while (p!=null)if(mark=1)q-next=p;q=q-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，并要求辅助
15、空间为 O(1)。8答：Linklist merge(Linklist A,Linklist B)Linklist C;Listnode *p;C=null;while (A&B)if(A-datadata)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;二、栈、队列和数组大纲要求：（一） 栈和队列的基本概念 （二） 栈和队列的顺序存储结构 （三） 栈和队列的链式存储结构 （四） 栈和队列的应用 （五） 特殊矩阵的压缩存储 知识点：1 栈、队列的定义及其相关数据结构的概念，包括：顺序栈、链栈、循环队列、链队列等。栈与队列存取数据（请注意包括：
