1算法及其描述(2-3) 一、 选择题1 下面关于算法的描述，正确的是A
 
1 算法及其描述(2‐3)
 
一、  选择题
 
1. 下面关于算法的描述， 正确的是
 
A.一个算法只能有一个输入
 
B.算法只能用框图来表示
 
C.一个算法的执行步骤可以是无限的
 
D.一个完整的算法， 不管用什么方法来表示， 都至少有一个输出结果
 
答案： D
 
2. 下列程序框图中表示处理计算的是(  )
 
A.①
 
B.②
 
C.③
 
D.④
 
答案： B
 
3.算法描述可以有多种表达方法， 下面哪些方法不可以描述“闰年问
 
题” 的算法 (   )
 
A.自然语言
 
B.流程图
 
C.伪代码
 
D.机器语言
 
答案： D
 
4. 下列说法正确的是(    )。
 
①算法是程序设计的灵魂， 由此可见算法的重要地位。
 
②简单的说， 算法就是解决问题的方法和步骤。
 
③著名的计算机科学家尼克劳斯指出： “算法+数据结构=程序”。
 
④一个问题的算法只能用一种程序设计语言实现。
 
A.①②③④
 
B.①②③
 
C.①②④
 
D.③④
 
答案： B
 
5. 以下说法正确的是(      )
 
①自然语言描述的算法的优点是通俗易懂。
 
②用自然语言描述算法缺乏直观性并容易产生歧义。
 
③用流程图描述算法形象、 直观、 更容易理解。
 
④伪代码是介于自然语言和计算机程序语言之间的一种算法描述方法。
 
A.①②③④
 
B.①②③
 
C.①②④
 
D.③④
 
答案： A
 
2 程序设计语言基础(3‐4)
 
一、  选择题
 
1. 在 VB 中数据有多种类型， 下列说明符中可以表示单精度类型的是(      )
 
A.Integer
 
B.Boolean
 
C.Single
 
D.String
 
答案： C
 
2. 浮点型包括 (     )
 
A.布尔型和逻辑型
 
B.字符串型和双精度型
 
C.单精度和双精度
 
D.布尔型和整型
 
答案： C
 
3. 以下声明变量方法正确的是(      )A.1+2
 
B.A#B
 
C.7i
 
D.a7i
 
答案： D
 
4. 下列给出的赋值语句中正确的是(      )
 
A.B=A‐3
 
B.‐M =M
 
C.x + y =0
 
D.4 = M
 
答案： A
 
5. VB 程序可以在运行时通过键盘获得数据， 下面输入语句正确的是)A.r=Read(“请输入圆的半径”  )B.r=InputBox(“请输入圆的半径” )C.r=Scanf(“请输入圆的半径”  )D.r=MsgBox(“请输入圆的半径” )
 
答案： B
 
3 程序设计语言基础(3‐5)
 
一、  选择题
 
1. VB 语言中， 下列各种基本数据类型说明符中表示整型数的是
 
(    )。 A.Boolean
 
B.Integer
 
C.Single
 
D.String
 
答案： B
 
