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

admin

数据结构19春在线作业1-0001
试卷总分:100  得分:100
一、单选题 (共 20 道试题,共 60 分)
1.数据结构中的任一数据元素至多只有一个前驱和一个后继，该数据结构是 ( )
/ v1 {# ?  j$ S* F6 dA.线性表
B.广义表
C.树形结构
; A% ]/ I3 w8 u4 u2 f- t7 `! {D.图结构
正确资料:

2.插入、删除只能在同一端进行的线性表，称为 ( )。
A.队列
B.循环队列
C.栈
( S' k# E+ H8 RD.循环栈
正确资料
' J" U0 y; G2 t$ z$ `
0 J  d, b0 ~7 `# [- X% b5 G  i3.任何一棵二叉树的叶结点在前序、中序和后序遍历序列中的相对次序 ( )。
A.不发生改变
$ u5 U, F- W6 ~# M# ?1 @8 D$ SB.发生改变
: s4 b$ |. R5 |0 h1 p; s3 y. A6 qC.稍有改变
D.不能确定
正确资料:

4.在k叉树中，度为0的结点称为 ( )。
A.根
" W4 S9 J! R/ e; |B.叶
4 C" N: \: W" sC.祖先
D.子孙
正确资料:
! X; t+ B- q6 C! }; `
2 ~& ~9 K+ e' L; l, u  k; t5.在下列排序算法中，哪一个算法的时间复杂度与记录初始排列无关 ()。
6 n* x% V9 w3 U  }1 eA.直接插入排序
B.冒泡排序
- J7 L$ C8 `8 E: g' z0 Q1 }9 PC.快速排序
D.直接选择排序
. m1 ^" K) r# y9 o% d5 t' ]  c; N正确资料来自谋学网（www.mouxue.com）
5 e9 j3 o; @2 D6 a- y. n% H# ]3 T
6.下面哪些方法可以判断出一个有向图是否有环（回路）? ()
3 A7 G' B0 L- |) [5 h# aA.广(宽)度优先遍历
B.拓扑排序
C.求最短路径
' |; k1 y6 M2 h$ y5 R5 ]D.求关键路径
- o! p7 {* d- E8 v* j- Q  E; H% K正确资料:

" Q7 {0 ~% X4 [) {! Y# ~( H7.串是一种特殊的线性表，其特殊性体现在 ( )。
) D* H  I, ~& g% sA.可以顺序存储
$ Y" W$ a' W: X( EB.数据元素是一个字符
C.可以链接存储
5 v$ |3 w! @6 a  ?* qD.数据元素可以是多个字符
正确资料:

0 n6 c# G& C, a4 T7 a3 b( X) T2 \8.head指向的带表头结点的单链表为空的判定条件是 ( )。
3 P6 o3 H2 c, [A.head = = NULL
8 M, O+ v/ R  z) g4 MB.head->next = = head
  u! y4 B: v% [! m9 [8 b  }) ^C.head ! = NULL
  K" S1 |5 ]0 u/ p' x- r* yD.head->next = = NULL
- X8 d, q4 w0 ^. N正确资料来自谋学网（www.mouxue.com）
9 j' M" j5 R2 G1 Q
9.二叉树在线索化后，仍不能有效求解的问题是 ( )。
A.前序线索二叉树中求前序后继
B.中序线索二叉树中求中序前驱
; ~5 p# K5 D  Q/ |$ I) sC.中序线索二叉树中求中序后继
D.后序线索二叉树中求后序后继
& W2 B1 D, `0 Y正确资料来自谋学网（www.mouxue.com）

6 x+ U- Q/ R9 ~0 R9 C1 N" V10.算法分析的两个主要方面是 ( )。
/ r4 e" m% [! r% W% ^A.正确性与健壮性
$ ^2 }: }, E# v/ `$ N3 KB.可读性与可用性
C.时间复杂度与空间复杂度
D.数据复杂性与程序复杂性
; k- X- L: T4 b% h2 t4 l$ ~  i正确资料

