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

admin

【奥鹏】[四川大学]《数据结构2264》18春在线作业1
# Z! J. ~# u% ~- E, K; A: x试卷总分:100    得分:100
/ b' t) M! j* c* h- l第1题,树最适合用来表示（    ）。
- i/ _' G5 Q* f% ?, L! N: FA、有序数据元素
B、无序数据元素
C、元素之间具有分支层次关系的数据
/ H& V: c: X! |; f6 p5 h; M  S( H+ mD、元素之间无联系的数据
% n! C, ]* Y) t; S! _! {

, Q0 h: O( S, Q* I) T5 T
0 N0 ]7 P" P3 N: M4 \* U第2题,下列关于数据结构的叙述中，正确的是（    ）。
7 f5 B# }2 M5 i- D, D9 Q9 P, bA、数组是不同类型值的集合
B、递归算法的程序结构比迭代算法的程序结构更为精炼
  U. @# }- @, u$ I7 yC、树是一种线性结构
D、用一维数组存储一棵完全二叉树是有效的存储方法
/ D/ x+ p$ w7 }4 ~& `& E; {


第3题,从一个长度为n的顺序表中删除第i个元素（    ）时，需向前移动的元素个数是（    ）。
A、n-i
' W" f0 H6 J4 S7 w0 q  n- u: }B、n-i+1
' }' Z" h  ^- Y% d, YC、n-i-1
: `) F- I# {' [D、i