2. 函数 Mid 可以从中间指定位置截取一定长度的字符串， Mid("李娜
 
是中国人的骄傲",4,2)的值为(      )
 
A.李娜
 
B.是中
 
C.骄傲
 
D.中国
 
答案： D
 
3. 在 VB 中， 表达式(2^2+5\2)Mod 5 的值是(      )
 
A.0
 
B.1
 
C.1.2
 
D.6
 
答案： B
 
4. 下列不属于赋值语句的是(      )A.d=b^2‐4*a*c
 
B.s=2*pi*r
 
C.Text1.text=“OK”
 
D.x+y=5
 
答案： D
 
5. 在 VB 语言中， 表示“a 大于 5 或小于 0”  的正确表达式是
 
A.0 < a < 5
 
B.a > 5 And a < 0
 
C.a > 5 Or a < 0
 
D.a > 0 And a < 5
 
答案： C
 
4 程序设计语言基础(3‐6)
 
一、  选择题
 
1. 在 VB 语言中， 下列正确的赋值语句是(   )
 
A.5 = c
 
B.3 a = 5 c
 
C.‐c = c ‐ 3
 
D.a=b+c
 
答案： D
 
2.下列属于整型常量的是 (     )
 
A.2006
 
B.一千零一
 
C."1997"
 
D.3.14
 
答案： A
 
3.下列逻辑表达式的值为“真” 的是
 
A.2 + 4 > 8
 
B.3 + 12 > 15
 
C.5 > 0 And 4 < 3
 
D.10 / 5 < 3
 
答案： D
 
4. 以下运算符中运算优先级最高的是 (    )。
 
A.+
 
B.‐
 
C.>=
 
D.*
 
答案： D
 
5.VB6.0 中， 正确表达 2013 年 3 月 8 日的日期表达式是(   )
 
A.{2013/3/8}
 
B.#2013/3/8#
 
C.“2013/3/8”
 
D.2013‐3‐8
 
答案： B
 
5 顺序结构(4‐1‐1)
 
一、  选择题
 
1. 结构化程序设计由三种基本结构组成， 下面哪个不属于这三种基本结构(    )。
 
A.顺序结构
 
B.输入、 输出结构
 
C.选择结构
 
D.循环结构
 
答案： B
 
2. 结构化程序设计由顺序结构,选择结构和循环结构三种基本结构组成,其中某程序中三个连续语句如下:
 
a=1
 
b=2
 
c=b+a
 
它属于(    )。
 
A.顺序结构
 
B.选择结构
 
C.循环结构
 
D.以上都不是
 
答案： A
 
3.下列程序执行后 A、 B 的值是
 
A=5
 
B=6
 
A=A+B： B=A‐B： A=A‐B ( )。
 
A.5、 6
 
B.6、 6
 
C.6、 5
 
D.5、 5
 
答案： C
 
4. 如图所示的流程图， 是一个(    )的流程图。
 

 
A.顺序结构
 
B.选择结构
 
C.循环结构
 
D.以上说法都不对
 
答案： A
 
5. 30.  下面程序段的运行结果是(    )
 
N1=Len("2008 奥运")
 
Print  N1
 
A.2008 奥运
 
B.6
 
C.2008
 
D.0
 
答案： B
 
6 顺序结构(4‐1‐2)
 
一、  选择题
 
1. 关于顺序结构程序说法正确的是(   )
 
①在顺序结构的程序中， 引发一个事件后， 计算机将逐条执行程序中的每一条语句， 最后得到处理结果。
 
②顺序结构是程序结构中最简单的一种结构。
 
③程序执行过程中没有分支、 没有重复， 我们把这种结构称为顺序结构。
 
④交换 a， b 两个数的算法， 可以用顺序结构实现。
 
A.①②③④
 
B.①②③
 
C.①②④
 
D.①③
 
答案： A
 
2.如图所示的流程图， 是一个(    )的流程图。
 

 
A. 顺序结构
 
B.选择结构
 
C.循环结构
 
D.以上说法都不对
 
答案： A
 
3. 要实现变量 M 的值与变量 N 的值进行交换,可用语句(    )。
 
A.X=M:M=N:N=X
 
B.M=N:N=M
 
C.M=N
 
D.N=M
 
答案： A
 
4. 以下程序段执行后， 整型变量 a 的值为(    )
 
a=5
 
b=8
 
b=b+a
 
a=a+b
 
A.5
 
B.8
 
C.13
 
D.18
 
答案： D
 
5.  有如下 Visual Basic 程序段：
 
Private Sub Command1_Click()
 
m = 8
 
n = 5
 
t = m + n
 
t = t ‐ n
 
End Sub
 
该程序段运行后， 变量 t 的值为(   )
 
A.5
 
B.8
 
C.10
 
D.13

17.【 STEMA】以下关于二分查找算法的描述中，不正确的是（A）
 A二分查找算法的最大查找时间与查找对象的大小成正比
 B二分查找一般从数组的中间元素开始
 C二分查找只对有序数组有效
 D二分查找可以使用递归实现

1. 算法描述
 
Dijkstra算法是图论中常用的一个算法，用于计算图中从一个指定点到其余所有点的最短路径。图是有向图，所有边的权重为非负数，图1是满足条件的一个简单有向图。
 
 
图1 有向加权图示例
 
 
在图1中，A到D的最短路径是A-->C-->B-->D，其长度为3+2+5=10。
 
其算法实现代码如下（数据结构与算法分析C++版）：
 
 
void Dijkstra(Graph *G, int *D, int s){
  int i, v, w;

  for(i = 0; i < G->n(); i++){
    D[i] = INFINITY;
  }
  D[0] = 0;
  for(i = 0; i < G->n(); i++){
    v = minVertex(G, D);
    if(D[v] == INFINITY)
      return;
    G->setMark(v, VISITED);
    for(w = G->first(v); w < G->n(); w = G->next(v, w))
      if(D[w] > (D[v] + G->weight(v,w)))
        D[w] = D[v] + G->weight(v, w);
  }
}

int minVertex(Graph *G, int *D){
  int i, v=-1;

  for(i = 0; i < G->n(); i++){
    if(G->getMark(i) == UNVISITED){
      v = i;
      break;
    }
  }
  for(i++; i < G->n(); i++){
    if((G->getMark(i) == UNVISITED) && (D[i] < D[v]))
    v = i;
  }
  return v;
}
 
算法中的每个结点使用整数表示，数组D[ ]定义了从出发点s到每个点v的最短路径，被初始化为INFINITY。另外，每个结点还有一个标识（Mark），通过函数setMark和getMark来设置和读取。标识具有两种状态：VISITED和UNVISITED。算法的工作步骤被描述如下：
 
1. 把所有结点的标识都设为UNVISITED，距离设为INFINIT。
 
2. 把出发点s的距离设置为0，状态设置为VISITED。
 
3. 从图中所有UNVISITED的点中选择距离最小的结点v。
 
4. 设置v的状态为VISITED。
 
5. 用v来更新其相邻结点。若某相邻结点u的当前距离D[u] > D[v] + weight(v, u)，则把u的距离D[u]更新为D[v] + weight(v, u)。
 
6. 重复3到5步的操作，直到所有结点状态都被设置为VISITED。
 
以图1为例，算法的计算过程为：
 
1. D[A] = 0。
 
 
2. 选择D[A]为距离最小的结点，设其状态为VISITED；更新D[B] = 10, D[C] = 3, D[D] = 20。
 
3. 选择D[C]为距离最小的结点，设其状态为VISITED；更新D[B] = D[C] + weight(C, B) = 3 + 2 = 5, D[E] = D[C] + weight(C, E) = 3 + 15 =18。
 
4. 选择D[B]为距离最小的结点，设其状态为VISITED；更新D[D] = D[B] + weight(B, D) = 5 + 5 = 10。
 
5. 选择D[D]为距离最小的结点，设其状态为VISITED；与D相连的结点E的距离D[E] = 18，小于D[D] + weight(D, E) = 10 + 11 = 21，所以不需要更新。
 
6. 选择D[D]为距离最小的结点，设其状态为VISITED；没有相连的点，所以不需要更新。
 
所以最终每个点的最小距离为D[A] = 0; D[B] = 5]; D[C] = 3]; D[D] = 10; D[E] = 18.
 
