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

奥鹏在线作业

福师《数据结构概论》在线作业一
2 ^( R+ V7 a1 P9 T8 t$ l
" E# q3 m" e1 m6 e6 t- s
1 c7 W; ^6 l3 C+ I( }
( F' \$ `! c; j) o) a1 s
一、单选题（共 25 道试题，共 50 分。）

1.  下列排序算法中，（ ）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。
. 堆排序
. 冒泡排序
! ?# U- h; I- W2 X5 c! }0 E/ A+ ~. 快速排序
7 Z/ C7 {# Q, |8 B6 j. 插入排序
正确资料：
- B9 R; K! `) i# o$ D2.  以下数据结构中，（ ）是非线性数据结构
. 树
. 字符串
* v/ ?0 A; x# D1 ?7 I( O* U9 I. 队
. 栈
正确资料：
3.  线性表（ 1,2,…,n）以链接方式存储时，访问第i位置元素的时间复杂性为（ ）
. O（i）
5 ^9 |- y* x2 k" n$ K. O（1）
. O（n）
. y3 P1 B- c2 D" d% ]. O（i-1）
& K  w, Q) G$ M  D# L* w' [6 E正确资料：
4.  设给定权值总数有n 个，其哈夫曼树的结点总数为（ ）
' y6 w; ^) F3 y. 不确定
. 2n
. 2n+1
. 2n-1
正确资料：
5.  从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（ ）排序法。
, ~: u, c" X2 E4 s. _. 插入
( {. B$ f2 R* O% e; U. 选择
7 D$ k9 x) X# Z) t  [2 H- U/ s) i. 希尔
. 二路归并
正确资料：
, A5 T, Y6 l4 K6.  就平均性能而言，目前最好的内排序方法是( )排序法。
7 T- p; Z: K" a7 |+ U/ p* Z8 `* ?. 冒泡
9 O3 Z* {, [1 o% e2 G; \. 希尔插入
! n) |. S( \) \- p" e* Z8 h. 交换
. 快速
1 Z1 \" @; N  O1 j8 d( ~3 U正确资料：
7.  对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（ ）。
( `9 J9 }7 V6 V, Y6 F+ ^& D9 H2 T6 Y. (2,5,12,16)26(60,32,72)
$ ]9 g, t; f) B, Z. ]. (5,16,2,12)28(60,32,72)
. (2,16,12,5)28(60,32,72)
. (5,16,2,12)28(32,60,72)
正确资料：
* B- i+ ?2 w; c7 v* E% V8.  适用于折半查找的表的存储方式及元素排列要求为( )
. 链接方式存储，元素无序
. 链接方式存储，元素有序
. 顺序方式存储，元素无序
. 顺序方式存储，元素有序
1 Z/ w+ I2 Z  Q5 {1 B3 p正确资料：
0 ]5 a( Q: p& \/ P9.  线索二叉树是一种（ ）构。
. 逻辑
. 逻辑和存储
* T$ a- t8 Z6 S2 \$ x. L0 F+ j$ q. 物理
. 线性
正确资料：
10.  对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ ）。
6 o' M' F8 s! G& [* u. O(n) O(n)
7 t! W( P- s& h% K. z# l. O(n) O(1)
6 S- c1 ?& l4 u. X. O(1) O(n)
. ?/ x3 O" D, h( Q- l3 B/ ]2 A. O(1) O(1)
& E% C7 n1 x. I6 `! K正确资料：
11.  若串S=’softwr’,其子串的数目是（ ）
% u( O3 E8 [( ?7 E3 _8 y# y. 8
8 m9 h; q5 u- d8 d, X* B& h. 37
  _  B' V8 f$ g7 Y8 ~1 a3 L. x3 Z. 36
' ^$ [. w* }/ q  V; O; f; n. 9
8 @5 c* R/ D: t& C正确资料：
3 B' g6 M* G& E  s* h1 y+ d6 f# X12.  要连通具有n个顶点的有向图，至少需要（ ）条边。
. n-l
5 @$ H) r6 u( h0 g; H8 ^4 w! d. n
. n+l
7 x( P0 p2 ]2 a6 E9 z. 2n
+ c# ]: e% u% ~0 E正确资料：
! M: [. y+ d* w) X+ t2 k3 A( b13.  已知串S=‘’,其Nxt数组值为（ ）
. 0123
( U  [) v+ p2 L4 X+ ]/ r1 s4 }. 1123
5 _9 h1 L5 G6 W: G5 W' k- d& X" b" k. 1231
8 s( ^  v0 o8 u: _  X7 o' p& n5 m' x. 1211
0 K, j! f/ e1 P! E3 R. W正确资料：
; H' k. c( }4 _6 b14.  在下面的程序段中，对x的赋值语句的频度为（ ）FOR i:=1 TO n OFOR j:=1 TO n O x:=x+1;
4 [, ?7 G# x' ?  j4 E. O(2n)
. O(n)
. O(n2)
# P. Z" A+ }8 s1 q0 E- i" d. O(log2n)
+ K3 X6 m8 k, `4 T9 ^: T正确资料：
15.  设森林F对应的二叉树为，它有m个结点，的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（ ）
5 ~/ g/ L' \) h5 d7 m8 g. m-n
. m-n-1
7 D3 s" n, G. k; S4 r2 d. n+1
. 条件不足，无法确定
正确资料：
; r. k) n+ O# I* Q9 t16.  线索二叉树是一种（ ）结构。
. 逻辑
" ]- ?# P; z4 j. 逻辑和存储
. 物理
( k' `. ^  m( e7 R6 w' J. W7 f0 O- G' G. 线性
正确资料：
17.  串的长度是指（ ）
. 串中所含不同字母的个数
' }1 y) b9 ?, r. D, R" i. 串中所含字符的个数
. 串中所含不同字符的个数
. 串中所含非空格字符的个数
" o& }1 O! P" v9 |正确资料：
# l- m# Q, R6 l18.  已知广义表L=（（x,y,z），，（u，t，w）），从L表中取出原子项t的运算是（ ）
. h（til（til（L）））
. til（h（h（til（L））））
. h（til（h（til（L））））
- Z. G) f$ {& z  h$ S  _. h（til(h（til（til（L）））)）
: J! ?  Z3 o& C- [) C( ?$ A7 N" ~# ~# Q正确资料：
19.  一个递归算法必须包括（ ）
. 递归部分
. 终止条件和递归部分
. 迭代部分
. 终止条件和迭代部分
正确资料：
, R5 K+ ?' M, ]6 ?1 T2 H# D6 ]: _20.  若串S=’softwr’,其子串的数目是（ ）。
. 8
. 37
. 36
. 9
正确资料：
5 `# ~2 a9 [6 H6 t1 w21.  对稀疏矩阵进行压缩存储目的是（ ）。
. K0 |5 h/ }9 M0 \& ^( ~. 便于进行矩阵运算
& W. v5 D" W8 t" O. 便于输入和输出
. 节省存储空间
. 降低运算的时间复杂度
3 W; B4 n, \) g, k! [* W7 T正确资料：
22.  下列排序算法中，占用辅助空间最多的是：( )
! M5 W3 n: z  k4 t, a9 x. 归并排序
; h# i" n8 w8 s& G  P. 快速排序
( \. {7 M7 k. N5 J' \. 希尔排序
# U1 k5 U7 u$ L. 堆排序
正确资料：
( k* Y5 k) n. x% K$ S. @) U5 d: U) n23.  由3 个结点可以构造出多少种不同的二叉树（ ）
9 r' d3 n" L6 t4 \& _# H+ z/ g- ^4 ^. 2
2 o/ u) d! k0 a8 }/ o# ]$ O. 3
4 r2 I7 G5 P# `8 o4 G: ~8 {. 4
. 5
& n, J# n7 B. R1 D正确资料：
  ^, P& m  S3 s! G24.  输入序列为，可以变为时，经过的栈操作为（ ）
6 X0 C& U6 B. R1 ^: ?. push,pop,push,pop,push,pop
. push,push,push,pop,pop,pop
. push,push,pop,pop,push,pop
1 s, w$ |0 H/ ]1 _+ F! Y. push,pop,push,push,pop,pop
正确资料：
% B0 ^! ?: W" U* x0 t% Q2 p) s25.  若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度（ ）(1<=i<=n+1)。
. O(0)
. O(1)
. O(n)
4 |3 D' {% \: G8 |% j7 s& m4 \. O(n2)
4 o& K' L; \& b正确资料：
/ |) e" V* N- @

  u5 ~" F) G! `5 m0 T+ E
$ H; A* k" a/ _福师《数据结构概论》在线作业一

7 A* H) J, C7 y: |8 y; L3 F

1 C* W- N3 a3 Z. z3 z
二、判断题（共 20 道试题，共 40 分。）
4 V. o8 l3 o' ~6 {/ n
1.  广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值（ ）
+ b3 D& [$ _3 ], G; H# s9 Z0 M, V. 错误
. 正确
/ r, N. A% s* \& Q' J) Y正确资料：
2.  用树的前序遍历和中序遍历可以导出树的后序遍历（ ）
$ f& z$ q) J) |' ~7 a" u. 错误
, c& m% x% v( s' D& f9 k* E( l9 r6 l. {' y. 正确
4 T0 m; X4 z  |  H/ Q3 a  j: Q- F正确资料：
. W( ?$ f  N9 F# \+ c" s3.  队列和栈都是运算受限的线性表，只允许在表的两端进行运算（ ）。
. 错误
. 正确
正确资料：
# ^/ h# A2 e' k3 m1 l4.  顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好（ ）
4 p! W9 v5 f6 ^2 C- p. 错误
1 o3 f/ A" R2 l9 r6 w. 正确
4 y. ^" h; j8 y! S正确资料：
+ f8 D  h3 B; X! y- `- c; i* M8 ^+ M5.  任一查找树(二叉分类树)的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间.
. 错误
; Z5 `- z! L) x8 F0 G: C) Q. 正确
正确资料：
6.  数据元素是数据的最小单位。
4 m8 C( o& d: e8 r7 l. 错误
$ Z" E/ U! F' W, b6 b& L. 正确
正确资料：
7 Z, F) s; W% D$ Q4 v- o0 f2 S7.  数据结构的抽象操作的定义与具体实现有关。
7 l+ s/ d) S: I. p, F. 错误
1 @+ [$ a8 G) D$ [) H. g. 正确
正确资料：
8.  广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表（ ）
. 错误
. 正确
正确资料：
9.  线性表只能用顺序存储结构实现（ ）
1 F' L# l3 M1 u: @3 r. 错误
6 @% K; F$ S' O( s1 p4 o* o. 正确
4 n( ~: k+ @  e1 {2 C( F正确资料：
& ~: V& D1 E% _10.  在顺序存储结构中，有时也存储数据结构中元素之间的关系（ ）
& c; v1 a) l: A6 I, U4 k. 错误
. z" n6 q* |2 m6 L' J. 正确
正确资料：
11.  循环队列通常用指针来实现队列的头尾相接。
5 Y1 A. X. S9 }1 e" v) e$ N. 错误
. 正确
正确资料：
12.  二叉树是度为2的有序树
$ K5 k+ ]. m3 }3 ~* R: Z* {. 错误
. 正确
正确资料：
8 g3 S3 `: ]5 s$ [13.  在查找树（二叉树排序树）中插入一个新结点，总是插入到叶结点下面（ ）
. 错误
( e- r' h% v% W4 S. 正确
正确资料：
14.  队列逻辑上是一个下端和上端既能增加又能减少的线性表。
. 错误
% X! ^( Y, @( e- @. 正确
正确资料：
( C# L- {6 q- v/ C. {15.  链表中的头结点仅起到标识的作用（ ）
# F5 L/ Q. I: U% M3 T& l. 错误
; d: {, Z3 w0 @$ y) R. 正确
. C4 r( S3 R5 E$ t) v' u正确资料：
16.  栈和队列都是限制存取点的线性结构（ ）
. 错误
. 正确
9 `. s/ ~; D! x3 p: @正确资料：
17.  链表中的头结点仅起到标识的作用。
. 错误
7 I+ }  y! X$ t1 N5 ^4 t. 正确
正确资料：
18.  二叉树以后序遍历序列与前序遍历序列反映的同样的信息(他们反映的信息不独立）（ ）
. 错误
. 正确
正确资料：
, K. P! d+ A& A4 x19.  对一棵二叉树进行层次遍历时，应借助于一个栈
5 D, U2 Z6 ~6 ~4 O8 {. 错误
; \0 y# l1 R. ]% B3 i6 R: h. 正确
正确资料：
20.  广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。
% a& [# d1 |. S2 t4 v. 错误
. 正确
( B0 r7 j: S5 }正确资料：
! E, ~' R/ g1 |' y


福师《数据结构概论》在线作业一

$ f, h! w0 G* K$ J' C


三、多选题（共 5 道试题，共 10 分。）

1.  以下数据结构中，哪些不是线性结构（ ）
* O" f; M7 r& H3 X; c) q7 G. 广义表
. 二叉树
  I3 D- Y$ h/ K& m. 稀疏矩阵
. 串
% C# B0 w/ d2 n; N9 {1 ?& Q6 ?( T. W正确资料：
2.  下列说法正确的是（ ）
2 y' P! A* k  X. 图的遍历是从给定的源点出发每一个顶点仅被访问一次
. 图的深度遍历不适用于有向图
. 遍历的基本算法有两种：深度遍历和广度遍历
* n& X2 c9 j! @% V+ a- E4 T, V" F+ b. 图的深度遍历是一个递归过程
0 U2 i: @8 p6 f- Q9 Q% n* _正确资料：
3.  下面几个符号串编码集合中，是前缀编码的是（ ）
0 z1 E3 k$ p, d: r+ m. {0,10,110,1111}
. {11,10,001,101,0001}
7 W7 F! Z0 Y+ O. {00,010,0110,1000}
. {,,,,,,}
  Q1 I" r( V1 A正确资料：
% b4 W- t; K. T& @% X6 h4.  下列哪种图的邻接矩阵不是对称矩阵？（ ）
. 有向图
* k9 k, ~* _$ q# y. 无向图
. OV网
. O网
! c; N. m( i$ G+ t: t6 X正确资料：
# e8 ~  `! f# I# o# r8 B" c5.  下面几个符号串编码集合中，是前缀编码的是（ ）
. {0,10,110,1111}
. {11,10,001,101,0001}
. {00,010,0110,1000}
. {,,,,,,}
正确资料：
1 E: X" [5 p- t) Q9 n

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

lnwbx

不错，OK ，满分！