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

admin

资料来源：谋学网（www.mouxue.com）数据结构Ⅱ-[东北大学]《数据结构Ⅱ》在线平时作业1
, p1 }5 X- I8 E( ?, A" G试卷总分:100    得分:100
第1题,判定"带头结点的链队列为空"的条件是
: |* a5 W% Y( D# v& m5 CA、Q.front==NULL
/ R+ ?6 l1 y1 i/ D6 }  \4 O6 r) jB、Q.rear==NULL
C、Q.front==Q.rear
D、Q.front!=Q.rear
8 ^6 }. U. T+ ~正确资料:
) a( T  O" ?, _- v( ~
6 k/ b  D# D: \  C; {
+ X8 J! n1 v2 G* B& a0 r第2题,对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为
- _2 k. d( o% R( D# ?3 f! F' m) VA、O(n)  O(n)
* G0 B1 E4 p$ o- ?B、O(n)  O(1)
C、O(1)  O(n)
D、O(1) O(1)
$ j- ?  z+ ^0 S! I正确资料:
# K. F' W( A! E2 g  t- O- B7 K0 D

* s! b- O3 r- h* A( |5 v5 ^1 R第3题,由同一关键字集合构造的各棵二叉排序树
A、其形态不一定相同，但平均查找长度相同
B、其形态不一定相同，平均查找长度也不一定相同
+ A9 D: f% N5 W, |$ ?5 F! NC、其形态均相同，但平均查找长度不一定相同
3 K, s* a4 V$ |$ N9 ?D、其形态均相同，平均查找长度也都相同
正确资料:
6 u4 {$ F6 c; ?* l  G5 B

  b# U: J, Y$ u0 r第4题,对关键字序列(56，23，78，92，88，67，19，34)进行增量为3的一趟希尔排序的结果为
A、(19，23，56，34，78，67，88，92)
B、(23，56，78，66，88，92，19，34)
' o1 A) c  U( E; t( mC、(19，23，34，56，67，78，88，92)
7 X* L9 x0 p9 [D、(19，23，67，56，34，78，92，88)
( U1 w, r: O, q, e# M7 S正确资料:


资料来源：谋学网（www.mouxue.com）,可有效提高次关键字查找效率的文件是
( E, v  U- p% i% u7 yA、顺序文件
B、倒排文件
C、散列文件
D、VSAM文件
正确资料:
1 Y* q7 X! O. G  {! `
' {; x3 k1 x5 |7 Y$ L: b
3 A8 @0 J: M% k6 n第6题,数据结构中所定义的数据元素，是用于表示数据的
# c1 K. t9 z2 ?7 m& y5 B' ZA、最小单位
B、最大单位
+ N( q3 @  Y9 d& {C、基本单位
" ~: l5 W& j3 q% `' r0 q6 VD、不可分割的单位
, J' u$ `& h- r2 S+ d# D2 P  g正确资料:
$ g- m+ @# {% k8 Q! V

3 d/ h$ }* a* ?( d第7题,若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为
A、O(0)
) @: k# O& X. ~$ rB、O(1)
C、O(n)
D、O(n2)
正确资料:


% q2 e1 I6 \9 ]$ O第8题,若vi, vj是有向图的一条边，则称
A、vi邻接于vj
( G8 ~- A, q* b4 m2 O( GB、vj邻接于vi
C、vi和vj相互邻接
* N  P& W& v( z7 BD、vi与vj-不相邻接
正确资料:
, R! b: ~8 Y/ k( S, T2 `
& K( V( ?8 P+ V; k5 R1 z
第9题,若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t），则在二分查找关键字b的过程中，先后进行比较的关键字依次为
7 `9 ]! ]: s9 @3 ~: dA、f,c,b
B、f,d,b
C、g,c,b
D、g,d,b
正确资料:


; p3 @4 u) }. i+ c0 Q& _资料来源：谋学网（www.mouxue.com）,高度为5的完全二叉树中含有的结点数至少为
A、16
4 D3 a5 |) d' g+ sB、17
C、31
4 u+ E- a8 D4 v% ED、32
8 x6 D0 M0 f# v" q& r* W/ a正确资料:
$ m( c* H" O' R2 n! N

第11题,含n个关键字的二叉排序树的平均查找长度主要取决于
# B* n2 K& ^- C: a. Q$ s+ ~8 p1 }A、关键字的个数
1 O5 R: \- |" s/ ~% [5 nB、树的形态
C、关键字的取值范围
+ `8 n0 E. H2 r# }4 MD、关键字的数据类型
正确资料:
3 l, p( z3 h6 ?: Y1 `9 g5 e. S

+ {6 j0 ]) s) f- d  a; w0 G资料来源：谋学网（www.mouxue.com）,队列和栈的主要区别是
' {( C. }# _0 jA、逻辑结构不同
B、存储结构不同
/ n6 j* P) H7 a% k( ?+ PC、所包含的运算个数不同
D、限定插入和删除的位置不同
正确资料:

$ V: X6 I( P% Q9 O
; c4 T2 D, Q* Z+ Y* s$ e2 h6 `第13题,已知散列表的存储空间为T[0..18]，散列函数H（key）=key%17,并用二次探测法处理冲突。散列表中已插入下列关键字：T[5]=39，T[6]=57和T[7]=7，则下一个关键字23插入的位置是
A、T[2]
  l( f+ [! j! h8 f0 c3 X" YB、T[4]
C、T[8]
D、T[10]
正确资料:
; I4 H5 E* a( D2 {
) y8 `6 e$ h+ y/ g2 Z& m
第14题,根据数据元素的关键字直接计算出该元素存储地址的存储方法是
- Z# p* l6 Z& ]3 tA、顺序存储方法
9 {: I/ r, D  J1 w0 |B、链式存储方法
! U+ e  i! K+ N7 V; fC、索引存储方法
" W, {$ y, W: L' k% s( O: ]D、散列存储方法
3 v6 P4 b! W9 g9 t' ]9 a正确资料:

# p" L/ {* v7 L9 [0 ]: R
6 i2 x, K' [' g+ _6 C; I9 B% f资料来源：谋学网（www.mouxue.com）,下列关键字序列中，构成小根堆的是
6 ?( f" _' t. |4 J% eA、{84，46，62，41，28，58，15，37}
3 x% {: D$ Q( u. M8 ^3 P8 Y+ i% O+ B5 @B、{84，62，58，46，41，37，28，15}
C、{15，28，46，37，84，41，58，62}
D、{15，28，46，37，84，58，62，41}
正确资料:

" v% o; g8 r8 G% Z# [0 z3 L
3 H! U6 N' D, z0 Q! k第16题,ISAM文件和VSAM文件的区别之一是
$ V+ s- ?& e- D0 r+ [7 e  E- EA、前者是索引顺序文件，后者是索引非顺序文件
4 n' W: I! W  K# G2 C0 mB、前者只能进行顺序存取，后者只能进行随机存取
C、前者建立静态索引结构，后者建立动态索引结构
( _. I2 s! _0 Q9 n! JD、前者的存储介质是磁盘，后者的存储介质不是磁盘
; C( _, o" @: ~0 Z+ ^; X正确资料:
$ x  c  r) D" P
) X* m. D3 X  B/ [2 X
$ H: l7 f# |$ L* U: @第17题,适宜进行批量处理的文件类型是
A、顺序文件
' R) g9 x8 L% G! H; WB、索引顺序文件
C、散列文件
D、多关键字文件
正确资料:
$ w: I& N& s3 L3 l- x8 B

* c0 b- K1 u4 Q7 S' Z7 x3 K" T* }第18题,下面关于线性表的叙述中，错误的是
8 ]+ X5 C, b; L8 o7 e8 d2 \6 nA、线性表采用顺序存储，必须占用一片连续的存储单元。
B、线性表采用顺序存储，便于进行插入和删除操作。
C、线性表采用链接存储，不必占用一片连续的存储单元。
" G! p; I% P% z: Y9 P) K$ f5 Y; N& O( ZD、线性表采用链接存储，便于插入和删除操作。
1 _6 {! p2 ?  @% d正确资料:
( d% b! f$ e# e, c4 ~
& Z0 m! b$ U5 l7 {
# t: l( U% j, O: m- K第19题,某带头结点的单链表的头指针为head，判定该链表为非空的条件是
A、head==NULL
B、head-next==NULL
C、head!=NULL
; U3 [5 h1 [4 q; N' J& T- hD、head-next!=NULL
: ~8 A$ D) h! P1 I( b正确资料:
9 O" ^: N6 v: u  H! {( N9 O7 }

资料来源：谋学网（www.mouxue.com）,计算机识别、存储和加工处理的对象被统称为
A、数据
0 o) K. l: s/ z& L$ H& g0 R2 nB、数据元素
C、数据结构
; T: U" F9 L# o+ vD、数据类型
- V( O% g  S9 z# l0 J* `- T$ ~# d正确资料:






; u) p  s( e: E' T



$ W" c, _3 g6 \