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

admin

资料来源：谋学网（www.mouxue.com）数据结构Ⅱ-[东北大学]《数据结构Ⅱ》在线平时作业3
3 J3 W2 Z& c8 B( z5 |试卷总分:100    得分:100
! ^7 u2 @" |/ U3 S) U第1题,一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为
A、O(n)
- S3 ^6 c; z9 ?5 ?B、O(e)
C、O(n+e)
! o, B9 z, V# E% WD、O(n2)
正确资料:


% W+ L! n7 j4 R, y- E: I  M$ J第2题,索引非顺序文件的特点是
A、主文件无序，索引表有序
B、主文件有序，索引表无序
) W7 ]+ h. I. E# Y  S/ B4 G; d2 }! o  WC、主文件有序，索引表有序
4 T9 l$ L4 H+ y. B, @D、主文件无序，索引表无序
4 k8 z7 f- K" R* Y3 H* [$ O正确资料:

( k" K7 e; C8 r
% a5 i6 {6 v5 k* R第3题,二维数组A按行优先顺序存储，其中每个元素占1个存储单元。若A［1］［1］的存储地址为420，A［3］［3］的存储地址为446，则A［5］［5］的存储地址为
2 m$ ]! A- s) g: [7 LA、470
! w8 I2 l, j+ N: V" t# |, I# lB、471
$ K# z& I( [" x4 }; u$ c, CC、472
D、473
& O, f0 {# c6 `, x2 z" d4 l正确资料:

/ u4 f/ x+ u+ n3 H6 N
第4题,在单链表中，指针p指向元素为x的结点，实现"删除x的后继"的语句是
A、p=p-next;
B、p-next=p-next-next;
C、p-next=p;
3 @1 U4 I& o$ q. I1 R: @D、p=p-next-next;
正确资料:
% ]) l$ j' E' ]0 N7 l

