东师《数据结构》15春在线作业1（随机）辅导资料

谋学网

谋学网(www.mouxue.com)是国内最专业的奥鹏作业资料，奥鹏离线作业资料及奥鹏毕业论文辅导型网站，主要提供奥鹏中医大、大工、东财、北语、北航、川大、南开等奥鹏作业资料辅导，致力打造中国最专业的远程教育辅导社区。
2 M- O( G1 R, q. t6 ^+ ]! b
: Z/ }' Y+ f" ]5 V- p3 u  k一、单选题（共 20 道试题，共 60 分。）V 1.  由3个结点可以构造出多少种不同的二叉树？( )
A. 15
B. 21
C. 30
4 C' k) u; ]! |* P  e& ?  zD. 33
      满分：3  分
6 @$ W, c2 |, ]1 U/ K, |2.  有n个顶点的无向图的边数最少为 ()。
A. 0
. Z7 u. a! O! C# [; @B. 1
C. n-1
D. n
      满分：3  分
3.  判断线索二叉树中某结点p有右子女的条件是 ( )。
- H, X# P" m# S: fA. p->rtag = = 0
' a* l' }3 s7 U6 X7 n" R" kB. p->rtag = = 1
6 W' q- a( U: V2 C$ m$ b! MC. p ! = NULL
% U8 A  ^$ }/ \2 UD. p->lchild ! = NULL
% A* J3 ]: r1 L      满分：3  分
4.  下列哪一种图的邻接矩阵是对称矩阵？ ()
  H: J, G, R/ oA. 有向图
B. 无向图
C. AOV 网
D. AOE 网
      满分：3  分
5.  head指向的不带表头结点的单链表为空的判定条件是 ( )。
4 d. w* U0 h: @4 V& A6 RA. head = = NULL
B. head->next = = head
C. head ! = NULL
0 t! |0 y& o2 p4 YD. head->next = = NULL
1 X2 t; |* K- D: y# l      满分：3  分
6.  线索二叉树是一种 ( ) 结构。
& ]" F' k6 V2 H7 }A. 逻辑
B. 物理
C. 逻辑和存储
D. 线性
      满分：3  分
7.  排序趟数与序列的原始状态有关的排序方法是 () 排序法。
A. 直接插入
5 k+ s* C, r2 e: z9 x' U0 d9 m- BB. 直接选择
+ v  Y1 E: [+ s# R2 L" t' gC. 冒泡
; k2 S, o2 B+ _- o3 tD. 归并
      满分：3  分
' X# T9 ~$ I, Q7 F% r0 ~. _+ m6 Y8.  采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为 ()。
- i! Q$ S/ L1 m$ u) FA. n
B. (n-1)/2
) U$ @  [9 D' A" c  E7 Y- XC. n/2
D. (n+1)/2
      满分：3  分
9.  顺序查找法适合于存储结构为下列哪一种方式的线性表 ()。
A. 散列存储
  W0 q- w2 T% j. C9 S0 ?B. 顺序存储或链接存储
C. 压缩存储
% g& J* G- g# S: f( I. dD. 索引存储
      满分：3  分
/ |9 M# V1 i% v$ O5 q10.  采用邻接表存储的图的深度优先遍历类似于二叉树的 ()。
/ |7 ]' U6 H- N; I# v6 V/ }A. 前序遍历
$ K9 O6 |  ?3 H* QB. 中序遍历
C. 后序遍历
+ p5 C8 B' I# l+ e' f+ V' J: U9 |D. 层次遍历
      满分：3  分
11.  已知一个顺序存储的线性表，设每个结点占c个单元，若第一个结点的地址为LOC(a0)，则第i个结点的地址为 ( )。
A. LOC(a0)+(i-1)*c
0 @. o  @; z7 y# zB. LOC(a0)+i*c
. a% K4 H' E& w- f8 T7 q- O8 V. a* }4 ZC. LOC(a0)-i*c
D. LOC(a0)+(i+1)*c
0 p( r* s3 e5 c2 h* p      满分：3  分
12.  在k叉树中，结点度数的最大值为 ( )。
A. k-1
9 V1 i: c- v( QB. k
  H4 D  D) C" M/ K2 I6 A9 D. zC. k+1
. m1 p2 }- ~) F! ZD. k*n
      满分：3  分
