《数据结构讲义》由会员分享,可在线阅读,更多相关《数据结构讲义(36页珍藏版)》请在金锄头文库上搜索。
1、考查目标】1. 理解数据结构的基本概念;掌握数据的逻辑结构、存储结构及其差异,以及各种基本操作的 实现。2. 掌握基本的数据处理原理和方法的基础上,能够对算法进行设计与分析。3. 能够选择合适的数据结构和方法进行问题求解。、线性表大纲要求:(一) 线性表的定义和基本操作(二) 线性表的实现1. 顺序存储结构2. 链式存储结构3. 线性表的应用 知识点:1 深刻理解数据结构的概念,掌握数据结构的“三要素”:逻辑结构、物理(存储)结构及在这种 结构上所定义的操作“运算”。2 时间复杂度和空间复杂度的定义,常用计算语句频度来估算算法的时间复杂度。 以下六种计算算法时间的多项式是最常用的。其关系为:O
2、(1)O(logn)O(n)O(nlogn) O(n2)O(n 3)指数时间的关系为: O(2 n)O(n!)li nk=p q li nk=s p li nk=s p li nk=s在一个长度为link ; p link=s;s link=plink ; s link=p;s link=qn的顺序表的表尾插入一个新元素的渐进时间复杂度为(B )。A. 0( n)B. 0( 1)C. 0 ( n?)D. 0 (log 2n)11. 表长为n的顺序存储的线性表,当在任何位置上插入一个元素的概率相等时,插入一个元素所需移动元素的平均个数为(B )A. nB. n/2C. (n -1)/2D. (n
3、 +1)/212. 循环链表的主要优点是(D )A. 不再需要头指针了。B. 已知某个结点的位置后,能很容易找到它的直接前驱结点。C. 在进行删除操作后,能保证链表不断开。D. 从表中任一结点出发都能遍历整个链表。(二)应用题1、按增长率由小至大排列以下7个函数。nlog22(Z)n、( 3 八 2100、log32n、log2(log2)2n答:(外2100、叱2nlog 2、(log2)2(3)n2、数据的存储结构由哪四种基本的存储方法实现,并做以简要说明? 答:四种表示方法(1) 顺序存储方式。数据元素顺序存放, 每个存储结点只含一个元素。存储位置反映数据元素间的 逻辑关系。存储密度大,
4、但有些操作(如插入、删除)效率较差。(2) 链式存储方式。每个存储结点除包含数据元素信息外还包含一组(至少一个)指针。指针反映数据元素间的逻辑关系。这种方式不要求存储空间连续,便于动态操作(如插入、删除等),但存储空间开销大(用于指针),另外不能折半查找等。(3) 索引存储方式。除数据元素存储在一地址连续的内存空间外,尚需建立一个索引表, 索引表中索引指示存储结点的存储位置(下标)或存储区间端点(下标),兼有静态和动态特性。(4) 散列存储方式。通过散列函数和解决冲突的方法,将关键字散列在连续的有限的地址空间内, 并将散列函数的值解释成关键字所在元素的存储地址,这种存储方式称为散列存储。其特点
5、是存取速 度快,只能按关键字随机存取,不能顺序存取,也不能折半存取。3.线性表有两种存储结构:一是顺序表,二是链表。试问:(1)如果有n个线性表同时并存,并且在处理过程中各表的长度会动态变化,线性表的总数也 会自动地改变。在此情况下,应选用哪种存储结构?为什么?(2)若线性表的总数基本稳定,且很少进行插入和删除,但要求以最快的速度存取线性表中的 元素,那么应采用哪种存储结构?为什么?答:(1)选链式存储结构。它可动态申请内存空间,不受表长度(即表中元素个数)的影响,插入、 删除时间复杂度为 O( 1)。( 2)选顺序存储结构。顺序表可以随机存取,时间复杂度为O( 1)。(三) 算法设计题1设计
6、算法,求带表头的单循环链表的表长。解: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指向最后结点时算法结束。算法如下: 解:void pur_LinkList(LinkList H) LNode *p,*q,*r; p=H-next; /*p指向第一个结点 */if(p=NULL) return;
7、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 q=q-next; /*while(q-next)*/p=p-next; /*p指向下一个,继续 */ /*while(p-next)*/该算法的时间性能为 O(n2) 。3. 已知指针 la 和 lb 分别指向两个无头结点的单链表中的首结点。请编写函数完成从表la 中删除自第 i 个元素开始的共 len
8、 个元素并将它们插入到表 lb 中第 j 个元素之前,若 lb 中只有 j-1 个元素, 则插在表尾。函数原型如下:int DeleteAndInsertSub(LinkList &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(i0|j0|len0)return -1;p=la;k=1;prev=NULL;while(p&knext; k+;if(!p)return -1;q=p;k=1;while(q&knext; k+;if(!q) return -1;if(!prev) la=q-n