2015宁夏回族自治区数据结构考试基础

格式：docx
大小：20.69 KB
文档页数：5

下载文档原格式

/ 5

2015宁夏回族自治区公共基础知识试题及答案

1、在Word中选择某句话后，连续单击两次工具条中的“B”按钮，则____。

A、这句话呈粗体格式B、这句话呈细体格式C、这句话格式不变D、产生出错报告2、将高级语言程序设计语言源程序翻译成计算机可执行代码的软件称为 ____A、汇编程序B、编译程序C、管理程序D、服务程序3、欲调整文本页边距，需选择____命令。

A、[文件][页面设置]B、[格式][页面设置]C、[格式][边界设置]D、[视图][边界设置]4、Internet的规范译名是____。

A、因特网B、万维网C、英特尔网D、以太网5、在计算机网络中，表征数据传输可靠性的指标是____。

A、误码率B、频带利用率C、信道容量D、传输速率6、在相互发送电子邮件的时候，我们必须知道彼此的____。

A、家庭详细地址B、电子信箱的大小C、密码D、电子邮件的地址7、计算机病毒具有破坏性、____、潜伏性和传染性等特点。

A、必然性B、再生性C、隐蔽性D、易读性8、单击浏览器中工具栏上的“HOME”则____。

A、直接连接微软的主页B、直接连接Netscape的主页C、用户定义的主页上D、返回到上一次连接的主页9、广域网和局域网是按照____来分的。

A、网络使用者B、信息交换方式C、网络连接距离D、传输控制规程10、Word主窗口水平滚动条的左侧有四个显示方式切换按钮：“普通视图”、“联机版式视图”、“页面视图”和____。

A、大纲视图B、主控文档C、其他视图D、全屏显示11、计算机当前正在运行的程序和数据主要存放在____中。

A、CPUB、微处理器C、主存储器D、键盘12、的网址中，可以明确地看出是属于哪一类机构____。

A、教育界B、政府单位C、法人组织D、公司13、以下哪一项服务不属于Internet服务____A、电子邮件B、货物速递C、电子商务D、文件传输14、一般所说的拨号入网，是指通过____与因特网服务器连接。

A、微波B、公用电话系统C、专用电缆D、电视线路15、电子邮件是Internet应用最广泛的服务项目，通常采用的传输协议是____。

2015年宁夏回族自治区数据库入门基础

1、对二叉树的某层上的结点进行运算，采用队列结构按层次遍历最适宜。

int LeafKlevel(BiTree bt, int k) //求二叉树bt 的第k(k>1) 层上叶子结点个数{if(bt==null || k<1) return(0);BiTree p=bt,Q[]; //Q是队列，元素是二叉树结点指针,容量足够大int front=0,rear=1,leaf=0; //front 和rear是队头和队尾指针, leaf是叶子结点数int last=1,level=1; Q[1]=p; //last是二叉树同层最右结点的指针，level 是二叉树的层数while(front<=rear){p=Q[++front];if(level==k && !p->lchild && !p->rchild) leaf++; //叶子结点if(p->lchild) Q[++rear]=p->lchild; //左子女入队if(p->rchild) Q[++rear]=p->rchild; //右子女入队if(front==last) {level++; //二叉树同层最右结点已处理,层数增1last=rear; } //last移到指向下层最右一元素if(level>k) return (leaf); //层数大于k 后退出运行}//while }//结束LeafKLevel2、设t是给定的一棵二叉树，下面的递归程序count(t)用于求得:二叉树t中具有非空的左,右两个儿子的结点个数N2;只有非空左儿子的个数NL;只有非空右儿子的结点个数NR和叶子结点个数N0。

N2、NL、NR、N0都是全局量，且在调用count(t)之前都置为0.typedef struct node{int data; struct node *lchild,*rchild;}node;int N2,NL,NR,N0;void count(node *t){if (t->lchild!=NULL) if (1)___ N2++; else NL++;else if (2)___ NR++; else (3)__ ;if(t->lchild!=NULL)(4)____; if (t->rchild!=NULL) (5)____;}26.树的先序非递归算法。

2015宁夏回族自治区最新公共基础知识真题演练汇总