% @3 q9 h+ m; x! {& @
6 Z9 [8 ]# J& w# o6 c; [: b6 T
第4题,若有序表为（    ），则在二分查找关键字b的过程中，先后进行比较的关键字依次为（    ）。
/ m7 W" M# z9 m9 \+ y3 j( CA、f,c,b
B、f,d,b
+ M  E! M' N6 r6 c  H# b" P: KC、g,c,b
0 n( j# a! z, q- m! Y$ mD、g,d,b



) _5 g$ u3 G& J" u1 h+ Q第5题,以下数据结构中哪一个是非线性结构？（    ）
0 E5 P. }+ h% VA、队列
3 N4 a. a6 Z4 g5 [6 C0 U- eB、栈
: n3 d7 f" ?$ w/ e+ XC、线性表
D、二叉树
$ x; r/ d1 s% Y/ ~( i
% R; x- E( j( d* u& C
4 a# j$ h9 Z; q# }) |* y
第6题,队列的特点是（    ）。
& p; u* m0 ]4 `% \8 RA、先进后出
% G4 @" [( H- E8 B( b3 o! D+ FB、先进先出
" G4 R# L& p  ?9 p. U- WC、任意位置进出
D、前面都不正确



第7题,对n个记录进行堆排序，所需要的辅助存储空间为（    ）。
6 c3 Z8 r/ h1 i6 i: M, q) D; g, U/ RA、O（1og2n
B、O（n）
C、O（1）
+ J, a* H5 T1 n; U3 x  w# aD、O（n2）

7 a4 H4 W" b' r2 e
8 w4 a5 k1 p- a& R! R
第8题,在数据结构中，数据元素可由（    ）。
A、实体
B、域
2 R/ |0 o0 r& W' h2 IC、数据项
, i% a" m$ t- g8 z2 aD、字段



! E) T3 N8 {6 D5 S) j. Z1 r第9题,在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i趟排序之前，无序区中元素的个数为（    ）。
" o3 @" p- x6 z# y* n  \5 @! A. yA、i
! m8 G9 F; ?; D4 T* bB、i+1
C、n-i
D、n-i+1
( p) B1 n9 C7 F8 w5 M3 f! [


第10题,一散列表长度m为100，采用除留余数法构造散列函数，即H（    ）=K%P （    ）,，为使散列函数具有较好的性能，P的选择应是（    ）。
1 Y4 P6 H0 u7 V: f; }A、99
( b! D+ T: }! a" }. gB、100
C、97
6 @. [6 p) H7 C  M$ ID、93
$ Z) X9 u% q: f2 R
: Q6 X9 v" H. y1 g" }
: F# p. q& b' T$ h8 |' W4 |4 S
第11题,设有一个二维数组A[m][n] （    ），假设A[0][0]存放位置在600，A[3][3]存放位置在678，每个元素占一个空间，则A[2][3]的存放位置是（    ）。
A、658
/ f. q! }5 ^) |' c* h( s; a. CB、648
7 U; i4 C/ w3 r5 L, n  n+ M# [C、633
1 V* p0 Z1 ~2 z) ?: ZD、653


! U  v/ t) e3 a" k
第12题,对一个算法的评价，不包括如下（    ）方面的内容。
2 }3 N4 N+ z, s9 I, ^" HA、健壮性和可读性
B、并行性
C、正确性
- C6 g! F% C* T- K1 h7 a9 aD、时空复杂度

8 |0 T7 ?4 f3 `. g0 W5 w

  R# P: ^( m$ {4 ~/ |; j" @- W6 r第13题,若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为（    ）。
A、图中每个顶点的入度
9 `  }" q( @8 R3 AB、图中每个顶点的出度
C、图中每个顶点的度
D、图中连通分量的数目



% j4 T- j* r5 `第14题,若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A[3]的比较序列的下标依次为（    ）。
A、1，2，3
B、9，5，2，3
C、9，5，3
. I& {% G4 d# a, Z8 ND、9，4，2，3

/ c6 N5 D; u3 A; M* S

第15题,对于关键字序列（    ）进行散列存储时，若选用H（    ）=K%7作为散列函数，则散列地址为0的元素有（    ）个。
0 [3 c  J6 B! ~  R3 V6 lA、1
B、2
C、3
D、4
4 V* X, @; k& A  i5 r$ s
0 J. c/ M  a" ^
5 p! R7 S% \3 j# R' t, x+ H1 T
3 \6 f! C& g$ I7 v" P/ @$ B. ^: ]第16题,采用开放定址法处理散列表的冲突时，其平均查找长度（    ）。
6 R8 @: m' }& {$ y* P' }8 nA、低于链接法处理冲突
B、高于链接法处理冲突
C、与链接法处理冲突相同
D、高于二分查找


2 ~# R: @. o( `0 l) B& P
第17题,下面关于图的存储的叙述中正确的是（    ）。
A、用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关。
B、用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关
C、用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关。
, P# S$ y; h! x. b: N& `D、用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关。


/ I8 N! s/ t% B/ o
第18题,从二叉搜索树中查找一个元素时，其时间复杂度大致为（    ）。
A、O(n)
B、O(1)
: q! x6 v1 W* h) IC、O(log2n)
2 E6 E% Y: u% g# J8 Q1 a' R( KD、O(n2)
, C1 y- f& u3 C+ S# P
/ W3 g' j/ ~$ B. v$ ~
( V  e3 F" K! b1 y  y. z$ w
第19题,假定有K个关键字互为同义词，若用线性探测法把这K个关键字存入散列表中，至少要进行（    ）次探测。
+ e! S, a; a0 W0 G# MA、K-1次
B、K次
C、K＋l次
6 N# I4 n6 y) w0 O% p& U9 D: BD、K(K+1)/2次



第20题,对于线性表（    ）进行散列存储时，若选用H（    ）=K % 9作为散列函数，则散列地址为1的元素有（    ）个。
A、1
6 N9 ^- V" A$ N4 @+ U! n7 LB、2
  F/ v' O* R, e+ V" o) jC、3
D、4



4 }! o% }# |+ t, A/ s  |% d第21题,设Huffman树的叶子结点数为m，则结点总数为（    ）。
A、2m
' e7 d1 x- e: fB、2m-1
6 W, Q: Q8 n0 W4 R0 h. z  j( iC、2m+1
5 r- u1 u6 K6 ^. D; G& b, }: HD、m+1
5 V. [9 j* K1 x) w- g. c$ g% p1 z; M
6 d- m/ U! m5 y) D5 o4 E* M$ w

- M3 n$ D( D+ d第22题,一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是（    ）。
A、2 3 1
4 t  j: [8 R( @$ F" K; IB、3 2 1
C、3 1 2
D、1 2 3

( a$ P0 O' U' A) r, E
  |6 e( a# }2 K- c/ U
; r  M* X: A8 s3 _5 L第23题,在一个带有附加表头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行（    ）。
A、HL=p; p-next=HL;
4 X+ ]9 q; x* F& MB、p-next=HL-next; HL-next=p;
$ ^! f1 Q6 Y0 q* C, f* l; eC、p-next=HL; p=HL;
; R/ A; u6 G/ [& ?! n/ YD、p-next=HL; HL=p;



第24题,设有6个结点的无向图，该图至少应有（    ）条边才能确保是一个连通图。
A、5
1 v+ M8 c- z$ l7 [. rB、6
2 F6 I- u1 y8 A* p2 QC、7
8 D' ]: a5 ]( M' f. s6 V3 h  QD、8



/ @. \: e# Y! C第25题,带有头结点的单循环链表的头指针为head，则该链表为空的判定条件是（    ）。
% M+ Y/ c% X6 x/ n$ u) RA、head= =NUL
; U, L  m5 c6 z- u& M" CB、head-next= =NULL
C、head!=NULL
8 C8 ^& S0 w1 j2 uD、head-next= =head
! n5 K0 C! i$ m; f3 j& s' w: X


第26题,对一个算法的评价，主要包括如下（    ）方面的内容。
A、健壮性和可读性
; V4 a8 _/ X/ ^: kB、并行性
# s8 _& C) R3 Z3 i- aC、正确性
* V7 P7 }- o- |& }& z8 OD、时空复杂度
2 [, Z/ r- A4 B& [9 l" xE、界面友好性
9 [# l" n$ M& L2 E* B: t0 w,C,D


第27题,以下哪些是队列的基本运算？（    ）
* N7 D2 |6 c! Z5 @" Z" l( J/ j7 O  eA、在队列第i个元素之后插入一个元素
B、从队头删除一个元素
( P5 A( i5 A& `7 v7 p/ PC、判断一个队列是否为空
; P4 K. D$ T6 q, W3 r0 B5 LD、读取队头元素的值
E、将队列中的元素排序
,C,D
, M/ h+ ]( }' [* G8 W& [# F# j/ W6 }5 v

  e: ^( i# W: i0 D$ i$ ~% ^第28题,以下序列中，是堆（    ）的有（    ）。
, i% D3 N; i" ~/ v$ t9 @0 jA、{15,26,38,49,27,51,39,62}
* T1 u3 l/ B6 p9 V2 w. yB、{15,23,71,94,72,68,26,73}
C、{15,27,26,49,38,62,39,51}
$ t, l7 n) }5 A$ V3 R+ r* {+ M' SD、{15,23,26,68,94,72,71,73}
E、{94,72,73,26,71,23,68,15}
6 g3 d2 D8 L1 Z% f; A7 {,C,D,E

5 V9 L: P; s4 h1 x+ r' F
第29题,下述（    ）是顺序存储方式的优点。
A、存储密度大
+ a% }  o) [5 N; _8 j( XB、插入和删除运算方便
, J% S# R5 k& y# c: YC、获取符合某种条件的元素方便
D、查找运算速度快
7 u& H$ m# j* b4 n" [E、可以很方便地存取第i个元素
4 |) D, k/ n' b) ]# G! z& m. U; j,E


0 Q8 M, B' A1 @/ _) e: ^# h' S7 q! z第30题,一个广义表（    ）,（    ）,c),（    ）))) 的表尾是（    ）,c),（    ）))。
* f( V2 g6 `; P2 MA、错误
B、正确
1 `$ O0 @6 y. g1 o( e


9 t5 D) R$ l8 u8 B5 `/ r) _第31题,有回路的有向图不能完成拓扑排序。
9 ^1 X3 X  J% o- _* o' G" ~A、错误
B、正确

! s9 e( y& |8 J: _

第32题,对任何用顶点表示活动的网络（    ）进行拓扑排序的结果都是唯一的。
- f) @: t* M4 `* D! e1 P# }1 [A、错误
) e# L0 c! G1 R# C8 kB、正确

; O+ Q# v7 b) L& ~

* e9 d: E+ E: A  R% w$ N1 i第33题,为度量一个搜索算法的效率，需要在时间和空间两个方面进行分析。
A、错误
B、正确

! T5 A& W2 C7 y, Q8 i

* z! G6 {1 `/ l8 P) o第34题,进行折半搜索的表必须是顺序存储的有序表。
A、错误
. W$ Z2 k" n, F0 ^$ p  oB、正确
; S0 m( c4 X& f9 f" |& j
; O! ~% Z, p" s  G) H

# z+ N$ L; S% `第35题,存储无向图的邻接矩阵是对称的，因此可以只存储邻接矩阵的下（    ）三角部分。
A、错误
B、正确

: |1 @. _8 c; _( W4 Z* v$ Y

' r6 l* ~0 [; W) o- i* S第36题,线性表若采用链式存储表示, 在删除时不需要移动元素。
A、错误
B、正确
2 _3 T  H" m' V$ I9 k
: ]* n: O7 u% p
/ l0 k% G6 u- b5 n  X9 o
0 }; J( \. {1 N* o4 X第37题,在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻。
4 @  Q& q& O1 ~, i- b% kA、错误
0 d+ G6 b( @( A+ w6 ^2 ?- o. {B、正确

* Y, v( C# p: u; w- U& y  Y
7 d* R  z* X0 Z- C; M
第38题,使用三元组表示稀疏矩阵中的非零元素能节省存储空间。
A、错误
B、正确

: j  N1 k; w1 T" V8 j  E

5 L9 C$ ]' h' u, j- j* z第39题,线性表若采用链式存储表示时，其存储结点的地址可连续也可不连续。
4 R$ [# X$ ?! V" e3 lA、错误
+ I1 A; o& o) J. D: D9 D4 @B、正确



. U& s( }$ A# Y5 ?第40题,二维数组是数组元素为一维数组的线性表，因此二维数组元素之间是线性结构。
* J1 n# {" g! V; F4 f( @A、错误
( L- L. m9 ~# MB、正确
1 U5 l6 X# A$ B$ k2 @, e/ r/ A


第41题,链式栈与顺序栈相比, 一个明显的优点是通常不会出现栈满的情况。
# H( I" U% Z  y  Q; `$ }A、错误
6 X: _" ~) ~2 x/ C' X- P$ zB、正确



第42题,数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的。
A、错误
B、正确


7 I- L6 x; \. q6 y# r2 j+ N+ M2 F
第43题,图G的某一最小生成树的代价一定小于其他生成树的代价。
A、错误
B、正确
: G  f$ w* F/ Q) |& Z


, \+ ^; _, r$ ?; Z" O第44题,在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。
A、错误
B、正确
& S. l5 ^9 ?4 ~" v2 f. \

/ M) M! r- k/ m6 J$ Y! s$ b
, h6 [4 c2 U) U. i% i; b, U
0 n3 d5 c& x6 T

  |" T) K: m+ D

! S6 O8 p* D: x
5 P6 v9 {& J8 ]( w, p




# S" a) ~" x* P
8 V  O/ p* a/ t7 n- a! s, B$ e, \: L

taoxin217

学长介绍来的

wyyy9

顶顶，资料下载试试！