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

谋学网

一、单选题（共 10 道试题，共 40 分。）V 1.  在具有n个单元的循环队列中，队满共有_______个元素。
A. n
B. n-1
C. n+1
D. n+2
      满分：4  分
$ P* P0 X0 p, x& \2.  设深度为k的二叉树上只有度为0和度为2的结点，则这类二叉树上所含结点总数最少( )个。
/ p! g& i4 p6 q3 i7 y% V) p+ XA. k+1
B. 2k
C. 2k-1
D. 2k+1
. @$ Z. c, }7 Y* g      满分：4  分
+ u8 m9 A, E) x+ q% y$ y' R$ S3.  PUSH和POP命令常用于（ ）操作
A. 队列
B. 数组
( d7 p& {" s: A( J8 L0 zC. 栈
/ t$ {' q' m5 q3 W6 }1 ]# d4 u3 RD. 记录
      满分：4  分
4.  在图的邻接表存储结构上执行深度优先搜索遍历类似于二叉树上的( )。
1 K9 _7 l9 _8 n; V: gA. 先根遍历
B. 中根遍历
# Z) Y3 K( s; L' \3 y3 C9 |$ lC. 后根遍历
7 n0 _: w6 s$ C$ u1 \& l# K1 YD. 按层次遍历
+ j5 h# W8 y+ u      满分：4  分
" `6 P% C" s8 v0 K" @5.  在数据结构中，逻辑上数据结构可分为：（ ）
0 H0 }# C; C' E0 s0 J/ @0 y2 CA. 动态结构和静态结构
B. 线性结构和非线性结构
1 g4 ~4 O: O3 }' aC. 紧凑结构和非紧凑结构
  Z! t' d) a) a' `D. 内部结构和外部结构
3 p3 D# }. y8 e! G+ p3 E; ?* c! \      满分：4  分
6.  非空的循环单链表head的尾结点(由指针p所指)满足( )。
' k8 ]3 u$ Q) W" e: |# GA. p->next=NULL
8 u3 |& p* M4 zB. p=NULL
C. p->next=head
D. p=head
      满分：4  分
& f# @9 e; s. {  \2 q- o9 R% b0 ]7.  线性表是具有n个（ ）的有限序列
7 u& H- t  y5 N. {+ f' }A. 表元素
B. 字符
& p6 X0 t5 `+ jC. 数据元素
( h7 Z5 J; u; x! @" N1 D9 N: p$ eD. 数据项
) }2 o# e% n0 ~9 [      满分：4  分
8.  单链表中，增加头结点的目的是为了( )。
1 d' x6 V1 }0 {A. 方便运算的实现
B. 用于标识单链表
5 e8 j0 n1 D& {! XC. 使单链表中至少有一个结点
% _( j" w% H# n% l" O9 n7 QD. 用于标识起始结点的位置
      满分：4  分
. O0 {& a. I+ [1 |9.  在排序过程中，键值比较的次数与初始序列的排列顺序无关的是()。
2 K* ^& L5 I0 U& b& x4 |A. 直接插入排序和快速排序
B. 直接插入排序和归并排序
% k) Z0 r+ Q5 _- VC. 直接选择排序和归并排序
* x1 b4 z) o, J/ V) YD. 快速排序和归并排序和归并排序
      满分：4  分
10.  在单链表中，删除p所指结点的直接后继的操作是( )
A. p->next=p->next->next;
B. p=p->next;p->next=p->next->next;
; q2 @0 s) ?+ w7 l  @) G) R9 KC. p->next=p->next;
D. p=p->next->next;
- o+ c1 m' D- x9 P: V/ [      满分：4  分

