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

admin

吉大《数据结构》在线作业一
试卷总分：100       测试时间：--
单选题 多选题 判断题  
2 |* D2 t* P6 |$ k# R1 q
2 [5 N. o, f4 Z: _
5 h  d& J! P9 i8 N; i一、单选题（共 10 道试题，共 40 分。）V 1.  在图的邻接表存储结构上执行深度优先搜索遍历类似于二叉树上的( )。
A. 先根遍历
) N7 ^2 h( V4 w6 d' k1 LB. 中根遍历
9 G+ D0 T. I' V% F$ u$ b/ U- [$ IC. 后根遍历
  G+ N4 }: {1 H! mD. 按层次遍历
      满分：4  分
2.  在数据结构中，逻辑上数据结构可分为：（ ）
. ~* Y% e  r0 W3 \5 LA. 动态结构和静态结构
B. 线性结构和非线性结构
2 n4 ^- t% t1 E/ O" a) ~C. 紧凑结构和非紧凑结构
* E9 L6 Q5 m7 rD. 内部结构和外部结构
      满分：4  分
3.  含n个顶点的连通图中的任意一条简单路径，其长度不可能超过( )。
A. 1
# l0 h, ], C7 xB. n/2
C. n-1
) s# d! M# ~+ H- v5 WD. n
. ^. ?0 ~/ f7 R0 H, v      满分：4  分
4 D, w& P8 N# v9 N9 e4.  单链表中，增加头结点的目的是为了( )。
A. 方便运算的实现
B. 用于标识单链表
# V6 S+ r8 h! y; [: rC. 使单链表中至少有一个结点
2 h0 t) P. b4 I7 jD. 用于标识起始结点的位置
5 H8 ?' m( C0 H7 V% R  ~- _( k1 n- F      满分：4  分
5.  从具有n个结点的单链表中查找值等于x的结点时，在查找成功的情况下，平均需比较( )个结点。
9 l8 K) \+ ~" lA. n
! d* J* s3 H1 U5 j7 \* OB. n/2
C. (n-1)/2
; K: t9 O- o  L* y; W! z' E  ID. (n+1)/2
      满分：4  分
, a( n/ L* [) P! V% n0 L( \6.  通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（ ）
A. 数据元素具有同一特点
$ M4 C8 K  s, j" u$ M! ^- _  H& V8 qB. 不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致
C. 每个数据元素都一样
% J  {7 }: S0 J( p, ]. V" Q  A( BD. 数据元素所包含的数据项的个数要相等
      满分：4  分
7.  在具有n个单元的循环队列中，队满共有_______个元素。
) n! V3 l. ?4 T9 D5 g% ^A. n
8 f* c+ T3 h$ T5 p' l) E0 r) F) VB. n-1
C. n+1
+ L0 S* d; `& c% S  MD. n+2
2 S1 B9 {8 L" B. [      满分：4  分
+ a; T  w7 w$ I& F' h! f8.  在 一个单链表中，已知q所指结点是p所指结点的直接前趋，若在p,q之间插入s结点，这执行（ ）操作。
* b3 s3 j) [7 y) `+ ~$ L, UA. s->next=p->next;p->next=s
5 ~5 N- Z4 P- O3 y, i  }6 s- YB. q->next=s;s->next=p
C. p->next=s->next;s->next=p;
% ]/ N$ S& Q5 e3 _  OD. p->next=s;s->next=q;
      满分：4  分
9.  在排序过程中，键值比较的次数与初始序列的排列顺序无关的是()。
9 H" D: y( y1 a' t6 J$ j; xA. 直接插入排序和快速排序
B. 直接插入排序和归并排序
C. 直接选择排序和归并排序
( I. p; H6 h: i& z) oD. 快速排序和归并排序和归并排序
      满分：4  分
