Skip to content

Latest commit

 

History

History
256 lines (201 loc) · 5.99 KB

100.md

File metadata and controls

256 lines (201 loc) · 5.99 KB
  1. 哪一条边在下图的最小生成树中？

clip_image001.jpg

a. AB
b. CD
c. CE
d. EF

  1. 完全二叉树 (complete binary tree) 的节点 (node) 的编号由最上层 (level 0) 往下、每一层由左往右依序编号。下图为一个完全二叉树，共有 15 个节点，节点编号如图所示。

clip_image001.png

一棵完全二叉树有 1025 个节点，最下面一层有多少个节点？

a. 1
b. 2
c. 511
d. 512

  1. 如果用数组表示最大堆，下面哪个不是最大堆？

a. 100, 99, 98, 97, …, 3, 2, 1
b. 10, 4, 7, 3, 1
c. 451, 102, 217, 58, 101, 218, 17, 10, 9, 8, 7, 6, 5, 4, 3
d. 50, 40, 30, 20, 10, 5, 25

  1. 要从乱序的 15 个不同的数中通过比较找出次大值，最坏情况下要比较多少次？

a. 14
b. 17
c. 21
d. 27

  1. 哪一个选项是下图的 BFS 序？

clip_image005.gif

a. 1→2→6→3→7→5→4
b. 1→2→3→4→7→5→6
c. 1→6→2→7→3→4→5
d. 1→6→5→7→2→3→4

  1. 将 1,2,3,4,5,6 依次 push 入一个栈，下面哪一个出栈序列是不可能出现的？

a. 215436
b. 324156
c. 154623
d. 326541

  1. $10,$ $15,$ $x,$ $8,$ $23$ 依次插入一棵二叉查找树，那么其前序遍历不可能是哪一个？（$x$ 可为 $6,$ $9,$ $20,$ $25$）

a. 10, 6, 8, 15, 23
b. 10, 8, 15, 9, 23
c. 10, 8, 15, 20, 23
d. 10, 8, 15, 25, 23

  1. $f(n)=2^3n^2-3n$。如果 Big-O 的概念来表示这个函数，下面哪一个是不正确的？

a. $f(n) = O(n^1)$
b. $f(n) = O(n^2)$
c. $f(n) = O(n^3)$
d. $f(n) = O(n^4)$

  1. 有一算法的时间复杂度可用下面的 $T(n)$ 表示，那么这个算法的时间复杂度是
    $$T(n) = \begin{cases}\ 2T\left(\cfrac{n}{2}\right)+n^2, & n>1\ 1, & n=1 \end{cases}$$

a. $\Theta (n \log n)$
b. $\Theta (n^2)$
c. $\Theta (n^2 \log n)$
d. $\Theta (n^3)$

  1. 现在有 3 根柱子和 5 个大小不同的盘子。开始盘子都在第一根柱子上，大盘在下，小盘在上。现在你需要把这 5 个盘子移动到第三根柱子上，并且也是大的在下，小的在上。问至少要移动多少次。

a. 15
b. 33
c. 17
d. 31

  1. 有一种排序叫 pancake sorting。对于一个数字串，每一步只允许对该串的某个前缀倒置。现在将 5,3,4,1,2 排序成1,2,3,4,5，最少需要多少步？

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

  1. 假设一个无符号整数（unsigned int）占用两个 bytes，则执行下列程序后哪一个值会出现在荧屏上？
#include<stdio.h>
int main()
{
  unsigned int m = 32;
  printf("%x\n", ~m);
  return 0;
}

a. ffffffff
b. ffff0000
c. ffffffdf
d. ffffddfd

  1. 下列程序片段描述一个链表的节点结构
struct node
{
  struct node *llink;
  int item;
  struct node *rlink;
};

llink 指向前一个节点，rlink 指向后一个节点。想要在节点 x 后插入一个新节点，下面的程序要按什么次序执行？
<$\textrm{i}$> p->rlink = x->rlink;
<$\textrm{ii}$> x->rlink = p;
<$\textrm{iii}$> x->rlink->llink = p;
<$\textrm{iv}$> p->llink = x;

