湖南大学数据结构试验5最短路径问题

HUNAN UNIVERSITY 课程实习报告

题目：最短路径问题

学生姓名刘乐

学生学号20080820208

专业班级通信工程2班

指导老师朱宁波

完成日期2010年5月17日

一、需求分析：

1.本程序来自于实际问题中选择带权值交通路线，使得费用最低从

某一场所到另一场所。

2.本程序要求：

（1）从文件中读取有限网中顶点的数量和顶点间票价的矩阵。（2）以用户指定的起点和终点，输出从起点到终点的花费。

3在dos系统下输入起点和终点。并输出最短路径。

4测试数据：

二、概要设计

为实现上述功能需要用到图的存储结构。

利用邻接矩阵构造图，并求出某一顶点到另一顶点的最短路径并打印输出。

算法基本思想

根据题目要求用弗洛伊德算法可以实现两点最短路径问题。弗洛伊德算法仍然使用图的邻接矩阵arcs[n+1][n+1]来存储带权有向图。算法的基本思想是:设置一个n x n的矩阵A(k)，其中除对角线的元素都等于0外，其它元素a(k)[i][j]表示顶点i到顶点j的路径长度，K表示运算步骤。开始时，以任意两个顶点之间的有向边的权值作为路径长度，没有有向边时，路径长度为∞，当K=0时, A (0)[i][j]=arcs[i][j]，以后逐步尝试在原路径中加入其它顶点作为中间顶点，如果增加中间顶点后，得到的路径比原来的路径长度减少了，则以此新路径代替原路径，修改矩阵元素。

程序设计流程

程序由三个模块组成：

（1）输入模块：起点终点和各点间的权值这都从文件中读取。

（2）求最短路径模块：通过弗洛伊德算法求出起点终点最短路径。

（3）输出模块：完成弗洛伊德算法后，把最短路径给出，并给出具体路径。

三、详细设计

1.因为设计中顶点数和权值都是从文件中读取，因此初始化一个最大顶点

数和最大权值。

#define mvnum 100 //最大顶点数

#define maxint 10000

2 本程序用图来实现故要定义图的存储结构

typedef struct{

char vexs[mvnum];

int arcs[mvnum][mvnum];

}MGraph;//定义图的存储结构

弗洛伊德算法求最短路径：

void Floyd(MGraph *G,int n)

