2011 年计算机学科专业基础综合全国联考卷

             

1. 一、单项选择题

   第 1-40 小题,每小题 2 分,共 80 分,下列每小题给出的四个选项中,只有一项符合题目要求的.请在答题卡上将所选项的字母涂黑.

   1.设 $n$ 是描述问题规模的非负整数,下面程序片段的时间复杂度是
$\qquad$ x = 2;
$\qquad$ while(x < n/2)
$\qquad$ $\quad$ x = 2*x;
A. $O(log_2n)$ $\quad$ B. $O(n)$ $\quad$ C. $O(nlog_2n)$ $\quad$ D. $O(n^2)$

   2. 元素 $a$,$b$,$c$,$d$,$e$ 依次进入初始为空的栈中,若元素进栈后可停留、可出栈,直到所有元素都出栈,则在所有可能的出栈序列中,以元素 $d$ 开头的序列个数是
A. 3 $\quad$ B. 4 $\quad$ C. 5 $\quad$ D. 6

   3.已知循环队列存储在一维数组 $A[0...n-1]$ 中,且队列非空时 front 和 rear 分别指向队头元素和队尾元素.若初始时队列为空,且要求第 1 个进入队列的元素存储在 $A[0]$ 处,则初始时 front 和 rear 的值分别是
A.$0$,$0$ $\quad$ B.$0$,$n-1$ $\quad$ C.$n-1$,$0$ $\quad$ D.$n-1$,$n-1$

   4.若一棵完全二叉树有 768 个结点,则该二叉树中叶结点的个数是
A. 257 $\quad$ B. 258 $\quad$ C. 384 $\quad$ D. 385

   5.若一棵二叉树的前序遍历序列和后序遍历序列分别为 1,2,3,4 和 4,3,2,1,则该二叉树的中序遍历序列不会是
A.1,2,3,4 $\quad$ B.2,3,4,1 $\quad$ C.3,2,4,1 $\quad$ D.4,3,2,1

   6.已知一棵有 2011 个结点的树,其叶结点个数为 116,该树对应的二叉树中无右孩子的结点个数是
A.115 $\quad$ B.116 $\quad$ C.1895 $\quad$ D.1896

   7.对于下列关键字序列,不可能构成某二叉排序树中一条查找路径的序列是
A.95,22,91,24,94,71 $\quad$ B.92,20,91,34,88,35
C.21,89,77,29,36,38 $\quad$ D.12,25,71,68,33,34

   8.下列关于图的叙述中,正确的是
Ⅰ. 回路是简单路径
Ⅱ.存储稀疏图,用邻接矩阵比邻接表更省空间
Ⅲ.若有向图中存在拓扑序列,则该图不存在回路
A.仅Ⅱ $\quad$ B.仅Ⅰ、Ⅱ $\quad$ C.仅Ⅲ $\quad$ D.仅Ⅰ、Ⅲ

   9.为提高散列(Hash)表的查找效率,可以采取的正确措施是
Ⅰ. 增大装填(载)因子
Ⅱ.设计冲突(碰撞)少的散列函数
Ⅲ.处理冲突(碰撞)时避免产生聚集(堆积)现象
A.仅Ⅰ $\quad$ B.仅Ⅱ $\quad$ C.仅Ⅰ、Ⅱ $\quad$ D.仅Ⅱ、Ⅲ

   10.为实现快速排序算法,待排序序列宜采用的存储方式是
A.顺序存储 $\quad$ B.散列存储 $\quad$ C.链式存储 $\quad$ D.索引存储

   11. 已知序列 25,13,10,12,9 是大根堆,在序列尾部插入新元素 18,将其再调整为大根堆,调整过程中元素之间进行的比较次数是
A.1 $\quad$ B.2 $\quad$ C.4 $\quad$ D.5

   12.下列选项中,描述浮点数操作速度指标的是
