数据结构,清华大学出版社,严蔚敏吴伟民编著

1、v1.0可编辑可修改第一章绪论1、数据结构是计算机中 存储、组织数据的方式。精心选择的数据结构可以带来最优效率的算法。2、程序设计=算法+数据结构3、解决问题方法的效率：跟数据的组织方式有关跟空间的利用效率有关跟算法的巧妙程度有关4、数据:所有能输入到计算机中，且被计算机处理的符号的集合，是计算机操作对象的总称；是计算机处理的信息的某种特定的符号表示形式。5、数据元素：数据中的一个“个体”，数据结构中讨论的基本单位。相当于“记录”，在计算机程序中通常作为一个整体考 虑和处理。6、数据项：相当于记录的“域”，是数据的不可分割的最小单位,如学号。数据元素是数据项的集合。7、数据对象：性质相同的数据

2、元素的集合.例如：所有运动员的记录集合8数据结构：是相互间存在某种关系的数据元素集合。9、数据结构是带结构的数据元素的集合。10、不同的关系构成不同的结构。11、次序关系:vai,ai+1>|i=1,2,3,4,5,612、对每种数据结构，主要讨论如下两方面的问题：1）数据的逻辑结构，数据结构的基本操作；2）数据的存储结构，数据结构基本操作的实现；13、数据的逻辑结构：数据之间的结构关系，是具体关系的抽象。数据结构的基本操作：指对数据结构的加工处理。14、数据的存储结构（物理结构）：数据结构在计算机内存中的表示。数据结构基本操作的实现：基本操作在计算机上的实现（方法）。15、数据结构的有

3、关概念线性表f 线性结构栈.仁数锯的逻辑结构=I数毎结构的三个方廁B.非缓性結构I树形的图形结构j 2,甄据的存储第枸.A 噸序存储B链式存储< 3、数据的运算：檢索.U序、插入.除、修改等16、数据元素的4类的基本结构： 集合； 线性结构：结构中数据元素之间存在一对一的关系； 树形结构：结构中数据元素之间存在一对多的关系；图状结构或网状结构：结构中数据元素之间存在多对多 的关系。17、C语言的优点：C语言可以直接操作内存。18、每个节点都由两部分组成：数据域和指针域。19、链接存储结构特点：比顺序存储结构的存储密度小（每个节点都由数据域和指针域组成）。逻辑上相邻的节点物理上不必相邻。插

4、入、删除灵活（不必移动节点，只要改变节点中的指针）。20、数据类型 是一个值的集合和定义在此集合上的一组操作的 总称。21、ADT有两个重要特征：数据抽象和数据封装。22、 抽象数据类型（Abstract Data Type 简称ADT）:是指一个 数学模型以及定义在此数学模型上的一组操作。23、 抽象数据类型有：数据对象数据对象的定义、数据关 系数据关系的定义、基本操作基本操作的定义。24、数据类型的定义和含义。定义：数据类型是一个值的集合和定义在这个值集上的一组 操作的总称。含义：将数据按一定次序与形式存放的结构。24、算法空间复杂度S（n）算法的存储量包括： 输入数据所占的空间； 程序本

5、身所占的空间； 辅助变量所占的空间。25、 算法具有有穷性、确定性、可行性、输入和输出五大特性。26、 抽象数据类型具有数据抽象、数据封装的特点。27、数据的储存结构分为：顺序存储结构和链式存储结构。第二章线性表1、线性结构的特点：在数据元素中的非空有限集中（1）存在唯一的一个被称作“第一”的数据元素；（2）存在唯一的一个被称作“最后一个”的数据元素；（3）除第一个外，集合中的每一个数据元素均只有一个前驱；（4）除最后一个外，集合中的每一个数据元素均只有一个后继。2、线性表（Linear List）: 一个线性表是n个数据元素的有限序列3、线性表的顺序存储实现：typedef struct E

