东北大学13春学期《数据结构Ⅱ》在线作业1-3

谋学网

  
9 a/ f) s9 \$ W& v$ N6 p9 A13春学期《数据结构Ⅱ》在线作业1
      
. ^) H" r% |0 D: e! L' i单选题

# N$ Q% b% g- _* P
一、单选题（共 20 道试题，共 100 分。）
+ b$ t( |  M' r6 a5 S1 q" t" H, ?1.   
, Y& y8 Z4 i; I在分块索引的在顺序表中查找，算法中采用的最佳技术是
A.
穷举法                       
B.
贪心法   
8 M' z& d# l- Z/ K7 BC.
分治法                     
D.
分支限界法
-----------------选择：A      
& i( t2 Y% O* n" \, R2.   
/ L% n& c  H  E; `8 ~9 d若要在单链表中的结点p之后插入一个结点s，则应执行的语句是
4 v" _6 X& m+ [2 B/ g      
A. s->next=p->next; p->next=s;      
$ e- h7 Y  B. _0 a- UB. p->next=s; s->next=p->next;
; d4 C& }! t3 t: K, K% q2 G      
/ E5 v# a8 m# r3 j, ^C.
p->next=s->next; s->next=p;     
D.
* h# M- ^5 ?) X5 V+ j: q* ss->next=p; p->next=s->next;
-----------------选择：A      
3.   
- S+ D8 }9 O+ h# e下面说法错误的是
    (1）算法原地工作的含义是指不需要任何额外的辅助空间
5 a! P. h- ~/ }5 `* `7 R5 b   （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法
   （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界
8 l. i+ ]. s# |, R( Q+ j; G5 e$ d   （4）同一个算法，实现语言的级别越高，执行效率就越低
; ?$ R: q# I+ l. r! dA.
2 c3 e* n$ q! s6 X" J+ o4 n, h( D (1)     
; O$ k9 y# h, `B.
! M" }) I6 M# R0 N& e( ~3 h (1),(2)   
C.
(1),(4)         
D.
(3)
-----------------选择：C      
5 I9 J. V, a2 Y& u4.   
某带头结点的单链表的头指针为head，判定该链表为非空的条件是
: c# N* ]( o% q: l) Z9 H   
* g1 h' y/ R8 rA.   head==NULL                     
7 O# m2 X. e. sB.   head->next==NULL
   
C.
6 m$ a% n9 U# N0 bhead!=NULL                     
, h3 P. p$ p- c2 Q$ p) M. C: [D.  head->next!=NULL
. Q7 e% H( J* T' d% W, p-----------------选择：B      
5.   
在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i趟排序之前，无序区中关键字元素的个数为
A.
8 A2 q: O* G9 t" Bi                              
B.
i+1
9 {- s% j4 C" d8 F. ?$ {- ^% UC.
n-i                           
1 M) ?6 O9 \7 X( g( C& R5 MD.
5 {0 ]: g7 i7 U. ]6 Dn-i+1
-----------------选择：D      
6.   
已知一组关键字为{25,48,36,72,79,82,23,40,16,35}，其中每相邻两个为有序子序列。对这些子序列进行一趟两两归并的结果是
A.
9 L1 j" @; _$ x+ T! J( Z.{25,36,48,72,23,40,79,82,16,35}
B.
.{25,36,48,72,16,23,40,79,82,35}
0 p5 z3 x# e2 _6 xC.
( g5 v2 e! Z! ^$ a$ b" {+ j8 i.{25,36,48,72,16,23,35,40,79,82}
D.
) }- V' h. O. r7 }$ P7 v.{16,23,25,35,36,40,48,72,79,82}
-----------------选择：D      
5 {3 Q4 Y7 _; v3 v& f" y4 p7.   
0 ]7 H  F! ^" S& j( P在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为
! f: ~8 a$ r+ P9 _8 X   
: I" q- J9 H& ~6 R: DA.   n-i+1                     
2 M7 A6 a, ]  a0 k8 MB.   i
2 t$ o8 U6 r6 i* M7 L   
/ A+ r) s, e- b+ p1 _- H8 I; n7 VC.  i+1                        
D.  n-i
5 J; X* E! c: I7 @  h7 d-----------------选择：D      
8.   
数据元素及其关系在计算机存储器内的表示，称为数据的
0 I6 U. p5 h, J  b   
0 z! u  u* h2 R9 GA. 逻辑结构               
' t- ~$ d( e% S2 t, x8 x8 |) |B. 存储结构
   
C.
* l! q  v7 ~# ?线性结构                  
D.
5 u9 U+ }8 Q% k3 p% h# Z非线性结构
$ A5 u2 x; G0 p+ n) Y-----------------选择：B      
; n+ a; S  k% Q. M$ L/ m6 F& p9.   
假设以数组A[m]存放循环队列的元素。已知队列的长度为length，指针rear指向队尾元素的下一个存储位置，则队头元素所在的存储位置为
6 x0 ?3 N  Z; z) H# Z6 s( U     
4 k! ]  q/ V# a5 `, PA. (rear-length+m+1)％m            
B. (rear-length+m)％m
   