A.MIPS $\quad$ B.CPI $\quad$ C.IPC $\quad$ D.MFLOPS

   13.float 型数据通常用 IEEE 754 单精度浮点数格式表示.若编译器将 float 型变量 $x$ 分配在一个 $32$ 位浮点寄存器 FR1 中,且 $x$=$-8.25$,则 FR1 的内容是
A.C104 0000H $\quad$ B.C242 0000H $\quad$ C.C184 0000H $\quad$ D.C1C2 0000H

   14.下列各类存储器中,不采用随机存取方式的是
A.EPROM $\quad$ B.CDROM $\quad$ C.DRAM $\quad$ D.SRAM

   15.某计算机存储器按字节编址,主存地址空间大小为 64MB,现用 4M×8 位的 RAM 芯片组成 32MB 的主存储器,则存储器地址寄存器 MAR 的位数至少是
A.22 位 $\quad$ B.23 位 $\quad$ C.25 位 $\quad$ D.26 位

   16.偏移寻址通过将某个寄存器内容与一个形式地址相加而生成有效地址.下列寻址方式中,属于偏移寻址方式的是
A.间接寻址 $\quad$ B.基址寻址 $\quad$ C.相对寻址 $\quad$ D.变址寻址

   17.某机器有一个标志寄存器,其中有进位/借位标志 CF、零标志 ZF、符号标志 SF 和溢出标志 OF,条件转移指令 bgt(无符号整数比较大于时转移)的转移条件是
A.$CF+OF=1$ $\quad$ B.$\overline{SF}+ZF=1$ $\quad$ C.$\overline{CF+ZF}=1$ $\quad$ D.$\overline{CF+SF}=1$

   18.下列给出的指令系统特点中,有利于实现指令流水线的是
Ⅰ. 指令格式规整且长度一致
Ⅱ.指令和数据按边界对齐存放
Ⅲ.只有 Load/Store 指令才能对操作数进行存储访问
A.仅Ⅰ、Ⅱ $\quad$ B.仅Ⅱ、Ⅲ $\quad$ C.仅Ⅰ、Ⅲ $\quad$ D.Ⅰ、Ⅱ、Ⅲ

   19.假定不采用 Cache 和指令预取技术,且机器处于 “开中断” 状态,则在下列有关指令执行的叙述中,错误的是
A.每个指令周期中 CPU 都至少访问内存一次
B.每个指令周期一定大于或等于一个 CPU 时钟周期
C.空操作指令的指令周期中任何寄存器的内容都不会被改变
D.当前程序在每条指令执行结束时都可能被外部中断打断

   20.在系统总线的数据线上,不可能传输的是
A.指令 $\quad$ B.操作数 $\quad$ C.握手(应答)信号 $\quad$ D.中断类型号

   21.某计算机有五级中断 $L4$~$L0$,中断屏蔽字为 $M_4M_3M_2M_1M_0$,$M_i=1$(0≤i≤4)表示对 $L_i$ 级中断进行屏蔽.若中断响应优先级从高到低的顺序是 $L4$→$L0$→$L2$→$L1$→$L3$,则 $L_1$ 的中断处理程序中设置的中断屏蔽字是
A.11110 $\quad$ B.01101 $\quad$ C.00011 $\quad$ D.01010

   22.某计算机处理器主频为 50MHz,采用定时查询方式控制设备 A 的 I/O,查询程序运行一次所用的时钟周期数至少为 500.在设备 A 工作期间,为保证数据不丢失,每秒需对其查询至少 200 次,则 CPU 用于设备 A 的 I/O 的时间占整个 CPU 时间的百分比至少是
A.0.02% $\quad$ B.0.05% $\quad$ C.0.20% $\quad$ D.0.50%

   23.下列选项中,满足短任务优先且不会发生饥饿现象的调度算法是