1、和通信网络相比，计算机网络最本质的功能是____。

A、数据通信B、资源共享C、提高计算机的可靠性和可用性D、分布式处理2、IP地址是Internet为每台主机分配的由32位____组成的唯一标识符。

A、二进制数B、八进制数C、十六进制数D、十进制数3、信息技术是指____。

A、获取信息的技术B、传输信息的技术C、处理信息的技术D、获取、处理、存储、传输信息的技术4、用户的电子邮件地址中必须包括以下____所给出内容，才完整。

A、用户名，用户口令，电子邮箱所在的主机域名B、用户名，用户口令C、用户名，电子邮箱所在的主机域名D、用户口令，电子邮箱所在的主机域名5、在Windows中，为了查找文件名以"A"字母打头，后跟一字母的所有文件，应当在查找名称框内输入____。

A、AB、A*C、A？D、A#6、因特网中的域名服务器系统负责全网IP地址的解析工作，它的好处是____A、我们只需简单地记住一个网站的域名，而不必记IP地址B、IP地址再也不需要了C、IP地址从32位的二进制地址缩减为8位的二进制地址D、IP协议再也不需要了7、计算机网络的主要作用有集中管理和分布处理、远程通信以及____。

A、信息交流B、辅助教学C、资源共享D、自动控制8、下列属于计算机系统软件的是____。

A、字处理软件B、电子表格软件C、操作系统软件D、EXCEL9、具有管理计算机全部硬件资源、软件资源功能的软件系统是____。

A、编译系统B、操作系统C、资源管理器D、网页浏览器10、下列4项内容中，不属于Internet（因特网）提供的服务的是____。

A、电子邮件B、文件传输C、远程登录D、实时监测控制11、LAN在计算机网络中表示的是____。

A、以太网B、广播网C、广域网D、局域网12、计算机里面的猫和老鼠指的是____。

A、Modem and MouseB、Tom and JerryC、键盘和鼠标器D、以上都对13、改变字体的正确操作是____。

2014宁夏回族自治区数据结构考试技巧、答题原则

A）loc(A1)+i*c B）loc(A1)+(i-1)*c
C）loc(A1)+i*c+1 D）loc(A1)+(i+1)*c
21、与无向图相关的术语有（ C ）。
A）强连通图 B）入度
C）路径 D）弧
36、n个顶点的强连通图至少有（ A ）条边。
A）n B）n+1 C）n-1 D）n(n-1)
37、广义表A=（A,B,(C,D),(E,(F,G))），则head(tail(head(tail(tail(A)))))=（ D ）。
A） (G) B） (D) C） C D） D
1、采用链结构存储线性表时，其地址（ B ）。
A）必须是连续的 B）连续不连续都可以
C）部分地址必须是连续 D）必须是不连续的
2、n个顶点的图的最小生成树必定（ D ），是不正确的描述。
A）不唯一 B）权的总和唯一
C）不含回路 D）有n条边
19、串的逻辑结构与（ D ）的逻辑结构不相同。
A）线性表 B）栈
C）队列 D）集合
20、用一维数组A进行顺序存储时，若起始地址为loc(A1)，元素长度为c，则A的第i个数组单元在存放地址loc(Ai)，等于（ B ）。
B）线性结构和非线性结构
C）紧凑结构和非紧凑结构
D）内部结构和外部结构
5、广义表head(((a,b),(c,d)))的运算结果为（ A ）。
A）(a,b) B）(c,d)
C）空表 D）（（a,b）,(c,d)）
12、以下属于顺序存储结构优点的是（ A ）。
A) 存储密度大 B) 插入运算方便
C）删除运算方便 D）可方便地用于各种逻辑结构的存储表示

2015年宁夏回族自治区数据结构试题集(10套题并附带答案)知识大全

