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

admin

【奥鹏】[四川大学]《数据结构2264》18春在线作业1
试卷总分:100    得分:100
# p+ t7 g) c$ _6 e. k9 p; W第1题,树最适合用来表示（    ）。
5 @& x! S6 i. x9 g: m7 U1 P" aA、有序数据元素
* F5 _4 D( M- g- E9 H5 \B、无序数据元素
C、元素之间具有分支层次关系的数据
D、元素之间无联系的数据
' j! n( u7 b$ e: L! c4 {& ~. V+ ^
4 u/ _7 E& i; T2 X1 u) |

第2题,下列关于数据结构的叙述中，正确的是（    ）。
A、数组是不同类型值的集合
B、递归算法的程序结构比迭代算法的程序结构更为精炼
8 H6 l5 W  O1 |7 H/ }1 w6 hC、树是一种线性结构
- r7 C- e# \+ B" q; [8 L/ g6 BD、用一维数组存储一棵完全二叉树是有效的存储方法


- x" f7 L9 j3 y' \
第3题,从一个长度为n的顺序表中删除第i个元素（    ）时，需向前移动的元素个数是（    ）。
0 \) A$ o# ^; D, s* oA、n-i
+ ?* L# f$ |5 _( K4 w  r  tB、n-i+1
- {- ^- ]  H9 |3 j' `" d" e- @& CC、n-i-1
D、i
2 j" E/ v! R3 s+ q


, \( V) ]! Z# d9 v! W6 Y第4题,若有序表为（    ），则在二分查找关键字b的过程中，先后进行比较的关键字依次为（    ）。
A、f,c,b
B、f,d,b
7 A4 r4 S# Q& o  rC、g,c,b
D、g,d,b


5 _% C0 T* A% m. I/ u+ b; k7 Q
第5题,以下数据结构中哪一个是非线性结构？（    ）
A、队列
% t; r! Z, F2 N' w1 z7 KB、栈
C、线性表
  @0 P5 e4 W  P' e$ zD、二叉树



0 ]& [! N& P" D7 @第6题,队列的特点是（    ）。
A、先进后出
. J2 T5 a# a' C9 |/ kB、先进先出
C、任意位置进出
$ R6 g4 S" f( A* r2 YD、前面都不正确



第7题,对n个记录进行堆排序，所需要的辅助存储空间为（    ）。
A、O（1og2n
B、O（n）
/ w% o, V  c2 F; o" W% vC、O（1）
D、O（n2）


3 q7 D- ^/ P3 s# x
第8题,在数据结构中，数据元素可由（    ）。
A、实体
B、域
) _( n6 `6 u* X# n* MC、数据项
3 _0 s) t5 |$ @! z! WD、字段

' {$ g; J7 Y/ a
( S3 {2 U, l. Z, H
9 O+ M: F/ `1 r0 L& r% J' V" g第9题,在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i趟排序之前，无序区中元素的个数为（    ）。
3 C& U6 k/ g/ ?% j& d0 }0 X, mA、i
+ M- u6 H. A: j  E6 SB、i+1
* A5 \4 M( m! s0 Y4 D4 g( `C、n-i
) X8 j2 q0 |& TD、n-i+1
' P& k% r5 o% p. J+ R5 h8 K9 T
, ^* Q9 \$ D. f. n9 d  z$ o
5 |5 J7 w. l$ U! r8 O
第10题,一散列表长度m为100，采用除留余数法构造散列函数，即H（    ）=K%P （    ）,，为使散列函数具有较好的性能，P的选择应是（    ）。
. u; |) Y( ?, y5 `A、99
, L8 `( F( Z8 c9 f& JB、100
C、97
D、93



, h5 G* m% z4 w' h, y; Q# N0 _* I. o第11题,设有一个二维数组A[m][n] （    ），假设A[0][0]存放位置在600，A[3][3]存放位置在678，每个元素占一个空间，则A[2][3]的存放位置是（    ）。
" C+ @9 b) G4 d# x1 {4 NA、658
; m- Z. F( a. S  F7 JB、648
( x5 ~0 S# ~$ Z  i3 EC、633
D、653
1 H% h/ s2 M, g4 n7 f* z  S$ h( c


$ W6 n9 D  i- M第12题,对一个算法的评价，不包括如下（    ）方面的内容。
A、健壮性和可读性
- \1 X, T  p8 SB、并行性
" S; @, H( h3 g5 X* ^, CC、正确性
: Z+ c" r) ?( S# X2 C9 ZD、时空复杂度

6 u. J' l4 h/ d% Y7 y3 ?  i) s
2 L4 I; P9 Z7 v. ^
第13题,若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为（    ）。
( l% B8 E* w8 fA、图中每个顶点的入度
* ]* y6 u- `6 U/ r. x; H+ S2 A; GB、图中每个顶点的出度
* w7 |2 J8 n8 t* v# oC、图中每个顶点的度
( c  ^# z0 ~1 H9 I! _D、图中连通分量的数目
5 O1 K) C4 M. y! {
2 C' M7 K8 h$ {$ I! z

6 y5 J1 L) p9 D+ l: }7 C6 k2 X$ }第14题,若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A[3]的比较序列的下标依次为（    ）。
9 ?3 B' o% t9 N9 TA、1，2，3
2 y5 {5 x( g  o! m1 \, o8 y+ SB、9，5，2，3
) Z5 [& D1 l- D- FC、9，5，3
* l7 ]; C2 k6 e: T. n" }D、9，4，2，3
/ E: |8 o+ p% O% J7 G2 w3 W) T. y
( C: s6 \# M, A2 @3 M- x1 p

, Q: B7 d  ~  s第15题,对于关键字序列（    ）进行散列存储时，若选用H（    ）=K%7作为散列函数，则散列地址为0的元素有（    ）个。
* z" G0 J! N8 y2 @" p, |A、1
$ \8 J, T0 O6 M$ |. iB、2
8 ]/ [$ A& y  t2 K1 IC、3
: q. P6 S7 {1 ^! Q: UD、4
# W, O" e$ Z  [; C2 S0 M+ N
# h8 ~3 P5 ]" _" u
  j. }5 ^  F0 L) z