A.先来先服务 $\quad$ B.高响应比优先 $\quad$ C.时间片轮转 $\quad$ D.非抢占式短任务优先

   24.下列选项中,在用户态执行的是 A.命令解释程序 $\quad$ B.缺页处理程序 $\quad$ C.进程调度程序 $\quad$ D.时钟中断处理程序

   25.在支持多线程的系统中,进程 P 创建的若干个线程不能共享的是 A.进程 P 的代码段 $\quad$ B.进程 P 中打开的文件 $\quad$ C.进程 P 的全局变量 $\quad$ D.进程 P 中某线程的栈指针

   26.用户程序发出磁盘 I/O 请求后,系统的正确处理流程是
A.用户程序→系统调用处理程序→中断处理程序→设备驱动程序
B.用户程序→系统调用处理程序→设备驱动程序→中断处理程序
C.用户程序→设备驱动程序→系统调用处理程序→中断处理程序
D.用户程序→设备驱动程序→中断处理程序→系统调用处理程序

   27. 某时刻进程的资源使用情况如下表所示.

表1:第 27 题表
分配 资源 分配 用资
R1 R2 R3 R1 R2 R3 R1 R2 R3
P1 2 0 0 0 0 1 0 2 1
P2 1 2 0 1 3 2 0 2 1
P3 0 1 1 1 3 1 0 2 1
P4 0 0 1 2 0 0 0 2 1

   此时的安全序列是
A.P1,P2,P3,P4
B.P1,P3,P2,P4
C.P1,P4,P3,P2
D.不存在

   28. 在缺页处理过程中,操作系统执行的可能是
Ⅰ. 修改页表 $\quad$ Ⅱ.磁盘 I/O $\quad$ Ⅲ.分配页框
A.仅Ⅰ、Ⅱ $\quad$ B.仅Ⅱ $\quad$ C.仅Ⅲ $\quad$ D.Ⅰ、Ⅱ和Ⅲ

   29.当系统发生抖动(.当系统发生抖动(thrashing thrashing)时,可用采取的有效措施是)
Ⅰ. 撤销部分进程
Ⅱ.增加磁盘交换区的容量
Ⅲ.提高用户进程的优先级
A.仅Ⅰ $\quad$ B.仅Ⅱ $\quad$ C.仅Ⅲ $\quad$ D.仅Ⅰ、Ⅱ

   30.在虚拟内存管理中,地址变换机构将逻辑变换为物理地址,形成该逻辑地址的阶段是
A.编辑 $\quad$ B.编译 $\quad$ C.链接 $\quad$ D.装载

   31.某文件占 $10$ 个磁盘块,现要把该文件磁盘块逐个读入主存缓冲区,并送用户区进行分析,假设一个缓冲区与一个磁盘块大小相同,把一个磁盘块读入缓冲区的时间为 $100\mu s$,将缓冲区的数据传送到用户区的时间是 $50\mu s$,CPU 对一块数据进行分析的时间为 $50\mu s$.在单缓冲区和双缓冲区结构下,读入并分析完该文件的时间分别是
A.$1500\mu s$、$1000\mu s$ $\quad$ B.$1550\mu s$、$1100\mu s$
C.$1550\mu s$、$1550\mu s$ $\quad$ D.$2000\mu s$、$2000\mu s$

   32.有两个并发执行的进程 $P1$ 和 $P2$,共享初值为 $1$ 的变量 $x$.$P1$ 对 $x$ 加 $1$,$P2$ 对 $x$ 减 $1$.加 $1$ 和减 $1$ 操作的指令序列分别如下所示.

   // 加 1 操作
load R1,x // 取 $x$ 到寄存器 $R1$ 中
inc R1
store x,R1 // 将 $R1$ 的内容存入 $x$

   // 减 1 操作
load R2,x // 取 $x$ 到寄存器 $R2$ 中
dec R2
store x,R2 // 将 $R2$ 的内容存入 $x$

   两个操作完成后,$x$ 的值
A.可能为-1 或 3
B.只能为 1
C.可能为 0、1 或 2
D.可能为-1、0、1 或 2

   33.TCP/IP 参考模型的网络层提供的是
