深度优先搜索练习题
一、填数字三角形问题
提交文件：numlist.exe /(numlist.pas 或numlist.bas)
问题描述：
将1—15这15个自然数，不重复不遗漏地填入如下给出的15个方框中，使除最上面一层外，每个框中的数字等于上面两个方框中数之差的绝对值，试编一程序找出所有填数的方案。按如下位置格式输出数字三角形。注：全部用输出语句输出结果的不得分。
□□□□□
□□□□
□□□
□□
□
数据输入输出说明：
本题没有数据输入，结果按如上格式输出到屏幕。
二、王伯买鱼（ FiSh）
提交文件：Fish．exe
输入文件： Fish．dat
输出文件：Fish. out
王伯退休后开始养鱼。他一早起来就赶去动物公园，发现这个世界的鱼真不少，五光十色、色彩斑调，大的、小的，什么都有。这些鱼实在是太美了，买的人越来越多，湖里的鱼越来越少。没有美丽的鱼。哪里有美丽的湖？于是动物公园不得不规定，对于每种鱼，每个人最多只能买一条。并且有些鱼是不能一起买的，因为它们之间会互相争斗吞食。
王伯想买尽可能多的鱼，但很可惜，他的资金有限。他冥思苦想，不知如何是好。请编写一个程序帮助他。如果有多个方案都能买尽可能多的鱼，选择所花资金最多的一个。
输入:
从输入文件读人数据。输入文件的第一行为两个正整数M（M<=100），N（N＜=30），分别表示王伯的资金和鱼的种类。以下 N行，每行有两个正整数S（ l=＜S＜=N），T，分别表示某种鱼的编号以及该鱼的价格。
接着，每行有两个整数P，Q。当P，Q均大于0时，表示P，Q不能共处；当P，Q均等于0时，表示输入文件的结束。
输出
输出文件的第一行为两个正整数X，Y，分别表示所买鱼的条数和总花费。以下X行，每行有一个正整数，表示所买鱼的编号。编号按升序排列输出。
如果题目有多个解，只需输出其中的一个。
输入举例
170 7
1 70
2 50
3 30
4 40
5 40
6 30
7 20
1 4
1 7
3 4
3 5
5 7
6 7
0 0
输出举例
4 160
2
4
5
6
三、数学家旅游
文件名：GOL YGON.pas
有一个城市的道路由规则的方砖组成。有一位数学家来到参观，他可沿方砖的边沿行走，有四种方法：n(0,1), s(0,-1), e(1,0), w(-1,0)，但他是一个很怪的数学家，他会走一段时间休息一会儿，然后继续走。他有几个很特别的特性：
不喜欢休息后走的方向和休息前一样；
第一次休息前走一步，休息后走的距离比休息前的距离长一步；
不喜欢重复走同一个地方；
要走回出发点。
我们称他的路线是一个goline，我们可以将出发的地点记为（0，0），城市有几个地点正在施工，是不可以通行的。为了这位奇怪的科学家可以旅游得开心，我们决定帮他设计旅游的方案，找出城市中有多少个他希望的goline。
输入：第一行是goline最大边的大小（不大于20），第二行是施工地点的个数（不大小50），以下的每行有两个数字，表示施工的地点的坐标。
输出：每一个goline的走法，每个占一行，最后输出goline的个数。
例如：输入：GOL YGON.dat
8
2
-2 0
6 -2
输出：GOL YGON.out
wsenenws
TOTAL=1
四、单词背诵
问题描述：
小小在背单词，她发现当背诵了单词beauty 以后，再接着背诵单词beautiful 就会觉
得容易许多。由于有很多单词要背，她希望找到一种好的背诵顺序。单词A和它的前驱B 的最大公共前缀的长度称为背诵单词A的便利值(例如：B=’beauty’,A=’beautiful’,则A 的便利值是len({A,B})=len(’beaut’)=5),我们认为一个背诵单词A的花费是它的长度(例如:’beautiful’的长度len(‘beautiful’)=9)与它的便利值之差（对于上述例子背诵A的花费为9-5=4）。请你求一个背诵顺序，使得背诵这些单词的花费总和最小。假设一开始你什么单词都不记得。
输入格式：
给定一个单词表：第一行N（N < 100）表示单词总数。接下来N行，每行一个单词。每个单词的长度不超过20，均为小写字母组成。
输出格式：
按照背诵顺序输出每个单词，每个单词占一行，不能有多余的字符。
样例：
五、分离单词
提交文件名：DIVWOED. EXE
问题描述：
一个长度为L的双重线形的纵横字串是指由L个小写英文字母排列而成的字串。它至少有两种划分的方法（称为分离法）分解成一组单词的排列，这些单词应该与从给定的单词表中选出来的相同。看下面的例子（L=17）：
| | | |
a n d a t a r e a l l a s t a s k
| | | | |
这些单词是从以下列表选出的：all，an，and, are，area, as，ask，at, data, last, or, read, real， task。
出现在第一种分离法的单词不能在第二种分离法中出现，反之亦然。并且，任何一个单词在任何一个分离法中不能重复出现。一个单词在一种分离法中结束的位置不能和某一个单词在另一种分离法中结束的位置相同（字串结尾的单词除外）。其中一种分离法可以只包含一个单词。
请你编写一个程序构造一个满足以上规则的长度为L的双重线形纵横字串，其组成的单词从一个给定的单词列表中选出。单词列表中的单词已按字典顺序排列好。
输入格式：
从当前目录下的文本文件“ DIVWORD.DAT”中读人数据。
文件中第一行是一个整数L（4= （N＜=1000），表示列表中的单词个数。以下是N行长度从2到20的字串单词（由小写英文字母构成）。这些单词已按字典顺序排列好，且没有重复。 输出格式： 结果输出到当前目录下的文本文件“ DIVWORD．OUT”中。对于输入的数据集，你的程序须输出任意一个给定长度的双重线形纵横字串。若这种字串不存在，程序须输出一行信息“NOSOLUTION”。 输入输出举例: 输入文件: DIVWORD.DAT 输出文件:DIVWORD.OUT 17 andatareallastask 14 all an and are area as ask at data last or read real task 六、虫食算 (alpha.pas/dpr/c/cpp) 【问题描述】 所谓虫食算，就是原先的算式中有一部分被虫子啃掉了，需要我们根据剩下的数字来判定被啃掉的字母。来看一个简单的例子： 43#9865#045 + 8468#6633 44445506978 其中#号代表被虫子啃掉的数字。根据算式，我们很容易判断：第一行的两个数字分别是5和3，第二行的数字是5。 现在，我们对问题做两个限制： 首先，我们只考虑加法的虫食算。这里的加法是N进制加法，算式中三个数都有N位，允许有前导的0。 其次，虫子把所有的数都啃光了，我们只知道哪些数字是相同的，我们将相同的数字用相同的字母表示，不同的数字用不同的字母表示。如果这个算式是N进制的，我们就取英文字母表午的前N个大写字母来表示这个算式中的0到N-1这N个不同的数字：但是这N个字母并不一定顺序地代表0到N-1)。输入数据保证N个字母分别至少出现一次。 BADC + CRDA DCCC 上面的算式是一个4进制的算式。很显然，我们只要让ABCD分别代表0123，便可以让这个式子成立了。你的任务是，对于给定的N进制加法算式，求出N个不同的字母分别代表的数字，使得该加法算式成立。输入数据保证有且仅有一组解， 【输入文件】 输入文件alpha.in包含4行。第一行有一个正整数N(N<=26)，后面的3行每行有一个由大写字母组成的字符串，分别代表两个加数以及和。这3个字符串左右两端都没有空格，从高位到低位，并且恰好有N位。 【输出文件】 输出文件alpha.out包含一行。在这一行中，应当包含唯一的那组解。解是这样表示的：输出N个数字，分别表示A，B，C……所代表的数字，相邻的两个数字用一个空格隔开，不能有多余的空格。 【样例输入】 5 ABCED BDACE EBBAA 【样例输出】 1 0 3 4 2 【数据规模】 对于30％的数据，保证有N<＝10； 对于50％的数据，保证有N<＝15； 对于全部的数据，保证有N<＝26。 合肥学院 计算机科学与技术系 课程设计报告 2013～2014学年第二学期 课程数据结构与算法 课程设计名称图的深度优先遍历算法的实现 学生姓名陈琳 学号1204091022 专业班级软件工程 指导教师何立新 2014 年9 月 一：问题分析和任务定义 涉及到数据结构遍会涉及到对应存储方法的遍历问题。本次程序采用邻接表的存储方法，并且以深度优先实现遍历的过程得到其遍历序列。 深度优先遍历图的方法是，从图中某顶点v 出发： （1）访问顶点v ； （2）依次从v 的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v 有路径相通的顶点都被访问； （3）若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。 二：数据结构的选择和概要设计 设计流程如图： 图1 设计流程 利用一维数组创建邻接表，同时还需要一个一维数组来存储顶点信息。之后利用创建的邻接表来创建图，最后用深度优先的方法来实现遍历。 图 2 原始图 1.从0开始，首先找到0的关联顶点3 2.由3出发，找到1；由1出发，没有关联的顶点。 3.回到3，从3出发，找到2；由2出发，没有关联的顶点。 4.回到4，出4出发，找到1，因为1已经被访问过了，所以不访问。 所以最后顺序是0,3,1,2,4 三：详细设计和编码 1.创建邻接表和图 void CreateALGraph (ALGraph* G) //建立邻接表函数. { int i,j,k,s; char y; EdgeNode* p; //工作指针. printf("请输入图的顶点数n与边数e(以逗号做分隔符)：\n"); scanf("%d,%d",&(G->n),&(G->e)); scanf("%c",&y); //用y来接收回车符. for(s=0;s ? ? 消除社会矛盾 #include 一、单选题（题数：50，共50.0 分） 1汉武帝之后的两千年里，历史基本的状态是（）。（1.0分）0.0 分 A、 儒表道里 B、 法表儒里 C、 道表儒里 D、 儒表法里 正确答案：D 我的答案：C 答案解析： 2历史上，通过（）的驱使才能实现大义灭亲。（1.0分）1.0 分 A、 利益 B、 惩罚 C、 金钱 D、 官位 正确答案：A 我的答案：A 答案解析： 3汉代的法律系统是（）。（1.0分）1.0 分 A、 法家化的 B、 道家化的 C、 儒法化的 D、 儒家化的 正确答案：A 我的答案：A 答案解析： 4所谓的“挪置罪名”是指将有罪的（）可以说成无罪之人。（1.0分）1.0 分A、 官吏的恩宠 B、 官员 C、 道德的模范 D、 人民的公仆 正确答案：A 我的答案：A 5下列人物中，不主张发展福利国家的是（）。（1.0分）1.0 分 A、 王安石 B、 韩非子 C、 司马光 D、 桑弘羊 正确答案：D 我的答案：D 答案解析： 6西方历史上，所谓的“重商主义”是指重视对商业的（）。（1.0分）1.0 分A、 尊重 B、 管控 C、 发展 D、 投资 正确答案：B 我的答案：B 答案解析： 7（）是秦制与封建制的主要区别。（1.0分）1.0 分 A、 经济发展模式 B、 政治制度 C、 文化模式 D、 附庸或者奴才的管理方式 正确答案：D 我的答案：D 答案解析： 8（）是秦制成功的关键所在。（1.0分）1.0 分 A、 使人人平等 B、 改善人民生活 C、 提高国际地位 D、 发展经济 正确答案：A 我的答案：A 9从（）开始，中国法律逐步儒家化。（1.0分）1.0 分 A、 春秋时代 B、 明清时代 C、 曹魏时代 D、 秦汉时代 正确答案：C 我的答案：C 答案解析： 10儒家学说认为，（）是个人的身体所有者。（1.0分）1.0 分 A、 国家 B、 自然 C、 自己 D、 父母 正确答案：D 我的答案：D 答案解析： 11（）不仅将首都迁至北京，而且在南京还留有模拟政府。（1.0分）1.0 分A、 明代 B、 宋代 C、 唐代 D、 清代 正确答案：A 我的答案：A 答案解析： 12从（）开始，尚书成为了一个庞大的机构。（1.0分）1.0 分 A、 西汉 B、 三国 C、 唐代 D、 东汉 正确答案：D 我的答案：D 上机实验报告 学院：计算机与信息技术学院 专业：计算机科学与技术(师范）课程名称：数据结构 实验题目：深度优先遍历（邻接矩阵）班级序号：师范1班 学号：201421012731 学生姓名：邓雪 指导教师：杨红颖 完成时间：2015年12月25号 一、实验目的： 1﹒掌握图的基本概念和邻接矩阵存储结构。 2﹒掌握图的邻接矩阵存储结构的算法实现。 3﹒掌握图在邻接矩阵存储结构上遍历算法的实现。 二、实验环境： Windows 8.1 Microsoft Visual c++ 6.0 二、实验内容及要求： 编写图的深度优先遍历邻接矩阵算法。建立图的存储结构，能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。 四、概要设计： 深度优先搜索遍历类似于树的先根遍历，是树的先根遍历的推广。假设初始状态是图中所有的顶点未曾被访问，则深度优先遍历可从图的某个顶点V出发，访问此顶点，然后依次从V的未被访问的邻接点出发深度优先遍历图，直至图中所有和V有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中的一个未被访问的顶点，重复上述过程，直至图中所有顶点都被访问到为止。 以图中无向图G4为例，深度优先遍历图的过程如图所示。假设从顶点V1出发进行搜索，在访问了顶点V1后，选择邻接点V2。因为V2未曾访问，则从V2出发进行搜索。依次类推，接着从V4,V8,V5出发进行搜索。在访问了V5之后，由于V5的邻接点已都被访问，则搜索回到V8。由于同样的理由，搜索继续回到V4，V2直至V1，此时由于V1的另一个邻接点为被访问，则搜索又从V1到V3，再继续进行下去。由此得到顶点的访问序列为： V1 V2 V4 V8 V5 V3 V6 V7 五、代码 #include 一．实验目的 熟悉图的存储结构，掌握用单链表存储数据元素信息和数据元素之间的关系的信息的方法，并能运用图的深度优先搜索遍历一个图，对其输出。 二．实验原理 深度优先搜索遍历是树的先根遍历的推广。假设初始状态时图中所有顶点未曾访问，则深度优先搜索可从图中某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有与v有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。 图的邻接表的存储表示： #define MAX_VERTEX_NUM 20 #define MAXNAME 10 typedef char VertexType[MAXNAME]; typedef struct ArcNode{ int adjvex; struct ArcNode *nextarc; }ArcNode; typedef struct VNode{ VertexType data; ArcNode *firstarc; }VNode,AdjList[MAX_VERTEX_NUM]; typedef struct{ AdjList vertices; int vexnum,arcnum; int kind; }ALGraph; 三．实验内容 编写LocateVex函数，Create函数，print函数，main函数，输入要构造的图的相关信息，得到其邻接表并输出显示。 四。实验步骤 1）结构体定义,预定义，全局变量定义。 #include"stdio.h" #include"stdlib.h" #include"string.h" #define FALSE 0 #define TRUE 1 #define MAX 20 typedef int Boolean; #define MAX_VERTEX_NUM 20 如果找答案直接使用WORD查找功能就好,只需要打入题干中几个字便可尔星泛雅 一、单选题（题数：50，共50.0 分） 1下列选项中，属于秦汉社会的特点是（）。（1.0分）0.0 分 A、 家族群居性 B、 小家庭性 C、 非宗法性 D、 宗法性 正确答案：C 我的答案：B 2从（）开始，儒家思想与道家思想开始疏远。（1.0分）1.0 分 A、 孔子时代 B、 孟子、庄周时代 C、 老子时代 D、 以上答案都错误 正确答案：B 我的答案：B 3贵族和平民的差异被（）削弱了。（1.0分）1.0 分 A、 隋唐时期 B、 唐朝时期 C、 宋朝时期 D、 秦制时期 正确答案：D 我的答案：D 4与其他乱臣贼子相比，王莽篡党夺权的特点是（）。（1.0分）1.0 分 A、 严重失去民心 B、 手段温和 C、 非常得民心 D、 手段残忍 正确答案：C 我的答案：C 5汉代时期的五铢钱因为（）的原因而对今天的收藏界来说卖不上价。（1.0分）0.0 分 A、 铸钱所用材质廉价 B、 工艺简单 C、 历史时间短 D、 发行数量大 正确答案：D 我的答案：A 6法家制度主张，在（）面前人人平等。（1.0分）0.0 分 A、 权利 B、 皇上 C、 法律 D、 法制 正确答案：A 我的答案：C 7（）是秦汉时期经济最发达的地区。（1.0分）1.0 分 A、 关东 B、 关中 C、 关南 D、 关西 正确答案：A 我的答案：A 8（）不仅将首都迁至北京，而且在南京还留有模拟政府。（1.0分）1.0 分A、 明代 B、 宋代 C、 唐代 D、 清代 正确答案：A 我的答案：A 9明清时代的家族观念是（）。（1.0分）0.0 分 A、 家族散居 B、 小家庭 C、 大家庭 D、 以上答案均错误 正确答案：C 我的答案：B 10中国历史上第二度出现大城市崛起的时间是在（）以后。（1.0分）1.0 分A、 元朝时期 B、 明朝时期 C、 秦汉时期 D、 唐宋时期 正确答案：D 我的答案：D 11汉武帝之后的两千年里，历史基本的状态是（）。（1.0分）0.0 分 A、 儒表道里 B、 法表儒里 C、 道表儒里 D、 儒表法里 #include 华北水利水电学院数据结构实验报告 20 10 ～20 11 学年第一学期2008级计算机专业 班级：107学号：200810702姓名：王文波 实验四图的应用 一、实验目的： 1．掌握图的存储结构及其构造方法 2．掌握图的两种遍历算法及其执行过程 二、实验内容： 以邻接矩阵或邻接表为存储结构，以用户指定的顶点为起始点，实现无向连通图的深度优先及广度优先搜索遍历，并输出遍历的结点序列。 提示：首先，根据用户输入的顶点总数和边数，构造无向图，然后以用户输入的顶点为起始点，进行深度优先和广度优先遍历，并输出遍历的结果。 三、实验要求： 1．各班学号为单号的同学采用邻接矩阵实现，学号为双号的同学采用邻接表实现。 2．C/ C++完成算法设计和程序设计并上机调试通过。 3．撰写实验报告，提供实验结果和数据。 4．写出算法设计小结和心得。 四、程序源代码： #include { int nData; QueueNode* next; }; struct QueueList { QueueNode* front; QueueNode* rear; }; void EnQueue(QueueList* Q,int e) { QueueNode *q=new QueueNode; q->nData=e; q->next=NULL; if(Q==NULL) return; if(Q->rear==NULL) Q->front=Q->rear=q; else { Q->rear->next=q; Q->rear=Q->rear->next; } } void DeQueue(QueueList* Q,int* e) { if (Q==NULL) return; if (Q->front==Q->rear) { *e=Q->front->nData; Q->front=Q->rear=NULL; } else { *e=Q->front->nData; Q->front=Q->front->next; } } //创建图 void CreatAdjList(Graph* G) { int i,j,k; edgenode* p1; edgenode* p2; 有两种常用的方法可用来搜索图：即深度优先搜索和广度优先搜索。它们最终都会到达所有 连通的顶点。深度优先搜索通过栈来实现，而广度优先搜索通过队列来实现。 深度优先搜索： 深度优先搜索就是在搜索树的每一层始终先只扩展一个子节点，不断地向纵深前进直到不能再前进(到达叶子节点或受到深度限制)时，才从当前节点返回到上一级节点，沿另一方向又继续前进。这种方法的搜索树是从树根开始一枝一枝逐渐形成的。 下面图中的数字显示了深度优先搜索顶点被访问的顺序。 "* ■ J 严-* 4 t C '4 --------------------------------- --- _ 为了实现深度优先搜索，首先选择一个起始顶点并需要遵守三个规则： (1) 如果可能，访问一个邻接的未访问顶点，标记它，并把它放入栈中。 (2) 当不能执行规则1时，如果栈不空，就从栈中弹出一个顶点。 (3) 如果不能执行规则1和规则2，就完成了整个搜索过程。 广度优先搜索： 在深度优先搜索算法中，是深度越大的结点越先得到扩展。如果在搜索中把算法改为按结点的层次进行搜索，本层的结点没有搜索处理完时，不能对下层结点进行处理，即深度越小的结点越先得到扩展，也就是说先产生的结点先得以扩展处理，这种搜索算法称为广度优先搜索法。 在深度优先搜索中，算法表现得好像要尽快地远离起始点似的。相反，在广度优先搜索中， 算法好像要尽可能地靠近起始点。它首先访问起始顶点的所有邻接点，然后再访问较远的区 域。它是用队列来实现的。 下面图中的数字显示了广度优先搜索顶点被访问的顺序。 实现广度优先搜索，也要遵守三个规则: ⑴ 访问下一个未来访问的邻接点，这个顶点必须是当前顶点的邻接点，标记它，并把它插入到队列中。（2）如果因为已经没有未访问顶点而不能执行规则1 *问题描述： 建立图的存储结构（图的类型可以是有向图、无向图、有向网、无向网，学生可以任选两种类型），能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。 1、邻接矩阵表示法: 设G=(V,E)是一个图，其中V={V1,V2,V3…,Vn}。G的邻接矩阵是一个他有下述性质的n阶方阵： 1，若(Vi,Vj)∈E 或 若图中每个顶点只含一个编号i(1≤i≤vnum)，则只需一个二维数组表示图的邻接矩阵。此时存储结构可简单说明如下： type adjmatrix=array[1..vnum,1..vnum]of adj; 利用邻接矩阵很容易判定任意两个顶点之间是否有边（或弧）相联，并容易求得各个顶点的度。 对于无向图，顶点Vi的度是邻接矩阵中第i行元素之和，即 n n D(Vi)＝∑A[i,j]（或∑A[i,j]） j=1 i=1 对于有向图，顶点Vi的出度OD(Vi)为邻接矩阵第i行元素之和，顶点Vi 的入度ID(Vi)为第i列元素之和。即 n n OD(Vi)＝∑A[i,j]，OD(Vi)＝∑A[j,i]） j=1j=1 用邻接矩阵也可以表示带权图，只要令 Wij, 若 成绩： 99.0 分 我的答案：C 孟子所在的时代“君”是指（）。 2007-05-27 晴 //采用非递归深度优先遍历算法，可以将回溯法表示为一个非递归过程 #include }; private: int Bound(int i); void Backtrack(int i); int c; //背包容量 int n; //物品数 int *w; //物品重量数组int *p; //物品价值数组int cw; //当前重量 int cp; //当前价值 int bestp; //当前最优值int *bestx; //当前最优解int *x; //当前解 }; int Knap::Bound(int i) //装满背包 if(i<=n) b+=p/w*cleft; return b; } void Knap::Backtrack(int i) { if(i>n) { if(bestp 第二章 两汉史学——中国封建史学的初步奠定 第一节：两汉史学形成的基本文化背景 战国末年，秦国的军事、政治、经济强大，需要在文化方面有个有力的指导。相国吕不韦《吕氏春秋》，成为秦的军事、政治、经济的指导原则。不久，政治上实现了大一统，但是秦始皇为了推行思想上的大一统，却采纳了法家李斯的建议，焚书坑儒，造成了中国学术空前的浩劫。焚书坑儒，使史书损失最大。西汉王朝“休养生息”。武帝时，西汉王朝进入了鼎盛时期。秦王朝二世而亡，只存在了短短的14年。汉初的君臣都在深刻的思索：为什么强大的秦王朝骤然灭亡？为何如此短命？新兴的汉王朝如何才能长治久安？陆贾的《楚汉春秋》汉初以无为求进取，促进恢弘的精神文化建设。汉武帝时，董仲舒以儒学为基础，主张大一统，天人合一，以神学作政治依据，重“天意”。天人关系问题成为此时研究的重点，是当时最大的课题。文学上，“大赋”这种文学形式非常兴旺，吸取《离骚》长篇大论的形式，恢弘博大，总览一切，气势博大。司马迁的《史记》，也是一样的恢弘博大，对周边国家都有记载。《史记》受到“大赋”的影响较大，此外，哲学上也深受董仲舒的影响。 第二节：司马迁和《史记》 司马迁是中国历史上第一重要的历史学家，被梁启超成为“史界太祖”。司马迁《史记》的撰成，是中国史学史上的一个重大事件，对中国史学影响巨大。 一、司马迁生平1、少年时代的家乡生活2、入仕前的壮游祖国山河。20岁以后，离家远游。这个过程对司马迁眼界的开阔、知识的积累和他进步的历史观的形成，都有极为巨大的影响。 3、入仕及宦途经历 4、36岁立志修史：一生的转折点 5、42岁开始著史 6、48岁自请宫刑 7、刑馀著史 8、《史记》宗旨：“仆窃不逊，近自托于无能之辞，网罗天下放失旧闻，考之行事，稽其成败兴坏之理，（上记轩辕，下至于兹，）凡百三十篇，亦欲以究天人之际，通古今之变，成一家之言。” 9、司马迁的著作：除《史记》和《报任安书》外，流传下来的还有《悲士不遇赋》一篇、《素王妙论》佚文四节，其他的都已经散失了，但就是《悲士不遇赋》这篇司马迁晚年的作品，也有人说是别人假借其名而伪造的。 二、《史记》的体例和内容 1、《史记》的体例分为五部分。“本纪”12篇，是编年体的大事记，是最高统治者的编年史。“世家”30篇，记载世代传家的政权人物等，分为三类：诸侯列国；汉朝的宰相、功臣，如萧何等；历史上的特殊地位的人物，如陈涉、孔子等。“书”8篇，涉及礼乐制度、历法、天文、地理、重大祭祀、经济财政等社会生活以及人与自然的关系等诸多方面，是一种综合论述的形式，以反映社会制度的变化为主，意在明其“损益”、“改易”之迹，“承蔽通变”之状。《汉书》后改为《志》。“表”10篇，有世表、年表、月表、人表等几种形式。是以谱牒的形式，厘清错综复杂的史事。“列传”70篇，记载各个时代不同阶层、不同类型的各种人物，为“扶义倜傥，不令己失时，立功名于天下”的各种历史人物立传。有专传、合传和类传的不同形式。这五种体例，并不是各自独立，而是互相配合，互为补充，从而形成一个不可分割的整体。郑樵说：“使百代而下，史官不能易其法，学者不能舍其书，《六经》之后，惟有此作。”赵翼说：“自此例一定，历代作史者，遂不能出其范围，信史家之极则也。”这五种体例都有前人的成就作为凭借。《史记》将这五种体例合为一书，自成一家，创立了纪传体。白寿彝先生认为“称《史记》为纪传体不恰当，实际是‘综合体’。” 2、《史记》是我国第一部纪传体通史： 通史的标准：①时间上：从古到今；②地域上：从南到北、从东到西，包括全国的广大地域；③内容上，包括政治、经济、文化、军事等各个方面。 *问题描述： 建立图的存储结构，能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。 1、邻接矩阵表示法: 设G=(V,E)是一个图，其中V={V1,V2,V3…,Vn}。G的邻接矩阵是一个他有下述性质的n阶方阵： 1，若(Vi,Vj)∈E 或 对于有向图，顶点Vi的出度OD(Vi)为邻接矩阵第i行元素之和，顶点Vi 的入度ID(Vi)为第i列元素之和。即 n n OD(Vi)＝∑A[i,j]，OD(Vi)＝∑A[j,i]） j=1j=1 用邻接矩阵也可以表示带权图，只要令 Wij, 若 数据结构实验报告 实验四图的应用 一、实验题目： 图的应用——xx优先／xx优先搜索遍历 二、实验内容： 很多涉及图上操作的算法都是以图的遍历操作为基础的。试编写一个算法，实现图的深度优先和广度优先搜索遍历操作。 要求： 以邻接矩阵或邻接表为存储结构，以用户指定的顶点为起始点，实现连通无向图的深度优先及广度优先搜索遍历，并输出遍历的结点序列。（注： 学号为奇数的同学使用邻接矩阵存储结构实现，学号为偶数的同学使用邻接矩阵实现） 提示： 首先，根据用户输入的顶点总数和边数，构造无向图，然后以用户输入的顶点为起始点，进行深度优先、广度优先搜索遍历，并输出遍历的结果。 三、程序源代码： #include int adjvex;//该弧所指向的顶点的位置 struct ArcNode *nextarc;//指向下一条弧的指针 }ArcNode; typedef struct VNode{ int data;//顶点信息 ArcNode *firstarc;//指向第一条依附该顶点的弧的指针}VNode,AdjList[MAX_VERTEX_NUM]; typedef struct{ AdjList vertices; }ALGraph; typedef struct QNode{ int data; struct QNode *next; }QNode,*QuePtr; typedef struct{ QuePtr front;//队头指针 QuePtr rear;//队尾指针 }LinkQue; void InitQue(LinkQue &q){} void EnQue(LinkQue &q,int e){} int DeQue(LinkQue &q){int e; 算法设计：深度优先遍历和广度优先遍历实现 深度优先遍历过程 1、图的遍历 和树的遍历类似，图的遍历也是从某个顶点出发，沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。它是许多图的算法的基础。 深度优先遍历和广度优先遍历是最为重要的两种遍历图的方法。它们对无向图和有向图均适用。 注意： 以下假定遍历过程中访问顶点的操作是简单地输出顶点。 2、布尔向量visited[0．．n-1]的设置 图中任一顶点都可能和其它顶点相邻接。在访问了某顶点之后，又可能顺着某条回路又回到了该顶点。为了避免重复访问同一个顶点，必须记住每个已访问的顶点。为此，可设一布尔向量visited[0．．n-1]，其初值为假，一旦访问了顶点Vi之后，便将visited[i]置为真。 -------------------------- 深度优先遍历(Depth-First Traversal) 1．图的深度优先遍历的递归定义 假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。 图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-First Search)。相应地，用此方法遍历图就很自然地称之为图的深度优先遍历。 2、深度优先搜索的过程 设x是当前被访问顶点，在对x做过访问标记后，选择一条从x出发的未检测过的 重庆邮电大学 数学大类专业 2008级《数学建模与数学实验》课程设计 设计题目：图的深度优先搜索遍历算法分析及其应用设计时间：2010.9.7-----2010.9. 12 班级： 学号： 指导教师： 图的深度优先搜索遍历算法分析及其应用 摘要:文章介绍了图论，图的基本概念及其图的表示方法。详细的分析了图中以邻接表为存储结构进行的图的深度优先搜索遍历的算法，并且在VC++环境中实现其算法的过程，对运行记过做了一定量的分析，最后介绍了基于该算法的一些应用。 关键词：图；深度优先搜索；遍历；算法 图论〔Graph Theory〕是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。 图（Graph）是一种较线性表和树更复杂的数据结构，图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。因此，在研究有关图的问题时，要考虑图中每个顶点的信息，访问图中的各个顶点，而访问图中各个顶点的操作过程即使图的遍历，图的遍历算法是求解图的连通性问题，拓扑排序和求关键路径等算法的基础。 1图的三元组定义 图Ｇ是一个三元组由集合V，E和关联函数组成，记为：G=（V，E，W（G））。其中V是顶点的集合，表示V（G）={V1，V2，V3，……Vn}，V（Ｇ）≠ＮＵＬＬ。Ｅ是V中的点偶对的有穷集，表示为E（G）={e1，e2，e3……em}，其中ei为 《秦汉史》期末考试新1 班级：默认班级成绩：分 一、单选题（题数：50，共分） 1 秦代实行中央集权后最早建立的是（）。分 A、 郡县制 B、 州县制 C、 省县制 D、 以上答案均错误 正确答案： A 我的答案：A 2 州在（）以后成了郡以上的行政单位。分 A、 西汉末年 B、 西汉初年 C、 东汉末年 D、 东汉初年 正确答案： C 我的答案：C 3 东汉的开朝皇帝刘秀起兵时的身份是（）。分 A、 豪强 B、 王嗣 C、 庶民 D、 循吏 正确答案： A 我的答案：A 4 周秦之变的主要改变是（）。 分 A、 消灭剥削者 B、 消灭阶级 C、 消除贫富分化 D、 消除社会矛盾 正确答案： B 我的答案：B 5 孟子所在的时代“君”是指（）。 分 A、 国王 B、 天子 C、 国民 D、 以上答案都错误 正确答案： C 我的答案：B 6 法家思想最早产生于（）。 分 A、 秦国 B、 齐国 C、 燕国 D、 赵国 正确答案： B 我的答案：B 7 秦汉社会一个很明显的特点是（）。分 A、 非宗法性 B、 宗法性 C、 家族群居性 D、 小家庭性 正确答案： A 我的答案：A 8 秦制的成功在于（）。 分 A、 发展经济 B、 使人人平等 C、 改善人民生活 D、 提高国际地位 正确答案： B 我的答案：B 9 汉代基层设置的官员在名称上往往和（）是对应的。分 A、 皇宫的等级 B、 社会的等级 C、 上级的官吏 D、 下级的官吏 正确答案： C 我的答案：B 10 庄子所代表的道家的特点是将一切（）。 分 A、 绝对化 B、 相对化 C、 理想化 D、 完美化 正确答案： B 我的答案：B 11 法家思想的特征之一是（）。 分 A、 反对社会福利 B、 主张救济穷人 C、 主张公平分配 D、 反对按劳分配 正确答案： A 我的答案：A 12 韩非子提出的观念“无先王之语，以吏为师”中的“先王”是指（）。分图的深度优先遍历算法课程设计报告
秦汉史期末考试题(含答案)
《秦汉史》期末考试 新 1
班级：默认班级 成绩： 78.0 分
一、 单选题（题数：50，共 50.0 分）
1
秦代实行中央集权后最早建立的是（）。
1.0 分
?
A、
郡县制
?
B、
州县制
?
C、
省县制
?
D、
以上答案均错误
正确答案： A 我的答案：A
2
州在（）以后成了郡以上的行政单位。
1.0 分
?
A、
西汉末年
?
B、
西汉初年
?
C、
东汉末年
D、
东汉初年
正确答案： C 我的答案：C
3
东汉的开朝皇帝刘秀起兵时的身份是（）。
1.0 分
?
A、
豪强
?
B、
王嗣
?
C、
庶民
?
D、
循吏
正确答案： A 我的答案：A
4
周秦之变的主要改变是（）。
1.0 分
?
A、
消灭剥削者
?
B、
消灭阶级
?
C、
消除贫富分化
?
D、
正确答案： B 我的答案：B
5
孟子所在的时代“君”是指（）。
0.0 分
?
A、
国王
?
B、
天子
?
C、
国民
?
D、
以上答案都错误
正确答案： C 我的答案：B
6
法家思想最早产生于（）。
1.0 分
?
A、
秦国
?
B、
齐国
?
C、
燕国
?
D、
赵国
正确答案： B 我的答案：B连通图深度优先遍历
秦汉史期尔雅末考试答案 (2)
深度优先遍历(邻接矩阵)
图的深度优先遍历实验报告
超星尔雅秦汉史答案超全版
邻接矩阵的深度优先遍历
图的深度优先遍历和广度优先遍历
广度优先搜索和深度优先搜索
邻接矩阵表示图深度广度优先遍历
2016尔雅秦汉史考试答案讲解
一、 单选题（题数：50，共 50.0 分）
1
秦代实行中央集权后最早建立的是（）。
1.0
?
郡县制
分
A、
?
州县制
B、
?
省县制
C、
?
D、
以上答案均错误
我的答案：A
2
州在（）以后成了郡以上的行政单位。
1.0
?
西汉末年
分
A、
?
B、
西汉初年
?
C、
东汉末年
?
D、
东汉初年
3
东汉的开朝皇帝刘秀起兵时的身份是（）。
1.0
?
豪强
分
A、
?
王嗣
B、
?
庶民
C、
?
循吏
D、
我的答案：A
4
周秦之变的主要改变是（）。
1.0
?
分
A、
消灭剥削者
?
B、
消灭阶级
?
C、
消除贫富分化
?
D、
消除社会矛盾
我的答案：B
5
0.0
?
国王
分
A、
?
天子
B、
?
国民
C、
?
D、
以上答案都错误
我的答案：B
6
法家思想最早产生于（）。
1.0
?
秦国
分
A、
?
齐国
B、
?
燕国
C、
?
赵国
D、
我的答案：B
7
秦汉社会一个很明显的特点是（）。采用非递归深度优先遍历算法
第二章 秦汉史学
邻接矩阵表示图_深度_广度优先遍历
实验四-图的应用――深度优先／广度优先搜索遍历
算法设计：深度优先遍历和广度优先遍历
图的深度优先搜索遍历算法分析及其应用
秦汉史期末考试题(含答案)
相关主题
文本预览