a. <$\textrm{i}$><$\textrm{ii}$><$\textrm{iii}$><$\textrm{iv}$>
b. <$\textrm{ii}$><$\textrm{i}$><$\textrm{iv}$><$\textrm{iii}$>
c. <$\textrm{iv}$><$\textrm{i}$><$\textrm{iii}$><$\textrm{ii}$>
d. <$\textrm{iv}$><$\textrm{iii}$><$\textrm{ii}$><$\textrm{i}$>

  1. 执行下面的程序后会输出什么
#include<stdio.h>
int f(int n)
{
  if ( n > 99 )
    return(n-10);
  return(f(f(n+11)));
}
void main()
{
  printf("%d", f(37) );
}

a. 90
b. 91
c. 92
d. 93

  1. n 为非负整数，加减乘除和大小比较需要常数等级的时间。根据下面的程序，哪一个描述是正确的？
long foo (long x, long n)
{
  long f;
  if (n % 2 == 0)
    f = 1;
  else
    f = x;
  if (n < 2)
    return f;
  return f*foo(x*x, n/2);
}

a. foo(x, n) 会返回 nx
b. foo(x, n) 会返回 xn
c. foo(x, n) 的时间复杂度是 $\Theta(\log x)$
d. foo(x, n) 的时间复杂度是 $\Theta(n \log n)$

  1. 执行下面的程序后会输出什么？
#include<stdio.h>
int f(int a)
{
  if (a == 0 || a == 1)
    return 1;
  return (f(a-1) + f(a-2));
}
int main ()
{
  printf("%d\n", f(10));
  return 0;
}

a. 8
b. 35
c. 89
d. 144

  1. 当程序设计师以 OOP 的思维模式开发一个「校务行政课程管理系统」时，下面哪一个通常不会用类 (class) 表示？

a. 学生
b. 教师
c. 课程
d. 姓名

  1. 下列哪种操作系统不是多工操作系统？

a. DOS (Disk Operating System)
b. Windows XP
c. Linux
d. FreeBSD

  1. 使用补码表示法，所能表示的最大的 64 位二进制整数是？

a. $2^{64}-1$
b. $2^{63}–1$
c. $10^{64} –1$
d. $10^{63}–1$

  1. 二进制数 101.101 的十进制表示是？

a. 101.101
b. 5.5
c. 5.625
d. 5.125

  1. 对于任何布尔型变量 $P$ 和 $Q$，$(P$ or $Q)=(P$ and $Q)$，那么下面哪个运算的结果是 true？（$\Leftrightarrow$ 表示当且仅当）

a. $P\Leftrightarrow Q$
b. not $P\Leftrightarrow Q$
c. $P\Leftrightarrow$ not $Q$
d. $P$ and $(Q\Leftrightarrow P)$

  1. $(57314)_8$ $+$ $(35023)_8$ $=$ ________

a. $(8\text{C}337){16}$
b. $(92337){16}$
c. $(112337){16}$
d. $(98\text{DF}){16}$

  1. 现有三个程序需要操作系统进行 CPU 处理。三个程序到达 CPU 的时间和运行所需的时间（以毫秒为单位）如下：
程序 抵达时间 运行耗时
P1 1 7
P2 3 2
P3 6 5

若该操作系统采用「先到先处理」的调度策略来处理这三个程序的话，则这三个程序的平均等待时间是多少毫秒？

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

  1. 下面哪一个不是 IPv4 地址？

a. 10.104.1.18
b. 172.16.3.1
c. 192.169.10.21
d. 222.122.265.5

  1. 小明有一台像素为 2592 × 1944 的数码相机，彩色品质是24 bits，拍摄一张照片需要多少空间存储？

a. 1.5MB
b. 15MB
c. 150MB
d. 1.5GB