A.无连接不可靠的数据报服务 $\quad$ B.无连接可靠的数据报服务
C.有连接不可靠的虚电路服务 $\quad$ D.有连接可靠的虚电路服务

   34.若某通信链路的数据传输速率为 2400bps,采用 4 相位调制,则该链路的波特率是
A.600 波特 $\quad$ B.1200 波特 $\quad$ C.4800 波特 $\quad$ D.9600 波特

   35.数据链路层采用选择重传协议(SR)传输数据,发送方已发送了 0~3 号数据帧,现已收到 1 号帧的确认,而 0、2 号帧依次超时,则此时需要重传的帧数是
A.1 $\quad$ B.2 $\quad$ C.3 $\quad$ D.4

   36.下列选项中,对正确接收到的数据帧进行确认的 MAC 协议是
A.CSMA $\quad$ B.CDMA $\quad$ C.CSMA/CD $\quad$ D.CSMA/CA

   37. 某网络拓扑如下图所示,路由器 R1 只有到达子网 192.168.1.0/24 的路由.为使 R1 可以将 IP 分组正确地路由到图中所有子网,则在 R1 中需要增加的一条路由(目的网络,子网掩码,下一跳)是

图
图 1:第 37 题图

  
A.192.168.2.0 $\quad$ 255.255.255.128 $\quad$ 192.168.1.1
B.192.168.2.0 $\quad$ 255.255.255.0 $\quad$ 192.168.1.1
C.192.168.2.0 $\quad$ 255.255.255.128 $\quad$ 192.168.1.2
D.192.168.2.0 $\quad$ 255.255.255.0 $\quad$ 192.168.1.2

   38. 在子网 192.168.4.0/30 中,能接收目的地址为 192.168.4.3 的 IP 分组的最大主机数是
A.0 $\quad$ B.1 $\quad$ C.2 $\quad$ D.4

   39.主机甲向主机乙发送一个(SYN=1,seq=11220)的 TCP 段,期望与主机乙建立 TCP 连接,若主机乙接受该连接请求,则主机乙向主机甲发送的正确的 TCP 段可能是
A.(SYN=0,ACK=0,seq=11221,ack=11221)
B.(SYN=1,ACK=1,seq=11220,ack=11220)
C.(SYN=1,ACK=1,seq=11221,ack=11221)
D.(SYN=0,ACK=0,seq=11220,ack=11220)

   40.主机甲与主机乙之间已建立一个 TCP 连接,主机甲向主机乙发送了 3 个连续的 TCP 段,分别包含 300 字节、400 字节和 500 字节的有效载荷,第 3 个段的序号为 900.若主机乙仅正确接收到第 1 和第 3 个段,则主机乙发送给主机甲的确认序号是
A.300 $\quad$ B.500 $\quad$ C.1200 $\quad$ D.1400

2. 二、综合应用题

   第 41~47 小题,共 70 分.请将答案写在答题纸指定位置上.

   41.(8 分)已知有 $6$ 个顶点(顶点编号为为 $0$~$5$)的有向带权图 $G$,其邻接矩阵 $A$ 为上三角矩阵,按行为主序(行优先)保存在如下的一维数组中.

表2:第 41 题图
$4$ $6$ $\infty$ $\infty$ $\infty$ $5$ $\infty$ $\infty$ $\infty$ $4$ $3$ $\infty$ $\infty$ $3$ $3$

   要求:
(1)写出图 $G$ 的邻接矩阵 $A$.
(2)画出有向带权图 $G$.
(3)求图 $G$ 的关键路径,并计算该关键路径的长度.

   42.(15 分)一个长度为 $L(L > =1)$ 的升序序列 $S$,处在第 $L/2$ 个位置的数称为 $S$ 的中位数.