A．2 B．3 C．4 D．∞
10、下列选项中，符合堆定义的是
A．{102，24，55，60，89，93}
B．{24，89，55，60，93，102}
C．{102，93，55，60，89，24}
D．{102，60。89，93，55，24}
51、下列选项中，其平均查找性能与基于二叉排序树的查找相当的是
A．二分查找 B．顺序查找 C．分块查找 D．索引顺序查找
52、若某线性表中最常用的操作是取第i个元素和找第i个元素的前驱，则采用( )存储方法最节省时间
A 顺序表 B单链表 C 双链表 D单循环链表
C． 72 D． 53
17、以下说法正确的是 D 。
A．数据项是数据的基本单位
B．数据元素是数据的最小单位
C．数据结构是带结构的数据项的集合
D．一些表面上很不相同的数据可以有相同的逻辑结构
18、以下说法正确的是 D 。
A．数据项是数据的基本单位
B．数据元素是数据的最小单位
D 存储方式最节省运算时间。
A．单链表 B．给出表头指针的单循环链表 C．双链表 D．带头结点的双循环链表
3、栈采用不同的存储方式时，下列关于出栈过程的叙述中，正确的是
A．顺序栈需要判定栈空，链栈也需要判定
B．顺序栈需要判定栈空，而链栈不需要判定
C．顺序栈不需要判定栈空，而链栈需要判定
D．顺序栈不需要判定栈空，链栈也不需要判定
4、在二维数组a[9][10]中：每个数组元素占用3个存储空间，从首地址SA开始按行优先
6、在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。
A．数据的处理方法 B．数据元素的类型

2015考研计算机数据结构试题及答案

2015年考研必备资料2015年考研计算机数据结构试题及答案目录2015年考研计算机数据结构试题及答案（1） (2)2015年考研计算机数据结构试题（1） (2)2015年考研计算机数据结构试题答案（1） (5)2015年考研计算机数据结构试题及答案（2） (6)2015年考研计算机数据结构试题（2） (6)2015年考研计算机数据结构试题答案（2） (9)2015年考研计算机数据结构试题及答案（3） (11)2015年考研计算机数据结构试题（3） (11)2015年考研计算机数据结构试题答案（3） (13)2015年考研计算机数据结构试题及答案（4） (15)2015年考研计算机数据结构试题（4） (15)2015年考研计算机数据结构试题答案（4） (17)2015年考研计算机数据结构试题及答案（5） (19)2015年考研计算机数据结构试题（5） (19)2015年考研计算机数据结构试题答案（5） (21)2015年考研计算机数据结构试题及答案（1）2015年考研计算机数据结构试题（1）一、选择题(24分)1.下列程序段的时间复杂度为( )。

i=0，s=0; while (s(A) O(n1/2) (B) O(n1/3) (C) O(n) (D) O(n2)2.设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用下列( )存储方式最节省运算时间。

(A) 单向链表 (B) 单向循环链表(C) 双向链表 (D) 双向循环链表3.设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B插入结点X的操作序列为( )。

(A) s->next=p->next;p->next=-s; (B) q->next=s; s->next=p;(C) p->next=s->next;s->next=p; (D) p->next=s;s->next=q;4.设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为( )。

宁夏回族自治区考研计算机科学与技术复习重点

宁夏回族自治区考研计算机科学与技术复习重点一、数据结构与算法数据结构是计算机科学与技术领域的基础，它关注如何组织和存储数据以便高效地访问和操作。

算法则是解决问题的步骤和方法，它涉及到如何设计和分析高效的解决方案。

1. 线性表线性表是最基本的数据结构之一，它包括顺序表和链表两种形式。

顺序表使用数组存储元素，具有随机访问的特点；链表通过指针将元素连接起来，方便插入和删除操作。

2. 栈和队列栈和队列是两种特殊的线性表。

栈具有后进先出（LIFO）的特点，插入和删除操作只能在一端进行；而队列具有先进先出（FIFO）的特点，插入操作在队尾进行，删除操作在队头进行。

3. 树和二叉树树是一种非线性的数据结构，它由节点和边组成。

每个节点可以有多个子节点，但每个节点只有一个父节点。

二叉树是树的一种特殊形式，每个节点最多有两个子节点。

4. 图图是由节点和边组成的非线性数据结构，它用于表示不同对象之间的关系。

图可以分为有向图和无向图，根据节点之间的关系可以有多种表示方法。

5. 排序和搜索算法排序算法用于将一组元素按照特定的顺序排列，常见的排序算法有冒泡排序、选择排序、插入排序、快速排序等。

搜索算法用于在给定数据集合中查找某个特定元素，常见的搜索算法有线性查找、二分查找、哈希查找等。

二、操作系统操作系统是计算机系统中的核心软件，它管理和控制计算机硬件资源，并提供用户与计算机系统之间的接口。

1. 进程和线程进程是正在执行的程序的实例，它包括代码、数据和资源等。

线程是进程中的一个执行单元，多个线程可以共享进程的资源，提高程序的执行效率。

2. 内存管理内存管理涉及到如何分配和释放计算机的内存资源，以及如何优化内存的使用。

常见的内存管理技术有分页、分段和虚拟内存等。

3. 文件系统文件系统是操作系统中用于管理文件和目录的组织方式。

它提供了文件的访问和操作接口，包括读取、写入、复制、删除等操作。

4. 进程间通信进程间通信用于不同进程之间的信息传递和共享。

2015年数据结构期末考试题及答案,推荐文档(2021年整理)

2015年数据结构期末考试题及答案,推荐文档(word版可编辑修改) 编辑整理：尊敬的读者朋友们：这里是精品文档编辑中心，本文档内容是由我和我的同事精心编辑整理后发布的，发布之前我们对文中内容进行仔细校对，但是难免会有疏漏的地方，但是任然希望（2015年数据结构期末考试题及答案,推荐文档(word版可编辑修改)）的内容能够给您的工作和学习带来便利。

同时也真诚的希望收到您的建议和反馈，这将是我们进步的源泉，前进的动力。

本文可编辑可修改，如果觉得对您有帮助请收藏以便随时查阅，最后祝您生活愉快业绩进步，以下为2015年数据结构期末考试题及答案,推荐文档(word版可编辑修改)的全部内容。

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) 。

