2015海南省数据结构分析加强
1、给定n个村庄之间的交通图，若村庄i和j之间有道路，则将顶点i和j用边连接，边上的Wij表示这条道路的长度，现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短?试设计一个解答上述问题的算法，并应用该算法解答如图所示的实例。（20分）
2、矩阵中元素按行和按列都已排序，要求查找时间复杂度为O（m+n），因此不能采用常规的二层循环的查找。可以先从右上角（i=a,j=d）元素与x比较，只有三种情况：一是A[i,j]>x，这情况下向j 小的方向继续查找；二是A[i,j] void search(datatype A[ ][ ], int a,b,c,d, datatype x) //n*m矩阵A,行下标从a到b,列下标从c到d,本算法查找x是否在矩阵A中. {i=a; j=d; flag=0; //flag是成功查到x的标志 while(i<=b && j>=c) if(A[i][j]==x) {flag=1;break;} else if (A[i][j]>x) j--; else i++; if(flag) printf(“A[%d][%d]=%d”,i,j,x); //假定x为整型. else printf(“矩阵A中无%d 元素”，x)； }算法search结束。 [算法讨论]算法中查找x的路线从右上角开始，向下（当x>A[i,j]）或向左（当x 3、数组A和B的元素分别有序，欲将两数组合并到C数组，使C仍有序，应将A和B拷贝到C，只要注意A和B数组指针的使用，以及正确处理一数组读完数据后将另一数组余下元素复制到C中即可。 void union(int A[],B[],C[],m,n) //整型数组A和B各有m和n个元素，前者递增有序，后者递减有序，本算法将A和B归并为递增有序的数组C。 {i=0; j=n-1; k=0;// i，j，k分别是数组A,B和C的下标，因用C描述，下标从0开始while(i if(a[i] while(i while(j>=0) c[k++]=b[j--]; }算法结束 4、要求二叉树按二叉链表形式存储。15分 （1）写一个建立二叉树的算法。（2）写一个判别给定的二叉树是否是完全二叉树的算法。BiTree Creat() //建立二叉树的二叉链表形式的存储结构 {ElemType x；BiTree bt; scanf(“%d”,&x); //本题假定结点数据域为整型 if(x==0) bt=null; else if(x>0) {bt=(BiNode *)malloc(sizeof(BiNode)); bt->data=x; bt->lchild=creat(); bt->rchild=creat(); } else error(“输入错误”)； return(bt); }//结束 BiTree int JudgeComplete(BiTree bt) //判断二叉树是否是完全二叉树,如是，返回1，否则，返回0 {int tag=0; BiTree p=bt, Q[]; // Q是队列，元素是二叉树结点指针，容量足够大 if(p==null) return (1); QueueInit(Q); QueueIn(Q,p); //初始化队列，根结点指针入队 while (!QueueEmpty(Q)) {p=QueueOut(Q); //出队 if (p->lchild && !tag) QueueIn(Q,p->lchild); //左子女入队 else {if (p->lchild) return 0; //前边已有结点为空，本结点不空 else tag=1; //首次出现结点为空 if (p->rchild && !tag) QueueIn(Q,p->rchild); //右子女入队 else if (p->rchild) return 0; else tag=1; } //while return 1; } //JudgeComplete 4、设从键盘输入一整数的序列：a1, a2, a3，…，an,试编写算法实现：用栈结构存储输入的整数，当ai≠-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。算法应对异常情况（入栈满等）给出相应的信息。 设有一个背包可以放入的物品重量为S，现有n件物品，重量分别为W1，W2，...，Wn。问能否从这n件物品中选择若干件放入背包，使得放入的重量之和正好是S。设布尔函数Knap(S，n)表示背包问题的解，Wi(i=1,2,...，n)均为正整数，并已顺序存储地在数组W中。请在下列算法的下划线处填空，使其正确求解背包问题。 Knap(S，n) 若S=0 则Knap←true 否则若（S<0）或(S>0且n<1) 则Knap←false 否则若Knap(1) , _=true 则print(W[n])；Knap ←true 否则 Knap←Knap(2) _ , _ 设有一个顺序栈S，元素s1, s2, s3, s4, s5, s6依次进栈，如果6个元素的出栈顺序为s2, s3, s4, s6, s5, s1，则顺序栈的容量至少应为多少？画出具体进栈、出栈过程。 假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间。例如： 设str1和str2是分别指向两个单词的头结点，请设计一个尽可能的高效算法，找出两个单词共同后缀的起始位置，分析算法时间复杂度。 将n(n>1)个整数存放到一维数组R中。设计一个尽可能高效（时间、空间）的算 法，将R中保存的序列循环左移p（0 5、冒泡排序算法是把大的元素向上移（气泡的上浮），也可以把小的元素向下移（气泡的下沉）请给出上浮和下沉过程交替的冒泡排序算法。 48.有n个记录存储在带头结点的双向链表中，现用双向起泡排序法对其按上升序进行排序，请写出这种排序的算法。（注：双向起泡排序即相邻两趟排序向相反方向起泡） 6、请编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树用llink-rlink法存储。 7、有一种简单的排序算法，叫做计数排序（count sorting）。这种排序算法对一个待排序的表(用数组表示)进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键码互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键码比该记录的关键码小，假设针对某一个记录，统计出的计数值为c，那么，这个记录在新的有序表中的合适的存放位置即为c。 (1) (3分)给出适用于计数排序的数据表定义; (2) (7分)使用Pascal或C语言编写实现计数排序的算法； (3) (4分)对于有n个记录的表，关键码比较次数是多少? (4) (3分)与简单选择排序相比较，这种方法是否更好?为什么? 8、设一棵二叉树的结点结构为 (LLINK,INFO,RLINK),ROOT为指向该二叉树根结点的指针，p 和q分别为指向该二叉树中任意两个结点的指针，试编写一算法ANCESTOR（ROOT，p,q,r）,该算法找到p和q的最近共同祖先结点r。 9、已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={ 写出G的拓扑排序的结果。 G拓扑排序的结果是：V1、V2、V4、V3、V5、V6、V7 数据结构(本)期末综合练习(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年普通高中基础会考试卷 通用技术科试题 注意事项： 1．本试卷分为第一卷（选择题）和第二卷（非选择题）两部分，试卷共12页，满分100分，考试时间90分钟。答卷前，考生务必在试卷和答题卡指定位置填写本人姓名和准考证号，在答题卡粘贴条形码，所有试题都在答题卡上答题。2．选择题的答题，必须使用2B铅笔将所选项方框涂黑。若修改答案，应使用橡皮将错选项方框涂点擦干净，并将改选项方框涂黑。3．非选择题的答题，使用黑色签字笔在题号指定答题区域书写答案，在题号指定答题区域以外及草稿纸．试题卷上书的答案无效。 4．考试结束后，将本试卷和答题卡一并交回。 第一部分：选择题（26分） 本卷全部为单项选择题，共23题，每小题2分，分为通用技术科和信息技术科两部分。1—13题为通用技术科试题；14—23题为信息技术科试题。在每小题给出的四个选项中，只有一项符合题目要求。 1．汽车在行驶时，轮胎胎压过低，耗油量大；胎压过高，可能导致爆胎。行驶 中，不会 ．．受胎压影响的是（） A．汽车的行驶安全B．轮胎的使用寿命 C．汽车驾驶室的温度D．汽车的使用成本 2．有一种能显示轮胎胎压的车胎帽，该车胎帽顶部的圆环能随胎压大小而改变颜色。红色表示胎压太低；黄色表示胎压太高；而黑色表示胎压正常。针对该设 计，表述不恰当 ．．．的是（） A．实现了胎压过高或过低的预警 B．用颜色表示胎压，直观可见 C．可了解胎压大小的具体数值 D．结构简单，容易安装 3．利用3D打印技术打印出来的牙刷能根据每个人牙齿及牙床个性化定制。使用时，只需放在牙齿表面，用“咬”的方式刷牙，即可快速清洁牙齿。这种牙刷刷牙效率得到提高的主要原因是（） 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 年初中毕业生学业水平考试 数 学 科 试 题 （考试时间 100 分钟，满分 120 分） 一、选择题（本大题满分 42 分，每小题 3 分） 在下列各题的四个备选答案中，有且只有一个是正确的，请在答题卡上把你认为正确的 答案的字母代号按．要．求．用 2B 铅笔涂黑． 1．- 2015 的倒数是 A ．－ 1 B ． 2015 1 C ．- 2015 D ．2015 2015 2．下列运算中，正确的是 A ．a 2＋a 4= a 6 B ．a 6÷a 3=a 2 C ．(- a 4)2 = a 6 D ．a 2·a 4 = a 6 3．已知 x = 1，y = 2，则代数式 x - y 的值为 A ．1 B ．- 1 C ．2 D ．- 3 4．有一组数据：1、4、- 3、 3、4，这组数据的中位数为 A ．- 3 B ．1 C ．3 D ．4 5．图 1 是由 5 个完全相同的小正方体组成的几何体，则这个几何体的主视图是 正面 A B C D 图 1 6．据报道，2015 年全国普通高考报考人数约 9 420 000 人，数据 9 420 000 用科学记数法表 示为 9.42×10n ，则 n 的值是 A ．4 B ．5 C ．6 D ．7 7．如图 2，下列条件中，不．能． 证明△ABC ≌△DCB 的是 A D A ．A B =D C ，AC =DB C ．BO =CO ，∠A =∠D 3 2 B ．AB =D C ，∠ABC =∠DCB O D ．AB =DC ，∠A =∠D B C 8．方程 = x x - 2 的解为 图 2 A ．x = 2 B ．x = 6 C ．x = - 6 D ．无解 9．某企业今 年 1 月份产值为 x 万元，2 月份比 1 月份减少了 10%，3 月份比 2 月份增加了 15% 则 3 月份的产值是 A ．(1- 10%)(1+15%)x 万元 C ．(x - 10%)( x +15%)万元 B ．(1- 10%+15%)x 万元 D ．(1+10%- 15%)x 万元 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 2015年海南省高考英语试题（新课标II） 英语 本试卷分第Ⅰ卷（选择题）和第Ⅱ卷（非选择题）两部分。考试结束后，将本试卷和答题卡一并交回。 第Ⅰ卷 注意事项： 1. 答第Ⅰ卷前，考生务必将自己的姓名、准考证号填写在答题卡上。 2. 选出每小题答案后，用铅笔把答题卡上对应题目的答案标号涂黑。如需改动，用橡皮擦干净后，再选涂其他答案标号。不能答在本试卷上，否则无效。 第一部分听力（共两节，满分30分） 做题时，先将答案标在试卷上。录音内容结束后，你将有两分钟的时间将试卷上的答案转涂到答题卡上。 第一节（共5小题；每小题1.5分，满分7.5分） 听下面5段对话。每段对话后有一个小题，从试题所给的A、B、C三个选项中选出最佳选项，并标在试卷的相应位置。听完每段对话后，你都有10秒钟的时间来回答有关小题和阅读下一小题。每段对话仅读一遍。 例：How much is the shirt? A. ￡19.15 B. ￡9.18 C. ￡9.15 答案是C。 1.What time is it now? A. 9:10 B. 9:50 C. 10:00 2.What does the woman think of the weather? A. It’s nice B. It’s warm C. It’s cold 3.What will the man do? A. Attend a meeting B. Give a lecture C. Leave his office 4.What is the woman’s opinion about the course? A. Too hard B. Worth taking C. Very easy 5. What does the woman want the man to do ? A. Speak louder. B. Apologize to her. C. Turn off the radio. 第二节（共15小题；每小题1.5分，满分22.5分） 听下面5段对话或独白。每段对话或独白后有几个小题，从题中所给的A、B、C三个选项中选出最佳选项，并标在试卷的相应位置。听每段对话或独白前，你将有时间阅读各个小题，每小题5秒钟；听完后，各小题将给出5秒钟的作答 - 1 - 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年海南省公务员联考《行测》真题及答案 一、常识判断 1.下列雕塑作品表现唐太宗李世民生平战功的是： A.马踏匈奴 B.击鼓说唱俑 C.昭陵六骏 D.乾陵石雕 【知识点】中国古代史 【答案】 C 【解析】马踏匈奴石雕，突出表现在大型纪念性石刻和园林的装饰性雕刻上，是汉朝骠骑将军霍去病墓石刻，是留存至今的一组非常具有代表性的大型石雕作品。击鼓说唱俑是出土于四川成都市东汉墓，它代表了东汉陶俑的平实感人的生活气息和艺术风格。昭陵六骏是指陕西醴泉唐太宗李世民陵墓昭陵北面祭坛东西两侧的六块骏马青石浮雕石刻，反映唐太宗生平战功。唐代乾陵石雕刻，在今陕西乾县梁山，是唐高宗李治和武则天合葬陵墓前石雕群像。因此， 本题答案为C。 2.十八届三中全会通过《决定》对普通公民生活相关的是： ①高考不分文理科 ②“单独”生二胎 ③农村户口宅基地也可私有 ④延迟退休 A.①②③ B.②③④ D.①②③④ 【知识点】时政 【答案】 C 【解析】《中共中央关于全面深化改革若干重大问题的决定》明确规定，深化教育领域综合改革探索全国统考减少科目、不分文理科、外语等科目社会化考试一年多考。因此，如果要考大学，可能不必文理分科的说法正确。《决定》坚持计划生育的基本国策，启动实施一方是独生子女的夫妇可生育两个孩子的政策，逐步调整完善生育政策，促进人口长期均衡发展。因此，如果你是单独家庭，可以生育二胎的说法正确。《决定》建立更加公平可持续的社会保障制度。研究制定渐进式延迟退休年龄政策。加快健全社会保障管理体制和经办服务体系。因此，如果你是劳动者，那么可能可以延迟退休说法正确。《决定》加快构建新型农业经营体系。坚持农村土地集体所有权，依法维护农民土地承包经营权，发展壮大集体经济。因此，如果你是农村户口，那么宅基地可以私有的说法错误，宅基地属于农村集体所有土地。因此，本题答案为C。 3.中国古代小说塑造了很多莽汉形象，他们外表威猛如金刚，性格天真似儿童，深受读者的喜爱，下列小说莽汉的时代顺序排列正确的是： ①张飞②程咬金③李逵④牛皋 A.②①③④ B.②①④③ C.④②①③ D.①②③④ 【知识点】中国古代史数据结构(本)期末综合练习(2015年
数据结构实验报告
2015年海南省通用技术会考试题及答案
2015年南京邮电大学数据结构初试真题
数据结构实验报告(2015级)及答案
数据结构实验十一：图实验
2015年海南中考数学试题及答案word
北大2015年秋季学期数据结构课程作业
《数据结构》课程设计题目及要求2015
数据结构实验---图的储存与遍历
2015年海南省高考英语试题(新课标II)
2015年数据结构期末考试题及答案
数据结构实验指导手册(2015版)
数据结构实验报告图实验
(完整word版)2015年海南省中考语文试题及答案
数据结构习题集答案(C语言严版)
数据结构实验
2015年海南省公务员联考《行测》真题及答案.
- 数据结构习题集答案(C语言严版)
- 严蔚敏版数据结构课后习题答案-完整版
- 广州大学2015年数据结构考试
- 数据结构与算法课程设计报告格式-计算机学院2015级适用
- 数据结构 类Pascal版 严蔚敏 chapt9-兰州大学信息院
- 2015广工数据结构实验报告平衡二叉树
- 数据结构课程实习大纲-2015
- 数据结构(C语言版)(严蔚敏)
- 南审《数据结构课程教学设计》个人说明任务题目一览(2015年度版)
- 数据结构实验报告(2015级)
- 数据结构实验指导手册(2015版)
- 数据结构第一章习题答案
- 2015数据结构复习-C++版-学生
- 数据结构2015版严.pdf
- 严版数据结构习题集答案
- 数据结构复习重点归纳(适于清华严版教材)
- 严版数据结构知识点
- 山西省2015年专升本选拔考试(C程序设计数据结构)历年真题详解
- 数据结构课程设计指导(2015级)
- 数据结构课程设计题目汇总(2015级)