10.  线性表是具有n个（ ）的有限序列
0 c/ h" s/ ]8 i* ~A. 表元素
+ Y5 J2 _9 J# B5 P# rB. 字符
3 b! f) Y' T/ J( |6 c# V' WC. 数据元素
8 V+ z( _' V0 a) D  X& ED. 数据项吉大《数据结构》在线作业一
: @+ p, ]+ P( `, `4 Q/ J2 M试卷总分：100       测试时间：--
单选题 多选题 判断题  

6 i6 Z- u! _% L, `3 L8 z
二、多选题（共 5 道试题，共 20 分。）V 1.  对线性表，可进行如下基本操作（ ）
( s1 T! \1 A* n, JA. 随机存取
B. 插入
C. 删除
" E" d+ _$ a" ED. 查找
# h% P  X' b* r9 W6 v8 H      满分：4  分
2.  对有序表的查找方式有以下几种（）
A. 折半查找
B. 斐波那契查找
# a  |7 J( z, G1 c+ wC. 插值查找
2 `1 K- X7 b( J5 ]) `0 tD. 二叉树查找
! X# X2 d. d0 `      满分：4  分
, s. t" V7 K9 M3.  属于插入排序的排序方法有（）
A. 直接插入排序
B. 对半插入排序
C. 渐减增量排序
! ]* j, \0 J' g& a+ p9 \7 l6 s% ~D. 冒泡排序
      满分：4  分
& ?' L- V* ?6 e: f4.  数据结构指的是数据之间的关系，主要包含3部分的内容（ ）
A. 数据的逻辑结构
4 t/ z+ N: l) u% [8 V6 UB. 数据的存储结构
# C; P, Q$ i' r) F1 x/ rC. 对数据施加的操作
D. 算法
      满分：4  分
5.  图的存储结构有（）
A. 邻接矩阵
B. 邻接表
C. 数组表示法
  ~0 T. W8 F2 c" X: z9 [' ]3 FD. 十字链表、判断题（共 10 道试题，共 40 分。）V 1.  算法在发生非法操作时可以作出处理的特性称为健壮性
A. 错误
% ^4 D  w+ ^+ d$ oB. 正确
      满分：4  分
2.  在一颗非空二叉树中，叶子节点的总数比度为2的节点总数多1个
7 P2 F3 ?8 [0 e2 }! ^0 rA. 错误
B. 正确
      满分：4  分
3.  不是所有的AOV网都有一个拓朴序列
A. 错误
0 {: t! A1 ]% QB. 正确
$ X  W9 Y" E9 x      满分：4  分
4.  任何一棵二叉树中至少有一个结点的度为2。( )
A. 错误
* n/ G& Q$ o; QB. 正确
9 \/ o* @9 s6 y' f' u" w      满分：4  分
& [$ X/ Z# V. |5 i1 i* \' [- C5.  在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是归并排序
3 U9 e) L* X: c3 yA. 错误
B. 正确
( ~7 L# C& D; x& R% n% e      满分：4  分
8 l( ]* }4 P) ^4 G7 E& h6.  快速排序的速度在所有排序方法中为最快，而且所需附加空间也最少
A. 错误
6 s3 ~& p  m5 C9 b$ @! E+ RB. 正确
6 {# G- V( |) D6 i4 }* D      满分：4  分
( u& P, w1 ~$ u; ^" [7.  判断一个表达式中左右括号是否匹配，采用栈实现较为方便
8 j8 D/ e0 c# _' q' E3 p. r; D/ k: SA. 错误
B. 正确
      满分：4  分
8.  Huffman树、平衡二叉树都是数据的逻辑结构
8 p6 H* h# c% `# y+ c1 _A. 错误
' `- O, Q/ I! T' u7 o5 HB. 正确
      满分：4  分
. }& E) F4 e& n. w1 u6 u8 U9.  若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是归并排序
+ r! X" g  S& v6 lA. 错误
B. 正确
6 y6 V; Z9 X# r8 P0 ]) i5 Q      满分：4  分
* N8 V3 c) i9 Q- j  B10.  设栈的输入序列是1,2,3,4，则1,4,3,2不可能是其出栈序列
A. 错误
B. 正确
      满分：4  分
! _. u- \/ W* j' r2 U! O3 S      满分：4  分
      满分：4  分