川大《数据结构2264》15秋在线作业2资料辅导资料

奥鹏在线作业

& k- A! P" N4 ~: W' g$ Z! C+ ?《数据结构2264》15秋在线作业2
1 G' r, \% f+ e/ @

% j; F9 t( v7 S' f0 l# R% ~
2 Y; {: f* |7 `
一、单选题（共 25 道试题，共 50 分。）
9 `+ i1 @1 b, F; O* s& o
2 x% T3 a3 C- F, I( f1.  有n个记录的文件，如关键字位数为，基数为r，则基数排序共要进行（ ）遍分配与收集。
. n
.
9 b+ x9 C& ?& K2 q: }8 O& v7 b. r
& ^* r, U& |7 @3 R8 G. n -
谋学网：www.mouxue.com：
5 e" b9 Y6 U8 p+ Z2.  对一棵有100个结点的完全二叉树按层编号，根结点编号为1，则编号为49的结点的父结点的编号为（ ）。
. 24
. 5
. 98
9 l1 ~3 P8 N  \  K1 d& j! |. 99
谋学网：www.mouxue.com：
4 ?. d2 @2 r$ H3.  采用开放定址法处理散列表的冲突时，其平均查找长度（ ）。
/ I( C' V. \3 Q! Q- B. 低于链接法处理冲突
3 F% h+ A( \1 x% y! v/ e  \. 高于链接法处理冲突
6 s7 B, j& i2 m4 V: [9 L; `5 l5 d) x. 与链接法处理冲突相同
0 s  V1 x0 u. D, a' q: Q4 [" G4 ^/ K. 高于二分查找
谋学网：www.mouxue.com：
4.  如表r有100000个元素，前99999个元素递增有序，则采用（ ）方法比较次数较少。
. 直接插入排序
. 快速排序
. 归并排序
& f, s" N5 {' L7 o. 选择排序
! s5 l* d0 t0 S* Z6 r& [谋学网：www.mouxue.com：
5.  下面关于图的存储的叙述中正确的是（ ）。
. 用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关。
! ]% N. L$ x6 o! V2 p/ d1 t. 用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关
. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关。
) Q, \! w3 B+ J; \) b, {. 用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关。
, h" G, I5 N4 _$ ~* {8 V; t* B谋学网：www.mouxue.com：
/ Q" s" A# Y# j# y7 {( H9 z" y6.  若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为（ ）。
. 图中每个顶点的入度
. 图中每个顶点的出度
. 图中每个顶点的度
. 图中连通分量的数目
谋学网：www.mouxue.com：
7.  对于关键字序列（ ）进行散列存储时，若选用H（ ）=K%7作为散列函数，则散列地址为0的元素有（ ）个。
4 w/ a$ f/ b0 ]& U7 B# }8 w" L. 1
. 2
$ o8 {+ F+ I6 m. 3
. 4
9 m4 u: E8 |# d4 |# H谋学网：www.mouxue.com：
8.  设有6个结点的无向图，该图至少应有（ ）条边才能确保是一个连通图。
6 e" b' I; G, p5 a5 e6 J. 5
. 6
! \9 i4 W3 ~/ J8 M0 K. 7
9 N3 r  R) s9 \# I- F5 a2 Y' C. 8
% N% G( _! l8 n% F0 c/ e! z- K5 S谋学网：www.mouxue.com：
9.  在线性表的下列运算中，不改变数据元素之间的结构关系的运算是（ ）。
. 插入
# b- h& l6 R" n; j: f; p. 删除
  f4 x+ \0 @5 L; Y1 k# j8 q. 排序
. 查找
* y4 J. Z2 ]3 L2 i3 U8 W+ g谋学网：www.mouxue.com：
0 Y# E5 k. u- a2 f9 X10.  对广义表L=（ ）,（ ）,（ ）执行操作til（ ）的结果是（ ）。
7 z, A/ u( o3 t6 i* V- j8 g( e. (,f)
2 H' G8 W/ {, q9 i6 W+ a. ((,f))
" A3 c8 X, c! V. |; C  }- ]% q. (f)
7 i! t* D+ Z- r9 O6 q) A/ i. ( )
  t" u$ L/ t2 E: a谋学网：www.mouxue.com：
7 [% i- t8 z4 V0 U  L4 {11.  若某二叉树结点的中序遍历的序列为、、、、、F、G，后序遍历的序列为、、、、F、G、。则该二叉树结点的前序遍历的序列为（ ）。
. 、G、F、、、、
. 、、G、、F、、
. 、、、、、G、F
- [( o) d0 d' Z& X9 ?# Y; W. 、G、、、、F、
4 ^, e1 h' r% d3 V谋学网：www.mouxue.com：
4 M6 d3 {5 t' S) Q12.  中缀表达式2+X*（ ）的后缀形式是（ ）。
. f1 Z2 }! c: t. 3 Y X 2 + * +
. Y 3 + X * 2 +
. 2 X Y 3 * + +
. 2 X Y 3 + * +
, R8 u- P" C. @/ k谋学网：www.mouxue.com：
13.  设森林F对应的二叉树为，它有m个结点，的根为p，p的右子树上的结点个数为n，森林F中第一棵树的结点个数是（ ）。
7 V) e" K. ]' i+ R. m-n-1
. n+1
) R2 |4 R2 j4 H+ M1 w6 f. m-n+1
. m-n
谋学网：www.mouxue.com：
/ a; N5 U2 P  ]14.  在一个带有附加表头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行（ ）。
2 N- |) [$ W  |. HL=p; p->nxt=HL;
. p->nxt=HL->nxt; HL->nxt=p;
. p->nxt=HL; p=HL;
. p->nxt=HL; HL=p;
) g: ^: t; b, p1 `2 F谋学网：www.mouxue.com：
9 B% q4 b  C6 \4 z/ A15.  队列的特点是（ ）。
. 先进后出
" }) k" c7 `% p7 s/ r& Y. N4 _2 O4 |. 先进先出
7 c8 T. V+ h/ _. 任意位置进出
. 前面都不正确
谋学网：www.mouxue.com：
16.  下面关于广义表的叙述中，不正确的是（ ）。
7 M# n8 o, i6 C' O+ g. 广义表可以是一个多层次的结构
- S# ]5 B, ^' u" E8 @. 广义表至少有一个元素
/ j5 s2 C% s8 O! z! O+ k6 _. 广义表可以被其他广义表所共享
# w5 I- A( c0 t7 g' o: r! j0 a- P% b. 广义表可以是一个递归表
谋学网：www.mouxue.com：
/ r# J- h  D% ?/ J. H17.  在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i趟排序之前，无序区中元素的个数为（ ）。
. i
7 e+ y; R5 P% Q9 o. i+1
6 x; d5 `0 y! x3 R. n-i
. n-i+1
# s" k6 X6 }0 x$ v, d# G谋学网：www.mouxue.com：
* \/ u" E0 S. t9 t6 z18.  树最适合用来表示（ ）。
. G% |; a# \* d. 有序数据元素
. 无序数据元素
( S+ ?9 p$ i" I5 x6 h. K: F4 H5 ]: d. 元素之间具有分支层次关系的数据
5 j0 Z( F& h( E. 元素之间无联系的数据
- x* `* ?* B' m' X# m" k  i7 |谋学网：www.mouxue.com：
19.  从L=（ ）,（ ）)中，取出nn元素的表达式为（ ）。
. h(til(L))
. h(h(til(L)))
0 F3 P! Y6 m: r1 |0 B. til(h(til(L)))
. h(til(h(til(L))))
谋学网：www.mouxue.com：
20.  设Huffmn树的叶子结点数为m，则结点总数为（ ）。
) l/ ]* s. J& _% ]. 2m
. 2m-1
. 2m+1
. m+1
谋学网：www.mouxue.com：
21.  对线性表进行二分法查找，其前提条件是（ ）。
. 线性表以链接方式存储，并且按关键码值排好序
+ U+ n9 C% ^6 B0 G( C. 线性表以顺序方式存储，并且按关键码值的检索频率排好序
. 线性表以顺序方式存储，并且按关键码值排好序
* Q0 x) W% f, `# {' X. 线性表以链接方式存储，并且按关键码值的检索频率排好序
2 \1 O; l% `% w  l谋学网：www.mouxue.com：
0 v$ r1 h3 D% G; X* n22.  k层（ ）二叉树的结点总数最多为（ ）。
1 ^% ~  o/ d5 B7 v8 F% c. 2k-1
2 ^9 L: Y6 H  h# S0 z/ T4 A, r. 2K+1
6 b0 J6 u. R. p. A; Q. 2K-1
7 l! t3 j4 i8 f* P/ [2 _3 u; C. 2k-1
谋学网：www.mouxue.com：
* d! n9 P2 x% t2 ^; ~, R0 J23.  假定有K个关键字互为同义词，若用线性探测法把这K个关键字存入散列表中，至少要进行（ ）次探测。
5 F  G/ }% U4 N7 I8 C+ E. K-1次
. K次
. K＋l次
. e& L- Q2 W2 g. K(K+1)/2次
谋学网：www.mouxue.com：
24.  从二叉搜索树中查找一个元素时，其时间复杂度大致为（ ）。
. O(n)
. O(1)
& t# E4 m( S5 d# p# r. O(log2n)
. O(n2)
谋学网：www.mouxue.com：
25.  若有序表为（ ），则在二分查找关键字的过程中，先后进行比较的关键字依次为（ ）。
. f,,
. f,,
. g,,
1 H" o: g; _+ F* G0 c7 o. g,,
6 E% b: ~$ k9 e' E: m" \/ o谋学网：www.mouxue.com：
4 t  {0 Z' D& F' `3 o# u


  _6 X% P3 I; ]4 \/ w4 k; Y《数据结构2264》15秋在线作业2
+ B7 U& D2 s/ Y, ^! r


+ s9 C, V9 ^  b) S; J( s
二、多选题（共 4 道试题，共 20 分。）
- p$ c3 Y/ Q8 P8 U- a4 H) V
7 ]* p5 }6 T1 h. }# z) X" C. U6 g1.  以下数据结构中哪一个是线性结构？（ ）
. 有向图
1 O+ Y" Z, M6 v+ S% x. 队列
) y$ g7 G4 L2 l& z4 m. 线索二叉树
. 线性表
* S0 r6 c3 u8 ], R" f% l4 Q4 K$ M: U. 栈
谋学网：www.mouxue.com：
2.  栈和队列的共同特点是（ ）。
4 Q6 q; D  T+ w6 h7 b4 G. 只允许在端点处插入和删除元素
. 都是先进后出
. 都是先进先出
. 没有共同点
  H& b! l9 B5 Q, D. 都可以采用顺序存储方式和链式存储方式
谋学网：www.mouxue.com：
/ o1 U! a! h7 l+ r' d3.  以下序列中，是堆（ ）的有（ ）。
; g5 T7 o* T) q( z1 N. {15,26,38,49,27,51,39,62}
- u5 J* m% w, ^2 n" D) j. {15,23,71,94,72,68,26,73}
. {15,27,26,49,38,62,39,51}
. {15,23,26,68,94,72,71,73}
3 ^$ ?4 v( E$ C. Z; N* E. {94,72,73,26,71,23,68,15}
0 Y4 ?+ ?! p/ Z3 {3 K, H谋学网：www.mouxue.com：
2 d7 m1 \  @7 h0 V4.  若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列为（ ）。
. 3，2，6，1，4，5
. 3，4，2，1，6，5
. 1，2，5，3，4，6
' m. z& n: E' F( N) w0 L. 5，6，4，2，3，1
. 6，5，4，3，2，1
% n1 X/ [  n6 B4 z/ K& a& G% n谋学网：www.mouxue.com：
' _3 q4 M: g) [7 |1 i4 v
4 y7 G0 D, M3 d* B; I

《数据结构2264》15秋在线作业2
0 I% h- p2 d! x$ p. M2 M
8 I+ K3 E) M1 s; y  C
3 x3 g$ M) g: a% L# T

5 o: n8 r6 D& h: I+ Y, }三、判断题（共 15 道试题，共 30 分。）
- S. S* v- f+ c+ v) j* W9 ~6 N! j
1.  用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数有关，而与图的边数无关。
; _% j0 E" _1 C/ H; m* w4 @( m. 错误
$ V% b- @0 I$ S: {. 正确
谋学网：www.mouxue.com：
2.  数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的。
. 错误
. 正确
1 ]0 H! d* a4 f+ c% C! s8 H  X谋学网：www.mouxue.com：
3.  一个广义表（ ）,（ ）,),（ ）))) 的表尾是（ ）,),（ ）))。
' \4 |4 i- T/ N7 R! s8 _0 {. 错误
: g" I# k5 I3 ^' S/ y0 n' k. 正确
谋学网：www.mouxue.com：
( ?+ ?  [) l# ]0 G4 y  f4.  在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。
. 错误
5 i- ?2 x+ X# R- \) J. 正确
谋学网：www.mouxue.com：
3 m' d/ }% X0 H9 F+ E8 P* W5.  在采用线性探测法处理冲突的哈希表中，所有同义词在表中相邻。
' ]/ D1 L! {- s' @. 错误
  C  Z& P# ?; g0 b' j. 正确
谋学网：www.mouxue.com：
6.  快速排序算法在每一趟排序中都能找到一个元素放在其最终的位置上。
- ]5 D$ s! ?6 Q4 G, v9 \; ]. 错误
. 正确
# L0 N, L) e. `$ r3 I+ q谋学网：www.mouxue.com：
" V$ f% M" r2 T6 s' q8 g# i7.  线性表的长度是线性表所占用的存储空间的大小。
* b6 \* t$ T6 |. 错误
  h) W0 G6 v) m7 T9 E) l. 正确
