22年春东北大学《数据结构Ⅱ》在线平时作业2-1

admin

资料来源：谋学网（www.mouxue.com）数据结构Ⅱ-[东北大学]《数据结构Ⅱ》在线平时作业2
3 U# }. w/ Q5 C" o试卷总分:100    得分:100
第1题,BFS算法可用来解决单源最短路径问题的条件是当各边上的权值
3 O. p7 b7 D- h4 Z9 f, d3 j: e1 N$ LA、均相等
, I/ I/ I- ~  E$ c* g0 K, w; }B、均互不相等
C、不一定相等
: r# x, `7 L2 M: w- {7 U  [; PD、任意值
( u7 K1 f" {( a9 g正确资料:

& B3 ^, Y" c9 d+ S1 K* n
& P' G* l! x; }! w第2题,下列序列中不构成堆的是
9 B$ s$ O6 Q4 y5 d8 lA、（1，2，5，3，4，6，7，8，9，10）
( y8 U4 |) D3 _% M, ]  P, H, fB、（10，5，8，4，2，6，7，1，3）
C、（10，9，8，7，3，5，4，6，2）
D、（1，2，3，4，10，9，8，7，6，5）
正确资料:
7 N& ?, J7 K; ^1 O4 k! U, P
" K  C; w* A' P% @0 R4 K# G" ]
第3题,若要在单链表中的结点p之后插入一个结点s则应执行的语句是
A、s-next=p-next; p-next=s;
7 Y7 l. O' `* ^B、p-next=s; s-next=p-next;
% B% d+ Y" `8 t' nC、p-next=s-next; s-next=p;
/ y. L; r' j- I. \D、s-next=p; p-next=s-next;
正确资料:
4 r4 w+ _  K- u
4 h0 h+ V& t- E
第4题,若在9阶B树中插入关键字引起结点分裂则该结点在插入前含有的关键字个数为
6 ?, y2 n: s* O9 P* `" l, SA、4
& f& l/ \/ M, b  `/ rB、5
" N- {8 s0 |' D: N6 c3 u3 fC、8
D、9
9 n; u5 h4 Y! b) y! @. }正确资料:

0 V3 I: R" E4 E+ a1 n, e
资料来源：谋学网（www.mouxue.com）,假设在构建散列表时采用线性探测解决冲突若连续插入的n个关键字都是同义词则查找其中最后插入的关键字时所需进行的比较次数为
* x$ E5 [* X: U8 TA、n-1
' y' N0 G, J- Q+ A3 N+ f7 ZB、n
  Y5 \2 C+ @; _) a: d' DC、n+l
