Skip to content

Latest commit

 

History

History
376 lines (311 loc) · 10.9 KB

105.md

File metadata and controls

376 lines (311 loc) · 10.9 KB
  1. 排序算法中常以交换的方式进行，交换代表某一个数字和某一个数字互换位置，例如给定一数列 $\texttt{5 3 2 4 1}$，我们想要将此数列从小到大排序，若不做重复的交换的话(同一个数字不能和另一个数字做两次以上的交换)，则至少要交换两次：

（目　标）$\texttt{1 2 3 4 5}$
（初始值）$\texttt{5 3 2 4 1}$
（第一次）$\texttt{1 3 2 4 5}$ 交换 $\texttt{(1,5)}$
（第二次）$\texttt{1 2 3 4 5}$ 交换 $\texttt{(2,3)}$

若要将数列 $\texttt{5 7 6 1 4 3 2}$ 进行排序（小到大），且不做重复的交换，最少交换几次后后即可完成排序?

a. 3
b. 4
c. 5
d. 6

  1. 利用较有效率的方法计算下列多项式时，总共需要几个加、减、乘法的运算？
    $$f(x) = 2x^4 + 3x^3 − 3x^2 + 5x − 1$$

a. 14
b. 12
c. 11
d. 8

  1. 给定下列物品清单，若卡车载重上限为 3500，请问最多可搬移多少价值的物品？
重量 815 906 127 914 633 98 279
价值 547 958 965 158 971 958 486

a. 5043
b. 4885
c. 4496
d. 4072

  1. 在图中，→ 表示机器人起点位置且为目前面对的方向， 机器人需要走到标注 ❤ 的位置。

Snipaste_2018-10-09_15-53-29.png

控制机器人的指令有两个：

  • CAN_MOVE(方向) 检查并回传是否可往「方向」前进
  • MOVE(方向) 表示往「方向」转后前进一步。

例如 CAN_MOVE(FORWARD) 即回传是否可往现在面对的方向前进一步；而 MOVE(LEFT) 则会让机器人左转并往前推进一步。

REPEAT UNTIL (Goal(❤))
{
  IF CAN_MOVE( 方向A ) MOVE( 方向A )
  IF CAN_MOVE( 方向B ) MOVE( 方向B )
  IF CAN_MOVE( 方向C ) MOVE( 方向C )
}

该程序会反复执行。请问： 方向 A 、方向 B 、 方向 C 应该分别设成什么，才可以让机器人以最短的路径走到 ❤ 的位置?

a. FORWARD, LEFT, RIGHT
b. RIGHT, FORWARD, LEFT
c. LEFT, FORWARD, RIGHT
d. LEFT, RIGHT, FORWARD

  1. 小城镇中的电车路线图如下，其中 A, B, C 和 D 表示四个站，单一箭头的连接线表示电车从端点为起站开向有箭头端的终站；双箭头的连接线表示两端点的站之间双向都有电车互通。

clip_image004.gif

若以一个二维数组 Map[i][j] 来记录这个电车路线图，Map[i][j]=1 表示从站 $i$ 到站 $j$ 有一条电车路线，否则 Map[i][j]=0。请问下列哪几个数组可以用以表示右侧电车路线图？

[1] [2] [3] [4]
0 0 0 0
1 0 1 0
0 1 0 1
1 1 1 0		 0 1 0 0
1 0 1 1
0 1 0 0
1 0 1 0		 0 1 1 1
1 0 0 1
0 0 0 0
0 1 1 0		 0 0 0 0
1 0 1 1
0 1 0 1
1 1 0 0

a. 只有数组 [1] 是可能的 b. 只有数组 [1] 跟 [3] 是可能的 c. 只有数组 [1] 跟 [4] 是可能的 d. 只有数组 [2] 跟 [3] 是可能的

  1. $e^x$ 的近似解可用下列式子表示：

$$e^x=1+\cfrac{x}{1!}+\cfrac{x^2}{2!}+\dots++\cfrac{x^{10}}{10!}$$

请在下划线处带入正确的式子，使该程序能正确计算 $e^x$。

scanf(“%d”,  &x);
sum=1;
n=0;
t=1;
while (n<10) {
  n++;
  t*=n;
  sum=________
}
printf(“e^x = %d”, sum);

a. sum+x^n/t
b. sum+x^t/n
c. sum+x*t/n
d. sum+x/t*n

  1. array 长度为 $n$。该程序拟将数组 array 的元素进行升幂排序，请问下划线处要填入哪个式子，才能使之正确排序？
for (int i=0; i < n-1; i++){
  for (int j=0; j < (a) ; j++){
    if (array[j+1] < array[j]){
      int temp = array[j];
      array[j] = array[j+1];
      array[j+1] = temp;
    }
  }
}

