《数据结构总复习》由会员分享，可在线阅读，更多相关《数据结构总复习（69页珍藏版）》请在金锄头文库上搜索。
1、数据结构总复习Date11 绪 论 1.1 知识点：基本概念：数据、数据元素、数据对象、数据结构 、数据类型、抽象数据类型数据的三个层次：数据、数据元素、数据项数据结构三要素：逻辑结构:集合结构、线性结构、树、图物理结构：操作（运算）算法的定义和五个特征时间复杂度:最坏时间复杂度，常用计算语句的频度 来估算算法的时间复杂度。Date2数据结构的研究范围P 逻辑结构 P 存储结构 P 运算的集合 Date31.2 练习题：2.执行下面程序段时，语句S的执行次数为（ ） for（i=0；idatap-nextp对于非空表（带头结点），可以通过头指针H访问表中结点， 从而找到要访问的所有结点的数据信
2、息：p=H-next （p指向表中首结点）通过 p-data访问首元素的数据l单链表Date6头插法建立一个“空表”输入数据元素an， 建立结点并插入输入数据元素an-1， 建立结点并插入 an-1依次类推,直至输入完a1结束。HHanL HanSS建立单链表：Date7LinkList Creat_ LinkList ( ) LinkList H=(LinkList)malloc(sizeof(LNode);H-next=NULL; LNode *s; int x; scanf(“%d”,while(x!=-1) s=(LinkList)malloc(sizeof(LNode); s-dat
3、a=x; s-next=H-next; H-next=s; scanf(“%d”,return H; anHxSDate8尾插法建立一个“空表” 输入数据元素a1， 建立结点并插入；输入数据元素a2， 建立结点并插入a2依次类推,直至输 入完an结束Ha1SSrrra1H rHr增设一个指针r始终指向尾结点Date9LinkList Creat_ LinkList2( ) LinkList H=(LinkList)malloc(sizeof(LNode);H-next=NULL; LNode *s, *r=H; int x; scanf(“%d”, while(x!=-1) s=(LinkLi
4、st)malloc(sizeof(LNode); s-data=x; s-next=r-next; r-next=s; r=s ; scanf(“%d”, return H; a1Hrxs rDate10l循环链表首尾相接的链表称为循环链表。将最后一个结点的指针又指回头结点即得循环链表。a1 a2 . an 循环单链表与单链表的差别在于：判别链表中最 后一个结点的条件不再是“后继是否为空”，而是 “后继是否为头结点”。rear尾指针rear-next多用尾指针指示循环单链表p-next!=HDate11l双向链表typedef struct dlnode ElemType data；struc
5、t dlnode *prior，*next； DLNode,* DLinkList；链表中每结点不仅有指向后继的指针，还有指 向前趋的指针。prior data next双向链表的结构定义：Date12双向链表插入eaiai-1ps-prior= p-prior;sp-prior-next= s;s-next= p;p-prior= s;前插 ：Date13ai-1aies-next = p-next; p-next = s; s-next-prior = s; s-prior = p;sai-1aip后插 ：Date14双向链表删除ai-1aiai+1p-prior-next = p-nex
6、t;pai-1free(p);p-next-prior = p-prior;Date15l双向循环链表非空表a1 a2 . an H空表Hpp-prior-next=p; p=p-next-prior;Date16v带头结点的单链表与不带头结点的单链表的区别：在不带头结点的单链表中，除了开始结点外，其它每个结点的 存储地址都存放在其前驱结点的next域中，而开始结点是由头指针 指示的。这个特例需要在单链表实现时特殊处理，这增加了程序 的复杂性。因此通常在单链表的开始结点之前附设一个头结点。 好处： （1）带头结点的链表，在表的任何结点之前插入或删除表中任何 结点，所要做的都是修改前一个结点的指
7、针域(若链表无头结点， 首元素结点没有前驱，在其前插入结点和删除该结点会比较麻烦) （2）对带头结点的链表，表头指针是指向头结点的非空指针，因 此空表和非空表的处理时一样的。2.2.难点解析Date17v区别头指针、头结点、首元结点头指针：链表的指针指向链表第一个结点的指针头结点：为了操作的方便，在单链表的第 一 个元素结点之前附设一个结点。 首元结点：第一元素结点头结点后面的第一个结点在第一元素结点前插入和删除第一元素 结点的操作与对其他结点的操作一致。Date18v何时选用顺序表、链表为宜? 若操作主要是查找，很少做插入和删除，顺序表为 宜。 事先知道存取元素数目的大致范围可优先考虑这种
8、结构（每个结点无需存储指针变量，结点存储密度 较高，整个表的存储利用率也较高） 频繁插入和删除，宜采用链表做存储结构（它不需 移动大量的其他结点，只要修改有限的指针变量即 可 事先不能确定存储结点的最大数量也可选择这种结 构（具有动态分配回收的机制，不会造成大量的空 间闲置） 单循环链表中，从任一结点出发都可访问到表中所 有结点。 若表的插入和删除主要发生在首尾两端，宜采用带 尾指针的单循环链表。（开始结点和终端结点查找 时间都是O(1)。）Date192.3 习题解析：1.顺序表中第一个元素的存储地址是100，每个元素的 长度为2，则第5个元素的存储地址是（ ）。 第5个元素的存储地址=第1
9、个元素的存储地址(51)2=108 2.线性表的顺序存储结构是一种（ ）的存储结构，线性 表的链接存储结构是一种（ ）的存储结构。 A 随机存取 B 顺序存取 C 索引存取 D 散列存取A,B3.单循环链表的主要优点是（ ）。 A 不再需要头指针了 B 从表中任一结点出发都能扫描到整个链表； C 已知某个结点的位置后，能够容易找到它的直接前趋； D 在进行插入、删除操作时，能更好地保证链表不断开。BDate204.若某线性表中最常用的操作是取第i 个元素和找第i个 元素的前趋，则采用（ ）存储方法最节省时间。 A 顺序表 B 单链表 C 双链表 D 单循环链表线性表中最常用的操作是取第i 个元
10、素，应选择随机存取结构即顺 序表，同时在顺序表中查找第i个元素的前趋也很方便。单链表和 单循环链表不能实现随机存取，查找第i个元素的前趋也不方便， 双链表虽然能快速查找第i个元素的前趋，但不能实现随机存取。 5.若链表中最常用的操作是在最后一个结点之后插入一个 结点和删除第一个结点，则采用（ ）存储方法最省时间 。 A 单链表 B 带头指针的单循环链表C 双链表 D 带尾指针的单循环链表 在链表中的最后一个结点之后插入一个结点需要知道终端结点的地 址，所以，A,B,C都不合适，考虑在带尾指针的单循环链表中删除 第一个结点，其时间性能是O(1)，所以，答案是D 。Date216.若链表中最常用的
11、操作是在最后一个结点之后插入一 个结点和删除最后一个结点，则采用（ ）存储方法 最节省运算时间。A 单链表 B 循环双链表 C单循环链表 D 带尾指针的单循环链表 在链表中的最后一个结点之后插入一个结点需要知道终端结点的地 址，所以，A,C不合适，删除最后一个结点需要知道终端结点的前 驱结点的地址，D不合适，B满足条件。 7.可由一个尾指针唯一确定的链表有循环链表，循环双 链表，双链表 .Date223 栈和队列 3.1 知识点： l 栈：栈是限定仅在表尾进行插入和删除操作的线性表 ，栈中元素除了具有线性关系外，还具有后进先出的 特性。 出栈可随时进行,只要某个元素位于栈顶就可以出 栈。例有三
12、个元素a、b、c，按a、b、c的次序进栈，且每个元素只 允许进一次栈，可能的出栈序列有abc、acb、bac、bca、cba 五种顺序栈：链栈：只能在表头进行插入和删除操作的单链表.上溢-栈满时进栈,上溢是一种出错状态，应设法避免。下溢栈空时退栈,下溢是正常现象，常用作程序控制转移的条 件。主要操作：初始化、入栈、出栈、判栈空/满Date23l队列：先进先出队列的删除在一端（头），插入在另一端（尾 ）。顺序队列：链队列：两个指针l循环队列用顺序存储结构表示队列，由于队列的性质(队尾 插入,队头删除),容易造成“假溢出”现象，即队尾 已到达一维数组的高下标，不能再插入，然而队中元 素个数小于队列
13、的长度。循环队列是解决“假溢出” 的一种方法。通常把一维数组看成首尾相接。在循环 队列下，通常采用“牺牲一个存储单元”或“作标记 ”的方法解决“队满”和“队空”的判定问题。 循环队列中元素个数的计算式：（rear-front+M）%M队满:(rear+1)%M=front 队空:front=rearDate243.2 习题解析： 1.一个栈的入栈序列是1,2,3,4,5,则不可能的输出序列是( ). A 54321 B 45321 C 43512 D 12345 技巧：在输出序列中任意元素后面不能出现比该元素小并且是升序 （指的是元素的序号）的两个元素。 2.给出栈的两种存储结构形式名称，在这
14、两种栈的存储结 构中如何判别栈空与栈满？ (1)顺序栈 （top用来存放栈顶元素的下标） 判断栈S空：如果S-top=-1表示栈空。 判断栈S满：如果S-top=Stack_Size-1表示栈满。 (2) 链栈(top为栈顶指针,指向当前栈顶元素前面的头结点) 判断栈空：如果top-next=NULL表示栈空。 判断栈满：当系统没有可用空间时，申请不到空间存放要 进栈的元素，此时栈满。 Date253.经过以下栈运算后，StackEmpty( s )的值是（ ）InitStack(s);Push(s,a);Push(s,b);Pop(s,x);Pop(s,y);A.a B.b C.1 D.0
15、4.4个元素a、b、c和d依次入栈，入栈过程中允许元素出 栈，假设某一时刻栈的状态是c（栈顶）、b、a（栈 底），则不可能的出栈顺序是（ ）。A. d,c,b,a B. c,b,d,a C. c,a,d,b D. c,d,b,a 5.若用一个大小为6的数组来实现循环队列，且当前rear 和front的值分别为0和3，当从队列中删除一个元素， 再加入两个元素后，rear和front的值分别为( )。A. 1和5 B. 2和4 C. 4和2 D. 5和1CCCBDate264 串4.1 知识点：l串是数据元素为字符的线性表。l子串、主串、空串空串是任意串的子串任意串是其自身的子串l串的存储：顺序：串的字符顺序的存入连续的存储单元中。链式:单链表形式存储。空串：零个字符的串，长度为零空白串：一个或多个空格字符组成的串,长度是空格数Date274.2 习题解析：1.设s=I AM A STUDENT，t=GOOD， q=WORKER。给出下列操作的结果： StrLength(s)=14; SubString(sub,s,7,1)
