奥鹏作业答案-谋学网-专业的奥鹏在线作业答案辅导网【官网】

 找回密码
 会员注册

微信登录,扫一扫

手机号码,快捷登录

VIP会员,3年作业免费下 !奥鹏作业,奥鹏毕业论文检测新手作业下载教程,充值问题没有找到答案,请在此处留言!
2022年5月最新全国统考资料投诉建议,加盟合作!点击这里给我发消息 点击这里给我发消息
奥鹏课程积分软件(2021年最新)
查看: 1264|回复: 0

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

[复制链接]
发表于 2012-12-19 13:54:38 | 显示全部楼层 |阅读模式
谋学网
一、单选(共 15 道试题,共 75 分。)V 1.    / U' ~$ M# \- @* h
用DFS遍历一个无环有向图,并在DFS算法退栈返回时打印相应的顶点,则输出的顶点序列是! a: \$ n% e0 {5 ]# v4 m4 F

* }6 x% n3 ^. s6 _0 b/ IA.
1 _/ D" O. v/ B( `4 v3 Y5 u 逆拓扑有序                        `* A1 x1 F! ^* e

7 C7 g% C0 `1 [% n  Y1 PB.
, J0 h4 `" P8 g+ M: U  j 拓扑有序           ' [7 M- y5 O( c
8 U# S, Z6 I1 D: _0 _, y3 q
C.
* j, A: c$ g3 K$ `; J 无序的            - Y- i5 G: I4 }+ h
; u* ]9 B/ A' D7 h6 N% r2 k
D. 8 b) x% V% c9 X9 @: Q) u& C
A和B
# F1 x  |7 s$ E: [! b5 y+ w, [# P: L9 i! Q" V+ x
      满分:5  分
% E8 p& ?3 w+ t2.   
6 V8 k9 c5 l2 Y无向图中一个顶点的度是指图中) P, s# ^0 \$ r+ J. O* E% `  |4 e

0 T7 C+ E$ q4 F" n' O; `- s% R   ' `# o' C5 n. T' y" B: V6 J$ R
. Z6 Q0 v1 N, e0 I- l, R8 E4 q
A.   通过该顶点的简单路径数        - c$ g0 J2 f( R  ?! x. f
B. 与该顶点相邻接的顶点数
) l9 {+ n3 p5 ?" v% HC. 4 s$ B5 T2 x8 ?8 v* }
通过该顶点的回路数         
/ e4 m+ p# B( o% X) z4 p4 |+ j/ A* c5 _/ L4 z
D.   与该顶点连通的顶点数
1 ~0 f" _( D, b# k2 k      满分:5  分
$ S$ I% M+ X# Q9 [6 i3.   
1 L  ?- v' V2 O3 k1 q: t若长度为n的线性表采用顺序存储结构,在其第i个位置插入一个新元素的算法的时间复杂度为% n. ~( ~* G  Z3 M2 ~$ N

* r5 `4 X, s# |; ]; q5 A     ' A- V0 ~# T- w- J

7 G+ N. a0 p6 M6 ^A.  O(0)                     
- v8 ?: P# L( i: y! P! RB. O(1)         
6 F, q, `& o8 ]' G   
  Y. ]/ S9 A' R$ ]# R. m/ D