/ O" J( V& c1 M- A+ Q4 s' c" O; Z11.下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序。( )
A.二叉排序树
8 C( U* b$ }- J3 aB.哈夫曼树
C.AVL树
. }1 W& l4 A9 P& aD.堆
正确资料来自谋学网（www.mouxue.com）
7 I' d; J; i( b% V# y
/ c: v, M& B# U12.设有100个关键字，用折半查找法进行查找时，最大比较次数为 ()。
A.6
B.7
C.25
8 w* Y' K: u3 t1 y/ U, gD.50
正确资料:
7 R1 ~; R  J8 A* G% d/ x* o
13.设根结点层次为1，某二叉树的结点前序序列和后序序列正好相反，则该二叉树一定是 ( )。
A.空或只有一个结点
B.高度等于其结点数
C.任一结点无左子女
& C+ l  x0 Q  l& X( G7 e# DD.任一结点无右子女
正确资料:
" N" \# H' n# n' F3 h
4 m; Z: X1 X0 }14.n个结点的线索二叉树上含有的线索数为 ( )。
) U: H; D$ P1 H$ @3 A; Z# _A.n-1
B.n
; N$ v4 Y/ d$ F% a; yC.n +1
2 X% N9 B' ]2 n. \D.2n
( o( X7 \  S% ^8 T- e5 m3 s正确资料
7 q8 F" R& U3 l1 l
15.广义表 (( a , b , c , d ) ) 的表头是 ()。
A.a
B.( )
, V' L3 \! F) j& v7 {+ xC.( a , b , c , d )
D.( b , c , d )
正确资料

16.将一个A [1..100, 1..100] 的三对角矩阵，按行优先次序存入一维数组B[1..298] 中，A中元素A [66, 65] 在数组B中的位置K为 () 。
, B3 A/ Q: \- I2 H: h/ w' zA.193
B.195
! Q6 L, n; h$ o% O! L9 c+ WC.197
1 I/ K/ I9 [, j9 N8 D* J* K$ kD.199
; l9 E: Z' \7 `, ~" N1 u# F8 G正确资料:

17.在链队列中，假设f和r分别为队首和队尾指针，则删除一个结点的操作是 ( )。
A.r = f->next;
0 b. r6 g6 r, \0 nB.r = r->next;
8 E3 A4 y$ q- o/ P" A# I  NC.f = f->next;
D.f = r->next;
( ?/ E% y- C0 N) F$ ^. p0 U正确资料

18.求图的最小(代价)生成树问题，考虑的是下面的哪一种图 ()。
; V7 m5 C. n8 P/ Z, M& gA.无向图
B.有向图
C.带权的无向图
D.带权的有向图
2 Q7 E! d% i6 R! |! \' `- F正确资料
5 F( O( U& A3 n  d2 p
, S0 n/ z: N* U" H1 F/ R' }5 S19.一个队列的入队序列是a、b、c、d，则队列的输出序列是 ( )。
7 _7 h8 r' Y( o1 r8 g* A4 X9 \# u+ wA.abcd
B.dcba
" v5 k. Z) @' [: ]* F2 OC.adcb
D.cbda
正确资料:
, w6 D" r/ R1 G4 S. w: }
) @! V) e% X, S) L2 k20.一个有向无环图的拓扑排序序列 () 是唯一的。
" k4 p3 Q) m! C! IA.一定
( @  s+ i6 L% T$ \' qB.不一定
6 w7 n. w- D1 I- wC.可能
D.三者均不对
正确资料:
; X( H' t- R3 ]$ N
& l! l. |( n9 u! p2 Q二、资料来源：谋学网（www.mouxue.com） (共 20 道试题,共 40 分)
21.数据的存储结构是数据的逻辑结构在计算机存储器上的实现，它是依赖于计算机的。
资料:正确
  l3 }. o+ V0 s! I# ?$ |- ?
22.AOV网的含义是以顶点表示活动的网。
资料:正确

23.在图G的最小生成树T中，可能会有某条边的权值超过未选边的权值。
4 M- M- g& t+ l9 S1 \资料:正确
5 C0 e2 z3 R: e
24.循环链表不是线性表。
' P$ v' y# d( b( b$ b资料:错误

25.分块查找在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中的元素个数有关。
0 M. G& W( q' N( D3 ?! b: L资料:正确

26.最佳二叉排序树是AVL树 ( 平衡二叉排序树 ) 。
资料:正确
- ~& B4 y  j$ m- ?0 Y
0 ~( i8 r7 E2 Y' l27.完全二叉树一定存在度为1的结点。
( d: h) X# E- o# u% w5 A) L) ]资料:错误
! C$ i9 P& o: B; E/ t6 M( l
28.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
资料:错误

29.链表中的表头指针与表头结点起到相同的作用。
资料:错误

30.链接存储结构属动态存储方式。
2 p2 J/ \; |1 [% x  h! A0 v资料:正确
+ V' y8 I. k3 I/ F
31.取顺序表的第i个元素的时间与i的大小无关。
资料:正确
$ P  m+ H  L6 H+ a) b
32.在指定结点之前插入新结点时，双链表比单链表更方便。
* h. N) j2 b  m资料:正确

33.若哈希表(散列表)的负载因子α < l，则可避免冲突的产生。
% ~* P9 k0 o  T  p, ~% R# C8 U: r5 R资料:错误

34.二叉树的叶结点，在前序遍历、中序遍历和后序遍历下皆以相同的相对位置出现。
资料:正确
6 O, Q% ]3 f. z7 m8 o8 D" v( n4 }
35.若输入序列为1, 2, 3, 4, 5, 6，则通过一个栈可以输出序列3, 2, 5, 6, 4, 1。
( ]* N6 B: T6 [0 k资料:正确

9 X$ v3 m/ }! a( L& v+ y36.数据的逻辑结构是指数据的各数据项之间的逻辑关系。
资料:错误
5 H; J2 S2 [9 L+ ^
8 L" T' U' J# `4 u" s/ P% d37.一个有向图的邻接表和逆邻接表中结点的个数可能不等。
" G4 ^* m) c" n" k, n1 B" x资料:错误

! P# }: Q3 S" n& [. e38.后序线索二叉树是不完善的，要对它进行遍历，还需要使用栈。
资料:正确
" H. `- c$ Y! F4 {! w
39.用一维数组存储二叉树时，总是以前序遍历顺序存储结点。
& X0 U: C- F  g3 `5 T资料:错误
5 k/ Q& r" p4 F+ N! d/ n0 z; M4 P
5 r* V. n. T  c' q% {3 R$ e% d' @, q40.任何一个递归过程都可以转换成非递归过程。
8 i0 j1 t5 ^/ }/ X5 D4 j8 N资料:正确
* b& u  }0 \) D8 O* I; A
0 W/ L! X# h/ _2 x
& s8 @; W+ K3 h: A& {2 Z; k

, f. q, c1 M# [
- ?/ A# `  ]8 [. a6 M9 b9 m9 R



6 p9 o$ L# }" t" O9 V