吉大《数据结构》在线作业二

admin

吉大《数据结构》在线作业二
试卷总分：100       测试时间：--
单选题 多选题 判断题  

4 P4 f, ]- h" }4 v7 l
0 M9 ]$ n7 I( e一、单选题（共 10 道试题，共 40 分。）V 1.  在无向图中，所有顶点的度数之和是所有边数的( )倍。
8 a& X9 U% N9 p5 fA. 0.5
# C0 Q; R6 |( {, H  WB. 1
C. 2
D. 4
      满分：4  分
2.  当文件局部有序或文件长度较小的情况下，最佳的排序方法是( )。
/ S5 R) q7 n4 D. c5 J! {" ?* s5 mA. 直接插入排序
% j; v/ z$ t- u, o0 fB. 直接选择排序
7 ]. [4 I( ]' y2 s, IC. 冒泡排序
D. 归并排序
      满分：4  分
: t. C) _& s1 g7 V  D3.  从具有n个结点的单链表中查找值等于x的结点时，在查找成功的情况下，平均需比较( )个结点。
A. n
' E$ c1 l; r( P, {) dB. n/2
C. (n-1)/2
! J5 T: e$ `" ^* Q7 s' B3 HD. (n+1)/2
      满分：4  分
4.  设深度为k的二叉树上只有度为0和度为2的结点，则这类二叉树上所含结点总数最少( )个。
A. k+1
B. 2k
C. 2k-1
D. 2k+1
      满分：4  分
5.  非空的循环单链表head的尾结点(由指针p所指)满足( )。
% w. k; C, h+ X( j% v+ K# L4 ^A. p->next=NULL
B. p=NULL
C. p->next=head
D. p=head
' m  S( \2 r0 T% V( u      满分：4  分
" G& l# \% G8 {" [# i2 X6.  在具有n个单元的循环队列中，队满共有_______个元素。
A. n
B. n-1
9 R6 K, @0 m" jC. n+1
  U) {' y: i- H8 ~! MD. n+2
+ w8 S$ n# E* q, b1 T- n      满分：4  分
" a6 E2 A% N- b/ H7.  在图的邻接表存储结构上执行深度优先搜索遍历类似于二叉树上的( )。
  g0 E5 _. ?+ G, T" @4 k- nA. 先根遍历
, t$ r! g4 c+ p0 T: W, O- HB. 中根遍历
1 Q' v& {, F; ?) N6 Q* W7 ?" MC. 后根遍历
* n) s3 g) h; N: N, A. |D. 按层次遍历
6 r! l9 s: j% H$ l0 p/ J1 c/ x0 B( ?      满分：4  分
8.  链栈与顺序栈相比，有一个比较明显得优点是( )
# @6 N& `7 V0 |  ?. |7 KA. 通常不会出现栈满的情况
B. 通常不会出现栈空的情况
C. 插入操作更加方便
D. 删除操作更加方便
2 g# N, P; |2 J      满分：4  分
) P/ ?# G* {7 {5 z' `( z9.  通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（ ）
A. 数据元素具有同一特点
7 b  f6 S( F' U3 i% CB. 不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致
C. 每个数据元素都一样
7 @) t5 g. N: a* x3 E3 KD. 数据元素所包含的数据项的个数要相等
      满分：4  分
: ~7 k: r  c/ {  @* A10.  在排序过程中，键值比较的次数与初始序列的排列顺序无关的是()。
A. 直接插入排序和快速排序
B. 直接插入排序和归并排序
C. 直接选择排序和归并排序
D. 快速排序和归并排序和归并排序吉大《数据结构》在线作业二
试卷总分：100       测试时间：--
单选题 多选题 判断题  

4 [4 ?  m: B; |. p" ^
. M( K. z8 l) j! s& O  V+ ]二、多选题（共 5 道试题，共 20 分。）V 1.  一个好的算法应具备以下性质（ ）
A. 正确性
+ g  N+ p% }2 r4 A5 u2 o* xB. 可读性
C. 稳健性
& k7 u7 y3 R* K$ q" K$ D& n% sD. 有穷性
# I) |( U  x  R) F3 {* g      满分：4  分
- p: w% C( j2 s1 L- j  c5 X2.  以下属于操作受限的顺序表是（ ）
$ |( X8 C% ^1 o/ }) h  l, oA. 栈
B. 队列
C. 单链表
' D0 S3 w, U$ P/ l7 ?* h* n- D) QD. 树
      满分：4  分
