21年春[四川大学]《数据结构2264》在线作业2（资料）

admin

资料来源：谋学网（www.mouxue.com）-[四川大学]《数据结构2264》在线作业2
试卷总分:100    得分:100
第1题,假定有K个关键字互为同义词，若用线性探测法把这K个关键字存入散列表中，至少要进行（    ）次探测。
; @: {4 V1 g0 s- p( E0 I$ AA、K-1次
B、K次
5 C1 V7 t6 i+ r2 K: AC、K＋l次
D、K(K+1)/2次
正确资料:
! {8 X# V* ~2 S/ K( R& q9 r6 E

第2题,k层（    ）二叉树的结点总数最多为（    ）。
A、2k-1
B、2K+1
+ ^3 p! y8 h4 x: tC、2K-1
D、2k-1
) n9 l) J1 h' b1 p+ C. h* e% y1 o: y, u正确资料:,D
& Z$ U- q5 Y2 U5 z) S6 r  v
6 q8 k* K9 }0 }) z" [# m! B& Q/ e! ~
' K4 {, w/ x! l# i* \$ {! e第3题,二维数组A[8][9]按行优先顺序存储，若数组元素A[2][3]的存储地址为1087，A[4][7]的存储地址为1153，则数组元素A[6][7]的存储地址为（    ）。
A、1207
B、1209
7 L% j. o3 F* P4 q9 \/ rC、1211
( ~6 W/ E/ A, j, [+ O# B8 g8 WD、1213
9 k. V+ `& V' C" ~" H% x$ L; k  Y正确资料:
& t" k* `; d3 S. V% G
3 |( X9 O- u/ p- p7 s  X
第4题,已知一个图的顶点集V={1,2,3,4,5,6,7}；边集E={（    ）3, （    ）5, （    ）8, （    ）10, （    ）6, （    ）15, （    ）12, （    ）9, （    ）4, （    ）20, （    ）18, （    ）25}，用克鲁斯卡尔算法得到最小生成树，则在最小生成树中依次得到的各条边为（    ）。
A、(1,2)3,  (4,6)4,  (1,3)5,  (1,4)8,  (2,5)10,  (4,7)20
B、(1,2)3,  (4,6)4,  (1,3)5,  (2,3)6,  (1,4)8,  (3,6)9
C、(1,2)3,  (1,3)5,  (1,4)8,  (4,6)4,  (2,5)10,  (4,7)20
D、(1,2)3,  (1,3)5,  (1,4)8,  (2,5)10,  (4,6)4,  (4,7)20
' u5 ?7 y* x0 Z) Z! \正确资料:
, o3 }% d( T- \& ~' o" d

* P$ j( n1 ~! M8 V" d# u资料来源：谋学网（www.mouxue.com）,设有一个二维数组A[m][n] （    ），假设A[0][0]存放位置在600，A[3][3]存放位置在678，每个元素占一个空间，则A[2][3]的存放位置是（    ）。
6 V0 V: p, n' W6 [) W) c; ]# k% YA、658
B、648
* B/ L9 C' d: BC、633
D、653
正确资料:
7 w& L# h- K7 o) @7 @2 |% v- q

第6题,从L=（    ）,（    ）)中，取出banana元素的表达式为（    ）。
. }  l0 k4 ]9 ^1 SA、head(tail(L))
9 |6 r7 y2 s* ]; ]+ [4 RB、head(head(tail(L)))
C、tail(head(tail(L)))
D、head(tail(head(tail(L))))
9 F9 f; V& ?2 B& q7 J) g8 @正确资料:
! Z: G2 s; A4 l' }

; X4 h/ t5 T% `  B' M2 \第7题,采用开放定址法处理散列表的冲突时，其平均查找长度（    ）。
A、低于链接法处理冲突
B、高于链接法处理冲突
C、与链接法处理冲突相同
D、高于二分查找
正确资料:
1 Q# b* h" u$ S4 M/ \' U

% d/ t/ k  Z, Q/ Y第8题,对关键字序列（    ）进行增量为3的一趟希尔排序的结果为（    ）。
& f6 H4 D7 S, KA、(19, 23, 56, 34, 78, 67, 88, 92)
B、(23, 56, 78, 66, 88, 92, 19, 34)
8 Q/ a* K$ b3 R3 }C、(19, 23, 34, 56, 67, 78, 88, 92)
2 U3 [! F) x9 ]  O6 v( ?D、(19, 23, 67, 56, 34, 78, 92, 88)
8 r5 W1 H# L1 k! e) V- E正确资料:

3 p: \! m5 \' p0 v0 d
第9题,设有6个结点的无向图，该图至少应有（    ）条边才能确保是一个连通图。
+ ?5 F; o! S+ H- E: ]2 F  q) P& qA、5
, U1 D' s0 i3 q" A) ]' E( OB、6
! K/ `) K7 k8 R3 ?8 XC、7
! x# u& F( S( \* u4 H  B: nD、8
正确资料:

' @. ?. \! L( J& h
资料来源：谋学网（www.mouxue.com）,树最适合用来表示（    ）。
( M5 P, Q2 b* o) fA、有序数据元素
B、无序数据元素
C、元素之间具有分支层次关系的数据
D、元素之间无联系的数据
正确资料:


5 t6 U  A/ L+ v. C7 ]第11题,下列关于数据结构的叙述中，正确的是（    ）。
A、数组是不同类型值的集合
8 j: n; [$ q, BB、递归算法的程序结构比迭代算法的程序结构更为精炼
C、树是一种线性结构
D、用一维数组存储一棵完全二叉树是有效的存储方法
' j/ |! H. \* K7 g正确资料:


1 l/ s# T2 W8 R$ f* I资料来源：谋学网（www.mouxue.com）,以下数据结构中哪一个是非线性结构？（    ）
A、队列
B、栈
2 a' T( a# S) _$ t2 N* {9 M0 P1 D* OC、线性表
% k  f$ W4 u  LD、二叉树
正确资料:
- ]( N' H1 ~9 C- B5 }) h: W
: J) U1 y0 o- u5 t6 o+ h3 e
第13题,对n个记录进行堆排序，所需要的辅助存储空间为（    ）。
: [* _3 `3 e4 Z! fA、O（1og2n
B、O（n）
C、O（1）
5 d2 S8 y( ]9 K. O! c2 nD、O（n2）
* o( K5 S( @9 P3 y8 X0 h5 F. |正确资料:

4 E! T' K( E+ w0 h) s
- D  s, @+ `, \  {1 e3 g8 G) O7 T) ^& d第14题,对一棵有100个结点的完全二叉树按层编号，根结点编号为1，则编号为49的结点的父结点的编号为（    ）。
A、24
, Y% M- p9 E4 O$ K6 z0 PB、5
2 |+ y  }: D& I+ NC、98
9 P7 Z: }, G0 E0 e0 }D、99
正确资料:


1 ^6 \; F# Z; v资料来源：谋学网（www.mouxue.com）,若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算时间的存储方式是（    ）。
8 F- J, Q" D& {A、单链表
* x/ D. Y2 b8 r) }8 g5 kB、仅有头指针的单循环链表
C、双链表
D、仅有尾指针的单循环链表
( A/ K! e! S* n- p正确资料:
6 ?( ]' J5 U2 H. n/ O

6 @# U0 A! Y: Y& {* \第16题,一散列表长度m为100，采用除留余数法构造散列函数，即H（    ）=K%P （    ）,，为使散列函数具有较好的性能，P的选择应是（    ）。
! y6 ~: t% u; g5 s' x, U# kA、99
0 }  o0 q1 H* {4 b- fB、100
C、97
D、93
正确资料:
2 V8 s# Q# o, g
! x* K$ o7 }7 ^7 f% ~! J9 q
第17题,下面关于广义表的叙述中，不正确的是（    ）。
A、广义表可以是一个多层次的结构
B、广义表至少有一个元素
C、广义表可以被其他广义表所共享
3 m5 R$ t  Q/ E" l) k# Y" `3 M$ iD、广义表可以是一个递归表
正确资料:
. T( p% Y" h" w. s9 a' q

1 E$ A2 m4 z$ P) c4 A7 l6 E第18题,在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i趟排序之前，无序区中元素的个数为（    ）。
7 w3 B0 X- i: l! m, R2 A* F0 ZA、i
1 W) B2 F/ p, f/ I+ E# f- m0 mB、i+1
4 q2 y' P8 h4 E( Z5 t! U( r' IC、n-i
3 {" p6 a' f' `; R( j9 v: R, ~D、n-i+1
正确资料:
7 M4 @" |3 f' e: r
6 J4 |" v  h0 ~0 ~; V
  F& m: B3 _/ ]2 b' M/ X第19题,设Huffman树的叶子结点数为m，则结点总数为（    ）。
6 U& b7 q) @* j; z0 r% u, IA、2m
B、2m-1
' \" {9 w, c  cC、2m+1
& q- |5 k' u) D& R/ e( uD、m+1
4 K4 x  q0 @" e9 r( u正确资料:

