东北大学2012秋学期《算法设计与分析》在线作业2

谋学网

一、单选题（共 15 道试题，共 75 分。）V 1.   
- v0 U- I+ V& l! v7 s. u6 ^n个顶点的强连通图中至少含有

6 @$ E7 ?. L. j
, H; W; k* E4 j2 e( {! I+ }
5 q" h+ q$ \1 t% x; c4 ]A.     n-1条有向边                        
! T5 w' |& b+ b# n; o6 R9 V6 l: s, gB.    n条有向边

/ R6 _; |+ ^* n! X
C.   n(n-1)/2条有向边               
D.    n(n-1)条有向边
) o* ~. a4 t& f: S$ L9 n+ b6 d      满分：5  分
2.   
算法每条语句的执行时间应该是执行该语句一次所需的时间与该语句执行的次数的乘积，称为
$ f/ d0 C/ C  w/ y; R9 c
0 ?# m7 e4 D; K: o9 UA.
, l3 V/ q9 u) f& Q2 E语句频度         

7 J! N' ^: k5 f9 }: ?B.
/ G- d$ z8 x7 a" v! D 执行次数      
, ^7 R* a4 E! @, _
C.
7 B5 Z  ~! a! C7 @- L, W  L 基本操作           

D.
A和B
. f3 k8 i$ [8 q  t( ?0 E. i
      满分：5  分
# m  k5 H! U7 l  U3.   
利用迭代算法策略求解问题，在确定迭代模型之后的工作是
7 u; _" }' L: G8 P, C
: _) \+ E- H: J9 d; n0 _

A.   控制迭代过程      
B.   建立迭代关系式   
C.  建立关系模型   
D.  分析迭代关系
7 u& h* N2 ^  m      满分：5  分
4.   
! u7 X/ d$ G$ T& z2 e6 m6 H在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是

% J" {, ]- V. p4 d5 L3 n9 ]   
( Q( G8 ~) D; Y0 Z
/ a% G, z3 V: S% @6 I7 @! tA.   O(1)                        
. b/ M8 X8 \; sB.  O(n)
) d4 \% s: K/ D' p2 n0 v   
/ F7 U, d7 L+ a- Y6 {: w6 L
C.  O(nlogn)                 
6 A& [# R) p2 TD.   O(n2)
/ y$ |- T: _$ i3 N3 X, J& j( T% l      满分：5  分
5.   
) F* |  L6 ]! `5 T某种样式的运动服的着色由底色和装饰条纹的颜色配成。底色可选红、蓝、橙、黄，条纹色可选黑、白，则共有着色方案的个数是

   
" A. }% c8 i6 W: u- n
A. 3
/ T: ^5 r# N* v0 iB. 5
C. 8
0 w$ k' b! M  K% k; H2 m7 fD. 15
* y5 [" X' t0 h5 N7 g      满分：5  分
2 m9 b3 R' t0 v' N: D: _- w# s1 ]' {6.   
2 Y1 F: G" @5 z0 ], P0 c; c栈和队列都是

   
4 S, t2 R* E2 i% G
A.  限制存取位置的线性结构      
; v  W. `6 S. `1 ]B. 顺序存储的线性结构
   
7 `. o8 L, w  _0 N0 y8 n
C.
链式存储的线性结构        
7 l1 [  v, M6 K4 W6 \' [: y: d- v
D.
限制存取位置的非线性结构
! c8 }# Y/ g, d, `
% w, {) }; I+ v( H1 ~  n      满分：5  分
7.   
1 t4 p4 ]" w4 ^& O  B! K; H7 w# t' o 一对兔子从出生后第三个月开始，每月生一对小兔子。小兔子到第三个月又开始生下一代小兔子。假若兔子只生不死，一月份抱来一对刚出生的小兔子，则第6个月时兔子的个数为，

+ j+ j$ U) h1 [+ AA. 5
B. 8
C. 9
D. 13
, r0 D8 I3 E7 K8 A      满分：5  分
8.   
下面的叙述不正确的是
, b4 F+ k  m- X0 f5 Y  ~
5 `' d" B/ U5 S8 W/ R5 x7 v1 PA.
% ]+ o- x, L- b4 }( t线性表在链式存储时，查找第i个元素的时间同i的值成正比
3 S+ d5 t( M' U5 J+ N
- y( g% i1 u0 _  f3 \& r
. \% J: H$ O3 ]/ W" ^5 ^
B.
2 s8 v+ M, K- a: t7 H' H0 |/ U    线性表在链式存储时，查找第i个元素的时间同i的值无关

6 V3 e2 _1 {* V6 u! X3 @/ V, o' wC.
' G; K0 ?5 G/ J+ \ 线性表在顺序存储时，查找第i个元素的时间同i 的值成反比
6 F+ e8 c) V7 P
/ A( Z2 U  }7 L% WD.
6 V, @8 M: L" Q6 I  
' K0 j+ A" Y) w. ~: w9 j; a& L4 T' y
% [- B, i- i- m  l线性表在顺序存储时，查找第i个元素的时间同i的值无关

1 b7 @9 A# }5 s5 @      满分：5  分
9.   
若<vi, vj>是有向图的一条边，则称
( I' y8 W" Y& W
+ \% k7 G# Q" o/ ?# g% _; d   
5 X9 b4 I  _$ Z8 Q% l
- z: I& ]8 R6 y5 vA.  vi邻接于vj                  
B. vj邻接于vi
  
3 i3 t4 |( u( I! V
C.  vi和vj相互邻接         
% l  d, f  d* y3 H  TD.  vi与vj&shy;不相邻接
      满分：5  分
2 {7 {: v- ^% k- W' P( {10.   
算法的时间复杂度主要取决于
7 G7 Q" L  [" u& n  A
A.
问题的规模         

B.
待处理数据的初态   

C.
难度   

) i) r2 b! l3 C* x% UD.
, ]3 r6 M$ `8 b, D0 _6 V A和B
- a- G; C0 ?8 |- d6 O/ r; m: \
      满分：5  分
/ v  v! K" A* E/ i11.   
2 H0 B7 }6 V2 r9 W7 L无向图中一个顶点的度是指图中
( ^8 T9 ?0 H1 L" D" L6 V7 n
" m  ~9 N7 I& E( J+ j   
4 O2 y4 l6 e, F) d+ z
A.   通过该顶点的简单路径数        
! E! h- l9 H1 bB. 与该顶点相邻接的顶点数
7 m* M0 Y) E+ q  ZC.
, Z5 a9 m& G) F8 Q 通过该顶点的回路数         
. S/ ^. i5 q- z% H9 o9 l' m2 j# Y
" q) M$ y6 `7 k7 N8 ]( U) ^D.   与该顶点连通的顶点数
      满分：5  分
