22年春东北大学《数据结构Ⅱ》在线平时作业3

admin

资料来源：谋学网（www.mouxue.com）数据结构Ⅱ-[东北大学]《数据结构Ⅱ》在线平时作业3
. L3 y8 I: d9 ?/ @! [4 k试卷总分:100    得分:100
, `& Y, g& e. D( S$ n" D# V第1题,一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为
A、O(n)
& m2 Y* G. \$ m; HB、O(e)
C、O(n+e)
D、O(n2)
正确资料:


第2题,索引非顺序文件的特点是
" c/ e8 S( d! U) s5 T& y) TA、主文件无序，索引表有序
B、主文件有序，索引表无序
" G: o: j# H/ e1 WC、主文件有序，索引表有序
) H) |% F4 N2 m) ?6 ?' e$ WD、主文件无序，索引表无序
7 Z' ]' c6 \3 r2 M) d9 ~: k正确资料:
8 r! i% c$ t& r& t1 a  K8 J4 ^) h

第3题,二维数组A按行优先顺序存储，其中每个元素占1个存储单元。若A［1］［1］的存储地址为420，A［3］［3］的存储地址为446，则A［5］［5］的存储地址为
" l  q3 T. O+ _6 W' [A、470
( s: [* j! O, @0 VB、471
C、472
6 h# w6 i1 x/ Q& e! oD、473
8 G+ K$ F' j4 H8 z& V正确资料:
4 p7 M* A7 y* g5 F5 b! }; i" J, s

第4题,在单链表中，指针p指向元素为x的结点，实现"删除x的后继"的语句是
7 l) c9 o3 n+ \$ b; qA、p=p-next;
$ _% S" ~' Q. l% h8 h5 T+ ^B、p-next=p-next-next;
C、p-next=p;
D、p=p-next-next;
正确资料:

/ w/ Z  C3 D& T+ n; `/ \6 C6 P
2 n5 N( X& Z7 Z! Z* O/ m- _& e资料来源：谋学网（www.mouxue.com）,引入二叉线索树的目的是
! L  @' }! F2 V- Q$ W+ x2 aA、加快查找结点的前驱或后继的速度
B、为了能在二叉树中方便的进行插入与删除
$ Q# W- F9 P: i. KC、为了能方便的找到双亲
- O; p5 o$ H6 U4 ND、使二叉树的遍历结果唯一
正确资料:
# E; F  ~$ B6 A

第6题,一棵树高为K的完全二叉树至少的结点是
A、2k -1
B、2k-1 -1
; k6 x8 R4 b5 G  }: }C、2k-1
D、2k
正确资料:
+ b% n( J+ B! n: b

第7题,下列查找算法中，平均查找长度与元素个数n不直接相关的查找方法是
  ?3 v5 A( a$ OA、分块查找
B、顺序查找
" p) U3 _% b% l8 UC、二分查找
! z3 h/ S( d' r8 Y% D$ [( gD、散列查找
) F) {" _2 M$ W$ l) Q+ @2 }正确资料:

. y: q! |9 H% L
' h3 C# c( }3 _+ ^第8题,某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E 则该二叉树对应的森林包括的树的棵树是
A、1
/ Y0 r, Y2 ~- F' K' o' e4 fB、2
  |, |/ ]1 a' D4 A) i- V9 c8 L* Y$ \. \C、3
D、4
正确资料:


第9题,已知循环队列的存储空间为数组data[21]，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为
A、5
B、6
8 Z" o" X3 m. y8 I: f( NC、16
; b  C1 [. v" J4 @6 RD、17
+ V/ L2 f7 e0 Q3 o正确资料:
* |  T3 Z4 ^# v/ P* d* [  m+ I
" K: u$ r) e  y  c, t7 J- v
: Y, Z( H, [+ f1 |资料来源：谋学网（www.mouxue.com）,在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为
0 y5 }( @8 v. E) b% z/ V* _1 r! FA、n-i+1
B、i
9 K  u( q6 ]$ I  q4 ?' Z' xC、i+1
D、n-i
5 @; J/ l8 i. d; c0 p% R; z, j( L% {% D正确资料:

2 Y! F, F2 u  Y. ?
第11题,从逻辑上可以把数据结构分为两大类，即
A、动态结构、静态结构
2 }( I6 X' j3 p8 d1 d9 O2 oB、顺序结构、链式结构
+ f( |- l4 {* _7 b* x' T3 o% `C、线性结构、非线性结构
/ h3 u, `6 F. g2 g& a4 {/ X" F$ Y# WD、初等结构、构造型结构
正确资料:
* u# i2 l& W  p8 Q/ ^; F0 J2 m
" n* A/ L* Z3 E" O' b# v! q
7 C0 C5 k7 m1 ^) a+ a资料来源：谋学网（www.mouxue.com）,如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用
8 B. j) a* ~7 f5 H- cA、深度优先搜索算法
; a" |+ l7 Y  T4 m# dB、广度优先搜索算法
C、求最小生成树的prim算法
D、拓扑排序算法
3 _# s' @' J. h3 \6 N正确资料:

' q4 W8 A9 a" ~) ]5 E, ^
第13题,为便于判别有向图中是否存在回路，可借助于
& ~2 B9 \$ B: w: I. t' u7 B2 q( xA、广度优先搜索算法
B、最小生成树算法
  m% `- E# o2 ?/ AC、最短路径算法
D、拓扑排序算法
5 T$ y, L/ H% l  q! i6 x正确资料:


! b, S9 K5 u3 s* w2 |4 a& |* ~) i第14题,队列和栈的主要区别是
4 o5 H/ ~; A" {6 ]/ BA、逻辑结构不同
) o9 y4 S- O: k" v7 zB、存储结构不同
& o$ w5 f" |! \4 lC、所包含的运算个数不同
$ M1 j0 q6 B/ {6 h7 k2 J* bD、限定插入和删除的位置不同
. x! C$ C3 a1 t6 P" y' J正确资料:
2 u4 y8 v! p& U8 m2 T) o/ U

5 H5 J" J7 W; r; B资料来源：谋学网（www.mouxue.com）,在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p-next-next=  head,则
& _/ ~2 h3 z0 ?8 S! S# r3 cA、p指向头结点
B、p指向尾结点
$ l" z  D. k# V& WC、p的直接后继是头结点
& h& I: ]8 L0 o9 b/ X, QD、P的直接后继是尾结点
4 i; _$ }) h, K0 G正确资料:


第16题,若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上
) {. A0 I5 x2 d: f' y( mA、操作的有限集合
, [) m' h8 K, ~( K- N1 C1 j+ @B、映象的有限集合
C、类型的有限集合
D、关系的有限集合
3 j5 c- }; I/ c9 ~5 H. \正确资料:
% Y7 M3 [' z7 C& S. R
$ _) Q8 {& Q# B5 K8 E
第17题,通常将链串的结点大小设置为大于1是为了
* M4 j9 @0 T. R  \' \A、提高串匹配效率
2 y5 \, M* r9 a4 p' A" F9 d. IB、提高存储密度
5 }; y! B9 B+ h" p$ s( uC、便于插入操作
D、便于删除操作
正确资料:

9 g  C4 Z3 T$ f- z, o
第18题,对长度为n的关键字序列进行堆排序的空间复杂度为
A、O（log2n）
$ k4 C, I6 y0 a1 i7 `* P2 N2 c! h8 `B、O（1）
2 z( f0 U4 r# }C、O（n）
D、O（n*log2n）
正确资料:
* t3 ~  }1 @4 N

! ?3 R, {9 p5 U2 w5 Z+ X0 K4 w第19题,在一个带权连通图G中，权值最小的边一定包含在G的
A、最小生成树中
2 z; j, S$ q: B% |; WB、深度优先生成树中
C、广度优先生成树中
D、深度优先生成森林中
正确资料:


资料来源：谋学网（www.mouxue.com）,假设以数组A[m]存放循环队列的元素。已知队列的长度为length，指针rear指向队尾元素的下一个存储位置，则队头元素所在的存储位置为
- V- B% @* O' K* l, FA、(rear-length+m+1)％m
, {& q1 n  \% M* o/ PB、(rear-length+m)％m
C、(rear-length+m-1)％m
) s% e& i. }& ]- `D、(rear-length)％m
正确资料:
1 p! @/ |2 p, `0 m/ U


( B( r) K/ n, {3 x



5 O3 f9 D8 }) f) D0 g# g( t
; O2 r) `+ G6 V8 H+ ^6 k
$ S! ^5 {/ J# ~2 C
4 A0 \) }% O" ~



5 e# h" m. y+ H5 G. U1 T9 T