a. n
b. n - i
c. n – i - 1
d. n - 1

  1. f(10) 的返回值为________
int f(int n) {
  if (n<=3) return 1;
  return f(n-1)+f(n-2)+f(n-3);
}

a. 55
b. 57
c. 105
d. 193

x = 1;
y = 10;
for (int i=1; i<=2; i++)
  x = x + x;
for (int i=1; i<=2; i++)
  x = x * x;
y = x; x = y;
printf (“%d\n”, x);

该程序片段输出为________

a. 4
b. 10
c. 16
d. 256

int x=0, y=10; // 全局变量
int swap(int x, int y) {
  int temp = x;
  x = y;
  y = temp;
  return 0;
}
int main() {
  int x=5, ans=0;
  ans += x;
  swap(x, y);
  ans += y;
  printf(“%d\n”, ans);
  return 0;
}

该程序片段输出为________

a. 0
b. 5
c. 10
d. 15

  1. 给定 adjust() 函式及数组 a[] 的内容如下：
void adjust (int a[], int root, int n) {
  int child, rootkey;
  int temp;
  temp = a[root];
  rootkey = a[root];
  child = 2 * root;
  while (child <= n) {
    if ((child < n) && (a[child] < a[child+1]))
      child++;
      if (rootkey > a[child])
        break;
      else {
        a[child/2] = a[child];
        child *= 2;
      }
  }
  a[child/2] = temp;
}
$i$ 1 2 3 4 5 6 7 8 9 10
a[i] 26 5 77 1 61 11 59 15 48 19

若 $n=10$，则执行以下 for 循环之后，a[5] = ________

for (i=n/2; i>0; i--) adjust(a, i, n);

a. 11
b. 19
c. 26
d. 61

int nfind(char *string, char *pat) {
  int i, j, start = 0;
  int lasts = strlen(string) - 1;
  int lastp = strlen(pat) - 1;
  int endmatch = lastp;
  for (i = 0; endmatch <= lasts; endmatch++, start++) {
    if (string[endmatch] == pat[lastp])
      for (j=0, i=start; j<lastp && string[i]==pat[j];
                                             i++, j++);
    if (j == lastp)
      return start; /* successful */
  }
  return -1;
}

若 pat = $\texttt{aab}$, string = $\texttt{ababbaabaaabb}$，则 nfind(string, pat) 会返回________

a.5
b. 7
c. 9
d. -1