6、leme ntType DataMAXSIZE;int Last; List;List L, *PtrL;4、初始化(建立空的顺序表)List *MakeEmpty() List *PtrL;PtrL = (List *)malloc( sizeof(List);PtrL->Last = -1;return PtrL;5、查找int Find( ElementType X, List *PtrL ) int i = 0;while( i <= PtrL->Last && PtrL->Datai!= X )i+;if (i > PtrL->La

7、st) return -1; /* 如果没找到，返回-1 */else return i; /*找到后返回的是存储位置*/6、插入算法void In sert( Eleme ntType X, i nt i, List *PtrL ) int j；if ( PtrL->Last = MAXSIZE-1 ) /*能插入*/printf("表满");return;if ( i < 1 | i > PtrL->Last+2) /*合法性*/printf("位置不合法");retur n;for ( j = PtrL->Last;

8、j >= i-1; j-)PtrL->Dataj+1 = PtrL->Dataj; /*表空间已满，不检查插入位置的将aiPtrL->Datai-1 = X; /*PtrL->Last+;/*Last新元素插入*/仍指向最后元素*/an倒序向后移动*/return;7、删除算法void Delete( int i, List *PtrL )7v1.0可编辑可修改 int j；if( i < 1 | i > PtrL->Last+1 ) /*检查空表及删除位置的合法性*/printf ( “不存在第并元素” ,i );return ;for ( j

9、 = i; j <= PtrL->Last; j+ )PtrL->Dataj-1 = PtrL->Dataj; /*将 ai+1 -an顺序向前移动*/PtrL->Last-; /*Last仍指向最后元素*/return;8求表长int Length ( List *PtrL ) List *p = PtrL; /* p指向表的第一个结点*/int j = 0;while ( p ) p = p->Next;j+;/*当前p指向的是第j个结点*/9、查找(1) 按序号查找：FindKth;List *Fi ndKth( int K, List *PtrL )

10、 List *p = PtrL;int i = 1;while (p 匸NULL && i < K ) p = p->Next;i+;if ( i = K ) retur n p;/*找到第K个，返回指针*/else return NULL;/* 否则返回空*/(2) 按值查找:FindList *Find( ElementType X, List *PtrL )List *p = PtrL;while ( p!=NULL && p->Data != X )p = p->Next;return p;10v1.0可编辑可修改10、插入(在链

11、表的第i-1(1 < i w n+1)个结点后插入一个值为X的 新结点)List *Insert( ElementType X, int i, List *PtrL ) List *p, *s;if ( i = 1 ) /*新结点插入在表头*/s = (List *)malloc(sizeof(List); /*申请、填装结点*/s->Data = X;s->Next = PtrL;return s; /*返回新表头指针*/p = FindKth( i-1, PtrL ); /* 查找第 i-1 个结点 */if ( p = NULL) /*第 i-1 个不存在，不能插入*/

12、printf("参数 i 错")；return NULL;else s= (List *)malloc(sizeof(List); /* 申请、填装结点*/s->Data = X;11s->Next = p->Next; /*新结点插入在第v1.0可编辑可修改若要删除的是指向第1个结从链表中删除*/释放被删除结查找第i-1个结i-1个结点的后面*/p->Next = s;retur n PtrL;11、删除（删除链表的第i （1 wi wn）个位置上的结点）List *Delete( int i, List *PtrL ) List *p, *s;i

13、f ( i = 1 ) /*表的第一个结点*/s = PtrL;/*s占*/八、IPtrL = PtrL->Next; /* free(s);/*占*/八、Ireturn PtrL;p = FindKth( i-1, PtrL );/*占*/八、Iif ( p = NULL ) printf（ “第%d个结点不存在”，i -1）;return NULL;13v1.0可编辑可修改17 else if ( p->Next = NULL )printf( “第d个结点不存在”，i);return NULL; else 指向第i个结从链表中删除*/释放被删s = p->Next;/*

14、s点*/八、Ip->Next = s->Next; /* free(s);/*除结点*/return PtrL;12、链表不具备的特点是_J可随机访问任一节点插入删除不须要移动元素 不必事先估计存储空间所需空间与其长度成正比13、带头结点的单链表head为空的判定条件是 /。 head=NULL head-> next=NULL head-> next=head head!=NULL14、如果最常用的操作是取第i个结点及其前驱，则采用 4 存 储方式最节省时间。单链表双链表单循环链表顺序表第三章 Chapter 3 栈(stacks)和队列(queues)1、栈是限定仅

15、能在表尾一端进行 插入、删除操作的线性表。2、栈的特点是“后进栈的元素先出栈”(last in, first out )， 故栈又称为后进先出表(LIFO)。3、一个栈是一些元素的线形列表，其中元素的插入和删除均在表 的同一端进行。插入和删除发生的一端称为栈顶(the top of the stack )。4、第一个进栈的元素在栈底，5、最后一个进栈的元素在栈顶，第一个出栈的元素为栈顶元素，最后一个出栈的元素为栈底元素。6、连续栈(Contiguous Stack) 的类型定义#define MaxStack 50Typedef structdatatype stackMaxStack;int

16、 top;Seqstack;Seqstack *s;7、判断栈是否已满viod Push(Seqstack *s, datatype x )if (s->top>=MaxStack-1) printf(“overflow ” );else s-> top+;s->stacks->top=x;8判断栈是否为空datatype pop(Seqstack *s ) if (s->top<0)printf(“underflow ” ); return(NULL);return(s->stacks->top);s->top-;9、返回栈顶元素的

17、值，栈不发生变化。datatype top(Seqstack *s ) if (s->top<0)printf(“underflow ” ); return(NULL);return(s->stacks->top);10、链栈(Linked Stack)的类型定义栈的链式存储结构称为链栈，它是运算受限的单链表，插入和删除 操作仅限制在表头位置上进行。由于只能在链表头部进行操作，故链 表没有必要像单链表那样附加头结点。栈顶指针就是链表的头指针。链栈的类型说明如下：typedef struct stack node datatype datastruct stack nod

18、e *n extstack node11、链式栈的特点：链式栈无栈满问题；空间可扩充；插入与删除仅在栈顶处执行；链式栈的栈顶在链头；适合于多栈操作。11、 栈是限定仅能在表的一端进行插入、删除操作的线性表。12、栈的元素具有后进先出的特点。13、栈顶元素的位置由栈顶指针的指示，进栈、出栈操作要修改栈 顶指针。14、抽象数据类型队列的定义：队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。15、队列亦称作先进先出(First In First Out)的线性表，简称FIFO表。16

19、、双端队列：就是限定插入和删除操作在表的两端进行的线性表。17、链队列结点定义：typedef struct Qnodev1.0可编辑可修改 QEIemType data; struct QNode *n ext; QNode,*QueuPtr;18、队列的顺序存储结构称为 顺序队列，在队列的顺序存储结构中， 除了用一组地址连续的储存单元依次存放从队头到队尾的元素 之外，尚需要附设两个指针fro nt和rear分别指示队列头元素 和队列尾元素的位置。19、在非空队列中，头指针始终指向队头元素，而尾指针始终指向 队尾元素的下一位置。20、 栈的特点是先进后出，队列的特点是先进后出。21、 栈和队

20、列的共同特点是只允许在端点处插入和删除元素。22、 一个栈的进栈序列是a, b, c, d，e,则栈的不可能的输出序列（A） edcba（ B）decba （ C） dceab （ D） abcde23、若已知一个栈的进栈序列是 p1, p2, p3,，pn。其输出序列为1, 2, 3,，n，若p3=1,则p1为 C。（A）可能是2 （B）定是2 （C）不可能是2 （ D）不可能是324、 设有一个空栈，栈顶指针为 1000H （十六进制，下同），现有输入序列为 1、2、3、4、5,经过 PUSH PUSH POP PUSH POP PUSHPUSH后，输出序列是3,栈顶指针是 5、4、3、2

21、、12、12、3 3、41005H24、一个队列的入队序列是若B。1002H1004H1003H1 , 2, 3, 4,则队列的输出序列是(A) 4, 3, 2, 1(B) 1, 2, 3, 4(C) 1, 4, 3, 2(D) 3, 2, 4, 125、若用一个大小为6的一维数组来实现循环队列，且当前rear和 front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear禾口 front 的值分别是 _B。（A）1 和 5（B）2 和 4（C） 4 和 2（ D）5 和 126、有5个元素，其入栈次序为 A B、CD E,在各种可能的出栈 次序中，以元素C D最先出栈（即C

22、第一个且D第二个出栈）的次 序有哪几个C D B、A、E C 、D E、B、AC D B、E、A44第六章树和二叉树1、树型结构是一类重要的非线性结构。2、树的定义：树是n(n>=0)个结点的有限集T, T为空时称为空树， 否则它满足如下两个条件：(1) 有且仅有一个特定的称为根的结点；(2) 当n>1时，其余结点可分为m(m>0个互不相交的有限集T1,T2, T3Tm其中每个子集又是一棵树，并称其为根的子树。3、基本术语结点一一表示树中的元素，包括数据项及若干指向其子树的分支结点的度(degree)结点拥有的子树数叶子(leaf)度为0的结点孩子(child)结点子树的根称

23、为该结点的孩子双亲(pare nts)孩子结点的上层结点叫该结点的兄弟(sibli ng)同一双亲的孩子树的度一一一棵树中最大的结点度数结点的层次(level)从根结点算起，根为第一层，它的孩子为第二层深度(depth)树中结点的最大层次数森林(forest)m(m 0)棵互不相交的树的集合例题:结点A的度：3叶子:K. L. F, G,结点A的层次：1结点M的层次：AE树的深度：4树的度：3结点I的双亲=0 结点L的双亲匸E结点A是结点F, G的祖先结点A的孩子：B, CT D 结点B的孩子：E, F结点B. C, D为兄弟 结点K, L为兄弟4、二叉树是由n(n>=0)个结点的有限集

24、合构成，此集合或者为空集, 或者由一个根结点及两棵互不相交的左右子树组成， 并且左右子树都 是二叉树 二叉树可以是空集合，根可以有空的左子树或空的右子树。 性质1:在二叉树的第i层上至多有2i-1个结点(i>=1) 性质2：深度为k的二叉树至多有2k -1个结点(k>=1)性质3:对任何一棵二叉树T,如果其终端结点数为n0,度为2的 结点数为n2，则n0= n2+ 1。性质4：具有n个结点的完全二叉树的深度为Iog2n + 1。性质5:如果对一棵有n个结点的完全二叉树的结点按层序编号(从 第1层到第Iog2n +1层，每层从左到右)，则对任一结点i(1<=i<二n)，有

25、：(1) 如果i = 1,则结点i无双亲，是二叉树的根；如果i>1 , 则其双亲是结点i/2。(2) 如果2i>n，则结点i为叶子结点，无左孩子；否则，其 左孩子是结点2i。(3) 如果2i + 1>n,贝卩结点i无右孩子；否则，其右孩子是结 点 2i + 1。一棵深度为k且有2k-1个结点的二叉树称为满二叉树。如:(a)完全二叉树(b)非完全二叉树)非完全二叉树5、二叉树的存储结构顺序存储结构define MAX-TREE-SIZE 100Typedef TelemType SqBiTree MAX-TREE-SIZE;SqBitree bt;缺点是有可能对存储空间造成极大

26、的浪费。链式存储结构二叉链式存储结构typedef struct BiTNode TElemType data;struct BiTNode *lchild, *rchild;BiTNode,*BiTree;三叉链表typedef struct node datatype data;struct node *lchild, *rchild, *pare nt;JD;6、遍历二叉树二叉树是由三个基本单元组成：根结点、左子树和右子树。若限定先左后右，则只有前三种情况，分别称之为先（根）序遍历,中（根）序遍历和后（根）序遍历。（1）先序遍历算法若二叉树为空树，则空操作；否则，访问根结点；先序遍历左子

27、树;先序遍历右子树。void PreOrder (BiTree bt ) /* 先序遍历二叉树 bt*/if (bt=NULL) return; /*递归调用的结束条件*/Visite ( bt->data )/*(1)访问结点的数据域*/PreOrder (bt->lchild ); /*(2)先序递归遍历bt的左子树*/PreOrder( bt->rchild );/*(3)先序递归遍历 bt 的右子树 */例题:D Cvoid preorder(JD *bt) if(bt!=NULL) prin tf("%dt",bt->data);preor

28、der(bt->lchild); preorder(bt->rchild);(2) 中序遍历算法若二叉树为空树，则空操作；否则,先序遍历左子树;访问根结点;先序遍历右子树。void In Order ( BiTree bt )/*先序遍历二叉树bt*/if (bt=NULL) return;/*递归调用的结束条件*/In Order (bt->lchild)；/*(2)先序递归遍历bt的左子树*/Visite ( bt->data );/*(1)访问结点的数据域*/);/*(3)先序递归遍历bt的右子树*/In Order ( bt->rchildA CC(3)

29、后序遍历算法若二叉树为空树，则空操作；否则,先序遍历左子树;先序遍历右子树;访问根结点。void PostOrder (BiTree bt ) /* 后序遍历二叉树 bt*/if (bt=NULL) return;/*递归调用的结束条件*/PostOrder (bt->lchild);/*(1)后序递归遍历bt的左子树*/PostOrder ( bt->rchild);/*(2)后序递归遍历bt的右子树Visite ( bt->data );/*(3)访问结点的数据域*/例题：r戸、x©后序遍历序列：D BC A(4) 层次遍历所谓二叉树的层次遍历，是指从二叉树的第

30、一层(根结点)开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问层次遍历序列:1 2 3 4 5 67、例题：1、先序序列：A B C D E F G H K 中序序列：B D C A E H G K F 后序序列：D C B H K G F E K 层次序列：A B E C F D G H K2、其先若先序遍历此二叉树，按访问结点的先后次序将结点排列起来,序序列为：-+a*b-cd/ef按中序遍历，其中序序列为：a+b*c-d-e/f按后序遍历，其后序序列为：abcd-*+ef/ -8 (1)查询二叉树中某个结点Status Preorder (BiTree T, Elem

31、Type x, BiTree &p) 12、先序线索二叉树Ta0bIc1d2e2f3g5b5j5data parentob1c1J2Ae2r3A誓SAh54SAftsun JHI eiit tc94時点一抹线：抹掉原二叉树中双亲与右孩子之间的连线 调整：将结点按层次排列，形成树结构14、森林转换二叉树(1) 将各棵树分别转换成二叉树(2) 将每棵树的根结点用线相连(3) 以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构13、二叉树转换成森林及沿右分支搜索到的所有抹线：将二叉树中根结点与其右孩子连线, 右孩子间连线全部抹掉，使之变成孤立的二叉树还原：将孤立的二

32、叉树还原成14、树和森林的遍历树的遍历 两种次序遍历树的方法：一种是先根（次序）遍历树，即先访问树的根结点，然后依次先根遍历根的每棵子树；一种是后根（次序）遍历，即先依次后根遍历每棵子树，然后访问根结点先根序列：A B C D E森林的遍历先序遍历：A B C D E F G H I J后根序列，B D C E A中序遍历：B C D A F E H J I G15、赫夫曼树及其应用50 110291 0711108111114110230 030 11111010例题： w=5, 29, 7, 8, 14, 23, 3, 11习题：1、 由于二叉树中每个结点的度最大为2,所以二叉树是一种特殊

33、的 树，这种说法_B_。（A）正确（B）错误2、某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是D。（A）空或只有一个结点（B）完全二叉树（C）二叉排序树（D）高度等于其节点数3、深度为5的二叉树至多有（二个结点。（A）16（ B）32（C）31（D）104、根据使用频率为5个字符设计的赫夫曼编码不可能是 C .(A) 111, 110, 10, 01, 00(B) 000, 001, 010, 011, 1(C) 100, 11, 10, 1, 0(D) 001, 000, 01, 11, 105、树和二叉树的主要差别是(1) 树的结点个数至少为 1,而二叉 树的结点个数可以为

34、 0 (2)树中结点的最大度数没有限制，而二叉 树结点的最大度数为 2 (3)树的结点无左、右之分，而二叉树的结 点右左、右之分。6、 深度为k的完全二叉树至少有 个结点，至多有 个结点，若按自上而下，从左到右次序给结点编号(从 1开始)，则编 号最小的叶子结点的编号 。7、 一棵二叉树的第i(i1)层最多有个结点；一棵有n(n>0)个结点的满二叉树共有 个叶子结点和_个非叶子结点。8已知二叉树的先序、中序和后序序列分别如下，其中有一些看不 清的字母用*表示，请构造出一棵符合条件的二叉树并画出该二叉树。先序序列是：*BC*FG中序序列是：CB*EAG*后序序列是：*EDB*FA9、将右图

35、所示的树转化为一叉树，并与出先序遍历，中序遍历和后序遍历的结果解:中序：EFGBCHIDA后序：GFEIHDCBA先序：ABEFGCDHIv1.0可编辑可修改10、设给定权集 w=2, 3, 4, 7, 8, 9，试构造关于 w的一棵赫夫曼树，并求其加权路径长度WPLWPL=(9+7+8)*2+4*3+(2+3)*4=80第十章内部排序1、内排序大致可分为五类：插入排序、交换排序、选择排序、归并排序和分配排序。插入排序（直插排序，二分排序，希尔排序）交换排序（冒泡排序.快速排序）选择排序（直选排序*树型排序*堆排序） 归并排序（二路归并排序鶯多路归井排序）'分配排序（多关键字排序.基数

36、排序）皿、2、直接插入排序直接插入的算法实现void sort(NODE array,i nt n)ey)初始状rsayj-1=girray67； j-3562 ：9 22 4ey<a57rayj-1.key)34I |I012345初第一趟结果,step=232967 25 35 1479120 729662v1.0可编辑可修改63ey> j-;初始状态j) ar(ayi=arrayj; i+;2514209)i+; 9(c)输(g)输251420)42 0512,26,37,412,26,37,例如次已7知，较得到第八小值7667010第六次【第七次（e）成堆high小值49第