例如,若序列 $S1=(11,13,15,17,19)$,则 $S1$ 的中位数是 $15$,两个序列的中位数是含它们所有元素的升序序列的中位数.例如,若 $S2=(2,4,6,8,20)$,则 $S1$ 和 $S2$ 的中位数是 $11$.现在有两个等长升序序列 $A$ 和 $B$,试设计一个在时间和空间两方面都尽可能高效的算法,找出两个序列 $A$ 和 $B$ 的中位数.要求:
(1)给出算法的基本设计思想.
(2)根据设计思想,采用 C 或 C++或 JAVA 语言描述算法,关键之处给出注释.
(3)说明你所设计算法的时间复杂度和空间复杂度.

3. 参考答案

4. 一、单项选择题

   1. 解答:A.程序中,执行频率最高的语句为 “$x=2*x$”.设该语句执行了 $t$ 次,则 $2t+1=n/2$,故 $t=log2(n/2)-1=log2n-2= O(log2n)$.

   2. 解答:B.出栈顺序必为 d_c_b_a_,e 的顺序不定,在任意一个 “_” 上都有可能.

   3. 解答:B.插入元素时,front 不变,rear+1.而插入第一个元素之后,队尾要指向尾元素,显然,rear 初始应该为 $n-1$,front 为 $0$.

   4. 解答:C.叶结点数为 $n$,则度为 2 的结点数为 $n-1$,度为 1 的结点数为 0 或 1,本题中为 1(总结点数为偶数),故而即 $2n=768$.

   5. 解答:C.由前序和后序遍历序列可知 3 为根结点,故(1,2)为左子树,(4)为右子树,C 不可能.或画图即可得出结果.

   6. 解答:D.本题可采用特殊情况法解.设题意中的树是如下图所示的结构,则对应的二叉树中仅有前 115 个叶结点有右孩子.