* T3 k  o6 A  _9 q第16题,采用开放定址法处理散列表的冲突时，其平均查找长度（    ）。
% h# ^$ t; @) a5 {* i+ U  A) e1 \; UA、低于链接法处理冲突
$ ~3 V& K# {2 DB、高于链接法处理冲突
7 [" U/ f2 B  L8 d3 ^2 L: g+ w; ~C、与链接法处理冲突相同
  k8 f, q" q( d# q6 a& a# QD、高于二分查找
0 D8 T* x$ s  a  D. t+ Q
- ]9 o7 u" w1 d* f* D

第17题,下面关于图的存储的叙述中正确的是（    ）。
/ ]. W3 q: h. j$ AA、用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关。
, b# S9 I% `" r9 L5 m9 zB、用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关
C、用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关。
5 `* M* ]! _  s7 KD、用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关。

( u8 j  D" o4 h
7 k, {, j; h' l# H2 m# W* s2 S8 P
第18题,从二叉搜索树中查找一个元素时，其时间复杂度大致为（    ）。
, \3 V! y2 m  p, h3 |% r* g4 cA、O(n)
B、O(1)
C、O(log2n)
% J; l' W, ^$ uD、O(n2)
- c: ?7 [: }1 |! E5 a6 Y# F* j

% N: F; U. K; J! D' t) b- U
第19题,假定有K个关键字互为同义词，若用线性探测法把这K个关键字存入散列表中，至少要进行（    ）次探测。
A、K-1次
B、K次
C、K＋l次
( |! l5 ~3 `5 h. H- eD、K(K+1)/2次

0 b, H. F2 r3 g# J# t& X
1 r. t, g( ?$ m9 M3 S/ K
6 E1 g- h$ s( c) z- ]& g第20题,对于线性表（    ）进行散列存储时，若选用H（    ）=K % 9作为散列函数，则散列地址为1的元素有（    ）个。
) e) a7 B2 @7 {0 S2 _3 LA、1
, A, l8 s3 f, j6 }B、2
* O) w0 E# Q6 [+ c* EC、3
# \: }; h6 o) o- X6 x1 ZD、4


