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

admin

亲，您好，如果下载后没有资料，请联系客服QQ 18586448 或者微信客服：mouxuewang223,或者微信扫码加好友，给您带来的不便，请谅解，祝学习愉快！
; W" n5 M0 u& g3 f  _0 g
【奥鹏】-[四川大学]《数据结构2264》20春在线作业1
试卷总分:100    得分:100
第1题,树最适合用来表示（    ）。
' E" M6 A6 D7 E9 }) LA、有序数据元素
B、无序数据元素
C、元素之间具有分支层次关系的数据
D、元素之间无联系的数据
正确资料:
4 [3 {; u9 s9 H" i

第2题,下列关于数据结构的叙述中，正确的是（    ）。
A、数组是不同类型值的集合
B、递归算法的程序结构比迭代算法的程序结构更为精炼
' z( c  v2 D( N- uC、树是一种线性结构
D、用一维数组存储一棵完全二叉树是有效的存储方法
; \1 S% S3 E# r% J+ [# W' M正确资料:


' F! |# q+ C6 s8 q6 v5 f* u0 d第3题,从一个长度为n的顺序表中删除第i个元素（    ）时，需向前移动的元素个数是（    ）。
A、n-i
B、n-i+1
2 ^/ r1 t" v& k3 f* H1 ]C、n-i-1
D、i
9 v7 a/ G" x5 y  n7 z& J8 l正确资料:
5 z5 r1 g% D5 ?
( _8 D; R& i$ g" S) X: r
第4题,若有序表为（    ），则在二分查找关键字b的过程中，先后进行比较的关键字依次为（    ）。
A、f,c,b
B、f,d,b
' d! s5 _5 B) j) _: `& q. A$ KC、g,c,b
D、g,d,b
9 e4 e; \. W+ s. E# J- }$ B- y正确资料:


第5题,以下数据结构中哪一个是非线性结构？（    ）
A、队列
9 Q/ x) Q, r3 {$ R8 ?B、栈
: D% A; g  w9 J  W/ NC、线性表
D、二叉树
正确资料:
& s0 w5 f/ z  z% w  S8 Y

第6题,队列的特点是（    ）。
A、先进后出
B、先进先出
C、任意位置进出
* o4 F  M; l/ g( A& y) gD、前面都不正确
- ~( t. F5 w( F8 m正确资料:
# d3 ?  `# A6 r3 k

第7题,对n个记录进行堆排序，所需要的辅助存储空间为（    ）。
4 u+ Q) r/ x! a$ M: ZA、O（1og2n
, h# _# T) Q: \8 H0 tB、O（n）
  G% V' y/ `0 `) x  Z0 lC、O（1）
D、O（n2）
: d& D- t; z. t1 i/ x, y4 C正确资料:
. e0 D6 z0 s% K/ V+ b" P* q7 r
+ K% R! X/ g; b- T; S
第8题,在数据结构中，数据元素可由（    ）。
A、实体
B、域
3 R. s# l, L3 }9 dC、数据项
D、字段
正确资料:


第9题,在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i趟排序之前，无序区中元素的个数为（    ）。
A、i
+ K6 t' n- u9 F- B+ ^, GB、i+1
. p. D3 N4 t' KC、n-i
4 z9 r+ [, N( \) i' |, WD、n-i+1
正确资料:

, C6 i7 k- k- X
第10题,一散列表长度m为100，采用除留余数法构造散列函数，即H（    ）=K%P （    ）,，为使散列函数具有较好的性能，P的选择应是（    ）。
# ~& ?' f  D# _, Y- U8 HA、99
B、100
C、97
D、93
; p  x8 n) H( o6 V/ D正确资料:

  ^# p9 O1 _8 Q3 U! g
, N. D7 f/ I4 N2 C( L  J# o第11题,设有一个二维数组A[m][n] （    ），假设A[0][0]存放位置在600，A[3][3]存放位置在678，每个元素占一个空间，则A[2][3]的存放位置是（    ）。
A、658
B、648
' Z( P0 g3 @  ]  v3 Z' H# TC、633
1 K4 P: L' L& w/ ~D、653
/ y$ }, W- s, r, _; g正确资料:
8 k* B$ m. s: V! l' q
$ b6 W8 [" v8 @) B- \! N! R- h
第12题,对一个算法的评价，不包括如下（    ）方面的内容。
A、健壮性和可读性
8 i1 {1 ~8 ]4 }+ O# ?+ {B、并行性
C、正确性
* Q1 _% @  Z4 X+ P/ f, TD、时空复杂度
正确资料:
) M8 m- ?( w; I6 F
3 B6 N4 i( N5 A7 y9 D5 W+ I
; ^+ f, Q$ \' E( m' N5 M第13题,若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为（    ）。
A、图中每个顶点的入度
B、图中每个顶点的出度
* a8 f1 W( ~" }) ?C、图中每个顶点的度
  t& d+ V- P2 v* [0 pD、图中连通分量的数目
; j4 @# O6 O+ u1 ?正确资料:


第14题,若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A[3]的比较序列的下标依次为（    ）。
3 _- X; z4 y. sA、1，2，3
B、9，5，2，3
C、9，5，3
% x* `5 z; Z- a8 a( [# H! k3 ND、9，4，2，3
( C( ?/ B8 ^* x8 U& x4 l- C正确资料:
; t; e$ j/ ~5 m" I

第15题,对于关键字序列（    ）进行散列存储时，若选用H（    ）=K%7作为散列函数，则散列地址为0的元素有（    ）个。
A、1
B、2
, k0 s. ?: [9 x3 r  w- zC、3
) [" a/ b. d0 j( v0 o: ^D、4
正确资料:
$ H2 v$ q* o- f3 Y' z
" `2 V! N' I; _) b/ X6 `/ {6 c; B* e
  ^& {8 {( B8 `1 @. W$ g& t第16题,采用开放定址法处理散列表的冲突时，其平均查找长度（    ）。
( V  b+ }! z5 UA、低于链接法处理冲突
1 M$ n, |( z1 r  }B、高于链接法处理冲突
C、与链接法处理冲突相同
D、高于二分查找
正确资料:


+ Z3 ^3 X" S$ L& }, ~+ _" L3 P* r第17题,下面关于图的存储的叙述中正确的是（    ）。
A、用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关。
' d; T. F% K8 w6 {1 |+ U7 EB、用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关
C、用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关。
! g6 ]4 |; Q6 _' VD、用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关。
# w: Y9 Y8 M: M& k6 t  ^1 i正确资料:


第18题,从二叉搜索树中查找一个元素时，其时间复杂度大致为（    ）。
" o2 ^' e( o" p  Q% ^# S5 y* uA、O(n)
4 x$ p# V& U/ \& t& x0 l4 n  vB、O(1)
C、O(log2n)
D、O(n2)
正确资料:

3 Y1 G* ?6 G& e- K# ^
第19题,假定有K个关键字互为同义词，若用线性探测法把这K个关键字存入散列表中，至少要进行（    ）次探测。
) Z1 Y* {: m1 \0 c/ u! ZA、K-1次
B、K次
C、K＋l次
D、K(K+1)/2次
正确资料:


第20题,对于线性表（    ）进行散列存储时，若选用H（    ）=K % 9作为散列函数，则散列地址为1的元素有（    ）个。
, K: u0 R+ y! u! i9 pA、1
B、2
C、3
4 ~( i: N) \# CD、4
正确资料:


第21题,设Huffman树的叶子结点数为m，则结点总数为（    ）。
A、2m
B、2m-1
C、2m+1
! ~- w' P! X% E) SD、m+1
3 n& X6 U6 L" o% u正确资料:
. `" [( K+ Q  o; x( ]

第22题,一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是（    ）。
4 R: j& a" \) ]+ o; k1 D# [6 BA、2 3 1
B、3 2 1
C、3 1 2
D、1 2 3
* ]' j; U+ E% ?( ^; T* Y正确资料:


第23题,在一个带有附加表头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行（    ）。
A、HL=p; p-next=HL;
5 e+ l3 W1 I1 ]0 }B、p-next=HL-next; HL-next=p;
C、p-next=HL; p=HL;
9 t: V8 l- V* D# YD、p-next=HL; HL=p;
正确资料:
" c2 S: [5 x" b9 f4 y
3 i( K2 H5 K/ q6 s& \# t7 ~$ M
第24题,设有6个结点的无向图，该图至少应有（    ）条边才能确保是一个连通图。
1 {' `+ }: E- d# w/ x' bA、5
B、6
9 b3 G2 ~1 L9 |" @3 p! wC、7
D、8
正确资料:

. |1 ~# L0 G0 s* `7 @( _
4 i" K8 ?  q5 J! Y9 Y* X第25题,带有头结点的单循环链表的头指针为head，则该链表为空的判定条件是（    ）。
A、head= =NUL
B、head-next= =NULL
C、head!=NULL
D、head-next= =head
7 O/ H' }( P- f& h" l正确资料:
# x) ^: x- Y0 p' m% |7 {& e% o+ z" j

0 H$ ]7 O; `; Z' E, P; N7 l第26题,对一个算法的评价，主要包括如下（    ）方面的内容。
A、健壮性和可读性
6 o% x* k& h! G6 m3 M0 SB、并行性
C、正确性
& B/ |5 K0 P2 SD、时空复杂度
E、界面友好性
正确资料:,C,D


% @# `, s- |2 r( C第27题,以下哪些是队列的基本运算？（    ）
3 C9 L9 q6 @: U0 D1 G9 R. dA、在队列第i个元素之后插入一个元素
% Z; }" s- T2 {B、从队头删除一个元素
C、判断一个队列是否为空
D、读取队头元素的值
E、将队列中的元素排序
正确资料:,C,D
6 x8 P$ w8 m6 Q% o
! P# q. \- I; E
第28题,以下序列中，是堆（    ）的有（    ）。
7 T! x- S9 q% {$ N. V9 |- PA、{15,26,38,49,27,51,39,62}
$ s3 i( V0 g+ r3 ^& [7 ^4 lB、{15,23,71,94,72,68,26,73}
# l$ r# x7 h4 s% wC、{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


第29题,下述（    ）是顺序存储方式的优点。
A、存储密度大
B、插入和删除运算方便
4 M$ A1 D) E( j' Z3 y' f! K1 yC、获取符合某种条件的元素方便
3 z1 a& n% p: U1 v. _: w; t/ qD、查找运算速度快
9 q. m& A- a6 y* n/ G5 VE、可以很方便地存取第i个元素
+ t  {7 C1 g7 h' n8 ^正确资料:,E

% D' b/ M( D  |
第30题,一个广义表（    ）,（    ）,c),（    ）))) 的表尾是（    ）,c),（    ）))。
A、错误
B、正确
8 }  f& j9 y; T0 j  C正确资料:
" B! \! h$ B1 C( j% p! G
# O* M' t5 r3 Y: L8 b7 V
6 t0 q+ e' l1 u+ t第31题,有回路的有向图不能完成拓扑排序。
# D5 A2 ], _3 B3 V7 z* f  bA、错误
. c* o) E. ?" z. MB、正确
正确资料:


第32题,对任何用顶点表示活动的网络（    ）进行拓扑排序的结果都是唯一的。
A、错误
8 X4 Q* r4 r# HB、正确
正确资料:
; S" i5 q- y5 O* G: K4 |

第33题,为度量一个搜索算法的效率，需要在时间和空间两个方面进行分析。
A、错误
! S- r3 A  `* fB、正确
+ |0 B3 G' o& X/ y正确资料:

2 k- j" Z* w% w. S- @6 u/ V
- p4 O0 H, a6 J% S+ |第34题,进行折半搜索的表必须是顺序存储的有序表。
A、错误
' i7 ^- F* |4 U# L! G$ s/ kB、正确
正确资料:
% C8 ^- R9 L5 A' f' n2 T8 k

+ w) ?& q- c" m( {第35题,存储无向图的邻接矩阵是对称的，因此可以只存储邻接矩阵的下（    ）三角部分。
A、错误
B、正确
正确资料:
5 }% Q* B+ i) p  w8 x# w$ ]. Y
9 W3 }9 s7 R$ h. x( G9 m% P
% K- F8 E/ f3 N" p第36题,线性表若采用链式存储表示, 在删除时不需要移动元素。
& T1 Z/ s: w, M1 N; bA、错误
B、正确
正确资料:
$ _( t" S8 x9 Q, O

第37题,在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻。
A、错误
5 n' b9 n7 k) w% {; hB、正确
& k& {6 z3 M6 D2 ^- n: l7 T7 u正确资料:


第38题,使用三元组表示稀疏矩阵中的非零元素能节省存储空间。
8 I# E3 m' s- c" jA、错误
% A3 @: l/ N, p, [5 jB、正确
& N$ y5 ~7 B4 o正确资料:
  [3 V; f" _2 f; G
$ ^% L  }9 W+ \7 F
第39题,线性表若采用链式存储表示时，其存储结点的地址可连续也可不连续。
A、错误
B、正确
1 b8 a7 j+ e8 W$ ~7 L/ y1 o, a正确资料:
3 E& c$ Z/ n) ?

8 [2 ^. u) R9 q第40题,二维数组是数组元素为一维数组的线性表，因此二维数组元素之间是线性结构。
* q( \" Y5 s! x6 E7 FA、错误
B、正确
4 v3 i1 s6 w2 F9 L& @正确资料:


+ v$ b% J1 \7 K# l( k8 L  X1 r第41题,链式栈与顺序栈相比, 一个明显的优点是通常不会出现栈满的情况。
A、错误
  r& U0 s( x: q9 x# T# f/ yB、正确
) e! j3 o) Z8 q- \9 s7 F) B正确资料:
: C& ^2 ]- T6 `9 O' h' J

4 ^/ R) i* [: b% _1 b第42题,数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的。
A、错误
5 q- W  P% Y* ]! O( R2 Z$ ]B、正确
正确资料:
  \  z! F( H" p5 R( @& m

第43题,图G的某一最小生成树的代价一定小于其他生成树的代价。
A、错误
( h$ A+ K# Q* Z( [- ]4 t; oB、正确
正确资料:
: d# n/ R- g! Z+ c$ ^; N

( I' D- r  R/ T第44题,在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。
3 B% b  ^& Q% cA、错误
B、正确
正确资料:
* F5 _5 |6 b9 d# I+ U4 B6 y  h


3 z. D, {/ y$ M! E  z5 `

9 \. F; `8 \6 }; L. k

; u" r# r; Y4 v/ n$ q


0 r" J6 P) C5 F% u6 V3 ]' F
. G5 q% l3 v  A( I


. J6 U8 c8 K9 f6 Y  V. g' G7 k