5 S$ l% P; A' W  d& B
! H+ I8 V; I" T" S9 B$ O资料来源：谋学网（www.mouxue.com）,在一个带有附加表头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行（    ）。
% o5 R3 g- ]/ x8 mA、HL=p; p-next=HL;
B、p-next=HL-next; HL-next=p;
2 h, [# O' d+ P$ ?C、p-next=HL; p=HL;
D、p-next=HL; HL=p;
正确资料:
6 b9 o; E. g2 t5 n: J/ i4 F& d' t

第21题,在数据结构中，数据元素可由（    ）。
- S3 C8 O2 Q' t( N3 E# E- _6 `; WA、实体
B、域
/ r8 ?: y8 }4 E9 |2 }% UC、数据项
D、字段
正确资料:
2 ~( e: n5 J9 p1 h8 e( h

3 m8 P+ T* a8 E2 L0 |* f9 k: S& w2 M第22题,带有头结点的单循环链表的头指针为head，则该链表为空的判定条件是（    ）。
) L1 B& ^9 p& ~; ]* G. ~2 R$ XA、head= =NUL
' l! i+ g  F! |% J& aB、head-next= =NULL
C、head!=NULL
  A% [9 c2 g. M" G' f/ ?D、head-next= =head
正确资料:


# v' q5 l, d2 n, N% _5 f" K第23题,队列的特点是（    ）。
A、先进后出
" S& }& B2 q* E6 v! E$ K5 ?B、先进先出
4 s! C+ v" {5 {2 x5 F4 p: eC、任意位置进出
  O; B- g( N1 Q6 T0 u' UD、前面都不正确
9 N& ~% ^0 Q2 X+ E7 Y正确资料:
6 V% d5 l3 ^2 P% B% B  ^/ R. H

7 ]& E1 Q, v7 x6 F第24题,一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是（    ）。
A、2 3 1
' Y% }$ Y# L) d2 Y) @- h( xB、3 2 1
C、3 1 2
0 E3 K/ V+ }6 P, n1 g3 e7 U- kD、1 2 3
正确资料:
+ e- D. }, x! a  S  I4 L
/ Z2 j6 B  u, q  U$ b+ \+ d4 D$ a
资料来源：谋学网（www.mouxue.com）,在二叉树结点的先序序列、中序序列和后序序列中，所有叶子结点的先后顺序（    ）
7 M, G2 x' o7 Z2 s' P5 e$ g9 y& j4 `A、都不相同
3 N* [  @1 e6 `' n  v# @/ F0 a" wB、完全相同
. I: m) i6 `( e8 p8 HC、先序和中序相同，而与后序不同
& A5 R( I! J( y6 cD、中序和后序相同，而与先序不同
正确资料:
. n# d6 C# {; a- U( H6 S

9 u4 @4 W2 ?( u! \3 {9 ~第26题,以下哪些是队列的基本运算？（    ）
A、在队列第i个元素之后插入一个元素
B、从队头删除一个元素
C、判断一个队列是否为空
D、读取队头元素的值
( Z* z* L, w3 y+ uE、将队列中的元素排序
正确资料:,C,D
5 e$ `  c' h: o# S- a/ F4 s6 C/ X
* s$ _* |% V8 b* X: }& o  _' w
* L6 F9 N5 F# h1 a# x/ @& S5 B6 Y第27题,对一个算法的评价，主要包括如下（    ）方面的内容。
A、健壮性和可读性
B、并行性
& L) Q9 P, o6 l' Z0 e1 G! A/ nC、正确性
" p8 A* [" z' ~( _9 DD、时空复杂度
- {7 l' b- E& j! |+ i1 ~E、界面友好性
正确资料:,C,D

; K' ~) e: s, q' Y) Y
/ C$ F$ [  L* \5 L7 c第28题,栈和队列的共同特点是（    ）。
" M  T/ P* I2 [# z5 W, l% @9 H& J) OA、只允许在端点处插入和删除元素
B、都是先进后出
C、都是先进先出
/ B5 S! {# N: a0 kD、没有共同点
E、都可以采用顺序存储方式和链式存储方式
) U5 X* W' e' r! [5 @* x正确资料:
+ H+ a- _# G2 P) i: H' l
( }% Y4 H4 U. T( N7 i" l- g# H# _- r
$ a- ~" e0 i/ |& N9 S0 V第29题,以下序列中，是堆（    ）的有（    ）。
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}
E、{94,72,73,26,71,23,68,15}
正确资料:,C,D,E
# L% B7 X. c( h

$ x; k' a7 W! X$ @3 P4 G6 ~* E  ?" ~1 I资料来源：谋学网（www.mouxue.com）,用字符数组存储长度为n的字符串，数组长度至少为n+1。
+ D9 S6 V( b/ @, [A、错误
6 }* h0 t9 {/ p3 dB、正确
1 z" q" q4 c+ z正确资料:
' a, C$ u: S8 Y
6 t2 r; r& P/ a% \: {
& {8 Y9 A; R3 O6 _- @0 Y" u; T7 O1 p第31题,图G的某一最小生成树的代价一定小于其他生成树的代价。
/ \5 S* g0 p* k- h0 B7 ZA、错误
* {9 x; v! q+ G- y1 x" [( hB、正确
, E5 L7 {$ _1 I/ o  I8 D6 K3 t正确资料:
4 ^9 t; M! q2 K' S; W6 K1 o% O
+ v( j9 H) Z& K6 U
1 ^+ W" c9 {; U) Y6 Y2 N& `, b, Q/ p第32题,顺序表用一维数组作为存储结构，因此顺序表是一维数组。
7 }9 {& O# \; z- h; zA、错误
B、正确
正确资料:

# y  G3 q7 {5 a& J
第33题,进行折半搜索的表必须是顺序存储的有序表。
: X* B5 c" r2 a$ B9 UA、错误
" W" x" O' ^8 Q: N) r7 ~7 nB、正确
& M" W6 Z. D  w3 m正确资料:

. h) c, A' t- Z: U1 {
# _( ~: O1 Z* P2 D第34题,线性表若采用链式存储表示, 在删除时不需要移动元素。
+ }# V9 f4 Y! [! fA、错误
' ]$ E: o0 s$ R$ kB、正确
1 r, X5 q+ q, Q正确资料:


; y# U0 E6 L; C4 R% t" }第35题,链式栈与顺序栈相比, 一个明显的优点是通常不会出现栈满的情况。
: g, f1 y8 s+ u3 hA、错误
' k- h. y/ G' [' }. L+ BB、正确
正确资料:


第36题,为度量一个搜索算法的效率，需要在时间和空间两个方面进行分析。
A、错误
B、正确
正确资料:

# N; l/ N6 }# F3 p+ R% C
' e7 F# i' X" i  @6 u7 F第37题,一个广义表（    ）,（    ）,c),（    ）))) 的表尾是（    ）,c),（    ）))。
, Z0 c$ r' ?9 ?9 C2 o0 uA、错误
" p( n. x5 `& |- Q2 L2 G9 yB、正确
; |5 U, W' v6 \3 o+ m正确资料:

4 l! K9 m0 x8 D4 w" [! }
  W# N: [/ e  u8 I7 x8 @第38题,若仅知道某二叉树的中序遍历序列和后序遍历序列，则不能够确定此二叉树的层次遍历的序列。
A、错误
# m% p0 y  r, p2 BB、正确
正确资料:

, r" J7 d' t3 H# a: P2 z" w1 `" ?
第39题,有回路的有向图不能完成拓扑排序。
; u& D; [: a: e  H" kA、错误
1 K; q& _( O8 Z' l3 eB、正确
4 r% v1 Z7 u+ W正确资料:
" U; R8 }: W. h5 G) o

3 z/ t8 F# }! r' \% I第40题,邻接矩阵适用于稠密图（    ），邻接表适用于稀疏图（    ）。
! ~' c3 Z, R: B: f7 x/ y1 X8 e  mA、错误
B、正确
9 q+ {! }9 Z7 G正确资料:
( J3 L8 X: z+ |4 Q! X

第41题,一个广义表的表头总是一个广义表。
6 {" Z3 e0 }6 x# c: n3 aA、错误
0 G( x! Q0 h. @5 z6 WB、正确
正确资料:


第42题,在线性链表中删除某个结点时，只需将被删结点释放。
A、错误
$ m8 a5 n3 ^3 s# H/ pB、正确
正确资料:
6 n$ A1 u# Y" e# G# Z

: Q9 I: X& W* g' _( f第43题,在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和后序遍历，则具有相同的结果。
A、错误
B、正确
+ P- v: `- }/ T; ~* p$ i正确资料:


2 i- M6 B0 S" h( V; e0 h第44题,二维数组是数组元素为一维数组的线性表，因此二维数组元素之间是线性结构。
! J  F: B8 H; O+ x* aA、错误
' o- ?) J& q- MB、正确
3 [: p% M9 n! K$ W% k正确资料:

! H* I  \; M2 t- i: m. j

% s* u1 F' ~0 \) e


- I( @0 F; ^7 `: P( c7 x& ~
5 w" l: C9 E( [7 V4 f9 \3 k9 `& h

+ ~% ^+ R" c  o, W" _9 c' d


6 e& f$ G5 x; _. _. p. x

wodetian55

资料不全！请楼主检查