14秋福师《数据结构概论》在线作业资料二辅导资料

谋学网

谋学网(www.mouxue.com)是国内最专业的奥鹏作业资料，奥鹏离线作业资料及奥鹏毕业论文辅导型网站，主要提供奥鹏中医大、大工、东财、北语、北航、川大、南开等奥鹏作业资料辅导，致力打造中国最专业的远程教育辅导社区。
4 e- Q) M( K+ R2 c! T
一、单选题（共 25 道试题，共 50 分。）V 1.  设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ ）
0 K& Y! H6 J5 c6 J+ p" DA. 5
B. 6
; n7 _2 Y8 I( c' e1 A7 Z! K" [C. 7
3 g# g8 d/ b  E0 t7 _D. 8
9 T, O, q) S# B1 t( h      满分：2  分
2.  算法的计算量的大小称为计算的（ ）。
A. 效率
. A# ^9 \1 d5 w+ o+ V% w1 X3 cB. 复杂性
# x2 d$ v' o, I7 D4 n$ OC. 现实性
9 Q  D  ?! \$ q4 l7 qD. 难度
      满分：2  分
4 T/ A, U4 A, n' W' d% n7 `8 ~2 V3.  有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ ）
) y/ `( g. L& ~( [3 PA. 5 4 3 6 1 2
0 u  G6 @" Y  i$ _9 U" p1 ?) ~6 NB. 4 5 3 1 2 6
C. 3 4 6 5 2 1
D. 2 3 4 1 5 6
      满分：2  分
7 x: C; C( W3 C5 w4.  对稀疏矩阵进行压缩存储目的是（ ）。
: y( ?" f. N/ ]+ h6 J: T' QA. 便于进行矩阵运算
B. 便于输入和输出
C. 节省存储空间
! v5 o9 x( x( D! z2 o! v8 ~D. 降低运算的时间复杂度
      满分：2  分
# X# R1 h4 F" Z5.  就平均性能而言，目前最好的内部排序方法是（ ）排序法。
- T+ ~4 A, l9 }: f1 L' xA. 冒泡
" z! n7 E5 F7 L, X3 `B. 希尔插入
# J% T- K0 t% YC. 交换
D. 快速
, `0 s* h0 }+ F, w6 Q7 v+ O( V8 B& J      满分：2  分
8 u! q) u2 ^1 c6.  对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ ）
6 |! q5 x. r0 {) K, l! {' K6 lA. head==NULL
B. head→next==NULL
C. head→next==head
; D3 k9 t) w8 MD. head!=NULL
4 C. _$ v* W/ K( ]      满分：2  分
# l1 S' z, Y9 [! l% ?+ y6 ^% g+ D7.  树的后根遍历序列等同于该树对应的二叉树的（ ）
9 C: F9 b1 e/ f2 VA. 先序序列
$ C0 d9 ]4 n1 l- _+ Y" w1 p! jB. 中序序列
$ q/ Y  |2 Q+ u2 ?0 X1 A4 MC. 后序序列
" w4 i/ g# S8 v, B, E9 N; HD. 都不正确
      满分：2  分
8.  具有10个叶结点的二叉树中有（ ）个度为2的结点，
. s0 H) y3 [2 [, q1 v3 E9 Y7 S/ KA. 8
7 d7 v+ G, \+ _3 W7 EB. 9
+ I- y- L" P6 T7 b6 h6 B6 N1 kC. 10
D. ll
( }, e# f; r: g      满分：2  分
5 `. f/ V5 P$ D# a7 ]6 S) I& j9.  算法的时间复杂度取决于（ ）
A. 问题的规模
9 j' Z$ ]. J7 ?, i' c/ k1 Y: HB. 待处理数据的初态
: v( Q$ W1 a7 {" s, R. w) AC. A和B
5 R1 U: B) E5 L* _) G+ g0 j3 tD. 变量个数
      满分：2  分
10.  对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1，8，20，7，15}；则采用的是（ ）排序。
0 Q5 E8 K9 Y0 s# A+ nA. 选择
" x. ]8 H; ^3 c# k) d  h( VB. 快速
C. 希尔
D. 冒泡
9 N( I0 ~# @7 a3 K$ F      满分：2  分
+ O: @& u/ O) Z% f+ G0 _, w8 i11.  设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ ）
# Y/ a( O! B: gA. 求子串
" i: q7 \4 J3 A" F4 y7 U0 e2 dB. 联接
C. 匹配
7 M  k% @" s; H% _D. 求串长
      满分：2  分
12.  散列函数有一个共同的性质，即函数值应当以( )取其值域的每个值。
% ~9 _- f) u9 {3 c2 [1 F8 TA. 最大概率
5 Q. D& r) a8 ~! {, z/ OB. 最小概率
* O8 j6 c6 r) x# i/ [# k! s4 {C. 平均概率
D. 同等概率
$ O$ \+ A, O$ A1 h" W  P      满分：2  分
- s% ?2 M: W; B3 v; r! Y8 X13.  对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( )
A. （N+1）/2
! k( T$ [' R4 r: tB. N/2
C. N
D. [（1+N）*N ]/2
9 ?9 N- V/ m  A% Q5 L      满分：2  分
14.  在下面的排序方法中，辅助空间为O（n）的是( )
) `& m# b5 L6 r  t* dA. 希尔排序
B. 堆排序
6 @! n8 ]; N  `3 iC. 选择排序
D. 归并排序
% t9 \) }; k& t' O$ @7 R  B      满分：2  分
15.  连续存储设计时，存储单元的地址（ ）。
: a2 O4 G% u% a4 M' bA. 一定连续
B. 一定不连续
( m1 ~! ?: i% sC. 不一定连续
( M! O6 E0 s+ L# w9 MD. 部分连续，部分不连续
- o: C1 I: x+ I: {      满分：2  分
% l7 T4 _3 E' J1 S/ d16.  下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是（ ）
A. 选择排序法
3 r) G0 t, F: f% z- o- J4 g2 FB. 插入排序法
C. 快速排序法
; V; a/ D+ _. B/ uD. 堆积排序法
( V1 _1 o9 G6 ?1 F5 M0 x$ o. B      满分：2  分
/ C, r9 L4 w( G1 b17.  对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1，8，20，7，15}；则采用的是（ ）排序。
A. 选择
B. 快速
C. 希尔
D. 冒泡
6 ?' o# W1 Z$ d. i  i3 |2 r      满分：2  分
8 H- n0 L% K; Z) E& o& e1 }* ?' F8 y4 |18.  假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（ ）
A. 808
B. 818
C. 1010
D. 1020
6 ]5 z3 i/ Z6 \) i$ D3 B8 O      满分：2  分
1 W4 ~7 Q- U! k19.  在完全二叉树中，若一个结点是叶结点，则它没（ ）
" z4 C6 w) V+ G: q& a" eA. 左子结点
B. 右子结点
C. 左子结点和右子结点
D. 左子结点，右子结点和兄弟结点
      满分：2  分
6 I2 B2 d. H4 t3 k( A% D3 w20.  设广义表L=（（a,b,c）），则L的长度和深度分别为（ ）。
: h1 a7 C" j) F2 {( H2 G- ^# hA. 1和1
& U! R% V  r" [; ~/ V+ B) L4 WB. 1和3
C. 1和2
D. 2和3
      满分：2  分
21.  设广义表L=（（a,b,c）），则L的长度和深度分别为（ ）
4 k3 m& b8 q  FA. 1和1
* Q1 V' P; E- C: e+ GB. 1和3
C. 1和2
D. 2和3
3 U- ^. O( ]# d7 p      满分：2  分
22.  对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（ ）
A. (2,5,12,16)26(60,32,72)
3 u9 z, M7 ?0 r9 C! j2 l1 mB. (5,16,2,12)28(60,32,72)
' p4 E  S2 Q$ a$ g/ u6 hC. (2,16,12,5)28(60,32,72)
D. (5,16,2,12)28(32,60,72)
3 V3 ?. Z5 G  x      满分：2  分
23.  有n个叶子的哈夫曼树的结点总数为（ ）
A. 不确定
B. 2n
C. 2n+1
D. 2n-1
      满分：2  分
24.  在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（ ）
' o! ^/ }- `: w) G" _A. p->next=s;s->next=p->next;
- ^0 W9 W% |4 t& V2 X. ?1 jB. s->next=p->next;p->next=s;
! D, u' ], z2 \& p7 f+ C" [! tC. p->next=s;p->next=s->next;
; T8 q3 B5 V1 ?4 _D. p->next=s->next;p->next=s;
# d2 |! [0 G9 u" h7 N8 l      满分：2  分
' b$ D1 Z3 F5 y/ j, ]25.  在下面的排序方法中，辅助空间为O（n）的是（ ）
A. 希尔排序
B. 堆排序
C. 选择排序
D. 归并排序
      满分：2  分

二、判断题（共 20 道试题，共 40 分。）V 1.  在伙伴系统中的伙伴是指任意两块大小相同、位置相邻的内存块。
A. 错误
) q" @/ i0 L, l* m9 F1 A9 yB. 正确
  H& {# r# k+ g, T  K      满分：2  分
2.  两分法插入排序所需比较次数与待排序记录的初始排列状态相关。
A. 错误
8 b! E6 s; k! iB. 正确
      满分：2  分
3.  二叉树的遍历结果不是唯一的（ ）
A. 错误
  t, e: a. B( v/ R3 R/ NB. 正确
      满分：2  分
4.  消除递归不一定需要使用栈，此说法（ ）
$ c# z, {! M( m9 y4 MA. 错误
B. 正确
      满分：2  分
6 E; f5 b  b6 C' |/ i0 z- M5.  二维以上的数组其实是一种特殊的广义表（ ）
+ o5 B- E4 S6 P4 l  LA. 错误
4 H& i  A. f, c9 e) H: f9 DB. 正确
      满分：2  分
6.  排序算法中的比较次数与初始元素序列的排列无关。
6 n  d8 K1 e9 s1 xA. 错误
B. 正确
) y9 i* ^8 j8 t      满分：2  分
4 r- X4 u+ d& h7.  二叉树以后序遍历序列与前序遍历序列反映的同样的信息(他们反映的信息不独立）。
/ s8 x: a& {% K5 |1 z: k7 v" GA. 错误
B. 正确
      满分：2  分
/ o: w. c; A+ k( k+ M9 e8.  当待排序的元素很多时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素（ ）
, c! c! {; ^( V1 d! e& b( pA. 错误
4 }: B9 U$ E- B, h% \* s/ ]B. 正确
      满分：2  分
  t# \7 U" a  i# o9.  通常使用队列来处理函数或过程的调用。
+ `2 n/ R' B' P6 _+ T3 p5 mA. 错误
: [9 N: G! y. }# R& U5 AB. 正确
      满分：2  分
6 @0 R9 ~8 N4 r6 h10.  对任何数据结构链式存储结构一定优于顺序存储结构（ ）。
A. 错误
B. 正确
      满分：2  分
11.  在查找树（二叉树排序树）中插入一个新结点，总是插入到叶结点下面。
& W: n: W0 I$ }7 N# d" wA. 错误
8 j3 U4 C& r. H  h& }B. 正确
! I- N/ I$ w; c      满分：2  分
12.  在待排数据基本有序的情况下，快速排序效果最好（ ）
A. 错误
B. 正确
      满分：2  分
& k4 h' Q) r) M3 f' d- l) e+ ?13.  二维以上的数组其实是一种特殊的广义表。
A. 错误
' H6 ~5 i% r0 c9 b0 z$ Q$ e  NB. 正确
8 z1 a$ D: I  C      满分：2  分
14.  算法的优劣与算法描述语言无关，但与所用计算机有关。
+ \8 v' }3 r: ^  aA. 错误
B. 正确
0 J6 w, M, }" r3 K* o) D      满分：2  分
15.  栈和队列都是限制存取点的线性结构。
A. 错误
7 C" a1 `! S. K1 A/ K2 w, {7 W2 _6 jB. 正确
      满分：2  分
16.  队列逻辑上是一个下端和上端既能增加又能减少的线性表（ ）。
- ^  g  ?! t1 uA. 错误
; P0 \0 o0 V% Z, x6 Y: l3 jB. 正确
! k6 Z/ s) Y8 N' L/ N" [1 S      满分：2  分
" g# ?. T8 U) j8 q. e8 E/ b7 Y17.  在查找树（二叉树排序树）中插入一个新结点，总是插入到叶结点下面（ ）
A. 错误
B. 正确
/ O# ?) q, M+ |, c# i9 |6 X      满分：2  分
18.  排序算法中的比较次数与初始元素序列的排列无关（ ）
A. 错误
8 o3 N$ x0 ?! k) W/ pB. 正确
# z! _$ y9 i% X. |( ]  Q      满分：2  分
19.  折半查找法的查找速度一定比顺序查找法快
. `' S' h' i% u9 m( X4 h) S1 ~A. 错误
B. 正确
      满分：2  分
3 }5 x% @0 v/ ]. `1 i; H4 d20.  在动态存储管理系统中做空间分配时，最佳适配法与最先适配法相比，前者容易增加闲置空间的碎片
$ I2 J) u2 J$ f  C2 yA. 错误
B. 正确
      满分：2  分
0 w% M% `; R) u7 h5 z0 g
0 P' X& I0 S5 D; V2 k! R: w三、多选题（共 5 道试题，共 10 分。）V 1.  有关二叉树下列说法不正确的是（ ）
' T/ Z( {+ F# q3 [' _, q1 sA. 二叉树的度为2
  p( d. j; }( O2 mB. 一棵二叉树的度可以小于2
1 K1 o/ m  X# i% Z3 V) IC. 二叉树中至少有一个结点的度为2
D. 二叉树中任何一个结点的度都为2
. b  X+ l/ u4 u" l# x/ V! B) l/ a# R      满分：2  分
2.  下述哪些不是顺序存储结构的优点（ ）
: y0 a6 [: C4 A# Y5 R- KA. 存储密度大
; A4 @3 G- |4 y9 FB. 插入运算方便
, @: D, [6 ~9 A* q! B: PC. 删除运算方便
D. 可方便地用于各种逻辑结构的存储表示
      满分：2  分
& e" r9 e+ z8 h: K' H1 j7 X. i& h3.  下面关于哈希(Hash)查找的说法不正确的是( )
; r" x' m& {6 Q7 c- F4 JA. 哈希函数构造的越复杂越好，因为这样随机性好，冲突小
B. 除留余数法是所有哈希函数中最好的
3 F2 }: z9 l, l' t3 p; U/ OC. 不存在特别好与坏的哈希函数，要视情况而定
D. 若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可
      满分：2  分
4.  下面关于求关键路径的说法正确的是（ ）
6 l$ _& \4 U( ^8 p/ LA. 求关键路径是以拓扑排序为基础的
B. ．一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同
C. 一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差
( A; d* S3 t: |  s9 |# f2 ~D. 关键活动一定位于关键路径上
      满分：2  分
5.  下面关于串的的叙述中，正确的是？（ ）
2 Y3 n  r9 a2 q* }! c  M* A! j% ~A. 串是字符的有限序列
  z* u( u. z2 }; K9 mB. 空串是由空格构成的串
5 g& l/ m2 o# f2 d( n& Z- FC. 模式匹配是串的一种重要运算
0 A1 [; B$ V- p5 d$ c% s0 ?4 ND. 串既可以采用顺序存储，也可以采用链式存储
      满分：2  分

3 D0 N# B: |- H$ m6 {( m% k% `谋学网(www.mouxue.com)是国内最专业的奥鹏作业资料，奥鹏离线作业资料及奥鹏毕业论文辅导型网站，主要提供奥鹏中医大、大工、东财、北语、北航、川大、南开等奥鹏作业资料辅导，致力打造中国最专业的远程教育辅导社区。