2. 算法正确性证明
 
上一节描述的Dijkstra算法把图中的结点分为两个部分，分别标记为VISITED和UNVISITED，使用S和V-S来表示。为证明的方便，区分了S和V-S中的点的距离函数，分别为D和D_est，V-S中的距离函数被称为估值函数。算法的主要操作是循环执行第3到5步。证明算法的正确性，可以通过证明每次循环执行之前，S和V-S中的结点满足以下3条属性，执行之后依然满足。
 
属性1. S中任意m的点的的路径长度D[m]就是其最短路径。
 
 
属性2. 估值函数满足下述条件： 
 
也就是说，对于V-S中的任意结点n，其估值路径D_est[n]是其只通过S中结点的最短路径。
 
 
属性3. V-S中估值最小的点n，D_est[n]的值就是其最短路径。
 
算法第一步S={s}，只包含出发结点，且D[s]=0，故而满足属性1，更新相邻结点之后，容易证明，也满足属性2。属性3则需要证明，过程如下。
 
证明：假设D_est[n]不是n的最短路径，因为D_est是只通过S中结点的最短路径，所以结点n的真实的最短路径必然会经过集合S之外的结点，设路径上第一个非S中的点为j。则真实的最短路径的形式为s->...->j->...->n。因为假设了j之前的点都是S中的，所以根据属性2，D_est[j] < =D[n] < D_est[n]，与n是估值最小的结点矛盾，所以属性成立。
 
算法接下来的操作是把n加入S，并试图更新V-S中结点的距离估值，容易证明，3-5步的一次操作之后，属性1-3仍然满足，所以得证。
 
 

1.算法定义
 
 
 
算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
 
 

  一个算法应该具有以下七个重要的特征： 
 

   ①有穷性（Finiteness）：算法的有穷性是指算法必须能在执行有限个步骤之后终止； 
  
 ②确切性(Definiteness)：算法的每一步骤必须有确切的定义； 
  
 ③输入项(Input)：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输 入是指算法本身定出了初始条件； 
  
 ④输出项(Output)：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没 有输出的算法是毫无意义的； 
  
 ⑤可行性(Effectiveness)：算法中执行的任何计算步骤都是可以被分解为基本的可执行 的操作步，即每个计算步都可以在有限时间内完成（也称之为有效性）； 
  
 ⑥高效性(High efficiency)：执行速度快，占用资源少； 
  
 ⑦健壮性(Robustness)：对数据响应正确。 
 
 
 
2. 时间复杂度
 
 
 
计算机科学中，算法的时间复杂度是