9 \7 m* }* _3 ^% t% tC. 6 y( Y( _8 ?! @" D( H
O(n)         
: f! S+ i- L$ i5 D/ b- f: u( Z& i5 c4 Y$ g2 j* U
D.
% W$ F4 s& [* a0 R2 {9 f7 y) F4 `O(n2)
+ {4 K! A8 b: i& k+ c- }" q+ n8 e5 j% `  t0 j7 G
      满分:5  分. q% D& `( X, G& Q0 w( Q* w
4.    ( ]8 X9 k1 b2 d0 Z
用有向无环图描述表达式(A+B)*((A+B)/A),至少需要顶点的数目为
0 n2 K' {, g1 q0 t  P- h/ y7 T
% O% W: b# L9 O2 @% J% X. jA. 5
, R6 H: X' B# f: yB. 6
7 j+ I3 |' J* e, YC. 85 q! N. q. Q7 b1 c, E1 ]
D. 95 \3 u# h* g, L+ W* e) k6 d
      满分:5  分! ]" [0 b9 |; m  R# W
5.    " r+ _  n. Y* Q. ]
而解递归方程的最直接方法,就是采用  Z% Z# h% [$ F& M. C; @
0 W- o4 @% M7 |8 P) J
A.
; ]7 d' m# P9 N3 f: l8 U$ B9 Z递推法               
  a( R6 r# D- R+ W+ T% L
1 n+ w# J- q7 y0 \' C% pB.
. d2 _% Q5 w7 J/ h穷举法              
, T( N6 I) N; T; `& ^- T9 z1 ]' R/ n" s! P  e
C.
6 s% y: f7 Q* ~2 s, p2 w搜索法      # e2 T3 V; ^: e5 x3 W4 U7 Y+ i

! {& y. Q% t( `1 U9 qD.
7 T' {' Q& h4 D4 `贪心法/ o& w* a. y# q5 m! F7 B1 Q

: o) n0 S+ l8 q      满分:5  分6 O: }: v) K0 G  h: H4 I" ~
6.    ' I' |; @5 C& `; v, o# R. u: Y
图论问题主要是研究数据结构是图形结构或树形结构的# o# B7 l/ k  n/ z3 X' r/ w

+ k& r0 C* e8 u8 t! T& d3 |# m1 tA. 5 i+ d4 d4 w5 i% h; U0 g- E
结构      
8 Y; A& C- ^# ^! ~# v( _
  A5 U: `+ T  m5 x+ Q$ \' [B.
2 d- o" D6 }+ v8 h: Q( a定义         
5 F4 |8 T& ]8 B+ n9 C
- d9 N1 e$ e% ]- @C.
& z5 z6 O7 D, v3 W. g算法      p8 a/ v7 e0 l4 N
5 k* m6 o8 u* A
D. 8 m+ r/ W! L+ k( _  I4 q% N
数据元素9 v7 |0 i2 r2 m3 }# z, `$ V& k  a3 {: h

