吉大11秋《数据结构》在线作业资料二

百分百晓林

一、单选题（共 10 道试题，共 40 分。）V 1.  含n个顶点的连通图中的任意一条简单路径，其长度不可能超过( )。
A. 1
B. n/2
3 ]: R- _" d" ]- }C. n-1
D. n
* K, x. p5 W( H% N8 S; m, b      满分：4  分
; G  _1 G5 K) l6 X. V% q% u; ~3 j# [2.  深度为6的二叉树最多有( )个结点。
5 o1 I5 A, F+ Q4 P! r9 i% ]: rA. 64
6 |8 Y# H) \, v4 r3 [# hB. 63
" _& u6 `+ j9 B* mC. 32
' ]. [7 j7 F' N$ Q; d; H/ \! @4 {$ iD. 31
( R- `0 }# Z& ~& A# C  j      满分：4  分
  N; J+ _: \& }6 ?6 k' ]& [3.  链栈与顺序栈相比，有一个比较明显得优点是( )
8 K, ]: S, r) l, T7 C( G' [A. 通常不会出现栈满的情况
/ Y" ?9 O6 i8 N5 J2 Y2 T, I5 }B. 通常不会出现栈空的情况
9 Q7 f( d- R6 Q" k1 f1 ^C. 插入操作更加方便
D. 删除操作更加方便
      满分：4  分
! ?2 i9 Q. X1 R4.  在数据结构中，逻辑上数据结构可分为：（ ）
, U1 j0 i& E- Q  k) E2 @A. 动态结构和静态结构
. G, x1 f$ F, f& N( eB. 线性结构和非线性结构
C. 紧凑结构和非紧凑结构
9 ^' }' ^+ b% r( g4 [% I$ |D. 内部结构和外部结构
      满分：4  分
: h' `. n7 k7 ~- h3 Z5.  在排序过程中，键值比较的次数与初始序列的排列顺序无关的是()。
A. 直接插入排序和快速排序
B. 直接插入排序和归并排序
$ ?% M& H/ O5 \# J- X. W) dC. 直接选择排序和归并排序
/ H8 C4 x2 Y9 A3 R! a! zD. 快速排序和归并排序和归并排序
      满分：4  分
6.  在具有n个单元的循环队列中，队满共有_______个元素。
A. n
% v- @0 R2 `1 P# u" X+ v2 l) F' eB. n-1
9 m( j! x9 q9 [2 UC. n+1
D. n+2
      满分：4  分
% p' j. C* N* l+ f- c+ j7.  在无向图中，所有顶点的度数之和是所有边数的( )倍。
$ I" b: B8 m* i$ s/ x& @A. 0.5
B. 1
C. 2
D. 4
      满分：4  分
8.  非空的循环单链表head的尾结点(由指针p所指)满足( )。
) L' ]; Q3 l, _A. p->next=NULL
B. p=NULL
9 s6 n% i- s$ J- h- w4 I. [C. p->next=head
D. p=head
2 p3 }8 p/ M* w' p      满分：4  分
& O" Y$ [+ {6 I& t9.  在图的邻接表存储结构上执行深度优先搜索遍历类似于二叉树上的( )。
& |' ?7 @, f0 }( F9 H, LA. 先根遍历
( Z. G8 P9 W/ e0 [! C$ {5 PB. 中根遍历
C. 后根遍历
D. 按层次遍历
      满分：4  分
5 Z$ `( c+ y) \! Z5 K10.  PUSH和POP命令常用于（ ）操作
5 ]) m, n6 F2 vA. 队列
( i' M8 R: T5 Q) w1 g6 AB. 数组
3 f1 \$ g+ z6 IC. 栈
* |$ [4 q& O9 nD. 记录
$ t) ^5 e8 U9 _: \      满分：4  分

二、多选题（共 5 道试题，共 20 分。）V 1.  二叉树的遍历方式有（）
* T% U) X; n# cA. 先根遍历
B. 中根遍历
C. 后根遍历
! O* E! l6 b- ]% D  Q/ r6 S/ X" OD. 深度遍历
      满分：4  分
