21秋东北大学《数据结构Ⅱ》在线平时作业1

admin

资料来源：谋学网（www.mouxue.com）数据结构Ⅱ-[东北大学]《数据结构Ⅱ》在线平时作业1
试卷总分:100    得分:100
5 _$ v) t; Y) ]* E第1题,判定"带头结点的链队列为空"的条件是
A、Q.front==NULL
B、Q.rear==NULL
3 B9 e1 Z0 p% E% m7 |C、Q.front==Q.rear
D、Q.front!=Q.rear
- V: D! y% @/ C正确资料:
/ V5 b' W2 i* v3 @$ Y% @

第2题,对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为
A、O(n)  O(n)
B、O(n)  O(1)
C、O(1)  O(n)
) e# M. K4 m5 |: QD、O(1) O(1)
, P6 ?) c8 E- n正确资料:


第3题,由同一关键字集合构造的各棵二叉排序树
: u# h: y# I: u* {( AA、其形态不一定相同，但平均查找长度相同
B、其形态不一定相同，平均查找长度也不一定相同
C、其形态均相同，但平均查找长度不一定相同
D、其形态均相同，平均查找长度也都相同
% W6 N/ \: f$ B+ L' C" {正确资料:

# W; }& e& T4 m2 u0 w- s+ }
; E3 M4 e) y) A: B8 ~- ]第4题,对关键字序列(56，23，78，92，88，67，19，34)进行增量为3的一趟希尔排序的结果为
9 x3 A1 Q, j: ]) L& q$ t- p. y& v" HA、(19，23，56，34，78，67，88，92)
B、(23，56，78，66，88，92，19，34)
, Y5 s8 ]% e  rC、(19，23，34，56，67，78，88，92)
D、(19，23，67，56，34，78，92，88)
2 S( v8 T. G% w" f9 S  q0 K正确资料:
2 k1 r1 e+ Z6 c7 q! D2 X( @
) H) K8 H6 s- T  K8 M+ W+ c
) `  g6 P1 y4 a1 }0 y资料来源：谋学网（www.mouxue.com）,可有效提高次关键字查找效率的文件是
A、顺序文件
B、倒排文件
! H4 T  e4 Y6 `1 T6 FC、散列文件
; |; E! C+ @2 E; E+ @0 cD、VSAM文件
1 t4 h6 e: K: p+ P. P8 b正确资料:
' z' A3 S+ ], i' L  h7 [

6 ~( B6 K1 r) G& J7 x2 x第6题,数据结构中所定义的数据元素，是用于表示数据的
* m/ m/ j: n% R" I' vA、最小单位
1 q; a, ]6 S. j# Z; j8 {9 r) FB、最大单位
& {& w, _9 a; X6 w1 cC、基本单位
* _/ H* Y/ ~' }/ `& tD、不可分割的单位
正确资料:


8 d" M7 A; z4 l第7题,若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为
A、O(0)
' T2 ^& |6 h" O7 _B、O(1)
! h7 g6 Z& k1 y* N- I$ XC、O(n)
/ ]7 ~* p' r7 h  t/ \" `2 v% y0 K6 mD、O(n2)
正确资料:


, u9 D3 d7 y9 R! e8 C第8题,若vi, vj是有向图的一条边，则称
A、vi邻接于vj
B、vj邻接于vi
C、vi和vj相互邻接
$ U# {8 X4 y. T4 M/ j  o& |D、vi与vj-不相邻接
6 J2 C  c0 F! {4 l) I1 E/ M正确资料:


# w+ Z( Q: j$ g  ~# U% `: ^" _第9题,若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t），则在二分查找关键字b的过程中，先后进行比较的关键字依次为
' ^4 X0 W, F/ e6 `A、f,c,b
! [& E) c' W4 u5 _; r: QB、f,d,b
C、g,c,b
1 n. B- K2 D; O. D& o7 vD、g,d,b
2 x4 Z- L# ~: A正确资料:

