数据结构第四章参考答案
习题4
1. 填空题
（1）一般来说，数组不执行（___________）和（___________）操作，所以通常采用（___________）方法来存储数组。通常有两种存储方式：（___________）和（___________）。 答案：删除 插入 顺序存储 行优先存储 列优先存储
（2）设8行8列的二维数组起始元素为A[0][0]，按行优先存储到起始元素下标为0的一维数组B 中，则元素B[23]在原二维数组中为（___________）。若该二维数组为上三角矩阵，按行优先压缩存储上三角元素到起始元素下标为0的一维数组C 中，则元素C[23]即为原矩阵中的（___________）元素。 答案：A[2][7] A[3][5]
（3）设二维数组A 为6行8列，按行优先存储，每个元素占6字节，存储器按字节编址。已知A 的起始存储地址为1000H ，数组A 占用的存储空间大小为（___________）字节，数组A 的最后一个元素的下标为（___________），该元素的第一个字节地址为（___________）H ，元素A[1][4]的第一个字节的地址为（___________）H 。（提示：下标从0开始计） 答案：288 A[5][7] 111AH 1048H
（4）设C++中存储三维数组A mnp ，则第一个元素为a 000，若按行优先存储，则a ijk 前面共有（___________）个元素；若按列优先存储，则a ijk 前面共有（___________）个元素。 答案：inp+jp+k i+mj+mnk
（5）常见的稀疏矩阵压缩方法有：（___________）和（___________）。 答案：三元组表 十字链表 （6）广义表（（a ），（（b ，c ），d ），（e ））的长度为（___________），表头为（___________），表尾为（___________）。 答案：3 （a ） （（（b ，c ），d ），（e ）） （7）设广义表LS ＝（（a ），（（b ，c ），d ），（e ）），若用取表头操作GetHead （）和取表尾操作GetTail （）进行组合操作，则取出元素b 的运算为（___________）。 答案：GetHead(GetHead(GetHead(GetTail(LS))))
（8）若广义表A 满足GetHead （A ）＝GetTail （A ），则A ＝（___________）。 答案：（（））
2. 问答题
（1）根据下面的矩阵，写出矩阵转置后的三元组表，起始行列值为1。
?????????
? ??-00000015000001800000130001400003005000000009120
（2）对于如下稀疏矩阵，请写出对应的三元组顺序表，若采用顺序取，直接存的算法进行转置运算，引入辅助数组number[]和position[]，分别表示矩阵各列的非零元素个数和矩阵中各列第一个非零元素在转置矩阵中的位置，请写出数组中的各元素（所有数组起始元素下标为0）。
原矩阵 ??
?
?
?
?
?
?
?-000051000003
02
（3）对于上题中的稀疏矩阵，写出对应的三元组表和十字链表。
十字链表：
3.算法设计
（1）设计上三角矩阵存储类，实现如下接口：
①对于上三角矩阵A[N][N]，可按行优先压缩存储和按列优先压缩存储。
②对于给定的一维数组B[M]，可根据行优先压缩存储或列优先压缩存储还原原始的上三角矩阵。
（2）针对24位真彩色BMP图像文件，编写程序实现如下功能：
①读取24位真彩色BMP图像文件。
②将原图像转换为24位灰度图像，并进行保存。转按公式如下：
Grey=0.3*Red+0.59*Blue+0.11*Green
③将24位灰度图像转换为8位灰度图像，并进行保存。
④将8位灰度图像分别进行4－邻域和8－邻域平滑，并分别进行保存。
(完整版)数据结构实验报告全集
数据结构实验报告全集 实验一线性表基本操作和简单程序 1 ．实验目的 （1 ）掌握使用Visual C++ 6.0 上机调试程序的基本方法； （2 ）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2 ．实验要求 （1 ）认真阅读和掌握和本实验相关的教材内容。 （2 ）认真阅读和掌握本章相关内容的程序。 （3 ）上机运行程序。 （4 ）保存和打印出程序的运行结果，并结合程序进行分析。 （5 ）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 实验代码： 1）头文件模块 #include iostream.h>// 头文件 #include
nodetype *create()// 建立单链表，由用户输入各结点data 域之值， // 以0 表示输入结束 { elemtype d;// 定义数据元素d nodetype *h=NULL,*s,*t;// 定义结点指针 int i=1; cout<<" 建立一个单链表"<
数据结构习题(,,章)
数据结构习题(,,章)
————————————————————————————————作者：————————————————————————————————日期：
第四章串 一．选择题 1．若串S='software',其子串的数目是（） A．8 B．37 C．36 D．9 2．设有两个串p和q,求q在p中首次出现的位置的运算称作（） A．连接B．模式匹配C．求串长D．求子串 3．设字符串S1=“ABCDEFG”，S2=“PQRST”，则运算： S=CONCAT（SUBSTR（S1，2，LEN（S2））；SUBSTR（S1，LEN（S2），2））；后的串值为（） A．A BCDEF B．BCDEFG C．BCDPQRST D． BCDEFEF 4．下面的说法中，只有（）是正确的 A．串是一种特殊的线性表B．串的长度必须大于零 C．串中元素只能是字母D．空串就是空白串 5．两个字符串相等的条件是（） A．两串的长度相等 B．两串包含的字符相同 C．两串的长度相等，并且两串包含的字符相同 D．两串的长度相等，并且对应位置上的字符相同 二．填空题 1．串“ababcbaababd”的next函数值为，nextval函数值为。2．子串的长度为。 第五章数组和广义表 一．选择题 1．设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为( ) A. BA+141 B. BA+180 C. BA+222 D. BA+225 2．假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（） A. 808 B. 818 C. 1010 D. 1020 3．对稀疏矩阵进行压缩存储目的是（） A．便于进行矩阵运算B．便于输入和输出C．节省存储空间D．降低运算的时间复杂度 4．假设以三元组表表示稀疏矩阵，则与如图所示三元组表对应的4×5的稀疏矩阵是（注：矩阵的行列下标均从1开始）（）
数据结构课后习题答案第四章
第四章 一、简述下列每对术语的区别： 空串和空白串；串常量和串变量；主串和子串；静态分配的顺序串和动态分配的顺序串；目标串和模式串；有效位移和无效位移。 答： ●空串是指不包含任何字符的串，它的长度为零。 空白串是指包含一个或多个空格的串，空格也是字符。 ●串常量是指在程序中只可引用但不可改变其值的串。 串变量是可以在运行中改变其值的。 ●主串和子串是相对的，一个串中任意个连续字符组成的串就是这个串的子串，而包含子串的串就称为主串。 ●静态分配的顺序串是指串的存储空间是确定的，即串值空间的大小是静态的，在编译时刻就被确定。 动态分配的顺序串是在编译时不分配串值空间，在运行过程中用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为：
数据结构复习题三
数据结构练习题 第一章绪论 一．选择题 1、在数据结构的讨论中把数据结构从逻辑上分为（）。 A.内部结构与外部结构 B.静态结构与动态结构 C.线性结构与非线性结构 D.紧凑结构与非紧凑结构 2、采用线性链表表示一个向量时，要求占用的存储空间地址（）。A: 必须是连续的 B 部分地址必须是连续的 C: 一定是不连续的C: 可连续可不连续 3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（）。 A: n B: n/2 C: (n-1)/2 D: (n+1)/2 4、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（）。 A: s→next = p→next;p→next = s; B: p→next= s; s→next = q; C: p→next = s→next;s→next = p;D: q→next= s;s→next= p; 8.下面程序段的时间复杂度为____________。 for(int i=0; i 二．填空题 1.通常，评价一个算法有正确性、健壮性、_________、时间复杂度、空间复杂度五个方面。 2.在数据结构中，数据的逻辑结构有线性结构、图结构、________________、_______________四种，物理实现上有顺序结构、索引结构、___________、_____________四种。 第三章线性表 一．选择题 1.在一个单链表HL中,若要向q所指结点之后插入一个指针p指向的结点,则执行. A. HL=p; p->next=HL B. P->next=HL; HL=p C. P->next=q->next; q->next=p D. P->next=q->next; q=p->next 2.在一个长度为n的顺序存储线性表中，向第i个元素(1≤i≤n+1)之前插入一个新元素时，需要从后向前依次后移个元素。 A、n-i B、n-i+1 C、n-i-1 D、i 3.在一个长度为n的顺序存储线性表中，删除第i个元素(1≤i≤n+1)时，需要从前向后依次前移个元素。 A、n-i B、n-i+1 C、n-i-1 D、i 4.在一个长度为n的线性表中顺序查找值为x的元素时，查找时的平均查找长度（即x同元素的平均比较次数，假定查找每个元素的概率都相等）为。 A、n B、n/2 C、(n+1)/2 D、(n-1)/2 5.在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行。 A、HL = p; p->next = HL; B、p->next = HL; HL = p; C、p->next = HL; p = HL; D、p->next = HL->next; HL->next = p; 6.在一个单链表HL中，若要在指针q所指的结点的后面插入一个由指针p所指的结点，则执行。 A、q->next = p->next ; p->next = q; B、p->next = q->next; q = p; 《数据结构》实验报告 实验序号：4 实验项目名称：栈的操作 附源程序清单： 1. #include { return false; } else { st->top++; //移动栈顶位置 st->data[st->top]=x; //元素进栈 } return true; } bool Pop(SqStack *st,ElemType &e) //出栈 { if(st->top==-1) { return false; } else { e=st->data[st->top]; //元素出栈 st->top--; //移动栈顶位置} return true; } //函数名：Pushs //功能：数组入栈 //参数：st栈名,a->数组名，i->数组个数 bool Pushs(SqStack *st,ElemType *a,int i) { int n=0; for(;n 江南大学现代远程教育第一阶段练习题及答案 考试科目:《数据结构》第一章至第四章（总分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、串的长度是指（）。 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． 课程实验报告课程名称：数据结构 专业班级：信安1302 学号： 姓名： 指导教师： 报告日期：2015. 5. 12 计算机科学与技术学院 目录 1 课程实验概述............ 错误!未定义书签。 2 实验一基于顺序结构的线性表实现 2.1 问题描述 ...................................................... 错误!未定义书签。 2.2 系统设计 ...................................................... 错误!未定义书签。 2.3 系统实现 ...................................................... 错误!未定义书签。 2.4 效率分析 ...................................................... 错误!未定义书签。 3 实验二基于链式结构的线性表实现 3.1 问题描述 ...................................................... 错误!未定义书签。 3.2 系统设计 ...................................................... 错误!未定义书签。 3.3 系统实现 ...................................................... 错误!未定义书签。 3.4 效率分析 ...................................................... 错误!未定义书签。 4 实验三基于二叉链表的二叉树实现 4.1 问题描述 ...................................................... 错误!未定义书签。 4.2 系统设计 ...................................................... 错误!未定义书签。 4.3 系统实现 ...................................................... 错误!未定义书签。 4.4 效率分析 ...................................................... 错误!未定义书签。 5 实验总结与评价 ........... 错误!未定义书签。 1 课程实验概述 这门课是为了让学生了解和熟练应用C语言进行编程和对数据结构进一步深入了解的延续。 绪论和线性表习题 一、选择题 1.在一个单链表中，若p↑结点不是最后结点，在p↑之后插入s↑结点，则实行( )。 A. s->next=p；p->next=s; B、s->next=p->next; p->next=s； C. s->next=p->next;p=s; D. p->next=s;s->next=p; 2.与单链表相比,双链表优点之一( ). A.插入删除操作更简单. B.可随机访问 C.可省略表头指针和表尾指针 D、顺序访问相临结点更灵活 3.在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为( ) A、 n-i+1 B.n-i C.i D.i-1 4.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( ) A.顺序表 B.用头指针表示的单循环链表 C、用尾指针表示的单循环链表 D.单链表 5.在需要经常查找结点的前驱与后继的场合中，使用( )比较合适。 A.单链表B、双链表 C.顺序表 D.循环链 表 6.下面关于线性表的叙述中，错误的为( ) A.顺序表使用一维数组实现的线性表 B.顺序表必须占用一片连续的存储单元 C.顺序表的空间利用率高于链表 D、在链表中，每个结点只有一个链域 7.带头结点head的单链表为空的判断条件是( ) A. head=NUIL B、head->next=NUIL C. head->next=head D. head!=NUIL 8.线性表通常采用两种存储结构是( ) A、顺序存储结构和链式存储结构 B.散列方式和索引方式 C.链表存储结构和数组 D.线性存储结构和非线性存储结构 9．线性表采用链式存储时，结点的存储地址（） A．必须是不连续的 B、连续与否均可 C．必须是连续的 D．和头结点的存储地址相连续 10．将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（） A．O（1） B．O（n） C、 O（m） D．O（m+n） 第四章空间数据的处理 学习要求：掌握数据处理的基本内容、途径和算法。 §4.1 矢量数据拓扑关系的自动建立 矢量数据拓扑关系在空间数据的查询与分析中非常重要，矢量数据拓扑关系自动建立的算法是GIS中的关键算法之一，这里介绍其实现的基本步骤和要点： 一、链的组织 找出在链的中间相交，而不是在端点相交的情况，自动切成新链；把链按一定顺序存储，然后把链按顺序编号。 二、结点匹配 结点匹配是指把一定限差内的链的端点作为一个结点，其坐标值取多个端点的平均值。 三、检查多边形是否闭合 检查多边形是否闭合可以通过判断一条链的端点是否有与之匹配的端点来进行。 四、建立多边形 建立多边形是矢量数据自动拓扑中最关键的部分，由于其算法比较复杂。先介绍了几个基本概念：顺时针方向构多边形、最靠右边的链、多边形面积的计算，然后介绍其实现的过程。 五、岛的判断 论述多边形之间的一种关系。岛的判断即指找出多边形互相包含的情况，也即寻找多边形的连通边界。 六、确定多边形的属性 多边形以内点标识。内点的属性常赋于多边形。 §4.2 矢量数据的图形编辑 图形编辑是纠正数据采集错误的重要手段，其基本的功能要求是：具有友好的人机界面；具有对几何数据和属性编码的修改功能；具有分层显示和窗口功能。图形编辑的关键是点、线、面的捕捉。 一、点的捕捉 图形编辑是纠正数据采集错误的重要手段。点的捕捉就是计算机屏幕上进行图形编辑时如何根据光标的位置找到需要编辑的要素点。 1、点的捕捉 图4-2-1 图4-2-2 但是由于在计算d时需进行乘方运算，所以影响了搜索的速度，因此，把距离d的计算改为： 二、线的捕捉 线的捕捉就是计算机屏幕上进行图形编辑时如何根据光标的位置找到需要编辑的线。方法是计算点到直线的距离。 图4-2-3 图 4-2-4 图4-2-5 如图4-2-5所示，点S(x,y)到直线段(x 1,y 1 ),(x 2 ,y 2 )的距离d的计算公 式为： 读书破万卷下笔如有神 《一定能摸到红球吗？》说课稿 林银花 教材说明：一、１、课题：《一定能摸到红球吗？》 ２、本节内容的地位和作用 在现代社会中，人们面临着更多的机会和选择，常常需要在不确定情境中作出合理的决策,概率正是通过对不确定现象和事件发生的可能性的刻画,来为人们更好的制定决策提供依据和建议.本节内容又是 义务教育阶段,唯一培养学生从不确定的角度来观察世界的数学内容,让学生了解可能性是普遍的,有助于他们理解社会,适应生活. ３、教学目标设计： (１)认知目标： （Ａ）经历猜测．实验．收集与分析试验结果等过程 （Ｂ）体会事件的发生的不确定性知道事情发生的可能性有多大。 （２）、能力目标： (Ａ)经历游戏等的活动过程，初步认识确定事件和不确定事件 （Ｂ）在与其它人交流的过程中，能合理清晰地表达自己的思维过程； （３）、情感目标： （Ａ）通过创设游戏情境，让学生主动参与，做“数学实验”，激发学生学习的热情和兴趣，激活学生思维。 （Ｂ）在与他人的合作过程中，增强互相帮助、团结协作的精神。 （Ｃ）体会到在生活中我们可以从确定和不确定两方面分析一件事情. ４、本课重点、难点分析： 学习的重点是初步体验事情发生的确定性和不确定性. 学习的难点是确定事件发生的可能性大小. 学习本节知识应注意猜测,试验,收集与分析实验结果,从中体会事件发生的可能性及大小. 二、教学对象分析： 1、初一学生性格开朗活泼，对新鲜事物特别敏感，且较易接受，因此，教学过程中创设的问题情境应较生动活泼，直观形象，且贴近学生的生活，从而引起学生的有意注意。 2、初一学生的概括能力较弱，推理能力还有待不断发展，所以在教学时，可让学生充分试验, 收集，分析,帮助他们直观形象地感知。 图实验 一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template { int i, j, k; vertexNum = n, arcNum = e; for(i = 0; i < vertexNum; i++) vertex[i] = a[i]; for(i = 0;i < vertexNum; i++) for(j = 0; j < vertexNum; j++) arc[i][j] = 0; for(k = 0; k < arcNum; k++) { cout << "Please enter two vertexs number of edge: "; cin >> i >> j; arc[i][j] = 1; arc[j][i] = 1; } } template 附录A 实验报告 课程：数据结构（c语言）实验名称：图的建立、基本操作以及遍历系别：数字媒体技术实验日期： 12月13号 12月20号 专业班级：媒体161 组别：无 姓名：学号： 实验报告内容 验证性实验 一、预习准备： 实验目的： 1、熟练掌握图的结构特性，熟悉图的各种存储结构的特点及适用范围； 2、熟练掌握几种常见图的遍历方法及遍历算法； 实验环境：Widows操作系统、VC6.0 实验原理： 1.定义： 基本定义和术语 图(Graph)——图G是由两个集合V(G)和E(G)组成的,记为G=(V,E)，其中：V(G)是顶点(V ertex)的非空有限集E(G)是边(Edge)的有限集合，边是顶点的无序对(即：无方向的，（v0,v2）)或有序对（即：有方向的, 无向图中顶点V i的度TD(V i)是邻接矩阵A中第i行元素之和有向图中， 顶点V i的出度是A中第i行元素之和 顶点V i的入度是A中第i列元素之和 邻接表 实现：为图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（有向图中指以Vi为尾的弧） 特点: 无向图中顶点Vi的度为第i个单链表中的结点数有向图中 顶点Vi的出度为第i个单链表中的结点个数 顶点Vi的入度为整个单链表中邻接点域值是i的结点个数 逆邻接表：有向图中对每个结点建立以Vi为头的弧的单链表。 图的遍历 从图中某个顶点出发访遍图中其余顶点，并且使图中的每个顶点仅被访问一次过程.。遍历图的过程实质上是通过边或弧对每个顶点查找其邻接点的过程，其耗费的时间取决于所采用的存储结构。图的遍历有两条路径：深度优先搜索和广度优先搜索。当用邻接矩阵作图的存储结构时，查找每个顶点的邻接点所需要时间为O（n2），n为图中顶点数；而当以邻接表作图的存储结构时，找邻接点所需时间为O（e），e 为无向图中边的数或有向图中弧的数。 实验内容和要求： 选用任一种图的存储结构，建立如下图所示的带权有向图： 要求：1、建立边的条数为零的图； 第四章习题（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的对象，要求一次搜索找出所有对象。 C.分析算法的效率以求改进 答：C D.分析算法的易懂性和文档性 （5）计算机算法指的是 （）。 答：C 答：B 2. 填空题 答：①逻辑结构 ②存储结构 ③运算 数据结构简明教程》练习题及参考答案 练习题1 1.单项选择题 （1）线性结构中数据元素之间是 （）关系。 A. 一对多 B.多对多 C.多对一 答：D D.—对一 （2）数据结构中与所使用的计算机无关的是数据 的 A.存储 B.物理 答：C C ?逻辑 （）结构。 D.物理和存储 （3）算法分析的目的是 （ A.找出数据结构的合理性 ）。 B.研究算法中的输入和输出的关系 （4）算法分析的两个主要方面 是 ）。 A.空间复杂性和时间复杂性 B.正确性和简明性 C.可读性和文档性 答：A D.数据复杂性和程序复杂性 A.计算方法 B.排序方法 C ?求解问题的有限运算序列 D.调度方法 （6）计算机算法必须具备输入 A. 可行性、可移植性和可扩充性 、输出和（）等5个特性。 B. 可行性、确定性和有穷性 C.确定性、有穷性和稳定性 D.易读性、稳定性和安全性 （1）数据结构包括数据的 卫 、数据的 ② 和数据的 ③ 这三个方面的内容。 数据结构简明教程 (2)数据结构按逻辑结构可分为两大类，它们分别是 ①和②。 答：①线性结构②非线性结构 (3)数据结构被形式地定义为(D,R),其中D是① 的有限集合,R是D上的止有限集合。 答：①数据元素②关系 (4)在线性结构中，第一个结点①前驱结点,其余每个结点有且只有1个前驱结点；最后一个结点②后继结点,其余每个结点有且只有1个后继结点。 答：①没有②没有 (5)在树形结构中，树根结点没有①结点,其余每个结点有且只有②个前驱结 点；叶子结点没有③结点,其余每个结点的后继结点数可以是④。 答：①前驱②1③后继④任意多个 (6)在图形结构中，每个结点的前驱结点数和后继结点数可以是 ()。 答：任意多个 (7)数据的存储结构主要有四种，它们分别是①、②、③和④存储结构。答：①顺序②链 式③索引④哈希 (8)一个算法的效率可分为① 效率和② 效率。 答：①时间②空间 3. 简答题 (1)数据结构和数据类型两个概念之间有区别吗？ 答：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素的集合。数据类型不仅定义了一组数据元素，而且还在其上定义了一组操作。 (2)简述线性结构、树形结构和图形结构的不同点。 答：线性结构反映结点间的逻辑关系是一对一的，树形线性结构反映结点间的逻辑关系是一对多的，图在结构反映结点间的逻辑关系是多对多的。 (3 )设有采用二元组表示的数据逻辑结构S=(D,R),其中D={ a,b, ?★}, R={(a,b),(a,c),(c,d),(c,f),(f,h),(d,e),(f,g),(h,i)}，问相对于关系R,哪些结点是开始结点,哪些结点是终端结点？ 答：该逻辑结构为树形结构，其中a结点没有前驱结点，称为根结点，b、e、g、i结点没有后继结点，是终端结点，也称为叶子结点。 (4) 以下各函数是算法中语句的执行频度，n为 练习 4 1.空间数据处理（融合、合并、剪切、交叉、合并） 2.设置地图投影及投影变换 空间数据处理 (1) 第1步裁剪要素 (2) 第2步拼接图层 (3) 第3步要素融合 (4) 第4步图层合并 (6) 第5步图层相交 (7) 定义地图投影 (9) 第6步定义投影 (9) 第7步投影变换――地理坐标系－>北京1954坐标系转换－>西安80坐标系 (10) 补充：图层相减，计算面积 (11) 空间数据处理 ●数据：云南县界.shp; Clip.shp西双版纳森林覆盖.shp 西双版纳县界.shp ●步骤： 将所需要的数据下载后，解压到到 e:\gisdata, 设定工作区:在ArcMap中 执行菜单命令：<工具>－><选项>，在“空间处理”选项页里，点 击“环境变量”按钮，在环境变量对话框 中的常规设置选项中，设定“临时工作空 间”为 e:\gisdata 第1步 裁剪要素 ◆在ArcMap中，添数据GISDATA\云南县界.shp，添加数据GISDATA\Clip.shp （Clip 中有四 个要素） ◆激活Clip图层。选中Clip图层中的一个要素，注意确保不要选中“云南县界”中的要素！ 点击打开ArcToolbox， 指定输出要素类路径及名称，这里请命名 为“云南县界_Clip1” 指定输入类：云南县界 指定剪切要素：Clip（必须是多边形要素） 依次选中Clip主题中其它三个要素，重复以上的操作步骤， 完成操作后将得到共四个图层（“云南县界_Clip1” , “云南县界_Clip2”，“云南县界_Clip3”，“云南县界_Clip4” ）。 第2步 拼接图层 ◆在ArcMap中新建地图文档，加载你在剪切要素操作中得到的 四个图层 ◆点击打开ArcToolbox 第四章空间数据与数据质量 空间数据是对现实世界对象(地理特征)的空间信息和专题属性信息描述，它具有诸如数据量巨大，结构复杂多样、操作是计算密集型的，具有自相关性等特征。空间数据是地理信息系统不可缺少的组成部分，其质量在很大程度上影响和制约着地理信息系统的可用性，为地理信息系统用户提供满足质量要求的空间数据是地理信息系统建设的关键任务之一。 4.1空间数据 4.1.1空间数据的来源 地理信息系统的数据源是指建立地理信息系统数据库所需要的各种类型数据的来源。地理信息系统的数据源是多种多样的，并随系统功能的不同而不同，通常包括以下几种： （1）地图数据：各种类型的地图是GIS最主要的数据源，因为地图是地理数据的传统描述形式，是具有共同参考坐标系统的点、线、面的二维平面形式的表示，内容丰富，图上实体间的空间关系直观，而且实体的类别或属性可以用各种不同的符号加以识别和表示。 （2）遥感数据：遥感数据是GIS中一个极其重要的信息源。通过遥感影象可以快速、准确地获得大面积的、综合的各种专题信息，航天遥感影象还可以取得周期性的资料，这些都为GIS提供了丰富的信息。 （3）测量数据：测量数据主要指使用大地测量、GPS、城市测量、摄影测量和其他一些测量方法直接量测所得到的测量对象的空间位置信息。各种实测数据特别是一些GPS点位数据、地籍测量数据常常是GIS的一个很准确和很现势的资料。（4）国民经济的各种统计数据常常也是GIS的数据源。如人口数量、人口构成、国民生产总值等等。各种文字报告和立法文件在一些管理类的GIS系统中，有很大的应用，如在城市规划管理信息系统中，各种城市管理法规及规划报告在规划管理工作中起着很大的作用。 4.1.2空间数据的基本特征 地理数据一般具有三个基本特征：属性特征（非定位数据）,描述空间对象的特性，即是什么，如对象的类别、等级、名称、数量等。空间特征（定位数据）：描述空间对象的地理位置以及相互关系，又称几何特征和拓扑特征，前者用经纬度、坐标表示，后者如交通学院与电力学院相邻等。时间特征（时间尺度）：指现象或物体随时间的变化，其变化的周期有超短期的、短期的、中期的、长期的《数据结构》实验报告
数据结构第1阶段练习题
数据结构课后习题及解析第四章
数据结构课程实验报告(15)
数据结构 习题
GIS原理与应用教案——第四章 空间数据的处理
严蔚敏数据结构c语言版习题集答案第四章串
数据结构实验报告--图实验
数据结构实验报告(图)
第4章数据结构与算法习题与答案
数据结构课程__课后习题答案
第四章 空间数据的处理及投影变换
空间数据与数据质量