[四川大学]《数据结构2264》18春在线作业1（参考资料）

admin

【奥鹏】[四川大学]《数据结构2264》18春在线作业1
试卷总分:100    得分:100
& F# t4 t7 S% F& f" f第1题,树最适合用来表示（    ）。
2 L/ U( X6 v; @! b2 ~5 r8 DA、有序数据元素
B、无序数据元素
C、元素之间具有分支层次关系的数据
D、元素之间无联系的数据

9 e; K1 p  @0 ?% K( z: s# [) u2 L

8 f7 m' \0 D  s) k+ H: w! |第2题,下列关于数据结构的叙述中，正确的是（    ）。
0 s; |; V/ K7 `. OA、数组是不同类型值的集合
7 s2 p5 ]* Y$ z0 mB、递归算法的程序结构比迭代算法的程序结构更为精炼
2 n" u0 `5 {1 K0 L+ [* _& s. K% u, \C、树是一种线性结构
D、用一维数组存储一棵完全二叉树是有效的存储方法



5 K4 ~1 }# D% L9 b( |# `第3题,从一个长度为n的顺序表中删除第i个元素（    ）时，需向前移动的元素个数是（    ）。
8 g) F; e* L+ i, E8 F" y' L$ _A、n-i
B、n-i+1
C、n-i-1
D、i
& D: Q5 D* m  q( }7 D/ ]
6 s% i) O; d5 {4 c; V1 f& `. @8 k

1 N7 ^+ m3 e$ k6 F, {/ f第4题,若有序表为（    ），则在二分查找关键字b的过程中，先后进行比较的关键字依次为（    ）。
3 v0 t; p' t/ T" Z* c$ r! IA、f,c,b
( {* y* Q% J* f# r9 e; y2 _/ ~9 ?B、f,d,b
3 q8 M+ i1 @4 n/ @C、g,c,b
# k3 W3 ^7 `- e3 GD、g,d,b
, ]% H) n8 [. z
0 P# t( |+ [; g6 f2 ^) w& I
, [1 J, a/ R, r( N4 N+ f4 c# R
: G, A  U9 z7 ]2 M+ I第5题,以下数据结构中哪一个是非线性结构？（    ）
A、队列
! B( @. I- c  ?7 JB、栈
C、线性表
D、二叉树
2 @' s# h, e  ], y1 ~8 l- W- C2 c

0 N% d, H: w) c
第6题,队列的特点是（    ）。
5 _7 t8 Q8 a, d7 PA、先进后出
B、先进先出
- e- K7 q! ?2 i- O# AC、任意位置进出
9 N2 ]; Z$ r" }$ YD、前面都不正确
6 e0 h2 N% j9 p0 o& e: x% S4 [

- y: V* ?# A/ k; h) w: Z6 g
' G+ Y  ]# x4 U$ k第7题,对n个记录进行堆排序，所需要的辅助存储空间为（    ）。
A、O（1og2n
B、O（n）
C、O（1）
1 S5 [) p; M* U* |5 x1 V, @5 RD、O（n2）
! S/ J3 s5 s# C2 C4 d/ Q. I
, D- x: A. {" D: {4 n
' p9 }8 A9 C* b9 s& e& K$ ?
第8题,在数据结构中，数据元素可由（    ）。
/ }8 q' X5 f3 }  |6 y$ ~6 q) fA、实体
B、域
( R1 ?6 Y: N6 C! J" b; j5 fC、数据项
D、字段

! \4 X$ e$ A" i* g9 j) p
0 X7 J6 k) r: q8 k; H: ~
9 o1 G2 m5 Z9 U. P7 U  @% \第9题,在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i趟排序之前，无序区中元素的个数为（    ）。
, ^$ ~- l+ ?6 R+ y& iA、i
, N  G  d1 N% p0 |9 k( X: u1 LB、i+1
C、n-i
D、n-i+1



第10题,一散列表长度m为100，采用除留余数法构造散列函数，即H（    ）=K%P （    ）,，为使散列函数具有较好的性能，P的选择应是（    ）。
: `# d/ b9 a- _  N  J0 u; u* f+ WA、99
, y7 Z9 `2 u/ e9 gB、100
C、97
8 ]8 |1 }7 {: a% w2 \  A" aD、93
2 n0 f: j! A+ a; J; O8 D9 ?' q1 M

: z2 D' V% j$ r3 c2 b4 h: Y. N' a
* w- F$ x3 n. q( g6 I第11题,设有一个二维数组A[m][n] （    ），假设A[0][0]存放位置在600，A[3][3]存放位置在678，每个元素占一个空间，则A[2][3]的存放位置是（    ）。
3 w2 _: S% H. {A、658
! H5 w8 i3 ]6 _( k" uB、648
C、633
D、653



第12题,对一个算法的评价，不包括如下（    ）方面的内容。
A、健壮性和可读性
" Q" I* i! x3 b/ u& b) s  e6 C2 B6 [B、并行性
! k% }$ p- R- ?" |+ U0 B0 qC、正确性
D、时空复杂度



6 L3 f" C' ~. s' C. `3 @第13题,若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为（    ）。
) U9 T% }# ]1 K( c* xA、图中每个顶点的入度
( c: n5 b$ t( A* ]B、图中每个顶点的出度
C、图中每个顶点的度
D、图中连通分量的数目

  O- Z! Q# A1 E, w( P; `2 W

) C0 K# s# M. |  i/ I第14题,若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A[3]的比较序列的下标依次为（    ）。
5 }0 O8 D$ t1 V7 \$ I9 QA、1，2，3
B、9，5，2，3
C、9，5，3
' |2 u; ]3 h# u$ zD、9，4，2，3
8 C8 p9 {4 l6 U) t

