[四川大学]《数据结构2264》20春在线作业1（答案）

skystar

【奥鹏】-[四川大学]《数据结构2264》20春在线作业1
试卷总分:100    得分:1000 ~; x1 R/ w* E6 s; E. W0 a. @
第1题,树最适合用来表示（    ）。+ C: A* u, I% Q3 O5 Z/ \. w
A、有序数据元素
B、无序数据元素
C、元素之间具有分支层次关系的数据
D、元素之间无联系的数据. `* _/ T* r7 D$ n
正确答案 w7 T* G8 C4 n8 J3 Q+ c
4 s4 }  B3 I6 P) p* }! ?- ^

第2题,下列关于数据结构的叙述中，正确的是（    ）。( @2 x# Z5 J. d- T/ a( {
A、数组是不同类型值的集合
B、递归算法的程序结构比迭代算法的程序结构更为精炼
C、树是一种线性结构
D、用一维数组存储一棵完全二叉树是有效的存储方法5 B3 H+ P7 V, g: V, o
正确答案:

! h4 e( T! l9 K! B& ?) ^4 b
第3题,从一个长度为n的顺序表中删除第i个元素（    ）时，需向前移动的元素个数是（    ）。
A、n-i# l; q. A; A% C0 U0 Y
B、n-i+1
C、n-i-1. z1 `5 a0 m' U# ^
D、i( g3 v6 {9 Z- L) K' ]7 y
正确答案:


第4题,若有序表为（    ），则在二分查找关键字b的过程中，先后进行比较的关键字依次为（    ）。  `9 u* U0 N, w. u3 i, z. p
A、f,c,b
B、f,d,b; B* E% u- y8 S9 O
C、g,c,b+ J- p" s# T5 V4 ~! g
D、g,d,b  J" V9 ~) q. o/ @4 p
正确答案:' T$ R- ]3 D3 k) M& b* b3 D
7 T) Q" p* ?7 d2 a/ s, W6 _+ I3 d

第5题,以下数据结构中哪一个是非线性结构？（    ）
A、队列. o' v% r8 q; E
B、栈
C、线性表0 D! ?) w3 B1 T  ~3 s9 ^6 P& h
D、二叉树' q9 P* C; N/ z2 _: Q, |
正确答案:! D+ H/ P7 \0 E5 x1 K
# H8 z! M2 M) x& v! b
5 M/ O  s  b! s( p6 ~+ O
第6题,队列的特点是（    ）。, h/ L- ]% [4 J# Z& L
A、先进后出! f5 O* p4 A5 k( U
B、先进先出
C、任意位置进出
D、前面都不正确
正确答案:* ]" R" u: b2 L- w( w* l
1 x! R) G: e6 h2 |) n: X. B

第7题,对n个记录进行堆排序，所需要的辅助存储空间为（    ）。0 Q$ e3 ?9 L% Q
A、O（1og2n
B、O（n）- L7 L3 a  f  e& f- w; h
C、O（1）( ]& l. W2 V# H) z
D、O（n2）% S$ l& I5 n- h% S6 f* ?
正确答案:


第8题,在数据结构中，数据元素可由（    ）。
A、实体
B、域
C、数据项. F0 h0 e& W4 w
D、字段
正确答案:, ?; J% l$ \3 a9 e$ J$ o


第9题,在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i趟排序之前，无序区中元素的个数为（    ）。% P# w0 r9 m  v
A、i% J0 w2 v8 O- K5 m8 e: v: w" T
B、i+1: }' g% s3 ?' t! Y# N- N  o6 s  B
C、n-i
D、n-i+1) M3 S, S+ F! m  N* H+ z4 O" ?! S
正确答案:


第10题,一散列表长度m为100，采用除留余数法构造散列函数，即H（    ）=K%P （    ）,，为使散列函数具有较好的性能，P的选择应是（    ）。
A、99
B、100
C、97  A9 e2 [1 R" \, V
D、93
正确答案:

9 h$ c! P) H0 J8 \2 O
第11题,设有一个二维数组A[m][n] （    ），假设A[0][0]存放位置在600，A[3][3]存放位置在678，每个元素占一个空间，则A[2][3]的存放位置是（    ）。
A、658
B、648
C、633
D、653! p: K# @( n4 n, G/ W7 W5 n/ C4 q
正确答案 ]( I% Q$ e9 Q; k8 ]9 ~5 S0 w$ |


第12题,对一个算法的评价，不包括如下（    ）方面的内容。# W1 I, E& D3 a' ~% F0 N
A、健壮性和可读性
B、并行性7 Q; c0 ~9 N* P( W* [5 n% a
C、正确性
D、时空复杂度; s% w% [7 o. j/ Z7 B; e5 L* @9 ^
正确答案:1 {$ `5 ?* H! d6 m2 y9 @6 J


第13题,若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为（    ）。
A、图中每个顶点的入度
B、图中每个顶点的出度
C、图中每个顶点的度
D、图中连通分量的数目
正确答案:
( ]% O! W0 |- N/ a& h: Z  J
! m0 X* _" {2 t+ t: N8 v# N
第14题,若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A[3]的比较序列的下标依次为（    ）。
A、1，2，3
B、9，5，2，37 a: C. a7 V+ a# j  P: U, W
C、9，5，3
D、9，4，2，3. H5 L' @% w& z2 g
正确答案:% |1 @1 e2 W# ?6 p! o4 Q3 O) {
" t4 R( u( x5 n: `$ r, t: K, O: x+ w

第15题,对于关键字序列（    ）进行散列存储时，若选用H（    ）=K%7作为散列函数，则散列地址为0的元素有（    ）个。
A、1
B、2
C、3
D、46 M5 ], Y$ G1 C: q& {: @' x
正确答案:9 i; c. F8 v0 m0 k
8 y) I+ ?( j, h/ F0 N4 y' P7 |
  [2 x! \4 E0 ]3 ^: n- P) G
