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

admin

资料来源：谋学网（www.mouxue.com）数据结构Ⅱ-[东北大学]《数据结构Ⅱ》在线平时作业3
试卷总分:100    得分:100
第1题,一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为
' X! N. `6 A/ [( y3 DA、O(n)
9 g( G9 I* _  Z6 J! v& ?: @7 U. k5 FB、O(e)
5 S* }: K# |- z  J4 h4 G! VC、O(n+e)
D、O(n2)
3 r3 e2 u' U; X; m) y正确资料:


8 A- k! {  F$ O" L$ i4 }+ s第2题,索引非顺序文件的特点是
8 p- Y( R6 {* V& l' BA、主文件无序，索引表有序
B、主文件有序，索引表无序
6 p" j! I4 W/ l9 o0 y1 V. hC、主文件有序，索引表有序
D、主文件无序，索引表无序
; @+ H1 Y% E; P& c' t4 l8 M! }正确资料:


第3题,二维数组A按行优先顺序存储，其中每个元素占1个存储单元。若A［1］［1］的存储地址为420，A［3］［3］的存储地址为446，则A［5］［5］的存储地址为
A、470
B、471
C、472
D、473
正确资料:
" l- }8 a6 u* D+ L4 ?  ]/ u& O

) T  H9 d# Z1 ]* O; n/ @第4题,在单链表中，指针p指向元素为x的结点，实现"删除x的后继"的语句是
! p/ G& G% [4 C4 f5 }# dA、p=p-next;
B、p-next=p-next-next;
C、p-next=p;
1 [8 f" P7 |3 b$ x# O5 ]- AD、p=p-next-next;
正确资料:
% b. V% R$ n, c! e& [3 s& Y
* b( j  @; I& F
- O" g4 g2 n# a# s资料来源：谋学网（www.mouxue.com）,引入二叉线索树的目的是
A、加快查找结点的前驱或后继的速度
B、为了能在二叉树中方便的进行插入与删除
0 R9 V8 m9 _. [' P6 `7 y+ S+ k, KC、为了能方便的找到双亲
D、使二叉树的遍历结果唯一
9 m- ?! m" ^2 h1 c/ w- q正确资料:
- a$ o1 Z9 r, O- p/ h

  y+ b9 d5 d- @0 P% H+ n( A第6题,一棵树高为K的完全二叉树至少的结点是
A、2k -1
B、2k-1 -1
C、2k-1
/ T. f- |* _  s5 P' J* v0 }; L  MD、2k
正确资料:
. I) ^# x" M" \1 F
4 e* U& ^2 [+ H6 n& X! N* k* O
, v; ]3 b* p2 h# u* f第7题,下列查找算法中，平均查找长度与元素个数n不直接相关的查找方法是
A、分块查找
% `+ b! a7 k# ?. a8 C% Q; [B、顺序查找
C、二分查找
% S% C! U! F5 @2 S* A7 E) [" m& ID、散列查找
* A! \7 b/ ]" _# P6 L( R正确资料:
: v9 R$ [+ Q  D6 f* e6 Z

" D) d1 z; H8 |& m$ m! D; }( T" ?第8题,某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E 则该二叉树对应的森林包括的树的棵树是
A、1
B、2
C、3
D、4
正确资料:

* I4 e  x( _% [* |; t5 h
+ @) Y5 T- K2 g% |- @第9题,已知循环队列的存储空间为数组data[21]，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为
A、5
2 {) v/ E* N' _$ E7 iB、6
" O3 B- \* Z4 P* C& {3 GC、16
2 }5 t2 q3 @5 [! S: ^D、17
正确资料:


资料来源：谋学网（www.mouxue.com）,在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为
A、n-i+1
B、i
) g) G9 D0 H2 f3 bC、i+1
. [/ G4 X: p/ |4 U. S& aD、n-i
! E8 S' h$ B2 P8 u- f! s- v. P正确资料:

2 I3 ^/ `6 D  {; p+ X9 k
第11题,从逻辑上可以把数据结构分为两大类，即
. H3 r0 g& i# r7 `4 h* }A、动态结构、静态结构
B、顺序结构、链式结构
C、线性结构、非线性结构
/ s0 h+ L* e! x4 t: jD、初等结构、构造型结构
. @* M. @5 H' p1 o: S正确资料:

" ]) i. S* U2 @( j4 K# Z! {
# m5 d6 {! r! }& T6 ?! I4 Y资料来源：谋学网（www.mouxue.com）,如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用
A、深度优先搜索算法
B、广度优先搜索算法
3 O  i6 G* ^- f' X! y" OC、求最小生成树的prim算法
6 X# l5 H4 I2 P! c. g9 vD、拓扑排序算法
1 @8 l% q2 o5 P& {正确资料:


6 T$ ^- d( B2 H, s, Q第13题,为便于判别有向图中是否存在回路，可借助于
A、广度优先搜索算法
B、最小生成树算法
C、最短路径算法
D、拓扑排序算法
正确资料:


: e5 V- N, |6 i# u1 V- I, T9 N第14题,队列和栈的主要区别是
3 R+ ?- T, {7 iA、逻辑结构不同
B、存储结构不同
C、所包含的运算个数不同
D、限定插入和删除的位置不同
正确资料:

0 a' P- O2 L6 ]3 j8 O5 z0 Y) N
( b, C  V3 t/ E" L3 i资料来源：谋学网（www.mouxue.com）,在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p-next-next=  head,则
8 L9 r8 ^9 _3 Y) v- gA、p指向头结点
B、p指向尾结点
C、p的直接后继是头结点
! o: H7 @' @! e( }, T, ^D、P的直接后继是尾结点
3 i3 S) {. Q0 n0 y正确资料:
5 g% V) }" }0 b4 j7 i* j' ?
5 W" o- m, Z: m& Y: J
第16题,若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上
A、操作的有限集合
0 w0 p' O) A9 dB、映象的有限集合
C、类型的有限集合
D、关系的有限集合
: D+ ^- g4 u# F. G! N) i( a, M正确资料:


5 s" w# s' k6 H8 ^0 S  `第17题,通常将链串的结点大小设置为大于1是为了
A、提高串匹配效率
B、提高存储密度
2 [& K4 v& S; bC、便于插入操作
D、便于删除操作
正确资料:


第18题,对长度为n的关键字序列进行堆排序的空间复杂度为
A、O（log2n）
' }( h+ Z- }3 p. GB、O（1）
( u  X; A2 u9 B$ r, pC、O（n）
( ]8 |" ^0 t, }# S7 tD、O（n*log2n）
: G+ R0 L0 R/ q  |! ^正确资料:

2 U2 Q; o0 h/ |
. a' m$ P7 H7 v第19题,在一个带权连通图G中，权值最小的边一定包含在G的
A、最小生成树中
B、深度优先生成树中
C、广度优先生成树中
D、深度优先生成森林中
+ J) T) g- b' s$ F- ?0 I正确资料:
# v+ u3 Q  ~- w; M# E# c' p

资料来源：谋学网（www.mouxue.com）,假设以数组A[m]存放循环队列的元素。已知队列的长度为length，指针rear指向队尾元素的下一个存储位置，则队头元素所在的存储位置为
A、(rear-length+m+1)％m
( |7 ?* {( S* E) D) K5 r# t- iB、(rear-length+m)％m
0 B; W. F6 |7 UC、(rear-length+m-1)％m
3 p/ [+ c& a5 WD、(rear-length)％m
正确资料:
9 u  e: |2 s: K1 T( c" ?" r/ ^; I

) k  F9 Y0 S$ m) m' l9 L0 ]
# K3 Q' c; X/ D  y7 j+ \: J; R$ A


6 [, ^' J7 s1 G* y4 D


6 {) A8 d8 y& k5 c$ @
5 k/ C& p' ]0 ^! q2 ^0 g