9 B7 S" ~3 }& \  f- ]: s7 s+ F  C) T3.  递归过程中要保存的信息包括（ ）
A. 返回地址
6 y; b% z  x( a( L; sB. 本次调用中与形参结合的实参值
9 l. y, P# z1 c. AC. 本次递归调用中的局部变量值
D. 执行结果
      满分：4  分
4.  数据结构指的是数据之间的关系，主要包含3部分的内容（ ）
A. 数据的逻辑结构
B. 数据的存储结构
C. 对数据施加的操作
D. 算法
8 Y( ^! @# u# v( V2 f      满分：4  分
& T$ C3 n9 q+ n' a5.  对线性表，可进行如下基本操作（ ）
, X" l6 Y9 e, C  y: v% k8 YA. 随机存取
  N! W! ]: O3 cB. 插入
. S' `1 F/ [6 X. kC. 删除
9 J* A, q! O6 }. a# L& M( ^  g; LD. 查找、判断题（共 10 道试题，共 40 分。）V 1.  从未排序的序列中依次取出一个元素与已排序序列中的元素进行比较，然后将其放在已排序序列的合适位置上，该排序方法称为插入排序
8 P" B5 V$ y/ D3 H5 c( R+ }: d3 RA. 错误
1 m$ L" w0 H; f7 s+ m9 hB. 正确
      满分：4  分
2.  任何一棵二叉树中至少有一个结点的度为2。( )
A. 错误
4 l' G9 F1 `  R1 C! u2 S- lB. 正确
2 V8 w. S7 Z' O' d' \6 D      满分：4  分
3.  对于前序遍历和中序遍历结果相同的二叉树为所有结点只有右孩子的二叉树
A. 错误
3 }+ u6 @& T- N+ q1 H, dB. 正确
      满分：4  分
+ z8 s# y5 E* n. W# w4.  设有两个串p和q，求q在p中首次出现的位置的运算称作模式匹配
7 y! A& Y  b" h, k. d' oA. 错误
B. 正确
5 {) B  |( f) x" y      满分：4  分
5 |7 n9 ~: h9 L) r2 W$ T  J& f5.  设栈的输入序列是1,2,3,4，则1,4,3,2不可能是其出栈序列
A. 错误
B. 正确
      满分：4  分
( X1 `3 d- I7 p8 e2 `) G, d6.  若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是归并排序
A. 错误
, }* ]# {3 _) x- _, GB. 正确
      满分：4  分
7.  算法在发生非法操作时可以作出处理的特性称为健壮性
A. 错误
/ c, a0 N! g  V- h& iB. 正确
( J. g9 g& T6 W% p      满分：4  分
: C+ ~% v- [) W' e9 Y8.  不是所有的AOV网都有一个拓朴序列
A. 错误
B. 正确
      满分：4  分
9.  在第一趟排序之后，一定能把数据表中最大或最小元素放在其最终的排序算法是冒泡排序
  U: f) y& V0 @4 M' gA. 错误
B. 正确
      满分：4  分
10.  单链表中的头结点就是单链表的第一个结点。( )
A. 错误
B. 正确
4 @9 P4 N. R& [- H# C6 E9 v1 x2 ]      满分：4  分
      满分：4  分
0 C5 c+ H* d7 w3 |, s      满分：4  分