大工15春《数据结构》在线作业1
: w* P2 e! y6 p% a! ~ F8 n$ m3 I6 J
一、单选题：3 j6 O) }9 L% A: q. Z; f
1.一个顺序栈S，元素a，b，c，d，e依次进栈，如果5个元素的出栈顺序为b，e，d，c，a，则顺序栈的容量至少应为( )。 (满分:5)
A. 2
B. 3, }1 |0 E" y. J/ y* W9 t
C. 4
D. 55 _* o6 G) t! w' q
2.对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是( )。 (满分:5)
A. head==NULL
B. head→next==NULL3 g% `" `: h5 W$ /
C. head→next==head
D. head!=NULL
3.最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是 ( )。 (满分:5)3 n3 Y- m# @( v1 h
A.(rear+1) MOD n=front
B. rear=front
C. rear+1=front
D.(rear-l) MOD n=front
4.广义表((e))的表头是( )。 (满分:5)
A. e
B.(e)( R$ {# ^. q( C5 i w6 n( p& e" X
C.( )
D.(( ))/ F. o% V% F4 Q0 b# d& d
5.在一个单链表中，删除*p结点之后的一个结点的操作是( )。 (满分:5)& J; F( J; D: o' `- s
A. p-next=p;/ w3 H- Y: R: E( ~0 C
B. p-next-next=p-next;
C. p-next-next=p;
D. p-next=p-next-next;5 u+ N7 s' @+ T/ N
6.在一个单链表中，若要在p所指向的结点之后插入一个新结点，则需要相继修改( )个指针域的值。 (满分:5)
A. 1
B. 2' d( m- f6 e" s! X7 @6 B6 Y/ K! }
C. 3
D. 4
7.在表长为n的顺序表中,若在每个位置插入数据元素的概率相等，插入一个数据元素平均需要移动( )个数据元素。 (满分:5)" Z$ U9 T+ e# h) [8 Q: h/ Y8 N- g: z
A.(n-1)/28 b; /! T5 c% t4 h- {9 l
B. n/2
C. n-1
D. n
8.表达式a*(b+c)-d的后缀表达式是( )。 (满分:5)9 @8 x8 N( G* ]3 D! J- o
A. abcd*+-- A1 |) O' V b- u: /
B. abc+*d-
C. abc*+d-
D. -+*abcd
9.在一个长度为n的线性表中，删除值为x的元素时需要比较元素和移动元素的总次数为( )。 (满分:5)
A.(n+1)/2
B. n/22 c, o$ }( K. n1 F. ` A
C. n) t! @( u' g/ Y2 A" H. a" `7 `
D. n+1
10.广义表L=（a，（b，c）），进行Tail（L）操作后的结果为( )。 (满分:5)
A. c
B. b，c
C. （b，c）+ ~# D M3 z, C4 v8 A9 l
D. （（b，c））
三、判断题：
1.4个元素按a,b,c,d顺序连续进入队列，队头的元素是a。( ) (满分:5)
A. 错误
B. 正确
2.若n阶方阵的对角线右上方的元素均等于零，称为下三角矩阵。( ) (满分:5)3 Y8 M9 R% F- x* V2 F
A. 错误, R7 a: B! Y9 w) i
B. 正确
3.顺序表的长度是表中的数据元素个数。( ) (满分:5)
A. 错误+ N$ g; }% ?' O7 ], R3 X+ d
B. 正确
4.栈和队列的共同特点是先进先出。( ) (满分:5)( l. `7 g8 l `! v- J
A. 错误
B. 正确8 o9 R9 i4 o4 { O
5.插入和删除只能在表的一端进行的线性表，称为队列。( ) (满分:5)
A. 错误7 `* N |; j0 c9 x
B. 正确
6.在栈中，出栈操作的时间复杂度为O(n)。( ) (满分:5)# g1 @- ]4 O( {/ Q; U
A. 错误
B. 正确# J8 w' c: X% d1 g6 K6 ^0 c$ l: S
7.栈是限定只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。( ) (满分:5)
A. 错误3 S5 G8 Y0 F9 C, e
B. 正确
8.中缀表达式A-(B+C/D)*E的后缀形式是ABCD/+E*-。( ) (满分:5)
A. 错误# r1 h$ R1 q6 f% X+ L5 k+ |7 V
B. 正确
9.算法分析的两个主要方面空间复杂度和时间复杂度。( ) (满分:5)
A. 错误# U% I# d) O8 l; |/ O2 ]$ v' K2 ?( K
B. 正确
10.顺序表中存取每一个元素的时间相同。( ) (满分:5)1 U# _8 d' @: D1 ~$ Q+ i6 ~+ K
A. 错误6 r8 ~. {; Y9 j w' T; k
B. 正确大工15春《数据结构》在线作业2, C: Z5 ~4 ?! i+ X/ t. c% ^
* _& z1 x! M$ L# N
一、单选题：) P# _5 b% Y1 Y( h- L
1.若串S="software",其子串的数目是( )。 (满分:5)/ {+ @3 x% B9 c7 S3 g
A. 81 S5 q3 i0 u5 g2 /5 m8 z) m4 g
B. 37
C. 36
D. 9
2.二叉树的先序遍历和中序遍历如下： 先序遍历：EFHIGJK；中序遍历: HFIEJKG 。该二叉树根的右子树的根是( )。 (满分:5)' p7 |+ q6 V. r9 K9 w
A. E
B. F
C. G% ?% p! d. ^/ t6 H
D. H" j% R% ~7 T# h5 T* A r1 z$ M
3.树中的结点数等于所有结点的度数加( )。 (满分:5)( `- X. n8 K( g; x% G7 l; G
A. 0
B. 1& V; t/ k' R: E. z. p! ~9 D
C. 26 d/ p: `/ c% Q- z
D. 3$ t7 {9 a) `0 m# H
4.已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 它的前序遍历是( )。 (满分:5)
A. acbed
B. decab1 Q, {5 {5 /( E. ^
C. deabc, [" b7 m) c4 `5 `
D. cedba
5.非空二叉树上叶子结点数等于双分支结点数加( )。 (满分:5)7 O4 t! ^; j" M
A. 0
B. 1- W& F: q; W9 B, x0 H* r7 `
C. 24 L( Z5 a% l$ S* S
D. 3
6.在完全二叉树中，若一个结点是叶结点，则它没( )。 (满分:5)
A. 左子结点
B. 右子结点
C. 左子结点和右子结点
D. 左子结点，右子结点和兄弟结点
7.对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( )次序的遍历实现编号。 (满分:5)1 /& r3 u. v @7 o! k V3 }
A. 先序- I) R$ L& b @
B. 中序
C. 后序: w f; e- R0 w
D. 从根开始按层次遍历+ n) K; ~9 t3 f0 |( p; H
8.concat(s,t)表示连接运算。将串t连接在串s之后，形成新的串s。若s="he",t="llo",则concat(s,t)之后，s="( )"。 (满分:5)4 [) }& N5 q6 S( r. |
A. hello3 R/ n o6 M1 b0 v1 Q, /* @1 {" /
B. helo7 }& {8 ^7 n8 [1 /
C. hllo
D. hell
9.union(A,B,C)表示求集合A和B的并集C。若A={a,b,c},B={c,d},则union(A,B,C)运算后C=( )。 (满分:5)
A. {a
b! u. y! P% u& F4 w8 K' @
c
d}/ O& C3 y6 V+ b" n' m2 v+ a, }: X
B. {a
b: J6 p- /& y' x) G6 z4 ?
c}
C. {a
b}0 t/ V. G U& l/ v
D. {c/ c. s5 n( G' O( C3 J
d}
10.一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足( )。 (满分:5)
A. 所有的结点均无左孩子
B. 所有的结点均无右孩子
C. 只有一个叶子结点5 M/ s& ?1 o9 A* a" o: c
D. 是任意一棵二叉树6 r* _8 ^& ?) I8 c5 M6 M
三、判断题：
1.遍历一棵具有n个结点的二叉树，在先序序列、中序序列和后序序列中所有叶子结点的相对次序都不相同。( ) (满分:5)
A. 错误
B. 正确
2.index(s,t)表示子串定位运算。若串t是串s的子串，则函数返回值是串t在串s中第一次出现的开始位置，否则返回值是0。( ) (满分:5)2 ^' j/ ~, [& ]+ v
A. 错误; Q4 R: `, g; A' I3 H
B. 正确
3.union(A,B,C)表示求集合A和B的并集C。( ) (满分:5)
A. 错误0 Z* o# A; g3 r0 R) Q( l+ ^" ~
B. 正确
4.广度优先遍历类似于二叉树的前序遍历。( ) (满分:5): e2 V; D6 _2 v
A. 错误
B. 正确
5.深度优先遍历类似于二叉树的后序遍历。( ) (满分:5)
A. 错误
B. 正确
6.在一个具有n个顶点和e条边的无向图的邻接表中，边结点的个数为2e。( ) (满分:5)
A. 错误
B. 正确
7.设树根为第1层，在一棵二叉树上第5层的结点数最多为16。( ) (满分:5)
A. 错误5 j& _( [2 X% s8 Z
B. 正确
8.difference(A,B,C)表示求集合A和B的差集C。( ) (满分:5)
A. 错误
B. 正确6 H" j. G7 a7 C% V" @2 q' v5 S
9.concat(s,t)表示连接运算。将串t连接在串s之后，形成新的串s。( ) (满分:5)# `7 x( Q0 ?3 c
A. 错误9 I a8 z- Y" _4 b+ o
B. 正确
10.具有5个顶点的无向图至少应有4条边才能确保是一个连通图。( ) (满分:5)
A. 错误
B. 正确大工15春《数据结构》在线作业3
2 V: ^, F8 I8 C! g: }$ ? m
一、单选题：6 b- }& E' `+ F5 L2 W# Y5 a
1.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，对成功的查找，其平均查找长度为( )。 (满分:5); J# y# W( L2 U: Y; i: Z ]
A.(n-1)/2
B. n/21 A& j8 v8 p7 @) o4 q& ]
C.(n+1)/24 N. b8 j- y9 /5 B7 p, |
D. n1 |; R( y2 w7 k! w1 r) d" Q) p
2.将10个元素散列到100000个单元的哈希表中，则( )产生冲突。 (满分:5); X" s7 b/ U$ ]1 Q. S
A. 一定会5 x' x3 L) k' d1 j' [& H, ^6 }; M
B. 一定不会& _/ C3 }" {( d/ d, ] j5 d+ E/ ]
C. 仍可能会
D. 以上都不对
3.运用直接插入排序方法对下面四个序列进行从小到大排序，元素比较次数最少的是( )。 (满分:5); S: f" W Y6 I: X6 M3 q
A. 900 S5 H' m, B5 M8 C
69$ A4 S& // @; ^& M, n
80
46, J8 [8 G3 y! d) A. v
21, J& G$ |. R8 `
404 M5 x5 M! D/ {8 e3 |$ p
B. 40
21! ?4 H ~+ H4 _# X5 /6 s
460 d8 P& h+ h* h7 Q2 d% P3 _ `
69
90
806 V% F) `9 n* {# U0 v
C. 908 W8 C6 r0 J, B$ I
80
691 M7 Z' /. _9 B" h3 f
46
40! P9 }/ p% x# ]" c b
21
D. 21/ f1 T* c8 |# E) `. L& J1 F
40
46$ }" U3 ] P+ d& C |
69
80 p+ [; ~$ F" U' E) I
90$ Z% s* D5 n( r9 i. q
4.若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选( )排序为宜。 (满分:5)7 ?! ?4 y9 d2 t i0 h2 a
A. 直接插入- L6 r% p O' Q$ g4 o9 |
B. 直接选择
C. 堆
D. 快速
5.一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为( )。 (满分:5)
A.(38
404 m( y' v8 G# n" C: f- C5 y
46( b) z: @- o0 H" c7 k$ p4 F
56/ t$ x/ O) o- r" O
79
84)( L; T- T% Z+ Q1 ]
B.(40
38
46
79
56
84)
C.(40
38
46
56
795 {4 I$ t) l8 L( a4 [7 N
84)% `. n% k( A6 w+ n: ` d. C. O2 g$ e
D.(40/ W5 `4 N0 F1 k ^. u) o
38
46
84
565 a6 {' n5 e! e+ // /+ @+ v) C
79)
6.下列排序算法中( )不能保证每趟排序至少能将一个元素放到其最终的位置上。 (满分:5)
A. 快速排序- d. w/ T; V% Z6 o
B. shell排序6 B1 t0 w9 _0 [
C. 堆排序
D. 冒泡排序$ y6 O) i) ^ q6 O O
7.采用简单选择排序，比较次数与移动次数分别为( )。 (满分:5)
A. O（n）
O(logn)
B. O(logn)
0(n*n)* Q7 L4 U0 A* p# S3 {1 k
C. 0(n*n): Y Q: g0 k, t" x2 d# p
0(n)$ D* ~" D3 G4 C- @5 @
D. 0(nlogn)& H- ?1 a! N3 V" V# M& o$ N
0(n)! [3 Z/ [9 b# j+ /6 Q
8.快速排序方法在( )情况下最不利于发挥其长处。 (满分:5): ?* x: P6 z- R" A
A. 要排序的数据量太大 `8 G |9 I2 D, A
B. 要排序的数据中含有多个相同值" p) U( y6 D/ /8 J5 [6 y; z1 d
C. 要排序的数据个数为奇数9 G& E; P2 M0 I. h
D. 要排序的数据已基本有序
9.散列表的地址区间为0-17,散列函数为H(K)=K mod 17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。存放元素59需要搜索的次数是( )。 (满分:5)
A. 2
B. 3# ^2 h# O; w/ [# F( t5 F+ V$ w
C. 43 S& @" S/ P0 K6 A$ p* b9 M
D. 54 B% w$ c- /; k% g }7 q
10.二分法查找，要求线性表一定是( )。 (满分:5)9 W; n8 _2 e& H/ R. A3 w
A. 顺序存储的无序表
B. 链式存储的无序表0 j* y/ l+ R0 w- f: B9 H3 f) y
C. 顺序存储的有序表
D. 链式存储的有序表
三、判断题：5 u3 Y5 k! h0 P1 h" A
1.堆是完全二叉树。( ) (满分:5)
A. 错误
B. 正确
2.用冒泡排序的方法对n个数据进行排序，第一趟共比较n-1对元素。( ) (满分:5)
A. 错误8 ?7 u e' p( v( o |
B. 正确
3.合并排序是利用“合并”方法来进行排序。合并是将两个或多个有序表进行合并，得到一个有序表。( ) (满分:5)0 v+ U$ n5 [- P# w+ ?. Y
A. 错误 {' v9 q8 a. C) C. A
B. 正确1 k/ x0 `, K$ ?) E9 B* I
4.从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）一端的方法，称为希尔排序。( ) (满分:5)$ B& H$ }: F; i) c- T4 X0 i
A. 错误- f- O( Y$ D7 K
B. 正确
5.存储在磁带上的顺序文件的查找只能用顺序查找。( ) (满分:5)$ D% /; F% k1 n- G
A. 错误$ a. f4 }6 d2 s7 E% ]% o+ J. L
B. 正确7 v% x$ g- U2 j- R
6.通常，磁带只适合于存储散列文件。( ) (满分:5)
A. 错误
B. 正确5 q. Q k1 N4 H/ _/ }
7.交换排序的基本思想是两两比较待排序记录的排序码，并交换不满足顺序要求的那些偶对，直到全部满足顺序要求为止。( ) (满分:5)# q6 q* F% S# F! V. ~) c' A
A. 错误
B. 正确2 r2 _+ k5 O. B5 p' Y" X$ ~7 Y
8.快速排序是稳定的排序方法。( ) (满分:5) F) A; [& B* R6 `6 G' I; M
A. 错误
B. 正确
9.散列文件的基本存储单位是页块。( ) (满分:5)- /" Q5 R& C. G
A. 错误
B. 正确
10.直接插入排序是不稳定性排序法。( ) (满分:5)
A. 错误
B. 正确' ~1 V& N X t" i+ M
2 E5 f- D* {: @! B
: w* P2 e! y6 p% a! ~ F8 n$ m3 I6 J
一、单选题：3 j6 O) }9 L% A: q. Z; f
1.一个顺序栈S，元素a，b，c，d，e依次进栈，如果5个元素的出栈顺序为b，e，d，c，a，则顺序栈的容量至少应为( )。 (满分:5)
A. 2
B. 3, }1 |0 E" y. J/ y* W9 t
C. 4
D. 55 _* o6 G) t! w' q
2.对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是( )。 (满分:5)
A. head==NULL
B. head→next==NULL3 g% `" `: h5 W$ /
C. head→next==head
D. head!=NULL
3.最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是 ( )。 (满分:5)3 n3 Y- m# @( v1 h
A.(rear+1) MOD n=front
B. rear=front
C. rear+1=front
D.(rear-l) MOD n=front
4.广义表((e))的表头是( )。 (满分:5)
A. e
B.(e)( R$ {# ^. q( C5 i w6 n( p& e" X
C.( )
D.(( ))/ F. o% V% F4 Q0 b# d& d
5.在一个单链表中，删除*p结点之后的一个结点的操作是( )。 (满分:5)& J; F( J; D: o' `- s
A. p-next=p;/ w3 H- Y: R: E( ~0 C
B. p-next-next=p-next;
C. p-next-next=p;
D. p-next=p-next-next;5 u+ N7 s' @+ T/ N
6.在一个单链表中，若要在p所指向的结点之后插入一个新结点，则需要相继修改( )个指针域的值。 (满分:5)
A. 1
B. 2' d( m- f6 e" s! X7 @6 B6 Y/ K! }
C. 3
D. 4
7.在表长为n的顺序表中,若在每个位置插入数据元素的概率相等，插入一个数据元素平均需要移动( )个数据元素。 (满分:5)" Z$ U9 T+ e# h) [8 Q: h/ Y8 N- g: z
A.(n-1)/28 b; /! T5 c% t4 h- {9 l
B. n/2
C. n-1
D. n
8.表达式a*(b+c)-d的后缀表达式是( )。 (满分:5)9 @8 x8 N( G* ]3 D! J- o
A. abcd*+-- A1 |) O' V b- u: /
B. abc+*d-
C. abc*+d-
D. -+*abcd
9.在一个长度为n的线性表中，删除值为x的元素时需要比较元素和移动元素的总次数为( )。 (满分:5)
A.(n+1)/2
B. n/22 c, o$ }( K. n1 F. ` A
C. n) t! @( u' g/ Y2 A" H. a" `7 `
D. n+1
10.广义表L=（a，（b，c）），进行Tail（L）操作后的结果为( )。 (满分:5)
A. c
B. b，c
C. （b，c）+ ~# D M3 z, C4 v8 A9 l
D. （（b，c））
三、判断题：
1.4个元素按a,b,c,d顺序连续进入队列，队头的元素是a。( ) (满分:5)
A. 错误
B. 正确
2.若n阶方阵的对角线右上方的元素均等于零，称为下三角矩阵。( ) (满分:5)3 Y8 M9 R% F- x* V2 F
A. 错误, R7 a: B! Y9 w) i
B. 正确
3.顺序表的长度是表中的数据元素个数。( ) (满分:5)
A. 错误+ N$ g; }% ?' O7 ], R3 X+ d
B. 正确
4.栈和队列的共同特点是先进先出。( ) (满分:5)( l. `7 g8 l `! v- J
A. 错误
B. 正确8 o9 R9 i4 o4 { O
5.插入和删除只能在表的一端进行的线性表，称为队列。( ) (满分:5)
A. 错误7 `* N |; j0 c9 x
B. 正确
6.在栈中，出栈操作的时间复杂度为O(n)。( ) (满分:5)# g1 @- ]4 O( {/ Q; U
A. 错误
B. 正确# J8 w' c: X% d1 g6 K6 ^0 c$ l: S
7.栈是限定只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。( ) (满分:5)
A. 错误3 S5 G8 Y0 F9 C, e
B. 正确
8.中缀表达式A-(B+C/D)*E的后缀形式是ABCD/+E*-。( ) (满分:5)
A. 错误# r1 h$ R1 q6 f% X+ L5 k+ |7 V
B. 正确
9.算法分析的两个主要方面空间复杂度和时间复杂度。( ) (满分:5)
A. 错误# U% I# d) O8 l; |/ O2 ]$ v' K2 ?( K
B. 正确
10.顺序表中存取每一个元素的时间相同。( ) (满分:5)1 U# _8 d' @: D1 ~$ Q+ i6 ~+ K
A. 错误6 r8 ~. {; Y9 j w' T; k
B. 正确大工15春《数据结构》在线作业2, C: Z5 ~4 ?! i+ X/ t. c% ^
* _& z1 x! M$ L# N
一、单选题：) P# _5 b% Y1 Y( h- L
1.若串S="software",其子串的数目是( )。 (满分:5)/ {+ @3 x% B9 c7 S3 g
A. 81 S5 q3 i0 u5 g2 /5 m8 z) m4 g
B. 37
C. 36
D. 9
2.二叉树的先序遍历和中序遍历如下： 先序遍历：EFHIGJK；中序遍历: HFIEJKG 。该二叉树根的右子树的根是( )。 (满分:5)' p7 |+ q6 V. r9 K9 w
A. E
B. F
C. G% ?% p! d. ^/ t6 H
D. H" j% R% ~7 T# h5 T* A r1 z$ M
3.树中的结点数等于所有结点的度数加( )。 (满分:5)( `- X. n8 K( g; x% G7 l; G
A. 0
B. 1& V; t/ k' R: E. z. p! ~9 D
C. 26 d/ p: `/ c% Q- z
D. 3$ t7 {9 a) `0 m# H
4.已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 它的前序遍历是( )。 (满分:5)
A. acbed
B. decab1 Q, {5 {5 /( E. ^
C. deabc, [" b7 m) c4 `5 `
D. cedba
5.非空二叉树上叶子结点数等于双分支结点数加( )。 (满分:5)7 O4 t! ^; j" M
A. 0
B. 1- W& F: q; W9 B, x0 H* r7 `
C. 24 L( Z5 a% l$ S* S
D. 3
6.在完全二叉树中，若一个结点是叶结点，则它没( )。 (满分:5)
A. 左子结点
B. 右子结点
C. 左子结点和右子结点
D. 左子结点，右子结点和兄弟结点
7.对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( )次序的遍历实现编号。 (满分:5)1 /& r3 u. v @7 o! k V3 }
A. 先序- I) R$ L& b @
B. 中序
C. 后序: w f; e- R0 w
D. 从根开始按层次遍历+ n) K; ~9 t3 f0 |( p; H
8.concat(s,t)表示连接运算。将串t连接在串s之后，形成新的串s。若s="he",t="llo",则concat(s,t)之后，s="( )"。 (满分:5)4 [) }& N5 q6 S( r. |
A. hello3 R/ n o6 M1 b0 v1 Q, /* @1 {" /
B. helo7 }& {8 ^7 n8 [1 /
C. hllo
D. hell
9.union(A,B,C)表示求集合A和B的并集C。若A={a,b,c},B={c,d},则union(A,B,C)运算后C=( )。 (满分:5)
A. {a
b! u. y! P% u& F4 w8 K' @
c
d}/ O& C3 y6 V+ b" n' m2 v+ a, }: X
B. {a
b: J6 p- /& y' x) G6 z4 ?
c}
C. {a
b}0 t/ V. G U& l/ v
D. {c/ c. s5 n( G' O( C3 J
d}
10.一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足( )。 (满分:5)
A. 所有的结点均无左孩子
B. 所有的结点均无右孩子
C. 只有一个叶子结点5 M/ s& ?1 o9 A* a" o: c
D. 是任意一棵二叉树6 r* _8 ^& ?) I8 c5 M6 M
三、判断题：
1.遍历一棵具有n个结点的二叉树，在先序序列、中序序列和后序序列中所有叶子结点的相对次序都不相同。( ) (满分:5)
A. 错误
B. 正确
2.index(s,t)表示子串定位运算。若串t是串s的子串，则函数返回值是串t在串s中第一次出现的开始位置，否则返回值是0。( ) (满分:5)2 ^' j/ ~, [& ]+ v
A. 错误; Q4 R: `, g; A' I3 H
B. 正确
3.union(A,B,C)表示求集合A和B的并集C。( ) (满分:5)
A. 错误0 Z* o# A; g3 r0 R) Q( l+ ^" ~
B. 正确
4.广度优先遍历类似于二叉树的前序遍历。( ) (满分:5): e2 V; D6 _2 v
A. 错误
B. 正确
5.深度优先遍历类似于二叉树的后序遍历。( ) (满分:5)
A. 错误
B. 正确
6.在一个具有n个顶点和e条边的无向图的邻接表中，边结点的个数为2e。( ) (满分:5)
A. 错误
B. 正确
7.设树根为第1层，在一棵二叉树上第5层的结点数最多为16。( ) (满分:5)
A. 错误5 j& _( [2 X% s8 Z
B. 正确
8.difference(A,B,C)表示求集合A和B的差集C。( ) (满分:5)
A. 错误
B. 正确6 H" j. G7 a7 C% V" @2 q' v5 S
9.concat(s,t)表示连接运算。将串t连接在串s之后，形成新的串s。( ) (满分:5)# `7 x( Q0 ?3 c
A. 错误9 I a8 z- Y" _4 b+ o
B. 正确
10.具有5个顶点的无向图至少应有4条边才能确保是一个连通图。( ) (满分:5)
A. 错误
B. 正确大工15春《数据结构》在线作业3
2 V: ^, F8 I8 C! g: }$ ? m
一、单选题：6 b- }& E' `+ F5 L2 W# Y5 a
1.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，对成功的查找，其平均查找长度为( )。 (满分:5); J# y# W( L2 U: Y; i: Z ]
A.(n-1)/2
B. n/21 A& j8 v8 p7 @) o4 q& ]
C.(n+1)/24 N. b8 j- y9 /5 B7 p, |
D. n1 |; R( y2 w7 k! w1 r) d" Q) p
2.将10个元素散列到100000个单元的哈希表中，则( )产生冲突。 (满分:5); X" s7 b/ U$ ]1 Q. S
A. 一定会5 x' x3 L) k' d1 j' [& H, ^6 }; M
B. 一定不会& _/ C3 }" {( d/ d, ] j5 d+ E/ ]
C. 仍可能会
D. 以上都不对
3.运用直接插入排序方法对下面四个序列进行从小到大排序，元素比较次数最少的是( )。 (满分:5); S: f" W Y6 I: X6 M3 q
A. 900 S5 H' m, B5 M8 C
69$ A4 S& // @; ^& M, n
80
46, J8 [8 G3 y! d) A. v
21, J& G$ |. R8 `
404 M5 x5 M! D/ {8 e3 |$ p
B. 40
21! ?4 H ~+ H4 _# X5 /6 s
460 d8 P& h+ h* h7 Q2 d% P3 _ `
69
90
806 V% F) `9 n* {# U0 v
C. 908 W8 C6 r0 J, B$ I
80
691 M7 Z' /. _9 B" h3 f
46
40! P9 }/ p% x# ]" c b
21
D. 21/ f1 T* c8 |# E) `. L& J1 F
40
46$ }" U3 ] P+ d& C |
69
80 p+ [; ~$ F" U' E) I
90$ Z% s* D5 n( r9 i. q
4.若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选( )排序为宜。 (满分:5)7 ?! ?4 y9 d2 t i0 h2 a
A. 直接插入- L6 r% p O' Q$ g4 o9 |
B. 直接选择
C. 堆
D. 快速
5.一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为( )。 (满分:5)
A.(38
404 m( y' v8 G# n" C: f- C5 y
46( b) z: @- o0 H" c7 k$ p4 F
56/ t$ x/ O) o- r" O
79
84)( L; T- T% Z+ Q1 ]
B.(40
38
46
79
56
84)
C.(40
38
46
56
795 {4 I$ t) l8 L( a4 [7 N
84)% `. n% k( A6 w+ n: ` d. C. O2 g$ e
D.(40/ W5 `4 N0 F1 k ^. u) o
38
46
84
565 a6 {' n5 e! e+ // /+ @+ v) C
79)
6.下列排序算法中( )不能保证每趟排序至少能将一个元素放到其最终的位置上。 (满分:5)
A. 快速排序- d. w/ T; V% Z6 o
B. shell排序6 B1 t0 w9 _0 [
C. 堆排序
D. 冒泡排序$ y6 O) i) ^ q6 O O
7.采用简单选择排序，比较次数与移动次数分别为( )。 (满分:5)
A. O（n）
O(logn)
B. O(logn)
0(n*n)* Q7 L4 U0 A* p# S3 {1 k
C. 0(n*n): Y Q: g0 k, t" x2 d# p
0(n)$ D* ~" D3 G4 C- @5 @
D. 0(nlogn)& H- ?1 a! N3 V" V# M& o$ N
0(n)! [3 Z/ [9 b# j+ /6 Q
8.快速排序方法在( )情况下最不利于发挥其长处。 (满分:5): ?* x: P6 z- R" A
A. 要排序的数据量太大 `8 G |9 I2 D, A
B. 要排序的数据中含有多个相同值" p) U( y6 D/ /8 J5 [6 y; z1 d
C. 要排序的数据个数为奇数9 G& E; P2 M0 I. h
D. 要排序的数据已基本有序
9.散列表的地址区间为0-17,散列函数为H(K)=K mod 17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。存放元素59需要搜索的次数是( )。 (满分:5)
A. 2
B. 3# ^2 h# O; w/ [# F( t5 F+ V$ w
C. 43 S& @" S/ P0 K6 A$ p* b9 M
D. 54 B% w$ c- /; k% g }7 q
10.二分法查找，要求线性表一定是( )。 (满分:5)9 W; n8 _2 e& H/ R. A3 w
A. 顺序存储的无序表
B. 链式存储的无序表0 j* y/ l+ R0 w- f: B9 H3 f) y
C. 顺序存储的有序表
D. 链式存储的有序表
三、判断题：5 u3 Y5 k! h0 P1 h" A
1.堆是完全二叉树。( ) (满分:5)
A. 错误
B. 正确
2.用冒泡排序的方法对n个数据进行排序，第一趟共比较n-1对元素。( ) (满分:5)
A. 错误8 ?7 u e' p( v( o |
B. 正确
3.合并排序是利用“合并”方法来进行排序。合并是将两个或多个有序表进行合并，得到一个有序表。( ) (满分:5)0 v+ U$ n5 [- P# w+ ?. Y
A. 错误 {' v9 q8 a. C) C. A
B. 正确1 k/ x0 `, K$ ?) E9 B* I
4.从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）一端的方法，称为希尔排序。( ) (满分:5)$ B& H$ }: F; i) c- T4 X0 i
A. 错误- f- O( Y$ D7 K
B. 正确
5.存储在磁带上的顺序文件的查找只能用顺序查找。( ) (满分:5)$ D% /; F% k1 n- G
A. 错误$ a. f4 }6 d2 s7 E% ]% o+ J. L
B. 正确7 v% x$ g- U2 j- R
6.通常，磁带只适合于存储散列文件。( ) (满分:5)
A. 错误
B. 正确5 q. Q k1 N4 H/ _/ }
7.交换排序的基本思想是两两比较待排序记录的排序码，并交换不满足顺序要求的那些偶对，直到全部满足顺序要求为止。( ) (满分:5)# q6 q* F% S# F! V. ~) c' A
A. 错误
B. 正确2 r2 _+ k5 O. B5 p' Y" X$ ~7 Y
8.快速排序是稳定的排序方法。( ) (满分:5) F) A; [& B* R6 `6 G' I; M
A. 错误
B. 正确
9.散列文件的基本存储单位是页块。( ) (满分:5)- /" Q5 R& C. G
A. 错误
B. 正确
10.直接插入排序是不稳定性排序法。( ) (满分:5)
A. 错误
B. 正确' ~1 V& N X t" i+ M
2 E5 f- D* {: @! B
版权声明
声明：有的资源均来自网络转载，版权归原作者所有，如有侵犯到您的权益
请联系本站我们将配合处理！
上一篇 : 大工15春《水工建筑物》在线作业答案
下一篇 :大工15春《楼宇自动化》在线作业答案