! e; j, u! O( b0 b4 ]7 I      满分:5  分6 q' L% `/ W3 w" |7 w9 I
7.    8 _% T  O6 s  L8 w9 K  a
若一个有向图的邻接距阵中,主对角线以下的元素均为零,则该图的拓扑有序序列 * u: u) {, i# e& k! o' a' t' b

: D: ^' G& r! h8 T# @& q& UA.
& B1 s3 ]. [& A' n; l 一定存在                          
; J+ [6 f* {9 W6 Q+ [: Q, e0 k8 p% F! {/ H( K: s* z
B.
9 a' q$ F6 R; t4 i( u, o$ s4 ^, a 一定不存在
3 l0 h1 q' n% N1 k4 E8 A! c9 }
$ x; `, C: e8 Z8 f' J' UC.
: T9 R8 G* n" k5 u) W! z) ]不一定存在                  
4 v  P; n/ K1 q  M! D' j* H8 d/ |8 D$ G) c$ {- d4 x
D. 0 C0 |4 `8 s0 {  H9 k
不确定
% G6 Z8 A& n9 H3 L  C" w7 X- k& n4 x7 X3 |1 h) z
      满分:5  分
( F5 D2 n" c/ _8 v8.    9 e# Q' a4 a* g- |
若进栈序列为1,2,3,4,5,6,且进栈和出栈可以穿插进行,则不可能出现的出栈序列是6 ~9 h5 x3 s! x1 M! L) z2 r
$ d$ N( y+ Q$ ~, f2 ]
A. : F: u7 B' A* m6 v2 f
2,4,3,1,5,6                 
6 O& H6 e$ D8 R9 b" r: m0 \7 L; m
B.
$ \; |* e9 R: a7 }' |; e; C3,2,4,1,6,5# a- B/ b4 Y+ z

  Q/ Q  q7 Y7 K; gC.
5 u8 ~; e* y) v& f9 p+ o+ a+ p% n4,3,2,1,5,6         , E! L8 J1 s+ H( h2 C( V: h

9 Y6 W# _& L+ q! [  ]% wD. 6 n2 U6 u# {7 [7 L- v5 Z1 J
2,3,5,1,6,4
' v! k; L: t+ e7 J2 j! l  H5 q; q" V8 e  T0 i
      满分:5  分: q) U# V* g! H& j
9.    ) H# I# ]! k: a% O% a
多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为# w% W) O* S5 _, l
; k' x; h+ ]8 H# w; D
A.
7 |0 H6 \3 r2 ~  [数组的元素处在行和列两个关系中   
7 W. F  S- O0 ]! J2 E# ^: r  ~7 _2 P! R' d! M3 b
B. $ c  x# e  m9 d& C' t/ i
数组的元素必须从左到右顺序排列
1 p5 e& M  V8 D6 F5 _. S/ N8 r* Y& `7 ^& Z  ?+ l
C.
% J4 f* K! e1 H  w8 j6 l$ N# S数组的元素之间存在次序关系    $ Z3 W) g6 }6 Q9 x8 H
/ g5 R+ n1 c# g5 {
D. / G- y. A5 J( q1 X7 n1 l, S
数组是多维结构,内存是一维结构! R8 x4 ~+ H* p+ m+ \/ q* n2 t1 @

/ k2 H' u1 u( }+ F      满分:5  分% H- ^* }, P/ H  A
10.    ) k0 }1 D( M9 X) [
若用一个大小为6的数组来实现循环队列,且当前rear和front的值分别为0和3,当从队列中删除一个元素,5 Q# P/ l& F: K$ o$ ], _  W" ~1 }
  X' V" j! a, `" l' b
    再加入两个元素后,rear和front的值分别为 * K6 k0 v2 p9 h4 R

2 k' |2 a: i; p& g1 \& V8 k2 a7 IA.
6 N' C7 V, {  |( C  1和 5                             
; F; c- C: V& d7 j- V0 v
2 w: i! H9 ]5 W8 v" J# E8 H3 XB. 0 |) o+ D& x/ r2 L/ S6 J
2和4         
' w3 a6 V% x( U
* c+ M$ _" F" G8 ZC.
# `1 u5 t3 q& A) O# E 4和2                  
! O  `) O+ r1 u9 ?6 ?
% u3 y+ u" z- [D. ; G7 m' P6 N3 R6 M" }$ f
5和1  
0 j5 Q( r$ l' _# L- b- {
9 S' f4 f  v9 J  G2 T0 x      满分:5  分
1 ?# w1 V5 x: [; j# f. L9 E11.   
) K. A+ G# {; P, r, |9 }已知在一棵度为3的树中,度为2的结点数为4,度为3的结点数为3,则该树中的叶子结点数为+ C. G, ^  A! I

5 q) a- I) ~1 k! O* v- r: D) `     3 _6 ^& O$ v  j3 W! B0 o- z3 ~: l! I
1 Z  [0 w! u  j& j$ P! h* M' ?
A. 5( i/ h  E* p& C4 f1 @0 K- Z' l
B. 8+ G  m- D/ M( B3 e5 K
C. 117 O# C, I/ f6 A* _$ {* Q3 F
D. 18
2 E& e2 ?# g  `3 c      满分:5  分, q, s( [3 o, Z1 I
12.    + ?7 E7 l( x: t+ q1 i! X: m
设有一个顺序栈,6个元素1、2 、3、4、5、6依次入栈,如果6个元素出栈的顺序是2、3、4、6、5、1,则栈的容量至少应该是1 \9 p$ Z: V  l- a- m  }* O! V
5 w9 |3 F4 N( V& e- m
     
, ~8 k% T9 v$ d4 m1 j. l8 k( z) ^5 F% u1 B8 \* F8 V
A. 2
+ Z1 e3 J' @: F  b) r7 v" VB. 3- L! w) v7 m/ n; {
C. 5
% V( v, x8 P" ^; f" z4 n7 dD. 6
; M3 L4 A* k' q: j) `5 s6 [. j3 u      满分:5  分% n$ k+ U1 F7 H4 }; M2 {
13.    ! B1 _2 X: I7 B. h; O
已知含10个结点的二叉排序树是一棵完全二叉树,则该二叉排序树在等概率情况下查找成功的平均查找长度等于( {6 u$ T; n" e* T. P0 I
6 h3 E& H* c4 z* s8 P
   
0 H2 h5 m5 W2 e9 x% z! k4 `5 ^2 x( m0 {8 I5 b
A.  1.0                             7 L- {0 h1 f! f9 m! ~% w, |
B.  2.9
" _9 `' y1 u# G/ N9 t   
; C# f1 n4 c0 g2 H7 H+ b2 L2 S
C.
4 W6 ^# N& [8 Z3.4                       
# G! H' H6 F" Z, A/ f
0 l! a. G" J3 u( g% [# k7 D; ^D.
# B9 H* `+ V2 I' o- d5.5
: e0 C8 V8 h; i! A9 R) ^$ i5 K7 c3 Z. f) M: U. `# ?
      满分:5  分" ?) U( c+ I7 r. q3 Q4 V3 _
14.    * S& }2 F* ]8 Y; R  S
利用迭代算法策略求解问题,在确定迭代模型之后的工作是
# |8 ~4 s/ R; b6 R
) R" T) I- m3 w8 K" {2 W9 L$ n9 f) y
! E- V% y5 b  N1 Y0 ?
6 {0 F8 V7 I; h) i' h) H9 a3 dA.   控制迭代过程      
8 g, {  f+ v/ j4 DB.   建立迭代关系式    ! b+ k* Z7 i1 J5 Y8 g+ e
C.  建立关系模型   . S- r% H% n* c: e+ _7 E  A
D.  分析迭代关系1 T9 u- Z7 [: I+ B1 n( ]6 e
      满分:5  分
, r! _0 y5 Q) r2 j15.   
1 e) N! H0 z7 E& b2 F, F5 e排序算法的选择取决于问题的处理环境和本身的. K, P! v6 s- L

. _! X3 b% D8 v( xA.
3 @2 n" s, K; I: b. P0 s$ Q规模         
8 U, ]' y8 C! ?/ I0 Z- _$ Z: t% t
$ d9 m2 S" S: I, g5 KB. " E( D: ]: ?( H/ \7 G# f- m6 t0 K$ a
特点      
9 E, q8 @; h3 v: y5 `( {7 X& c$ }" t$ P5 \5 n; d
C. 5 d$ X5 K' l7 T/ h- }8 v
结构       # a# E7 p* U; [/ N

/ D1 Z; L; t! x; w& y4 R# uD.
' ^& M$ c( Y$ H! A9 b+ k. ?# n) `作用
1 ~  U& \& Q- \" |+ _
0 }( X* ~3 ^+ t      满分:5  分
/ d& h- e. B; c6 [: @8 ^5 ]( |* J/ m2 b9 D% {
二、判断题(共 5 道试题,共 25 分。)V 1.    * J* z0 r: E3 E! F) O" ]8 c
Hanoi问题的递归算法的时间复杂度为O(n)。算法的空间度杂度为O((n))。2 X: E2 J5 ]9 S

7 }3 D% Z% ~9 Y+ V6 OA. 错误
2 Y+ j' v: h$ ]8 k% a5 v, ~! z- ?B. 正确& L( W+ o5 M; n1 |5 X' {
      满分:5  分
6 C, K8 C& s9 W0 {8 ~, X2.  克鲁斯卡尔算法的时间复杂度为  O(eloge), 它对稀疏图较为适合。
. `6 \* k( w- r" zA. 错误" S" o- y( m# I3 O5 y
B. 正确) Z4 ~0 |3 f. h
      满分:5  分3 `, m2 O+ k  o( Q' g" X: }0 ]& b
3.  记忆化限界搜索算法在求解时,还是按着自顶向下的顺序,但是每求解一个状态,就将它的解保存下来。9 q  U3 m- S& x: q
A. 错误
1 k. P: b$ _  |5 e6 {8 T8 lB. 正确
4 Q% u) ^, {  x      满分:5  分
: E8 R. B; k2 Q7 [4.  索引文件中的索引表指示记录的关键字与物理记录之间一一对应的关系。- g2 Z+ B' ^  c# N- i
A. 错误
9 Y/ A* q) L* {. l! IB. 正确
7 f- z  V9 y4 ]. r+ r. r      满分:5  分1 {$ }+ K. H% d- k  b" V
5.  可以在多项式时间内解决的判定性问题属于NP类问题。
9 g  O; F7 ]9 q# l6 [A. 错误
2 P) U8 K  i& x5 bB. 正确
  [& s) ?; l1 S0 ~( P3 S& o0 l$ ~      满分:5  分
0 `  g1 e( X# z/ R' B
% {  B) A8 Z! O

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有账号?会员注册

×
奥鹏作业答案,奥鹏在线作业答案
您需要登录后才可以回帖 登录 | 会员注册

本版积分规则

 
 
客服一
客服二
客服三
客服四
点这里给我发消息
点这里给我发消息
谋学网奥鹏同学群2
微信客服扫一扫

QQ|关于我们|联系方式|网站特点|加入VIP|加盟合作|投诉建议|法律申明|Archiver|小黑屋|奥鹏作业答案-谋学网 ( 湘ICP备2021015247号 )

GMT+8, 2024-3-29 05:48 , Processed in 0.119992 second(s), 24 queries .

Powered by Discuz! X3.5

Copyright © 2001-2023 Tencent Cloud.

快速回复 返回顶部 返回列表