广工anyview数据结构第七章

/**********

【题目】试写一算法，如果三个整数a，b和c的值 不是依次非递增的，则通过交换，令其为非递增。 ***********/

void Descend(int &a, int &b, int &c) /* 通过交换，令 a >= b >= c */ {

if(c<=b&&b<=a) return; else {

if(a

void swap(int &a,int &b) {

int temp; temp=a; a=b; b=a; }

/**********

【题目】试编写算法求一元多项式 P(x) = a0 + a1x + a2x^2 + ... + anx^n

的值P(x0)，并确定算法中每一语句的执行次数和整个算法 的时间复杂度。 **********/

float Polynomial(int n, int a[], float x)

/* 求一元多项式的值P(x)。 */ /* 数组a的元素a[i]为i次项的系数，i=0,...,n */ {

float answer =a[0]; float temp= 1.0; for(int

习题七 图

一、单项选择题

1.设有无向图G=（V，E）和G’=（V’,E’）,如G’为G的生成树，则下面不正确的说法是（ ）

A．G’为G的子图 B．G’为G的连通分量 C．G’为G的极小连通子图且V’=V D．G’是G的无环子图 2.任何一个带权的无向连通图的最小生成树（ ）

A．只有一棵 B．有一棵或多棵 C．一定有多棵 D．可能不存在 3．以下说法正确的是（ ）

A．连通分量是无向图中的极小连通子图。 B．强连通分量是有向图中的极大强连通子图。

C．在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧。 D．对有向图G,如果从任意顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图。 4．图中有关路径的定义是（ ）。

A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列 C．由不同边所形成的序列 D．上述定义都不是 5．设无向图的顶点个数为n，则该图最多有（ ）条边。

2

A．n-1 B．n(n-1)/2 C

第七章 图

一、选择题

1．图中有关路径的定义是（ ）。【北方交通大学 2001 一、24 （2分）】

A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列 C．由不同边所形成的序列 D．上述定义都不是 2．设无向图的顶点个数为n，则该图最多有（ ）条边。

2

A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n 【清华大学 1998 一、5 （2分）】【西安电子科技大 1998 一、6 （2分）】 【北京航空航天大学 1999 一、7 （2分）】

3．一个n个顶点的连通无向图，其边的个数至少为（ ）。【浙江大学 1999 四、4 (4分)】

A．n-1 B．n C．n+1 D．nlogn； 4．要连通具有n个顶点的有向图，至少需要（ ）条边。【北京航空航天大学 2000 一、6(2分）】

A．n-l B．n C．n+l

第七章 图 试题

一、单项选择题

1. 在无向图中定义顶点的度为与它相关联的（ ）的数目。

A. 顶点 B. 边 C. 权 D. 权值

2. 在无向图中定义顶点 vi与vj之间的路径为从vi到达vj的一个（ ）。

A. 顶点序列 B. 边序列 C. 权值总和 D. 边的条数

3. 图的简单路径是指（ ）不重复的路径。

A. 权值 B. 顶点 C. 边

D. 边与顶点均

4. 设无向图的顶点个数为n，则该图最多有（ ）条边。

A. n-1 B. n(n-1)/2 C. n(n+1)/2 5. n个顶点的连通图至少有（ ）条边。

A. n-1 B. n

C. n+1

D. n(n-1)

D. 0

6. 在一个无向图中，所有顶点的度数之和等于所有边数的 ( ) 倍。

A. 3 B. 2 C. 1 D. 1/2 7. 若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个 ( )。

A. 上三角矩阵 B. 稀疏矩阵 C. 对角矩阵 D. 对称矩阵

8. 图的深度优先搜索类似于树的（

/**********

【题目】试写一算法，如果三个整数a，b和c的值 不是依次非递增的，则通过交换，令其为非递增。 ***********/

void Descend(int &a, int &b, int &c) /* 通过交换，令 a >= b >= c */ { int t;

if(a<=b){t=a;a=b;b=t;} if(b<=c){t=b;b=c;c=t;} if(a<=b){t=a;a=b;b=t;} }

/**********

【题目】试编写算法求一元多项式 P(x) = a0 + a1x + a2x^2 + ... + anx^n

的值P(x0)，并确定算法中每一语句的执行次数和整个算法 的时间复杂度。 **********/

float Polynomial(int n, int a[], float x)

/* 求一元多项式的值P(x)。 */ /* 数组a的元素a[i]为i次项的系数，i=0,...,n */ { int i,j;float p=0,t=1; for(i=0;i<=n;i++) {

p=a[i]*t+p; t=t*x ; } return p; }

/**********

【题目】已知k阶裴波那契序列的定义为 f(0)=0, f(1)=0, ..., f(k-2)=0, f

第七章 图

一、选择题

1．图中有关路径的定义是（ ）。【北方交通大学 2001 一、24 （2分）】

A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列 C．由不同边所形成的序列 D．上述定义都不是 2．设无向图的顶点个数为n，则该图最多有（ ）条边。

2

A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n 【清华大学 1998 一、5 （2分）】【西安电子科技大 1998 一、6 （2分）】 【北京航空航天大学 1999 一、7 （2分）】

3．一个n个顶点的连通无向图，其边的个数至少为（ ）。【浙江大学 1999 四、4 (4分)】

A．n-1 B．n C．n+1 D．nlogn； 4．要连通具有n个顶点的有向图，至少需要（ ）条边。【北京航空航天大学 2000 一、6(2分）】

A．n-l B．n C．n+l

第七章 图

一、选择题

1．图中有关路径的定义是（ ）。【北方交通大学 2001 一、24 （2分）】

A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列 C．由不同边所形成的序列 D．上述定义都不是 2．设无向图的顶点个数为n，则该图最多有（ ）条边。

2

A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n 【清华大学 1998 一、5 （2分）】【西安电子科技大 1998 一、6 （2分）】 【北京航空航天大学 1999 一、7 （2分）】

3．一个n个顶点的连通无向图，其边的个数至少为（ ）。【浙江大学 1999 四、4 (4分)】

A．n-1 B．n C．n+1 D．nlogn； 4．要连通具有n个顶点的有向图，至少需要（ ）条边。【北京航空航天大学 2000 一、6(2分）】

A．n-l B．n C．n+l D．2n 5．n个结点

一、单选题（每题1分，共16分）

（ C ）1. 在一个图中，所有顶点的度数之和等于图的边数的 倍。

A．1/2 B. 1 C. 2 D. 4 （ B ）2. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍。 A．1/2 B. 1 C. 2 D. 4 （ B ）3. 有8个结点的无向图最多有 条边。

A．14 B. 28 C. 56 D. 112 （ C ）4. 有8个结点的无向连通图最少有 条边。

A．5 B. 6 C. 7 D. 8 （ C ）5. 有8个结点的有向完全图有 条边。

A．14

第七章

结构游戏

结构游戏常常被人们称为培养建筑师、工程师的游戏，与角色游戏、表演游戏并称三大创造性游戏。结构游戏是幼儿园开展较为普及、幼儿接触时间比较长的游戏，对发展幼儿的精细动作、手眼协调能力、创造力和想象力，促进幼儿了解各种事物的外形特征、操作材料及其物理属性等均有积极的促进作用。

第一节 结构游戏概述

“结构”一词是拉丁文Construstlc演变而来，它的愿意是建筑，即构造活动。一般来讲，结构游戏是指儿童利用各种结构材料或玩具进行构造活动的游戏。

最早的结构游戏是用小木棍、小木块、小木片、石子、泥、沙等常见材料进行拼搭的建筑游戏。随着社会经济文化的飞速发展，结构游戏得到了较快发展，在游戏的材料、玩法、结构物的造型等方面都发生了较大的变化。出现了塑料、金属等多种材料，产生了接插与镶嵌、黏合与螺旋等多种新的结构技能，结构物的造型也从周围生活中常见的物品扩展到动物、人物、科技新产品等。

幼儿园常用的结构材料有积木、积塑、泥塑、沙土、冰雪、竹制材料、金属材料等。

一、 结构游戏的特点

结构游戏和角色游戏的相同点在于，它们都是通过幼儿的想象，创造性地反映周围生活。两者的不同之处在于，结构游戏是通过使用一些

结构材料来建筑或构造各种建筑物和物体，通过操作、造型活

1.题目

采用顺序存储结构实现堆的筛选，建造，插入，删除，排序等操作。 ADT Heap{

基本操作： void MakeHeap(Heap &H, RcdType *E, int n, int size, int tag) 操作结果：构造一个堆； Destroy(&H)

初始条件：堆已存在。 操作结果：销毁堆H。 GetLength(H)

初始条件：堆H已存在。

操作结果：返回堆H中元素个数。 Get(L, i, &e)

初始条件：堆H已存在，1≤i≤LengthList(L)。 操作结果：用e返回堆H中第i个元素的值。 RemoveFirstHeap(H,e); 初始条件：堆H已存在

操作结果：删除第一个节点

insertH