第十七章-数据结构与算法.docx

《第十七章-数据结构与算法.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、窗体顶端数据结构与算法您现在的位置：希赛网 > 云阅读 > 软件设计师考试试题分类精解（2018版） > 试题1(2017年下半年试题4)第17章：数据结构与算法应用作者：希赛软考学院    来源：希赛软考学院    2017年11月21日试题1(2017年下半年试题4)阅读下列说明和C代码，回答问题1至问题2，将解答写在答题纸的对应栏内。【说明】一个无向连通图G点上的哈密尔顿（Hamiltion）回路是指从图G上的某个顶点出发，经过图上所有其他顶点一次且仅一次，最后回到该顶点的路劲。一种求解无向图上哈密尔顿回路算法的基础私下如下：假设图G存

2、在一个从顶点V0出发的哈密尔顿回路V1——V2——V3——...——Vn-1——V0。算法从顶点V0出发，访问该顶点的一个未被访问的邻接顶点V1，接着从顶点V1出发，访问V1一个未被访问的邻接顶点V2，..。；对顶点Vi，重复进行以下操作：访问Vi的一个未被访问的邻接接点Vi+1；若Vi的所有邻接顶点均已被访问，则返回到顶点Vi-1，考虑Vi-1的下一个未被访问的邻接顶点，仍记为Vi；知道找到一条哈密尔顿回路或者找不到哈密尔顿回路，算法结束。【C代码】下面是算法的C语言实现。（1）常量和变量说明n:图G中的顶点数c［］［］:图G的邻接矩阵K:

3、统计变量，当期已经访问的定点数为k+1 x［k］:第k个访问的顶点编号，从0开始 Visited［x［k］］：第k个顶点的访问标志，0表示未访问，1表示已访问⑵C程序#include#include#defineMAX100 VidoHamilton（intn,intx［MAX,intc[MAX][MAX]）｛int;intvisited[MAX];intk; /*初始化x数组贺visited数组*/for（i=0:i

4、顶点*/k=0（ ）；x[0]=0K=k+1/*访问其他顶点*/while（k>=0）｛   x[k]=x[k]+1;   while（x[k]>

5、      prinf（〝%d--〝,x[k]; /*输出哈密尔顿回路*/          ｝          prinf（〝%d--〝,x[0];          return；｝elseifx[k]

6、空（1）~（5）.【问题2】（5分）根据题干说明和C代码，算法采用的设计策略为（6），该方法在遍历图的顶点时，采用的是（7）方法（深度优先或广度优先）。试题分析哈密顿图是一个无向图，由天文学家哈密顿提出，由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次。在图论中是指含有哈密顿回路的图，闭合的哈密顿路径称作哈密顿回路，含有图中所有顶点的路径称作哈密顿路径。回溯法是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而

7、满足回溯条件的某个状态的点称为“回溯点”。在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯（其实回溯法就是对隐式图的深度优先搜索算法）。若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。算法题历来都被认为是比较难的题，一个程序开发人员都不喜欢看别人的代码。但是要得分也不是太

8、难。问题2比较容易得分，而且第二空就是个二选一的填空。只要了解到回溯法的相关原理，基本可以得满分。对于问题1就需要花一些心思，去读懂题干和代码，但是这里的第1空和第