资料来源：谋学网（www.mouxue.com）,引入二叉线索树的目的是
A、加快查找结点的前驱或后继的速度
B、为了能在二叉树中方便的进行插入与删除
! \( a1 b& r* y% r* |& d( {C、为了能方便的找到双亲
4 Z. X" Y- H2 a; xD、使二叉树的遍历结果唯一
7 G5 p! k( U. P* _正确资料:


. g) q+ x/ e5 c' d4 Z4 d第6题,一棵树高为K的完全二叉树至少的结点是
7 P! x; D+ @9 s6 M+ T. lA、2k -1
B、2k-1 -1
C、2k-1
D、2k
; Q% f$ m( d1 `- f( @/ x( H: M0 K正确资料:

6 t& D8 m0 G# @! D1 R% m# g, B
( {- p6 _9 \  b  `5 E6 ~& P第7题,下列查找算法中，平均查找长度与元素个数n不直接相关的查找方法是
A、分块查找
  l! B1 Y9 f4 z7 mB、顺序查找
C、二分查找
9 q' s+ b. K7 ~. m$ U/ @9 UD、散列查找
正确资料:
3 R" [8 I# R5 e4 j9 I$ o

第8题,某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E 则该二叉树对应的森林包括的树的棵树是
) h, N/ @# d) D; M2 h! |8 TA、1
. e) c0 s- o5 UB、2
* J; a- U: ?6 RC、3
D、4
正确资料:

) n& H3 X8 R) c% q. K
第9题,已知循环队列的存储空间为数组data[21]，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为
( Q& ?3 W* n1 A! U+ G& ?. lA、5
B、6
C、16
D、17
% m0 ]; N4 V( |9 K$ X+ D, ]正确资料:
9 j' L; l( U+ d" }6 S' T$ A' _
( h8 R5 S; X9 e% Y
( s# ^3 {7 K4 a资料来源：谋学网（www.mouxue.com）,在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为
. ]4 A: W7 N3 B8 `A、n-i+1
B、i
C、i+1
$ @! h9 [3 \( nD、n-i
正确资料:

) R4 D" e$ ?, \; I0 n6 A2 f
第11题,从逻辑上可以把数据结构分为两大类，即
+ ]4 Q4 ?( s/ N6 FA、动态结构、静态结构
B、顺序结构、链式结构
C、线性结构、非线性结构
) W  z2 `- u5 e, JD、初等结构、构造型结构
* v8 w$ R# p. X' U/ K: M0 I) y正确资料:


4 @, s  W1 M3 Q6 `) @2 z资料来源：谋学网（www.mouxue.com）,如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用
! D4 K5 x+ p, w) s; oA、深度优先搜索算法
/ R# H" o8 H/ t9 \9 s8 uB、广度优先搜索算法
/ R/ Y/ T% M9 HC、求最小生成树的prim算法
6 H4 q3 k( o# K+ lD、拓扑排序算法
, C6 W5 M! f; \7 ]3 g正确资料:


, f9 d$ R) a1 {, ~. }5 O第13题,为便于判别有向图中是否存在回路，可借助于
A、广度优先搜索算法
B、最小生成树算法
C、最短路径算法
D、拓扑排序算法
% g7 i# o; g  y5 u1 ]正确资料:
' M# y& E+ v& Z3 c7 T- ?) b

第14题,队列和栈的主要区别是
. v$ c: g; b' j9 h* _' iA、逻辑结构不同
B、存储结构不同
C、所包含的运算个数不同
D、限定插入和删除的位置不同
2 g. x; L; E5 N* G$ [. b正确资料:


0 n$ i2 q+ y, b$ @资料来源：谋学网（www.mouxue.com）,在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p-next-next=  head,则
$ Y/ K4 d$ K( U+ N  aA、p指向头结点
+ G; s, V6 h* ~# UB、p指向尾结点
C、p的直接后继是头结点
* @& N4 Z9 d/ ~. LD、P的直接后继是尾结点
; P+ o1 G/ G4 ?& t2 T/ ?正确资料:

7 x, s. {6 U5 h7 ?  @) c6 \6 M, a
" T0 l  z( F( o+ ?. j第16题,若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上
6 C( b5 Z. [( p4 q  yA、操作的有限集合
0 s/ G' Y, r& \8 ]' n. c# DB、映象的有限集合
C、类型的有限集合
D、关系的有限集合
正确资料:


第17题,通常将链串的结点大小设置为大于1是为了
A、提高串匹配效率
B、提高存储密度
: K1 D  H6 H! d0 RC、便于插入操作
D、便于删除操作
! s% \' w- q. ~6 [$ x9 V3 m正确资料:

2 d$ J: @# r  h  y( A  f
第18题,对长度为n的关键字序列进行堆排序的空间复杂度为
' C- d( e0 t) y5 nA、O（log2n）
5 M' L$ Q8 o8 d/ a5 k* BB、O（1）
C、O（n）
1 i$ y2 l4 D. RD、O（n*log2n）
正确资料:

$ j3 e2 e$ Y& d: v
第19题,在一个带权连通图G中，权值最小的边一定包含在G的
0 o) N- g% W' YA、最小生成树中
B、深度优先生成树中
C、广度优先生成树中
& t6 P( ?7 I  p  p3 KD、深度优先生成森林中
$ e* D4 v6 i- u. i7 w正确资料:
4 Q6 k2 ?' }' z7 ^; _( X% z

) r: q. N$ @9 u) x3 E1 ?; @' p1 h资料来源：谋学网（www.mouxue.com）,假设以数组A[m]存放循环队列的元素。已知队列的长度为length，指针rear指向队尾元素的下一个存储位置，则队头元素所在的存储位置为
! g- j+ W8 t! D2 |, g" t+ pA、(rear-length+m+1)％m
1 t4 q& Y9 J; {  W7 I" UB、(rear-length+m)％m
C、(rear-length+m-1)％m
& ^; X( t# @7 i) f7 cD、(rear-length)％m
/ H5 M2 t$ s; p* }正确资料:


0 f, \! o' ]8 g/ J  L5 N


5 m3 d% H/ z2 n9 J, \; `& W  N! M



) E$ i9 q) P6 [
% N. l, P0 U1 Y* @5 N4 U
8 P( C: e$ l8 m# t$ J
* u4 ?  q1 r$ v% }7 M' f
$ V( `5 @9 ]# l3 X