第16题,采用开放定址法处理散列表的冲突时，其平均查找长度（    ）。. ~6 s; c) Z: |0 H$ z1 S
A、低于链接法处理冲突) g& R5 r7 q6 ]2 J" a: v5 P
B、高于链接法处理冲突
C、与链接法处理冲突相同
D、高于二分查找
正确答案:


第17题,下面关于图的存储的叙述中正确的是（    ）。+ T4 b$ G% Y( [& X# x& V7 E
A、用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关。5 k# g# B+ _5 w
B、用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关
C、用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关。
D、用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关。' o. ?1 [7 ~: V* Q2 }
正确答案:

7 \8 h4 h: y% t* }' p
第18题,从二叉搜索树中查找一个元素时，其时间复杂度大致为（    ）。
A、O(n)" t6 V% G4 v( s  k9 w
B、O(1)) J  S( n* ?5 y3 J5 K( m% K2 y) c5 A
C、O(log2n)
D、O(n2)' y  ?9 x' w. ~% _
正确答案:
" i1 o) Y  A) C6 e1 U! }
8 ?7 _0 ]% T- i& j( K
第19题,假定有K个关键字互为同义词，若用线性探测法把这K个关键字存入散列表中，至少要进行（    ）次探测。
A、K-1次7 [& G$ @: Z5 _& ?, V
B、K次% y8 z& `/ L$ ~4 W
C、K＋l次5 i) A( V& u+ ^1 v( @( ]
D、K(K+1)/2次& M" X. ^8 r& o3 _+ q
正确答案:
. C  y7 O4 M6 N' O3 |" {

第20题,对于线性表（    ）进行散列存储时，若选用H（    ）=K % 9作为散列函数，则散列地址为1的元素有（    ）个。
A、17 q' a1 Q" p  ]& G( K
B、2
C、3% `& o9 k0 A5 I; }/ e" Z
D、4. C. ]! ^' x( A& [& i
正确答案:
; D" k2 h. a% |+ R, B1 \
# v! b# z) ~1 l2 n0 N
第21题,设Huffman树的叶子结点数为m，则结点总数为（    ）。
A、2m' n( w2 W6 A7 F7 {$ ^- I' s
B、2m-1* ^  o9 r! n( Q+ T2 p% B
C、2m+1! ?) S* P4 O2 G5 Q
D、m+1  B! y5 ]( }  ~% h& L2 z# J5 [; ~
正确答案:% k$ j0 ^/ j# h% e6 m
  J+ R& ~5 R9 B# ?  _  h