# K$ S3 d, n/ g) u13.  顺序存储结构的优点是( )。
8 A( L6 |8 i7 \8 t* c$ WA. 存储密度大
1 X; R) H; ^5 \8 C3 s9 zB. 插入运算方便
C. 删除运算方便
D. 结构可动态变化
4 o( C" X# z8 W% m$ c; V      满分：3  分
; J( Q' q: @, p7 z+ c14.  下列序列中，() 是执行第一趟按递减序快速排序后所得的序列。
A. [ 68, 11 , 18 , 69 ] 70 [ 23 , 93 , 73]
" H- \3 o' ]9 N8 e3 f3 n! o- M! s# J3 R$ LB. [ 68 , 11 , 69 , 23 ] 70 [18, 93, 73 ]
4 v& ^$ `0 U) z1 Y% MC. [ 93, 73 ] 70 [ 68, 11, 69, 23, 18 ]
D. [ 68 , 11 , 69, 23, 18 ] 70 [ 93, 73 ]
, s/ c1 R; S* m" j. Q      满分：3  分
15.  用ISAM组织文件适合于 ()。
A. 磁带
B. 磁盘
C. 光盘
7 X. G. j( j0 \6 K  |& T+ RD. 外存储器
      满分：3  分
4 |. Z: x% B1 H  b* C1 L8 y& p16.  下列哪项不是利用查找表中数据元素的关系进行查找的方法 ()。
3 \# }5 }: g8 _# B1 o# aA. 有序表的查找
B. 二叉排序树的查找
2 {. d. `9 d- nC. AVL树
8 y& s4 t; F3 K1 V0 n! wD. 散列查找
      满分：3  分
17.  在数据结构中，从逻辑上可以把数据结构分成 ( )。
A. 动态结构和静态结构
B. 紧凑结构和非紧凑结构
C. 线性结构和非线性结构
* y5 u' F- Z/ @) \7 [0 g' J" zD. 内部结构和外部结构
      满分：3  分
8 c; y8 I. U1 V* \5 f9 Y. t" J18.  若对n阶对称矩阵A按行优先顺序将其下三角形的元素（包括主对角线上的所有元素）依次存放于一维数组B [1..n(n+1)/2 ] 中，则在B中确定aij ( i < j）的位置k的关系为 () 。
: l8 z/ U  c8 l4 F; _1 {- EA. i*(i-1)/2+j
B. j*(j-1)/2+i
. Y7 d* [" d8 O! [8 _C. i*(i+1)/2+j
/ {8 w% [" `9 @' M0 AD. j*(j+1)/2+i
      满分：3  分
19.  由3个结点可以构造出多少种不同的有向无序树？( )
A. 9
B. 10
C. 11
5 ]8 k$ w6 `; e+ E. q2 {& K6 {D. 12
      满分：3  分
20.  设F是一个森林， B是由F变换得到的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有 ( ) 个。
7 S' A" O1 y& p8 k7 qA. n-1
B. n
C. n +1
, w! F, `+ Y( ^: c* t$ i! pD. n+2
& i( @1 k. x- T' N3 t3 b' \: M( n      满分：3  分

7 G' [* [( \' u) }( {, i二、判断题（共 20 道试题，共 40 分。）V 1.  对n个记录的文件进行堆排序，最坏情况下的执行时间是O(nlog2n )。
A. 错误
2 \/ c9 T5 K7 t1 k7 a7 [( W( SB. 正确
; K- v' T+ i3 `- k/ V      满分：2  分
2.  链接存储结构属静态存储方式。
A. 错误
B. 正确
      满分：2  分
3.  强连通分量是无向图的极大强连通子图。
; O# W4 T1 J  w2 K' H% k# ^A. 错误
/ @2 X* j4 _% ?) y6 z# ?- z% jB. 正确
      满分：2  分
4.  哈夫曼树是带权 ( 外部 ) 路径长度最短的树，路径上权值较大的结点离根较近。
  K: \6 w/ C% e& C' AA. 错误
B. 正确
      满分：2  分
& j$ W( B" ^/ u8 _2 j6 s7 k* b, V5.  用链表 ( lchild-rchild表示法 ) 存储的包含n个结点的二叉树，结点的2n个指针域中有n + l 个空指针。
A. 错误
B. 正确
      满分：2  分
8 V' J' j- F. k6.  快速排序的速度在所有排序方法中最快，而且所需附加空间也最少。
A. 错误
B. 正确
      满分：2  分
' J7 x2 r9 x: B% K- Y7.  链表中的表头指针与表头结点起到相同的作用。
A. 错误
B. 正确
% R, j" u2 [. v- a" J* c' l      满分：2  分
8.  无向图的邻接矩阵可用一维数组存储。
- E& u6 e, P  H* |8 c1 U$ L3 s1 tA. 错误
1 b5 o) G; a( h) v1 f( pB. 正确
1 y! F8 T, F( Z" W      满分：2  分
9.  当待排序记录已经从小到大排序或从大到小有序时，快速排序的执行时间最省。
- d3 {/ Q3 I2 J. E! c- F  jA. 错误
B. 正确
6 {) o1 l- i& I! e1 c5 u# j% i( c! h      满分：2  分
10.  需要借助于一个队列来实现DFS算法。
A. 错误
B. 正确
- K; b1 ^5 e: w# P, ~" w! s      满分：2  分
11.  一棵树中的叶子数一定等于与其对应的二叉树的叶子数。
A. 错误
8 j7 t6 E( o; E; D# X% h: uB. 正确
      满分：2  分
+ s1 O9 \# H% v8 `/ K7 f12.  非空的二叉树一定满足：某结点若有左子女，则其中序前驱一定没有右子女。
A. 错误
B. 正确
8 z& E8 H  U8 H7 A9 W6 I- b; B      满分：2  分
13.  堆排序是稳定的排序方法。
A. 错误
B. 正确
( ?- F' }/ N4 M8 E& I' [: q% ?" x5 w& C      满分：2  分
14.  数据结构的运算(操作)是定义在数据的逻辑结构之上的。
: ?! \0 a' B& ^: S9 B7 J- x" _5 ^A. 错误
B. 正确
) E; @% B+ a. a7 n      满分：2  分
15.  存放在磁盘、磁带上的文件，既可以是顺序文件，也可以是索引结构或其他结构类型的文件。
3 m  Q/ s0 w' b" ~- O; ?3 WA. 错误
B. 正确
      满分：2  分
16.  广义表的取表尾运算，其结果通常是一个表，但有时也可是一个单元素值。
A. 错误
B. 正确
      满分：2  分
5 m" V1 g9 n. R17.  堆是完全二叉树。
5 N" e5 }0 g1 x% F( EA. 错误
+ ?/ D% P6 R, c2 S) E/ o2 s9 A2 WB. 正确
      满分：2  分
18.  数据对象是具有相同性质的数据元素的集合。
A. 错误
/ [2 t$ ]6 h3 E7 A; FB. 正确
! r4 P/ w6 |9 F; A      满分：2  分
19.  在执行某个排序算法过程中，出现了排序码朝着它最终排序位置相反的方向移动，则该算法是不稳定的。
A. 错误
; {8 [+ K+ p  g- y+ g4 f: EB. 正确
      满分：2  分
/ Z; w, t7 }4 O* y20.  哈希函数越复杂越好，因为这样随机性好，冲突概率小。
A. 错误
: z+ E+ a  x- E( Y5 _# gB. 正确
. ?5 a- I& ~( e8 J- O      满分：2  分

% q+ f  P5 r  H& |! H$ g; m+ t谋学网(www.mouxue.com)是国内最专业的奥鹏作业资料，奥鹏离线作业资料及奥鹏毕业论文辅导型网站，主要提供奥鹏中医大、大工、东财、北语、北航、川大、南开等奥鹏作业资料辅导，致力打造中国最专业的远程教育辅导社区。