免费智能真题库 > 历年试卷 > 软件设计师 > 2017年下半年 软件设计师 下午试卷 案例
  第4题      
  知识点:   常量   矩阵   常量和变量   定点数

 
【说明】
一个无向连通图G点上的哈密尔顿(Hamiltion)回路是指从图G上的某个顶点出发,经过图上所有其他顶点一次且仅一次,最后回到该顶点的路劲。一种求解无向图上哈密尔顿回路算法的基础私下如下:
假设图G存在一个从顶点V0出发的哈密尔顿回路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:统计变量,当期已经访问的定点数为k+1
x[k]:第k个访问的顶点编号,从0开始
Visited[x[k]]:第k个顶点的访问标志,0表示未访问,1表示已访问
(2)C程序

 
问题:4.1   (10分)
根据题干说明。填充C代码中的空(1)~(5).
 
问题:4.2   (5分)
根据题干说明和C代码,算法采用的设计策略为(6),该方法在遍历图的顶点时,采用的是(7)方法(深度优先或广度优先)。
 
 
 

   知识点讲解    
   · 常量    · 矩阵    · 常量和变量    · 定点数
 
       常量
        与C语言不同,使用final关键字,C++语言则是const,如final float pi=3.14f、 final byte c=12。浮点常数后面要加"f",如12.7f、 1.02f。
 
       矩阵
               特殊矩阵
               若矩阵中元素(或非零元素)的分布有一定的规律,则称之为特殊矩阵。常见的特殊矩阵有对称矩阵、三角矩阵、对角矩阵等。
               对称矩阵:若矩阵An×n中的元素有
               aij=aji1≤i,jn
               则称之为n阶对称矩阵。
               上(下)三角矩阵:矩阵的上(下)三角(不包括对角线)中的元素均为常数或零。
               对角矩阵:矩阵中的非零元素都集中在以主对角线为中心的带状区域中,即除了主对角线上和在对角线上、下方若干条对角线上的元素外,其余的矩阵元素都为零。
               稀疏矩阵
               在一个矩阵中,若非零元素的个数远远少于零元素的个数,且非零元素的分布没有规律,则称之为稀疏矩阵。存储稀疏矩阵的非零元素时必须同时存储其位置(行、列号),用三元组(i,j,aij)可唯一确定矩阵中的一个元素。因此,一个稀疏矩阵可由表示非零元素的三元组及其行、列数唯一确定。
               稀疏矩阵的三元组表的顺序存储结构称为三元组顺序表,常用的三元组表的链式存储结构是十字链表。
 
       常量和变量
        按照程序运行时数据的值能否改变,将程序中的数据分为常量和变量。程序中的数据对象可以具有左值和(或)右值,左值指存储单元(或地址、容器),右值是值(或内容)。变量具有左值和右值,在程序运行过程中其右值可以改变;常量只有右值,在程序运行过程中其右值不能改变。
 
       定点数
        所谓定点数,就是表示数据时小数点的位置固定不变。小数点的位置通常有两种约定方式:定点整数(纯整数,小数点在最低有效数值位之后)和定点小数(纯小数,小数点在最高有效数值位之前)。
        设机器字长为n,各种码制表示下的带符号数的范围如下表所示。当机器字长为n时,定点数的补码和移码可表示2n个数,而其原码和反码只能表示2n-1个数(0表示占用了两个编码),因此,定点数所能表示的数值范围比较小,运算中很容易因结果超出范围而溢出。
        
        机器字长为n时各种码制表示的带符号数的范围
   题号导航      2017年下半年 软件设计师 下午试卷 案例   本试卷我的完整做题情况  
1 /
2 /
3 /
4 /
5 /
6 /
 
第4题    在手机中做本题