第22题,一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是（    ）。" q. e, _5 H& W* ^' j8 R, y4 o
A、2 3 1
B、3 2 14 R* g1 }+ I% z: |/ ?: f5 `
C、3 1 2
D、1 2 3
正确答案:4 E' G6 g! @7 t8 w5 L8 p5 r

7 r3 M* V& g' R  H' a) ^1 i
第23题,在一个带有附加表头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行（    ）。
A、HL=p; p-next=HL;
B、p-next=HL-next; HL-next=p;
C、p-next=HL; p=HL;
D、p-next=HL; HL=p;6 [5 A: D. C8 s1 ?0 G
正确答案:


第24题,设有6个结点的无向图，该图至少应有（    ）条边才能确保是一个连通图。. b6 ~- y3 }+ ], G" [" i
A、5
B、6
C、7
D、8$ p3 J) p- a+ U- B
正确答案:0 d6 T* A1 @4 O% r; u8 q! l

8 o* {# \6 `7 A( J
第25题,带有头结点的单循环链表的头指针为head，则该链表为空的判定条件是（    ）。7 t( Q: s8 s3 f( M' j" v/ z
A、head= =NUL
B、head-next= =NULL1 ]* _4 l9 P) |9 t% w
C、head!=NULL
D、head-next= =head
正确答案:
5 W; R" W# S5 _: J/ Y4 m

第26题,对一个算法的评价，主要包括如下（    ）方面的内容。  T$ m& w8 c. q0 v/ Q
A、健壮性和可读性: Y- v$ X7 v$ \) t  x* L
B、并行性6 z( [! A; H  ]
C、正确性4 {  J7 g; X) w% q- L% W2 g; Z% G
D、时空复杂度* d% p; _( V& T! D' U8 V
E、界面友好性! A$ Y0 @/ c7 B1 z# ]
正确答案:,C,D


第27题,以下哪些是队列的基本运算？（    ）# Q* s/ N) t5 ]) J$ z" l
A、在队列第i个元素之后插入一个元素( V9 ?3 m6 i# b9 I
B、从队头删除一个元素
C、判断一个队列是否为空
D、读取队头元素的值
E、将队列中的元素排序
正确答案:,C,D3 j5 r; W" p$ `+ x9 q0 d+ u


第28题,以下序列中，是堆（    ）的有（    ）。+ A( `- d/ _6 H9 x* U5 Z
A、{15,26,38,49,27,51,39,62}
B、{15,23,71,94,72,68,26,73}
C、{15,27,26,49,38,62,39,51}
D、{15,23,26,68,94,72,71,73}8 v- G2 K  A. y# C$ s7 y; p
E、{94,72,73,26,71,23,68,15}. e7 I/ G! o3 i( V9 r
正确答案:,C,D,E; l& k! G  G9 z7 {0 W* ~8 T
) U" I$ \1 B: O. s- P. a  i

第29题,下述（    ）是顺序存储方式的优点。" H" z( `. j7 k; C- |% f" X; ^
A、存储密度大# S3 S' T4 A: Z
B、插入和删除运算方便
C、获取符合某种条件的元素方便
D、查找运算速度快
E、可以很方便地存取第i个元素
正确答案:,E6 R6 x' L) m! V; s- N
' `* e. Y. U. t" V

第30题,一个广义表（    ）,（    ）,c),（    ）))) 的表尾是（    ）,c),（    ）))。
A、错误8 K% F! F3 f- Q$ t. l
B、正确& s; I' r2 ~1 o7 I- f8 z# ^
正确答案:
) s8 Y0 E; b8 A8 i& K) D! i3 o
4 J) P% a# X" ^% E
第31题,有回路的有向图不能完成拓扑排序。
A、错误
B、正确5 @5 i% `* X% N$ v& c+ `  T
正确答案:! F; w; Y% S2 X4 I* p  I' X" I+ Y3 R
' L0 g5 ]1 e9 m4 E" A- S) i! A, }
# T% Z  G1 T4 F: {+ c4 n2 m
第32题,对任何用顶点表示活动的网络（    ）进行拓扑排序的结果都是唯一的。
A、错误
B、正确1 b& i( [. u' k! U3 |+ L
正确答案:2 W2 ]+ K" M. [: P- ]9 Y
1 k* \  b9 r8 a8 |7 Q9 X  _% N! M  O
. R& h9 q+ H: u% E/ @/ a3 D4 _
第33题,为度量一个搜索算法的效率，需要在时间和空间两个方面进行分析。6 u" F1 z4 c$ `5 {8 M
A、错误
B、正确2 s3 H, ~$ S* k7 T# F' t) f" X& Z
正确答案:! i3 }5 s" x% I% t/ X8 b
+ P' ^9 A+ t1 t1 T$ P
1 x: w5 H0 d! d) r8 U/ p3 E
第34题,进行折半搜索的表必须是顺序存储的有序表。6 m5 o) c8 E8 H' g! H9 w
A、错误
B、正确
正确答案:
6 [  @( R, h5 Y+ o& ~, [
* ~, l8 [) m* q
第35题,存储无向图的邻接矩阵是对称的，因此可以只存储邻接矩阵的下（    ）三角部分。4 S0 q9 Q+ [8 G9 P) \  i
A、错误3 C- B3 V' H' S( Z! g1 G
B、正确
正确答案 v' c' O- `6 d

+ }+ M1 w# _8 W6 @
第36题,线性表若采用链式存储表示, 在删除时不需要移动元素。' ~- S) b: h3 h' R8 V" w# A9 ?
A、错误
B、正确( m2 F' t' w/ c& h
正确答案:' N& z, I9 r. Z
: ~  P* Z; I$ d9 f
; o& O, E; s, O2 |
第37题,在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻。3 m: R- \; J$ |9 Z, m
A、错误/ ]$ y2 @0 m" A% k$ \* G- v( y2 x6 d
B、正确
正确答案:

; n5 i& H5 K3 q) Y
第38题,使用三元组表示稀疏矩阵中的非零元素能节省存储空间。7 a9 F1 K  N( }2 N2 F
A、错误
B、正确2 T$ d* V, e: H2 @8 ~
正确答案:- d- r+ o( u8 q8 `, ^) \! e


第39题,线性表若采用链式存储表示时，其存储结点的地址可连续也可不连续。
A、错误
B、正确
正确答案:4 \. {% V; A6 A, o
, s( U  K) o$ a) [6 |
0 d  S0 u& T% c1 H3 x
第40题,二维数组是数组元素为一维数组的线性表，因此二维数组元素之间是线性结构。7 j$ r& z6 g, t, I2 w- j
A、错误
B、正确
正确答案:: |+ u* q: l- N* }- Z: A% z
( R% t3 l- \; {* B8 a: M

第41题,链式栈与顺序栈相比, 一个明显的优点是通常不会出现栈满的情况。
A、错误
B、正确
正确答案:

9 I  P" o: I: c
第42题,数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的。
A、错误! J. @6 P0 U, Y( v" k
B、正确
正确答案:
1 ?# A( L* S! [

第43题,图G的某一最小生成树的代价一定小于其他生成树的代价。
A、错误0 D6 W" ]1 X! ^8 s! X' z/ ~  g, {
B、正确, o+ o$ @" F# a
正确答案:


第44题,在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。0 w$ \. d2 \4 \( F
A、错误- n) s2 E+ M/ e" O2 o# S8 A
B、正确