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

谋学网

一、单选题（共 10 道试题，共 40 分。）V 1.  在具有n个单元的循环队列中，队满共有_______个元素。
- Z4 ^% @* N; P7 CA. n
B. n-1
: i! H0 U! v8 IC. n+1
D. n+2
) M6 p1 r/ ]: r. N/ ]# v      满分：4  分
2.  设深度为k的二叉树上只有度为0和度为2的结点，则这类二叉树上所含结点总数最少( )个。
2 q9 ^3 H- c3 f) {6 ~. \A. k+1
B. 2k
C. 2k-1
D. 2k+1
      满分：4  分
3.  PUSH和POP命令常用于（ ）操作
A. 队列
  k5 B3 t6 \' @, y) E% fB. 数组
C. 栈
2 p6 A  g0 Y: F( L: |& MD. 记录
2 u4 M8 |+ Z9 Y; A0 V' R& _4 `% Z' k      满分：4  分
( M# n+ q  r( L* ?7 Q- w* {# ]4.  在图的邻接表存储结构上执行深度优先搜索遍历类似于二叉树上的( )。
' d* v$ d( r& Q/ h1 @9 `A. 先根遍历
* X* l9 V) v- ]/ p5 Z4 @2 @2 fB. 中根遍历
C. 后根遍历
D. 按层次遍历
. U6 X7 j; w5 I9 b/ L" T      满分：4  分
+ Q1 W) j  w* R! d9 M5.  在数据结构中，逻辑上数据结构可分为：（ ）
A. 动态结构和静态结构
$ q+ m7 z$ C& p0 tB. 线性结构和非线性结构
! W/ O+ n: q. B# P0 [) Q( E* W4 D# H/ tC. 紧凑结构和非紧凑结构
- d$ \, m1 r& e* |+ tD. 内部结构和外部结构
, M( W1 \6 \2 z7 L      满分：4  分
$ B: x8 U4 ^# p7 Z! c6.  非空的循环单链表head的尾结点(由指针p所指)满足( )。
( s( V$ ]; \/ P* Z4 H( PA. p->next=NULL
B. p=NULL
  L7 \! N$ d3 N8 G. kC. p->next=head
D. p=head
      满分：4  分
0 Y+ m8 m, d' Y  j& ^1 j, N2 G* A' D7.  线性表是具有n个（ ）的有限序列
  z8 @4 C5 t+ OA. 表元素
B. 字符
! E! s' b. {" `: f& {  R! U9 [C. 数据元素
D. 数据项
      满分：4  分
8.  单链表中，增加头结点的目的是为了( )。
A. 方便运算的实现
B. 用于标识单链表
' @2 M7 ^# ?. B) _& ^C. 使单链表中至少有一个结点
D. 用于标识起始结点的位置
      满分：4  分
- J' y/ S* r" f1 l! r" o9.  在排序过程中，键值比较的次数与初始序列的排列顺序无关的是()。
A. 直接插入排序和快速排序
  d6 X5 u2 E6 P( M! _: tB. 直接插入排序和归并排序
C. 直接选择排序和归并排序
- A3 \; ?; f3 ]& Q' ]  SD. 快速排序和归并排序和归并排序
8 k0 S" I& d% H/ s5 y6 ]' g      满分：4  分
3 d. \4 X- l7 a5 l7 |6 E8 K7 g10.  在单链表中，删除p所指结点的直接后继的操作是( )
A. p->next=p->next->next;
4 v5 x; J8 T8 c# l' M9 _B. p=p->next;p->next=p->next->next;
C. p->next=p->next;
2 J1 L$ w7 X8 G8 z( I- z. XD. p=p->next->next;
      满分：4  分
; T( w: c- P* n, ^
( u6 Z6 T1 `/ A7 j! D% m2 q; ]3 H- ?二、多选题（共 5 道试题，共 20 分。）V 1.  递归过程中要保存的信息包括（ ）
A. 返回地址
) l& j" `2 M/ m" A9 LB. 本次调用中与形参结合的实参值
  s& g8 ?) ]$ e5 U' hC. 本次递归调用中的局部变量值
' L$ M+ D/ Z- X+ n  BD. 执行结果
( m* H& H3 z) b3 }      满分：4  分
: R. [8 v. y- d& E, z- h9 ]. t2.  属于插入排序的排序方法有（）
+ ^4 p. r7 r9 t. F, h, T9 v8 rA. 直接插入排序
B. 对半插入排序
C. 渐减增量排序
! ~" Y- B' S1 Z  tD. 冒泡排序
7 l5 m1 S  K# z3 J7 Z! q) I      满分：4  分
) S  ~) m7 ~) L) q% w3.  对有序表的查找方式有以下几种（）
A. 折半查找
B. 斐波那契查找
C. 插值查找
D. 二叉树查找
      满分：4  分