2.  对线性表，可进行如下基本操作（ ）
A. 随机存取
' }- e& `4 i! y! cB. 插入
C. 删除
D. 查找
      满分：4  分
3.  一个好的算法应具备以下性质（ ）
- T4 K9 H! [4 c8 h  S1 v; g3 WA. 正确性
, C6 {5 l5 e" mB. 可读性
5 U# }. O1 J: P& z  d6 |C. 稳健性
D. 有穷性
      满分：4  分
4.  数据结构指的是数据之间的关系，主要包含3部分的内容（ ）
" O1 \- Q7 O" h7 [% EA. 数据的逻辑结构
B. 数据的存储结构
C. 对数据施加的操作
, A7 V) M. h7 ]& iD. 算法
5 C. C" C; r5 }' Y      满分：4  分
5.  图的存储结构有（）
A. 邻接矩阵
* w6 d  g3 z2 W" m9 t% y2 l6 sB. 邻接表
C. 数组表示法
/ I1 W) z0 Y  [9 y1 Q3 A. u- iD. 十字链表
4 X0 r0 I4 k( j1 \5 I# W9 F  }2 b      满分：4  分
9 {- _$ X8 v1 F" A1 W* L
& I% u: ?* F4 B; U* C, z: r9 N三、判断题（共 10 道试题，共 40 分。）V 1.  在第一趟排序之后，一定能把数据表中最大或最小元素放在其最终的排序算法是冒泡排序
6 Y- f3 a) b, Z' G" P4 ]- F9 AA. 错误
$ D, _) a- a' x- NB. 正确
      满分：4  分
2.  快速排序的速度在所有排序方法中为最快，而且所需附加空间也最少
A. 错误
B. 正确
$ F% ~& U; b& U      满分：4  分
# h% I& e, K3 g6 A  Z- ]3.  算法在发生非法操作时可以作出处理的特性称为健壮性
A. 错误
4 [9 p& j& j% d7 \' x: UB. 正确
! J# o) p, |1 m7 W, f( P      满分：4  分
4.  不是所有的AOV网都有一个拓朴序列
+ n( J5 U+ H9 dA. 错误
B. 正确
, }" O+ i" Z* }      满分：4  分
! x. d' b% F" _1 w8 v$ _/ p5.  判断一个表达式中左右括号是否匹配，采用栈实现较为方便
& R0 ^: E0 b4 h# eA. 错误
, T- _& o$ x, ?$ \B. 正确
% j$ L! T: B; ^0 n      满分：4  分
" y5 a; H  n  _4 @; ?) e# F, Y( j6.  单链表中的头结点就是单链表的第一个结点。( )
4 |& {* e) P( p2 kA. 错误
B. 正确
      满分：4  分
4 P# J  |5 R% w6 M2 R3 W7.  设有两个串p和q，求q在p中首次出现的位置的运算称作模式匹配
8 _; F- b. j* j. D/ pA. 错误
B. 正确
3 e7 g: k3 i' L4 j      满分：4  分
: V' |( k5 h' x) w8.  栈和队列都是限制取点的线性结构（）
" |1 I  g- Q1 k( cA. 错误
' X! d0 q* n+ g  \6 LB. 正确
      满分：4  分
9.  在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是归并排序
A. 错误
# a/ V6 O6 O" Q/ O$ C. a; ?B. 正确
# k! Z5 `% a) D1 E+ u      满分：4  分
& M2 v" d3 e% \10.  字符串是一种线性表，其特殊性表现在它的数据元素是一个字符
A. 错误
! E% D' G; f" ?- j; JB. 正确
      满分：4  分
! i7 [# V% O% U: s( ~1 J: ?( V1 m* {
9 x! X. E; T- |, \- k# |9 @