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

谋学网

一、单选题（共 10 道试题，共 40 分。）V 1.  在具有n个单元的循环队列中，队满共有_______个元素。
4 v( z0 B  n+ ?. g& k1 L' JA. n
' n# O4 C$ k4 \) _3 FB. n-1
8 S9 O+ i" G* p# EC. n+1
, T+ S" T; A' s3 O; {! d5 |D. n+2
. @% ?4 ~4 T" e3 ^7 o      满分：4  分
2.  设深度为k的二叉树上只有度为0和度为2的结点，则这类二叉树上所含结点总数最少( )个。
A. k+1
B. 2k
; g9 u( \# q) S, w5 {4 S4 \C. 2k-1
8 h5 D( Q. p! |D. 2k+1
/ @" h- Y" M" L      满分：4  分
3.  PUSH和POP命令常用于（ ）操作
A. 队列
, e6 w2 L; E# E/ KB. 数组
2 j- }& P$ }. x# {2 [9 dC. 栈
D. 记录
9 b' x5 C8 F1 Q  N) i      满分：4  分
4.  在图的邻接表存储结构上执行深度优先搜索遍历类似于二叉树上的( )。
. g4 L4 `. R1 Q3 P8 T5 HA. 先根遍历
B. 中根遍历
. M2 ?4 [( S5 k5 wC. 后根遍历
D. 按层次遍历
      满分：4  分
3 W% f. R4 }( g1 W+ b5.  在数据结构中，逻辑上数据结构可分为：（ ）
; ~" R( u. z4 `3 V* |( r" mA. 动态结构和静态结构
/ P* p& {" S/ O/ x  x1 ?) K! bB. 线性结构和非线性结构
C. 紧凑结构和非紧凑结构
D. 内部结构和外部结构
      满分：4  分
' E% l; Z# V3 N6.  非空的循环单链表head的尾结点(由指针p所指)满足( )。
A. p->next=NULL
B. p=NULL
C. p->next=head
D. p=head
      满分：4  分
8 g, A$ G- O3 V0 N& j; D4 `& O7.  线性表是具有n个（ ）的有限序列
8 S3 {  D% |" J/ c& d5 _: KA. 表元素
& L, c$ r4 E3 C7 @. R2 cB. 字符
8 n! l) `6 R3 N. m( r# Q/ U" z  wC. 数据元素
& [& p) \, [& Y! M3 w! m$ KD. 数据项
      满分：4  分
7 T) ]- D6 |9 o$ c* t8.  单链表中，增加头结点的目的是为了( )。
A. 方便运算的实现
B. 用于标识单链表
' ^* F4 L( ?& M) l' f+ h7 tC. 使单链表中至少有一个结点
D. 用于标识起始结点的位置
0 v2 c' s: O: Y: I# v0 o      满分：4  分
9.  在排序过程中，键值比较的次数与初始序列的排列顺序无关的是()。
A. 直接插入排序和快速排序
% o% C, [& A! d4 mB. 直接插入排序和归并排序
7 e+ [  z7 Q& f7 ~4 AC. 直接选择排序和归并排序
6 @1 }# l6 l* ID. 快速排序和归并排序和归并排序
: F. V0 B5 @; o- d2 M      满分：4  分
10.  在单链表中，删除p所指结点的直接后继的操作是( )
0 v7 ~  C$ q1 y" s5 @A. p->next=p->next->next;
B. p=p->next;p->next=p->next->next;
  s( y& r5 d% {8 L. `C. p->next=p->next;
$ v0 v9 U# N- u: u6 W( _+ w# i3 yD. p=p->next->next;
      满分：4  分
8 S4 O7 y8 c- g5 [
二、多选题（共 5 道试题，共 20 分。）V 1.  递归过程中要保存的信息包括（ ）
A. 返回地址
B. 本次调用中与形参结合的实参值
C. 本次递归调用中的局部变量值
: w8 t3 \" z2 KD. 执行结果
      满分：4  分
2.  属于插入排序的排序方法有（）
% ~* `3 j) ]6 Y# s! `. XA. 直接插入排序
B. 对半插入排序
8 w. E0 S2 w& ^" b5 fC. 渐减增量排序
9 o$ U3 n% I  `/ K( S" e0 B: W% ID. 冒泡排序
3 I( h; h' i: D8 m3 a9 y: `; E      满分：4  分
3.  对有序表的查找方式有以下几种（）
A. 折半查找
* c$ ?/ p) W! K2 L# A! k/ u9 c" z% sB. 斐波那契查找
# ]7 v/ H  ~+ |1 RC. 插值查找
/ P. W7 `- i% a( F6 ^/ pD. 二叉树查找
      满分：4  分
4.  二叉树的遍历方式有（）
A. 先根遍历
# ^/ _2 O, C- j5 t1 e+ vB. 中根遍历
C. 后根遍历
D. 深度遍历
5 z; t; o* {# d  X      满分：4  分
' p  r6 X$ _( d8 P( l5.  图的存储结构有（）
A. 邻接矩阵
B. 邻接表
C. 数组表示法
) M' e- g. q0 @7 R4 _D. 十字链表
/ _/ e2 L( i/ s# w& [      满分：4  分

三、判断题（共 10 道试题，共 40 分。）V 1.  算法和程序没有区别，所以在数据结构中二者是通用的。( )
' D$ Y6 r2 O  vA. 错误
  K$ U1 n, [$ N9 [9 pB. 正确
* A2 @/ b4 Y. U( [      满分：4  分
2.  在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是归并排序
A. 错误
- j! u, g2 L( cB. 正确
4 X: i; `, D2 y1 y' |      满分：4  分
6 ]. M6 {+ ]! {+ }$ v& S$ ^3.  Huffman树、平衡二叉树都是数据的逻辑结构
A. 错误
1 Y. h  ]; g' VB. 正确
7 i* b0 Z" n  R5 _( j1 H# t      满分：4  分
& `# m: |' }  M& ^; b$ F2 M4.  设有两个串p和q，求q在p中首次出现的位置的运算称作模式匹配
A. 错误
B. 正确
: U; I. p( \# |' W5 s* r5 ~1 e9 ^+ f      满分：4  分
& y# q+ ~0 Y7 _: F' r- [) x' `5.  栈和队列都是限制取点的线性结构（）
A. 错误
B. 正确
      满分：4  分
  k! g% o5 b6 A' x+ K/ C" H6.  若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是归并排序
) M+ f) r6 G9 D" R- LA. 错误
B. 正确
      满分：4  分
7.  设栈的输入序列是1,2,3,4，则1,4,3,2不可能是其出栈序列
3 m6 L0 Q5 r. i% o% ~2 pA. 错误
B. 正确
. T& x: E, x) ^1 _      满分：4  分
8.  任何一棵二叉树中至少有一个结点的度为2。( )
A. 错误
B. 正确
      满分：4  分
4 e0 w1 L# b3 f, e* e9.  具有n（n>0）个顶点的无向图最多含有n(n-1)/2条边
A. 错误
B. 正确
      满分：4  分
10.  单链表中的头结点就是单链表的第一个结点。( )
. f, I5 i% |+ d6 g( J) a$ S: r0 e1 r" lA. 错误
B. 正确
      满分：4  分