21年7月川大《数据结构2264》21春在线作业2

admin

资料来源：谋学网（www.mouxue.com）数据结构2264-[四川大学]《数据结构2264》21春在线作业2
. F" n7 F: o2 Q; f试卷总分:100    得分:100
( J2 V: h4 F! q7 P+ U& Z第1题,在线性表的下列运算中，不改变数据元素之间的结构关系的运算是（    ）。
A、插入
B、删除
' G0 ]1 P" ^4 jC、排序
D、查找
正确资料:


第2题,下面关于广义表的叙述中，不正确的是（    ）。
5 E6 g' w8 b! R4 G; Z$ eA、广义表可以是一个多层次的结构
B、广义表至少有一个元素
& P3 ~5 ^3 t. f$ h( ?: UC、广义表可以被其他广义表所共享
D、广义表可以是一个递归表
正确资料:
+ |  l- j: i$ Z9 r
7 T' d' u6 V5 ?8 Q8 W
5 o' C$ v' C8 W7 X- l* ]% i" i第3题,在一个带有附加表头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行（    ）。
A、HL=p; p-next=HL;
% q5 e8 M* S4 V+ v  S. R1 nB、p-next=HL-next; HL-next=p;
) R0 z( m4 ^+ k  U+ TC、p-next=HL; p=HL;
D、p-next=HL; HL=p;
, ]% \2 a- K1 ~" H8 C, L: d5 c正确资料:

