21秋东北大学《数据结构Ⅱ》在线平时作业3-1

admin

资料来源：谋学网（www.mouxue.com）数据结构Ⅱ-[东北大学]《数据结构Ⅱ》在线平时作业3
' m, h+ o- ^- r! i4 i$ m! O试卷总分:100    得分:100
第1题,一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构则计算该有向图中某个顶点出度的时间复杂度为
: W( V( l0 X2 g; r2 u4 l3 VA、O(n)
1 x$ X, t3 G3 T3 N$ }B、O(e)
C、O(n+e)
D、O(n2)
6 G8 I  p. Q4 Z; k正确资料:


/ J: c3 E: B! n" }2 l; C! }  }第2题,索引非顺序文件的特点是
A、主文件无序，索引表有序
B、主文件有序，索引表无序
! f! i9 t: G. m4 AC、主文件有序，索引表有序
) N1 P% X2 t: a" ]3 BD、主文件无序，索引表无序
正确资料:
/ t5 _6 T; D" i& v
$ m4 ~7 ]5 }# K4 P9 b1 b2 q
1 r1 h( T( X8 X第3题,二维数组A按行优先顺序存储其中每个元素占1个存储单元若A［1］［1］的存储地址为420A［3］［3］的存储地址为446则A［5］［5］的存储地址为
A、470
B、471
C、472
) G- p( r2 P4 H8 g8 P! SD、473
正确资料:

) p3 V  O- l8 t- T4 ~
0 U3 O! G8 K% Y; Q2 w第4题,在单链表中指针p指向元素为x的结点实现"删除x的后继"的语句是
$ M5 r2 X/ g% k6 s( X6 NA、p=p-next;
1 a5 n, q* m6 ~* P3 G! ?2 M) iB、p-next=p-next-next;
. p3 L1 n8 w( ?6 x6 Y/ V' jC、p-next=p;
% h* G1 c3 Z1 `* _" O5 s  ND、p=p-next-next;
正确资料:

! r% @' a4 G# c$ U  ?
9 n& Q7 d4 y4 `资料来源：谋学网（www.mouxue.com）,引入二叉线索树的目的是
  d' m8 e- ?  IA、加快查找结点的前驱或后继的速度
B、为了能在二叉树中方便的进行插入与删除
C、为了能方便的找到双亲
D、使二叉树的遍历结果唯一
4 ?; n  N; L/ Z正确资料:
6 w6 n  a) O& {" c; y/ |0 f

第6题,一棵树高为K的完全二叉树至少的结点是
A、2k -1
B、2k-1 -1
C、2k-1
D、2k
7 n; U7 R; E1 G正确资料:


第7题,下列查找算法中平均查找长度与元素个数n不直接相关的查找方法是
. i! s3 b8 J  a. R0 I8 tA、分块查找
B、顺序查找
: R0 K9 R1 R" p: h% ]  H! LC、二分查找
, P- B9 C: ^2 C# K& b, _% qD、散列查找
& K4 u5 G7 E* ~: p正确资料:

2 Q1 K- g: ^4 M& a
第8题,某二叉树中序序列为ABCDEFG后序序列为BDCAFGE则该二叉树对应的森林包括的树的棵树是
A、1
+ V3 U/ l5 g  `9 O5 l; WB、2
6 V5 b7 U4 y& f) y/ yC、3
+ T) B2 j8 ]- o* h3 J. V! J8 P3 FD、4
3 v9 W# ~( z# ?正确资料:

$ f& W2 F: Q0 N7 B- L
  E2 P% ?- j, x2 H6 s第9题,已知循环队列的存储空间为数组data[21]且当前队列的头指针和尾指针的值分别为8和3则该队列的当前长度为
( M6 {5 u  ?* @6 S3 Z" |. b$ LA、5
" c  s! A( S8 c2 GB、6
C、16
' z  K. i5 w7 h" CD、17
正确资料:
& g  e% t; A' m! |

资料来源：谋学网（www.mouxue.com）,在长度为n的顺序表中删除第i个元素1≤i≤n时元素移动的次数为
A、n-i+1
B、i
C、i+1
D、n-i
正确资料:


第11题,从逻辑上可以把数据结构分为两大类即
& }0 L. e- c- n/ dA、动态结构、静态结构
B、顺序结构、链式结构
C、线性结构、非线性结构
D、初等结构、构造型结构
正确资料:

" J! j# ]- i: V6 i6 P
; b& j% W: v$ N5 M资料来源：谋学网（www.mouxue.com）,如果求一个连通图中以某个顶点为根的高度最小的生成树应采用
A、深度优先搜索算法
B、广度优先搜索算法
( F6 L0 V. _6 ]9 B8 G) bC、求最小生成树的prim算法
# R4 I7 ~3 O. `( @0 gD、拓扑排序算法
正确资料:

8 R# x9 A0 ?9 T6 S* }
第13题,为便于判别有向图中是否存在回路可借助于
A、广度优先搜索算法
/ P! _/ g# n+ S/ @9 FB、最小生成树算法
1 X/ H# q+ P: y# e+ m9 k) |7 bC、最短路径算法
D、拓扑排序算法
正确资料:
0 M4 i/ O7 D2 B. S/ I0 L+ r; V
5 b4 `. f! ^1 n% Y3 M
第14题,队列和栈的主要区别是
A、逻辑结构不同
B、存储结构不同
C、所包含的运算个数不同
" A4 H, p4 y( H2 v, N( tD、限定插入和删除的位置不同
1 O1 L6 [' n" j( T6 m, |正确资料:


; x" i- ?! U5 {" m* I( j& }资料来源：谋学网（www.mouxue.com）,在头指针为head且表长大于1的单循环链表中指针p指向表中某个结点若pnextnext=head则
A、p指向头结点
B、p指向尾结点
C、p的直接后继是头结点
D、P的直接后继是尾结点
) D$ y% {  [0 [8 }正确资料:
/ y# J* l# F2 S' s. O

第16题,若将数据结构形式定义为二元组KR其中K是数据元素的有限集合则R是K上
A、操作的有限集合
B、映象的有限集合
C、类型的有限集合
8 s$ |5 |: \, a( s0 z0 W9 BD、关系的有限集合
+ }8 K& U5 d! f7 P% j正确资料:

+ Z1 L5 V& s) ?" A
第17题,通常将链串的结点大小设置为大于1是为了
: x2 o: w# J. w2 S* L( L( F& VA、提高串匹配效率
2 U: g- @# u: l; C+ X, C4 ~  r$ pB、提高存储密度
C、便于插入操作
D、便于删除操作
正确资料:

0 k( {4 s) d# v, }7 |
第18题,对长度为n的关键字序列进行堆排序的空间复杂度为
A、O（log2n）
B、O（1）
$ i" A+ j+ F8 J+ j+ BC、O（n）
D、O（n*log2n）
正确资料:
" m$ ~$ ^! _6 z; r, ^

第19题,在一个带权连通图G中权值最小的边一定包含在G的
A、最小生成树中
9 ?, ^  P% c+ |' k9 uB、深度优先生成树中
C、广度优先生成树中
D、深度优先生成森林中
正确资料:
% v7 Z9 l2 q" i1 b( W9 n

7 e9 e+ U0 H# \0 K资料来源：谋学网（www.mouxue.com）,假设以数组A[m]存放循环队列的元素已知队列的长度为length指针rear指向队尾元素的下一个存储位置则队头元素所在的存储位置为
A、(rear-length+m+1)％m
B、(rear-length+m)％m
C、(rear-length+m-1)％m
8 N. t5 L, [9 \5 bD、(rear-length)％m
4 p$ S( R* j" p8 G. T$ v正确资料:







. ]( Q( A. Z8 g0 L0 h2 o
" X$ k+ V. O. \3 C, B; n6 W
4 E0 z' g& e+ f% u$ |. ~% ]: b
( O% D9 W# V; }- w4 Y/ ^+ P
+ Y7 |2 R. J/ F
. ^% A& }2 ]( \6 G1 _3 e
8 B' E2 Q7 X8 k- j) y4 T
' b0 N# E: l/ b) G+ J