数据结构 串与模式匹配
常熟理工学院
《数据结构与算法》实验指导与报告书
_2017-2018_____学年第__1__ 学期
专业：物联网工程
实验名称：串与模式匹配
实验地点： N6-210 指导教师：聂盼红
计算机科学与工程学院
2017
实验四串与模式匹配
【实验目的】
1、掌握串的存储表示及基本操作；
2、掌握串的两种模式匹配算法：BF和KMP。
3、了解串的应用。
【实验学时】
2学时
【实验预习】
回答以下问题：
1、串和子串的定义
串：串是由零个或多个任意字符组成的有限序列。
子串：串中任意连续字符组成的子序称为该串的字串。
2、串的模式匹配
串的模式匹配是数据结构中字符串的一种基本运算，给定一个子串，要求在某个字符串中找出与该子串相同的所有子串，这就是模式匹配。假设P是给定的子串，T是待查找的字符串，要求从T中找出与P相同的所有子串，这个问题成为模式匹配问题。P称为模式，T 称为目标。如果T中存在一个或多个模式为P的子串，就给出该子串在T中的位置，称为匹配成功；否则匹配失败
【实1
验内容和要求】/
1、按照要求完成程序exp4_1.c，实现串的相关操作。调试并运行如下测试数据给出运行结果：
?求“This is a boy”的串长；
?比较”abc 3”和“abcde“； 表示空格
?比较”english”和“student“；
?比较”abc”和“abc“；
?截取串”white”，起始2，长度2；
?截取串”white”，起始1，长度7；
?截取串”white”，起始6，长度2；
?连接串”asddffgh”和”12344”；
实验代码：
#include
#include
#define MAXSIZE 100
#define ERROR 0
#define OK 1
/*串的定长顺序存储表示*/
typedef struct
{
char data[MAXSIZE];
int length;
} SqString;
int strInit(SqString *s); /*初始化串*/
int strCreate(SqString *s); /*生成一个串*/ int strLength(SqString *s); /*求串的长度*/ int strCompare(SqString *s1,SqString *s2); /*两个串的比较*/ int subString(SqString *sub,SqString *s,int pos,int len); /*求子串*/
int strConcat(SqString *t,SqString *s1,SqString *s2); /*两个串的连接*/
/*初始化串*/
int strInit(SqString *s)
{
s->length=0;
s->data[0]='\0';
return OK;
}/*strInit*/
/*生成一个串*/
int strCreate(SqString *s)
{
printf("input string :");
gets(s->data);
s->length=strlen(s->data);
return OK;
}/*strCreate*/
/*（1）---求串的长度*/
int strLength(SqString *s)
{
return s->length;
}/*strLength*/
/*（2）---两个串的比较，S1>S2返回>0，s1 int strCompare(SqString *s1,SqString *s2) { int i; for(i=0; i if(s1->data[i] != s2->data[i]) return s1->data[i] - s2->data[i]; return s1->length - s2->length; }/*strCompare*/ /*（3）---求子串，sub为返回的子串，pos为子串的起始位置，len为子串的长度*/ int subString(SqString *sub,SqString *s,int pos,int len) { int i; if(pos<1 || pos>s->length || len<0 || len>s->length-pos+1) return ERROR; sub->length = 0; for(i=0; i sub->data[i] = s->data[i+pos-1]; sub->length++; } sub->data[i] = '\0'; return OK; }/*subString*/ /*（4）---两个串连接，s2连接在s1后，连接后的结果串放在t中*/ int strConcat(SqString *t,SqString *s1,SqString *s2) { int i=0, j=0; while(i t->data[i] = s1->data[i]; i++; } while(j t->data[i++] = s2->data[j++]; t->data[i] = '\0'; t->length = s1->length + s2->length; return OK; }/*strConcat*/ int main() { system("color 1f"); int n,k,pos,len; SqString s,t,x; do { printf("\n ---String--- \n"); printf(" 1. strLentgh\n"); printf(" 2. strCompare\n"); printf(" 3. subString\n"); printf(" 4. strConcat\n"); printf(" 0. EXIT\n"); printf("\n ---String---\n"); printf("\ninput choice:"); scanf("%d",&n); getchar(); switch(n) { case 1: printf("\n***show strLength***\n"); strCreate(&s); printf("strLength is %d\n",strLength(&s)); break; case 2: printf("\n***show strCompare***\n"); strCreate(&s); strCreate(&t); k=strCompare(&s, &t); /*（5）---调用串比较函数比较s，t*/ if(k==0) printf("two string equal!\n"); else if(k<0) printf("first string else printf("first string>second string!\n"); break; case 3: printf("\n***show subString***\n"); strCreate(&s); printf("input substring pos,len:"); scanf("%d,%d",&pos,&len); if(subString(&t,&s,pos,len)) printf("subString is %s\n",t.data); else printf("pos or len ERROR!\n"); break; case 4: printf("\n***show subConcat***\n"); strCreate(&s); strCreate(&t); if(strConcat(&x, &s, &t)) /*（6）---调用串连接函数连接s&t*/ printf("Concat string is %s",x.data); else printf("Concat ERROR!\n"); break; case 0: exit(0); default: break; } } while(n); return 0; } 2、按照要求完成程序exp4_2.c，实现BF&KMP串的模式匹配算法。调试及测试数据并给出结果： ?应用BF算法求子串”JING”在主串”BEIJING”中的位置，测试起始位置分别为1和5的情况； ?应用KMP算法求子串”abaabcac”在主串”acabaabaabcacaabc”中的位置，测试起始位置分别为1，10的情况，并写出子串的next[]值； exp4_2.c部分代码如下： #include #include #define MAXSIZE 100 #define ERROR 0 #define OK 1 /*串的定长顺序存储表示*/ typedef struct { char data[MAXSIZE]; int length; } SqString; int strCreate(SqString *s); int indexBf(SqString *s,SqString *t,int pos); /*串的模式匹配BF*/ void getNext(SqString *t,int next[]); /*KMP求next值*/ int indexKmp(SqString *s,SqString *t,int start,int next[]); /*串的模式匹配KMP*/ /*生成一个串*/ int strCreate(SqString *s) { printf("input string :"); gets(s->data); s->length=strlen(s->data); return OK; }/*strCreate*/ /*（1）---串的模式匹配BF*/ int indexBf(SqString *s,SqString *t,int pos) { int i = pos-1, j = 0; while(i if(s->data[i] == t->data[j]){ i++; j++; } else{ i = i - j +1; j = 0; } if(j >= t->length) return i - t->length+1; else return 0; }/*index_bf*/ /*（2）---KMP求next值*/ void getNext(SqString *t,int next[]) { int i = 0, j = -1; next[0] = -1; while(i < t->length){ if((j==-1) || (t->data[i]==t->data[j])){ i++; j++; next[i] = j; } else j = next[j]; } }/*getNext*/ /*（3）---KMP模式匹配*/ int indexKmp(SqString *s,SqString *t,int start,int next[]) { int i = start - 1, j = 0; while(i if(j==-1 || s->data[i]==t->data[j]){ i++; j++; } else j = next[j]; if(j >= t->length) return i - t->length+1; else return 0; }/*index_kmp*/ int main() { system("color 1f"); int n,i,pos,next[MAXSIZE]; SqString s,t; do { printf("\n ---String--- \n"); printf(" 1. Index_BF\n"); printf(" 2. INdex_KMP\n"); printf(" 0. EXIT\n"); printf("\n ---String---\n"); printf("\ninput choice:"); scanf("%d",&n); getchar(); switch(n) { case 1: printf("\n***show Index_BF***\n"); printf(" s:"); strCreate(&s); printf(" t:"); strCreate(&t); printf("input start position:"); scanf("%d",&pos); printf("BF:index is %d\n",indexBf(&s,&t,pos)); break; case 2: printf("\n***show Index_KMP***\n"); printf(" s:"); strCreate(&s); printf(" t:"); strCreate(&t); printf("input start position:"); scanf("%d",&pos); getNext(&t,next); printf("KMP:\n"); printf("next[]:"); for(i=0; i printf("%3d",next[i]); printf("\n"); printf("index is %d\n",indexKmp(&s,&t,pos,next)); break; case 0: exit(0); default: break; } } while(n); return 0; } 【实验小结】 通过这次实验，我在其中遇到了很多问题。比如掌握了串的存储表示及基本操作，认识到事情的解决有很多方式。比如求next的值就BF算法以及KMP算法。两种算法时间复杂度一个是线性的一个是非线性的，运行起的效率就会明显不一样。所以认识问题要全面，就觉问题要多考虑。并且还了解了串的应用，对这种结构有了更深一步的认识。 天津大学数据结构和程序设计考研真题-考研资料- 笔记讲义 许多学生在考研复习的时候,都会遇到重点不明确,不知道从何复习的情况。为此,天津考研网建议,考研复习中,专业的考研复习资料,是帮助考生能够快速掌握复习重点及方法必不可少的因素,然后就是真题和讲义,可以让同学了解历年考研的出题方向和大致范围。天津考研网推出了天津大学数据结构和程序设计的考研复习资料及真题解析班,以下为详细介绍: 天津大学数据结构和程序设计考研真题等资料由天津考研网签约的天津大学计算机科学与技术学院高分考研学生历时近一月所作,该考生在考研中取得了专业课129分的好成绩并在复试中更胜一筹,该资料包含该优秀本校考生的考研经验、考研试题解题思路分析、复试流程经验介绍以及针对官方指定参考书的重难要点并根据天津大学本科授课重点整理等,从漫漫初试长路到紧张复试亮剑为各位研友提供全程考研指导攻关。 特别说明:此科目06年以前科目名称为数据结构;自06年到08年科目名称改为计算机基础(包含数据结构、程序设计、计算机原理);自09年开始全国统考,科目名称为计算机学科专业基础综合;自2013年开始由学校自主命题,科目名称改为901数据结构与程序设计。 第一部分由天津考研网提供的核心复习资料: 天津大学数据结构和程序设计资料编者序言:本文的重点在于C++,数据结构的复习和复试基本情况介绍。C++、数据结构又分别从复习规划,复习用书,重点知识点结合历年考题这四个方面来展开的。复习规划大家务必看一下,然后根据自己的实际情况在制定自己的复习时间,因为内容很多,大多数同学都在考试之前复习不完,在心理因素上就落了一节。重点知识点一定要看了,这些知识点几乎每年都会有题了。另外我还给了历年试题的答案供大家参考。有的答案是自己做的答案,可能会有疏忽的地方。望大家提出宝贵的意见和建议。复试的东西现在了解一下即可,等到进复试了,还是有足够的时间看的。另外我还给了些自己复习心得。考完后感慨很多,回顾了这多半年来自己的成败得失。希望大家从一开始就沿着比较高效的方向前进,减少不必要时间的浪费。本资料格式为A4纸打印版,总量达到了130页 《数据结构与算法设计》 实验报告 ——实验二 学院：自动化学院 班级： 学号： ： 一、实验目的 按照四则运算加、减、乘、除、幂（^）和括号的优先关系和惯例，编写计算器程序。 二、实验容 简单计算器。 请按照四则运算加、减、乘、除、幂（^）和括号的优先关系和惯例，编写计算器程序。要求： ①从键盘输入一个完整的表达式，以回车作为表达式输入结束的标志。 ②输入表达式中的数值均为大于等于零的整数。中间的计算过程如果出现小数也只取 整。 例如，输入：4+2*5= 输出：14 输入：(4+2)*(2-10)= 输出：-48 三、程序设计 概要设计 1、宏定义 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 2、基本函数： （1）void InitStack_char(SqStack *S) //char型栈初始化 （2）void InitStack_int(sqStack *S) //int型栈初始化 （3）void Push_char(SqStack *S,char ch) //char型元素进栈 （4）void Push_int(sqStack *S,int num) //int型元素进栈 （5）char GetTop_char(SqStack *S) //取char型栈顶元素 （6）int GetTop_int(sqStack *S) //取int型栈顶元素 （7）Status In(char c) //判断是否为运算符，若是运算符则返回，否则返回 （8）char Precede(char a,char b) //判断两运算符的先后次序 （9）Status Pop_char(SqStack *S,char &x) //char型栈出栈 （10）Status Pop_int(sqStack *S,int &x) //int型栈出栈 （11）int Operate(int a,char theta,int b) //计算a和b运算结果 3、流程图 相对于结构化数据(即行数据,存储在数据库里,可以用二维表结构来逻辑表达实现的数据)而言,不方便用数据库二维逻辑表来表现的数据即称为非结构化数据,包括所有格式的办公文档、文本、图片、XML、HTML、各类报表、图像和音频/视频信息等等。 字段可根据需要扩充，即字段数目不定，可称为半结构化数据，例如Exchange存储的数据。 非结构化数据库 在信息社会，信息可以划分为两大类。一类信息能够用数据或统一的结构加以表示，我们称之为结构化数据，如数字、符号；而另一类信息无法用数字或统一的结构表示，如文本、图像、声音、网页等，我们称之为非结构化数据。结构化数据属于非结构化数据，是非结构化数据的特例 数据清洗从名字上也看的出就是把“脏”的“洗掉”。因为数据仓库中的数据是面向某一主题的数据的集合，这些数据从多个业务系统中抽取而来而且包含历史数据，这样就避免不了有的数据是错误数据、有的数据相互之间有冲突，这些错误的或有冲突的数据显然是我们不想要的，称为“脏数据”。我们要按照一定的规则把“脏数据”“洗掉”，这就是数据清洗.而数据清洗的任务是过滤那些不符合要求的数据，将过滤的结果交给业务主管部门，确认是否过滤掉还是由业务单位修正之后再进行抽取。不符合要求的数据主要是有不完整的数据、错误的数据、重复的数据三大类。 (1)不完整的数据 这一类数据主要是一些应该有的信息缺失，如供应商的名称、分公司的名称、客户的区域信息缺失、业务系统中主表与明细表不能匹配等。对于这一类数据过滤出来，按缺失的内容分别写入不同Excel文件向客户提交，要求在规定的时间内补全。补全后才写入数据仓库。 (2)错误的数据 这一类错误产生的原因是业务系统不够健全，在接收输入后没有进行判断直接写入后台数据库造成的，比如数值数据输成全角数字字符、字符串数据后面有一个回车操作、日期格式不正确、日期越界等。这一类数据也要分类，对于类似于全角字符、数据前后有不可见字符的问题，只能通过写SQL语句的方式找出来，然后要求客户在业务系统修正之后抽取。日期格式不正确的或者是日期越界的这一类错误会导致ETL运行失败，这一类错误需要去业务系统数据库用SQL的方式挑出来，交给业务主管部门要求限期修正，修正之后再抽取。 (3)重复的数据 对于这一类数据——特别是维表中会出现这种情况——将重复数据记录的所有字段导出来，让客户确认并整理。 数据清洗是一个反复的过程，不可能在几天内完成，只有不断的发现问题，解决问题。对于是否过滤，是否修正一般要求客户确认，对于过滤掉的数据，写入Excel文件或者将过滤数据写入数据表，在ETL开发的初期可以每天向业务单位发送过滤数据的邮件，促使他们尽快地修正错误,同时也可以做为将来验证数据的依据。数据清洗需要注意的是不要将有 北京航空航天大学程序设计与数据结构试题 (2001年) 一、问答题(10’) 一般情况下，线性表可以采用哪几种存储结构？请分别叙述每一种存储结构的构造原理与特点。 二、(10’) 已知AOE网为G=(V，E)，其中V={v1，v2，v3，v4，v5，v6，v7，v8，v9，v10}，E={a1， a2，a3，a4，a5，a6，a7，a8，a9，a10，a11，a12，a13，a14}，其中： a1:(v1，v2)5a2:(v1，v3)6a3:(v2，v5)3a4:(v3，v4)3 a5:(v3，v5)6a6:(v4，v5)3a7:(v4，v7)1a8:(v4，v8)4 a9:(v5，v6)4a10:(v5，v7)2a11(v6，v10)4a12:(v7，v9)5 a13:(v8，v9)2a14:(v9，v10)2 注：顶点偶对右下角的数字表示边上的权值。 请按下述过程指出所有关键路径： ee[1:10]: le[1:10]: e[1:14]: l[1:14]: 其中，ee[i]与le[i]分别表示事件v i的最早发生时间与最晚发生时间；e[i]与l[i]分别表示活动a i的最早开始时间与最晚开始时间。 三、(10’) 欲建立一文献库，其正文(文献本身)存放在一个双向循环链表的各个链接点中。 1.为便于链接点的插入、删除操作，以及按题目、发表日期、发表者名称、主题词(假设每文最多给出三个主题词)进行检索，请设计该链表的链接点结构(给出链接点每个域的名称，并说明该域内存放什么信息。注：以下各小题设计链结点结构也这样要求)。画出整个链表结构的示意图。 2.设计一个三级索引结构，其中第三级索引称为题目索引，示按文献题目构造的稠密索引，通过该级索引并根据给定题目可得到每个文献的存放地址；该级索引按文献学科类分类存放。第二级索引称为中类索引，是题目索引的索引，指出同一中类的文献题目索引的存放位置(例如农林类、气象类……，古代史类，近代史类……)。第一级索引称为大类索引，指出同一大类(如：自然科学类、历史类……)的文献的中类索引的存放位置。请设计每一级索引的结点结构，并画出该索引的整体示意图。 3.在设计一种三级索引结构，其中第三级索引仍是题目索引(与2题所述相同)，第二级索引把具有相同主题词的文献题目索引地址组织在一个单链表中。第一级索引称为主题词索引，用文献给出的主题词做关键字组成杂凑表，即该级索引为一个杂凑表，能够指出具有同一主题词的文献题目索引的索引链表的第一个链结点的存储位置。该杂凑表采用链地址法处理冲突。请设计每一级索引的结点结构，并画出该索引的整体示意图。 四、(10’) 已知非空线性链表由list 五、(5’+10’) 已知求两个正整数m与n的最大公因子的过程用自然语言可以表述为反复执行如下动作： 大数据架构和模式（一）: 大数据分类和架构简介 1.本文对大数据做了哪些分类？ 2.对数据进行分类后，如何将它与合适的大数据模式匹配? 如何将大数据分为不同的类别 大数据问题的分析和解决通常很复杂。大数据的量、速度和种类使得提取信息和获得业务洞察变得很困难。以下操作是一个良好的开端：依据必须处理的数据的格式、要应用的分析类型、使用的处理技术，以及目标系统需要获取、加载、处理、分析和存储数据的数据源，对大数据问题进行分类。 概述 大数据可通过许多方式来存储、获取、处理和分析。每个大数据来源都有不同的特征，包括数据的频率、量、速度、类型和真实性。处理并存储大数据时，会涉及到更多维度，比如治理、安全性和策略。选择一种架构并构建合适的大数据解决方案极具挑战，因为需要考虑非常多的因素。 这个“大数据架构和模式” 系列提供了一种结构化和基于模式的方法来简化定义完整的大数据架构的任务。因为评估一个业务场景是否存在大数据问题很重要，所以我们包含了一些线索来帮助确定哪些业务问题适合采用大数据解决方案。 从分类大数据到选择大数据解决方案 如果您花时间研究过大数据解决方案，那么您一定知道它不是一个简单的任务。本系列将介绍查找满足您需求的大数据解决方案所涉及的主要步骤。 我们首先介绍术语“大数据” 所描述的数据类型。为了简化各种大数据类型的复杂性，我们依据各种参数对大数据进行了分类，为任何大数据解决方案中涉及的各层和高级组件提供一个逻辑架构。接下来，我们通过定义原子和复合分类模式，提出一种结构来分类大数据业务问题。这些模式有助于确定要应用的合适的解决方案模式。我们提供了来自各行各业的示例业务问题。最后，对于每个组件和模式，我们给出了提供了相关功能的产品。 第1 部分将介绍如何对大数据进行分类。本系列的后续文章将介绍以下主题：?定义大数据解决方案的各层和组件的逻辑架构 ?理解大数据解决方案的原子模式 ?理解用于大数据解决方案的复合（或混合）模式 ?为大数据解决方案选择一种解决方案模式 ?确定使用一个大数据解决方案解决一个业务问题的可行性 ?选择正确的产品来实现大数据解决方案 依据大数据类型对业务问题进行分类 业务问题可分类为不同的大数据问题类型。以后，我们将使用此类型确定合适的分类模式（原子或复合）和合适的大数据解决方案。但第一步是将业务问题映射到它的大数据类型。下表列出了常见的业务问题并为每个问题分配了一种大数据类型。 Programming Principles 1 1.2 THE GAME OF LIFE Exercises 1.2 Determine by hand calculation what will happen to each of the configurations shown in Figure 1.1 over the course of five generations. [Suggestion: Set up the Life configuration on a checkerboard. Use one color of checkers for living cells in the current generation and a second color to mark those that will be born or die in the next generation.] Answer (a) Figure remains stable. (b) (c) (d) Figure is stable. 1 2 Chapter 1 _ Programming Principles (e) (f) Figure repeats itself. (g) (h) (i) Figure repeats itself. (j) (k) (l) Figure repeats itself. Section 1.3 _ Programming Style 3 1.3 PROGRAMMING STYLE Exercises 1.3 E1. What classes would you define in implementing the following projects? What methods would your classes possess? (a) A program to store telephone numbers. Answer The program could use classes called Phone_book and Person. The methods for a Phone_book object would include look_up_name, add_person, remove_person. The methods for a Person object would include Look_up_number. Additional methods to initialize and print objects of both classes would also be useful. (b) A program to play Monopoly. Answer The program could use classes called Game_board, Property, Bank, Player, and Dice. In addition to initialization and printing methods for all classes, the following methods would be useful. The class Game_board needs methods next_card and operate_jail. The class Property needs methods change_owner, look_up_owner, rent, build, mortgage, and unmortgage. The class Bank needs methods pay and collect. The class Player needs methods roll_dice, move_location, buy_property and pay_rent. The class Dice needs a method roll. (c) A program to play tic-tac-toe. Answer The program could use classes called Game_board and Square. The classes need initialization and printing methods. The class Game_board would also need methods make_move and is_game_over. The class Square would need methods is_occupied, occupied_by, and occupy. (d) A program to model the build up of queues of cars waiting at a busy intersection with a traffic light. Answer The program could use classes Car, Traffic_light, and Queue. The classes would all need initialization and printing methods. The class Traffic_light would need additional methods change_status and status. The class Queue would need additional methods add_car and remove_car. E2. Rewrite the following class definition, which is supposed to model a deck of playing cards, so that it conforms to our principles of style. class a { // a deck of cards int X; thing Y1[52]; /* X is the location of the top card in the deck. Y1 lists the cards. */ public: a( ); void Shuffle( ); // Shuffle randomly arranges the cards. thing d( ); // deals the top card off the deck } ; Answer class Card_deck { Card deck[52]; int top_card; public: Card_deck( ); void Shuffle( ); Card deal( ); 西安科技大学 2013年硕士研究生入学考试试题A ───────────────────────────────── 科目编号：824 科目名称： 数据结构与算法设计 考生须知： 1、 答案必须写在答题纸上，写在试题或草稿纸上不给分。 2、 答题须用蓝、黑色钢笔或圆珠笔，用铅笔、红色笔者不给分。 3、 答题必须写清题号，字迹要清楚，卷面要保持整洁。 4、 试题要随答题纸一起交回。 一、单项选择题（每小题2分，共30分） （1）并归排序的时间复杂度是（ ）。 A ．O(n 2) B ．O(nlog 2n) C ．O(n) D ．O(log 2n) （2）设一个链表最常用的操作是在末尾插入结点和删除尾结点，选用（ ）存储结构最节省时间。 A ．单链表 B ．单循环链表 C ．带尾指针的单循环链表 D ．带头结点的双循环链表 （3）散列文件是一种（ ）。 A ．顺序文件 B ．索引文件 C ．链接文件 D ．计算机寻址文件 （4）常用于函数调用的数据结构是（ ）。 A ．栈 B ．队列 C ．数组 D ．链表 （5）两个矩阵sn ms B A ,相乘的时间复杂度是（ ）。 A ．O(n 2) B ．O(s 2) C ．O(msn) D ．O(mn) （6）图的广度优先搜索遍历使用的数据结构是（ ）。 A ．栈 B ．队列 C ．集合 D ．树 （7）在单链表中，每个存贮结点有两个域，即数据域和指针域，指针域指向该结点的（ ）。 A ．直接前驱 B ．直接后继 C ．开始结点 D ．终端结点 （8）在已知头指针的单链表中，要在其尾部插入一个新结点，其时间复杂度是（ ）。 A ．O(n 2) B ．O(1) C ．O(n) D ．O(log 2n) （9）在链队列中执行入队操作，（ ）。 A ．需判断队是否为空 B ．限定在链表头p 进行 C ．需判断队是否为满 D ．限定在链表尾p 进行 （10）对序列（95，83，62，70）进行冒泡排序（由小到大），第2趟排序后的结果为（ ）。 A ．（70，83，62，95） B ．（70，62，83，95） 1.技术实现框架 1.1大数据平台架构 1.1.1大数据库是未来提升业务能力的关键要素 以“大数据”为主导的新一波信息化浪潮正席卷全球，成为全球围加速企业技术创新、推动政府职能转变、引领社会管理变革的利器。目前，大数据技术已经从技术研究步入落地实施阶段，数据资源成为未来业务的关键因素。通过采集和分析数据，我们可以获知事物背后的原因，优化生产/生活方式，预知未来的发展动态。 经过多年的信息化建设，省地税已经积累了丰富的数据资源，为下一步的优化业务、提升管理水平，奠定了坚实的基础。 未来的数据和业务应用趋势，大数据才能解决这些问题。 《1.巨杉软件SequoiaDB产品和案例介绍 v2》P12 “银行的大数据资产和应用“，说明税务数据和业务分析，需要用大数据解决。 《1.巨杉软件SequoiaDB产品和案例介绍 v2》P14 “大数据与传统数据处理”，说明处理模式的差异。 1.1.2大数据平台总体框架 大数据平台总体技术框架分为数据源层、数据接口层、平台架构层、分析工具层和业务应用层。如下图所示： （此图要修改，北明） 数据源层：包括各业务系统、服务系统以及社会其它单位的结构化数据和非结构化数据； 数据接口层：是原始数据进入大数据库的入口，针对不同类型的数据，需要有针对性地开发接口，进行数据的缓冲、预处理等操作； 平台架构层：基于大数据系统存储各类数据，进行处理？； 分析工具层：提供各种数据分析工具，例如：建模工具、报表开发、数据分析、数据挖掘、可视化展现等工具； 业务应用层：根据应用领域和业务需求，建立分析模型，使用分析工具，发现获知事物背后的原因，预知未来的发展趋势，提出优化业务的方法。例如，寻找服务资源的最佳配置方案、发现业务流程中的短板进行优化等。 1.1.3大数据平台产品选型 针对业务需求，我们选择巨杉数据库作为大数据基础平台。 《数据结构与算法分析》课程设计教学任务书 一、课程设计的目的 数据结构与算法课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。 学习数据结构与算法是为了将实际问题中涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。通过此次课程设计主要达到以下目的： 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。 二、课程设计的基本要求 1. 独立思考，独立完成：课程设计中各任务的设计和调试要求独立完成，遇到问题可以讨论，但不可以拷贝。 2. 做好上机准备：每次上机前，要事先编制好准备调试的程序，认真想好调试步骤和有关环境的设置方法，准备好有关的文件。 3. 按照课程设计的具体要求建立功能模块，每个模块要求按照如下几个内容认真完成： a）需求分析： 在该部分中叙述，每个模块的功能要求 b）概要设计： 在此说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义） c）详细设计： 各个算法实现的源程序，对每个题目要有相应的源程序（可以是一组程序，每个功能模块采用不同的函数实现） 源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释 d）调试分析： 测试数据，测试输出的结果，时间复杂度分析，和每个模块设计和调试时存在问题的思考（问题是哪些，问题如何解决？），算法的改进设想 课程设计总结：（保存在word文档中）总结可以包括：课程设计过程的收获、遇到的问题、解决问题过程的思考、程序调试能力的思考、对数据结构这门课程的思考、在课程设计过程中对《数据结构》课程的认识等内容 4. 实现的结果必须进行检查和演示，程序源代码和程序的说明文件必须上交，作为考核内容的一部分。（上交时每人交一份，文件夹的取名规则为：“学号姓名”，如“09201199王五”。该文件夹下至少包括：“源代码”、“课程设计报告”、“可执行文件”。由学习委员收 非结构化数据存储方案 一、存储类型体系： 1.1 存储类型体系结构图 1.2 存储类型体系描述 （1）块存储：将存储区域划分为固定大小的小块，是传统裸存设备的存储空间对外暴露方式。块存储系统将大量磁盘设备通过SCSI/SAS或FC SAN与存储服务器连接，服务器直接通过SCSI/SAS或FC协议控制和 访问数据。主要包括DAS和SAN两种存储方式。对比如下图： （2） 分布式文件存储：文件存储以标准文件系统接口形式向应用系统提供 海量非结构化数据存储空间。分布式文件系统把分布在局域网内各个计算机上的共享文件夹集合成一个虚拟共享文件夹，将整个分布式文件资源以统一的视图呈现给用户。它对用户和应用程序屏蔽各个节点计算机底层文件系统的差异，提供用户方便的管理资源的手段和统一 的访问接口。主要包括NAS 和HDFS 两种存储方式。 a) 网络附加存储NAS 结构如图： b)HDFS分布式文件系统存储结构如图： （3）对象存储：对象存储为海量非结构化数据提供Key-Value这种通过键-值查找数据文件的存储模式，提供了基于对象的访问接口，有效地合并了NAS和SAN的存储结构优势，通过高层次的抽象具有NAS的跨平台共享数据优点，支持直接访问具有SAN的高性能和交换网络结 构的可伸缩性。主要包括swift和ceph两种实现形式。 a)Swift，OpenStack Object Storage（Swift）是OpenStack项目的子项目 之一，被称为对象存储。它构建在比较便宜的标准硬件存储基础设 施之上，无需采用RAID（磁盘冗余阵列），通过在软件层面引入一致性散列技术和数据冗余性，牺牲一定程度的数据一致性来达到高可 用性和可伸缩性，支持多租户模式、容器和对象读写操作，适合解 决非结构化数据存储问题。 b)ceph，Linux下PB级分布式文件系统，可轻松扩展PB容量，提供了 对多种工作负载的高性能和高可靠性。它大致分为四部分：客户端 （数据用户），元数据服务器（缓存和同步分布式元数据），一个对 象存储集群（包括数据和元数据），以及最后的集群监视器（执行监 视功能）。 湖南师范大学硕士研究生入学考试自命题考试大纲 考试科目代码：[967] 考试科目名称：C语言程序设计和数据结构 一、试卷结构 1) 试卷成绩及考试时间 本试卷满分为150分，考试时间为180分钟。 2)答题方式：闭卷、笔试 3)试卷内容结构 C语言程序设计部分 80% 数据结构部分 20% 4)题型结构 a: 单项选择题，共40分 b: 程序填空题，共30分 c: 程序阅读题，共25分 d: 编程题，共45分 e: 分析题，共10分 二、考试内容与考试要求 （一）C语言程序设计部分 考试内容 1、基本知识 （1）C语言的数据类型 （2）C语言中各种类型常量的表示法 （3）各类数值型数据间的混合运算 （4）C运算符 （5）关系表达式及运算，逻辑表达式及运算 2、顺序、选择与循环结构 （1）赋值语句，格式输入与输出 （2）if语句，switch语句 （3）goto、while、do-while、for、break、continue语句3、数组 （1）一维数组的定义和引用 （2）二维数组的定义和引用 （3）字符数组的定义和引用，字符串及其处理函数 4、函数 （1）函数定义与调用 （2）局部变量和全局变量 （3）变量的存储类型 （4）内部函数与外部函数 5、宏定义 （1）带参数的宏定义 （2）包含文件的处理 6、指针 （1）地址和指针的概念 （2）数组的指针和指向数组的指针变量 （3）字符串的指针和指向字符串的指针变量 （4）函数的指针和指向函数的指针变量 （5）指针数组和指向指针的数组 7、结构体和共同体 （1）结构体变量的定义和使用方法 （2）指向结构体类型变量的指针 （3）用指针处理链表 （4）共同体变量的定义和使用方法 《数据结构与C语言程序设计》复习大纲 《数据结构与C语言程序设计》包括“数据结构”与“C语言程序设计”两门课程的内容，各占比例50%。 《数据结构》部分 指定参考书： 《数据结构教程（第二版）》唐发根编著，北京航空航天大学出版社，2005 一、概述 1．简要了解数据的逻辑结构与存储结构的基本概念； 2．了解算法的定义、算法的五个基本性质以及算法分析最基本的概念，包括算法分析的前提、目的。 二、线性表 1．了解线性关系、线性表的定义，线性表的基本操作； 2．线性表的顺序存储结构与链式存储结构(包括单链表、循环链表和双向链表)的构造原理； 3．掌握在以上两种存储结构的基础上对线性表实施的基本操作，重点包括顺序表的插入和删除、链表的建立、插入和删除、检索等操作对应的过程和算法的设计。 三、堆栈与队列 1．了解堆栈与队列(不含循环队列)的基本概念、基本操作； 2．掌握堆栈与队列的顺序存储结构与链式存储结构的构造原理； 3．掌握在不同存储结构的基础上对堆栈与队列实施插入与删除等基本操作过程。 四、树与二叉树 1．了解树型结构的基本概念，基本特征、名词术语； 2．了解完全二叉树、满二叉树的概念；二叉树的基本性质（至少要记住结论）； 3．了解二叉树的顺序存储结构与二叉链表存储结构的构造原理及特点，重点是二叉链表存储结构； 4．掌握二叉树的前序遍历、中序遍历、后序遍历和按层次遍历算法(非递归算法)以及利用遍历解决有关二叉树的其它操作； 5．掌握二叉排序树的基本概念、建立(插入)和查找。 五、图 1．了解图结构的基本概念、基本名词术语； 2．掌握图的邻接矩阵存储方法和邻接表存储方法的基本构造原理与特点； 3．图的深度优先搜索和广度优先搜索的基本过程，遍历的基本作用； 4．最小生成树的求解过程，拓扑排序及其目的。 六、文件及查找 1．掌握顺序查找法、折半查找法的查找过程，了解折半查找方法的基本要求； 2．了解散列(Hash)文件的基本特点，散列函数和散列冲突的概念，处理散列冲突的方法。 七、内排序 了解插入排序法、选择排序法、泡排序法、快速排序法以及堆积排序(大顶堆积)法等排序方法的排序原理、规律和特点。 《C语言程序设计》部分 指定参考书： 《C程序设计》（第三版）谭浩强著，清华大学出版社, 2005.7 814程序设计与数据结构考试大纲 085211计算机技术专业 一、考试目的 本考试是全日制计算机技术专业学位研究生的入学资格考试之专业基础课，各语种考生统一用汉语答题。各招生院校根据考生参加本考试的成绩和其他三门考试的成绩总分来选择参加第二轮，即复试的考生。 二、考试的性质与范围 本考试是测试考生计算机科学基础知识的水平考试。考试范围包括本大纲规定的C++语言程序设计和数据结构。 三、考试基本要求 1. 具备扎实的C++语言程序设计基本功。 2. 具备设计数据结构和算法求解问题的基本能力。 四、考试形式 本考试采取客观试题与主观试题相结合，单项技能测试与综合技能测试相结合的方法，强调考生设计数据结构和算法并编程实现来求解问题的能力。试题分类参见“考试内容一览表”。 五、考试内容 本考试包括两个部分：C++程序设计、数据结构。总分150分。 I. C++程序设计 1. 考试要求 该部分要求考生对C++语言基本特性、面向对象程序设计方法和Visual C++编译器相关特性有很好的了解。 2. 题型 选择题、读程序写出Visual C++下的执行结果、程序填空，共75分。 II. 数据结构 1. 考试要求 该部分要求考生掌握线性表（及其扩展：栈和FIFO队列）、树（包括基本的二叉树和堆、搜索树等特殊树结构）、图等基本数据结构及其上的操作；掌握二分搜索、Hash技术及搜索树等搜索方法；掌握选择、起泡、插入等简单排序算法，堆排序、快速排序、归并排序和谢尔（希尔）等快速排序算法，以及箱子、基数排序等非比较排序算法。具备利用上述数据结构和算法以及设计新数据结构和算法来求解问题的能力。 2. 题型 选择题、简答题、算法设计题，共75分。 2013年“数据结构与C程序设计”(代码991)试题 一、单项选择题（本题共20分，每小题各2分） 1．对于长度为n的线性表，建立其对应的单链表的时间复杂度为( )。 A．O(1)；B．O(log2n)；．O(n)；D．O(n2)。 2．一般情况下，在一个双向链表中插入一个新的链结点，( )。 A．需要修改4个指针域内的指针；B．需要修改3个指针域内的指针； C．需要修改2个指针域内的指针；D．只需要修改1个指针域内的指针。 3．假设用单个字母表示中缀表达式中的一个运算数(或称运算对象)，并利用堆栈产生中缀表达式对应的后缀表达式。对于中缀表达式A+B*(C/D-E)，当从左至右扫描到运算数E时，堆栈中的运算符依次是( )。(注：不包含表达式的分界符) A．+*/-；B．+*(/-；C．+*-；．+*(-。 4．若某二叉排序树的前序遍历序列为50,20,40,30,80,60,70，则后序遍历序列为( )。 A．30,40,20,50,70,60,80；B．30,40,20,70,60,80,50； C．70,60,80,50,30,40,20；D．70,60,80,30,40,20,50。 5．分别以6, 3, 8, 12, 5, 7对应叶结点的权值构造的哈夫曼(Huffman) 树的深度为( )。 A．6；B．5；C．4；D．3。 6．下列关于图的叙述中，错误的是( )。 A．根据图的定义，图中至少有一个顶点； B．根据图的定义，图中至少有一个顶点和一条边(弧)； C．具有n个顶点的无向图最多有n(n-1)/2条边； D．具有n个顶点的有向图最多有n(n-1)条边(弧)。 7．若在有向图G的拓扑序列中，顶点vi在顶点vj之前，则下列4种情形中不可能出现的是( )。 A．G中有弧 《数据结构》 Part1 一．选择 1. 组成数据的基本单位是（） A）数据项B）数据类型C）数据元素D）数据变量 2．算法分析的目的是（） A）找出数据结构的合理性B）研究算法的输入/输出关系 C）分析算法的效率以求改进D）分析算法的易读性 3．在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（）A）O(1) B）0(n) C）O(n^2) D）O(nlog2n) 4．若线性表采用顺序存储结构，每个元素占用4个存储单元，第一个元素的存储地址为100，则第12个元素的存储地址是（） A）112 B）144 C）148 D）412 5．下面关于线性表的叙述中，错误的是（） A）顺序表使用一维数组实现的线性表B）顺序表必须占用一片连续的存储单元. C）顺序表的空间利用率高于链表D）在单链表中,每个结点只有一个链域. 6．在需要经常查找结点的前驱与后继的情况下，使用（）比较合适 A）单链表B）双链表C）顺序表D）循环链表 7．队列通常采用的两种存储结构是（） A）顺序存储结构和链式存储结构B）散列方式和索引方式 C）链表存储结构和线性存储结构D）线性存储结构和非线性存储结构 8．在一个单链表中，若删除p所指结点的后继结点，则执行（） A）p->next=p->next->next；B）p=p->next；p->nex=p->next->next； C）p->next=p->next；D）p=p->next->next； 9．若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间 A）单链表B）仅有头指针的单循环链表C）双链表D）仅有尾指针的单循环链表 10．按二叉树的定义，具有三个结点的二元树共有（）种形态。 A）3 B）4 C）5 D）6 11．任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（）A）发生改变B）不发生改变C）不能确定D）以上都不对12．深度为5的二叉树至多有（）个结点 A）16 B）32 C）31 D）10 13．在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，那么度为0的结点数为（）个。 A）4 B）5 C）6 D）7 14．对于一个具有n个顶点的无向图，若采用邻接表表示，则存放表头结点的数组(顶点表)的大小为（） A）n B）n+1 C）n-1 D）n/2 15．静态查找表和动态查找表二者的根本差别在于（） 数据结构与及程序设计专题 实验报告 一．实验任务： 对于给定的源文档 SourceDoc.txt， 1) 统计其中所有字符的频度（某字符的频度等于其出现的总次数除以总字符数），字符包括字母（区分大小写）、标点符号及格式控制符（空格、回车等）。 2) 按频度统计结果构建哈夫曼编码表。 3) 基于哈夫曼编码表进行编码，生成对应的二进制码流，并输出到文件 Encode.dat，完成信源的编码过程。 4) 根据生成的哈夫曼编码表，对二进制码流文件Encode.dat 进行解码，把结果输出到文件 TargetDoc.txt，完成信源的解码过程。 5) 判断 TargetDoc.txt 与 SourceDoc.txt 内容是否 一致，以验证编解码系统的正确性。 二．实验内容: 1) 线性链表的构建以及排序; 2) 哈夫曼树的构建; 3) 基于哈夫曼码进行编码; 4) 对二进制码进行解码; 5）对生成文件与原文件进行比较；三．程序的算法描述 四．程序运行结果： 五．源程序代码： #include { NODE *h, *p, *s,*death; int i; h=(NODE*)malloc(sizeof(NODE));p=(NODE*)malloc(size of(NODE)); h->next=p;h->pre=NULL; p->pre=h;p->next=NULL; p->data=b[0]; p->count=1.0; for(i=1;b[i]!='\0';i++) {s=(NODE*)malloc(sizeof(NODE)); s->data=b[i]; s->count=1.0; s->next=NULL; s->pre=p; p->next=s; p=s; } return h; } void fun(NODE* h,int amount) { NODE *p,*q,*death; for(p=h->next;p;p=p->next){ 在数据分析中，我们会接触到很多的数据，而这些数据都是有类别之分的。这些数据根据结构分类被划分为三种，它们分别是结构化数据、非结构化数据、半结构化数据。在这篇文章中我们就简单地给大家介绍一下这三种数据的相关知识。 首先我们说一下结构化数据，结构化的数据是指可以使用关系型数据库表示和存储，表现为二维形式的数据。一般特点是：数据以行为单位，一行数据表示一个实体的信息，每一行数据的属性是相同的。能够用数据或统一的结构加以表示，我们称之为结构化数据，如数字、符号。传统的关系数据模型、行数据，存储于数据库，可用二维表结构表示。而结构化的数据的存储和排列是很有规律的，这对查询和修改等操作很有帮助。 然后我们说一下半结构化数据，半结构化数据是结构化数据的一种形式，它并不符合关系型数据库或其他数据表的形式关联起来的数据模型结构，但包含相关标记，用来分隔语义元素以及对记录和字段进行分层。因此，它也被称为自描述的结构。半结构化数据，属于同一类实体可以有不同的属性，即使他们被组合在一起，这些属性的顺序并不重要。所谓半结构化数据，就是介于完全结构化数据和完全无结构的数据之间的数据，XML、HTML文档就属于半结构化数据。它一般是自描述的，数据的结构和内容混在一起，没有明显的区分。而不同的半结构化数据的属性的个数是不一定一样的。有些人说半结构化数据是以树或者图的数据结构存储的数据，怎么理解呢？ 最后我们给大家介绍一下非结构化数据，非结构化数据顾名思义，就是没有固定结构的数据。各种文档、图片、视频、音频等都属于非结构化数据。对于这类数据，我们一般直接整体进 行存储，而且一般存储为二进制的数据格式。非结构化数据库是指其字段长度可变，并且每 个字段的记录又可以由可重复或不可重复的子字段构成的数据库，用它不仅可以处理结构化 数据而且更适合处理非结构化数据。 在这篇文章中我们简单地给大家介绍了结构化数据、非结构化数据以及半结构化数据的知识，其实现在很多的数据分析师都开始加大对非结构化数据的研究。由此可见，非结构化数据的 前景还是十分明朗的。天津大学数据结构和程序设计考研真题
数据结构与算法设计实验
结构化数据和非结构化数据
程序设计与数据结构-2001
大数据架构和模式
数据结构与程序设计C++描述(Kruse著)高等教育出版社_课后答案.
824数据结构与算法设计A
大数据平台架构~巨衫
天津科技大学数据结构与算法课程设计
(完整版)非结构化存储方案
C语言程序设计和数据结构
数据结构与C语言程序设计
814程序设计与数据结构考试大纲
北航数据结构与程序设计真题-2013北航991真题与答案
数据结构和C++程序设计_题库
数据结构与及程序设计专题实验报告
简述结构化数据、非结构化数据、半结构化数据