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

admin

资料来源：谋学网（www.mouxue.com）数据结构Ⅱ-[东北大学]《数据结构Ⅱ》在线平时作业1
试卷总分:100    得分:100
第1题,用二叉链表表示具有n个结点的二叉树时值为空的指针域的个数为
; k! I7 k+ D$ y% |: \2 vA、n-1
% i+ a; J- I. i! C: uB、n
C、n+l
7 l  y  H, y# u) w. ~. yD、2n
正确资料:


) R; H7 x5 f: |0 t; f3 G5 L7 E+ ]第2题,已知含10个结点的二叉排序树是一棵完全二叉树则该二叉排序树在等概率情况下查找成功的平均查找长度等于
A、1.0
B、2.9
  P) I2 `; q$ I) l/ kC、3.4
) L6 D& R/ ]9 \3 AD、5.5
正确资料:

% y- F. A4 r  K0 P; y
第3题,对长度为n的关键字序列进行堆排序的空间复杂度为
. L; S) [8 b$ n# L$ ]: WA、O（log2n）
B、O（1）
: Y/ z% \+ d4 m4 L2 OC、O（n）
8 m) v! B+ {" ?D、O（n*log2n）
正确资料:
2 t' h5 Y' K5 W

第4题,已知含6个顶点v0v1v2v3v4v5的无向图的邻接矩阵如图所示则从顶点v0出发进行深度优先遍历可能得到的顶点访问序列为
A、.(v0，v1，v2，v5，v4，v3)
6 e; q: ^- U* a: }6 d  mB、(v0，v1，v2，v3，v4，v5)
+ B& |: D1 Q, pC、(v0，v1，v5，v2，v3，v4)
+ c( c* T+ X! AD、.(v0，v1，v4，v5，v2，v3)
正确资料:

% }' M3 L! N" ]- H; D
& N2 U" c8 q* Q+ J. w* N% @资料来源：谋学网（www.mouxue.com）,n个顶点的有向完全图中含有向边的数目最多为
A、n-1
" G# G* {; N. Q( EB、n
C、n(n-1)/2
/ Z4 O, J$ a9 \5 |5 sD、n(n-1)
正确资料:
- m8 L1 r$ p; k$ ?) L( [7 Q+ v7 Y

6 m4 X' e# P9 `第6题,在以单链表为存储结构的线性表中数据元素之间的逻辑关系用
A、数据元素的相邻地址表示
8 H# _: I: L) n7 l: d, a" E) XB、数据元素在表中的序号表示
# k  p" S5 ^4 XC、指向后继元素的指针表示
D、数据元素的值表示
( @& [& {4 {% Z  {6 @正确资料:
$ U$ a$ i! Y8 ~) S7 s; C* R8 P# Y! m

第7题,倒排文件的主要优点是
A、便于进行插入和删除运算
B、便于进行文件的恢复
8 T/ O; d( |9 s4 ]$ O: cC、便于进行多关键字查询
) |: U8 ~1 w& s3 c" aD、节省存储空间
8 `4 F+ ]" X3 m: t( e" B0 h( a$ t9 K9 ]正确资料:
, `, j/ Y! F& {8 _* [* J* K1 |2 f

. Q# N2 l% L* l( U* P2 s第8题,已知二叉树的先序序列为ABDECF中序序列为DBEAFC则后序序列为
A、DEBAFC
B、DEFBCA
C、DEBCFA
+ S$ _. g" n! pD、DEBFCA
正确资料:
! b8 C1 l1 H& i

第9题,若以1234作为双端队列的输入序列则既不能由输入受限的双端队列得到也不能由输出受限的双端队列得到的输出序列是
+ ], \) B% Y: o( T6 `; j  ZA、1234
B、4132
C、4231
D、4213
正确资料:


+ s, a, L9 B, e- g* n资料来源：谋学网（www.mouxue.com）,已知循环队列的存储空间为数组data[21]且当前队列的头指针和尾指针的值分别为8和3则该队列的当前长度为
. v1 P5 U1 i6 `9 i8 NA、5
B、6
4 a/ I7 j6 ^/ T6 vC、16
, B$ i3 ]2 N8 I4 O. b0 N/ UD、17
正确资料:


第11题,一棵具有n个结点的完全二叉树的树高度深度是
A、?logn?+1
( L4 u+ m8 Z7 U, [0 H5 E. u4 ^B、logn+1
C、?logn?
D、logn-1
正确资料:
* Q- B: r% G2 I% j" P% c4 a
$ V( Z! D/ k6 E3 w8 ?2 Z% Q
9 n. ]- o- V, i资料来源：谋学网（www.mouxue.com）,在图采用邻接表存储时求最小生成树的Prim算法的时间复杂度为
A、O(n)
B、O(n+e)
C、O(n2)
D、O(n3)
正确资料:


第13题,已知广义表LS=abcdef运算head和tail函数取出元素e的运算是
A、head(tail(LS))
B、tail(head(LS))
! t' @$ V( M( v$ ZC、head(tail(head(tail(LS))))
D、head(tail(tail(head(LS))))
, U3 A3 N. L2 e' L正确资料:
5 G1 i! ~# Y+ h1 n9 ?! ?+ h/ w

, }. t- \: i$ z/ D) R4 b4 k/ W第14题,稠密索引是在索引表中
A、为每个记录建立一个索引项
& v) h  L1 D! q/ j0 t) N% i# F) b1 KB、为每个页块建立一个索引项
5 o3 j" w6 t# N" w2 o3 R. kC、为每组记录建立一个索引项
D、为每个字段建立一个索引项
正确资料:


3 u& r1 U4 _6 I: a& _  z( {0 V资料来源：谋学网（www.mouxue.com）,如果求一个连通图中以某个顶点为根的高度最小的生成树应采用
A、深度优先搜索算法
B、广度优先搜索算法
- Q+ o2 M' V& ?1 i9 }7 bC、求最小生成树的prim算法
D、拓扑排序算法
正确资料:
4 N# L; x: N' t# ]7 z: o
, r- W1 g6 O& d9 B: q; F
7 Z- G6 ?0 `% `' d( ]% c" D第16题,下述哪一条是顺序存储结构的优点
8 k, p8 o8 [- L) g5 ^. u. F, fA、存储密度大
( z# B/ z* v- l' NB、插入运算方便
) W' I6 E. x4 }C、删除运算方便
6 `$ j; W8 Q- ^D、可方便地用于各种逻辑结构的存储表示
正确资料:

: a  X3 g" t1 v3 D! D2 L+ @/ |
: W7 t: o  F% @% E第17题,判定"带头结点的链队列为空"的条件是
A、Q.front==NULL
B、Q.rear==NULL
) r, F, d- _& B! z1 D" \) wC、Q.front==Q.rear
1 d* O4 s. i) ~2 H  ~. w4 wD、Q.front!=Q.rear
正确资料:
! T9 r( t9 b# B+ ^1 r4 Y! _0 X

第18题,下列数据结构中属于非线性数据结构的是
A、栈
0 C9 e; z( W# c3 j! TB、队列
C、完全二叉树
D、堆
正确资料:

3 I$ _0 A6 x6 F9 q! z& K
, G! M( I& |8 S# }5 I第19题,二维数组A按行优先顺序存储其中每个元素占1个存储单元若A［1］［1］的存储地址为420A［3］［3］的存储地址为446则A［5］［5］的存储地址为
A、470
  i3 }# @; V. v% X8 L! q/ tB、471
$ V- t$ k8 n; k- y; cC、472
: K) j  h7 V: c, w( N2 e, @/ jD、473
正确资料:

( }: C# f/ s  h) H; D6 I
资料来源：谋学网（www.mouxue.com）,一棵完全二叉树上有1001个结点其中叶子结点的个数是
A、250
B、500
C、254
D、以上资料都不对
正确资料:



( A2 R) y) J( U8 v6 V


# ^& g( n8 a/ G9 S
, \" n4 M) {' o6 ^, a
2 @* g) {& M" w


0 o. ~6 b: L4 b% F! Z

7 H+ A& ~' u/ Z  B( ^* l% ?
5 k) Z$ h0 ^  h  _. {- G) S9 P