东北师范《数据结构》》21秋学期在线作业1答卷

admin

数据结构19春在线作业1-0001
1 \  t- V; \( Q! b8 y! w试卷总分:100  得分:100
7 N7 K0 z% H2 x1 m; h, g* k一、单选题 (共 20 道试题,共 60 分)
1.数据结构中的任一数据元素至多只有一个前驱和一个后继，该数据结构是 ( )
3 F" K$ Y8 E8 T7 W* wA.线性表
3 Z8 q" m. ?4 U( ?( wB.广义表
  U9 w2 b1 Z; Z- C* @+ a; X1 OC.树形结构
% h/ H4 B7 ?# G+ |D.图结构
正确资料:
% o/ S4 [0 O0 b4 Q" v- Y1 g4 i9 x
& [( e9 H) l" B2.插入、删除只能在同一端进行的线性表，称为 ( )。
3 \3 k2 K( `: B! {/ ?# Z' J3 [% uA.队列
; t. C0 y) B( eB.循环队列
1 L0 C5 k1 D3 Z4 cC.栈
D.循环栈
$ L( y) R% @% L0 x9 A正确资料

+ K, C+ n7 [" g$ X4 q3.任何一棵二叉树的叶结点在前序、中序和后序遍历序列中的相对次序 ( )。
A.不发生改变
  y8 m) Q4 I$ ?  O) [B.发生改变
C.稍有改变
5 G5 X% s: }/ S- L3 [% m% zD.不能确定
, O2 T' H9 f6 z正确资料:

4.在k叉树中，度为0的结点称为 ( )。
A.根
B.叶
C.祖先
* ~+ ^* Q" j9 b+ ]9 j3 uD.子孙
* K% L8 D" q) M  q2 W* K正确资料:
$ ~& i. `7 C0 [( _. U. W1 y
5.在下列排序算法中，哪一个算法的时间复杂度与记录初始排列无关 ()。
4 b% A4 O8 Q6 [" P) A/ `A.直接插入排序
9 s, A" n* b9 jB.冒泡排序
C.快速排序
D.直接选择排序
" p" R- {4 B9 d$ K9 n5 F: p正确资料来自谋学网（www.mouxue.com）
5 S5 i/ _7 O# U* R7 t; Q4 I* w
6.下面哪些方法可以判断出一个有向图是否有环（回路）? ()
A.广(宽)度优先遍历
6 E2 G1 K. q* v3 W# ?; AB.拓扑排序
C.求最短路径
' B7 [2 g6 G) W5 w4 s# bD.求关键路径
正确资料:

7.串是一种特殊的线性表，其特殊性体现在 ( )。
A.可以顺序存储
B.数据元素是一个字符
C.可以链接存储
; y! T+ \9 t4 P- `- _3 G  ]  c3 dD.数据元素可以是多个字符
* {1 x4 Z0 L+ a2 }: v* c正确资料:

8.head指向的带表头结点的单链表为空的判定条件是 ( )。
. u$ `; b7 F% U6 ]A.head = = NULL
) ~+ P- G6 u3 h( rB.head->next = = head
C.head ! = NULL
: A* D( H2 i, M( F5 ^2 ^# bD.head->next = = NULL
正确资料来自谋学网（www.mouxue.com）
- l$ K, ], }# U" l5 X* f
$ H# P( A3 L2 @6 X6 M* b# k& Q: A9.二叉树在线索化后，仍不能有效求解的问题是 ( )。
$ B% W. c! l4 _  TA.前序线索二叉树中求前序后继
B.中序线索二叉树中求中序前驱
C.中序线索二叉树中求中序后继
D.后序线索二叉树中求后序后继
' N+ L9 }+ D- h" w7 r. B正确资料来自谋学网（www.mouxue.com）

10.算法分析的两个主要方面是 ( )。
A.正确性与健壮性
. M8 N  e( d1 oB.可读性与可用性
0 B: f- i! B9 ^4 q3 KC.时间复杂度与空间复杂度
7 `( x# N' C# Y, a- t; bD.数据复杂性与程序复杂性
正确资料
6 a! R2 H1 ~! v) a$ \
11.下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序。( )
A.二叉排序树
" M7 p: f9 z1 `* Z9 U3 q8 ZB.哈夫曼树
C.AVL树
6 H; g0 Y! G% \9 o7 SD.堆
9 Z1 f! Y9 H) m2 f正确资料来自谋学网（www.mouxue.com）

8 I3 \6 d+ l) e12.设有100个关键字，用折半查找法进行查找时，最大比较次数为 ()。
/ m% T% i' ~0 c4 [0 H5 o! @A.6
; B8 G* x+ }* V5 u! NB.7
7 u0 b, u- X6 I. n# O) Z: tC.25
D.50
正确资料:

4 ]$ K) M1 N  z13.设根结点层次为1，某二叉树的结点前序序列和后序序列正好相反，则该二叉树一定是 ( )。
* [) s8 ~  r8 {9 VA.空或只有一个结点
B.高度等于其结点数
C.任一结点无左子女
D.任一结点无右子女
' |$ D6 M1 s* ?; B正确资料:

. [! s4 N; s& w. t14.n个结点的线索二叉树上含有的线索数为 ( )。
A.n-1
% E* p, L3 p) [- O# LB.n
C.n +1
D.2n
正确资料

, D/ m6 N9 q- h( b6 {" Q7 Z15.广义表 (( a , b , c , d ) ) 的表头是 ()。
& L" d/ ~8 H, V4 L$ K* }' l3 J# G  gA.a
B.( )
& V$ Z8 [3 I* L0 b: h/ G  }2 E6 GC.( a , b , c , d )
# Y; k( O3 m2 L; K4 hD.( b , c , d )
. E( E1 k) S" \, V, A7 l正确资料
# m8 N& C& l6 c
* D6 ~6 t* r& W; p& ^9 l, D16.将一个A [1..100, 1..100] 的三对角矩阵，按行优先次序存入一维数组B[1..298] 中，A中元素A [66, 65] 在数组B中的位置K为 () 。
0 \$ c3 ?4 M4 W- Q7 T& `8 Y& QA.193
% ]2 H, x. ?7 u* V4 IB.195
+ {/ r7 ^1 e9 |C.197
1 ~' Q) ^/ u0 fD.199
8 c0 O# u6 s0 Y% Z$ d( Y7 k8 V8 A正确资料:

$ n+ W& p" I' ]5 L0 d17.在链队列中，假设f和r分别为队首和队尾指针，则删除一个结点的操作是 ( )。
9 Z% ~; w3 l+ e, w* r. CA.r = f->next;
B.r = r->next;
! f8 P' J. Z7 h2 T9 [6 LC.f = f->next;
D.f = r->next;
5 v6 e  S, G$ D! W. A, w/ N! e% u正确资料

18.求图的最小(代价)生成树问题，考虑的是下面的哪一种图 ()。
A.无向图
B.有向图
  {: {+ Q8 _8 l: G6 [6 ~C.带权的无向图
D.带权的有向图
正确资料
9 W/ n2 a% G, k6 x( n
19.一个队列的入队序列是a、b、c、d，则队列的输出序列是 ( )。
* a; m7 H' U9 v7 S; ~A.abcd
- Y- q1 z' u4 `B.dcba
( K% t6 \* S) D( z) G2 {  WC.adcb
D.cbda
正确资料:

20.一个有向无环图的拓扑排序序列 () 是唯一的。
A.一定
B.不一定
C.可能
& r- L; Z- O& r: L1 l) jD.三者均不对
正确资料:

二、资料来源：谋学网（www.mouxue.com） (共 20 道试题,共 40 分)
21.数据的存储结构是数据的逻辑结构在计算机存储器上的实现，它是依赖于计算机的。
资料:正确
) @$ M% o( D+ h: w4 [
# o5 S& S- g7 [. l& T, b) @22.AOV网的含义是以顶点表示活动的网。
资料:正确
$ }3 b3 H/ g. h
23.在图G的最小生成树T中，可能会有某条边的权值超过未选边的权值。
资料:正确

24.循环链表不是线性表。
2 Y* Q0 V! g: d/ o9 |0 f7 ]7 a资料:错误
$ N9 e7 b& a: U. j6 ?
3 W1 c# ~( L, o$ u25.分块查找在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中的元素个数有关。
资料:正确
. ^9 m$ p* n6 F2 y, [: b
26.最佳二叉排序树是AVL树 ( 平衡二叉排序树 ) 。
  t9 r( ^1 f+ @# ~* N! H资料:正确

27.完全二叉树一定存在度为1的结点。
) l' b2 t9 G+ }8 x6 |3 ]! x6 A资料:错误
" [4 P/ a7 ~  s% H
' @& f9 U0 I) i9 r  z* c) o+ e8 B28.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
资料:错误

# m4 {1 [! D  ?6 {/ P29.链表中的表头指针与表头结点起到相同的作用。
: |$ m) @- t' C5 Y, F/ o9 T. e; m资料:错误
  |, k5 y+ L7 u1 u: }. X
/ [3 X1 B1 B1 y; H4 K) @" L! ~30.链接存储结构属动态存储方式。
0 l- E" [- e; L8 P* U) J资料:正确
2 g: W5 \$ @" g! L2 e
: Y+ g, Q( \9 \31.取顺序表的第i个元素的时间与i的大小无关。
9 k/ F( f. R: ]3 V* k. K9 X& X; L资料:正确
' A0 c$ C4 k& W+ a$ r: H
32.在指定结点之前插入新结点时，双链表比单链表更方便。
资料:正确

33.若哈希表(散列表)的负载因子α < l，则可避免冲突的产生。
& M7 L: X. W- X资料:错误
) E' p, _; d9 V& y+ `$ `- J
5 W8 ?2 o4 u. {3 [, ?' Y0 c34.二叉树的叶结点，在前序遍历、中序遍历和后序遍历下皆以相同的相对位置出现。
资料:正确

8 z" o0 T" G! V35.若输入序列为1, 2, 3, 4, 5, 6，则通过一个栈可以输出序列3, 2, 5, 6, 4, 1。
8 X5 B5 V' S7 B5 o* g2 B% I, ^资料:正确
% J& d/ X0 E/ e$ `3 @, }
36.数据的逻辑结构是指数据的各数据项之间的逻辑关系。
" W: G( h9 ^6 B: j& p! I; t2 j- D资料:错误
) F* ~+ ?6 D1 K8 {1 T& n& P; X
; ~; x& q2 }# r37.一个有向图的邻接表和逆邻接表中结点的个数可能不等。
资料:错误
  D( N" c: Q! W$ w/ b
38.后序线索二叉树是不完善的，要对它进行遍历，还需要使用栈。
资料:正确

39.用一维数组存储二叉树时，总是以前序遍历顺序存储结点。
' ]# R! U% s% K4 O资料:错误
- G% g. N* }8 T
40.任何一个递归过程都可以转换成非递归过程。
- F5 a! h0 j" b' v* @8 I! W资料:正确

6 S, ?) |: n+ H2 B' x

' V/ Z- c4 Q( l0 j
9 j" _$ k( F' ?




' X8 ?4 l& F: S: V7 S
' u- A7 \! r, n% L