|
|
资料来源：谋学网（www.mouxue.com）数据结构-[东北师范大学]《数据结构》2023年秋学期在线作业2
! Z) D) c* I- k) M+ S4 G4 J5 w2 B试卷总分:100 得分:100
/ s. m0 A; z9 @第1题,递归过程的实现需用到8 d& M$ U- J# o6 e( M3 i- _
A、线性表
/ z0 M" @* \9 k: t' n# r aB、链表
- C8 J5 L* `5 c3 T' o ~ n+ LC、栈
' d' Q' q/ C+ F* q/ S' O! j3 HD、队列
3 l$ ?0 n- l7 {; |正确答案:
- I2 i1 I$ Y. v: s3 P& A" N
. R, J5 y9 q/ |7 O' v% `+ w* j
第2题,在下列情况中可称为二叉树的是" s- |5 t( R0 J
A、每个结点至多有两棵子树的树
& g$ s7 Y* h5 o$ CB、哈夫曼树
1 o8 J1 z6 T: y* @C、每个结点至多有两棵子树的有序树; n& \1 F4 ^$ q7 D% ^2 L0 j' J
D、每个结点只有一棵右子树% r a* D# Y5 j. e
正确答案:% `4 |1 i8 a, F5 ^
* C. a3 X. j9 O' f# y/ U) K! F2 g# G# `+ `! {* ~* O
第3题,经过下列栈的操作后GetTopST的值是InitStackSTpushST'a'pushST'b'popSTx
, {* V# ]; i7 r oA、a8 r' Y2 g+ ]" o
B、b! o# R f9 T4 t% V3 S7 _+ v1 m+ u% R
C、1
& }- o2 L b+ k9 X5 W7 N8 }2 jD、2
9 f1 k3 ], P2 W! m- O! X$ l4 I! [正确答案:: A. m! _ d/ `" G$ T7 _
6 [9 m% T- V; |; a1 I- b2 s0 |) w: l% z
第4题,若要求尽可能快地对序列进行稳定的排序则应选8 D- a, c9 R# ?3 N% b# C0 w; S
A、快速排序9 T4 K o( w0 k! G( J
B、归并排序
$ z2 n: T) a0 k$ V# XC、起泡排序
0 y! b3 a# H( w. H5 T7 qD、希尔排序
* q; W, _8 A8 T正确答案:# d6 _- s& ]( t( a
) K3 d# J/ n2 \! w1 N) |
0 U- P; T( j$ e9 F9 R9 J资料来源：谋学网（www.mouxue.com）,一个算法应该是
* W5 Z' o1 N' {! a- @! g; g* E! SA、程序7 n$ h% ~ A. s3 I9 b. V; Q
B、问题求解步骤的描述
# y% d1 t6 h5 R' J5 n nC、要满足五个基本特性
* @9 q/ \+ H; F0 a) VD、A和C
4 R* {+ a/ D+ p1 O正确答案:
" Q: o; S& O( U" s, ]: x' ?& \, }
% c- s; f, h# t$ M, ]& g* V0 t6 n. R" E, K) ^" }
第6题,判断线索二叉树中某结点p有左子女的条件是
1 i- r0 O- Q) V9 _$ }A、p ! = NULL6 `0 x g1 p8 f' h8 k3 ]$ W" W
B、p-lchild ! = NULL
$ |! m# |% s+ wC、p-ltag = = 0
% @2 P3 W. M9 N4 m- d( ?1 ED、p-ltag = = 1
5 v- n( H# W* ^" Q正确答案:
9 f4 z, F( q! F9 y' C& n) m) {9 K( u; T. z( b" e
* r3 T7 g7 }- S& B9 c1 u; t% \
第7题,二叉树在中序线索化后仍不能有效求解的问题是
M. r7 m0 p4 z3 S* gA、求指定结点的前序后继
' h/ i; t* K, I7 t& m0 r/ H; }+ q% xB、求指定结点的中序前驱
" g4 I j1 p+ l# HC、求指定结点的中序后继
9 O: x% i* C( }" fD、求指定结点的后序后继
2 m7 b7 L$ G) B+ z正确答案:: I9 |' c8 q( t' b9 y
* v- ~1 e+ ^" R+ ^& M/ ]3 V# T& B7 Q
第8题,顺序文件采用顺序结构实现文件的存储对大型的顺序文件的少量修改要求重新复制整个文件代价很高采用的方法可降低所需的代价
( V. c8 F( ~! l1 r7 L/ U7 r dA、附加文件
. y, }* M3 d5 oB、按关键字大小排序: F; r, k3 C$ Z1 q) w; W& v( t
C、按记录输入先后排序
* d; E( d- r8 gD、连续排序
5 [* f# g5 M- g! o正确答案:2 o7 y+ [3 S$ ?0 W# P. T
6 e7 z: b, P& D5 b0 H
0 U7 w) _8 L. Q3 H6 ?! R) x) @7 O第9题,广义表A=abcdefg则式子headtailheadtailtailA的值为
( r5 z/ F+ M7 P6 J/ SA、( g )
+ G# t, U7 F. N* D/ ~: ]+ ]$ ]B、( d )
4 ?" N9 p1 \' v8 `0 Y' T EC、c2 d$ I) h( x" L, n( `, `2 S0 c- S. U) A
D、d$ R, O6 y. d* O4 K/ l
正确答案:
( ]8 q) d( Y; m0 q& [
/ s M4 U' X. t
! y5 I* B9 \8 s! C) E资料来源：谋学网（www.mouxue.com）,的遍历仍需要栈的支持
2 p! W' J8 ]6 S: ~, ~A、前序线索二叉树3 ?* `. ^0 O; d# X2 n8 ?! H
B、中序线索二叉树
4 s3 |9 c" ^ A4 SC、后序线索二叉树
5 f( ?: {6 z4 h+ UD、前三种均需要
$ \% Z& |9 ~ G m正确答案:
% b, T6 K5 ~; C% q2 T2 W' D. L* w( e8 x0 d
/ C( B* D( w" i. T. N8 j第11题,线索二叉树是一种结构! }6 t! k0 z( b$ Y; e/ ^' H. i, K
A、逻辑6 y: n+ U- C L" v5 n' ]
B、物理; L4 c6 _4 a! c" m. M3 J
C、逻辑和存储; j! N- e8 t" M) q% z
D、线性+ h+ k1 [; {. Q8 p
正确答案:
4 c$ }( o, E6 {: T! Q4 `
4 P' G- i. o/ [( t% V$ M/ F! S; i
资料来源：谋学网（www.mouxue.com）,有一个100*90的稀疏矩阵非零元素有10个设每个整型数占2字节则用三元组表示该矩阵时所需的字节数是6 _4 P3 q" w$ R6 r" ?
A、608 g, u7 y$ M7 @7 y
B、66
: }2 o2 I+ x% r/ o: Q8 KC、18000* Y; a* F7 y& B- D* w5 Y
D、33& w5 s: ]. q. |7 s
正确答案:$ X& _& R) e- d& d* {/ [
- V- Z7 M# {5 w+ {% X. F
7 u: r; R Y% C, N# k第13题,就排序算法所用的辅助空间而言堆排序、快速排序、归并排序的关系是0 f& O! k/ {2 O$ s
A、堆排序＜快速排序＜归并排序# ?" E2 T2 J$ w% Z3 x
B、堆排序＜归并排序＜快速排序+ a, ~/ @7 O4 B$ b
C、堆排序＞归并排序＞快速排序5 R: n& ]) ~) C) F$ I' I
D、堆排序＞快速排序＞归并排序
7 d! v4 H* ?7 |: C+ `+ q& ^# n正确答案:
5 n' T: n0 Q7 r/ T2 _7 _: \% H: s! s) @# L
- M8 X B2 \1 G! g: P, {第14题,下列说法不正确的是
' g M) R+ h/ J" a9 a7 yA、图的遍历是从给定的源点出发每个顶点仅被访问一次: x+ l. v1 m+ t
B、遍历的基本方法有两种：深度优先遍历和广度优先遍历
& `+ ?8 g# p- q% G" xC、图的深度优先遍历不适用于有向图
, u% W* @% n, Z& _2 w8 r4 m7 JD、图的深度优先遍历是一个递归过程
+ s/ S+ S- {6 ~+ z5 t0 J0 |/ \5 R正确答案: l3 |' A& o8 t3 ]. Q% W2 d1 J9 s
( ]$ c7 t; S$ F) H6 V/ T N: p! h' g6 `9 w" r) u, _
资料来源：谋学网（www.mouxue.com）,在一个图中所有顶点的度数之和等于图的边数的几倍 @4 v% A& }& X
A、1/2
: k' F: j& t, t" I- mB、17 ^4 e0 G4 i, ~
C、2' Y" a) ?! y& z8 g5 G, _5 V
D、46 B' I7 n+ | O9 Y* i* O
正确答案:) w7 `7 [) B4 D4 @
; k/ _$ `* W# |" d3 k4 D
2 L8 b9 u) z) s! ?, A( q/ \第16题,在一个单链表中已知q所指结点是p所指结点的前驱结点若在p之前插入s所指结点则执行0 a- z5 \5 v+ x2 r
A、p-next = s; s-next = q;; Z7 W$ l& X* ~9 c
B、s-next = p-next; p-next = s;
) g0 t9 d( |0 f0 u7 OC、p-next = s-next; s-next = p;
& v4 M* L/ c, A+ p$ y/ N( CD、q-next = s; s-next = p;; O# u5 j3 X- D! s" E/ l! |
正确答案:
3 O5 ~, h( k4 x: }& S- R( n4 e! g. a9 q, h- H/ U7 ~# L
+ t3 V* X% I$ M1 V第17题,在对n个元素的序列进行排序时堆排序所需要的附加存储空间是4 O+ P" B8 R6 w l- B1 _
A、O(log2n )5 f: {+ l5 U- G; {: h
B、O( 1 ). n; U! u2 h* p) ]3 q
C、O(n )) ~/ V. N e7 x8 y+ R/ L
D、O(nlog2n )7 @: S4 F- C+ \3 f; f. t# f
正确答案:
( b7 T) n9 P, ?
/ Z: v+ O6 B1 y* F; t r3 _5 d4 W4 I2 W0 V5 A$ _! A
第18题,已知一个顺序存储的线性表设每个结点占c个单元若第一个结点的地址为LOCa0则第i个结点的地址为* s2 c) u4 Y* @% S
A、LOC(a0)+(i-1)*c1 [ B. J6 R" H! u3 x, D6 E
B、LOC(a0)+i*c
! M0 z: E% [" }( k$ L4 a: q: KC、LOC(a0)-i*c: T) W: I ?+ U/ G: u8 V
D、LOC(a0)+(i+1)*c
V- u! [( C6 b% ^6 d% \( ^6 v! D正确答案:' k( V& Y( f* Z6 m+ E$ g
: z1 B; V! p6 ]: R5 l3 E1 ?9 T5 S% Z! K
第19题,分块查找要求表中的结点/ P, U3 ?' }$ N; s
A、全部无序8 p4 n _3 p0 p1 Y! C1 ?8 t& `2 Q
B、块之间无序
. i1 V4 u7 K) h& ?C、全部有序
4 e9 k& \2 ]& b0 c8 r. q5 BD、块之间有序
0 U2 h; y, ^/ ~1 h' w) c正确答案:
" A4 E Y7 G# i. a: ^" z! q! x
$ d% `8 J$ z+ f6 _
U3 {1 K! ]$ q X; ~资料来源：谋学网（www.mouxue.com）,下面关于串的叙述中哪一个是不正确的
x- R [$ u- B H- T k/ |A、串是字符的有限序列
( ~' d7 T. Y! y& w- q1 ]B、空串是由空格构成的串2 C% n% A, g( b, L" L/ _/ Z, _
C、模式匹配是串的一种重要运算
, h& _' K/ D0 i3 V9 \% T TD、串既可以采用顺序存储，也可以采用链式存储
$ l$ M3 L1 \7 c$ o- Z- s正确答案:
' y6 J& {( I2 h' m" ?) u
$ I/ o S6 S" X4 r+ U; F/ J
5 d+ A7 m$ M) l0 f第21题,二叉树按某种次序线索化后任一结点均有指向其前序结点和后继结点的线索! O# I, F4 n* G+ W
A、错误5 U3 ^ L3 ? N. [2 G/ I7 j
B、正确
* P! w1 W1 K: d) q" R正确答案:: Q" ?" s# z- `
+ l( S- K8 ~1 X/ D4 J/ Z
# E0 F8 b, ?2 m6 b, l- {第22题,在执行某个排序算法过程中出现了排序码朝着它最终排序位置相反的方向移动则该算法是不稳定的
* E6 X8 ?4 z8 [. _+ K. l; |: [+ Z' NA、错误
/ W& L* J* y3 U% q3 m% nB、正确4 b, v: y5 n7 U! C, p
正确答案:
7 l* ]$ T$ |, i; w6 Q) e. M w# ]0 @; U1 I
( f) R7 c. a' W/ d
第23题,非空的二叉树一定满足某结点若有左子女则其中序前驱一定没有右子女
0 @5 E1 w9 n. Q0 k4 o7 uA、错误! H W# A+ f4 {. Y4 z, u
B、正确
5 `* J* Z4 I1 t% X正确答案:
6 P$ p- B; i5 E8 k$ j% F! [) ~4 j
/ F9 z+ O1 n- A" N+ ?* L5 A第24题,数组是同类型值的集合
9 w% {# B' J% j) TA、错误
, W+ ^8 {, q8 n. P4 R! P1 T( p* mB、正确
. D [5 q" X6 \3 T( Q正确答案:
: G" o; E' q# ?7 ~! d9 ^+ w* x8 T# q( n8 h
1 z3 y2 k/ W6 g8 f, M, d1 D
资料来源：谋学网（www.mouxue.com）,用链表lchildrchild表示法存储的包含n个结点的二叉树结点的2n个指针域中有n+l个空指针
! b4 x9 j4 J( |' S" z/ WA、错误
* @% `3 V X. IB、正确7 P" K& h2 N; L, [, K
正确答案:- z X* y7 I, Z0 `; J5 b3 H. d1 t: {
6 {) @* @2 M# A2 `1 t9 l2 j
8 v* f5 F; h, l- q9 C第26题,链表中的表头指针与表头结点起到相同的作用4 [* Q$ b( @/ l1 @! E& Z
A、错误 u# A: w# W6 f+ z' y
B、正确
) ?( Q3 K$ o1 j3 l. h正确答案:9 W+ g( {9 M; ^# n
3 g {0 ]; O0 x
3 {6 H5 G1 R$ [! o: {
第27题,栈和队列的存储方式既可以是顺序方式又可以是链式方式3 M0 H, X8 o$ [$ Y- C9 \
A、错误
' S2 i# [' X* G9 p" a4 _B、正确) |0 @8 j& O3 V% ~# u& C: q& e: l
正确答案:
9 \0 [! ~ F% Z4 K: O) N5 s
7 y5 {8 O1 V/ X1 H d% K' R
1 l# c! v6 f8 |* v第28题,一个有向图的邻接表和逆邻接表中结点的个数可能不等
& J+ Y( k! [. Q9 H: M! V$ WA、错误 F Y3 z: j, J" |# v
B、正确
9 O" G& I& z6 m正确答案:
0 H+ K! o) C" A2 p( e5 Z8 }
6 {3 y8 \% s5 r( V0 o
3 Q4 ^( D5 F+ O0 t第29题,对大小均为n的有序表和无序表分别进行顺序查找在等概率查找的情况下对于查找成功它们的平均查找长度是相同的而对于查找失败它们的平均查找长度是不同的3 w/ {6 a7 u1 P8 l$ {! L/ Z
A、错误( W J0 B0 H5 e7 \2 w
B、正确
8 i8 R" u( A- Q4 n! ^正确答案:
% z B3 ]) Q% P* ^8 }
" M- y: ^; s: w
. `7 Z: Z. U4 M! o, ^, J& N资料来源：谋学网（www.mouxue.com）,任何无向图都存在生成树" e# P. z# \* s' V; l( K, l W, Z" O
A、错误" `- A9 J) J4 H! L! _
B、正确+ p# r% G7 `5 q6 F6 i1 {; k
正确答案:# U" r# S% I$ R0 i
. T. o4 t. ]- z# P* G# y
& f: ~7 }) N/ _: U. ~- q. o第31题,在完全二叉树中若一个结点没有左子女则它必是树叶8 U+ M" b7 |$ s
A、错误
$ S' @6 N9 U- eB、正确& {2 }. [1 f( K$ s+ e1 f) e
正确答案:
/ |# p+ C. m4 G: g5 i
! }+ N0 K4 Y4 y" g8 R. v6 j& W5 x0 m$ |. P& b( s9 n- V) Z6 n( a
第32题,链表中的表头结点仅起到标识的作用$ p' l. q- h& X5 ?: C H
A、错误% A3 H/ p8 l4 c o" j
B、正确
5 I% Q/ T; L- W' R正确答案:6 K# x% D; g! R( b# R, `) n# B
4 G6 \1 f. ~5 I$ P; z4 H
/ l: D0 T; R. S3 X: S
第33题,将一棵树转成二叉树根结点没有右子树& u; A, n" z( I8 |# x4 W& d+ L
A、错误
9 `* }3 l# d+ S2 t% Y. B$ {B、正确
0 H. L6 _& D6 @1 w正确答案:
2 L: n% c) H1 {& \$ n h! x% }# C$ y/ A
5 X, G5 G( g4 [9 @4 B
第34题,连通分量是无向图中的极大连通子图
3 A; p" }- D1 |3 pA、错误
" J2 s7 p9 ^" cB、正确
! s. a& Y/ x3 J2 o. ~正确答案:
" Q; _. a& X# n( A6 a
2 P' d/ \; o4 p/ |! B
( p/ K) R) X2 E1 ?7 f第35题,所谓取广义表的表尾就是返回广义表中最后一个元素
; _2 _1 z5 Y4 A* {8 v; T4 hA、错误1 \/ f8 |) S) ?' [3 a
B、正确
; Q- k) }+ [& |" F" u正确答案:/ i1 ^; _+ ?6 p5 X1 p- i3 [
' B4 e) c4 e) [0 y. V$ Z
. o0 Z3 U4 @' _" M5 N2 }* h- ~
第36题,需要借助于一个栈来实现DFS算法
+ _5 r1 m& G* l( u; J* i* hA、错误
* A! F: R% C( E; c! b4 RB、正确
1 ?6 G& Q u- B正确答案:! }) D, x7 j2 H* I3 A2 n
9 S$ }5 j* E- ?% y
) b% {3 k& s! f& y
第37题,必须把一般的树转换成二叉树后才能进行存储
) [! _; Q6 ?' m( a2 QA、错误8 P& K$ F) i! V! }+ m
B、正确
. ?2 v7 [ X. y d2 D正确答案:. L4 J+ ]# t4 P, e
4 O2 Y# M4 b4 x4 f, F
9 M) m" ^6 R: _
第38题,对于插入、删除运算来说链接存储结构一定优于顺序存储结构
& p5 M2 A- f3 H8 xA、错误
4 C& r+ w; p) \# z. l& aB、正确
( _* }$ E4 W$ o i; c0 b正确答案:& [" S' Q/ W6 T
0 J! e1 }+ U7 U2 N' g$ H& o* ?/ B( {
: [2 y- F8 t2 J7 | |第39题,后序线索二叉树是不完善的要对它进行遍历还需要使用栈( f2 ]2 [! s2 h- d. V" n
A、错误& p& E+ @2 ]7 U: b/ Y, m- o
B、正确4 A7 L2 e. q P" X+ ?; m
正确答案:
2 [! T1 j% \; } ^2 P) N
) s7 `, q/ k/ D- j
3 U B2 I, y" h& V4 T3 l3 k第40题,二维以上的数组其实是一种特殊的广义表! [$ }6 P3 p" {5 J
A、错误) B1 t- L1 i$ F% D& E
B、正确2 M# Q# m W+ \+ A% N, I/ b# N/ ?
正确答案:
, X; s7 S0 a. s) I P; o! }; {/ W! N& x2 a, I- U
6 k3 q, ^2 `; p- J; g- X
, _0 ]9 E, ` x' t. ]
4 v" b( T) n1 Y+ H* ~
- y+ ?% I; a$ j1 P, V. B6 @5 k2 v& V9 G3 l- |3 z
1 F8 r9 ^& f8 G3 `2 c# \& E9 m# W
9 x: l, B0 M( _$ [$ a/ |, ]) d
+ j$ x( O: K" P' T" L
) {. C! t* A! |5 ~2 h
1 y# B4 j& J3 |+ \
& A7 m% s( \# q: e- B- ]1 p$ Q. i2 d+ `9 m0 ~
|
|
IP卡
狗仔卡
发表于 2023-12-14 00:39:51
微信登陆 
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
显身卡
发表于 2023-12-15 10:06:54
客服一