图
图 2:第 6 题解答图

   7. 解答:A.选项 A 中,当查到 91 后再向 24 查找,说明这一条路径之后查找的数都要比 91 小,后面的 94 就错了.

   8. 解答:C.Ⅰ.回路对应于路径,简单回路对应于简单路径;Ⅱ.刚好相反;Ⅲ.拓扑有序的必要条件.故选 C.

   9. 解答:B.III 错在 “避免” 二字.

   10. 解答:A.内部排序采用顺序存储结构.

   11. 解答:B.首先与 10 比较,交换位置,再与 25 比较,不交换位置.比较了二次.

   12. 解答:D.送分题.

   13. 解答:A.$x$ 的二进制表示为 $-1000.01$﹦$-1.000 01$×$2^{11}$ 根据 IEEE754 标准隐藏最高位的 “$1$”,又 $E-127=3$,所以 $E=130=1000 0010_{(2)}$ 数据存储为 $1$ 位数符+$8$ 位阶码(含阶符)+$23$ 位尾数. 故 FR1 内容为 1 10000 0010 0000 10000 0000 0000 0000 000,即 1100 0001 0000 0100 0000 0000 0000 0000,即 C104000H.

   14. 解答:B.光盘采用顺序存取方式.

   15. 解答:D.64MB 的主存地址空间,故而 MAR 的寻址范围是 64M,故而是 26 位.而实际的主存的空间不能代表 MAR 的位数.

   16. 解答:A.间接寻址不需要寄存器,EA=(A).基址寻址:EA=A+基址寄存器内同;相对寻址:EA﹦A+PC 内容;变址寻址:EA﹦A+变址寄存器内容.

   17. 解答:C.无符号整数比较,如 A>B,则 A-B 无进位/借位,也不为 0.故而 CF 和 ZF 均为 0.

   18. 解答:D.指令定长、对齐、仅 Load/Store 指令访存,以上三个都是 RISC 的特征.均能够有效的简化流水线的复杂度.

   19. 解答:C.会自动加 1,A 取指令要访存、B 时钟周期对指令不可分割.

   20. 解答:C.握手(应答)信号在通信总线上传输.

   21. 解答:D.高等级置 0 表示可被中断,比该等级低的置 1 表示不可被中断.

   22. 解答:C.每秒 200 次查询,每次 500 个周期,则每秒最少 200×500﹦10 0000 个周期,100000÷50M=0.20%.

   23. 解答:B.响应比=作业响应时间/作业执行时间=(作业执行时间+作业等待时间)/作业执行时间.高响应比算法,在等待时间相同情况下,作业执行时间越少,响应比越高,优先执行,满足短任务优先.随着等待时间增加,响应比也会变大,执行机会就增大,所以不会产生饥饿现象.先来先服务和时间片轮转不符合短任务优先,非抢占式短任务优先会产生饥饿现象.

   24. 解答:A.缺页处理程序和时钟中断都属于中断,在核心态执行.进程调度属于系统调用在核心态执行,命令解释程序属于命令接口,它在用户态执行.

   25. 解答:D.进程中某线程的栈指针,对其它线程透明,不能与其它线程共享.

   26. 解答:B.输入/输出软件一般从上到下分为四个层次:用户层、与设备无关软件层、设备驱动程序以及中断处理程序.与设备无关软件层也就是系统调用的处理程序.所以争取处理流程为 B 选项.

   27. 解答:D.使用银行家算法得,不存在安全序列.

   28. 解答:D.缺页中断调入新页面,肯定要修改页表项和分配页框,所以 I、III可能发生,同时内存没有页面,需要从外存读入,会发生磁盘 I/O.

   29. 解答:A.在具有对换功能的操作系统中,通常把外存分为文件区和对换区.前者用于存放文件,后者用于存放从内存换出的进程.抖动现象是指刚刚被换出的页很快又要被访问为此,又要换出其他页,而该页又快被访问,如此频繁的置换页面,以致大部分时间都花在页面置换上.撤销部分进程可以减少所要用到的页面数,防止抖动.对换区大小和进程优先级都与抖动无关.

   30. 解答:B.编译过程指编译程序将用户源代码编译成目标模块.源地址编译成目标程序时,会形成逻辑地址.

   31. 解答:B.单缓冲区下当上一个磁盘块从缓冲区读入用户区完成时下一磁盘块才能开始读入,也就是当最后一块磁盘块读入用户区完毕时所用时间为150×10=1500.加上处理最后一个磁盘块的时间50为1550.双缓冲区下,不存在等待磁盘块从缓冲区读入用户区的问题,也就是100×10+100=1100.

   32. 解答:C.将 P1 中 3 条语句变为 1,2,3,P2 中 3 条语句编为 4,5,6.则依次执行 1,2,3,4,5 得结果 1,依次执行 1,2,4,5,6,3 得结果 2,执行 4,5,1,2,3,6 得结果 0.结果-1 不可能得出,选 C.

   33. 解答:A.TCP/IP 的网络层向上只提供简单灵活的、无连接的、尽最大努力交付的数据报服务.此外考察 IP 首部,如果是面向连接的,则应有用于建立连接的字段,但是没有;如果提供可靠的服务,则至少应有序号和校验和两个字段,但是 IP 分组头中也没有(IP 首部中只是首部校验和).因此网络层提供的无连接不可靠的数据服务.有连接可靠的服务由传输层的 TCP 提供

   34. 解答:B.有 $4$ 种相位,则一个码元需要由 $log24=2$ 个 bit 表示,则波特率=比特率/$2$=$1200$ 波特.

   35. 解答:B.选择重传协议中,接收方逐个地确认正确接收的分组,不管接收到的分组是否有序,只要正确接收就发送选择 ACK 分组进行确认.因此选择重传协议中的 ACK 分组不再具有累积确认的作用.这点要特别注意与 GBN 协议的区别.此题中只收到 1 号帧的确认,0、2 号帧超时,由于对于 1 号帧的确认不具累积确认的作用,因此发送方认为接收方没有收到 0、2 号帧,于是重传这两帧.

   36. 解答:D.可以用排除法.首先 CDMA 即码分多址,是物理层的东西;CSMA/CD 即带冲突检测的载波监听多路访问,这个应该比较熟悉,接收方并不需要确认;CSMA,既然 CSMA/CD 是其超集,CSMA/CD 没有的东西,CSMA 自然也没有.于是排除法选 D.CSMA/CA 是无线局域网标准 802.11 中的协议.CSMA/CA 利用 ACK 信号来避免冲突的发生,也就是说,只有当客户端收到网络上返回的 ACK 信号后才确认送出的数据已经正确到达目的地址.

   37. 解答:D.此题主要考察路由聚合.要使 R1 能够正确将分组路由到所有子网,则 R1 中需要有到 192.168.2.0/25 和 192.168.2.128/25 的路由.观察发现网络 192.168.2.0/25 和 192.168.2.128/25 的网络号的前 24 位都相同,于是可以聚合成超网 192.168.2.0/24.从图中可以看出下一跳地址应该是 192.168.1.2.

   38. 解答:C.首先分析 192.168.4.0/30 这个网络.主机号占两位,地址范围 192.168.4.0/30~ 192.168.4.3/30,即可以容纳(4-2=2)个主机.主机位为全 1 时,即 192.168.4.3,是广播地址,因此网内所有主机都能收到,因此选 C.

   39. 解答:C.主机乙收到连接请求报文后,如同意连接,则向甲发送确认.在确认报文段中应把 SYN 位和 ACK 位都置 1,确认号是甲发送的 TCP 段的初始序号 seq=11220 加 1,即为 ack= 11221,同时也要选择并消耗一个初始序号 seq,seq 值由主机乙的 TCP 进程确定,本题取 seq= 11221 与确认号、甲请求报文段的序号没有任何关系.

   40. 解答:B.TCP 段首部中的序号字段是指本报文段所发送的数据的第一个字节的序号.第三个段的序号为 900,则第二个段的序号为 900-400=500.而确认号是期待收到对方下一个报文段的第一个字节的序号.现在主机乙期待收到第二个段,故甲的确认号是 500.