4.  二叉树的遍历方式有（）
, S& U7 q% X, [4 W: C/ w! uA. 先根遍历
! k0 Z& a3 Q! b9 OB. 中根遍历
7 c& h6 |8 o8 w, P' ^C. 后根遍历
4 p  {, D0 a# U' r6 G7 `D. 深度遍历
' y5 E% N: r0 q; E" S) j  Z9 x3 K      满分：4  分
9 j3 t4 {. a. ]) y5.  图的存储结构有（）
A. 邻接矩阵
B. 邻接表
9 Z, h! O1 ~7 B  `C. 数组表示法
- Y& {) \8 p1 M8 F& tD. 十字链表
7 \( v' O& o! e      满分：4  分

- G9 L" N8 J1 r: l  t- ?+ `三、判断题（共 10 道试题，共 40 分。）V 1.  算法和程序没有区别，所以在数据结构中二者是通用的。( )
A. 错误
$ G6 j! T: [; X0 XB. 正确
      满分：4  分
" u# f% j. X- R, m( h2.  在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是归并排序
A. 错误
' a; y; e, g+ Z* aB. 正确
7 T+ ]% P- m* T: F3 U& ?( R      满分：4  分
3.  Huffman树、平衡二叉树都是数据的逻辑结构
: a" R9 S" ]; i1 Z+ T( i7 m9 zA. 错误
B. 正确
      满分：4  分
8 q+ p9 z" c) n1 W6 Z4.  设有两个串p和q，求q在p中首次出现的位置的运算称作模式匹配
7 u! S) N# u' ?4 D% J" UA. 错误
6 d, E9 i" ?! u: Y/ s7 ~% uB. 正确
      满分：4  分
" K4 t) o9 @, o7 U) W2 X0 }( P7 b- ~5.  栈和队列都是限制取点的线性结构（）
A. 错误
6 d( c# I! s$ q1 jB. 正确
      满分：4  分
; J7 c! p) y% \; y- J6.  若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是归并排序
. M0 S5 P$ b6 @. d0 e3 dA. 错误
& W/ _2 t! H1 SB. 正确
, c4 V2 z) c3 M5 S: F4 a      满分：4  分
5 ^% x  q4 `3 s0 P$ X6 ^7.  设栈的输入序列是1,2,3,4，则1,4,3,2不可能是其出栈序列
6 J. x' T4 F$ N, g( o7 y1 {7 S9 xA. 错误
' H. j, V: g, _( JB. 正确
1 a2 T$ W% s2 Y* W" y4 [. U      满分：4  分
8 @; h% M# n* D2 ~7 A- ]+ b8.  任何一棵二叉树中至少有一个结点的度为2。( )
A. 错误
7 Z4 @6 R" Y& c8 OB. 正确
9 E- ]& Q/ G5 Y2 J. I0 T  ^      满分：4  分
. h, }, _5 G. r! }, W9.  具有n（n>0）个顶点的无向图最多含有n(n-1)/2条边
A. 错误
B. 正确
! o7 o# I* y$ s7 p! E9 N7 X      满分：4  分
5 A+ B& q. \: I; F0 e9 ]  {' c* A10.  单链表中的头结点就是单链表的第一个结点。( )
+ D9 o7 V5 b% l! G) ?# b7 g$ @A. 错误
$ S; ~2 i2 e% t  gB. 正确
      满分：4  分
! u0 a  F- T6 N1 }6 D. u8 |  z
: ^! T* u8 `6 i- G5 G$ d$ {