2015年下半年宁夏省银行招聘考试计算机学：计算机基础考试题

2015年下半年宁夏省银行招聘考试计算机学：计算机基础考试题本卷共分为1大题50小题，作答时间为180分钟，总分100分，60分及格。

一、单项选择题（共50题，每题2分。

每题的备选项中，只有一个最符合题意）1.下列可选项，都是硬件的是。

A：Windows、ROM和CPUB：WPS、RAM和显示器C：ROM、RAM和PascalD：硬盘、光盘和软盘E：以上都不正确2.下列各组软件中，全部属于系统软件的一组是。

A：程序语言处理程序、操作系统、数据库管理系统B：文字处理程序、编辑程序、操作系统C：财务处理软件、金融软件、网络系统D：WPS 0mce 2003、Excel 2000、Windows 98E：以上都不正确3.在Windows XP桌面左上角有一个“我的电脑”图标，双击该图标可以。

A：启动我的电脑B：关闭我的电脑C：关闭Winows XP系统D：浏览本计算机上的资源E：以上都不正确4.关于关系的完整性约束，由DBMS自动完成的是。

(1)实体完整性(2)用户定义的完整性(3)参照完整性(4)域完整性A：(1)B：(1)(2)C：(1)(3)D：全部E：以上都不正确5. 在Word窗口中，如果光标停在某个字符前，当选择某个样式时，该样式起作用的对象为。

A：当前字符B：当前行C：当前段落D：文档中的所有段落E：以上都不正确6. 下列操作中，直接删除文件或文件夹而不送入回收站。

A：按下Shift键拖动文件或文件夹到回收站B：选定文件或文件夹后，按Del键C：选定文件或文件夹后，使用“文件”中的“删除”D：选定文件或文件夹后，按Alt键E：以上都不正确7. 十进制数14对应的二进制数是。

A：1111B：1110C：1100D：1010E：以上都不正确8. 存储容量1GB等于。

A：1024KBB：1000KBC：1024MBD：1000MBE：以上都不正确9. 一个汉字的国标码需用。

A：1个字节B：2个字节C：4个字节D：8个字节E：以上都不正确10. 可以同时显示的按钮是。

2015宁夏回族自治区数据结构基础理论考试试题及答案

1、下列各种数据结构中属于线性结构的有（ A ）。

A）栈 B) 二叉树C) 广义表 D) 图2、在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为（ C ）。