- x, i: d* C& t
资料来源：谋学网（www.mouxue.com）,高度为5的完全二叉树中含有的结点数至少为
5 J6 ?: p8 X0 F1 p; A8 L! wA、16
3 H" ]7 K: n0 r8 {B、17
) `+ o% v2 K8 ?2 PC、31
4 W/ e( }+ ^8 M2 {D、32
; r+ K& @2 C/ I正确资料:
7 y$ N. n3 Q1 w7 [5 F, I& r

* i2 X+ i4 g0 w& m第11题,含n个关键字的二叉排序树的平均查找长度主要取决于
A、关键字的个数
6 m5 Y  \! [# i5 Z2 yB、树的形态
C、关键字的取值范围
D、关键字的数据类型
4 k# s- r$ b- r0 z" B正确资料:

4 y  C- e( o2 v: U% M
) o* k' r  r8 @资料来源：谋学网（www.mouxue.com）,队列和栈的主要区别是
8 A5 [  N2 x3 }, yA、逻辑结构不同
B、存储结构不同
7 w1 C3 e1 H1 z& PC、所包含的运算个数不同
D、限定插入和删除的位置不同
4 X( q- t; y4 [" A5 N正确资料:

! c8 {& L3 }7 j  \9 q
第13题,已知散列表的存储空间为T[0..18]，散列函数H（key）=key%17,并用二次探测法处理冲突。散列表中已插入下列关键字：T[5]=39，T[6]=57和T[7]=7，则下一个关键字23插入的位置是
A、T[2]
* @* I2 |' n! xB、T[4]
5 |2 k% p; v+ k. {" W8 LC、T[8]
D、T[10]
# _2 l! T  x2 A+ I4 N) _正确资料:
% f' ~( v  ]& I$ S. ^

第14题,根据数据元素的关键字直接计算出该元素存储地址的存储方法是
4 n6 G+ K3 {1 kA、顺序存储方法
+ p( D) p5 l0 N% i6 o5 i* aB、链式存储方法
; c) `3 \5 J9 i6 G2 RC、索引存储方法
# \6 Y* u9 T' k/ dD、散列存储方法
7 R  ~* n  C- a# T, M( Y正确资料:
) q0 w. }% P( i  Z1 L
4 \- D/ D8 g: |+ |% m
资料来源：谋学网（www.mouxue.com）,下列关键字序列中，构成小根堆的是
7 h# R, a7 v5 z! c* }. J" Z( ?A、{84，46，62，41，28，58，15，37}
- @9 M! I$ U, I- Q* x% {' WB、{84，62，58，46，41，37，28，15}
C、{15，28，46，37，84，41，58，62}
% L# B) i/ x5 ~; a+ }& Y3 BD、{15，28，46，37，84，58，62，41}
正确资料:


4 [$ _, |) H. U2 H第16题,ISAM文件和VSAM文件的区别之一是
. U2 f6 I( z9 [, V1 U( K1 y' qA、前者是索引顺序文件，后者是索引非顺序文件
6 y- K" U& D' @: YB、前者只能进行顺序存取，后者只能进行随机存取
C、前者建立静态索引结构，后者建立动态索引结构
3 p6 ~& o1 E. A; Y% p* GD、前者的存储介质是磁盘，后者的存储介质不是磁盘
% }' u8 _. O4 R6 v) x4 Q* I. a正确资料:
+ s% ~2 X: |1 U$ e

第17题,适宜进行批量处理的文件类型是
A、顺序文件
B、索引顺序文件
C、散列文件
- z# m7 f& f* K; qD、多关键字文件
正确资料:
4 R! u( L: H3 q7 H- ?1 F# ^
. u, w0 v9 g8 G" C; M- H5 P
第18题,下面关于线性表的叙述中，错误的是
/ d: y) |" T4 n! Z* [# CA、线性表采用顺序存储，必须占用一片连续的存储单元。
. g+ }. e. N+ m& E* \4 ~B、线性表采用顺序存储，便于进行插入和删除操作。
C、线性表采用链接存储，不必占用一片连续的存储单元。
D、线性表采用链接存储，便于插入和删除操作。
1 G; c1 F' j  G正确资料:

  I3 a+ w1 t4 S5 u. W* @6 \
第19题,某带头结点的单链表的头指针为head，判定该链表为非空的条件是
A、head==NULL
5 ~% D# D1 D9 i0 SB、head-next==NULL
, K& I' g  E$ ?( rC、head!=NULL
0 Y3 z7 ^5 s. i! MD、head-next!=NULL
3 ?$ O$ a) f5 ?1 S" j: k正确资料:
7 E2 h, D, {% K: q9 S0 r, M

资料来源：谋学网（www.mouxue.com）,计算机识别、存储和加工处理的对象被统称为
A、数据
B、数据元素
, V; |3 Q" r& }1 k4 TC、数据结构
1 U/ m7 o/ Z  u: S6 nD、数据类型
正确资料:
& L+ s& ~+ [% a6 M' b: Z1 k$ N* \* c

( d& g9 [: W2 {+ D6 q


3 Q& F3 c* g# L3 D" J9 E8 A5 }

: A- l& [' }: v8 P. d4 C
) z5 s' Q' W  o) t& D: s  G

2 R; F6 K8 S- D! w4 [' A

3 c8 y/ q5 }; ]

% |; `" Q; }( g5 R' j8 i