2 E* C) L; G0 E/ `9 Y# k12.   
如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是
! X& v% d3 ]$ ^! M& @- H

& U: r) x$ G; O  e( g0 B5 S) h
A.     有向完全图               
B.    连通图
( q* N$ }, q. ^/ }4 f; }   
' g. l2 f8 g* T! P
0 h% ~) B- H7 E! pC.    强连通图                    
2 I) w. [& |5 U# ~( T( B0 K) J- ~D.     有向无环图
      满分：5  分
13.   
) I) }: h/ t2 S6 g& J 对于递归算法的时间效率分析，先建立算法执行时间的
7 s4 A: l5 S- Z1 f5 V( P0 J% `. x  N& A
! _+ H$ N2 N3 C8 h! F' [A.
% G( G9 f* v6 I. I) k& W, |/ f) k; [递推方程            

7 D& f/ }/ h7 N# X; u4 F0 h5 @B.
, C. e$ E1 i2 S# B# x3 e递归方程      

C.
) Z; u2 q+ T# I      分析方程   

8 D! a/ b4 z) @3 dD.
数学方程
7 h% `; `: a7 v* S/ m) p3 y
      满分：5  分
14.   
$ @; \' c$ O" }& B: e: J9 w# C0 P# X& G对关键字序列（5，1，4，3，7，2，8，6）进行快速排序时，以第一个元素5为基准的一次划分的结果为
" ~7 G. R. d8 k, F' N- h
A.
5 m) t, Q. m, |8 j; p（1，2，3，4，5，6，7，8）      
- L+ ~$ T- o7 K6 f% @3 Y1 d) }" j
8 F1 V2 q* [& `B.
（1，4，3，2，5，7，8，6）
9 l# _+ f8 X  k  w" i' U
! C+ `9 y) M) G7 K) I4 LC.
（2，1，4，3，5，7，8，6）   
& r% V" i1 G, f- ?$ N. y9 I
D.
+ P4 n2 x0 {9 @- G) D* H9 F（8，7，6，5，4，3，2，1）

8 e0 h. T8 w/ F4 Y; |      满分：5  分
% l5 w1 S, D& K8 J8 x- t1 q15.   
在对一些问题进行分析或建立数学模型时，若从前向后分析问题感到比较棘手，则使问题容易理解和解决，可采用
( x5 k1 A3 u" E% T1 g, e
3 e1 W6 t1 x, n* j9 |9 ?8 Q" W" BA.
正推法            
( K8 o, b, ?  d: _, G
1 t; V" }4 j% K% ~  ?B.
循环法         

/ J$ q, w; Q9 v! sC.
' |/ u8 }' S. S1 S6 X+ ]: C迭代法         

D.
  V4 U8 o5 h- E' Q/ u' L1 r) F倒推法
! B# i  {; @8 s4 n1 o9 d
& c, P3 i  \# P) j  M4 c      满分：5  分

( r1 d7 {5 L6 q二、判断题（共 5 道试题，共 25 分。）V 1.  对算法的评价有两个大的方面：一是人对算法维护的方便性。二是算法运行的时间和空间效率。
A. 错误
B. 正确
; U; z. D  L7 m( a, f( a      满分：5  分
2.   
& [$ W6 a% A; n, i3 x快速排序是基于分治策略实现的排序方法，是对插入排序的一种改进算法。

2 Z( Z! l8 ]+ C8 _% QA. 错误
& S( s: T3 `2 p5 U, m3 `9 JB. 正确
      满分：5  分
3.  在一个长度为n的循环链表中，删除其元素值为x的结点的时间复杂度为O(n) 。
A. 错误
, v0 g) Z" ?) F2 c8 f  V/ k, YB. 正确
8 H3 N5 ]# _& d* ^( W8 l' n% J      满分：5  分
4.   
一个算法具有五个特性:无穷性、确定性、可行性、有零个或多个输入、有一个或多个输出。

A. 错误
B. 正确
1 h' J2 _( c$ I' @3 B      满分：5  分
9 \9 |! M2 d7 v) x5.  递归算法中递归的终止条件，也称作递归出口。
A. 错误
B. 正确
, u$ R' }4 x4 m, Q      满分：5  分
+ `4 F0 b% p6 ^  ^* l. d3 B/ H
% ]& P1 Q. u0 Q" J/ O* h