词法分析部分算法的设计与实现 按学号尾号选择下列题...

一般而言，算法设计完成后，需要进行算法的模拟与分析。关于算法的模拟与分析回答问题：分析下列算法的时间复杂性。 Start of the Algorithm (1) S[1]=1; Sum=0; 初始化距离数组D[n][n]; /*I层的循环，即下列步骤为每次找出一个城市，I从2到n，即从找出第2个城市一直到找出第n个城市 (2) I=2; /*K层的循环，即下列步骤为从所有未访问过的城市中查找距离S[I-1]最近的城市j，K依然从2到n寻找 (3) K=2; (4) 将Dtemp设为一个大数(比所有两个城市之间的距离都大) /*L层的循环，即下列步骤为判断一个城市是否已被访问过，如果已被访问，则跳过该城市，寻找新的城市，L从1到I-1，因为已经有I-1个城市被访问过。 (5) L=1； (6) 如果S[L]==K，转步骤(10)； (7) L=L+1； (8) 如果L <i，转步骤(6)； *l层的循环结束 (9) (10) k="K+1;" (11) *k层的循环结束 (12) s[i]="j;" (13) sum="Sum+D[1," (14) i="I+1;" (15) *i层的循环结束 (16) j]； (17) 逐个输出s[n]中的全部元素; (18) 输出sum。 end of the algorithm> A、

B、

C、

D、

一般而言，算法设计完成后，需要进行算法的模拟与分析。关于算法的模拟与分析回答问题： 算法的时间复杂性T(n)，可以通过评估算法基本语句的执行次数来获得。分析下列算法的时间复杂性。 Start of the algorithm(算法开始) (1) 输入结点的数目n； (2) 当前最短路径Path设为空，当前最短距离Dtemp设为最大值； 注：一个路径是n个结点的一个组合，任何一个结点在路经中不能重复出现 (3) 组合一条新路径NewPath并计算该路径的距离D； (4) 如果D <dtemp 则path="NewPath，且Dtemp" d； (5) 如果所有路径组合完毕，则结束；否则转第(3)步继续执行； (6) 输出path及dtemp； end of the algorithm(算法结束)> A、

B、

C、

D、

下列三种算法是经常应用的内排序算法：插入排序、选择排序和冒泡排序。阅读下列算法，回答问题。 INSERTION-SORT(A) 1. for i=2 to N 2. { key = A[i] ; 3. j =i-1; 4. While (j>0 and A[j]>key) do 5. { A[j+1]=A[j]; 6. j=j-1; } 7. A[j+1]=key; 8. } SELECTION-SORT(A) 1. for i=1 to N-1 2. { k=i; 3． for j=i+1 to N 4. { if A[j] <a[k] then k="j;" } 5. if> i then 6. { 7. temp =A[k]; 8. A[k]=A[i]; 9. A[i]=temp; 10. } 11. } BUBBLE-SORT(A) 1. for i=1 to N-1 2. { haschange=false; 3. for j=1 to N-i 4. { if A[j]>A[j+1] then 5. { temp =A[j]; 6. A[j]=A[j+1]; 7. A[j]=temp; 8. haschange=true; 9. } 10. } 11. if (haschange ==false) then break; 12. } 关于排序的选择法和冒泡法，下列说法不正确的是_____。

A、“选择法”和“冒泡法”都是每一轮次找出一个最小值元素，只是寻找最小值元素的方法不一样，在效率方面没有什么差别；

B、“选择法”通过将所有未排序元素与当前轮次待寻找的最小值元素进行比较，获得当前轮次的最小值元素；而“冒泡法”通过相邻元素的两两比较，一个轮次完成也能获得一个最小值元素；

C、虽然“选择法”和“冒泡法”都是每一轮次找出一个最小值元素，但选择法每轮次仅比较，没有交换，直至找到最小值后做一次交换；而冒泡法每一轮次是通过相邻元素比较来找最小值，如果不满足排序，则交换相邻两个元素，交换可能频繁发生。这样来看，选择法比冒泡法要快一些；

D、上述说法有不正确的。

下列三种算法是经常应用的内排序算法：插入排序、选择排序和冒泡排序。阅读下列算法，回答问题。 INSERTION-SORT(A) 1. for i=2 to N 2. { key = A[i] ; 3. j =i-1; 4. While (j>0 and A[j]>key) do 5. { A[j+1]=A[j]; 6. j=j-1; } 7. A[j+1]=key; 8. } SELECTION-SORT(A) 1. for i=1 to N-1 2. { k=i; 3． for j=i+1 to N 4. { if A[j] <a[k] then k="j;" } 5. if> i then 6. { 7. temp =A[k]; 8. A[k]=A[i]; 9. A[i]=temp; 10. } 11. } BUBBLE-SORT(A) 1. for i=1 to N-1 2. { haschange=false; 3. for j=1 to N-i 4. { if A[j]>A[j+1] then 5. { temp =A[j]; 6. A[j]=A[j+1]; 7. A[j]=temp; 8. haschange=true; 9. } 10. } 11. if (haschange ==false) then break; 12. } 关于BUBBLE-SORT算法的基本思想，下列说法正确的是_____。

A、一个轮次一个轮次的处理。在每一轮次中依次对待排序数组元素中相邻的两个元素进行比较：如不符合排序关系，则交换两个元素。直到某一轮次没有元素交换发生则结束

B、一个元素一个元素的处理。每次处理一个元素，通过与当前已排序元素的比较，将该元素放入到当前正确排序的位置。直到最后一个元素则算法结束

C、一个轮次一个轮次的处理。将元素集合分成两个部分，已排序元素集合和未排序元素集合，开始时已排序元素集合为空。在每一轮次，从未排序元素集合中找出最小值的元素，将其移入已排序元素集合；直到未排序元素集合为空时则算法结束

D、其它三个选项都不正确

下列三种算法是经常应用的内排序算法：插入排序、选择排序和冒泡排序。阅读下列算法，回答问题。 INSERTION-SORT(A) 1. for i=2 to N 2. { key = A[i] ; 3. j =i-1; 4. While (j>0 and A[j]>key) do 5. { A[j+1]=A[j]; 6. j=j-1; } 7. A[j+1]=key; 8. } SELECTION-SORT(A) 1. for i=1 to N-1 2. { k=i; 3． for j=i+1 to N 4. { if A[j] <a[k] then k="j;" } 5. if> i then 6. { 7. temp =A[k]; 8. A[k]=A[i]; 9. A[i]=temp; 10. } 11. } BUBBLE-SORT(A) 1. for i=1 to N-1 2. { haschange=false; 3. for j=1 to N-i 4. { if A[j]>A[j+1] then 5. { temp =A[j]; 6. A[j]=A[j+1]; 7. A[j]=temp; 8. haschange=true; 9. } 10. } 11. if (haschange ==false) then break; 12. } 关于三种排序算法，下列说法正确的是_____。

A、三种算法的时间复杂度都为，所以三种算法的执行效率是一样的；

B、尽管三种算法的时间复杂度都为，但细致比较还是有差别的，例如冒泡法排序比选择法排序要快一些；

C、尽管细致比较三种算法的执行时间是有差别的，但这种差别对内排序问题而言是可以忽略不计的

D、尽管细致比较三种算法的执行时间是有差别的，这种差别对内排序问题而言是重要的，因为内排序算法可能要被频繁的执行

下列三种算法是经常应用的内排序算法：插入排序、选择排序和冒泡排序。阅读下列算法，回答问题。 INSERTION-SORT(A) 1. for i=2 to N 2. { key = A[i] ; 3. j =i-1; 4. While (j>0 and A[j]>key) do 5. { A[j+1]=A[j]; 6. j=j-1; } 7. A[j+1]=key; 8. } SELECTION-SORT(A) 1. for i=1 to N-1 2. { k=i; 3． for j=i+1 to N 4. { if A[j] <a[k] then k="j;" } 5. if> i then 6. { 7. temp =A[k]; 8. A[k]=A[i]; 9. A[i]=temp; 10. } 11. } BUBBLE-SORT(A) 1. for i=1 to N-1 2. { haschange=false; 3. for j=1 to N-i 4. { if A[j]>A[j+1] then 5. { temp =A[j]; 6. A[j]=A[j+1]; 7. A[j]=temp; 8. haschange=true; 9. } 10. } 11. if (haschange ==false) then break; 12. } 关于三种排序算法，下列说法正确的是_____。

A、尽管细致比较三种算法的执行时间是有差别的，这种差别对内排序问题而言是重要的，因为内排序算法可能要被频繁的执行

B、三种算法的时间复杂度都为，所以三种算法的执行效率是一样的

C、尽管三种算法的时间复杂度都为，但细致比较还是有差别的，例如冒泡法排序比选择法排序要快一些

D、尽管细致比较三种算法的执行时间是有差别的，但这种差别对内排序问题而言是可以忽略不计的

下列三种算法是经常应用的内排序算法：插入排序、选择排序和冒泡排序。阅读下列算法，回答问题。 INSERTION-SORT(A) 1. for i=2 to N 2. { key = A[i] ; 3. j =i-1; 4. While (j>0 and A[j]>key) do 5. { A[j+1]=A[j]; 6. j=j-1; } 7. A[j+1]=key; 8. } SELECTION-SORT(A) 1. for i=1 to N-1 2. { k=i; 3． for j=i+1 to N 4. { if A[j] <a[k] then k="j;" } 5. if> i then 6. { 7. temp =A[k]; 8. A[k]=A[i]; 9. A[i]=temp; 10. } 11. } BUBBLE-SORT(A) 1. for i=1 to N-1 2. { haschange=false; 3. for j=1 to N-i 4. { if A[j]>A[j+1] then 5. { temp =A[j]; 6. A[j]=A[j+1]; 7. A[j]=temp; 8. haschange=true; 9. } 10. } 11. if (haschange ==false) then break; 12. } 阅读BUBBLE-SORT算法，其中关于haschange变量的作用，下列说法不正确的是_____。

A、其它选项的说法有不正确的

B、haschange用于标记每个轮次的相邻元素比较中，是否有“交换”发生

C、haschange用于判断至某个轮次时是否已完成排序，以便提前结束算法

D、haschange需要在每轮次之前置初始值为假，表示没有“交换”发生

E、涉及haschange的语句全部去掉，算法仍旧能够正确执行