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

admin

【奥鹏】[四川大学]《数据结构2264》18春在线作业1
+ y. \! [. D6 ~: M) r1 X2 Z+ b试卷总分:100    得分:100
第1题,树最适合用来表示（    ）。
A、有序数据元素
9 P2 |, B- i# ^B、无序数据元素
C、元素之间具有分支层次关系的数据
D、元素之间无联系的数据
0 p5 a1 B  r# G0 h$ a

% a, i4 z; T3 z1 S+ I# z9 g! Z' E9 S
6 r$ q& t) T' \* W2 D2 |第2题,下列关于数据结构的叙述中，正确的是（    ）。
A、数组是不同类型值的集合
B、递归算法的程序结构比迭代算法的程序结构更为精炼
C、树是一种线性结构
! {5 |6 i4 A  {" F! w( d  iD、用一维数组存储一棵完全二叉树是有效的存储方法
& J$ O6 v! N  d1 ~& F7 P

# w; U; J& Y" ^
) F  E: d- [, _. O) c第3题,从一个长度为n的顺序表中删除第i个元素（    ）时，需向前移动的元素个数是（    ）。
% `) w% ]& O+ B$ `9 aA、n-i
B、n-i+1
C、n-i-1
7 u7 f- ]* W4 x2 v; }D、i


9 z( B& Q8 K. p& ]
第4题,若有序表为（    ），则在二分查找关键字b的过程中，先后进行比较的关键字依次为（    ）。
+ N4 I. b  T* E- {5 O$ i8 L" dA、f,c,b
B、f,d,b
6 w- T, L' Y, V: ~; s# w, TC、g,c,b
D、g,d,b



第5题,以下数据结构中哪一个是非线性结构？（    ）
0 Q/ g" H# ]. a7 K  [& ?% XA、队列
B、栈
9 i- q4 G: i4 Z. p, ]9 IC、线性表
8 i& b0 s* f2 ?* H9 v+ BD、二叉树



第6题,队列的特点是（    ）。
/ h8 \0 w' m  c6 ^& |: u. LA、先进后出
8 K. w( x; B! V% h4 MB、先进先出
' D) c; g5 z' YC、任意位置进出
D、前面都不正确
. A5 _) ?! f' Q$ \
/ y1 S  n" Y' f3 t, i

2 K. x! q: \% I" z$ I第7题,对n个记录进行堆排序，所需要的辅助存储空间为（    ）。
A、O（1og2n
B、O（n）
C、O（1）
D、O（n2）


