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

admin

吉大《数据结构》在线作业一
试卷总分：100       测试时间：--
: ^0 U; u( z/ j 单选题 多选题 判断题  
. w) o( I8 t/ m/ |( d
5 X5 E! n. q( b) G
% \5 L! {- ^+ `* y8 M, U% c2 y一、单选题（共 10 道试题，共 40 分。）V 1.  在图的邻接表存储结构上执行深度优先搜索遍历类似于二叉树上的( )。
6 J& t4 Y5 m' Y3 t% jA. 先根遍历
1 P. m) O' t3 {) Q2 KB. 中根遍历
C. 后根遍历
D. 按层次遍历
0 d$ i* J3 Y2 i. G  g: r      满分：4  分
2.  在数据结构中，逻辑上数据结构可分为：（ ）
A. 动态结构和静态结构
5 }/ ^- y$ c' ~/ YB. 线性结构和非线性结构
: j1 @' V' C- t4 D1 `C. 紧凑结构和非紧凑结构
& @7 ^1 T2 a+ _% [D. 内部结构和外部结构
9 o9 X" U9 g6 Z" y+ \- V      满分：4  分
; l0 X" m4 D* L$ }3.  含n个顶点的连通图中的任意一条简单路径，其长度不可能超过( )。
A. 1
B. n/2
C. n-1
D. n
! g. h1 M/ K" Z" `" ?8 ]" `9 |0 d      满分：4  分
; o8 i) {7 P4 B5 Z4.  单链表中，增加头结点的目的是为了( )。
A. 方便运算的实现
& e4 u4 m) }3 O! u1 ^' pB. 用于标识单链表
% e* {7 r! s3 p6 M% D2 D, S0 ~8 MC. 使单链表中至少有一个结点
D. 用于标识起始结点的位置
* q2 z( L6 M# I" d5 E      满分：4  分
5.  从具有n个结点的单链表中查找值等于x的结点时，在查找成功的情况下，平均需比较( )个结点。
A. n
B. n/2
" [1 q) F& W; s- AC. (n-1)/2
0 r$ t4 C8 i# E% x( n! aD. (n+1)/2
      满分：4  分
1 i/ h9 s, _$ Q' j" K6.  通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（ ）
A. 数据元素具有同一特点
B. 不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致
C. 每个数据元素都一样
& ~1 ?9 p6 x5 ]6 oD. 数据元素所包含的数据项的个数要相等
; Z8 E7 x# h7 b0 m$ a$ n      满分：4  分
7.  在具有n个单元的循环队列中，队满共有_______个元素。
A. n
B. n-1
C. n+1
# ?4 s' J, O0 r, z5 R1 cD. n+2
      满分：4  分
$ C0 W8 i# C2 P2 @$ }3 f6 T$ V8.  在 一个单链表中，已知q所指结点是p所指结点的直接前趋，若在p,q之间插入s结点，这执行（ ）操作。
% S5 R/ H- V: ?6 RA. s->next=p->next;p->next=s
# Q% C; A4 Y' z1 ?  T* rB. q->next=s;s->next=p
) m) I. m# x3 x, R2 h$ z' i5 |/ m  kC. p->next=s->next;s->next=p;
D. p->next=s;s->next=q;
- V6 V, M; V9 A* J      满分：4  分
9.  在排序过程中，键值比较的次数与初始序列的排列顺序无关的是()。
% k; @9 X+ n& _$ R: PA. 直接插入排序和快速排序
. k# g% F; a7 k% FB. 直接插入排序和归并排序
5 ]' g9 p5 g$ e0 ]( FC. 直接选择排序和归并排序
D. 快速排序和归并排序和归并排序
      满分：4  分
10.  线性表是具有n个（ ）的有限序列
A. 表元素
B. 字符
C. 数据元素
9 H0 ^% d5 N) Z9 c. i" WD. 数据项吉大《数据结构》在线作业一
, ~9 ]5 D, t6 y试卷总分：100       测试时间：--
单选题 多选题 判断题  
  D: h6 t" f6 K, i0 D