C.
(rear-length+m-1)％m              
+ i; k6 M; l. c! u/ f) wD.
(rear-length)％m
-----------------选择：B      
, T, [. S+ T& s: u8 j4 F6 N% {9 J10.   
在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为
A.
  O(n)                              
3 I. r/ ?/ ]* iB.
  O(n+e)      
* g$ ~' ^: g; d7 h3 ?3 F( SC.
3 b. n& _/ D& b; l$ M' x O(n2)                          
D.
O(n3)
-----------------选择：B      
11.   
在按层次遍历二叉树的算法中，需要借助的辅助数据结构是
' a7 ^( M& G5 N/ H6 C0 e% _1 p   
A.  队列                       
0 q! N+ A; \/ ~+ T  q: [B.  栈
   
C.  线性表                     
D.  
8 w" j/ z/ x0 n' Z   有序表
-----------------选择：      
12.   
) l& y; W- @( y% u三维数组A[4][5][6]按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素的存 储地址为120，则元素A［３］[4][5]的存储地址为
     
A. 356
B. 358
C. 360
+ ?! ~9 k/ G1 r! Q5 Y- VD. 362
-----------------选择：      
0 Z7 J, W. w7 S4 U  Z* @13.   
能进行二分查找的线性表,必须以
     
A. 顺序方式存储,且元素按关键字有序
   
4 ]: [* w+ A0 `! O9 a4 T* Y: e+ X! \' ~B.
2 t2 \8 ^! s2 m- z' _链式方式存储,且元素按关键字有序
   
, ]% y% z/ C; F6 YC.
: L. V0 G3 E  |% Q% I  L* v' Z顺序方式存储,且元素按关键字分块有序
3 J# }+ u6 G" {0 ^9 `/ H- ]- j, E   
D.
. H! C2 I7 k* h) W2 S链式方式存储,且元素按关键字分块有序
- B' X; Z1 _- ]# T/ k2 O9 J& s-----------------选择：     
14.   
* V' Q, E' X2 o: P- p+ W对关键字序列(56，23，78，92，88，67，19，34)进行增量为3的一趟希尔排序的结果为
A.
(19，23，56，34，78，67，88，92)        
B.
3 C  b! C# F4 i1 F; t (23，56，78，66，88，92，19，34)
9 K1 m' v+ S9 n0 m0 }; Q# IC.
(19，23，34，56，67，78，88，92)      
D.
: U9 H; ]* [2 ^9 M, Y' c (19，23，67，56，34，78，92，88)
+ N/ p2 B, k; ]: Y5 x-----------------选择：     
15.   
- B/ d2 {/ m0 [% |用有向无环图描述表达式(A+B)*((A+B)/A)，至少需要顶点的数目为
A. 5
B. 6
+ h9 o# R" |) W, W6 z  M4 L8 PC. 8
6 m4 w9 t0 b+ U- u8 B/ pD. 9
-----------------选择：      
! }- R! N8 r: x16.   
+ _2 R' c: n, f下列编码中属于前缀编码的是
2 o: \# _+ M# f* {; I   
A.  {1,01,000,001}               
B.   {1,01,011,010}
     
! K$ n( f# j* B/ ~C.
{0,10,110,11}                 
7 G- q+ g( q- s& @: \2 g0 q- {% pD.   {0,1,00,11}
' E& F5 V& u! [. ^0 J( x! `-----------------选择：     
17.   
下述哪一条是顺序存储结构的优点
A.
1 ^' p5 \, |- g: d  P/ S1 A. ?存储密度大                  
B.
: W7 D8 ?7 F) H: G/ Q5 j: J( k插入运算方便  
C.
删除运算方便               
D.
+ Q  d2 [# b$ I' @: k可方便地用于各种逻辑结构的存储表示
. M$ Q' i2 j) n/ L2 a: n5 Z) u-----------------选择：      
18.   
8 M, }& B; |) r) R- \( G下面的叙述不正确的是
   
A.
线性表在链式存储时，查找第i个元素的时间同i的值成正比
' e' [* X* B$ Q; k' k$ V  m% OB.  线性表在链式存储时，查找第i个元素的时间同i的值无关
. v* s* E- e% o; uC.  线性表在顺序存储时，查找第i个元素的时间同i 的值成反比
D.   线性表在顺序存储时，查找第i个元素的时间同i的值无关
-----------------选择：      
19.   
( W: |  x3 A$ ]5 _; m若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的
     
A.  层次遍历算法                     
- P* n, g8 X: _( c: P5 _" hB.  前序遍历算法
) |+ r0 k1 l9 i% e! L     
) r1 Z- o* M0 R  b/ d) ZC.
中序遍历算法                     
D.  后序遍历算法
-----------------选择：      
5 Q5 j; y6 t& e2 [. Z: z9 R20.   
, r% Z, `( ^8 x  w1 Y) d# w在平衡二叉树中插入一个结点后引起了不平衡，设最低(最接近于叶子)的不平衡点是A，并已知A的左、右孩子的平衡因子分别为-1和0，则应进行的平衡旋转是
3 n) \8 \* N& N1 n( P6 c      
$ p; u8 v5 f5 L( J2 Y# hA.  LL型                       
B. LR型      
: ~! [" J! f9 r9 y0 S" L      
C.
RL型                        
D.  RR型
- }3 y" X( y: W0 Y& a, e2 K-----------------选择：      
7 w7 }9 w# C0 `1 o3 s, i: }
6 N5 D% L+ R4 k; h- c