{

int i,j,k,v,w;

for(i=1;i<=n;i++)//设置路径长度和路径初值

for(j=1;j<=n;j++)

{

if(G->arcs[i][j]!=maxint)

P[i][j]=j;//j是i的后继

else

P[i][j]=0;

D[i][j]=G->arcs[i][j];

}

for(k=1;k<=n;k++)

{//做K次迭代，每次均试图将顶点扩充到当前求得的i到j的最短路径上

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

{

if(D[i][k]+D[k][j]

{

D[i][j]=D[i][k]+D[k][j];//修改路径长度

P[i][j]=P[i][k];

}

}

}

printf("输入起点：v:");

scanf("%d",&v);

printf("输入终点：w:");

scanf("%d",&w);

k=P[v][w];//K为起点V的后继顶点

if(k==0)

{

printf("顶点%d到%d无路径！\n",v,w);

printf("\n");

}

else

{

if(v!=w)

{

printf("从顶点%d到%d的最短路径是：%d",v,w,v);

while(k!=w)

{

printf("→%d",k);//输出后继顶点

k=P[k][w];//继续找下一个后继顶点

}

printf("→%d",w);//输出终点W

printf("路径长度：%d\n",D[v][w]);

printf("\n");

}

else

printf("您已经在这个地方了！\n");

printf("\n");

}

}//Floyd

主程序：

void main()

{

FILE *fp;

MGraph *G;

int n,e,v;

int xz=1;

G=(MGraph *)malloc(sizeof(MGraph));

printf("输入图中顶点个数和边数n,e: ");

fp=fopen("chengxu.txt","r");

fscanf(fp,"%d,%d\n",&n,&e); 从文件中读取n，e

printf("%d,%d\n",n,e);

int i,j,k,w;

for(i=1;i<=n;i++)//输入顶点信息

G->vexs[i]=(char)i;

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

G->arcs[i][j]=maxint;//初始化邻接矩阵

printf("请输入与各边相关的顶点及边的权值：\n");

for(k=1;k<=e;k++) //读入e条边，建立邻接矩阵

{

fscanf(fp,"%d,%d,%d",&i,&j,&w);

G->arcs[i][j]=w;

}

for(i=1;i<=n;i++)

{

for(j=1;j<=n;j++)

printf("%d\t",G->arcs[i][j]);

printf("\n");

}

printf("有向图的存储结构建立完毕！\n");

printf("\n");

fclose(fp);

while(xz!=0)

{

printf("******求点之间的最短路径******\n");

printf("================================\n");

printf("求任意的两个点之间的最短路径\n");

printf("================================\n");

printf(" 请选择：2 ，选择0退出：");

scanf("%d",&xz);

if(xz==2)

Floyd(G,n);

printf("结束求最短路径，再见！\n");

printf("\n");

}

}

四、算法具体步骤：

弗洛伊德算法流程图：

算法的时空分析：算法时间复杂度同迪杰斯特拉算法时间复杂度相同也为o（n^3）

输入输出格式：

五、实验心得：

本次实验主要是在宿舍完成的，因此去了就是让助教老师看了一下就通过了，因为书上学到这个弗洛伊德算法比迪杰斯特拉算法简单易理解些，我就主要用这种方法实现了，这次实验不仅熟悉了文件的读取内容，而且对新学的内容有了更深的理解，我想数据结构这门课就是需要时刻与对应程序问题结合才能真正的融会贯通，我在网上搜集了一些数据结构各章节有关的程序，正在看，相信会有更多提高。

六、实验源程序：

#include

#include

#define mvnum 100 //最大顶点数

#define maxint 10000

enum boolean{FALSE,TURE};

int D1[mvnum];

int D2[mvnum],P2[mvnum];

int D[mvnum][mvnum],P[mvnum][mvnum];

typedef struct{

char vexs[mvnum];

int arcs[mvnum][mvnum];

}MGraph;//定义图的存储结构

void Floyd(MGraph *G,int n)

{

int i,j,k,v,w;

for(i=1;i<=n;i++)//设置路径长度和路径初值

for(j=1;j<=n;j++)

{

if(G->arcs[i][j]!=maxint)

P[i][j]=j;//j是i的后继

else

P[i][j]=0;

D[i][j]=G->arcs[i][j];

}

for(k=1;k<=n;k++)

{//做K次迭代，每次均试图将顶点扩充到当前求得的i到j的最短路径上

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

{

if(D[i][k]+D[k][j]

{

D[i][j]=D[i][k]+D[k][j];//修改路径长度

P[i][j]=P[i][k];

}

}

}

printf("输入起点：v:");

scanf("%d",&v);

printf("输入终点：w:");

scanf("%d",&w);

k=P[v][w];//K为起点V的后继顶点

if(k==0)

{

printf("顶点%d到%d无路径！\n",v,w);

printf("\n");

}

else

{

if(v!=w)

{

printf("从顶点%d到%d的最短路径是：%d",v,w,v);

while(k!=w)

{

printf("→%d",k);//输出后继顶点

k=P[k][w];//继续找下一个后继顶点

}

printf("→%d",w);//输出终点W

printf("路径长度：%d\n",D[v][w]);

printf("\n");

}

else

printf("您已经在这个地方了！\n");

printf("\n");

}

}//Floyd

void main()

{

FILE *fp;

MGraph *G;

int n,e,v;

int xz=1;

G=(MGraph *)malloc(sizeof(MGraph));

printf("输入图中顶点个数和边数n,e: ");

fp=fopen("chengxu.txt","r");

fscanf(fp,"%d,%d\n",&n,&e);

printf("%d,%d\n",n,e);

int i,j,k,w;

for(i=1;i<=n;i++)//输入顶点信息

G->vexs[i]=(char)i;

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

G->arcs[i][j]=maxint;//初始化邻接矩阵printf("请输入与各边相关的顶点及边的权值：\n");

for(k=1;k<=e;k++) //读入e条边，建立邻接矩阵

{

fscanf(fp,"%d,%d,%d",&i,&j,&w);

G->arcs[i][j]=w;

}

for(i=1;i<=n;i++)

{

for(j=1;j<=n;j++)

printf("%d\t",G->arcs[i][j]);

printf("\n");

}

printf("有向图的存储结构建立完毕！\n");

printf("\n");

fclose(fp);

while(xz!=0)

{

printf("******求点之间的最短路径******\n");

printf("================================\n");

printf("求任意的两个点之间的最短路径\n");

printf("================================\n");

printf(" 请选择：2 ，选择0退出：");

scanf("%d",&xz);

if(xz==2)

Floyd(G,n);

printf("结束求最短路径，再见！\n");

printf("\n");

}

}

(完整word版)数据结构课后习题及答案

填空题(10 * 1 '= 10') 一、概念题 22当对一个线性表经常进行的是插入和删除操作时，采用链式存储结构为宜。 23当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，最好采用顺序存储结构。 2.6. 带头结点的单链表L中只有一个元素结点的条件是L->Next->Next==Null。 36循环队列的引入，目的是为了克服假溢出。 4.2. 长度为0的字符串称为空串。 4.5. 组成串的数据元素只能是字符。 4.8. 设T和P是两个给定的串，在T中寻找等于P的子串的过程称为模式匹配，又称P为模式。 7.2. 为了实现图的广度优先搜索，除一个标志数组标志已访问的图的结点外，还需要队列存放被访问的结点实现遍历。 5.7. 广义表的深度是广义表中括号的重数 7.8. 有向图G可拓扑排序的判别条件是有无回路。 7.9. 若要求一个稠密图的最小生成树，最好用Prim算法求解。 8.8. 直接定址法法构造的哈希函数肯定不会发生冲突。 9.2. 排序算法所花费的时间，通常用在数据的比较和交换两大操作。 1.1. 通常从正确性、可读性、健壮性、时空效率等几个方面评价算法的(包括程序)的质量。 1.2. 对于给定的n元素，可以构造出的逻辑结构有集合关系、线性关系树形关系、图状关系四种。 1.3. 存储结构主要有顺序存储、链式存储、索引存储、散列存储四种。 1.4. 抽象数据类型的定义仅取决于它的一组逻辑特性，而与存储结构无关，即不论其内部结构如何变化，只要它的数学特性不 变，都不影响其外部使用。 1.5. 一个算法具有五大特性：有穷性、确定性、可行性，有零个或多个输入、有一个或多个输入。 2.8. 在双向链表结构中，若要求在p指针所指的结点之前插入指针为s所指的结点，则需执行下列语句： s_>prior= p_>prior; s->next= p; p_>prior- next= s; p_>prior= s;。 2.9. 在单链表中设置头结点的作用是不管单链表是否为空表，头结点的指针均不空，并使得对单链表的操作 (如插入和删除)在各种情况下统一。 3.1. 队列是限制在表的一端进行插入和在另一端进行删除的线性表，其运算遵循先进先出原则。 3.2 .栈是限定尽在表位进行插入或删除操作的线性表。 3.5. 在链式队列中，判定只有一个结点的条件是(Q->rear==Q->fro nt)&&(Q->rear!=NULL) 。 3.7. 已知链队列的头尾指针分别是f和r，则将x入队的操作序列是node *p=(node *)malloc(node); p->next=x;] p_>next=NULL; if(r) {r->next=p; r=p;} else {r=p; f=p;}。 3.8. 循环队列的满与空的条件是(rear+1)%MAXSIZE==fornt 和(fron t=-1 &&rear+ ^=MAXSIZE) 。 4.3. 串是一种特殊的线性表，其特殊性表现在数据元素都是由字符组成。 4.7. 字符串存储密度是串值所占存储位和实际分配位的比值，在字符串的链式存储结构中其结点大小是可变的。 5.3. 所谓稀疏矩阵指的是矩阵中非零元素远远小于元素总数，则称该矩阵为矩阵中非零元素远远小于元素总数，则称该矩阵为稀 疏矩阵。 5.4. —维数组的逻辑结构是线性结构，存储结构是顺序存储结构；对二维或多维数组，分别按行优先和列优先两种?不同的存储 方式。 7.4. 在有向图的邻接矩阵表示中，计算第i个顶点入度的方法是求邻接矩阵中第?i列非10元素的个数。 7.10. AOV网中，结点表示活动，边表示活动之间的优先关系，AOE网中，结点表示事件，边表示活动。 9.1. 按排序过程中依据不同原则对内部排序方法进行分类，主要有选择排序、交换排序、插入排序归并排序等4类。 9.3 .在堆排序、快速排序和归并排序中若只从排序结果的稳定性考虑，则应选择归并排序方法；若只从平均情况下 排序最快考虑，则应选择快速排序方法；若只从最坏情况下排序最快且要节省类存考虑，则应选择堆排序方法。 9.4. 直接插入排序用监视哨的作用是存当前要的插入记录，可又省去查找插入位置时对是否出界的判断。 9.6. 设表中元素的初始状态是按键值递增的，则直接插入排序最省时间，快速排序最费时间。 4.9. 下列程序判断字符串s是否对称，对称则返回1,否则返回0;如？(abba”返回1, ? (”abab”)返回0. Int f (char*s) { Int i=0,j=0;

湖南大学实验报告

HUNAN UNIVERSITY C++ 学生姓名李国龙 学生学号201408010211 专业班级计算机科学与技术 指导老师杨圣洪 2015年12月 30日

一、实验原理：运用MFC的知识编写一个系统，实现二进制文件的创建，读取，查询，插入，修改，删除，排序，索引，基于索引的查询等功能。 二、实验目标：掌握MFC的相关知识，学会利用MFC进行文件操作系统的编写。 三、实验设计： 1、建立框架 利用 MFC Exe 模板建立 MFC 的基础界面，其中第 3 步中不选“ActiveX 控件”，在第 5 步中选择“作为静态的DLL”，其他取默认值，等你熟练后，你再百度或搜狗找办法，定制所你的喜欢的模式。项目名称为 Lt13DTextFile。建立菜单：我的文件、我的编辑在“我的文件”下方建：建立文本文件 ID_MENUITEMFILENEW、读取文本文件ID_MENUITEMFILEREAD、查询单条记录ID_MENUITEMQUERYONE、查询多条记录 ID_MENUITEMQUERYM 在“ 我的编辑” 下方建：修改 ID_MENUITEMEDITMODI 、删除ID_MENUITEMEDITDEL 、插入 ID_MENUITEMEDITINSERT 、排序ID_MENUITEMEDITSORT1 、排序 2 ID_MENUITEMEDITSORT2 、索引ID_MENUITEMEDITINDEX、根据索引查询ID_MENUITEMEDITQUERYINDEX。 单击后显示一句话。先建立菜单系统，为每个菜单项的单击事件写

上 MessageBox(NULL,"函数名","测试 ",MB_OK)，等将来建立相应对话框后，再进行修改。由于保存在 LT13DTextFileView.cpp 即 View 文件中，显示对话框的命令为：voidCLt13DTextFileView::OnMenuitemeditqueryindex() { MessageBox("根据索引文件快速查询","初始代码",MB_OK); } 2、建立数据结构类 StudScore 在当前项目中建立 StudScore.h，将 LT12B 中同名文件的内容复制过来。再新建 StudScore.cpp，当我将 LT12B::StudScore.cpp 代码贴到当前文件中，再编译时出现如下错误：studscore.cpp(248) : fatal error C1010: unexpected end of file while looking for precompiled header directive，百度一下在最前面加上“#include"stdafx.h"”，这是将普通的 DOSAPP 迁移到 MFC 时发生的现象，是正常的！因为不符合 MFC 的规范。 3、建立文件操作类 StudScoreAFile 在当前项目中建立 studScoreAFile.h，将 LT12B 中同名文件的内容复制过来。建立 studScoreAFile.cpp，复制 LT12B 中相关代码，可以要进行修改，加上 include"stdafx.h"后，编译竟然能能通过，不是说 MFC 与 DOSAPP 中 C++的文件读写操作不一样吧？不再是流媒体 ofstream 或 iftream，而是采用 CStdioFile 吗？先试试看。经实际测试，只需要将以上函数中 stringstream sdata 换成

数据结构课后习题及答案

填空题（10 * 1’ = 10’） 一、概念题 .当对一个线性表经常进行的是插入和删除操作时，采用链式存储结构为宜。 .当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，最好采用顺序存储结构。 .带头结点的单链表L中只有一个元素结点的条件是L->Next->Next==Null。 .循环队列的引入，目的是为了克服假溢出。 .长度为0的字符串称为空串。 .组成串的数据元素只能是字符。 .设T和P是两个给定的串，在T中寻找等于P的子串的过程称为模式匹配，又称P为模式。 .为了实现图的广度优先搜索，除一个标志数组标志已访问的图的结点外，还需要队列存放被访问的结点实现遍历。 .广义表的深度是广义表中括号的重数 .有向图G可拓扑排序的判别条件是有无回路。 .若要求一个稠密图的最小生成树，最好用Prim算法求解。 . 直接定址法法构造的哈希函数肯定不会发生冲突。 .排序算法所花费的时间，通常用在数据的比较和交换两大操作。 .通常从正确性﹑可读性﹑健壮性﹑时空效率等几个方面评价算法的（包括程序）的质量。 .对于给定的n元素，可以构造出的逻辑结构有集合关系﹑线性关系树形关系﹑图状关系四种。 .存储结构主要有顺序存储﹑链式存储﹑索引存储﹑散列存储四种。 .抽象数据类型的定义仅取决于它的一组逻辑特性，而与存储结构无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部使用。 .一个算法具有五大特性：有穷性﹑确定性﹑可行性，有零个或多个输入﹑有一个或多个输入。 .在双向链表结构中，若要求在p指针所指的结点之前插入指针为s所指的结点，则需执行下列语句：s->prior= p->prior; s->next= p; p->prior- next= s; p->prior= s;。 .在单链表中设置头结点的作用是不管单链表是否为空表，头结点的指针均不空，并使得对单链表的操作（如插入和删除）在各种情况下统一。 .队列是限制在表的一端进行插入和在另一端进行删除的线性表，其运算遵循先进先出原则。 .栈是限定尽在表位进行插入或删除操作的线性表。 .在链式队列中，判定只有一个结点的条件是(Q->rear==Q->front)&&(Q->rear!=NULL)。 .已知链队列的头尾指针分别是f和r，则将x入队的操作序列是node *p=(node *)malloc(node); p->next=x; p->next=NULL; if(r) {r->next=p; r=p;} else {r=p; f=p;}。 .循环队列的满与空的条件是(rear+1)%MAXSIZE==fornt和(front=-1&&rear+1==MAXSIZE)。 .串是一种特殊的线性表，其特殊性表现在数据元素都是由字符组成。 .字符串存储密度是串值所占存储位和实际分配位的比值，在字符串的链式存储结构中其结点大小是可变的。 .所谓稀疏矩阵指的是矩阵中非零元素远远小于元素总数，则称该矩阵为矩阵中非零元素远远小于元素总数，则称该矩阵为稀疏矩阵。 .一维数组的逻辑结构是线性结构，存储结构是顺序存储结构；对二维或多维数组，分别按行优先和列优先两种不同的存储方式。 .在有向图的邻接矩阵表示中，计算第i个顶点入度的方法是求邻接矩阵中第i列非0元素的个数。 网中，结点表示活动，边表示活动之间的优先关系，AOE网中，结点表示事件，边表示活动。 .按排序过程中依据不同原则对内部排序方法进行分类，主要有选择排序﹑交换排序﹑插入排序归并排序等4类。 .在堆排序、快速排序和归并排序中若只从排序结果的稳定性考虑，则应选择归并排序方法；若只从平均情况下排序最快考虑，则应选择快速排序方法；若只从最坏情况下排序最快且要节省类存考虑，则应选择堆排序方法。 .直接插入排序用监视哨的作用是存当前要的插入记录，可又省去查找插入位置时对是否出界的判断。 .设表中元素的初始状态是按键值递增的，则直接插入排序最省时间，快速排序最费时间。 .下列程序判断字符串s是否对称，对称则返回1，否则返回0；如?(“abba”)返回1，?（”abab”）返回0. Int f (char*s) { Int i=0,j=0; 求串长*/

最新湖南大学数据结构第5次作业

1 1、画出对下列存储于数组中的值执行buildheap后得到的最大值堆： 2 10 5 12 3 2 1 8 7 9 4 3 4 先序遍历为12 10 4 1 2 9 5 8 3 7 5 中序遍历为1 4 2 10 5 9 12 3 8 7 6 7 2、假设某字母表各个字母的权如下： 8 Q Z F M T S O E 9 2 3 10 10 10 15 20 30 10 (a)按照这个字母表，一个包含n个字母的字符串采用Huffman编码在最差情 11 况下需要多少位？怎样的串会出现最差情况？ 12 13 在最差的情况下需要5*n位，当所有的字母都是Q或者Z的时候。 （b）按照这个字母表，包含n个字母的字符串采用Huffman编码在最佳情况 14 15 下需要多少位？怎样的串会出现最佳情况？ 16 在最佳的情况下需要2*n位，当所有的字母都是E或者O的时候。 17 （c）按照一个字母表，一个字母平均需要多少位？ 18 （2*30 + 2*20 + 3*15 + 3*10 + 3*10 + 4*10 + 5*3+ 5*2）/100 =2.7 19 ∴ 2.7

20 3、编写一个算法来判断两棵树是否相同。尽可能提高算法效率，并分析算法21 的运行时间代价。 22 template 23 bool Compare(GTNode* tree1, GTNode* tree2) { 24 GTNode *num1, *num2; 25 if (((tree1 == NULL) && (tree2 != NULL)) || 26 ((tree2 == NULL) && (tree1 != NULL))) 27 return 0; 28 if ((t1 == NULL) && (t2 == NULL)) return 1; 29 if (tree1->val() != tree2->val()) return 0; Num1 = tree1->left_child(); 30 31 Num2 = tree2->left_child(); 32 while(!((num1 == NULL) && (num2 == NULL))) { if (!Compare(num1, num2)) return false; 33 34 if (num1 != NULL) num1 = num1->right_value(); 35 if (num2 != NULL) num2 = num2->right_value(); 36 }} 37 38 O（n）

最新湖南大学数据结构第5次作业

1、画出对下列存储于数组中的值执行buildheap后得到的最大值堆： 10 5 12 3 2 1 8 7 9 4 先序遍历为12 10 4 1 2 9 5 8 3 7 中序遍历为1 4 2 10 5 9 12 3 8 7 2、假设某字母表各个字母的权如下： Q Z F M T S O E 2 3 10 10 10 15 20 30 (a)按照这个字母表，一个包含n个字母的字符串采用Huffman编码在最差情况下需要多少位？怎样的串会出现最差情况？ 在最差的情况下需要5*n位，当所有的字母都是Q或者Z的时候。 （b）按照这个字母表，包含n个字母的字符串采用Huffman编码在最佳情况下需要多少位？怎样的串会出现最佳情况？ 在最佳的情况下需要2*n位，当所有的字母都是E或者O的时候。 （c）按照一个字母表，一个字母平均需要多少位？ （2*30 + 2*20 + 3*15 + 3*10 + 3*10 + 4*10 + 5*3+ 5*2）/100 =2.7 ∴ 2.7 3、编写一个算法来判断两棵树是否相同。尽可能提高算法效率，并分析算法的运行时间代价。 template bool Compare(GTNode* tree1, GTNode* tree2) { GTNode *num1, *num2; if (((tree1 == NULL) && (tree2 != NULL)) || ((tree2 == NULL) && (tree1 != NULL))) return 0; if ((t1 == NULL) && (t2 == NULL)) return 1; if (tree1->val() != tree2->val()) return 0; Num1 = tree1->left_child();

11年湖南大学材料科学基础真题

2011年材料科学基础真题 一、名词解释（任选6题，每题5分，共30分） 1.键能曲线： 2.玻璃转变温度：当物质由固体加热或由熔体冷却时，在相当于晶态物质熔点绝对温度2/3~1/2温度附近出现热膨胀、比热容等性能的突变。该温度称为玻璃转变温度。 3.空间点阵：组成晶体的粒子（原子、离子或分子）在三维空间中形成有规律的某种对称排列，如果我们用点来代表组成晶体的粒子，这些点的空间排列就称为空间点阵。 4.非均匀形核：熔融液体冷却过程中，依附于母相中某种界面上的形核过程。 5.共格界面：所谓共格晶界，是指界面上的原子同时位于两相晶格的结点上，即两相的晶格是彼此衔接的界面上的原子为两者共有。 6.相图杠杆定律：某一成分的二元合金在某温度时，处于二元相图的两相区内，则两相之间的质量比可用“杠杆法则”求得。在此温度处做一条水平线与该两相区的相界线相交，两个交点内水平线被合金的成分垂线分成两段，两相的质量比与这两线段的长度成反比，用相对百分数表示，这个现象好像力学中的杠杆，所以称为“杠杆定律”。 7.位错滑移：在一定应力作用下，位错线沿滑移面移动的位错运动。 二、简答题（共10题，任选6题，每题10分） 1.MgO中加入Li2O后的空位浓度变化 2.热塑性材料与热固性材料的结构与性能区别 答：热塑性：具有线性和支化高分子链结构，加热后会变软，可反复加工成形。 热固性：具有体型（立体网状）高分子链结构，不溶于任何溶剂，也不能熔融，一旦定型后不能再改变形状，无法再生。 3.固溶体强度比纯金属强的原因 答：因为合金两类原子尺寸不同，引起点阵畸变，阻碍位错运动，造成固溶强化。

4.刃型位错与螺型位错的区别 答：刃型位错和螺型位错的异同点：①刃型位错位错线垂直于柏氏矢量，螺型位错位错线平行于柏氏矢量；②刃型位错柏氏矢量平行于滑移运动方向，螺型位错柏氏矢量垂直于滑移运动方向；③刃型位错可作攀移运动且只有一个滑移面，螺型位错只可作滑移运动但有无数个滑移面；④两者都可以用柏氏矢量表示。 5.施密特定律的表示及各量的物理意义 6.Ni的晶体结构为面心立方结构，其原子半径位r=0.1243nm，试求Ni的晶格常数及原子数，间隙种类 4r40.1243 a===0.3516nm 22 三、论述题（任选4题，每题15分） 1.与三种基本结合键的有关论述与弹性模量的关系 2.关于固溶体固溶度的影响因素 答：溶质原子以原子态溶入溶剂点阵中组成的单一均匀的固体；溶剂的点阵类型被保留。 影响固溶体的因素有： 1.原子尺寸因素。当溶剂、溶质原子直径尺寸相对差小于+15%时，有大的代位溶解度。 2.负电性因素。溶剂、溶质的负电性差越小溶解度越大，一般小于0.4~0.5会有较大溶解度。 3.电子浓度因素。有两方面的含义：一是原子价效应，即同一溶剂金属，溶质原

数据结构(C++版)课后作业1-6章带答案

数据结构(C++版)课后作业 1-6章带答案 标准化文件发布号：（9312-EUATWW-MWUB-WUNN-INNUL-DQQTY-

第1 章绪论 课后习题讲解 1. 填空 (1) 从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。 (2) 数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。 (3)算法在发生非法操作时可以作出处理的特性称为（）。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。 A 线性结构 B 非线性结构C 存储位置 D 指针 ⑵假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是（）。 A 树 B 图 C 线性表 D 集合 3. 判断题 (1) 每种数据结构都具备三个基本操作：插入、删除和查找。 第2 章线性表 课后习题讲解 1. 填空 ⑵顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的存储地址是（）。第5个元素的存储地址=第1个元素的存储地址＋(5－1)×2=108 ⑶设单链表中指针p 指向结点A，若要删除A的后继结点（假设A存在后继结点），则需修改指针的操作为（）。【解答】p->next=(p->next)->next ⑸非空的单循环链表由头指针head指示，则其尾结点（由指针p所指）满足（）。p->next=head ⑹在由尾指针rear指示的单循环链表中，在表尾插入一个结点s的操作序列是（）；删除开始结点的操作序列为（）。。【解答】s->next =rear->next; rear->next =s; rear =s; q=rear->next->next; rear->next->next=q->next; delete q; 2. 选择题 ⑴线性表的顺序存储结构是一种（）的存储结构，线性表的链接存储结构是一种（）的存储结构。 A 随机存取 B 顺序存取 C 索引存取 D 散列存取【解答】A，B 【分析】参见2.2.1。 ⑵线性表采用链接存储时，其地址（）。 A 必须是连续的 B 部分地址必须是连续的 C 一定是不连续的 D 连续与否均可以【解答】D 【分析】线性表的链接存储是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以连续，也可以不连续，甚至可以零散分布在内存中任意位置。

07年湖南大学材料科学基础真题

2007年材料科学基础真题 一、名词解释（30分） 1.孪晶：在切应力作用下，晶体的一部分沿一定的晶面（称为孪生面）和晶向（称为孪生方向）相对于另一部分晶体作均匀的切边时所长生的变形。孪生变形后，相邻两部分晶体的取向不同，恰好以孪生面为对称面形成镜像对称，形成孪晶。 2.柯肯达尔效应：在置换式固溶体中，由于两种原子以不同的速度相对扩散而造成标记面飘移的现象。 3.二次渗碳体：从奥氏体中析出的渗碳体称为二次渗碳体，其形态一般沿奥氏体晶界呈网状分布。 4.小角度晶界：界面两侧的晶粒取向差小于10o的晶界，有对称倾侧晶界和非对称倾侧晶界之分。 5.成分过冷：在合金凝固过程中，虽然液相中的实际温度分布一定，但是由于固液界面前沿液相中的溶质富集，导致液相的实际熔点下降。液相的实际凝固温度与熔体中的溶质的实际温度不一致，产生过冷现象。这种过冷是由于成分变化与实际温度分布这两个因素共同决定，这种过冷呈为成分过冷。 6.施密特（Schmid）因子：拉伸变形时，能够引起晶体滑移的分切应力t的大小取决于该滑移面和晶向的空间位置（）。t与拉伸应力σ间的关系为： 被称为取向因子，或称施密特因子，取向因子越大，则分切应力越大。 二、简答题（任选5题，50分） 1.简述柯垂尔气团和铃木气团的特点 答：溶质与刃型位错之间产生交互作用，形成柯垂尔气团。 溶质原子与层错交互作用形成铃木气团。 当材料的温度升高时，柯垂尔气团容易消失而铃木气团受温度的影响很小。 2.写出FCC、BCC和HCP晶胞中的四面体、八面体间隙数，致密度和原子配位数。 答：（1）间隙

FCC晶胞：4个八面体间隙，8个四面体间隙； BCC晶胞：6个八面体间隙；12个四面体间隙； HCP晶胞：6个八面体间隙；12个四面体间隙； （2）配位数 BCC：最近邻8个，考虑次近邻为（8+6）个 FCC：最近邻12个 HCP：理想状态12个，非理想状态（6+6）个 （3）致密度 BCC：0.68 FCC：0.74 HCP：0.74 3.简述固溶体和中间相的特点 答：（1）固溶体：固溶体保持了溶剂的晶格类型；成分可以在一定范围内变化，但不能用一个化学式来表示；不一定满足原子比或电子数比；在相图上为一个区域；具有明显的金属性质。例如具有一定的导电、导热性质和塑性等。固溶体中的结合键主要是金属键。 （2）中间相：金属与金属，或金属与非金属（氮、碳、氢、硅）之间形成的化合物总称为金属间化合物。由于金属间化合物在相图中处于相图的中间位置，故也称为中间相。 金属间化合物的晶体结构不同于构成它的纯组元，键合方式也有不同的类型，可能有离子键、共价键，但大多数仍然属于金属键类型。 4.相界面结构有哪几种形式，其界面能特点是什么？ 答：有共格、半共格和非共格三种。 共格界面的晶格畸变能最高，化学能最低；非共格界面的化学能最高而晶格畸变能最低；半共格界面介于两者之间。 5.变形织构有哪几种类型，对材料的性能有何影响？如何消除？ 答：（1）有丝织构和板织构 （2）造成材料的性能产生显著的各异性。如，对于板材，在冲压成型时容易产生制耳。

《数据结构》课后参考答案

单元练习1 一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳） （√）（1）数据的逻辑结构与数据元素本身的内容和形式无关。 （√）（2）一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。（ㄨ）（3）数据元素是数据的最小单位。 （ㄨ）（4）数据的逻辑结构和数据的存储结构是相同的。 （ㄨ）（5）程序和算法原则上没有区别，所以在讨论数据结构时可以通用。 （√）（6）从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。 （√）（7）数据的存储结构是数据的逻辑结构的存储映像。 （√）（8）数据的物理结构是指数据在计算机内实际的存储形式。 （ㄨ）（9）数据的逻辑结构是依赖于计算机的。 （√）（10）算法是对解题方法和步骤的描述。 二．填空题 （1）数据有逻辑结构和存储结构两种结构。 （2）数据逻辑结构除了集合以外，还包括：线性结构、树形结构和图形结构。（3）数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。 （4）树形结构和图形结构合称为非线性结构。 （5）在树形结构中，除了树根结点以外，其余每个结点只有 1 个前趋结点。 （6）在图形结构中，每个结点的前趋结点数和后续结点数可以任意多个。 （7）数据的存储结构又叫物理结构。 （8）数据的存储结构形式包括：顺序存储、链式存储、索引存储和散列存储。（9）线性结构中的元素之间存在一对一的关系。 （10）树形结构结构中的元素之间存在一对多的关系， （11）图形结构的元素之间存在多对多的关系。 （12）数据结构主要研究数据的逻辑结构、存储结构和算法（或运算）三个方面的内容。 （13）数据结构被定义为(D，R)，其中D是数据的有限集合，R是D上的关系的有限集合。 （14）算法是一个有穷指令的集合。 （15）算法效率的度量可以分为事先估算法和事后统计法。 （16）一个算法的时间复杂性是算法输入规模的函数。 （17）算法的空间复杂度是指该算法所耗费的存储空间，它是该算法求解问题规模n 的函数。 （18）若一个算法中的语句频度之和为T（n）=6n+3nlog2n，则算法的时间复杂度为 O （nlog2n）。 （19）若一个算法中的语句频度之和为T（n）=3n+nlog2n+n2，则算法的时间复杂度为 O

湖南大学《材料科学基础》2009-2013年期末试卷及详细答案

湖南大学2009年《材料科学基础》期末考试试卷 一. 图1是Na 2 O的理想晶胞结构示意图，试回答： 1．晶胞分子数是多少； 2．结构中何种离子做何种密堆积；何种离子填充何种空隙，所占比例是多少； 3．结构中各离子的配位数为多少，写出其配位多面体； 4．计算说明O2-的电价是否饱和； 5．画出Na 2 O结构在（001）面上的投影图。 二. 图2是高岭石(Al 2O 3 ·2SiO 2 ·2H 2 O)结构示意图，试回答： 1．请以结构式写法写出高岭石的化学式； 2．高岭石属于哪种硅酸盐结构类型； 3．分析层的构成和层的堆积方向； 4．分析结构中的作用力； 5．根据其结构特点推测高岭石具有什么性质。

三. 简答题： 1.晶体中的结构缺陷按几何尺寸可分为哪几类？ 2.什么是负扩散？ 3．烧结初期的特征是什么？ 4.硅酸盐晶体的分类原则是什么？ 5.烧结推动力是什么？它可凭哪些方式推动物质的迁移？ 6.相变的含义是什么？从热力学角度来划分，相变可以分为哪几类？ 四. 出下列缺陷反应式： 1.NaCl形成肖特基缺陷； 2.AgI形成弗仑克尔缺陷（Ag+进入间隙）； 3.TiO 2掺入到Nb 2 O 3 中，请写出二个合理的方程，并判断可能成立的方程是 哪一种？再写出每个方程的固溶体的化学式。 4.NaCl溶入CaCl 2 中形成空位型固溶体 五. 表面力的存在使固体表面处于高能量状态，然而，能量愈高系统愈不稳定，那么固体是通过何种方式降低其过剩的表面能以达到热力学稳定状态的。 六.粒径为1μ的球状Al 2O 3 由过量的MgO微粒包围，观察尖晶石的形成， 在恒定温度下，第一个小时有20%的Al 2O 3 起了反应，计算完全反应的时间：⑴ 用杨德方程计算；⑵用金斯特林格方程计算。 七.请分析熔体结构中负离子团的堆积方式、聚合度及对称性等与玻璃形成之关系。 八.试从结构和能量的观点解释为什么D晶界>D晶内？ 九.试分析二次再结晶过程对材料性能有何影响？工艺上如何防止或延缓二次再结晶的发生？ 十.图3是A-B-C三元系统相图，根据相图回答下列问题： 1．写出点P，R，S的成分； 2．设有2kgP，问需要多少何种成分的合金Z才可混熔成6kg成分为R的合金。

湖南大学数据结构试验图遍历问题

HUNAN UNIVERSITY 课程实习报告 题目：图的遍历问题 学生姓名刘乐 学生学号20080820208 专业班级通信工程2班 指导老师朱宁波 完成日期2010年5月17日 一、问题描述: 从图中某个顶点出发访问图中所有顶点，且使得每一顶点仅被访问一次，这个过程称为图的遍历。图的遍历是从图中某个顶点出发，沿着某条搜索路径对图中其余每个顶点进行访问, 并且使图中的每个顶点仅被访问一次的过程。 二、基本要求： 1、实现无向图的深度优先遍历和广度优先遍历。 2、分别输出每种遍历下的结点访问序列.从图中某个顶点出发，沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。它

是许多图的算法的基础。 三、实验主要模块构造思想： 深度优先搜索的过程 a 基本思想: 首先访问图中某一个指定的出发点Vi； 然后任选一个与顶点Vi相邻的未被访问过的顶点Vj； 以Vj为新的出发点继续进行深度优先搜索，直至图中所有顶点均被访问过。 b具体过程: 设x是当前被访问顶点，在对x做过访问标记后，选择一条从x出发的未检测过的边(x，y)。若发现顶点y已访问过，则重新选择另一条从x出发的未检测过的边，否则沿边(x，y)到达未曾访问过的y，对y访问并将其标记为已访问过；然后从y开始搜索，直到搜索完从y出发的所有路径，即访问完所有从y 出发可达的顶点之后，才回溯到顶点x，并且再选择一条从x出发的未检测过的边。上述过程直至从x出发的所有边都已检测过为止。此时，若x不是源点，则回溯到在x之前被访问过的顶点；否则图中所有和源点有路径相通的顶点(即从源点可达的所有顶点)都已被访问过，若图G是连通图，则遍历过程结束，否则继续选择一个尚未被访问的顶点作为新源点，进行新的搜索过程。 广度优先遍历（Breadth-First Traverse）: 特点：尽可能先从指定的出发点，横向地访问图中各个顶点。 1．广度优先遍历的定义 在访问了起始点之后,首先依次访问起始点的各个邻接点,然后依次访问这些顶点中未被访问过的邻接点.依此类推,直到所有被访问到的顶点的邻接点都被访问过为止. 2. 广度优先搜索的过程 a算法基本思想： 首先访问图中某一指定的出发点Vi； 然后依次访问Vi的所有接点Vi1，Vi2…Vit； 再次访问Vi1，Vi2…，Vit的邻接点中未经访问过的顶点，依此类推，直到图中所有顶点均被访问为止。 b具体过程： 从广度优先搜索遍历方法可知，先被访问的顶点的邻接点也被访问，即假设顶点V在W之前被访问，那么顶点V的所有未经访问的邻接点也在顶点W的所有未经访问的邻接点之前被访问。这样可以在广度优先遍历的算法中设置一个队列结构，用以保存已访问过的顶点的序号，访问该顶点的所有未经访问的顶点。 广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样会出现回退的现象。因此它不是个递归的过程。为了实现逐层访问，算法中使用了一个队列以记忆正在访问的这一层和上一层的顶点，以便于向下一层访问。为了避免重复访问，需要一个辅助函数visitvex[]给被

材料科学基础考研真题汇编

全国名校材料科学基础考研真题汇编（含部分答案）益星学习网提供全套资料 目录 1．清华大学材料科学基础历年考研真题及详解 2009年清华大学材料科学基础（与物理化学或固体物理）考研真题及详解 2008年清华大学材料科学基础（与物理化学或固体物理）考研真题及详解 2007年清华大学材料科学基础（与物理化学或固体物理）考研真题及详解 2．北京科技大学材料科学基础历年考研真题 2014年北京科技大学814材料科学基础考研真题 2013年北京科技大学814材料科学基础考研真题 2012年北京科技大学814材料科学基础考研真题 2011年北京科技大学814材料科学基础考研真题 3．西北工业大学材料科学基础历年考研真题及详解 2012年西北工业大学832材料科学基础考研真题及详解 2011年西北工业大学832材料科学基础（A卷）考研真题及详解 2010年西北工业大学832材料科学基础（A卷）考研真题及详解 4．中南大学材料科学基础历年考研真题及详解 2012年中南大学963材料科学基础考研真题（回忆版） 2009年中南大学959材料科学基础考研真题及详解 2008年中南大学963材料科学基础考研真题 2008年中南大学963材料科学基础考研真题（A组）详解 5．东北大学材料科学基础历年考研真题 2015年东北大学829材料科学基础考研真题（回忆版） 2014年东北大学829材料科学基础考研真题 6．北京工业大学材料科学基础历年考研真题及详解 2012年北京工业大学875材料科学基础考研真题 2009年北京工业大学875材料科学基础考研真题及详解 2008年北京工业大学875材料科学基础考研真题及详解 7．中国科学技术大学材料科学基础历年考研真题 2014年中国科学技术大学802材料科学基础考研真题 2013年中国科学技术大学802材料科学基础考研真题 2012年中国科学技术大学802材料科学基础考研真题 8．东华大学材料科学基础历年考研真题 2013年东华大学822材料科学基础考研真题 2012年东华大学822材料科学基础考研真题 9．南京航空航天大学材料科学基础历年考研真题及详解 2014年南京航空航天大学818材料科学基础（A卷）考研真题 2013年南京航空航天大学818材料科学基础（A卷）考研真题 2008年南京航空航天大学818材料科学基础考研真题及详解 10．其他名校材料科学基础历年考研真题及详解 2011年武汉理工大学833材料科学基础考研真题及详解

严蔚敏版数据结构课后习题答案-完整版

第1章绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据

类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={} 基本操作： InitComplex(&C,re,im) 操作结果：构造一个复数C ，其实部和虚部分别为re 和im DestroyCmoplex(&C)

——湖南大学材料科学基础真题汇总

2008年材料科学基础真题 (1)名词解释（每题5分，共40分） 1.空间点阵：组成晶体的粒子（原子、离子或分子）在三维空间中形成有 规律的某种对称排列，如果我们用点来代表组成晶体的粒子，这些点的空间排列就称为空间点阵。 2.中间相：金属与金属，或金属与非金属（氮、碳、氢、硅）之间形成的化合物总称为金属间化合物。由于金属间化合物在相图中处于相图的中间位置，故也称为中间相。 3.全位错：柏氏矢量等于点阵矢量的位错称为全位错。 4.共格界面：所谓共格晶界，是指界面上的原子同时位于两相晶格的结点上，即两相的晶格是彼此衔接的界面上的原子为两者共有。 5.滑移临界分切应力：滑移系开动所需的最小分切应力；它是一个定值，与材料本身性质有关，与外力取向无关。 6.包晶转变：成分为H点的δ固相，与它周围成分为B点的液相L，在一定的温度时，δ固相与L液相相互作用转变成成分是J点的另一新相γ固溶体，这一转变叫包晶转变或包晶反应。即HJB---包晶转变线，LB+δH→γJ 7.再结晶：塑性变形金属后续加热过程通过形核与长大无畸变等轴晶逐渐取代变形晶粒的过程。 8.上坡扩散：在化学位差为驱动力的条件下，原子由低浓度位置向高浓度位置进行的扩散。 (2)简答题（每题8分，共56分） 1.采用四轴坐标系标定六方晶体的晶向指数时，应该有什么样的约束条件？为什么？ 2.写出FCC、BCC、HCP晶体的密排面、密排面间距、密排方向、密排方向最

3.指出图1中各相图的错误，并加以解释。 4.什么是柯肯达尔效应？请用扩散理论加以解释。若Cu-Al组成的互扩散偶发生扩散时，界面标志物会向哪个方向移动。 答：柯肯达尔效应：在置换式固溶体的扩散过程中，放置在原始界面上的标志物朝着低熔点元素的方向移动，移动速率与时间成抛物线关系。

大学数据结构期末考试试题(有答案)

“数据结构”期末考试试题 一、单选题(每小题2分，共12分) 1．在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( )。 A． HL＝ps p一>next＝HL B． p一>next＝HL；HL＝p3 C． p一>next＝Hl；p＝HL； D． p一>next＝HL一>next;HL一>next＝p； 2．n个顶点的强连通图中至少含有( )。 A.n—l条有向边 B.n条有向边 C.n(n—1)／2条有向边 D.n(n一1)条有向边 3.从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A.O(1) B.O(n) C.O(1Ogzn) D.O(n2) 4．由权值分别为3，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为( )。 A．24 B．48 C． 72 D． 53 5．当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为( )参数，以节省参数值的传输时间和存储参数的空间。 A.整形 B.引用型 C.指针型 D.常值引用型· 6．向一个长度为n的顺序表中插人一个新元素的平均时间复杂度为( )。 A．O(n) B．O(1) C．O(n2) D．O(10g2n) 二、填空题(每空1分，共28分) 1．数据的存储结构被分为——、——、——和——四种。 2．在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为——域和——域。 3．——中缀表达式 3十x*(2.4／5—6)所对应的后缀表达式为————。 4．在一棵高度为h的3叉树中，最多含有——结点。 5．假定一棵二叉树的结点数为18，则它的最小深度为——，最大深度为——· 6．在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定——该结点的值，右子树上所有结点的值一定——该结点的值。 7．当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层——调整，直到被调整到——位置为止。 8．表示图的三种存储结构为——、——和———。 9．对用邻接矩阵表示的具有n个顶点和e条边的图进行任一种遍历时，其时间复杂度为——，对用邻接表表示的图进行任一种遍历时，其时间复杂度为——。 10．从有序表(12，18，30，43，56，78，82，95)中依次二分查找43和56元素时，其查找长度分别为——和——· 11．假定对长度n＝144的线性表进行索引顺序查找，并假定每个子表的长度均为，则进行索引顺序查找的平均查找长度为——，时间复杂度为——· 12．一棵B—树中的所有叶子结点均处在——上。 13．每次从无序表中顺序取出一个元素，把这插入到有序表中的适当位置，此种排序方法叫做——排序；每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做——排序。 14．快速排序在乎均情况下的时间复杂度为——，最坏情况下的时间复杂度为——。 三、运算题(每小题6分，共24分) 1．假定一棵二叉树广义表表示为a(b(c，d)，c(((，8)))，分别写出对它进行先序、中序、后序和后序遍历的结果。 先序： 中序； 后序： 2．已知一个带权图的顶点集V和边集G分别为： V＝{0，1，2，3，4，5}； E={(0，1)8，(0，2)5，(0，3)2，(1，5)6，(2，3)25，(2，4)13，(3，5)9，(4，5)10}， 则求出该图的最小生成树的权。 最小生成树的权； 3．假定一组记录的排序码为(46，79，56，38，40，84，50，42)，则利用堆排序方法建立的初始堆为——。 4．有7个带权结点，其权值分别为3，7，8，2，6，10，14，试以它们为叶子结点生成一棵哈夫曼树，求出该树的带权路径长度、高度、双分支结点数。 带权路径长度：——高度：——双分支结点数：——。 四、阅读算法，回答问题(每小题8分，共16分) 1．VOldAC(List&L) { InitList(L)； InsertRear(L;25)；