东北大学16春学期《数据结构Ⅰ》在线作业3资料辅导资料

奥鹏在线作业

" X3 b6 C' Q( }+ o4 E' l% ?# s16春学期《数据结构Ⅰ》在线作业3

5 ~4 v' p( ?+ g% ^' J$ O# t
4 z3 ]  @# r$ M; j# h4 P
- d# [- g, t6 o
) B, t) _/ L" G/ E5 i$ u  r一、资料来源（谋学网www.mouxue.com）（共 20 道试题，共 100 分。）
( c" b  t# ^0 w) ?0 Z. q8 t
1.   
将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是
: h5 {/ i6 W/ M. n
) I% m6 t- R# w* ~  E# f. y+ m. 2n-1
$ E- _* N" @+ g$ \. 2n
- I# o# U7 W- a- ]8 J. n-1
0 N% P, b8 L: a# ?  t' F: e+ n正确资料：
2.   
为便于判别有向图中是否存在回路，可借助于
   
  m# l3 t) E  ?8 N' U.   广度优先搜索算法               
( S5 s+ y0 y# ~7 y  F.   最小生成树算法
     
' i7 S/ A, y) |0 a* q; H.  最短路径算法                     
.  拓扑排序算法
正确资料：
3.   
+ Y7 a) D- C7 @+ [在平衡二叉树中插入一个结点后引起了不平衡，设最低(最接近于叶子)的不平衡点是，并已知的左、右孩子的平衡因子分别为-1和0，则应进行的平衡旋转是
3 J# u- b( U, s      
.  LL型                          
8 G' V8 r4 P0 i; ]4 g" @0 c. LR型      
  V: }: z# M8 T  x     
.   RL型                        
. Y' U% w: I% N' }- |# H.  RR型
0 Q# f1 i" I: x% l1 ^) d- n4 k正确资料：
4.   
一个有向无环图的拓扑排序序列是
) g! P3 G6 Q& B& |  
. 一定唯一的                        
. 一定不唯一的
! J  e7 H6 T: i; d, J, W.
+ E4 @( `# W9 }0 ~/ e不一定唯一的                        
7 t( }! s, z; l) u- J# N. 都不对
正确资料：
5.   
6 t& K2 b5 I5 V* L  m5 I0 u 设给定权值总数有n 个，其哈夫曼树的结点总数为

  r7 l1 G8 |; d% V3 h0 V: Y- [.  不确定                        
* t$ J* ]. f/ o3 A) n.  2n         
6 M! e. Z: T% Y: C+ k: S
.  2n+1                           
4 Q0 `4 F$ a, O# ^; {# [. 2n-1
正确资料：
6.   
以下属于逻辑结构的是
.
顺序表      
1 s7 @& H% \2 ^+ x/ r7 U.  哈希表      
.  有序表         
# n( q7 w0 z) `% \1 r2 E* Z.   单链表
6 P/ e: x( O3 c' |) \  R% {正确资料：
7.   
执行下列程序段后，串X的值为
        S=〞fgh〞;   T=〞xyzw〞;
        sustr (X,S,2,strln(T));
        sustr (Y,S, stln(T),2);
        strt (X,Y);
.
! Z( E; X$ v  j  a2 l0 E  s〞fgh〞               
! p# D6 R3 i0 y; K.  〞xyzw〞
.
) L" P4 s9 X! W; B2 A6 T; v〞fxy〞               
, T; S+ x. z( v8 Y8 T9 F$ |0 D* d7 x. 〞ff〞
正确资料：
2 ^7 Q% V# T" l$ i0 K; J9 |/ ?" A: F  i8.   
& N8 z% U& W' @) Q2 l下列数据结构中，属于非线性数据结构的是
, J  h" l9 M3 C7 E1 w.
' l# W  y/ ^- w" X( e$ S  H栈            
+ Z/ z) E  u( Y7 X* M( s.   队列      
.     完全二叉树      
.  堆
正确资料：
9.   
6 v4 i/ b0 g4 o; x# O7 R; q若数组s[0..n-1]为两个栈s1和s2的共用存储空间，且仅当s[0..n-1]全满时，各栈才不能进行进栈操作， 则为这两个栈分配空间的最佳方案是：s1和s2的栈顶指针的初值分别为
1 v- H5 ]$ ~0 k   
1 i  k" Z3 b+ \3 c.   1和n+1                    
.  1和n/2
   
) j8 a% f- P) s" A# R.  －1和n                    
/ Z( p3 b2 I0 l.  －1和n+1
% {& p5 }, ?: ^2 h正确资料：
: O( t& B! J4 T. [9 [10.   
  T7 k% z/ }. s/ |) ]) u. 对长度为15的有序顺序表进行二分查找，在各记录的查找概率均相等的情况下，查找成功时所需进行的关键字比较次数的平均值为
8 R- x+ t* [; E7 Y, N, P1 w   
.  39/15                              
, X; \3 n# ~1 b9 y0 _. ?& A. u5 X.   49/15.
' \0 k2 Q) M& G- k     
. 51/15                              
.  55/15
0 k8 @% ?) X4 P/ H: P9 Q! z2 k正确资料：
11.   
/ r8 i: T/ R2 t- r3 }/ i$ ?- K 假设在构建散列表时，采用线性探测解决冲突。若连续插入的n个关键字都是同义词，则查找其中最后插入的关键字时，所需进行的比较次数为
3 y% }2 O( P3 t     
: r4 w! C# V  l, Z6 W1 J. n-1
. n
. n+1
% T4 {2 R* U& V& g# Q# J( V. n+2
( ^3 c  b5 @0 Q. A0 \# T4 @正确资料：
12.   
: M% j! I! I3 Z" n. a以下数据结构中，属于线性结构的是
( B" Z3 ~* `  }- V/ H.
广义表        
.   二叉树     
* B7 Y4 j9 y1 e. M: \: U.   稀疏矩阵         
.   串
8 ]. V/ c& S/ n2 @# r8 b; J正确资料：
13.   
; \! X+ H" d: l在一棵高度为k的满二叉树中，结点总数为
   
.   2k-1                                                
0 d5 B; G$ ^; W7 J2 B8 {! a.  2k            
        
) ]9 B: p* p- d0 T8 B) ]. 2k-1                        
' s6 Q4 e( Z/ Q) a.  log2k?+1
# G4 O7 A* J) }, j, K2 r正确资料：
3 h  ?; R1 [. Y4 {8 X4 x- u& r: U14.   
如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是
6 u& [" k7 i; k+ m6 R) p* a1 R+ E% M     
. N6 C2 m" |- D' R9 C) O.   栈                                
- H5 |) u& v2 ^  n$ a+ \/ ^.  队列
   
( S' l9 T6 y. `.    树                                 
.  图
9 |9 ~# u7 V8 z8 J7 C( I正确资料：
15.   
在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系
& b5 ~4 h% b+ S" S' W! m8 q     
.  不一定相同                     
.  都相同
) h) C8 n6 E6 S% {( [   
.   都不相同                     
.    互为逆序
正确资料：
$ {- T, ~, @& H! q16.   
倒排文件的主要优点是
   
! w( V  t- v$ ~/ @4 n" q( N" n.   便于进行插入和删除运算         
.  便于进行文件的恢复
, S5 K4 W4 m; u; w7 S1 ~  
.     便于进行多关键字查询         
- \1 q% y9 ]& D4 N. x.    节省存储空间
正确资料：
17.   
" m$ r, w5 v! |已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为
; A) A5 J; I+ f+ P6 J. o     
) T8 ], L: K& `2 F& i6 I6 ^. 0
. 1
. 48
/ v7 J7 l2 r% k. 49
' I# `" g2 R5 v  x. e$ L1 O& l  v正确资料：
, Y: m0 ?# }' h8 Z, I8 y4 M* t  T4 {18.   
含n个关键字的二叉排序树的平均查找长度主要取决于
+ c9 G: [. `1 {% r$ n! U     
# e% h3 n5 R' k  w* H9 ~8 Y.   关键字的个数               
- K+ v8 V7 w9 j' J9 i4 V2 x.   树的形态
   
.    关键字的取值范围            
, ^8 P9 L3 h+ l7 _, i7 e0 d" x.  关键字的数据类型
# D: {5 }* F; `0 v* y) ~8 c, o正确资料：
19.   
7 E. J$ M9 N- ]0 K; V8 m1 G+ X算法的时间复杂度主要取决于
.
7 T! v- a* N/ [- L3 i5 m问题的规模      
, d# @# W! {6 l0 K) W8 M  Q.  待处理数据的初态      
.
难度   
; `8 i( J; z+ Z7 H$ a/ c.  和
* Y# c/ q' {* a* R3 A5 o6 ?正确资料：
% k* G9 u& J5 c20.   
假设以数组[n]存放循环队列的元素，其头、尾指针分别为front和rr。若设定尾指针指向队列中的队尾
     元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为
( F/ j+ y& @' a5 Q7 S4 e   
! t+ B$ D5 O9 t6 k+ j# j1 x.  (rr-front-1)％n            
; a  y/ _/ b1 k9 _) Y% O6 e.    (rr-front)％n
   
# o9 g1 p% C5 P$ r.  (front-rr+1)％n              
; ]- z3 Y4 c6 d+ v.  (rr-front+n)％n
+ q  m4 s) `$ Z% [5 {* v5 w正确资料：


& A: }! T6 u7 @3 M
谋学网(www.mouxue.com)是国内最专业的奥鹏作业资料，奥鹏离线作业资料及奥鹏毕业论文辅导型网站，主要提供奥鹏中医大、大工、东财、北语、北航、川大、南开等奥鹏作业资料辅导，致力打造中国最专业的远程教育辅导社区。

ouyangchily

谋学网不错

zhihanxiaoyan

同学介绍，不错

chenzhiyong

同学介绍，不错