8 z6 j9 C( N6 }9 `  h* P: ~2 a" F
二、多选题（共 5 道试题，共 20 分。）V 1.  对线性表，可进行如下基本操作（ ）
0 |, h5 B1 X* v2 L4 h: \3 EA. 随机存取
B. 插入
" m* n" s" Y9 M8 Z% `' G& @: {# ]C. 删除
D. 查找
2 c7 [; {& o7 V) ?% A" \3 s      满分：4  分
8 z9 ^$ H; Q" \- R' L7 N$ b8 L2.  对有序表的查找方式有以下几种（）
( ]% ~  ~% y; U# r9 S4 iA. 折半查找
B. 斐波那契查找
0 V8 f2 o  R0 E/ iC. 插值查找
D. 二叉树查找
      满分：4  分
2 \8 f5 I- }; z1 E3.  属于插入排序的排序方法有（）
A. 直接插入排序
B. 对半插入排序
C. 渐减增量排序
" G3 Q2 X) h( S1 H+ VD. 冒泡排序
' w6 e) A* y  e& G/ O      满分：4  分
  \* b! E0 R# H$ r$ p# u1 L4.  数据结构指的是数据之间的关系，主要包含3部分的内容（ ）
A. 数据的逻辑结构
B. 数据的存储结构
C. 对数据施加的操作
. o5 K& K, V/ t) s$ TD. 算法
5 p+ ^6 N3 f1 r: ~4 x" i8 @' G      满分：4  分
5.  图的存储结构有（）
/ I& y6 `. ~, I2 c' f9 sA. 邻接矩阵
B. 邻接表
C. 数组表示法
D. 十字链表、判断题（共 10 道试题，共 40 分。）V 1.  算法在发生非法操作时可以作出处理的特性称为健壮性
A. 错误
) M9 F' \0 G+ I) t( J0 ^( wB. 正确
& g' ?. U' [: T1 q      满分：4  分
& s, D: d' A% i9 P' j+ `0 ~% O1 |* D2.  在一颗非空二叉树中，叶子节点的总数比度为2的节点总数多1个
A. 错误
B. 正确
      满分：4  分
3.  不是所有的AOV网都有一个拓朴序列
A. 错误
" }, `- w, B; \. gB. 正确
9 v9 S5 r( U% G' B+ c      满分：4  分
/ V$ L! @, ~1 t4 z4.  任何一棵二叉树中至少有一个结点的度为2。( )
A. 错误
6 Q' o. k. Z* _" j' Y! e; eB. 正确
      满分：4  分
3 {* w3 g3 X! Q5 }* z5.  在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是归并排序
A. 错误
B. 正确
      满分：4  分
6.  快速排序的速度在所有排序方法中为最快，而且所需附加空间也最少
* q( r  H" d) Y5 b' x9 P  k7 HA. 错误
B. 正确
      满分：4  分
& w: {- R8 o6 H- e7.  判断一个表达式中左右括号是否匹配，采用栈实现较为方便
- K3 g6 [( ?! j- y2 CA. 错误
B. 正确
      满分：4  分
/ J% h5 _) p. D5 M1 h4 q8.  Huffman树、平衡二叉树都是数据的逻辑结构
A. 错误
5 Y( t) t) G, A3 X" {8 S6 J7 e" jB. 正确
      满分：4  分
9.  若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是归并排序
A. 错误
B. 正确
      满分：4  分
6 l4 R# {& H- a" _4 n0 H10.  设栈的输入序列是1,2,3,4，则1,4,3,2不可能是其出栈序列
% }9 W2 X0 l4 r; [; s) LA. 错误
$ z- r- O# Q2 J& _B. 正确
6 }( m7 |1 p- v' k: M% i' Y. R( H      满分：4  分
      满分：4  分
      满分：4  分