A）4 B）5C）6 D）73、已知广义表L=((x,y,z),a,(u,t,w))，从L 表中取出原子项t 的操作是（ D ）。

A) Head(Head(Tail(Tail(L))))B) Tail(Head(Head(Tail(L))))C) Head(Tail(Head(Tail(L))))D)Head(Tail(Head(Tail(Tail(L)))))4、与无向图相关的术语有（ C ）。

A）强连通图 B）入度C）路径 D）弧5、二叉树第i(i≥1)层上至多有（ C ）结点。

A）2i B）2i C）2i-1 D）2i-16、倘若在对串的插入、删除运算中，期望运算速度最快，则应采用（ C ）。

A）顺序表示法 B）单字符为结点的单链表表示法C）等量分块表示法 D）不等量分块表示法7、数据结构中，在逻辑上可以把数据结构分成（ B ）。

A）动态结构和静态结构B）线性结构和非线性结构C）紧凑结构和非紧凑结构D）内部结构和外部结构8、下列各种数据结构中属于线性结构的有（ A ）。

A）栈 B) 二叉树C) 广义表 D) 图9、若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个（ D ）。

A）上三角矩阵 B) 稀疏矩阵C) 对角矩阵 D) 对称矩阵10、下面程序段的时间复杂度是( A )。

s =0;for( i =0; i<n; i++)for(j=0;j<n;j++)s +=B[i][j];sum = s ;A） O(n2) B） O(n)C） O(m*n) D）O(1)11、n个顶点，e条边的有向图的邻接矩阵中非零元素有（ C ）个。

A）n B）2e C）e D） n+e12、线性表的链接实现有利于（ A ）运算。

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

1、请编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树用llink-rlink法存储。

2、设一棵二叉树的结点结构为 (LLINK,INFO,RLINK),ROOT为指向该二叉树根结点的指针，p 和q分别为指向该二叉树中任意两个结点的指针，试编写一算法ANCESTOR（ROOT，p,q,r）,该算法找到p和q的最近共同祖先结点r。

3、由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树，下面程序的作用是实现由已知某二叉树的前序遍历和中序遍历序列，生成一棵用二叉链表表示的二叉树并打印出后序遍历序列，请写出程序所缺的语句。

#define MAX 100typedef struct Node{char info; struct Node *llink, *rlink; }TNODE;char pred[MAX],inod[MAX];main(int argc,int **argv){ TNODE *root;if(argc<3) exit 0;strcpy(pred,argv[1]); strcpy(inod,argv[2]);root=restore(pred,inod,strlen(pred));postorder(root);}TNODE *restore(char *ppos,char *ipos,int n){ TNODE *ptr； char *rpos; int k;if(n<=0) return NULL;ptr->info=(1)_______;for((2)_______ ; rpos<ipos+n;rpos++) if(*rpos==*ppos) break;k=(3)_______;ptr->llink=restore(ppos+1, (4)_______,k );ptr->rlink=restore ((5)_______+k,rpos+1,n-1-k);return ptr;}postorder(TNODE*ptr){ if(ptr=NULL) return;postorder(ptr->llink); postorder(ptr->rlink); printf(“%c”,ptr->info);}4、若第n件物品能放入背包，则问题变为能否再从n-1件物品中选出若干件放入背包（这时背包可放入物品的重量变为s-w[n]）。

若第n件物品不能放入背包，则考虑从n-1件物品选若干件放入背包（这时背包可放入物品仍为s）。

若最终s=0,则有一解；否则，若s<0或虽然s>0但物品数n<1,则无解。

（1）s-w[n],n-1 //Knap(s-w[n],n-1)=true（2）s,n-1 // Knap←Knap(s,n-1)5、设t是给定的一棵二叉树，下面的递归程序count(t)用于求得:二叉树t中具有非空的左,右两个儿子的结点个数N2;只有非空左儿子的个数NL;只有非空右儿子的结点个数NR和叶子结点个数N0。

