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

admin

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


一、单选题（共 10 道试题，共 40 分。）V 1.  在图的邻接表存储结构上执行深度优先搜索遍历类似于二叉树上的( )。
A. 先根遍历
B. 中根遍历
C. 后根遍历
D. 按层次遍历
      满分：4  分
9 s( T. V9 F- \9 ~# p& L, a2.  在数据结构中，逻辑上数据结构可分为：（ ）
3 F1 r9 ]1 o" n$ \! E7 t' XA. 动态结构和静态结构
2 `8 ]' L; c, D* t6 IB. 线性结构和非线性结构
C. 紧凑结构和非紧凑结构
5 b- P3 @% p9 U- RD. 内部结构和外部结构
      满分：4  分
3.  含n个顶点的连通图中的任意一条简单路径，其长度不可能超过( )。
/ R+ a. E* h7 g- A/ Z4 mA. 1
B. n/2
C. n-1
, B; T1 f: F2 U# c3 KD. n
      满分：4  分
4.  单链表中，增加头结点的目的是为了( )。
A. 方便运算的实现
B. 用于标识单链表
C. 使单链表中至少有一个结点
1 A* l: A# ~, I7 TD. 用于标识起始结点的位置
+ S1 W+ L2 K6 J# b3 A6 [/ r7 G5 \$ U      满分：4  分
5.  从具有n个结点的单链表中查找值等于x的结点时，在查找成功的情况下，平均需比较( )个结点。
A. n
B. n/2
: F. M' X5 P8 J- R8 m' [  u$ EC. (n-1)/2
- s, a6 `8 r* R( [' W7 _D. (n+1)/2
      满分：4  分
6.  通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（ ）
A. 数据元素具有同一特点
B. 不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致
C. 每个数据元素都一样
D. 数据元素所包含的数据项的个数要相等
+ [/ b3 W& M6 {. ~8 E& ~      满分：4  分
7.  在具有n个单元的循环队列中，队满共有_______个元素。
A. n
# ^1 H( _! g& [B. n-1
: x: l& t5 M. |C. n+1
D. n+2
      满分：4  分
8.  在 一个单链表中，已知q所指结点是p所指结点的直接前趋，若在p,q之间插入s结点，这执行（ ）操作。
A. s->next=p->next;p->next=s
B. q->next=s;s->next=p
3 Y# U9 d& s+ q; e7 X4 o3 A; \- DC. p->next=s->next;s->next=p;
! L4 u$ M7 j7 z. I1 X# gD. p->next=s;s->next=q;
% {! p9 ~, t# Q5 ^7 s      满分：4  分
; y! O9 v' F: p$ n3 M. \9.  在排序过程中，键值比较的次数与初始序列的排列顺序无关的是()。
7 K7 u- M" a& j6 I4 Y' t8 C( Q) rA. 直接插入排序和快速排序
% K8 d# W6 Q  bB. 直接插入排序和归并排序
, V# u& x+ b  _4 t8 ^. _( I6 UC. 直接选择排序和归并排序
& q5 x9 }1 V: o+ [* h7 ND. 快速排序和归并排序和归并排序
      满分：4  分
10.  线性表是具有n个（ ）的有限序列
A. 表元素
  @: K2 m6 V) D, e  G3 N$ a: {4 uB. 字符
2 j2 z$ k, D) R& AC. 数据元素
4 B. W( A: L; V  d3 C+ Z! W. \D. 数据项吉大《数据结构》在线作业一
试卷总分：100       测试时间：--
单选题 多选题 判断题  
0 K3 J4 W+ i, s" R* f

二、多选题（共 5 道试题，共 20 分。）V 1.  对线性表，可进行如下基本操作（ ）
, d7 ?' D+ S, U4 C4 mA. 随机存取
B. 插入
' P/ s- ^6 d8 Q& v. zC. 删除
  L  f; s; C$ u. X0 FD. 查找
      满分：4  分
8 j5 v; b0 M$ f5 \2.  对有序表的查找方式有以下几种（）
; u- M; y* i+ |A. 折半查找
+ T9 A7 R1 x, f. RB. 斐波那契查找
C. 插值查找
8 ]; ^8 |0 T  J6 rD. 二叉树查找
0 {1 y% g6 N) Y9 `- X8 S      满分：4  分
3.  属于插入排序的排序方法有（）
A. 直接插入排序
B. 对半插入排序
! a, }+ J$ Q0 v/ ?0 w6 o9 mC. 渐减增量排序
D. 冒泡排序
% D- ?4 ^# m* I4 f/ h3 Q      满分：4  分
4.  数据结构指的是数据之间的关系，主要包含3部分的内容（ ）
: H+ W) l. f- M1 Y' bA. 数据的逻辑结构
B. 数据的存储结构
8 e4 m$ I2 Y- K4 C, ?3 aC. 对数据施加的操作
9 ]; s3 }& M7 K2 l" c8 E1 Z- LD. 算法
      满分：4  分
5.  图的存储结构有（）
A. 邻接矩阵
5 T2 Z- k7 Z- T2 K7 A+ }B. 邻接表
C. 数组表示法
% |% N% G3 c6 L+ u% y1 ED. 十字链表、判断题（共 10 道试题，共 40 分。）V 1.  算法在发生非法操作时可以作出处理的特性称为健壮性
- T* G' b9 V* i4 m5 kA. 错误
% k- q  y" L* z7 Y' sB. 正确
      满分：4  分
2.  在一颗非空二叉树中，叶子节点的总数比度为2的节点总数多1个
A. 错误
% r. r& }8 X. n3 K8 M, [) ZB. 正确
# k. s/ G# g: D3 L9 V' l, k      满分：4  分
% V4 z( V: j+ {6 P7 V# E$ H% T. S3.  不是所有的AOV网都有一个拓朴序列
A. 错误
7 K: P  M: n2 F- h6 d. ZB. 正确
( a/ a0 X! |5 u4 t$ W) E      满分：4  分
3 y$ I" Q& A: H9 w" \, e0 ?4 q4.  任何一棵二叉树中至少有一个结点的度为2。( )
" |" f. B  d0 v/ W, q* bA. 错误
9 T1 ^3 }3 u1 g5 ^2 v* FB. 正确
      满分：4  分
4 ~: F6 J* b% [5.  在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是归并排序
A. 错误
$ K+ B8 w+ e( O- FB. 正确
/ m+ a9 F# ]( L1 i7 G4 H      满分：4  分
6.  快速排序的速度在所有排序方法中为最快，而且所需附加空间也最少
A. 错误
* y9 L3 Q" S$ p7 rB. 正确
      满分：4  分
7.  判断一个表达式中左右括号是否匹配，采用栈实现较为方便
% y, T0 Z" y; a( {! V9 F/ WA. 错误
B. 正确
( V$ _9 I* s1 n6 M      满分：4  分
% }9 q( [5 ]+ \! Z  U. K+ R8.  Huffman树、平衡二叉树都是数据的逻辑结构
A. 错误
; i9 l% y6 H' T. M! |, k: w& [B. 正确
. s6 v" D1 M) `: v# J      满分：4  分
9.  若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是归并排序
7 @& Z0 ~2 j6 C6 AA. 错误
/ v5 s9 Q  W' b+ f5 ~B. 正确
      满分：4  分
5 a& o: \4 k+ S% O# e10.  设栈的输入序列是1,2,3,4，则1,4,3,2不可能是其出栈序列
A. 错误
% R* b  p/ d4 x9 GB. 正确
0 A6 o' E( O/ S" w# V- x      满分：4  分
      满分：4  分
      满分：4  分