D、n+2
正确资料:
; r" l: g3 d# h2 ~: X
' T' d: l/ l& `: r
) A; h: d) l# A. H/ q% \3 L" X  U3 r, u第6题,文件中主关键字能唯一标识
A、一个记录
B、一组记录
. B0 J' [" h1 i# P- GC、一个类型
D、一个文件
正确资料:
8 C& l6 Q# o6 n2 [
2 ?- e: V* W# a
第7题,假设以数组A[m]存放循环队列的元素已知队列的长度为length指针rear指向队尾元素的下一个存储位置则队头元素所在的存储位置为
- y" `$ |( G3 f( Q" tA、(rear-length+m+1)％m
: ~$ |5 j6 u0 Z( k5 U$ LB、(rear-length+m)％m
C、(rear-length+m-1)％m
' s% p# t6 H) \% a" L9 `D、(rear-length)％m
正确资料:

5 w! Z  c$ o4 P  i, Z$ B6 I
' E% p+ T# ]9 V  U. h+ e3 ]3 y8 }8 w第8题,设顺序存储的线性表共有123个元素按分块查找的要求等分成3块若对索引表采用顺序查找来确定块并在确定的块中进行顺序查找则在查找概率相等的情况下分块查找成功时的平均查找长度为
% b6 N8 U. N" Q2 C/ ]% B9 |# eA、21
8 O% t  _! K4 c" T0 y: q0 FB、23
C、41
D、62
0 J6 o% q5 L. T* g3 E正确资料:


0 y; ?; h8 I. t第9题,数据结构中所定义的数据元素是用于表示数据的
9 t* J% R  b7 R; i: ~A、最小单位
, d9 h% A( b( AB、最大单位
8 Y1 l) h/ G& pC、基本单位
+ t1 t/ G0 W# y( qD、不可分割的单位
! _0 a- l8 k* L. ~正确资料:

: _2 S7 B6 X4 m- B: ?# u6 o: f% w
资料来源：谋学网（www.mouxue.com）,对n个关键字的序列进行快速排序平均情况下的空间复杂度为
% @/ l) n4 }+ e$ f$ n; qA、O(1)
B、O(logn)
C、O(n)
2 }9 |! k  N" PD、O(n logn)
正确资料:

4 ]( c5 G; B% @' ?/ x+ e4 N
/ O& \9 T* G5 U! L$ n+ H第11题,若允许表达式内多种括号混合嵌套则为检查表达式中括号是否正确配对的算法通常选用的辅助结构是
$ I: {* G' H8 M/ \A、栈
B、线性表
4 s; B2 A& U( c% b. g* ^C、队列
D、二叉排序树
& s& F* a. Z/ d正确资料:


资料来源：谋学网（www.mouxue.com）,下面关于数据结构正确的说法是
) ~6 t! g. Y% S9 X/ _! T! hA、一种数据类型
9 J) V1 m; x# KB、数据的存储结构
C、一组性质相同的数据元素的集合
+ O( q7 @( @9 mD、相互之间存在一种或多种特定关系的数据元素的集合
; _6 k+ a6 h( r6 O, J正确资料:
# h' N0 o! h9 B2 ~
3 \" r1 w. k  s0 ~* O
第13题,如果在数据结构中每个数据元素只可能有一个直接前驱但可以有多个直接后继则该结构是
/ r, E! g1 L: l# YA、栈
2 p/ i2 k4 C; ~B、队列
5 b+ e' {5 u( Z& e; m* j1 EC、树
+ Y: Y  ?  ^. w- K# ~+ E. xD、图
1 Y* C" |& E3 c9 v$ W2 h正确资料:


第14题,下面的说法中正确的是1任何一棵二叉树的叶子节点在三种遍历中的相对次序不变2按二叉树定义具有三个节点的二叉树共有6种
. N1 h) i4 r8 I! B. ?' @0 d, U% [# nA、(1)，(2)
B、(1)
$ G9 _7 H, N' P0 z2 J, [2 JC、(2)
D、(1)，(2)都错
正确资料:

! C* i$ I* q, \* j& T9 C+ z" C9 F
资料来源：谋学网（www.mouxue.com）,下列关键字序列中构成小根堆的是
A、{84，46，62，41，28，58，15，37}
B、{84，62，58，46，41，37，28，15}
! C5 I7 j6 m( S( b9 p1 xC、{15，28，46，37，84，41，58，62}
D、{15，28，46，37，84，58，62，41}
正确资料:
' N: M% w# x9 |3 _

/ Z# u7 R+ G4 v" p第16题,设一个栈的输入序列为12345则借助一个栈所得到的输出序列不可能是
A、23415
% P5 W* E+ H. K& a. A' vB、54132
C、23145
& S9 S. S( x& }* B) }D、15432
* O( R3 g6 E7 J0 o: P正确资料:
# d5 j" ]7 }! h6 b7 D, W+ Z4 |" O

第17题,对关键字序列51437286进行快速排序时以第一个元素5为基准的一次划分的结果为
A、（1，2，3，4，5，6，7，8）
! w! p; G' }- P( f5 CB、（1，4，3，2，5，7，8，6）
% e( e* s9 j# ]1 B5 p* v. gC、（2，1，4，3，5，7，8，6）
D、（8，7，6，5，4，3，2，1）
8 ]$ U, j3 H: X- x2 \3 h) _正确资料:
* V6 `9 |( {* |' t

第18题,在下列各种文件中不能进行顺序查找的文件是
A、顺序文件
B、索引文件
C、散列文件
D、多重表文件
" r% c+ g$ ^" k+ v5 W正确资料:
0 {1 Q& N0 C6 s0 U
; X- F0 X& o, S, ]5 R
* h$ K7 j. d! N) |. g+ _! i第19题,若将数据结构形式定义为二元组KR其中K是数据元素的有限集合则R是K上
  b2 w( O% Z, y. f. R; W# BA、操作的有限集合
B、映象的有限集合
C、类型的有限集合
& n" |3 S' o0 j6 z4 ND、关系的有限集合
正确资料:
; V$ X" }. w3 |/ {2 I
' n- }3 b3 P- v/ F% j' Y
资料来源：谋学网（www.mouxue.com）,引起循环队列队头位置发生变化的操作是
A、出队
" s; x0 }" V0 b1 `) G& pB、入队
C、取队头元素
' v& |5 Q( M" [5 N0 x" DD、取队尾元素
  y" a/ V; T6 c. x: L+ C* ~4 ]# m正确资料:

7 N, c) r8 D" i6 R: X! y/ ^$ P




( R# r3 r4 ]# D
) j9 P( T) p. A3 D
$ D* M) R& J, S! o

6 D: o% O( Y+ }3 V* i' t6 ^

  Y  A# i  O% U; x
( [- ?( q1 w9 C
" ~: Q% j) M5 d