二、多选题（共 5 道试题，共 20 分。）V 1.  递归过程中要保存的信息包括（ ）
( s+ X) N+ t' Q7 ~9 K: cA. 返回地址
" [9 d* Q6 q8 n4 O. pB. 本次调用中与形参结合的实参值
/ H3 ?: O& r8 p" nC. 本次递归调用中的局部变量值
( K& l0 w0 R% bD. 执行结果
( y, {: z4 S3 G3 ~      满分：4  分
$ K2 E2 Q/ A2 Y/ n. w. p' \/ \6 S2.  属于插入排序的排序方法有（）
A. 直接插入排序
/ _, r; N, \1 l2 ]7 pB. 对半插入排序
. `/ l# T- L, ~; I3 c( L& cC. 渐减增量排序
5 K9 b" V: u$ n' yD. 冒泡排序
      满分：4  分
- _0 T: V& L  f- L6 O# n% W3.  对有序表的查找方式有以下几种（）
8 R: [  a3 P: ?9 i* W: {( x; @/ R  lA. 折半查找
: x5 _) n0 \$ w2 W  ^+ U, TB. 斐波那契查找
5 V0 Z  E* K- l. ]C. 插值查找
0 k3 _/ Q2 u4 |+ f' ?3 n, vD. 二叉树查找
      满分：4  分
, Y9 `* H) \, y9 K4.  二叉树的遍历方式有（）
A. 先根遍历
B. 中根遍历
4 O. s: M0 y7 H) Z" T( t4 tC. 后根遍历
D. 深度遍历
( Z- ^4 }) w+ \% Y      满分：4  分
" k" E0 i( L' m7 R6 }$ ], B$ j+ M5.  图的存储结构有（）
9 n0 f( U! o5 m) }6 f4 a, b: q5 jA. 邻接矩阵
& g5 ~  p2 Z2 `0 MB. 邻接表
. r6 G8 V- i- P% gC. 数组表示法
D. 十字链表
: o) ~% e) j8 D# ?) I2 [0 }# o      满分：4  分
5 m- r; w4 ?/ ]2 |8 z- c
三、判断题（共 10 道试题，共 40 分。）V 1.  算法和程序没有区别，所以在数据结构中二者是通用的。( )
A. 错误
B. 正确
6 z- D" v. i3 {* |6 F  W( Y6 N0 G- K      满分：4  分
2.  在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是归并排序
# b; l7 M7 j) k0 t4 O9 C# w9 E% y' WA. 错误
( P" l* X8 R, e) D% Q9 q7 |9 TB. 正确
. O/ _) I0 @( t' U  k      满分：4  分
3.  Huffman树、平衡二叉树都是数据的逻辑结构
A. 错误
B. 正确
) \6 o/ \! ]& s9 N' ]8 {9 K9 M      满分：4  分
6 T5 z8 S- \+ Q4 Q* U% H4.  设有两个串p和q，求q在p中首次出现的位置的运算称作模式匹配
A. 错误
5 Q3 q% H- N  n4 t$ f) t( eB. 正确
8 G7 F' R$ J7 d# @4 h      满分：4  分
2 Y, V& y7 T0 U$ h5 t/ x0 F' m5.  栈和队列都是限制取点的线性结构（）
A. 错误
B. 正确
      满分：4  分
6.  若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是归并排序
2 G3 v# [0 c+ F7 N3 F$ l% [+ jA. 错误
B. 正确
      满分：4  分
7.  设栈的输入序列是1,2,3,4，则1,4,3,2不可能是其出栈序列
A. 错误
" C1 ^8 J6 m5 z$ _8 g/ hB. 正确
( e% A3 Q! Z# X, l4 X( d, J+ q1 P# G      满分：4  分
1 q! n8 B% r! m+ [/ m* g0 N" Y6 L! l8.  任何一棵二叉树中至少有一个结点的度为2。( )
- L% _! d2 r5 R3 }9 ]2 A9 HA. 错误
; _8 X/ H, M0 h7 I% q1 C; X  fB. 正确
      满分：4  分
9.  具有n（n>0）个顶点的无向图最多含有n(n-1)/2条边
$ ~: [1 z5 u4 f! WA. 错误
B. 正确
( K1 l; b9 |% J8 O! @      满分：4  分
10.  单链表中的头结点就是单链表的第一个结点。( )
% n# r1 d8 `) j3 iA. 错误
* [% _6 l: X' n8 S' v& @0 B& YB. 正确
      满分：4  分
: M& ^- D5 y* d5 T- M
( a3 N! r1 X! V# j; v' W, z, c