6 K( y6 a3 N& R/ ^1 Z6 T
9 h' c( v; d7 x第21题,设Huffman树的叶子结点数为m，则结点总数为（    ）。
/ T% C5 E$ C/ m* rA、2m
/ a3 t1 Z. M3 p# B0 rB、2m-1
( U, @# M% i) oC、2m+1
* m  `: w! Y% A" ?D、m+1
- F+ K7 J/ |2 q0 W% r2 p; H; ~  y& |$ _' Z
# d- ]0 Z0 L' x

第22题,一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是（    ）。
A、2 3 1
B、3 2 1
9 i/ W2 {8 y; g0 X% e1 v" e: O$ `C、3 1 2
D、1 2 3
/ ]: z+ ~6 j4 r- S5 w; N
$ t5 Q; d1 M; T8 R, ^( Z

2 L# X+ J+ e( g; \6 Q) ?8 Y/ y9 T第23题,在一个带有附加表头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行（    ）。
3 q( R! k. ^- MA、HL=p; p-next=HL;
0 K3 i" [5 W  P* iB、p-next=HL-next; HL-next=p;
' M# ]6 g9 [1 BC、p-next=HL; p=HL;
D、p-next=HL; HL=p;

! ~; L% y  t6 s; o5 v# P

8 I- c/ W( R6 n- t第24题,设有6个结点的无向图，该图至少应有（    ）条边才能确保是一个连通图。
A、5
B、6
8 c' q  h; s% w/ r$ ~, e0 NC、7
3 `3 ~: ~4 P" v1 Q) LD、8
( I0 z! L; K' J$ [% p
2 [' U+ h' a1 M" P7 _' ^* T
2 M1 p! x8 r0 A0 G" A
  D3 m7 r0 P3 J* r7 B; a第25题,带有头结点的单循环链表的头指针为head，则该链表为空的判定条件是（    ）。
$ s+ ]  G  i  MA、head= =NUL
B、head-next= =NULL
) {0 u. ~8 w# ?3 a. u6 zC、head!=NULL
D、head-next= =head

3 ?7 I, {  A5 |- @7 `: ~
3 j1 E4 H% n8 F( A) X
第26题,对一个算法的评价，主要包括如下（    ）方面的内容。
8 K& Q! a5 C8 ~A、健壮性和可读性
B、并行性
6 ~, Y" C; N( d6 N. m' u2 XC、正确性
D、时空复杂度
- Y* a& F' D- Y1 q/ q' {6 U' K1 KE、界面友好性
,C,D

. h0 M% v8 R2 ~  I+ o
5 n8 F: a7 K( g第27题,以下哪些是队列的基本运算？（    ）
A、在队列第i个元素之后插入一个元素
B、从队头删除一个元素
8 x! y0 T& m$ U/ V7 L7 qC、判断一个队列是否为空
" E" u- R9 c9 ~# W1 r) ]5 fD、读取队头元素的值
E、将队列中的元素排序
& n# G& i6 w# E) q, W' x& u,C,D

/ Q8 m) G. c) H0 {/ u( Y4 P
8 E3 q  _0 z. w; c0 V' z7 s第28题,以下序列中，是堆（    ）的有（    ）。
A、{15,26,38,49,27,51,39,62}
6 d( F$ v+ x5 Z9 XB、{15,23,71,94,72,68,26,73}
  H8 i2 B1 S' hC、{15,27,26,49,38,62,39,51}
' C- Q) o$ s+ [8 H5 ^/ f$ |+ y/ \D、{15,23,26,68,94,72,71,73}
E、{94,72,73,26,71,23,68,15}
,C,D,E
& S$ K1 Y5 Q6 E' Q8 X" L

第29题,下述（    ）是顺序存储方式的优点。
" B8 p% f1 I0 y  s# A& MA、存储密度大
  K8 x1 W3 ^. z" NB、插入和删除运算方便
C、获取符合某种条件的元素方便
D、查找运算速度快
E、可以很方便地存取第i个元素
* i  L$ ~7 I+ _, m2 s" u9 _,E

8 x( N2 ?+ O) c+ L
第30题,一个广义表（    ）,（    ）,c),（    ）))) 的表尾是（    ）,c),（    ）))。
0 y" u  Q+ W1 L0 e% j( XA、错误
B、正确
. h' H% K0 ?, c9 e1 c
/ k0 r$ K- e: g6 L8 U2 n( m
9 v* S! W, M+ s: W5 V
4 f6 P+ z4 P2 Q# W! _第31题,有回路的有向图不能完成拓扑排序。
A、错误
: X: F0 Z( c* N( VB、正确
8 I8 x4 m% M8 ?' \8 z

0 S4 `# S0 v1 y/ I  }  t
" l& e+ L. h5 l$ a; j5 h% b第32题,对任何用顶点表示活动的网络（    ）进行拓扑排序的结果都是唯一的。
, B) h: C! B9 m- KA、错误
4 {) q7 }% T# C' i8 G7 x2 Q$ HB、正确

" @5 N+ M. P% |6 t: ?
% y1 r. k9 V0 h4 T# d6 X* X* |+ Y
第33题,为度量一个搜索算法的效率，需要在时间和空间两个方面进行分析。
, s: |8 u$ P8 l1 h8 W1 }6 CA、错误
2 K6 d. W  u" R) ~1 Y4 y, h6 BB、正确

- G8 d  j) A; p) C
0 G$ l4 I+ @$ N) i& u2 D& f  s
6 V2 m3 D" `* p第34题,进行折半搜索的表必须是顺序存储的有序表。
A、错误
  O6 O6 K4 g( |B、正确

6 Q* ]& }0 [! ?! O

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

  n4 \7 T7 y% v' `( e; P& F. `& o8 i

$ t+ ~( S+ N. N+ b& P% V第36题,线性表若采用链式存储表示, 在删除时不需要移动元素。
A、错误
6 d  L" E& X6 z4 p9 Y+ l$ ZB、正确


, K: S, O% Q) w# Z: K4 @: E# E
第37题,在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻。
) ?5 T3 H  ]: NA、错误
B、正确


2 G" E1 R  k) x! \) u8 ^/ d
6 {, a6 ~; G& q. V第38题,使用三元组表示稀疏矩阵中的非零元素能节省存储空间。
A、错误
, z' K, N2 ~  c: c$ ~B、正确


  s+ C5 t1 A- m, v
0 K; {2 v7 y3 @8 A% |9 ?第39题,线性表若采用链式存储表示时，其存储结点的地址可连续也可不连续。
A、错误
B、正确
1 X& R' Y  s3 {


( ?7 o$ F. j/ Z# P/ v第40题,二维数组是数组元素为一维数组的线性表，因此二维数组元素之间是线性结构。
A、错误
3 h' Z: x: Y* q! i) SB、正确
4 o  r) J* C" X. f% }& T

* W% O5 o+ L$ U, C+ \
第41题,链式栈与顺序栈相比, 一个明显的优点是通常不会出现栈满的情况。
A、错误
6 H9 J+ t& {9 [B、正确

$ ^5 S' f7 @: h6 |4 L
1 V1 _- S, N. ~, C" |; q2 N+ [
$ B7 G" Y! ^* @* Q4 F& d4 G第42题,数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的。
A、错误
B、正确


! t2 p+ S5 ^( N, K) w4 S) P
第43题,图G的某一最小生成树的代价一定小于其他生成树的代价。
/ O3 k8 [6 _$ g" ?4 ~' S0 Z3 mA、错误
/ Y4 a! A, I0 g# j9 nB、正确


! q- P) B) L- e- L3 x/ B
第44题,在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。
+ B( v1 t& O  C. J9 JA、错误
. k. h0 f, f* p7 n! I1 |B、正确

5 k3 t. }& S5 _, F+ a6 O9 b
+ Q* [, s" F& g) S
1 R7 _8 g2 I! g* ?1 R
( ^, q8 D( P9 [, Z% C
  a9 C* ^+ r7 Z1 D6 W/ `
, t+ L9 J2 i8 r8 h# T- c
2 i: v; l! Z  S: e3 c
; F8 b" E% s1 |


, R4 k0 o% s' {2 \
* P  a, g6 Z1 s
2 w7 f; w9 Y+ Z, W

' v! T' S: x) I. V

taoxin217

学长介绍来的

wyyy9

顶顶，资料下载试试！