当前位置：文档库 › 作业4-数据结构-图

作业4-数据结构-图

作业四

四⑴、有一带权无向图G=（V，E），其中

V={v1，v2，v3，v4，v5，v6，v7，v8}，

E={（v1，v2，12），（v1，v5，2），（v2，v8，5），（v2，v6，3），（v3，v4，8）（v3，v5，2），（v3，v6，4），（v4，v5，10），（v4，v7，8），（v6，v7，7）}

a) 画出该无向图的邻接表（要求每个顶点的单链表按照顶点序号升序排列）；

b) 画出该无向图的邻接矩阵；

c) 画出该图；

d) 根据你给的邻接表，分别写出从v1出发进行深度优先搜索遍历和广度优先搜索遍历

的顶点序列。

四⑵、有向网G如下图所示，

a) 请求从顶点A出发到各顶点的最短路径及路径值（写出详细计算过程）；

b) 请求出图G（不计弧上的权值）的拓扑排序（写出详细过程）。

数据结构作业系统第七章答案

7.22③试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径(i≠j)。注意：算法中涉及的图的基本操作必须在此存储结构上实现。实现下列函数： Status DfsReachable(ALGraph g, int i, int j); /* Judge if it exists a path from vertex 'i' to */ /* vertex 'j' in digraph 'g'. */ /* Array 'visited[]' has been initialed to 'false'.*/ 图的邻接表以及相关类型和辅助变量定义如下：Status visited[MAX_VERTEX_NUM]; typedef char VertexType; typedef struct ArcNode { int adjvex; struct ArcNode *nextarc; } ArcNode; typedef struct VNode { V ertexType data; ArcNode *firstarc; } VNode, AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices; int vexnum, arcnum; } ALGraph; Status DfsReachable(ALGraph g, int i, int j) /* Judge if it exists a path from vertex 'i' to */ /* vertex 'j' in digraph 'g'. */ /* Array 'visited[]' has been initialed to 'false'.*/ { int k; ArcNode *p; visited[i]=1; for(p=g.vertices[i].firstarc;p;p=p->nextarc) { if(p) { k=p->adjvex; if(k==j)return 1; if(visited[k]!=1)

数据结构--重修作业题

第一章绪论一、选择题 3.在数据结构中，从逻辑上可以把数据结构分成（）（A）动态结构和静态结构（B）紧凑结构和非紧凑结构（C）线性结构和非线性结构（D）内部结构和外部结构 5.算法分析的目的是（）。（A）找出数据结构的合理性（B）研究算法中的输入和输出的关系（C）分析算法的效率以求改进（D）分析算法的易懂性和文档性二、判断题 1.数据的机内表示称为数据的存储结构。（） 2.算法就是程序。（） 5.算法的时间复杂度取决于问题的规模和待处理数据的初态。（）三、填空题 1.数据逻辑结构包括________、________、_________ 和_________四种类型,其中树形结构和图形结构合称为_____。 2.在线性结构中,第一个结点____前驱结点,其余每个结点有且只有______个前驱结点；最后一个结点______后续结点,其余每个结点有且只有_______个后续结点。 3.在树形结构中,树根结点没有_______结点,其余每个结点有且只有_______个前驱结点；叶子结点没有________结点,其余每个结点的后续结点可以 _________。 4.在图形结构中,每个结点的前驱结点数和后续结点数可以_________。 5.线性结构中元素之间存在________关系,树形结构中元素之间存在______关系,图形结构中元素之间存在_______关系。 8.链式存储结构与顺序存储结构相比较,主要优点是 ________________________________。 9.设有一批数据元素,为了最快的存储某元素,数据结构宜用_________结构,为了方便插入一个元素,数据结构宜用____________结构。

数据结构-图习题

第8章图 8-1 画出1个顶点、2个顶点、3个顶点、4个顶点和5个顶点的无向完全图。试证明在n 个顶点的无向完全图中，边的条数为n(n-1)/2。【解答】【证明】在有n 个顶点的无向完全图中，每一个顶点都有一条边与其它某一顶点相连，所以每一个顶点有 n-1条边与其他n-1个顶点相连，总计n 个顶点有n(n-1)条边。但在无向图中，顶点i 到顶点j 与顶点j 到顶点i 是同一条边，所以总共有n(n-1)/2条边。 8-2 右边的有向图是强连通的吗？请列出所有的简单路径。【解答】点，它不是强连通的有向图。各个顶点自成强连通分量。所谓简单路径是指该路径上没有重复的顶点。从顶点A 出发，到其他的各个顶点的简单路径有A →B ，A →D →B ，A →B →C ，A →D →B →C ，A →D ，A →B →E ，A →D →E ，A →D →B →E ，A →B →C →F →E ，A →D →B →C →F →E ，A →B →C →F ，A 1个顶点的无向完全图 2个顶点的无向完全图 3个顶点的无向完全图 4个顶点的无向完全图 5个顶点的无向完全图 A D

????????? ?????? ?????=01 00000001001010000 010*********Edge →D →B →C →F 。从顶点B 出发，到其他各个顶点的简单路径有B →C ，B →C →F ，B →E ，B →C →F →E 。从顶点C 出发，到其他各个顶点的简单路径有C →F ，C →F →E 。从顶点D 出发，到其他各个顶点的简单路径有D →B ，D →B →C ，D →B →C →F ，D →E ，D →B →E ，D →B →C →F →E 。从顶点E 出发，到其他各个顶点的简单路径无。从顶点F 出发，到其他各个顶点的简单路径有F →E 。 8-3 给出右图的邻接矩阵、邻接表和邻接多重表表示。【解答】 (1) 邻接矩阵 A D

数据结构作业电子版

1数据结构课程研究的主要内容包括（）（）（） 2一个完整的算法应该具有_____ _____ ______ ______ ______五个特性 3数据的逻辑结构可分为_____ ______两大类 4数据的逻辑结构是指而存储结构是指 5逻辑上相邻的数据元素在物理位置上也相邻是存储结构的特点之一 6为了实现随机访问线性结构应该采用存储结构 7链式存储结构的主要特点是 8算法分析主要从和这两个方面对算法进行分析（1）数据（2）数据元素（3）数据类型（4）数据结构（5）逻辑结构（6）存储结构（7）线性结构（8）非线性结构第二章作业一、判断题(在你认为正确的题后的括号中打√，否则打X)。 1．线性表的逻辑顺序与存储顺序总是一致的。 2．顺序存储的线性表可以按序号随机存取。 3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。 4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。 5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。 6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。7．线性表的链式存储结构优于顺序存储结构。 8．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。 9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。二、单项选择题。 1．线性表是( ) 。 (A) 一个有限序列，可以为空； (B) 一个有限序列，不能为空； (C) 一个无限序列，可以为空； (D) 一个无序序列，不能为空。 2．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的（）个元素。 (A) n/2 (B) n+1/2 (C) n -1/2 (D) n 3．线性表采用链式存储时，其地址( ) 。

第4章数据结构与算法习题与答案

第四章习题（P111-113）一、复习题 1、试述数据和数据结构的概念及其区别。数据是对客观事物的符号表示，是信息的载体；数据结构则是指互相之间存在着一种或多种关系的数据元素的集合。（P93） 2、列出算法的五个重要特征并对其进行说明。算法具有以下五个重要的特征：有穷性：一个算法必须保证执行有限步之后结束。确切性：算法的每一步骤必须有确切的定义。输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件。输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法没有实际意义。可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。（P95） 3、算法的优劣用什么来衡量？试述如何设计出优秀的算法。时间复杂度空间复杂度（P97-98） 4、线性和非线性结构各包含哪些种类的数据结构？线性结构和非线性结构各有什么特点？线性结构用于描述一对一的相互关系，即结构中元素之间只有最基本的联系，线性结构的特点是逻辑结构简单。所谓非线性结构是指，在该结构中至少存在一个数据元素，有两个或两个以上的直接前驱（或直接后继）元素。树型和图型结构就是其中十分重要的非线性结构，可以用来描述客观世界中广泛存在的层次结构和网状结构的关系。（P99-105） 5、简述树与二叉树的区别；简述树与图的区别。树用来描述层次结构，是一对多或多对一的关系；二叉树（Binary Tree）是个有限元素的集合，该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。二叉树是有序的，即若将其左、右子树颠倒，就成为另一棵不同的二叉树。图也称做网，是一种比树形结构更复杂的非线性结构。在图中，任意两个节点之间都可能相关，即节点之间的邻接关系可以是任意的，图表示的多对多的关系。（P102-P104） 6、请举出遍历算法在实际中使用的例子。提示：根据实际生活中需要逐个访问处理的情况举例。 7、编写一个算法，统计在一个输入字符串中各个不同字符出现的频度。用适当的测试数据来验证这个算法。提示：根据查找算法和串中求子串的算法，查找输入串中以单个字符形式的子串。 8、若对有n个元素的有序顺序表和无序顺序表进行顺序搜索，试就下列三种情况分别讨论两者在等搜索概率时的平均搜索长度是否相同? (1) 搜索失败； (2) 搜索成功，且表中只有一个关键码等于给定值k的对象； (3) 搜索成功，且表中有若干个关键码等于给定值k的对象，要求一次搜索找出所有对象。

数据结构图的基本操作实现

实验五图的遍历及其应用实现一、实验目的 1．熟悉图常用的存储结构。 2．掌握在图的邻接矩阵和邻接表两种结构上实现图的两种遍历方法实现。 3．会用图的遍历解决简单的实际问题。二、实验内容 [题目一] ：从键盘上输入图的顶点和边的信息,建立图的邻接表存储结构,然后以深度优先搜索和广度优先搜索遍历该图,并输出起对应的遍历序列. 试设计程序实现上述图的类型定义和基本操作,完成上述功能。该程序包括图类型以及每一种操作的具体的函数定义和主函数。提示：输入示例上图的顶点和边的信息输入数据为： 5 7 DG A B C D E AB AE BC CD DA DB EC [题目二]：在图G中求一条从顶点 i 到顶点 s 的简单路径 [题目三]：寻求最佳旅游线路（ACM训练题）在一个旅游交通网中，判断图中从某个城市A到B是否存在旅游费用在s1-s2元的旅游线路，为节省费用，不重游故地。若存在这样的旅游线路则并指出该旅游线路及其费用。输入：第一行：n //n-旅游城市个数第2行：A B s1 s2 //s1,s2-金额数第3行---第e+2行 ( 1≤e≤n(n-1)/2 ) 表示城市x,y之间的旅行费用，输入0 0 0 表示结束。

输出：第一行表示 A到B的旅游线路景点序列第二行表示沿此线路，从A到B的旅游费用设计要求： 1、上机前，认真学习教材，熟练掌握图的构造和遍历算法,图的存储结构也可使用邻接矩阵等其他结构. 2、上机前，认真独立地写出本次程序清单，流程图。图的构造和遍历算法分别参阅讲义和参考教材事例图的存储结构定义参考教材相关函数声明： 1、/* 输入图的顶点和边的信息,建立图*/ void CreateGraph(MGraph &G) 2、/* 深度优先搜索遍历图*/ void DFSTraverse(Graph G, int v) 3、/*广度优先搜索遍历图 */ void BFSTraverse(Graph G, int v)4、 4、/* 其他相关函数 */…… 三、实验步骤㈠、数据结构与核心算法的设计描述㈡、函数调用及主函数设计（可用函数的调用关系图说明）㈢程序调试及运行结果分析㈣实验总结四、主要算法流程图及程序清单 1、主要算法流程图： 2、程序清单（程序过长，可附主要部分）

数据结构--图重点

一、定义与术语图：无序数据结构基本构成：1.边集（Edge ）：a. 有向图，有向边，弧，弧头，弧尾，权值 b. 无向图，无向边(v, w)，权值 2.顶点集（Vertices ）：a. 无向图：度(TD(v)) b. 有向图：出度(ID(v))，入度(OD(v))，度(TD(v) = ID(v) + OD(v)) 无向完全图：n 个顶点，(1)2 n n -条边有向完全图：n 个顶点，(1)n n -条边网：带权图连通分量：无向图中的极大连通子图（多个），无向完全图的连通分量就是本身（一个）强连通分量：有向图中的极大连通子图，其中i v 到j v 以及j v 到i v 都有路径生成树：图的极小连通子图，含有图的全部n 个顶点，只有n-1条边，少一条则不能连通，多一条则形成回路生成森林：不完全图中的各个连通分量的生成树，构成图的生成森林二、存储结构顶点：可采用链表或数组存储顶点列表，一般采用链表存储边：1. 邻接矩阵（数组） a. 无向图：对称阵，可采用矩阵压缩存储方式。A[i][j] = 0表示i v 和j v 没有连接； A[i][j] = 1表示i v 和j v 有边连接；第i 行的和表示顶点i v 的度 b. 有向图：不对称阵。,[][]i j A i j w =表示顶点i v 到j v 的有向弧的权值；[][]A i j =∞ 表示表示顶点i v 到j v 没有弧连接或者i = j 2. 邻接表（链表，有向无向都可用）边结点：adjvex （邻接点），nextarc （下一条边），info （权值）顶点结点：data （顶点数据），firstarc （第一条边） 3. 十字链表（Othogonal List ）弧结点：tailvex （弧尾结点），headvex （弧头结点），tlink （弧尾相同的下一条弧），hlink （弧头相同的下一条弧），info （权值）顶点结点：data （顶点数据），firstin （第一条入弧），firstout （第一条出弧）三、图的遍历（每个顶点只被访问一次） 1. 深度优先遍历（类似树的先根遍历）基本思想：假设初始状态是图中所有顶点未曾被访问，则深度优先搜索可从图中某个顶点v 出发，访问此结点，然后依次从v 的未被访问的邻接点出发深度优先遍历图，直至图中所有和v 有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问（非连通图），则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

数据结构课后习题答案第四章

第四章一、简述下列每对术语的区别：空串和空白串；串常量和串变量；主串和子串；静态分配的顺序串和动态分配的顺序串；目标串和模式串；有效位移和无效位移。答： ●空串是指不包含任何字符的串，它的长度为零。空白串是指包含一个或多个空格的串，空格也是字符。 ●串常量是指在程序中只可引用但不可改变其值的串。串变量是可以在运行中改变其值的。 ●主串和子串是相对的，一个串中任意个连续字符组成的串就是这个串的子串，而包含子串的串就称为主串。 ●静态分配的顺序串是指串的存储空间是确定的，即串值空间的大小是静态的，在编译时刻就被确定。动态分配的顺序串是在编译时不分配串值空间，在运行过程中用malloc和free等函数根据需要动态地分配和释放字符数组的空间(这个空间长度由分配时确定，也是顺序存储空间)。 ●目标串和模式串:在串匹配运算过程中，将主串称为目标串，而将需要匹配的子串称为模式串，两者是相对的。 ●有效位移和无效位移：在串定位运算中，模式串从目标的首位开始向右位移，每一次合法位移后如果模式串与目标中相应的字符相同，则这次位移就是有效位移(也就是从此位置开始的匹配成功)，反之，若有不相同的字符存在，则此次位移就是无效位移(也就是从此位置开始的匹配失败)。二、假设有如下的串说明： char s1[30]="Stocktom,CA", s2[30]="March 5 1999", s3[30], *p; (1)在执行如下的每个语句后p的值是什么? p=stchr(s1,'t'); p=strchr(s2,'9'); p=strchr(s2,'6'); (2)在执行下列语句后，s3的值是什么? strcpy(s3,s1); strcat(s3,","); strcat(s3,s2); (3)调用函数strcmp(s1,s2)的返回值是什么?

数据结构课后习题第四章

第四章串习题4 一、选择题 1.串是一种分外的线性表，其分外性体现在（）。 A.可以顺序存储 B.数据元素是一个字符 C.可以连接存储 D.数据元素可以是多个字符 2.有两个串P和Q，求P在Q中首次出现的位置的运算称为（）。 A.模式匹配 B.联接 C.求子串 D.求串长 3.设S为一个长度为n的字符串，其中的字符各不相同，则S中的互异的非通俗子串（非空且例外于S本身）的个数为（）。 A.n2 B.（n2/2）+（n/2） C.（n2/2）+（n/2）-1 D.（n2/2）-（n/2）-1 4.设串s1=“ABCDEFG”,s2=“PQRST”，函数concat（x，y）返回x和y串的连接串，subString（s，i，j）返回串s的从序号i的字符开始的j个字符组成的子串，Strlength（s）返回串s的长度，则concat（subString（s1，2，Strlength （s2）），subString(s1，Strlength（s2），2)））的结果串是（）。 A.BCDEF B.BCDEFG C.BCPQRST D.BCDEFEF 5.顺序串中，根据空间分配方式的例外，可分为（）。 A.直接分配和间接分配 B.静态分配和动态分配 C.顺序分配和链式分配 D.随机分配和不变分配 6.设串S=“abcdefgh”，则S的所有非通俗子串（除空串和S自身的串）的个数是（）。

A.8 B.37 C.36 D.35 7.设主串的长度为n，模式串的长度为m，则串匹配的KMP算法时间复杂度是（）。 A.O(m) B.O（n） C.O（m+n） D.O（n*m） 8.已知串S=“aaab”，其next数组值为（）。 A.0123 B.1123 C.1231 D.1211 二丶填空题 1.在空串和空格串中，长度不为0的是（）。 2.空格串是指（），其长度等于（）。 3.按存储结构的例外，串可分为（）、（）和（）。 4.C语言中，以字符（）表示串值的终结。 5.在块链串中，为了提高存储密度，应该增大（）。 6.假设每个字符占1个字节，若结点大小为4个字节的链串的存储密度为50％，则其每个指针占（）个字节。 7.串操作虽然较多，但都可以通过五中基本操作（）、（）、（）、（）和（）构成的最小子集中的操作来实现。 8.设串S=“Ilikecomputer.”，T=“com”，则Length（S）=（），Index（S,T,1）=（）。 9.在KMP算法中，next[j]只与（）串有关，而与（）串无关。 10.字符串“ababaaab”的nextval函数值为（）。 11.两个字符串相等的充分必要条件是（）。 12.实现字符串复制的函数strcpy为：

数据结构实验图的基本操作

浙江大学城市学院实验报告课程名称数据结构实验项目名称实验十三/十四图的基本操作学生姓名专业班级学号实验成绩指导老师（签名）日期2014/06/09 一.实验目的和要求 1、掌握图的主要存储结构。 2、学会对几种常见的图的存储结构进行基本操作。二.实验内容 1、图的邻接矩阵定义及实现：建立头文件test13_AdjM.h，在该文件中定义图的邻接矩阵存储结构，并编写图的初始化、建立图、输出图、输出图的每个顶点的度等基本操作实现函数。同时建立一个验证操作实现的主函数文件test13.cpp（以下图为例），编译并调试程序，直到正确运行。 2、图的邻接表的定义及实现：建立头文件test13_AdjL.h，在该文件中定义图的邻接表存储结构，并编写图的初始化、建立图、输出图、输出图的每个顶点的度等基本操作实现函数。同时在主函数文件test13.cpp中调用这些函数进行验证（以下图为例）。

3、填写实验报告，实验报告文件取名为report13.doc。 4、上传实验报告文件report13.doc到BB。注: 下载p256_GraphMatrix.cpp(邻接矩阵)和 p258_GraphAdjoin.cpp(邻接表)源程序，读懂程序完成空缺部分代码。三. 函数的功能说明及算法思路（包括每个函数的功能说明，及一些重要函数的算法实现思路）四. 实验结果与分析（包括运行结果截图、结果分析等）

五.心得体会

程序比较难写，但是可以通过之前的一些程序来找到一些规律（记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。）【附录----源程序】 256: //p-255 图的存储结构以数组邻接矩阵表示, 构造图的算法。 #include #include #include #include typedef char VertexType; //顶点的名称为字符 const int MaxVertexNum=10; //图的最大顶点数 const int MaxEdgeNum=100; //边数的最大值 typedef int WeightType; //权值的类型 const WeightType MaxValue=32767; //权值的无穷大表示 typedef VertexType Vexlist[MaxVertexNum]; //顶点信息，定点名称 typedef WeightType AdjMatrix[MaxVertexNum][MaxVertexNum]; //邻接矩阵typedef enum{DG,DN,AG,AN} GraphKind; //有向图,有向网,无向图,无向网typedef struct{ Vexlist vexs; // 顶点数据元素 AdjMatrix arcs; // 二维数组作邻接矩阵 int vexnum, arcnum; // 图的当前顶点数和弧数 GraphKind kind; // 图的种类标志 } MGraph; void CreateGraph(MGraph &G, GraphKind kd)// 采用数组邻接矩阵表示法，构造图G {//构造有向网G int i,j,k,q; char v, w; G.kind=kd; //图的种类 printf("输入要构造的图的顶点数和弧数：\n"); scanf("%d,%d",&G.vexnum,&G.arcnum); getchar();//过滤回车 printf("依次输入图的顶点名称ABCD...等等：\n"); for (i=0; i

数据结构中图的全部操作

#include #include #include #include #include #include using namespace std; #define MAX_VERTEX_NUM 100 #define INFINITY INT_MAX #define EXTERN 10 #define OK 1 #define ERROR -1 #define MAX -1 #define MAXW 10000 typedef int Status; typedef bool VisitIf; typedef char VertexType;//顶点数据类型 typedef int VRType; //顶点关系( 表示是否相邻) typedef int InfoType; //弧相关信息

typedef enum{DG,DN,UDG,UDN} GraphKind;//图的类型 bool visited[MAX_VERTEX_NUM]; //邻接矩阵 typedef struct ArcCell { VRType adj;//权值 InfoType *info; }ArcCell,AdjMartix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { VertexType vexs[MAX_VERTEX_NUM]; //顶点向量 AdjMartix arcs; //邻接矩阵 int vexnum,arcnum; //图当前顶点数,弧数 GraphKind Kind; //图的类型 }MGraph; bool VexExist(MGraph G,VertexType v)//判断定点是否在图中{

数据结构课后习题及解析第四章

11．写算法，实现顺序串的基本操作 StrReplace(&s,t,v) r1 中第 index 个字符起求出首次与串 r2 相同的子串的起始位置。写一个函数将顺序串 s1 中的第 i 个字符到第 j 个字符之间的字符用 s2 串替换。写算法，实现顺序串的基本操作 StrCompare(s,t) 。第四章习题 1. 设 s=' I AM A STUDENT , t= ' GOO D, q=' WORKER 给出下列操作的结果: StrLength(s); SubString(sub1,s,1,7); SubString(sub2,s,7,1); StrIndex(s, ' A ' ,4); StrReplace(s, ' STUDEN 'T,q); StrCat(StrCat(sub1,t), StrCat(sub2,q)); 2. 编写算法，实现串的基本操作 StrReplace(S,T,V) 。 3. 假设以块链结构表示串，块的大小为 1，且附设头结点。试编写算法，实现串的下列基本操作： StrAsign(S,chars) ； StrCopy(S,T) ； StrCompare(S,T) ； StrLength(S) ； StrCat(S,T) ； SubString(Sub,S,pos,len) 。 4．叙述以下每对术语的区别：空串和空格串；串变量和串常量；主串和子串；串变量的名字和串变量的值。 5．已知：S=”(xyz)* ” ,T= ”(x+z)*y ”。试利用联接、求子串和置换等操作，将 S 转换为T. 6． S 和T 是用结点大小为1的单链表存储的两个串，设计一个算法将串 S 中首次与T 匹配的子串逆置。 7． S 是用结点大小为4的单链表存储的串，分别编写算法在第k 个字符后插入串T ,及从第k 个字符删除 len 个字符。以下算法用定长顺序串： 8．编写下列算法： 1) 将顺序串 r 中所有值为 ch1 的字符换成 ch2 的字符。 2) 将顺序串 r 中所有字符按照相反的次序仍存放在 r 中。 3) 从顺序串 r 中删除其值等于 ch 的所有字符。 5) 从顺序串 r 中删除所有与串 r1 相同的子串。从顺序串 9． 10．

数据结构作业系统_第四章答案

4.10③编写对串求逆的递推算法。要求实现以下函数： void Reverse(StringType &s); /* Reverse s by iteration. */ StringType是串的一个抽象数据类型，它包含以下6种基本操作： void InitStr(StringType &s); // 初始化s为空串。 void StrAssign(StringType &t, StringType s); // 将s的值赋给t。s的实际参数是串变量。 int StrCompare(StringType s, StringType t); // 比较s和t。若s>t，返回值>0；若s=t，返回值=0；若s

数据结构第1阶段练习题

第一阶段练习题考试科目:《数据结构》第一章至第四章（总分100分） ______________学习中心（教学点）批次：层次：专业：学号：身份证号：姓名：得分：一、选择题（每题3分，共30分） 1、在树形结构中，数据元素间存在（）的关系。Ａ、一对一Ｂ、一对多Ｃ、多对多Ｄ、除同属一个集合外别无关系 2、下列说法中错误的是（）。Ａ、数据对象是数据的子集Ｂ、数据元素间关系在计算机中的映象即为数据的存储结构Ｃ、非顺序映象的特点是借助指示元素存储地址的指针来表示数据元素间逻辑关系Ｄ、抽象数据类型指一个数学模型及定义在该模型上的一组操作 3、下列不属算法特性的是（）。Ａ、有穷性Ｂ、确定性Ｃ、零或多个输入Ｄ、健壮性 4、在长为n的顺序表中删除一个数据元素，平均需移动（）个数据元素。Ａ、n Ｂ、n-1 Ｃ、n/2 Ｄ、(n-1)/2 5、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。Ａ、顺序表Ｂ、双链表Ｃ、带头结点的双向循环链表Ｄ、单循环链表 6、在一个可存放n个数据元素的顺序栈中，假设以高地址端为栈底，以top为栈顶指针，当向栈中压入一个数据元素时，top的变化是（）。Ａ、不变Ｂ、top=n Ｃ、top++ Ｄ、top-- 7、设在一不带头结点的链队列中，front和rear分别为其队头和队尾指针，则删除一个结点的操作是（）。Ａ、rear=front->next Ｂ、rear=rear->next Ｃ、front=front->next Ｄ、front=rear->next 8、判定一个栈顶指针为S且不带头结点的链栈为空栈的条件是（）。Ａ、S Ｂ、S->next Ｃ、S->next==NULL Ｄ、!S 9、设在一不带头结点的链队列中，front和rear分别为其队头和队尾指针，则判定该队中只有一个结点的条件是（）。Ａ、front->next Ｂ、rear->next Ｃ、front==rear Ｄ、front!=rear 10、串的长度是指（）。

《数据结构》基本操作指导

目录指导一、单链表的操作----------------------------------------------------- 2指导二、栈及其应用------------------------------------------------------- 10指导三、串的基本操作---------------------------------------------------- 16指导四、二叉树的基本操作---------------------------------------------- 21指导五、图的存储和遍历------------------------------------------------- 31指导六、查找--------------------------------------------------------------- 41 指导七、排序--------------------------------------------------------------- 49

指导一、单链表的操作一、指导目的 1、掌握线性表的链式存储结构。 2、掌握利用链式存储结构实现线性表的基本操作。 3、掌握链式存储结构中的算法实现。二、指导内容 1、建立带头结点的单链表，并输出该单链表。 2、实现带头结点的单链表上的插入、删除、查找、修改操作。三、操作指导 1、定义单链表的结点结构单链表的结点结构可为一个结构体类型(slnodetype)，其成员是数据域和指针域，数据域可以是整数。 2、模块划分和程序控制流程根据实验要完成的各功能，设置初始化、建立单链表、输出单链表、插入、删除、查找、修改和主函数8个模块，对于要完成的各功能，采用适当的人机界面，用循环和分支结构构成菜单进行选择。 3、初始化模块int initiate(slnodetype **h) 该模块中产生一个只有头结点的空单链表，用指针h作为函数的参数返回，因为h是指针变参，所以在函数的参数位置要以二级指针出现。在函数里，申请一个头结点空间。 4、建立单链表模块int createlink(slnodetype *h) 该模块中建立有若干个结点的单链表，用循环控制输入若干个整数，申请相应的结点空间，以输入的整数作为结点中的数据，依次链接到初始只有头结点的单链表h中，可以把输入0作为建立链表的结束。 5、输出单链表模块void display(slnodetype *h) 对于传入的单链表h，依次输出单链表中的结点(数据)。 6、插入结点模块int inserti(slnodetype *h) 设在第i个结点前插入数据为data的结点。在该函数模块中输入i和数据data，对于传入的单链表h，先查找是否存在插入的位置(单链表h中至少要有i-1个结点)，若不存在插入位置，则不做任何操作；若存在插入位置，则申请一个结点，其数据为data，挂在第i-1个结点的后面。 7、删除结点模块int delete(slnodetype *h) 在该函数模块中，首先可以调用输出模块输出传入的单链表h，以便选择要删除的结点，然后输入要删除结点的数据data，再查找是否存在要删除的结点，若不存在要删除的结点，则显示相应的信息；若存在要删除的结点，则删除该结点(包括删除该结点空间)。 8、查找模块int search(slnodetype *h)