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

谋学网

15秋学期《数据结构Ⅰ》在线作业3
      
单选题

- \+ L! ?" y7 \
9 N' _, [; K( k6 a$ y( s' [# \一、单选题（共 20 道试题，共 100 分。）
1.   
' S6 K8 D7 L9 @' g' @) Z; w采用ISM或VSM组织的文件是
9 }" k! c' f# B" }, Z   
  }4 }' B* ~3 \# j( A4 k, K/ \  e3 r: A.   索引非顺序文件                 
5 m) H3 a' P) R5 w5 l% h1 y' _.   顺序文件
& H- \, x. e  ]( A* w6 n6 z6 F& m     
.  索引顺序文件                    
& z6 _" i" I0 r& N. R7 Z.  散列文件
-----------------选择：      
2.   
. 对长度为15的有序顺序表进行二分查找，在各记录的查找概率均相等的情况下，查找成功时所需进行的关键字比较次数的平均值为
   
.  39/15                              
.   49/15.
0 B2 u# N& i+ S     
/ i, d0 m( l& [$ S5 T/ b. 51/15                              
.  55/15
& }6 \9 r5 f7 }( |( p-----------------选择：      
3.   
假设一棵完全二叉树按层次遍历的顺序依次存放在数组T[m]中，其中根结点存放在T[0]，若T中的结点有左孩子，则左孩子存放在
      
, U/ _/ M9 w7 p8 j! F, L/ q- F- L.  T[i/2]                     
7 J. l  m- _* ^6 @3 g/ Y.    T[2*i-1]
     
.   T[2*i]                       
.   T[2*i+1]
7 Y* k' U8 \2 z6 m- W/ Y3 D-----------------选择：      
1 B% J" ^5 D& K$ s/ i9 T& Q  |4.   
) I5 A/ P! \5 q/ ^) Dfor（i=0；i<m；i++）
$ \+ N. ?5 q0 n; @" K  Y+ k; O        for（j=0；j<t；j++）
- N8 t( N3 L/ L2 y* n) Y［i］［j］=0；
for（i=0；i<m；i++）
for（j=0；j<t；j++）
  p  {# q) p9 O1 Z! D7 h/ l1 P0 ]for（k=0；k<n；k++）
［i］［j］=［i］［j］+［i］［k］*［k］［j］；
    上列程序的时间复杂度为
, v* v% s! ~( s7 ?' f4 N  
.    O（m+n×t）                    
.   O（m+n+t）
   
.   O（m×n×t）                  
( P# q, o; t& e.   O（m×t+n）
1 H9 D7 B* ?. ~8 U# Q-----------------选择：      
5.   
, j! O7 B1 k5 P' o( KFS算法可用来解决单源最短路径问题的条件是当各边上的权值
.
均相等                             
" o# o$ O+ {9 y$ W4 H.  均互不相等     
.
不一定相等                          
. 任意值
-----------------选择：      
9 k2 r) S; C9 ~8 X6 T. G7 u6.   
高度为5的完全二叉树中含有的结点数至少为
      
. 16
' O; Z- h. K2 E% P! m. 17
. 31
6 d& E8 l5 H! ^% @7 F. 32
. D/ k9 d  x+ M% ^$ ?" N( x/ Z-----------------选择：      
7.   
. m2 G8 f( C2 S5 u0 `8 H+ F' h下列序列中，不构成堆的是
.
（1，2，5，3，4，6，7，8，9，10）
.
" F. r3 y* Q# Q' u% q6 j（10，5，8，4，2，6，7，1，3）
.
; O4 u" ~& T7 A* N（10，9，8，7，3，5，4，6，2）
.
9 f( _3 A! |) s1 Q（1，2，3，4，10，9，8，7，6，5）
: D: j4 G6 g3 Z$ E/ w: E: q-----------------选择：      
8.   
9 @4 u, g) ^  V4 {多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为
.
' m6 R3 |$ d1 M- r9 x数组的元素处在行和列两个关系中   
9 K: e4 R7 X. H4 l5 Y* z5 z% b+ ?$ e+ c5 B( P. 数组的元素必须从左到右顺序排列
.
数组的元素之间存在次序关系      
7 A* s% r5 B( F4 g# s* @) h.  数组是多维结构，内存是一维结构
- ^! @* R8 q- M-----------------选择：      
9.   
用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为
, c  o, b" i# C9 k. E     
  c2 ~$ K& B& g2 w) N. n-1
8 F2 Z0 X3 `; l) P+ g8 q. n
. n+1
. 2n
6 g9 O( _! |3 K+ [) j* {-----------------选择：谋学网www.mouxue.com      
10.   
在线性表的下列运算中，不改变数据元素之间结构关系的运算是
  
" I' d, V2 m' s8 y8 V- p7 Q.   插入                        
. 删除
   
6 M1 z" q  A$ d0 H. 排序                        
0 s* c& W; B" C% p! ?2 |5 n.  查找
-----------------选择：      
11.   
% k" j0 J: V0 a" Z4 p导致栈上溢的操作是
& Y/ q' D7 v# G5 T.
栈满时执行的出栈                  
.   栈满时执行的入栈
9 H8 q; J; q; _/ k  X& T6 |.
栈空时执行的出栈                  
- ^. K2 e# w- _.   栈空时执行的入栈
-----------------选择：      
3 Z/ v6 ]* Z. k7 x/ ~$ ?" b' [9 q; {12.   
) |6 s" p, w% V! r8 @8 D判断两个串大小的基本准则是
.
两个串长度的大小              
.   两个串中首字符的大小
.
两个串中大写字母的多少        
.   对应的第一个不等字符的大小
/ F( ~$ a8 h6 Q- }-----------------选择：      
13.   
可有效提高次关键字查找效率的文件是
   
.  顺序文件                        
.   倒排文件
     
.  散列文件                        
.  VSM文件
8 D1 }6 N. t3 U& r: D-----------------选择：      
& V6 w4 w- W& m14.   
4 h  D( o8 a7 y" R  [- F& b& h  T若<vi, vj>是有向图的一条边，则称
   
% n$ ~, ^/ y6 i; |, n& ^% T.  vi邻接于vj                  
/ t6 O, _: p- l+ s$ r8 B.  vj邻接于vi
   
.  vi和vj相互邻接               
. vi与vj?不相邻接
) y2 a. h5 E$ n8 s+ T8 x  r# J: u-----------------选择： 谋学网www.mouxue.com     
. X% S3 g2 O( O8 q15.   
/ m  ~! Z& z; c6 A; b+ q% x2 ~某二叉树中序序列为,,,,E,F,G，后序序列为,,,,F,G,E 则该二叉树对应的森林包括的树的棵树是
   
. 1
! m3 Y* o6 M# {7 F  B/ J& ?' g. 2
. 3
. 概念上是错误的
-----------------选择：      
16.   
在一个单链表中，已知q结点是p结点的前驱结点，若在q 和p之间插入结点s，则执行操作
6 ~# O4 N6 e/ b- F, }  k     
.   s->next=p->next;p->next=s;
5 X3 u: Z% O  ~5 }.     s->next=p; q->next=s
1 F# Q/ J1 Q8 G( N* F: j     
.   q->next=s;s->next=p;          . p->next=s;s->next=q;
$ d1 j& [& U- D' J. \8 I.   q->next=s;s->next=p;          . p->next=s;s->next=q;
0 U( E$ D( j- S9 n- k4 I5 N-----------------选择：      
17.   
下面说法错误的是
    (1）算法原地工作的含义是指不需要任何额外的辅助空间
' D- N* I, u, T" I   （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法
9 }, z2 L: i( r6 J  L1 A1 I   （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界
   （4）同一个算法，实现语言的级别越高，执行效率就越低
.
(1)                 
.   (1),(2)   
.
(1),(4)                 
6 h! A+ w$ A$ D6 r. K0 r+ J.  (3)
! j: [0 T! U" Q: e) d0 ?-----------------选择：      
/ i9 B, Z( w% `18.   
n个顶点的有向完全图中含有向边的数目最多为
1 o* L) W  C$ N' ?4 r2 e.
2 N8 f/ A) L- fn-1                                
.     n           
# t; L: C  e( p.
6 s0 o. K" w: {1 D/ [, \( w. Z* R" Rn(n-1)/2                              
.  n(n-1)
-----------------选择： 谋学网www.mouxue.com     
19.   
$ A  D- }- P( B0 i$ K; ?$ ~$ r, m对有18个元素的有序表作二分查找，则查找[3]的比较序列的下标为
) ^( T2 k# n& v% K0 |   
2 |2 ], p, P1 Q5 O: A6 `.  1，2，3                        
.   9，5，2，3   

. 9，5，3                        
.   9，4，2，3
-----------------选择：      
6 I* F2 ~2 ]0 g8 {5 d4 ^" y7 p20.   
若用一个大小为6的数组来实现循环队列，且当前rer和front的值分别为0和3，当从队列中删除一个元素，
& f! K; O8 O2 {3 ?8 x! u    再加入两个元素后，rer和front的值分别为

+ J) ^* {7 |5 l7 ^.  1和 5                              
.  2和4         
.
; b. `, C7 _. T; i  {  4和2                              
8 T, A" f. G8 c+ ~0 ].   5和1  
+ F% C! ^# g9 U. ?) L, `- R-----------------选择：      
- A. L: W& q$ ^0 x: N' L

alvinyang

OK，资料不错