! {: i% Q# [! s. A+ I
第4题,从二叉搜索树中查找一个元素时，其时间复杂度大致为（    ）。
A、O(n)
' h, O# a8 U5 Y  }9 AB、O(1)
C、O(log2n)
D、O(n2)
, x" M; G0 w% V/ r" r+ K正确资料:
; V: W, q9 z7 N

. N- h9 U" \  Z1 S& H- h' r7 W资料来源：谋学网（www.mouxue.com）,已知一个图的顶点集V={1,2,3,4,5,6,7}；边集E={（    ）3, （    ）5, （    ）8, （    ）10, （    ）6, （    ）15, （    ）12, （    ）9, （    ）4, （    ）20, （    ）18, （    ）25}，用克鲁斯卡尔算法得到最小生成树，则在最小生成树中依次得到的各条边为（    ）。
6 u9 R/ J2 ?" V0 |A、(1,2)3,  (4,6)4,  (1,3)5,  (1,4)8,  (2,5)10,  (4,7)20
/ e, p* D7 H! I! \0 AB、(1,2)3,  (4,6)4,  (1,3)5,  (2,3)6,  (1,4)8,  (3,6)9
C、(1,2)3,  (1,3)5,  (1,4)8,  (4,6)4,  (2,5)10,  (4,7)20
D、(1,2)3,  (1,3)5,  (1,4)8,  (2,5)10,  (4,6)4,  (4,7)20
. w5 z0 c: W. J0 J' m正确资料:
$ F: n, y5 K) E. s" E1 T2 l
" }" ~2 n8 `! U! z( N
% I8 ?9 q. v# h; G第6题,设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树上的结点个数为n，森林F中第一棵树的结点个数是（    ）。
A、m-n-1
% Z1 f# T  O$ I: V6 hB、n+1
* g3 B+ N  N; v  G' ^  }$ XC、m-n+1
4 O1 e1 S. g! k* g" T! qD、m-n
正确资料:
& h( N& n% p% k: |& D" b
. [) m3 O$ l3 K& k
" Z- h3 k' e' L# H" ?( D, Z! d) Y第7题,数据的基本单位是（    ）。
  S; B: v0 A/ t: z* t" S' Q( rA、数据项
B、数据类型
C、数据元素
D、数据变量
, S  A  w+ A7 n正确资料:

% G& v' [  `6 Q6 C( u* @. o# i
5 K. b, q. V9 A# m6 N+ o. A4 a第8题,从一个长度为n的顺序表中删除第i个元素（    ）时，需向前移动的元素个数是（    ）。
A、n-i
B、n-i+1
/ P* V- J3 M" Z! Q  {+ BC、n-i-1
D、i
$ r- d( [' Y' k正确资料:

% S5 s& R1 J! U1 [. B0 s* N, K
第9题,若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算时间的存储方式是（    ）。
5 u4 J: c+ s/ W: u! B, AA、单链表
5 x0 c* ]4 M4 W6 v6 b% }B、仅有头指针的单循环链表
C、双链表
, a2 B2 c. W- Z0 N' S4 AD、仅有尾指针的单循环链表
9 F4 B4 M, k* A4 R5 v8 S正确资料:


资料来源：谋学网（www.mouxue.com）,采用开放定址法处理散列表的冲突时，其平均查找长度（    ）。
A、低于链接法处理冲突
B、高于链接法处理冲突
C、与链接法处理冲突相同
- Y( b% F) c5 `% |9 ]# BD、高于二分查找
+ v" u! D, [, v  I4 ^6 K0 i$ u正确资料:
& }8 |, `5 @$ ~% ^

第11题,下列关于数据结构的叙述中，正确的是（    ）。
A、数组是不同类型值的集合
B、递归算法的程序结构比迭代算法的程序结构更为精炼
0 e: @: y+ X$ x! m; ~" G& Z2 EC、树是一种线性结构
D、用一维数组存储一棵完全二叉树是有效的存储方法
2 l  B" {  f) }( @8 B正确资料:
' b8 W/ T7 V* F$ w& I: Z

& c8 q! X! p9 G9 @$ a* g; A资料来源：谋学网（www.mouxue.com）,对关键字序列（    ）进行增量为3的一趟希尔排序的结果为（    ）。
A、(19, 23, 56, 34, 78, 67, 88, 92)
( J4 N2 c2 x* Z4 d; |B、(23, 56, 78, 66, 88, 92, 19, 34)
- b" N: _  U/ E0 S& N" F- ~5 I3 BC、(19, 23, 34, 56, 67, 78, 88, 92)
$ q3 m  W7 R9 L+ R+ R" x3 ^5 p' z# uD、(19, 23, 67, 56, 34, 78, 92, 88)
: e8 O) J- Q4 @" @5 l( u* L正确资料:


8 B1 ?% H# {: S2 a$ s第13题,以下数据结构中哪一个是非线性结构？（    ）
7 H% X# [7 s, |/ T5 ]A、队列
- ~4 [! C+ E) h1 R8 x4 H8 |& sB、栈
C、线性表
D、二叉树
; X) C# h' k, Z正确资料:
2 i9 @/ z0 k+ R$ c: I
1 b6 R# s2 F& {0 w/ _4 P
8 C" P9 i1 d1 H; u. t第14题,在二叉树结点的先序序列、中序序列和后序序列中，所有叶子结点的先后顺序（    ）
A、都不相同
B、完全相同
C、先序和中序相同，而与后序不同
7 L7 r; {0 y2 q' hD、中序和后序相同，而与先序不同
正确资料:

/ O% a" Y$ o. Q
, h( s3 Q+ M# @; v+ G- \% ~资料来源：谋学网（www.mouxue.com）,对线性表，在下列哪种情况下应当采用链表表示？（    ）
- C4 o5 j9 C4 n4 YA、经常需要随机地存取元素
# {9 K! @" x7 M- }# T! iB、经常需要进行插入和删除操作
9 S! _6 t$ ~' [3 |4 UC、表中元素需要占据一片连续的存储空间
8 M  d, ?3 @, H# p: J' x  d+ E  e7 gD、表中元素的个数不变
! p1 O, o5 G; ^) j( V" k2 E7 O% I+ s正确资料:

) A% {8 t1 D* i% v3 u
: h. B7 z5 C; h+ `第16题,AOV网是一种（    ）。
A、有向图
B、无向图
: d( V0 A2 Q* h& ~3 F+ x+ JC、无向无环图
5 m4 S" Y' ~" K# R$ `# s% fD、有向无环图
( b3 y6 Z2 G( D% o5 q; f# M# [% y正确资料:
2 x) H4 B8 x* t, j& A
% B" z  z7 s+ ]- N( F
) g7 T3 d: g' ^  E第17题,若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A[3]的比较序列的下标依次为（    ）。
6 e# c, E/ S) |* O: \, K/ I$ f" iA、1，2，3
B、9，5，2，3
+ H7 m/ Q5 h2 t8 iC、9，5，3
; D. ~9 E% k  V) Y* y, rD、9，4，2，3
正确资料:

( o( T. I- D5 d: Y& m% @4 h
第18题,由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为（    ）。
: ?1 W* Y/ p% w! H" _8 p% aA、11
B、35
C、19
! I& {' c# s% s( G4 N/ W1 hD、53
正确资料:
, ]& D9 r/ D9 _1 A8 w
0 ~- Y2 F- C/ ]; v
第19题,对一棵有100个结点的完全二叉树按层编号，根结点编号为1，则编号为49的结点的父结点的编号为（    ）。
% P: m2 l9 f: W8 G4 T7 \A、24
- P- {9 C  ~- a3 WB、5
C、98
D、99
+ r. k1 n6 `1 l* c. v& Q5 T正确资料:


' F& i" i# Q* r/ o6 r资料来源：谋学网（www.mouxue.com）,若有序表为（    ），则在二分查找关键字b的过程中，先后进行比较的关键字依次为（    ）。
A、f,c,b
. l: u' J: V( N; G* s8 C1 u3 |B、f,d,b
C、g,c,b
7 G4 d6 e; g" oD、g,d,b
, ]& ]: W+ K( F( H6 [4 f正确资料:


第21题,下面关于图的存储的叙述中正确的是（    ）。
A、用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关。
B、用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关
C、用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关。
6 D3 q7 i8 `# j* P  I: ZD、用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关。
正确资料:
7 u9 G# q; @9 a* a) S& [+ k# Y

第22题,假定有K个关键字互为同义词，若用线性探测法把这K个关键字存入散列表中，至少要进行（    ）次探测。
; k: T3 [# Q/ y6 o% s2 V2 Z7 oA、K-1次
B、K次
! A5 s& D  W7 F: b  N. e! SC、K＋l次
, j( e& r+ m" y; h6 _4 iD、K(K+1)/2次
6 J- P; H# v7 C; S! f3 A# z: f正确资料:


第23题,在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点，则执行如下（    ）语句序列。
  Q6 x% K% u' y; |: {, i0 c/ _A、p=q; p-next=q;
$ V; e5 ^3 k! x* D+ P" uB、p-next=q; q-next=p;
C、p-next=q-next; p=q;
D、q-next=p-next; p-next=q;
正确资料:


第24题,若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为（    ）。
2 v" ~: W1 \6 OA、图中每个顶点的入度
B、图中每个顶点的出度
C、图中每个顶点的度
2 U* j8 j  Z* F+ R% _# `D、图中连通分量的数目
正确资料:
7 o& q/ x) {* F/ S: ~, K
" h* e# d* S: }2 q: z2 m
5 E! e7 G. Q9 N$ S) c& r" `资料来源：谋学网（www.mouxue.com）,在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i趟排序之前，无序区中元素的个数为（    ）。
8 I) T) K. N% C+ Z2 U1 WA、i
B、i+1
C、n-i
& s0 l- ?. [( K, o$ T, Z$ TD、n-i+1
2 n: O) ]) z. t7 }% I* a: A7 Y正确资料:
, g. Z0 B% F1 Q" ?: w* A

/ p) C0 f) @* g5 d第26题,栈和队列的共同特点是（    ）。
; D2 t6 h# A, q* ?1 h$ |* s& J+ \A、只允许在端点处插入和删除元素
B、都是先进后出
: J- m; R# L6 P' yC、都是先进先出
D、没有共同点
E、都可以采用顺序存储方式和链式存储方式
正确资料:,E
; w& p0 N4 b% F