int i = 20;
while (i > 0) {
  for (int j=i; j<=i+15; j++)
    printf (“#”);
  i--;
}

它会输出________个 $\texttt{#}$。

a. 320
b. 300
c. 285
d. 280

  1. 背包客找寻旅馆时会以离捷运站距离及价格为考虑，若旅馆 $t$ 比旅馆 $t’$ 近捷运站， 则在距离条件上旅馆 $t$ 优于旅馆 $t’$。若旅馆 $t$ 比旅馆 $t’$ 价格便宜，则在价格条件上旅馆 $t$ 优于旅馆 $t’$。若旅馆 $t$ 的两个条件都优于旅馆 $t’$，或是一个条件相同另一个条件较优，都可说在整体条件上旅馆 $t$ 优于 $t’$。候选旅馆则是没有其他旅馆整体条件比它优的旅馆。下面的伪代码可挑出候选旅馆，当旅馆 $t$ 整体条件优于旅馆 $t’$，Compare(t,t’) 将回传 1；若旅馆 $t’$ 整体条件优于旅馆 $t$，则回传 2；否则回传 0。
C = Ø ;
for each hotel t in H do {
  check ← True;
  for each hotel t’ in C do {
    r ← Compare(t, t’);
    if (r==2) {
      check = False;
      break;
    }
    if (r==1) {
      C ← 将 t’从 C 中移除;
    }
  }
  if (check) {
    C ← 将 t 加入 C;
  }
}
return C;

若存储旅馆信息的数据库中共有 4 组数据：$H={$(200m, 2000 元)</code>、<code>(120m, 3000 元)</code>、<code>(500m, 2500 元)</code>、<code>(150m, 3200 元)$}$，第一个数字代表离捷运站的距离，第二个数字为价格。若要找出所有候选旅馆，Compare(t, t’) 共会被执行________次 a. 4
b. 5
c. 6
d. 8

  1. （续上题）若现有 20 间旅馆（以集合 $H$ 表示），但不知道这些旅馆的顺序，但已知最后找出的候选旅馆共有 4 间（以集合 $C$ 表示），请问上述伪码程序中 Compare(t, t’) 最多会执行________次

a. 64 次
b. 70 次
c. 80 次
d. 190 次

  1. 一个有 105 个数值的递增数列，使用二分查找，最多需搜寻 $m$ 次，最少需搜寻 $n$ 次，便可确定要搜寻的数值是否在数列中，则 $m+n=$________

a. 6
b. 7
c. 8
d. 9

  1. 有 $X, Y, Z$ 三个数，分别是 $X=(\text{E}4)_{16}$、$Y=(343.56)_8$、$Z=(11100100.11)_2$，请问这三个数的大小关系为何？

a. $X &gt; Y &gt; Z$
b. $Y &gt; X &gt; Z$
c. $Z &gt; Y &gt; X$
d. $Z &gt; X &gt; Y$

  1. 某哈希表 (hash table) 有 11 个空格，编号为 0 到 10。假设哈希函数 (hash function) 为 $h(k) = k \bmod 11$，且此哈希表使用平方探测法 (quadratic probing)：$h(k,i) = {[h(k) + i^2] \bmod 11, i =1, 2, 3, …}$ 处理碰撞 (collision)。依此方法，若将 27、35、21、4、59、75、33、41 等 8 个数字依序存入后，则此时编号 3 的位置存储的是________

a. 75
b. 33
c. 41
d. 没有数字

  1. 一棵二叉树使用后序遍历 (Postorder Traversal) 结果为 0, 6, 3, 7, 1, 4, 2, 5, 8, 9，使用中序遍历 (Inorder Traversal) 结果为 0, 4, 1, 6, 7, 3, 2, 8, 5, 9，则二叉树使用前序遍历 (Preorder Traversal) 结果为________

a. 9, 8, 2, 5, 4, 0, 1, 7, 6, 3
b. 6, 3, 7, 0, 1, 4, 2, 5, 8, 9
c. 9, 8, 2, 4, 0, 1, 7, 6, 3, 5
d. 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

  1. 假设系统中只有四个程序 P1，P2，P3 与 P4 欲执行，且每个程序分别需要花费 6ms、8ms、7ms 与 3ms 的 CPU 时间 (CPU time)。若采用最短时间优先 (shortest-job-first) 的调度策略时，在不考虑各种额外花费的时间 (overhead) 下，则这四个程序的平均等待时间（不包含程序本身运行时间）为多少？

a. 10ms
b. 11ms
c. 6ms
d. 7ms

  1. 已知若问题 A 存在解答，则问题 B 也存在解答。下列两推断是否正确？
  • Q1: 若问题 A 不可解， 问题 B 也不可解；
  • Q2: 若问题 B 不可解， 问题 A 也不可解。

a. Q1 正确、Q2 正确
b. Q1 正确、Q2 不正确
c. Q1 不正确、Q2 正确
d. Q1 不正确、Q2 不正确

  1. 右图是下列那一个逻辑表达式的真值表？
$A$ $B$ $C$ 结果
F F T F
F T F F
F T T T
T T F F

a. $(A$ OR $B)$ AND $(B$ OR $C)$
b. $(A$ AND $C)$ OR $(B$ AND $C)$
c. $(A$ AND $B)$ OR $(B$ AND $C)$
d. $(A$ OR $C)$ AND $(B$ OR $C)$

  1. 归并排序 (merge sort) 主要运用了哪种思想？

a. divide and conquer（分治法）
b. greedy algorithm（贪婪算法）
c. branch-and-bound（分支定界）
d. backtracking（回溯法）

  1. 已知有一个二叉树，以前序遍历 (Preorder Traversal) 走访节点的顺序为 C, D, A, B, E, F, G, H。以中序遍历 (Inorder Traversal) 走访节点的顺序为 A, D, B, C, G, F, H, E。以下叙述何者错误？

a. C 为根节点
b. F 是 G 的父节点
c. E 为一个叶节点
d. A 为 B 的兄弟节点

  1. 给定以下指令：
  • PUSH 用来将一组数据放入一个栈 (stack) 中，
  • POP 用来从栈顶取一组数据，并将取出数据存入一个最大值优先队列 (Priority queue)，
  • DEMAXQUEUE 用来从最大值优先队列中取出并输出其中的最大值数据

若依次执行下述指令后

PUSH(数据 1)
PUSH(数据 2)
POP
POP
DEMAXQUEUE
PUSH(数据 3)
POP
DEMAXQUEUE
DEMAXQUEUE

所得到的输出数据依序为 3, 2, 1。请问数据 1、数据 2、数据 3 应分别为哪个数字？

a. 数据 1 为 3, 数据 2 为 2, 数据 3 为 1
b. 数据 1 为 2, 数据 2 为 3, 数据 3 为 1
c. 数据 1 为 1, 数据 2 为 3, 数据 3 为 2
d. 以上皆可能