void example(b)btree *b;{ btree *stack[20], *p；int top;if (b!=null){ top=1; stack[top]=b;while (top>0){ p=stack[top]; top--;printf(“%d”,p->data);if (p->rchild!=null){(1)___; (2)___;}if (p->lchild!=null)(3)___; (4)__;}}}}6、约瑟夫环问题（Josephus问题）是指编号为1、2、…，n的n（n>0）个人按顺时针方向围坐成一圈，现从第s个人开始按顺时针方向报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列，…，如此重复直到所有的人全部出列为止。

现要求采用循环链表结构设计一个算法，模拟此过程。

#include<stdlib.h>typedef int datatype;typedef struct node{datatype data;struct node *next;}listnode;typedef listnode *linklist;void jose(linklist head,int s,int m){linklist k1,pre,p;int count=1;pre=NULL;k1=head; /*k1为报数的起点*/while (count!=s) /*找初始报数起点*/{pre=k1;k1=k1->next;count++;}while(k1->next!=k1) /*当循环链表中的结点个数大于1时*/{ p=k1; /*从k1开始报数*/count=1;while (count!=m) /*连续数m个结点*/{ pre=p;p=p->next;count++;}pre->next=p->next; /*输出该结点，并删除该结点*/printf("%4d",p->data);free(p);k1=pre->next; /*新的报数起点*/}printf("%4d",k1->data); /*输出最后一个结点*/free(k1);}main(){linklist head,p,r;int n,s,m,i;printf("n=");scanf("%d",&n);printf("s=");scanf("%d",&s);printf("m=",&m);scanf("%d",&m);if (n<1) printf("n<0");else{/*建表*/head=(linklist)malloc(sizeof(listnode)); /*建第一个结点*/head->data=n;r=head;for (i=n-1;i>0;i--) /*建立剩余n-1个结点*/{ p=(linklist)malloc(sizeof(listnode));p->data=i;p->next=head;head=p;}r->next=head; /*生成循环链表*/jose(head,s,m); /*调用函数*/}}7、假设以邻接矩阵作为图的存储结构，编写算法判别在给定的有向图中是否存在一个简单有向回路，若存在，则以顶点序列的方式输出该回路（找到一条即可）。

（注：图中不存在顶点到自己的弧）有向图判断回路要比无向图复杂。

利用深度优先遍历，将顶点分成三类：未访问；已访问但其邻接点未访问完;已访问且其邻接点已访问完。

下面用0，1，2表示这三种状态。

前面已提到，若dfs（v）结束前出现顶点u到v的回边，则图中必有包含顶点v和u的回路。

对应程序中v的状态为1，而u是正访问的顶点，若我们找出u的下一邻接点的状态为1，就可以输出回路了。

void Print(int v,int start ) //输出从顶点start开始的回路。

{for(i=1;i<=n;i++)if(g[v][i]!=0 && visited[i]==1 ) //若存在边（v,i），且顶点i的状态为1。

{printf(“%d”,v);if(i==start) printf(“\n”); else Print(i,start);break;}//if}//Printvoid dfs(int v){visited[v]=1;for(j=1;j<=n;j++ )if (g[v][j]!=0) //存在边(v,j)if (visited[j]!=1) {if (!visited[j]) dfs(j); }//ifelse {cycle=1; Print(j,j);}visited[v]=2;}//dfsvoid find_cycle() //判断是否有回路，有则输出邻接矩阵。

visited数组为全局变量。

{for (i=1;i<=n;i++) visited[i]=0;for (i=1;i<=n;i++ ) if (!visited[i]) dfs(i);}//find_cycle8、编写一个过程，对一个n×n矩阵，通过行变换，使其每行元素的平均值按递增顺序排列。

9、请设计一个算法，要求该算法把二叉树的叶子结点按从左到右的顺序连成一个单链表，表头指针为head。

二叉树按二叉链表方式存储，链接时用叶子结点的右指针域来存放单链表指针。

分析你的算法的时、空复杂度。

10、给定n个村庄之间的交通图，若村庄i和j之间有道路，则将顶点i和j用边连接，边上的Wij表示这条道路的长度，现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短?试设计一个解答上述问题的算法，并应用该算法解答如图所示的实例。

（20分）11、假设以邻接矩阵作为图的存储结构，编写算法判别在给定的有向图中是否存在一个简单有向回路，若存在，则以顶点序列的方式输出该回路（找到一条即可）。