数据结构2015版严.pdf
数据结构(本)期末综合练习(2015年
数据结构(本)期末综合练习(2015年11月)
数据结构（本）期末综合练习 2015年11月 综合练习一 一、单项选择题 1.对稀疏矩阵进行压缩存储,可采用三元组 表，一个10 行8列的稀疏矩阵A共有73 个零元素，其相应的三元组表共有( C ) 个元素。 A．8 B．80 C．7 D．10 2. 对稀疏矩阵进行压缩存储,可采用三元组 表，一个10 行8列的稀疏矩阵A，其相应的 三元组表共有6个元素，矩阵A共有 ( C )个零元素。 A．8 B．72 C．74 D．10 3.字符串( A )是“abcd321ABCD”的子串。 A. “21AB” B. “abcD” C. “aBCD” D. “321a” 4. 程序段 char a[ ]=“abdcacdef”;
char *p=a; int n=0; while( *p!=‘\0’){ n++; p++;} 结果中,n 的值是（ D ）。 A. 6 B.8 C. 7 D.9 5.栈和队列的共同特点是（ A ）。 A．都是操作受限的线性结构 B．元 素都可以随机进出 C．都是先进后出 D．都是 先进先出 6. 10,6,2,1按顺序依次进栈，该队列的可 能输出序列是（ A ）。 (进栈出栈可以交替进行）。 A．6,10,1,2 B．2,10,6,1 C．6,1,10,1 D．1,6,10,2 7. 在一个链队中，假设f和r分别为队头 和队尾指针，p指向一个新结点,要为结点p 所指结点赋值x,并入队的运算为 p->data=x; p->next=NULL;（ B ）。 A. f->next=p; f=p; B． r->next=p;r=p; C．r=p; p->next=r;
数据结构实验报告
数据结构实验报告 一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include 2015年南京邮电大学数据结构考研初试题目 判断题（共15题*2分） 1.消除递归不一定需要使用栈，此说法() 2.稀疏矩阵压缩存储后，必会失去随机存取功能() 3.完全二叉树中，若一个结点没有左孩子，则它必是叶结点() 4.连通分量是无向图的极大强连通子图() 5.在9阶B-树中，除叶子以外的任意结点的分支数介于5和9之间() 6.在平衡二叉树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转() 7.10个叶子结点的哈弗曼树，其高度最小为58.队列和栈不可以使用散列存储() 选择题（共15题*2分） 1.以下属于逻辑结构的是（）。 A．顺序表B.哈希表 C.有序表 D.单链表 2.下列数据中，（）是非线性数据结构。 A．栈B.队列C.完全二叉树D.堆 3.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）储方式最节省运算时间。 A．单链表B．仅有头指针的单循环链表C．双链表D．仅有尾指针的单循环链表 4.循环队列存储在数组A[0..m]中，则入队时的操作为（）。 A.rear=rear+1 B.rear=(rear+1)mod(m-1) C.rear=(rear+1)mod m D.rear=(rear+1)mod(m+1) 5.二叉树在线索后，仍不能有效求解的问题是（）。 A.先序线索二叉树中求先序后继B．中序线索二叉树中求中序后继C．中序线索二叉树中求中序前驱D．后序线索二叉树中求后序后继6.下面几个符号串编码集合中，不是前缀编码的是（）。 A．{0,10,110,1111}B．{11,10,001,101,0001} C．{00,010,0110,1000} D．{b,c,aa,ac,aba,abb,abc} 7.用有向无环图描述表达式(A+B)*（（A+B）/A），至少需要顶点的数目为()。 A．5B．6C．8D．9 8.下列关于AOE网的叙述中，不正确的是（）。 A．关键活动不按期完成就会影响整个工程的完成时间 B．任何一个关键活动提前完成，那么整个工程将会提前完成 C．所有的关键活动提前完成，那么整个工程将会提前完成 D．某些关键活动提前完成，那么整个工程将会提前完成 9.m阶B-树是一棵() A.m叉排序树 B.m叉平衡排序树 C.m-1叉平衡排序树 D.m+1叉平衡排序树 10.关于杂凑查找说法不正确的有几个()【南京理工大学2000一、16（1.5分）】 A.采用链地址法解决冲突时，查找一个元素的时间是相同的 数据结构实验报告(2015级)及答案 《数据结构》实验报告 专业__信息管理学院______ 年级__2015级___________ 学号___ _______ 学生姓名___ _ _______ 指导老师____________ 华中师范大学信息管理系编 I 实验要求 1．每次实验中有若干习题，每个学生至少应该完成其中的两道习题。 2．上机之前应作好充分的准备工作，预先编好程序，经过人工检查无误后，才能上机，以提高上机效率。 3．独立上机输入和调试自己所编的程序，切忌抄袭、拷贝他人程序。 4．上机结束后，应整理出实验报告。书写实验报告时，重点放在调试过程和小节部分，总结出本次实验中的得与失，以达到巩固课堂学习、提高动手能力的目的。 II 实验内容 实验一线性表 【实验目的】 1．熟悉VC环境，学习如何使用C语言实现线性表的两种存储结构。 2．通过编程、上机调试，进一步理解线性表的基本概念,熟练运用C语言实现线性表基本操作。 3．熟练掌握线性表的综合应用问题。 【实验内容】 1．一个线性表有n个元素（n 的顺序不变。设计程序实现。要求：采用顺序存储表示实现；采用链式存储表示方法实现；比较两种方法的优劣。 2. 从单链表中删除指定的元素x，若x在单链表中不存在，给出提示信息。 要求： ①指定的值x由键盘输入； ②程序能处理空链表的情况。 3．设有头结点的单链表，编程对表中的任意值只保留一个结点，删除其余值相同的结点。 要求： ①该算法用函数（非主函数）实现； ②在主函数中调用创建链表的函数创建一个单链表， 并调用该函数，验证算法的正确性。 LinkedList Exchange（LinkedList HEAD，p）∥HEAD是单链表头结点的指针，p是链表中的一个结点。本算法将p所指结点与其后 继结点交换。 {q=head->next；∥q是工作指针，指向链表中当前待处理结点。 pre=head；∥pre是前驱结点指针，指向q的前驱。 while（q!=null && q!=p）{pre=q；q=q->next；} ∥ 一，实验题目 实验十一：图实验 采用邻接表存储有向图，设计算法判断任意两个顶点间手否存在路径。 二，问题分析 本程序要求采用邻接表存储有向图，设计算法判断任意两个顶点间手否存在路径，完成这些操作需要解决的关键问题是：用邻接表的形式存储有向图并输出该邻接表。用一个函数实现判断任意两点间是否存在路径。 1，数据的输入形式和输入值的范围：输入的图的结点均为整型。 2，结果的输出形式：输出的是两结点间是否存在路径的情况。 3，测试数据：输入的图的结点个数为：4 输入的图的边得个数为：3 边的信息为：1 2，2 3，3 1 三，概要设计 （1）为了实现上述程序的功能，需要： A，用邻接表的方式构建图 B，深度优先遍历该图的结点 C，判断任意两结点间是否存在路径 （2）本程序包含6个函数： a，主函数main（） b，用邻接表建立图函数create_adjlistgraph() c，深度优先搜索遍历函数dfs() d，初始化遍历数组并判断有无通路函数dfs_trave() e，输出邻接表函数print() f，释放邻接表结点空间函数freealgraph() 各函数间关系如右图所示： 四，详细设计 （1）邻接表中的结点类型定义： typedef struct arcnode{ int adjvex; arcnode *nextarc; }arcnode; （2）邻接表中头结点的类型定义： typedef struct{ char vexdata; arcnode *firstarc; }adjlist; （3）邻接表类型定义： typedef struct{ adjlist vextices[max]; int vexnum,arcnum; }algraph; （4）深度优先搜索遍历函数伪代码： int dfs(algraph *alg,int i,int n){ arcnode *p; visited[i]=1; p=alg->vextices[i].firstarc; while(p!=NULL) { if(visited[p->adjvex]==0){ if(p->adjvex==n) {flag=1; } dfs(alg,p->adjvex,n); if(flag==1) return 1; } p=p->nextarc; } return 0; } （5）初始化遍历数组并判断有无通路函数伪代码： void dfs_trave(algraph *alg,int x,int y){ int i; for(i=0;i<=alg->vexnum;i++) visited[i]=0; dfs(alg,x,y); } 五，源代码 #include "stdio.h" #include "stdlib.h" #include "malloc.h" #define max 100 typedef struct arcnode{ //定义邻接表中的结点类型 int adjvex; //定点信息 arcnode *nextarc; //指向下一个结点的指针nextarc }arcnode; typedef struct{ //定义邻接表中头结点的类型 char vexdata; //头结点的序号 arcnode *firstarc; //定义一个arcnode型指针指向头结点所对应的下一个结点}adjlist; typedef struct{ //定义邻接表类型 adjlist vextices[max]; //定义表头结点数组 2015年秋季学期《数据结构》课程作业 一. 单选题，每空有一个正确选择，请将正确的选择填在题号前边。（每空1分，共30分） 1.鼓励独立完成作业，严惩抄袭！数据的逻辑结构被形式地定义为B=(K,R),其中K 是 ____C__的有限集合，R是K上的___H___的有限集合。（第一章） a 存储 b 数据操作c数据元素d操作 e逻辑结构 f 映象 g算法h关系 2.以下关于算法的说法不正确的是____B _________。（第一章） a 一个算法应包含有限个步骤 b算法越简单越好 c算法中的所有操作都可以通过已经实现的基本操作运算有限次实现之 d算法中的每个步骤都能在有限时间内完成 3．设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03， 07>，<03，08>，<03，09>}，则数据结构A是______B________。（第一章） a 线性结构 b 树型结构 c 物理结构 d 图型结构 4.下面程序段的时间复杂度为___C___（第一章） int sum=0; for(i=0; i 一、关于本次课程设计 1、每位同学限选1题，并到所在自然班的班长处登记，同一题不超过4人（一个班之内）。 2、课程设计成绩分为5级：优秀（5分）、良好（4分）、中等（3分）、及格（2分）、不及格（1 分）。 3、题目有难易和工作量大小之分（具体见题目后的“星级”），为体现公平，请参见下表，请同学 们结合自身情况选择题目。 4、课程设计报告和源代码严禁抄袭，报告要严格遵照“课程设计任务书”的要求来撰写，大致包含 以下内容： ①需求分析：叙述每个模块的功能性要求； ②概要设计：阐述每个模块的算法设计（可以是描述算法的流程图）、使用的存储结构（如 果指定存储结构请写出该存储结构的struct或typedef定义）； ③详细设计：各个算法的实现源代码（注意只写算法的源代码，完整的源代码放在附录里面）。 源代码必须正确缩进，关键性代码（如关键变量/ 参数/ 语句的意义、每个函数的功能等）要给出清楚的中文注释； ④调试分析：需要测试数据的至少给出3组测试数据，记录每一组数据输出的结果；并用文 字描述调试过程中遇到的问题（问题是哪些？问题如何得以解决？）； ⑤课设总结：课程设计过程的收获、遇到的问题、解决问题过程的思考、程序调试能力的思 考、对数据结构这门课程的思考等内容（严禁套话）； ⑥附录：完整的源代码（必须正确缩进）。 5、程序运行时，要有友好的说明界面和操作提示菜单（以英文文字显示即可），严禁出现“一运 行屏幕一片黑”的情形；程序要有良好的容错性，当输入数据不合理或非法，程序必须能处理之并显示友好的提示信息而不能崩溃。 二、可选题目 1、一元多项式计算器（★★） 问题描述：创建两个一元多项式A和B，计算A+B, A-B, A*B并显示。多项式的项数和每一项的系数/指数在运行时指定。 2、航空订票系统（★★★★） 问题描述：编写程序模拟航空订票系统，要求实现以下功能： ①允许增、删、改航班信息，包括“航班号/ 机型/ 起降城市/ 起降时间/ 座位数/ 票价等”（所有航班 信息存储在数据文件中，数据结构自定义）； ②允许以“航班号/ 起降城市” 等条件查询航班信息； ③订票：无票时应能提供相关可选择的航班以继续操作（订票数据存储在数据文件中）。 ④退票：退票后应修改相关数据文件。 3、迷宫问题（★★） 问题描述：迷宫以16*16的矩阵存储在数据文件中（迷宫中的障碍物要占到一定比例），编写非递归的程序求出一条从入口到出口的路径并显示之（若能用TC的绘图函数显示迷宫和路径则另加1分）。 4、约瑟夫环问题（★★★） 问题描述：编号是1，2，……，N的N个人按照顺时针方向围坐一圈，每个人持有一个密码（一个正整数）。一开始任选一个正整数作为报数上限值M，从第一个人开始顺时针方向自1开始顺序报数，报到M时停止报数。报M的人出列，并将他持有的密码作为新的M值，再从他的顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。编写程序求出列顺序（采用单循环链表实现，N、M、每个人的密码均在运行时指定）。 5、二叉树的创建和遍历（★★） 问题描述：根据运行时输入的先序序列创建一棵二叉树，分别对其进行先、中、后、层序遍历并显示遍历结果。 6、算术表达式的求值（★★★） 问题描述：若干个算数表达式存放在数据文件中（每行一个），形如“（6+6）*6+2-3*（2.4/6）”，编写程序计算每个表达式的值（算法参见清华的中文版教材第三章）。 7、二叉查找树的创建、查找、插入和删除（★★★） 问题描述：运行时产生若干个随机整数，依次插入到一棵初始为空的二叉查找树中，并能在其中查找、插入、删除指定的整数。 数据结构实验---图的储存与遍历 学号： 姓名： 实验日期： 2016.1.7 实验名称： 图的存贮与遍历 一、实验目的 掌握图这种复杂的非线性结构的邻接矩阵和邻接表的存储表示，以及在此两种常用存储方式下深度优先遍历(DFS)和广度优先遍历(BFS)操作的实现。 二、实验内容与实验步骤 题目1：对以邻接矩阵为存储结构的图进行DFS 和BFS 遍历 问题描述：以邻接矩阵为图的存储结构，实现图的DFS 和BFS 遍历。 基本要求：建立一个图的邻接矩阵表示，输出顶点的一种DFS 和BFS 序列。 测试数据：如图所示 题目2：对以邻接表为存储结构的图进行DFS 和BFS 遍历 问题描述：以邻接表为图的存储结构，实现图的DFS 和BFS 遍历。 基本要求：建立一个图的邻接表存贮，输出顶点的一种DFS 和BFS 序列。 测试数据：如图所示 V0 V1 V2 V3 V4 三、附录： 在此贴上调试好的程序。 #include #define M 100 typedef struct node { char vex[M][2]; int edge[M ][ M ]; int n,e; }Graph; int visited[M]; Graph *Create_Graph() { Graph *GA; int i,j,k,w; GA=(Graph*)malloc(sizeof(Graph)); printf ("请输入矩阵的顶点数和边数(用逗号隔开)：\n"); scanf("%d,%d",&GA->n,&GA->e); printf ("请输入矩阵顶点信息：\n"); for(i = 0;i 2012年数据结构期末考试题及答案 一、选择题 1．在数据结构中，从逻辑上可以把数据结构分为C。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指A。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的A结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储C。 A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑A。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是D。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是C，算法分析的两个主要方面是A。 （1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系 C．分析算法的效率以求改进C．分析算法的易读性和文档性 （2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O（n2）。 s ＝0； for（I ＝0；i＜n；i＋＋） for（j＝0；j＜n；j＋＋） s ＋＝B[i][j]； sum ＝s ； 9．下面程序段的时间复杂度是O（n*m）。 for（i ＝0；i＜n；i＋＋） for（j＝0；j＜m；j＋＋） A[i][j] ＝0； 10．下面程序段的时间复杂度是O（log3n）。 i ＝0； while（i＜＝n） i ＝i * 3； 11．在以下的叙述中，正确的是B。 A．线性表的顺序存储结构优于链表存储结构 B．二维数组是其数据元素为线性表的线性表 C．栈的操作方式是先进先出 D．队列的操作方式是先进后出 12．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着B 。 A．数据元素具有同一特点 B．不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等 13．链表不具备的特点是A。 A．可随机访问任一结点B．插入删除不需要移动元素 C．不必事先估计存储空间D．所需空间与其长度成正比 14．不带头结点的单链表head为空的判定条件是A。 五邑大学计算机学院 数据结构实验指导手册 2015年3月 目录 实验一线性表 (1) 1．实验目的 (1) 2．实验内容 (1) 3．解题思路 (1) 实验二栈 (4) 1．实验目的 (4) 2．实验内容 (4) 3．解题思路 (4) 实验三队列 (8) 1．实验目的 (8) 2．实验内容 (8) 3．解题思路 (8) 实验四二叉树 (12) 1．实验目的 (12) 2．实验内容 (12) 3．解题思路 (12) 实验五哈夫曼树 (18) 1．实验目的 (18) 2．实验内容 (18) 3．解题思路 (18) 实验六图的基本存储 (21) 1．实验目的 (21) 2．实验内容 (21) 3．解题思路 (21) 实验七图的应用 (26) 1．实验目的 (26) 2．实验内容 (26) 3．解题思路 (26) 实验八查找 (30) 1．实验目的 (30) 2．实验内容 (30) 3．解题思路 (30) 实验九排序 (32) 1．实验目的 (32) 2．实验内容 (32) 3．解题思路 (32) 说明 (36) 附录实验报告模板 (37) 实验一线性表 1．实验目的 （1）了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系有顺序存储结构和链式存储结构； （2）掌握这两种存储结构的描述方法； （3）掌握线性表的基本操作（查找、插入、删除）； （4）考虑时间和空间复杂度设计算法。 2．实验内容 （1）创建一个顺序表，存放在数组A[N]中，元素的类型为整型，设计算法调整A，使其左边的所有元素小于0，右边的所有元素大于0（要求算法的时间复杂度和空间复杂度均为O(n)）。 （2）建立一个循环单链表，其节点有prior，data和next三个域，其中data为数据域，存放元素的有效信息，next域为指针域，指向后继节点，prior为指针域，它的值为NULL。编写一个算法将此表改为循环双链表。 3．解题思路 （1）如图1-1所示，设立两个工作指针i和j，i由数组的左端向右移动，查找大于等于0的数，j由数组的右端向左端移动，查找小于0的数，然后交换，如图1-2所示，直到i>=j，调整结束。 图1-1 邻接矩阵的实现 1. 实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现2. 实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历3．设计与编码MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template int vertexNum, arcNum; }; #endif MGraph.cpp #include 1.1解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 解： 1.4 解：ADT Complex{ 数据对象：D={r,i|r,i为实数} 数据关系：R={ 实验1 (C语言补充实验) 有顺序表A和B,其元素值均按从小到大的升序排列，要求将它们合并成一 个顺序表C,且C的元素也是从小到大的升序排列。 #include 求A QB #include 数据结构（本）期末综合练习 2015年11月 综合练习一 一、单项选择题 1.对稀疏矩阵进行压缩存储,可采用三元组表，一个10 行8列的稀疏矩阵A共有73 个零元素，其相应的三元组表共有( C )个元素。 A．8 B．80 C．7 D．10 2. 对稀疏矩阵进行压缩存储,可采用三元组表，一个10 行8列的稀疏矩阵A，其相应的 三元组表共有6个元素，矩阵A共有( C )个零元素。 A．8 B．72 C．74 D．10 3.字符串( A )是“abcd321ABCD”的子串。 A. “21AB” B. “abcD” C. “aBCD” D. “321a” 4. 程序段 char a[ ]=“abdcacdef”; char *p=a; int n=0; while( *p!=‘\0’){ n++; p++;} 结果中,n的值是（ D ）。 A. 6 B.8 C. 7 D.9 5.栈和队列的共同特点是（ A ）。 A．都是操作受限的线性结构 B．元素都可以随机进出 C．都是先进后出 D．都是先进先出 6. 10,6,2,1按顺序依次进栈，该队列的可能输出序列是（ A ）。 (进栈出栈可以交替进行）。 A．6,10,1,2 B．2,10,6,1 C．6,1,10,1 D．1,6,10,2 7. 在一个链队中，假设f和r分别为队头和队尾指针，p指向一个新结点,要为结点p 所指结点赋值x,并入队的运算为p->data=x; p->next=NULL;（ B ）。 A. f->next=p; f=p; B． r->next=p;r=p; C． r=p; p->next=r; D． p->next=f;f=p; 8. 对一个栈顶指针为top的链栈进行出栈操作，用变量e保存栈顶元素的值，则执行 ( B ）。 A．e= top->next; top->data=e; B．e=top->data; top=top->next; C．top=top->next; e=top->data; D．top=top->next; e=data; 9. 数据结构中，与所使用的计算机无关的是数据的( A ) 结构。 A.逻辑 B.存储 C.逻辑与存储 D.物理 10. 算法的时间复杂度与( A )有关。 A. 算法本身 B. 所使用的计算机 C. 算法的程序设计 D. 数据结构 11．顺序表所具备的特点之一是（ A ）。 图实验 一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template 数据结构教程 上机实验报告 实验七、图算法上机实现 一、实验目的： 1.了解熟知图的定义和图的基本术语，掌握图的几种存储结构。 2.掌握邻接矩阵和邻接表定义及特点，并通过实例解析掌握邻接 矩阵和邻接表的类型定义。 3.掌握图的遍历的定义、复杂性分析及应用，并掌握图的遍历方 法及其基本思想。 二、实验内容： 1.建立无向图的邻接矩阵 2.图的深度优先搜索 3.图的广度优先搜索 三、实验步骤及结果： 1.建立无向图的邻接矩阵： 1)源代码： #include "" #include "" #define MAXSIZE 30 typedef struct { char vertex[MAXSIZE]; ertex=i; irstedge=NULL; irstedge; irstedge=p; p=(EdgeNode*)malloc(sizeof(EdgeNode)); p->adjvex=i; irstedge; irstedge=p; } } int visited[MAXSIZE]; ertex); irstedge; ertex=i; irstedge=NULL; irstedge;irstedge=p; p=(EdgeNode *)malloc(sizeof(EdgeNode)); p->adjvex=i; irstedge; irstedge=p; } } typedef struct node { int data; struct node *next; }QNode; ertex); irstedge;ertex); //输出这个邻接边结点的顶点信息 visited[p->adjvex]=1; //置该邻接边结点为访问过标志 In_LQueue(Q,p->adjvex); //将该邻接边结点送人队Q } 数据结构试题 一、单选题 1、在数据结构的讨论中把数据结构从逻辑上分为（） A 内部结构和外部结构 B 静态结构和动态结构 C 线性结构和非线性结构 D 紧凑结构和非紧凑结构。 2、采用线性链表表示一个向量时，要求占用的存储空间地址（） A 必须是连续的 B 部分地址必须是连续的 C 一定是不连续的 D 可连续可不连续 3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（）。 A n B n/2 C (n-1)/2 D (n+1)/2 4、在一个单链表中，若q结点是p结点的前驱结点，若在q和p之间插入结点s，则执行（）。 A s→link= p→link;p→link= s; B p→link = s; s→link = q; C p→link= s→link;s→link= p; D q→link = s;s→link = p; 5、如果想在4092个数据中只需要选择其中最小的5个，采用（）方法最好。 A 起泡排序 B 堆排序 C 锦标赛排序 D 快速排序 6、设有两个串t和p，求p在t中首次出现的位置的运算叫做（）。 A 求子串 B 模式匹配 C 串替换 D 串连接 7、在数组A中，每一个数组元素A[i][j]占用3个存储字，行下标i从1到8，列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储字数是（）。 A 80 B 100 C 240 D 270 8、将一个递归算法改为对应的非递归算法时，通常需要使用（）。 A 栈 B 队列 C 循环队列 D 优先队列 9、一个队列的进队列顺序是1, 2, 3, 4， 第二章线性表 顺序表的操作 1、顺序表的建立（从键盘或者数组中导入数据） Status InitList(SqList &L) { //构造一个空的顺序表 L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!L.elem) exit(OVERFLOW); L.length=0; L.listsize=LIST_INIT_SIZE; return OK; } 2、顺序表按照值查找位置 int LocateElem(SqList L, ElemType e) { //根据数据元素的值，返回它在线性表L中的位置 int i=0; while ((i<=L.length)&&(*(L.elem+i-1)!=e)) i++; if (i<=L.length) return i; else return(-1); } 3、顺序表按照序号查找元素的值 Status GetElem(SqList L,int i,ElemType &e) { //根据数据元素在线性表L中的位置，返回它的值 if(i<1||i>L.length ) return ERROR; e=*(L.elem+i-1); return OK; } 4、顺序表数据元素的插入 Status ListInsert(SqList &L,int i,ElemType e) { // 在L中第i个位置之前插入新的数据元素e，L的长度加1 ElemType *p,*q,*newbase; if(i<1||i>L.length+1) return ERROR; if(L.length>=L.listsize) {newbase=(ElemType *)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof(ElemType)); if(!newbase)exit(OVERFLOW); 2015年lO月高等教育自学考试全国统一命题考试 数据结构试卷 (课程代码02331) 本试卷共8页。满分l00分。考试时间l50分钟。 考生答题注意事项： 1．本卷所有试题必须在答题卡上作答。答在试卷上无效，试卷空白处和背面均可作草稿纸. 2．第一部分为选择题。必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑。 3．第二部分为非选择题。必须注明大、小题号，使用0．5毫米黑色字迹签字笔作答。 4．合理安排答题空间．超出答题区域无效。 第一部分选择题 一、单项选择题(本大题共l5小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题卡” 的相应代码涂黑。未涂、错涂或多涂均无分。 1．下列选项中，不属于线性结构的是 A．网 B．栈 C．队列 D．线性表 2．长度为n的顺序表，删除位置i上的元素(0≤i≤n一1)，需要移动的元素个数为 A．n—i B．n—i—l C．i D．i+1 3．栈采用不同的存储方式时，下列关于出栈过程的叙述中，正确的是 A．顺序栈需要判定栈空，链栈也需要判定 B．顺序栈需要判定栈空，而链栈不需要判定 C．顺序栈不需要判定栈空，而链栈需要判定 D．顺序栈不需要判定栈空，链栈也不需要判定 4．若一个栈以数组V[0．．n-1]存储，初始栈顶指针top为n，则x入栈的正确操作是 A．top=top+1；V[top]=x B．V[top]=x；top=top+1 C．top=top一1；V[mp]=x D．V[top]=x；top=top—l 5．在二维数组a[9][10]中：每个数组元素占用3个存储空间，从首地址SA开始按行优先 连续存放，则元素a[8][5]的起始地址是 A．SA+141 B．SA+144 C．SA+222 D．SA+255 6．广义表A=(x，((y)，((a))，A))的深度是 A．2 B．3 C．4 D．∞2015年南京邮电大学数据结构初试真题
数据结构实验报告(2015级)及答案
数据结构实验十一：图实验
北大2015年秋季学期数据结构课程作业
《数据结构》课程设计题目及要求2015
数据结构实验---图的储存与遍历
2015年数据结构期末考试题及答案
数据结构实验指导手册(2015版)
数据结构实验报告图实验
数据结构习题集答案(C语言严版)
数据结构实验
数据结构(本)期末综合练习(2015年11月)
数据结构实验报告图实验
数据结构图实验报告
2015(1)年度中国石油大学数据结构试题及答案
南审《数据结构课程设计》个人任务题目一览(2015版)
2015年10月自考数据结构试题及答案解析
- 2015数据结构复习-C++版-学生
- 严版数据结构前7章习题答案.doc汇总
- 北京科技大学2015年数据结构与算法分析试卷+答案
- 数据结构实验报告(2015级)及答案
- 第二炮兵工程大学考研试题843数据结构(2015年~2016年)
- 南审《数据结构课程设计》个人任务题目一览(2015版)
- 数据结构实验指导书(2015版)
- 2015版数据结构课程设计 (1)
- 数据结构(C语言版)第2章习题答案
- 数据结构习题集答案(C语言严版)
- 严蔚敏版数据结构课后习题答案-完整版
- 广州大学2015年数据结构考试
- 数据结构与算法课程设计报告格式-计算机学院2015级适用
- 数据结构 类Pascal版 严蔚敏 chapt9-兰州大学信息院
- 2015广工数据结构实验报告平衡二叉树
- 数据结构课程实习大纲-2015
- 数据结构(C语言版)(严蔚敏)
- 南审《数据结构课程教学设计》个人说明任务题目一览(2015年度版)
- 数据结构实验报告(2015级)
- 数据结构实验指导手册(2015版)