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

admin

资料来源：谋学网（www.mouxue.com）数据结构Ⅱ-[东北大学]《数据结构Ⅱ》在线平时作业3
试卷总分:100    得分:100
第1题,一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为
A、O(n)
B、O(e)
* J: Z5 |+ h% vC、O(n+e)
D、O(n2)
正确资料:

8 p8 t. @4 o3 k, N
第2题,索引非顺序文件的特点是
A、主文件无序，索引表有序
B、主文件有序，索引表无序
9 B. H; z5 E+ G2 ?- D9 @8 qC、主文件有序，索引表有序
0 Y& R$ l2 W$ M+ r9 dD、主文件无序，索引表无序
正确资料:
4 I  b' `1 ?% m. ]3 ^

( G* l, ?# ^$ {9 a% {第3题,二维数组A按行优先顺序存储，其中每个元素占1个存储单元。若A［1］［1］的存储地址为420，A［3］［3］的存储地址为446，则A［5］［5］的存储地址为
A、470
2 {% Z* F( j3 q: M/ x' v5 VB、471
C、472
D、473
正确资料:

( a* g# e9 @$ K8 R3 `% O1 j4 l
* Y7 d7 Y0 \# G0 U( A% A第4题,在单链表中，指针p指向元素为x的结点，实现"删除x的后继"的语句是
) V* F- a7 c" p% B8 W1 T: _6 \A、p=p-next;
B、p-next=p-next-next;
C、p-next=p;
. ]$ n/ W- d. }+ u: _1 C& xD、p=p-next-next;
正确资料:


% E$ F6 m; L% ]5 T' f: R5 @# I$ B; Y资料来源：谋学网（www.mouxue.com）,引入二叉线索树的目的是
A、加快查找结点的前驱或后继的速度
3 d8 w  c/ I+ j" e  ~* iB、为了能在二叉树中方便的进行插入与删除
) m0 l+ I( O$ y! ?7 eC、为了能方便的找到双亲
) S. b/ ~' ~* }9 mD、使二叉树的遍历结果唯一
正确资料:
/ z; d# Q  i( `! ~
+ P: K+ H! T) M+ q: V$ M
第6题,一棵树高为K的完全二叉树至少的结点是
A、2k -1
B、2k-1 -1
4 b% X) ]& d- d  r0 a  Q% M/ hC、2k-1
D、2k
1 w+ ^  V: f& Y: u6 N正确资料:


第7题,下列查找算法中，平均查找长度与元素个数n不直接相关的查找方法是
8 ?- _( {$ |' r! z8 p/ O* K  tA、分块查找
B、顺序查找
4 b9 i9 J+ t2 [C、二分查找
' U0 M- t2 |' V  }/ }1 h5 u, cD、散列查找
正确资料:


第8题,某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E 则该二叉树对应的森林包括的树的棵树是
A、1
B、2
  c1 Z- s# q7 T8 @0 rC、3
D、4
正确资料:


第9题,已知循环队列的存储空间为数组data[21]，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为
6 F5 B4 V6 a! }! r" ]7 X/ bA、5
B、6
' [4 a6 `: e( M  x4 a- RC、16
2 R5 p9 I5 m( v8 |9 F0 B5 yD、17
正确资料:

  n; D% t  a! k- F1 l7 L& D/ Z
资料来源：谋学网（www.mouxue.com）,在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为
: k# ?" t& W; H' CA、n-i+1
) l) N. Q" y% p3 m# ?B、i
C、i+1
D、n-i
+ D- o/ A8 ^/ p7 C. i  {正确资料:


第11题,从逻辑上可以把数据结构分为两大类，即
A、动态结构、静态结构
& |# W. a8 y: w" lB、顺序结构、链式结构
. X+ q: z* g( m, N6 z) Y* Y0 |C、线性结构、非线性结构
/ p/ N: S8 C+ qD、初等结构、构造型结构
正确资料:

  B! z& x2 a+ n, R0 G3 _# \- E
资料来源：谋学网（www.mouxue.com）,如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用
, q7 F1 r, C0 ?9 n9 ~A、深度优先搜索算法
8 ^4 d7 ?  {* v) OB、广度优先搜索算法
C、求最小生成树的prim算法
! U  x$ d# @; z# {- B+ ?9 AD、拓扑排序算法
7 |0 I1 Q: [$ a' j( D( h" f正确资料:
: {9 D! n# O+ j' ]; m
2 y: ]; g% T8 C
第13题,为便于判别有向图中是否存在回路，可借助于
A、广度优先搜索算法
4 y7 ^2 g# I6 O8 ^( z! C  N- vB、最小生成树算法
C、最短路径算法
D、拓扑排序算法
% g; B$ {9 A& y* b4 x' q正确资料:

: R4 a8 x& z, S  v: i3 }
$ r: q$ j/ I) x9 R" m第14题,队列和栈的主要区别是
A、逻辑结构不同
B、存储结构不同
4 S% A$ p$ n6 e% v: a7 F) h$ zC、所包含的运算个数不同
D、限定插入和删除的位置不同
正确资料:

5 @3 S' U1 l( h1 z  D
. f2 Q) ]9 q/ ]- I1 q资料来源：谋学网（www.mouxue.com）,在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p-next-next=  head,则
8 A5 ~. ?2 G1 yA、p指向头结点
# b* P% }: ?+ _' V$ }$ z- e  lB、p指向尾结点
+ t; s1 v+ x2 I  l. C! y% w! gC、p的直接后继是头结点
  _6 w, J. j+ K- k+ CD、P的直接后继是尾结点
. w2 d% q( E' f- x6 H9 }正确资料:
5 @5 ^7 Z# w# _2 M$ C
7 B! h9 n( I1 L* \( F0 }
% |$ g# m1 y4 F第16题,若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上
. e& g* p+ K- K  |$ |A、操作的有限集合
B、映象的有限集合
C、类型的有限集合
D、关系的有限集合
正确资料:

# `: o; b& A" V8 j0 e! Y
第17题,通常将链串的结点大小设置为大于1是为了
A、提高串匹配效率
' u( A4 w: m$ d; x: w& XB、提高存储密度
C、便于插入操作
" m% c) d9 E7 k( g; MD、便于删除操作
* t) C: D, ?' M" e正确资料:

: ^  a: E! n9 _
第18题,对长度为n的关键字序列进行堆排序的空间复杂度为
A、O（log2n）
B、O（1）
C、O（n）
& Q( \" R+ F! g8 UD、O（n*log2n）
正确资料:
) W( H1 {, A8 c' m, e& ]
+ @: G  @! ?8 e; J1 B! _
第19题,在一个带权连通图G中，权值最小的边一定包含在G的
A、最小生成树中
' E& G& Y# X& r8 ZB、深度优先生成树中
- M7 h0 Y: [  C2 QC、广度优先生成树中
D、深度优先生成森林中
. e1 y; g( _+ [% P3 O正确资料:


( d: r! g9 X  J- ?资料来源：谋学网（www.mouxue.com）,假设以数组A[m]存放循环队列的元素。已知队列的长度为length，指针rear指向队尾元素的下一个存储位置，则队头元素所在的存储位置为
A、(rear-length+m+1)％m
$ _; r: @7 ]% n4 cB、(rear-length+m)％m
C、(rear-length+m-1)％m
D、(rear-length)％m
2 |3 Y& q  [& {3 V$ y- {正确资料:





% o0 L2 `4 E% i- O# M" H% M5 o

; ^* c- W4 Z3 D) M* t; z0 w& J# p3 W
, g0 I) k/ K0 n1 b  P& l# k


7 F5 `7 B# c) z' e7 v1 W' m* M
' M  T! ?/ k' M8 Y