" ^. x# q- [& \3 t% u8 U谋学网：www.mouxue.com：
; Y; d, {. I+ v3 g. e! N8.  线性表若采用链式存储表示时，其存储结点的地址可连续也可不连续。
. 错误
+ u% R6 @, c# @; e" }. 正确
9 F5 ~' p) g/ r4 T! O0 }8 _谋学网：www.mouxue.com：
9.  二维数组是数组元素为一维数组的线性表，因此二维数组元素之间是线性结构。
/ s! u9 D( S8 w6 I. 错误
. 正确
谋学网：www.mouxue.com：
10.  用字符数组存储长度为n的字符串，数组长度至少为n+1。
; C! x% C7 z$ ?6 k# \* q1 g: I% ^7 ]. 错误
) Z; `5 t, c5 i, ^2 f& F+ Y& b  \. 正确
9 v. C% }% e% n8 ?/ m2 Z谋学网：www.mouxue.com：
( P, V4 ]. Z) N* W* W! C. Q11.  线性表若采用链式存储表示, 在删除时不需要移动元素。
. 错误
1 C% L: k4 J5 Q: t% r2 v/ B0 y. 正确
谋学网：www.mouxue.com：
12.  邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。
. 错误
* R) X* A2 ]2 _+ Y. 正确
# \9 [# r8 g; c$ m# \谋学网：www.mouxue.com：
13.  使用三元组表示稀疏矩阵中的非零元素能节省存储空间。
. 错误
* l* V, v/ o, b. P+ i* v' O. 正确
, W. `+ _  @( C* N谋学网：www.mouxue.com：
$ L7 E( q- `! G0 [/ S14.  若一棵二叉树的任一非叶子结点的度为2，则该二叉树为满二叉树。
. 错误
. 正确
谋学网：www.mouxue.com：
15.  链式栈与顺序栈相比, 一个明显的优点是通常不会出现栈满的情况。
. 错误
. 正确
谋学网：www.mouxue.com：

" `" q# @7 s1 x) [, l8 G% J
  M+ j& f5 k8 N

q120725437

资料不错哦，希望一直有这么好

╰独自遨游╯

哈哈，爽！

200802036280

不错

qibao

不错，OK ，满分！

周卫东肥东

哈哈，爽！

cshine

谋学网资料就是好！

ws02810348

抄的资料都满分，会不会老师怀疑

睡觉大过天

OK，资料不错

雪鸶

值得信赖