吉大11秋《数据结构》在线作业一

百分百晓林

一、单选题（共 10 道试题，共 40 分。）V 1.  带头结点的单链表head为空的判断条件是()。
A. head=NULL
B. head->next=NULL
C. head->next=head
D. head!=NULL
6 r' W) w) [! y* C      满分：4  分
/ R' K& X/ ?: x+ b2 m  s* m2.  设深度为k的二叉树上只有度为0和度为2的结点，则这类二叉树上所含结点总数最少( )个。
$ c) S$ H# b3 x# C0 P$ ], T* [! vA. k+1
$ Q1 q; Q, ^3 c" `% ~B. 2k
C. 2k-1
D. 2k+1
      满分：4  分
- R. y1 [& a) x) ?( T3.  在图的邻接表存储结构上执行深度优先搜索遍历类似于二叉树上的( )。
+ n' q8 i% \: Z- A+ p, z. a/ AA. 先根遍历
B. 中根遍历
6 r& z) ]  ?% J5 J7 e1 g. O9 e2 |3 o: QC. 后根遍历
* J/ B- O+ \; l- z$ ?1 {; [. c' YD. 按层次遍历
8 j# g" Z9 k* A  F1 D      满分：4  分
# u+ ~, M+ t1 z4 v: a% _. z& o4.  在数据结构中，逻辑上数据结构可分为：（ ）
A. 动态结构和静态结构
; H2 O7 C2 B5 r& q# UB. 线性结构和非线性结构
C. 紧凑结构和非紧凑结构
D. 内部结构和外部结构
      满分：4  分
7 F2 j" f) w/ t9 c5.  链栈与顺序栈相比，有一个比较明显得优点是( )
A. 通常不会出现栈满的情况
) I* {% u. r7 I/ p2 nB. 通常不会出现栈空的情况
2 b% m- Y& ]+ S2 y% ^7 SC. 插入操作更加方便
D. 删除操作更加方便
      满分：4  分
" Y0 y% P6 ^- B+ ?! m  W6.  单链表中，增加头结点的目的是为了( )。
A. 方便运算的实现
B. 用于标识单链表
C. 使单链表中至少有一个结点
D. 用于标识起始结点的位置
      满分：4  分
7.  在具有n个单元的循环队列中，队满共有_______个元素。
' Q# v; G. P* k5 |- U0 sA. n
* k0 _% F  g1 B$ M- VB. n-1
2 M3 E/ Z. c6 W9 {) d2 D$ M# _C. n+1
/ P$ p1 N/ D, b, wD. n+2
      满分：4  分
8.  深度为6的二叉树最多有( )个结点。
4 `$ Y) \+ d( s! v! Y) {7 PA. 64
# G8 X! M$ N/ Y/ x. S- x! eB. 63
C. 32
D. 31
      满分：4  分
9.  任何一颗二叉树的叶结点在其先根、中根、后跟遍历序列中的相对位置( )。
( P9 e( K* J# oA. 肯定发生变化
B. 有时发生变化
7 u" |5 b' o8 p7 J  ~) g8 p# e3 EC. 肯定不发生变化
D. 无法确定
1 X" B! r0 J8 Y" n& D      满分：4  分
$ T, ^5 ~/ Z. @& n+ h$ u' u10.  非空的循环单链表head的尾结点(由指针p所指)满足( )。
A. p->next=NULL
4 ]+ i" P: N$ C4 u/ VB. p=NULL
- e+ S* A% w/ t$ v" Q9 XC. p->next=head
D. p=head
( P: p, h6 H, Z      满分：4  分
4 b4 n5 n  z1 H/ r! j& F( D& W( L
/ t- S$ \9 o9 w4 }6 p& g二、多选题（共 5 道试题，共 20 分。）V 1.  一个好的算法应具备以下性质（ ）
A. 正确性
B. 可读性
C. 稳健性
D. 有穷性
7 k" L& h- E9 T! j9 r( K      满分：4  分
2.  对有序表的查找方式有以下几种（）
5 T$ v) W" k, F; N0 j; hA. 折半查找
B. 斐波那契查找
C. 插值查找
D. 二叉树查找
6 T% b$ m; C& c  c+ k* ~' u      满分：4  分
3.  二叉树的遍历方式有（）
- z0 k! Q; d" N) o# {& }5 dA. 先根遍历
/ o! B: x; ?% R& nB. 中根遍历
C. 后根遍历
D. 深度遍历
      满分：4  分
4.  属于插入排序的排序方法有（）
& G0 i+ E0 C" EA. 直接插入排序
1 a6 I$ j/ E% G! u- pB. 对半插入排序
/ s; `4 J/ n2 p& J+ jC. 渐减增量排序
9 e$ k- b, L* p4 f0 jD. 冒泡排序
      满分：4  分
5.  递归过程中要保存的信息包括（ ）
A. 返回地址
; V* X0 k* b& N$ JB. 本次调用中与形参结合的实参值
C. 本次递归调用中的局部变量值
0 Y; e' T1 h, s: J' [6 t9 O7 DD. 执行结果
      满分：4  分

9 Y+ l& y' D$ Q4 d( O三、判断题（共 10 道试题，共 40 分。）V 1.  对于前序遍历和中序遍历结果相同的二叉树为所有结点只有右孩子的二叉树
A. 错误
B. 正确
      满分：4  分
8 J5 L5 I$ ^* Z0 x2.  在一颗非空二叉树中，叶子节点的总数比度为2的节点总数多1个
, Q' |' c! N7 @. j& ZA. 错误
! F" Z& Q. n2 R% `( oB. 正确
      满分：4  分
1 v' c- [0 W: l; a2 P, u! A+ i4 I" F3.  快速排序的速度在所有排序方法中为最快，而且所需附加空间也最少
A. 错误
B. 正确
4 a5 W$ D' p" E& a7 W8 l, H+ j3 t      满分：4  分
4.  算法和程序没有区别，所以在数据结构中二者是通用的。( )
A. 错误
B. 正确
3 d7 l3 d% k& {      满分：4  分
5.  在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是归并排序
: q4 C2 E% k) y- y1 |; fA. 错误
B. 正确
1 d6 K( C; p8 a5 t+ W4 u1 M      满分：4  分
8 C( ~8 ^5 E5 k, ~/ q' {4 B6.  由权值为9,2,5,7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度44
5 `, C3 I9 o1 x- E: }# K3 l" AA. 错误
, n+ U( A! N5 X: @2 L, uB. 正确
" O1 R# g, ]8 a0 ]- ]! l" U6 @      满分：4  分
0 s$ Q/ K" D) z: q3 L% \7.  从未排序的序列中依次取出一个元素与已排序序列中的元素进行比较，然后将其放在已排序序列的合适位置上，该排序方法称为插入排序
A. 错误
2 ?2 T' t8 b( f9 D$ z  jB. 正确
      满分：4  分
" P$ {( N+ _. M5 G. z2 I/ C8.  字符串是一种线性表，其特殊性表现在它的数据元素是一个字符
A. 错误
B. 正确
4 e6 n2 \  r- a9 E# A      满分：4  分
8 G0 ^# f/ i% R1 d, Y5 \9.  设有两个串p和q，求q在p中首次出现的位置的运算称作模式匹配
& t* [( f+ w. K- HA. 错误
7 h7 O! S% C7 rB. 正确
      满分：4  分
$ Y3 l5 O6 x7 R10.  邻接多重表示法对于有向图和无向图的存储都适用
; n! R: x- ^9 ~$ xA. 错误
( `. a8 ^% E: m  D( mB. 正确
( U' j' a' _9 }+ M      满分：4  分

! k1 y7 ]# U% O  z& v$ o: @7 Q. u- E; _