5. 二、综合应用题

   41. 解答: (1)图 G 的邻接矩阵 A 如下所示.
(待输入……)

   (2)有向带权图 G 如下图所示.

图
图 3:向带权图 G

   (3)关键路径为 $0- > 1- > 2- > 3->5$(如下图所示粗线表示),长度为 $4+5+4+3=16$.

图
图 4:关键路径

   42. 解答:
(1)算法的基本设计思想如下.
分别求出序列 $A$ 和 $B$ 的中位数,设为 $a$ 和 $b$,求序列 $A$ 和 $B$ 的中位数过程如下:
1)若 $a=b$,则 $a$ 或 $b$ 即为所求中位数,算法结束.
2)若 $a < b$,则舍弃序列 $A$ 中较小的一半,同时舍弃序列 $B$ 中较大的一半,要求舍弃的长度相等;
3)若 $a > b$,则舍弃序列 $A$ 中较大的一半,同时舍弃序列 $B$ 中较小的一半,要求舍弃的长度相等;
在保留的两个升序序列中,重复过程 1)、2)、3),直到两个序列中只含有一个元素时为止,较小者即为所求的中位数.

   (2)算法的实现如下: (待输入……)

   (3)算法的时间复杂度为 $O(log_2n)$,空间复杂度为 $O(1)$.

致读者: 小时百科一直以来坚持所有内容免费无广告,这导致我们处于严重的亏损状态。 长此以往很可能会最终导致我们不得不选择会员制,大量广告,内容付费等。 因此,我们请求广大读者热心打赏 ,使网站得以健康发展。 如果看到这条信息的每位读者能慷慨打赏 10 元,我们一个星期内就能脱离亏损, 并保证网站能在接下来的一整年里向所有读者继续免费提供优质内容。 但遗憾的是只有不到 1% 的读者愿意捐款, 他们的付出帮助了 99% 的读者免费获取知识, 我们在此表示感谢。

         

© 小时科技 保留一切权利