/ C- `# n' {0 q; ], M第27题,下述（    ）是顺序存储方式的优点。
A、存储密度大
B、插入和删除运算方便
C、获取符合某种条件的元素方便
D、查找运算速度快
E、可以很方便地存取第i个元素
正确资料:,E
' O3 d5 j6 g; z% m$ z8 g/ N, m

第28题,对一个算法的评价，主要包括如下（    ）方面的内容。
1 C' Z# V3 g7 I4 R3 @A、健壮性和可读性
B、并行性
C、正确性
D、时空复杂度
* C# e5 Y. B; M# v% g0 YE、界面友好性
正确资料:,C,D

* D3 i3 K/ ]  V& V- H  T
9 c* g4 E- x( U- K* j" U第29题,若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列为（    ）。
A、3，2，6，1，4，5
4 Y+ z9 [# f% E; n. Y: _8 LB、3，4，2，1，6，5
C、1，2，5，3，4，6
% d& [$ g/ T4 K! _. g: W! QD、5，6，4，2，3，1
6 o8 a; T2 t/ ~6 ]5 n, iE、6，5，4，3，2，1
6 v" ]# M( \  a正确资料:,C,D
: U2 D6 {" G! [0 [2 e
  t6 t& y/ p8 I3 C* b" M" F
+ K- K. K: r( A资料来源：谋学网（www.mouxue.com）,若仅知道某二叉树的中序遍历序列和后序遍历序列，则不能够确定此二叉树的层次遍历的序列。
! E& h8 ]% `7 }  r9 RA、错误
B、正确
' k( h2 |3 E/ C. q5 P' a正确资料:
9 x; `8 f/ U  t8 h  G

第31题,在线性链表中删除某个结点时，只需将被删结点释放。
A、错误
B、正确
. t3 `, Y7 P. L0 q, v4 g正确资料:
; b3 [8 f$ v5 j3 w/ \

第32题,图G的某一最小生成树的代价一定小于其他生成树的代价。
2 A+ H( ]1 b; c  XA、错误
B、正确
正确资料:


第33题,链式栈与顺序栈相比, 一个明显的优点是通常不会出现栈满的情况。
' B5 ^; W" e* I- g0 B7 X# W+ nA、错误
+ X, |: i5 M  T0 c5 QB、正确
" F( R( ~/ |; L4 X正确资料:

$ A; t! n1 G% |/ C' G* {$ _
7 Q  G& a, p6 T0 l, b  X第34题,用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数有关，而与图的边数无关。
. Z. r) k2 E8 V* sA、错误
8 x9 e. ?# n% F/ M# E1 EB、正确
正确资料:
* C5 d2 R+ G4 H" H: q5 b
+ f) m9 ?/ T8 `7 j  l
2 n) L/ f/ n, M3 V7 a第35题,一个广义表（    ）,（    ）,c),（    ）))) 的表尾是（    ）,c),（    ）))。
' d* V, S0 x0 b$ IA、错误
: a" u: K3 Z5 O3 c2 oB、正确
4 B% `- {9 _. N/ z' q) M( Y正确资料:
: _0 R" k- x: r( @% m3 i$ w

第36题,在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻。
A、错误
  ~0 `+ \) _. t* }# dB、正确
, Z+ Q9 ^) C; `  f: R4 o. c正确资料:

4 v7 o9 _8 Z/ c8 ?, _* w
第37题,在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。
A、错误
1 P' ?' w* P3 e" l- GB、正确
正确资料:
, ^" d/ C1 u) ?5 B* J/ n
4 z& {4 U. u- _& x' B
2 U! A% ?+ f6 f) W8 u6 Z0 l第38题,用字符数组存储长度为n的字符串，数组长度至少为n+1。
0 e/ {" a6 s8 v  ?, hA、错误
% s1 c. R2 q3 h' {  i! \  l2 HB、正确
: y8 E4 @& Z. w3 J) E' \正确资料:


. A0 S9 y. n& ?' D) f# M2 g+ K" B; y# {第39题,在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和后序遍历，则具有相同的结果。
3 i  v& i  O" w, [5 B; fA、错误
B、正确
正确资料:

0 v: M- s) d6 Q) k+ ~
- I$ H4 ?/ c; V0 _* j1 r4 H& o1 x第40题,线性表若采用链式存储表示时，其存储结点的地址可连续也可不连续。
' r6 h, o7 H+ _0 yA、错误
2 {; C$ F9 R3 p- }0 z9 p+ w. x1 oB、正确
1 u* L8 a- h! f' \正确资料:
5 s, f/ x$ ~/ k2 j
( e2 g; V2 e: }  S
" n5 ]* x* G5 P$ A) Q0 Q$ J/ q第41题,对任何用顶点表示活动的网络（    ）进行拓扑排序的结果都是唯一的。
: W( L( l# @  J1 ?9 ]A、错误
- u! s" Y5 c- z  H, {- JB、正确
正确资料:
' W) b1 l, {5 c) F8 Z. X4 V* \

第42题,快速排序算法在每一趟排序中都能找到一个元素放在其最终的位置上。
% }( v& r5 r% Q! Y0 M% eA、错误
! k' o  S  H* G- V. L5 ~& e! uB、正确
正确资料:
1 C( m9 e7 n+ B) q0 \& Z

第43题,进行折半搜索的表必须是顺序存储的有序表。
% I& l$ C2 y* o+ c( ]A、错误
, }8 p$ ~( N2 g8 iB、正确
正确资料:


第44题,使用三元组表示稀疏矩阵中的非零元素能节省存储空间。
A、错误
B、正确
正确资料:



0 Y% Q& u$ A, V& g. o' _0 U


# e  Y9 w. E4 U
3 ]% G* O1 S, Q5 n5 x

+ b; `  x: k# Y- k& c

- }$ a, d8 v8 ?; h% @
% w  c5 `* s8 @' R

( C2 b6 K% K2 h2 f5 r; t0 b8 k; S