37、 一Whil序 (ivj & 專arrayi.key<二10-4 low1 28 11926in8897476初始状二趟6第五況5,214id-1 94) 768405 11，92），现要查找关键字为$c）将以38为根快速排序的一次划分图?7-5 13直接选择排序I的过6； 640f14小值 66985131921375664758088911lollIII1234567high id S 91011513192137566475808891hi吵 I”6710 11123图7-8 5建立堆的过程示意图91011513192137566475808892T16high891234

38、567 S 91011513192137566475808892丄midhigh1234567891011513192137566475808892申山lowmidh讪2345678910II513192137566475808892low mid high折半查找的效率比顺序查找高，但折半查找只适用于有序表，且限于 顺序存储结构。3、查找方法的比较顺序查找二分法查找分块查找ASL最大最小两者之间表结构有序表无序表有序表分块有序表存储结构顺序存储结构线性链表顺序存储结构顺序存储结构线性链表4、二叉排序树的插入例45 ，24，53，45，12，24，908060270删除鮒>删脸60 &g

39、t;5、含有n个结点的二叉排序树的平均查找长度和树的形态有关第7章图1、图的定义和术语若图中的边是顶点的有序对，则称此图为有向图。若图中的边是顶点的无序对，则称此图为无向图。有向边又称为弧，通常用尖括号表示一条有向边， vv, w表示从 顶点v到w顶点的一条弧，v称为边的始点(或弧尾)，w称为边 的终点(或弧头)。有向完全图：具有n(n-1)条弧的有向图称为有向完全图。无向完全图：n个顶点的无向图最大边数是n(n-1)/2，具有n( n-1)/2条边的无向图称为无向完全图。度的例题：顶点2入度三1出g, 3顶点4入1 出度：0顶点5的度：3顶点2的度二4子图的例题：0 (T5：旬子圏 于图oT

40、0(b) til/1总的例题：路径J, 2, 3, 5, 6, 3 X 路径长度二5简单路径2, 3, 5回路：1, 2. 3, 5, 6, 3, 1简单回路匸3, 5, 6, 3路径:1, 2f 5, 7, 6, 5, 2, 3径长度豈7简单路1. 2S 5, 7, 6回路上 1, 2, 5, 7, 6, 5, 2, 1简单回路二1, 2, 3, 1若G中任意两个顶点都是连通的，则称 G为连通图非连通图的极大连通子图叫做连通分量强连通图与强连通分量在有向图中，若对于每一对顶点vi和vj，都存在一条从vi到vj 和从vj到vi的路径，则称此图是强连通图。非强连通图的极大强连 通子图叫做强连通分

41、量。若给图中每一条边附加一个实数作为权，则该图称为带权图或网2、图的存储结构 无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是不对称的数组表示法（邻接矩阵）网的邻接矩阵可为:®011000000001©1000®)5 ("01010101010101110100_01100©> 0057003 5g487OC0021 QC42006_ 3816CC _1）有向图的十字链表表示法23D： J1F200L30A0102A1J*131A32AA2）无向图的邻接多重表存储表示401234、图的遍历通常有两条遍历图的路径:深度优先搜索遍历;4、广度

42、优先搜索遍历广度遍历Vi V戶 V3 => V4 => V5 => V6 n V7 n V8广度遍历v戸V v4 v6> V v8 v5如何拓扑排序在有向图中选一个没有前驱的顶点且输出之。C1拓扑厅列；C1-C2-C3-C4- C5(5>拓邪丹列：C1-C2-C3-C4-C5-C7-C9列：C1-C2-C3-C4-C5-C7-C9C1O-C11-C1CCll-C6(11>拓扑序和：C1-C2-C3-C4-CS-C7-C9-C1C Cll C6 C12 C8揺扌卜序列：C1-C2-Z：3-CC5 -C7-C9 -CJ0-C11-C6-C12(12第二章 hom

43、ework1、填空题：(1) 在顺序表中插入或删除一个元素，平均要移动_表中一半的 元素，具体移动的元素个数与_插入或删除的位置有关。(2 )线性表有 顺序存储和链式存储 两种存储结构。(3 )顺序表中，逻辑上相邻的元素，其物理位置_必定_相邻。在单链表中，逻辑上相邻的元素，其物理位置 _不一定相邻。2、选择题：(1) 在线性表中最常用的操作是存取第 i个元素及其前驱的值，采用_存储方式最省 时间A. 顺序表B.带头结点的单向链表C.带头指针的单向循环链表D.带头指针的双向循环链表E.带尾指针的单向循环链表(2) 已知L是无表头结点的单链表，且P结点即不是首元素结点，也不是尾元素结点。按 要求

44、在下列语句中选择合适的语句序列。A. 在P结点后插入S结点的语句序列是： D、AB. 在P结点前插入S结点的语句序列是：GKHDAC. 在表首插入S结点的语句序列是：E、LD. 在表尾插入 S结点的语句序列是：KIAFA. P->n ext=S; B. P->n ext=P->n ext->n ext; C. P->n ext=s->n ext;D. S-> next=P-> next; E. S-> next=L;F. S-> next=NULL;G. Q=P;H. while(P-> next!=Q)P=P-> nex

45、t;I. while(P-> next!=NULL)P=P-> next; J. P=Q;=L;L. L=S; M. L=P;(3) 某线性表中最常用的操作是存取序号为 i的元素和在最后进行插入和删除运算，则采用匚存储方式时间性能最好。A.双向链表 B.双向循环链表C.单向循环链表D.顺序表v1.0可编辑可修改(4) 下列选项中，_D项是链表不具有的特点。A插入和删除运算不需要移动元素B. 所需要的存储空间与线性表的长度成正比C. 不必事先估计存储空间的大小D. 可以随机访问表中的任意元素3、描述以下三个概念的区别：头指针，头结点，首元素结点(略)。4、 已知顺序表L递增有序，编写

46、一个算法，将X插入到线性表的适当位置上，以保持线性 表的有序性。Void in serX(Seqlist *L,Elemtype x)int i;i=L->le ngth-1;while(i>=0 && x<L->elemi)L_>elemi+1=L_>elemi;i-;L->elemi=x;L->le ngth+;5、 编写一个算法，从顺序表中删除自第i个元素开始的k个元素。Void deletexfromatob(Seqlist *L,int i,int k) int j;for(j=i+k;j<L->le ngt

47、h;j+;i+)L->elemi=L->elemj;L->le ngth=L->le ngth-k;6、已知线性表中的元素(整数)以值递增有序排列，并以单链表作存储结构。试编写一个高效算法，删除表中所有大于minK且小于maxK的元素(若表中存在这样的元素)，分析你的算法的时间复杂度(注意：minK和maxK是给定的两个参变量，它们的值为任意的整数)Void DeleteX(linklist *head,int mink,int maxk)Li nklist *p,*q,*s;q=head;p=head->n ext;while(p!=NULL)While(p!=

48、NULL && p->data < mink)知两个有序表 La和Lb,把两个有序表合并成仍然有序的线性表Lc.代码：#i nclude""#i nclude""#defi ne Maxsize 50if (i>la->le ngth+1) pri ntf("Error!n");int j;i=i-1;for(j=la->le ngth_1;j>=i;j_)la->computerj+1=la->computerj;la->computeri=x;la->le

49、 ngth=la->le ngth+1;void Delete(sqlist *la,int i)int i,flag=O;for(i=0;i<la->le ngth;i+)if (la->computeri=e) flag=1;return i+1;if (flag=0)return 0;void Union (sqlist *la,sqlist *lb)int i,j=0,t;for(i=0;i<la->le ngth;i+)lc->computeri=la->computeri;lc->le ngth=la->le ngth;for(i=la->le ngth;i<(la->le ngth+lb->le ngth);i+)lc->computeri=lb->computerj;lc->le ngth=lc->le ngth+1;j+;for(i=0;i<lc->le ngth;i+)for(