4 r; ?5 z! x) P) w+ v5 F
) o% c: |: \. {& l第15题,对于关键字序列（    ）进行散列存储时，若选用H（    ）=K%7作为散列函数，则散列地址为0的元素有（    ）个。
6 h: f# L7 b$ JA、1
B、2
- r0 P8 |8 r4 R/ A+ ^: aC、3
D、4
8 C& V( {5 t% T1 x2 B

, |3 O' d3 _* ^& R+ x0 g" Q
2 h( Z1 h. _3 B5 a( F. L  O第16题,采用开放定址法处理散列表的冲突时，其平均查找长度（    ）。
A、低于链接法处理冲突
6 Q. g% p2 {  y; Z  aB、高于链接法处理冲突
* A1 s  {2 @- c1 O$ P/ c2 J& o( TC、与链接法处理冲突相同
D、高于二分查找
# T" c! h1 l) s4 `, q& t6 ?
1 Z- v, F* z! H! `& V* N* D

2 w* D2 i3 l4 y# ^第17题,下面关于图的存储的叙述中正确的是（    ）。
6 ^8 B. l1 Z  u+ ?A、用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关。
+ r7 ?* N5 M4 Z  DB、用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关
& H3 f3 c8 a+ ]6 `, F5 ZC、用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关。
D、用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关。

- x7 B. W- l7 Z# c; W6 T- U
  x1 C; m1 |* o8 F' Z/ A7 i) P
' F5 ]' n! ?, R8 j6 e第18题,从二叉搜索树中查找一个元素时，其时间复杂度大致为（    ）。
A、O(n)
" {' }- r/ f- m6 T: HB、O(1)
C、O(log2n)
D、O(n2)

! z% c! F4 x# J( x7 p

第19题,假定有K个关键字互为同义词，若用线性探测法把这K个关键字存入散列表中，至少要进行（    ）次探测。
: T6 W2 T. d+ H7 TA、K-1次
3 I: b' c9 T: A2 SB、K次
C、K＋l次
; @8 ^4 C7 Y. \D、K(K+1)/2次



% N9 ~1 p% k% M( U* W第20题,对于线性表（    ）进行散列存储时，若选用H（    ）=K % 9作为散列函数，则散列地址为1的元素有（    ）个。
A、1
B、2
5 k# P' `8 m1 l' ?+ dC、3
D、4

( c: ]6 y# K6 |5 A6 W+ k6 L: }# B
3 p, `/ _! `4 Y" Y, c! t( I* \
第21题,设Huffman树的叶子结点数为m，则结点总数为（    ）。
A、2m
6 M/ U# R. h6 I) u! a- ^B、2m-1
: n% }4 u1 y4 h6 t( L; l: r( qC、2m+1
D、m+1
, J& w( y, I( z. f, P# M1 S+ H
7 n2 L8 J) Q% I6 A( e$ \) u! [2 U$ T1 I

第22题,一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是（    ）。
A、2 3 1
% s& [, M* w! z- K0 M' TB、3 2 1
C、3 1 2
D、1 2 3
/ S% r- b" U; R' S! \" \# j9 @  j

- r/ N; U1 |0 S3 f8 n1 F2 P7 C6 x
第23题,在一个带有附加表头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行（    ）。
A、HL=p; p-next=HL;
) B4 v, v9 M" W( v$ Y9 lB、p-next=HL-next; HL-next=p;
$ o$ [& @; g( D+ E7 a. |" T; MC、p-next=HL; p=HL;
D、p-next=HL; HL=p;



第24题,设有6个结点的无向图，该图至少应有（    ）条边才能确保是一个连通图。
A、5
B、6
8 \8 A3 H! z4 N4 o0 d/ J- HC、7
D、8



第25题,带有头结点的单循环链表的头指针为head，则该链表为空的判定条件是（    ）。
A、head= =NUL
B、head-next= =NULL
" V! q1 L* e* u- k. j" eC、head!=NULL
D、head-next= =head



第26题,对一个算法的评价，主要包括如下（    ）方面的内容。
$ r( i- t* }  ^1 M; XA、健壮性和可读性
B、并行性
2 f8 y) z6 h$ f: T) L, ?2 qC、正确性
D、时空复杂度
E、界面友好性
,C,D
) J" g# W; M" o( j( K) A+ W0 Y& o
9 e8 G$ |1 |4 d% K8 B+ q: j
第27题,以下哪些是队列的基本运算？（    ）
2 `$ V  N6 x# q: Y; l' xA、在队列第i个元素之后插入一个元素
% @% z8 J' r1 C0 e4 o+ cB、从队头删除一个元素
  M+ L5 d; \5 c' a! R% FC、判断一个队列是否为空
D、读取队头元素的值
E、将队列中的元素排序
,C,D

( N* f9 e9 ?( e9 y" ?7 y% C
1 V4 H2 o  \0 w+ K" y  f* E7 z% P" @第28题,以下序列中，是堆（    ）的有（    ）。
4 W; J* E6 w7 f/ Q& GA、{15,26,38,49,27,51,39,62}
& ^1 J3 A% s# G3 m) RB、{15,23,71,94,72,68,26,73}
6 M& y$ D: o8 J2 q+ |C、{15,27,26,49,38,62,39,51}
D、{15,23,26,68,94,72,71,73}
E、{94,72,73,26,71,23,68,15}
,C,D,E

9 Y5 m" b# c6 ~( P7 a9 @
' k& I7 U; D& r/ a# {第29题,下述（    ）是顺序存储方式的优点。
; K: N+ r5 x* y. K9 u* Z0 Z) dA、存储密度大
B、插入和删除运算方便
C、获取符合某种条件的元素方便
D、查找运算速度快
E、可以很方便地存取第i个元素
,E

" D% W% G) K: m6 J9 m  p* A, a
第30题,一个广义表（    ）,（    ）,c),（    ）))) 的表尾是（    ）,c),（    ）))。
- q* D8 a* ]+ _) T" Y/ aA、错误
* Z4 X2 t; |4 z% I. W6 CB、正确

; p3 o' B5 P- b& W
9 A7 G0 K: \$ N! L1 E
第31题,有回路的有向图不能完成拓扑排序。
; r! _! D9 q6 y, o) EA、错误
2 x1 Q/ m! ?) y: V& WB、正确
) Q) R# W  h8 b, L& E/ G
/ l5 c3 Q0 K$ s. l- n7 J

第32题,对任何用顶点表示活动的网络（    ）进行拓扑排序的结果都是唯一的。
A、错误
0 r. G' R# y5 NB、正确
9 I4 Z8 a2 F5 E* W

* H# V7 A* a% A5 d- e. H# J" V
第33题,为度量一个搜索算法的效率，需要在时间和空间两个方面进行分析。
# Y# l2 ?- @4 A, i5 F4 N% yA、错误
( V$ X! v: C/ R( b' I( y( NB、正确

, O6 l# Z' B9 M, J( ?) @
. z6 a' x% R# o. e8 r; b. w  N/ q& k
( X- f& W7 B1 V- H1 X, A第34题,进行折半搜索的表必须是顺序存储的有序表。
A、错误
. G1 k" R& _& U" d+ v6 oB、正确
6 j( A. \" V3 F
  |: `; u( t* ?% c' E

第35题,存储无向图的邻接矩阵是对称的，因此可以只存储邻接矩阵的下（    ）三角部分。
A、错误
B、正确


  k8 W( x& `) |8 J1 k! @
第36题,线性表若采用链式存储表示, 在删除时不需要移动元素。
8 _7 p) y/ G) h. qA、错误
B、正确
2 R5 P7 b. Y& M  K, H2 t
$ H% V5 t6 i" a( C# |! k, w

% N- \& d, O& K$ R: d) e第37题,在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻。
A、错误
B、正确
+ h/ u& L- V6 Z5 d0 e6 D$ J$ y5 I' u
( [' \# h( f; g# p; S( N0 W+ D/ `

$ A0 H4 A8 n! A3 m, b! d6 V第38题,使用三元组表示稀疏矩阵中的非零元素能节省存储空间。
! J# Y9 {" T, E$ sA、错误
- _' N& z0 Y3 r; T" X7 o' E) BB、正确
- c6 N/ T- O' V2 c


6 d0 d' P7 A2 c7 A第39题,线性表若采用链式存储表示时，其存储结点的地址可连续也可不连续。
A、错误
( z2 b2 p$ l/ K  N  a6 u6 sB、正确



+ a& X( g2 O4 N第40题,二维数组是数组元素为一维数组的线性表，因此二维数组元素之间是线性结构。
A、错误
B、正确



第41题,链式栈与顺序栈相比, 一个明显的优点是通常不会出现栈满的情况。
A、错误
B、正确
1 x% q: m/ j4 e( l% k& A& y" O

# E+ F, C' h! R% @4 f5 g# x6 m
0 a- l- W7 x  J- u$ v) p9 y$ O第42题,数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的。
. f9 C' M& G# X; `; c* xA、错误
B、正确

# y, t  v4 ~; W% a3 @2 }
% f& j( f- b* F! c2 w2 e7 n
; Z* }: x3 m& Y% `5 B第43题,图G的某一最小生成树的代价一定小于其他生成树的代价。
A、错误
B、正确


: y% x2 }% ^1 D9 h9 S
1 v) V! }/ _, u, P第44题,在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。
A、错误
5 t8 ~7 q( h1 oB、正确


: \7 r. i3 l2 H' q3 I% s/ T) }
1 L, a' K; z7 Z  c& n
3 W2 d: R: o" Y  d7 q

4 ~) D0 _; E$ a# ^' I1 ^! d0 K

# f! _/ n( s2 K5 @/ p/ d7 e

2 G5 a5 r2 \* \
! Q+ U) ]/ ~( T$ T% P! w


# n' w  z) O4 B% N" @1 F
! A; T6 x, y4 C7 H$ I# m; \

taoxin217

学长介绍来的

wyyy9

顶顶，资料下载试试！