3 L& c; i8 W  U+ N
" g  G6 @2 h7 D5 K8 S% Z) R' c) C第8题,在数据结构中，数据元素可由（    ）。
: n7 q4 C2 f, X! ^. yA、实体
9 `1 C' c* u. C* i& PB、域
  {: ^& q8 [( G* n4 sC、数据项
D、字段
  {! b  R/ X; d- x, m$ a
! D; ~" A' p, A- u2 ~- E) y
1 M- ~: D1 Q! o) n: w; h
第9题,在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i趟排序之前，无序区中元素的个数为（    ）。
  Z$ M* J4 J: r  _A、i
B、i+1
. c0 X. Q6 i9 A8 iC、n-i
D、n-i+1

" u3 F+ o2 p$ R$ E2 B8 a1 g* e
* a3 j* \0 X2 H0 r  g0 V4 o
第10题,一散列表长度m为100，采用除留余数法构造散列函数，即H（    ）=K%P （    ）,，为使散列函数具有较好的性能，P的选择应是（    ）。
A、99
+ T. c0 Y+ l1 V+ v, T/ n- U/ |9 QB、100
$ }7 g( M2 i. K& \C、97
D、93

0 @) C4 D' L& w1 w

第11题,设有一个二维数组A[m][n] （    ），假设A[0][0]存放位置在600，A[3][3]存放位置在678，每个元素占一个空间，则A[2][3]的存放位置是（    ）。
9 q" X7 r2 m& X& q  ~6 a5 U* _) wA、658
B、648
C、633
D、653

, ^1 b! b$ e) d/ H

第12题,对一个算法的评价，不包括如下（    ）方面的内容。
A、健壮性和可读性
( ?, K4 S3 W* y; NB、并行性
C、正确性
D、时空复杂度
% A3 t$ z% i' [% M# E" O


第13题,若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为（    ）。
: I, ^& `% f5 c6 c1 o) HA、图中每个顶点的入度
B、图中每个顶点的出度
C、图中每个顶点的度
6 ?; S3 ]8 Q- @/ U! k! p& R! C( sD、图中连通分量的数目


' i1 `: A/ `4 D, l6 f. `
/ I4 r  b+ ~$ l; P  j( N: e: _+ q第14题,若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A[3]的比较序列的下标依次为（    ）。
' f- g2 @" y2 N: n* TA、1，2，3
" l7 ]! b% d3 n( v- RB、9，5，2，3
& h1 E/ s  R+ qC、9，5，3
D、9，4，2，3

+ a% s, V" e! Y$ y
! t: S7 x8 W- S+ h3 l6 B
第15题,对于关键字序列（    ）进行散列存储时，若选用H（    ）=K%7作为散列函数，则散列地址为0的元素有（    ）个。
$ `2 g$ @1 V% h5 M+ Y3 RA、1
7 ~! L3 C" h2 oB、2
C、3
* h9 h3 ~0 x  _  W- C) ?! BD、4
: f* |. R" L/ y6 ^


( S- W' L2 l# n$ d第16题,采用开放定址法处理散列表的冲突时，其平均查找长度（    ）。
% Y$ u  ~2 w" V0 q* UA、低于链接法处理冲突
6 Y  k5 \* O; {- V, w, R, JB、高于链接法处理冲突
C、与链接法处理冲突相同
D、高于二分查找
! ?6 ~5 o" ~3 I) Z. t. f& v8 S

- C# f4 _. s! l4 g" ?9 g; g0 t" N
第17题,下面关于图的存储的叙述中正确的是（    ）。
A、用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关。
B、用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关
' y+ c- R# t- S' c9 w5 P& B; @+ vC、用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关。
D、用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关。

) j$ M( V/ }. s. u4 {0 n. [
3 H7 k- B( o4 h' Z. I0 `6 W
第18题,从二叉搜索树中查找一个元素时，其时间复杂度大致为（    ）。
; `5 k$ t& V- A5 v$ NA、O(n)
% x2 X. b# `  {3 {* G8 r$ QB、O(1)
C、O(log2n)
2 G' q, H3 e+ fD、O(n2)



4 L; @8 ^( g+ G8 U( _% `0 j5 N第19题,假定有K个关键字互为同义词，若用线性探测法把这K个关键字存入散列表中，至少要进行（    ）次探测。
A、K-1次
* C2 v  U( ]+ z, o% UB、K次
C、K＋l次
D、K(K+1)/2次

0 q) `4 [& |0 S

第20题,对于线性表（    ）进行散列存储时，若选用H（    ）=K % 9作为散列函数，则散列地址为1的元素有（    ）个。
A、1
( r4 [/ z" C0 J) f  n; O; s4 ZB、2
7 o# i; C, b! [. Q; L0 K" k/ t. XC、3
% j" a! d" ~( {/ R- j" ~3 \1 SD、4


9 W" I/ b# f. @* Z5 t
+ A! b: R/ G- x' A* \第21题,设Huffman树的叶子结点数为m，则结点总数为（    ）。
A、2m
B、2m-1
: A* R: D1 u; ZC、2m+1
* V# C: ]9 c5 F$ S- R( HD、m+1

" _6 E1 V- H: X7 }4 ^6 B
& ]7 G& _3 x5 t5 h
第22题,一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是（    ）。
5 \% I# s0 D. v% ?3 s" F  f  mA、2 3 1
5 @4 g, X/ j! l- ~% VB、3 2 1
C、3 1 2
$ {8 |" E) |( T. w7 S% uD、1 2 3


) I1 q' {/ @$ d7 v1 ~* C1 o* Q
8 q9 `" H/ d( Y6 v, e第23题,在一个带有附加表头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行（    ）。
# r' ?& ]8 U3 v, K2 V% |5 ^A、HL=p; p-next=HL;
! {/ O* i! u) i1 l; `, VB、p-next=HL-next; HL-next=p;
C、p-next=HL; p=HL;
D、p-next=HL; HL=p;

; A: j3 ^" i* X  n& |, R6 I" I1 ~& L$ M
6 T1 t8 }1 l! n
第24题,设有6个结点的无向图，该图至少应有（    ）条边才能确保是一个连通图。
( x' G0 s, B) B, m3 @) `A、5
5 x, p. Z; t# N. xB、6
C、7
D、8
& Z9 F9 c7 U  B$ j* N; Y9 @
! z0 X  Z0 s6 |1 w2 u& G

! @3 V2 z/ e+ q% b第25题,带有头结点的单循环链表的头指针为head，则该链表为空的判定条件是（    ）。
A、head= =NUL
# S% t! ^: u8 m9 S  BB、head-next= =NULL
C、head!=NULL
6 E4 J+ ?0 P4 g1 }D、head-next= =head
2 K; K) [1 T$ W9 U6 @3 R6 b
+ j4 g" m! i5 m- T. V' t# c

第26题,对一个算法的评价，主要包括如下（    ）方面的内容。
A、健壮性和可读性
B、并行性
5 o- R/ o) _6 a) E; B, c6 k, S! xC、正确性
9 ~" t) _' N  S- XD、时空复杂度
# Z8 {# y3 F) I  ^$ b( w) }6 C' {7 uE、界面友好性
- x2 _5 v+ j+ J5 ?7 y6 P, o,C,D
: d0 N6 R) a% l) {
- P/ H- c. o* e5 H- Y
第27题,以下哪些是队列的基本运算？（    ）
A、在队列第i个元素之后插入一个元素
: A/ t! n& G8 \B、从队头删除一个元素
- w- {4 n# I. c8 yC、判断一个队列是否为空
/ b5 H5 {& K. ^: dD、读取队头元素的值
E、将队列中的元素排序
,C,D
% H& G. }( T7 D- n+ u. f7 R

7 {' R) s$ _' C4 o) w& X7 R1 x/ ^第28题,以下序列中，是堆（    ）的有（    ）。
/ E- d$ i% F! K% @! l3 U) EA、{15,26,38,49,27,51,39,62}
" D& y8 k& `$ z9 H, }5 t1 @9 cB、{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}
" ]0 D5 m0 s, L) d7 J,C,D,E


/ b7 g0 M1 w; ]6 r$ s- h, X第29题,下述（    ）是顺序存储方式的优点。
# n/ [+ }# k6 o9 Q9 ^8 _& ?A、存储密度大
: ^/ @9 V- G% ?3 o% F# e, }/ U- AB、插入和删除运算方便
C、获取符合某种条件的元素方便
+ q5 j9 g! H: t! Z# R/ rD、查找运算速度快
E、可以很方便地存取第i个元素
9 m) }2 b2 B8 @* P,E


1 s" m' |% D7 E, D第30题,一个广义表（    ）,（    ）,c),（    ）))) 的表尾是（    ）,c),（    ）))。
A、错误
; X/ O0 A' y# G+ QB、正确

% ]6 C( Z" I/ W, e
$ p  D: u. z: b5 x" i
! T* F0 ~: E7 v6 ?; _3 K第31题,有回路的有向图不能完成拓扑排序。
A、错误
) _  X- k: w% H# z9 w" J8 VB、正确
# N3 O  e6 Q  O9 S% R/ _" O. V; B5 f
; V8 P+ n9 @3 J# P+ h
% E1 f% X" \0 u$ j2 w( x/ m
第32题,对任何用顶点表示活动的网络（    ）进行拓扑排序的结果都是唯一的。
A、错误
; t2 J3 a# A& Z6 ]; C- y1 tB、正确
$ [( z; O* y9 U+ C# x

. r* a, I/ I2 p7 N! ~
3 `, V2 j4 M3 b9 u) i- l第33题,为度量一个搜索算法的效率，需要在时间和空间两个方面进行分析。
  k/ g5 J( o% tA、错误
B、正确


5 d9 l) |6 u) ]! s  g0 t0 F1 I
: t) O. u# D. C% ?$ Y第34题,进行折半搜索的表必须是顺序存储的有序表。
A、错误
B、正确
" [9 E8 K: J/ _9 `8 W  F8 `
' Z. A4 K5 |# I( J

& E+ b' m. I/ |  D8 R$ r第35题,存储无向图的邻接矩阵是对称的，因此可以只存储邻接矩阵的下（    ）三角部分。
0 J! X2 U* {* J  [* z$ qA、错误
" W9 E. m) z% a4 ^  S& R- p( bB、正确
* r; U  q0 P  O1 }( P! m
/ T' k- e& r( T( M/ B4 V# M1 Y$ r
( c& B3 A8 _, B
第36题,线性表若采用链式存储表示, 在删除时不需要移动元素。
( ^1 O) [  Y7 g( J7 L2 ?( V0 bA、错误
B、正确



第37题,在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻。
( f$ Q* |) u. J' k% U0 y' t1 `A、错误
B、正确

* K2 P: k5 _# K4 ~7 C6 V

第38题,使用三元组表示稀疏矩阵中的非零元素能节省存储空间。
A、错误
B、正确



5 c7 [0 i/ ]& Q1 e7 b$ r; R- b2 ^第39题,线性表若采用链式存储表示时，其存储结点的地址可连续也可不连续。
; t' M- W0 G+ JA、错误
! B  s& u- M& M; OB、正确
1 U5 A) N+ [& U& X- n
" F" Y8 m/ T8 ~0 U6 o

3 N& ~# ]  g- e3 o第40题,二维数组是数组元素为一维数组的线性表，因此二维数组元素之间是线性结构。
/ S# ^6 X  F1 rA、错误
! b- b# T( m( t% A0 g8 BB、正确


3 ~3 j* T8 O  {9 P$ j
第41题,链式栈与顺序栈相比, 一个明显的优点是通常不会出现栈满的情况。
+ s- Z6 N" o% D3 |0 g4 KA、错误
& m4 q5 P( O6 m. A0 n2 J5 }B、正确
& o( h1 L/ t2 C' b+ ^8 q# X
. t- A! z& T) `# M# w, h  L5 i  ]

5 g3 ~7 r% s9 o8 N3 S/ A0 ]9 E6 b第42题,数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的。
3 x* f6 O5 U% K8 s0 TA、错误
, m  ]6 l( c( G+ s- GB、正确


0 ]3 L7 y0 n# N) [" V6 P
第43题,图G的某一最小生成树的代价一定小于其他生成树的代价。
A、错误
B、正确

. r* M: q7 j9 d# ~7 s9 w9 b

  {, C: A& d# G第44题,在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。
A、错误
B、正确
7 s8 W" s) K  l  ^' H
" V8 J, m) y3 y' Q# K; s$ k# Q

# o+ U( k1 e- p# O+ l! T! s
  l8 P5 v% o) K4 f' n


- H. u( z/ D$ K2 ]

$ K6 Y( W0 f3 Z  W
' G. K/ u! d- U5 G
- K+ E& Z- T: U; l1 ^% a

taoxin217

学长介绍来的

wyyy9

顶顶，资料下载试试！