20年春福师《数据结构概论》在线作业一-1（答案参考）
【奥鹏】-[福建师范大学]福师《数据结构概论》在线作业一试卷总分:100 得分:100
第1题,下列排序算法中（ ）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。
A、堆排序
B、冒泡排序$ L* C6 X! @/ x$ u
C、快速排序$ x! h+ a2 B3 s1 p0 k7 K7 L
D、插入排序5 \& qs) V, H# w/ A
正确答案:
第2题,n个结点的线索二叉树上含有的线索数为（ ）8 T! z, Cg$ |9 g( A2 H
A、2n/ e3 VY3 ~- L5 J2 c8 m% N
B、n－l
C、n＋l' t3 f1 a* P3 K6 U# _4 L
D、n
正确答案:
5 F5 F- ~+ L- kx9 z
, e; L) b: A, z$ q
第3题,输入序列为ABC，可以变为CBA时，经过的栈操作为（ ）
A、push,pop,push,pop,push,pop% L, m" ~* G. |8 n
B、push,push,push,pop,pop,pop4 [& d* P; t3 f; u, }
C、push,push,pop,pop,push,pop$ @2 A% ~: A: j" ?& |$ p! |
D、push,pop,push,push,pop,pop
正确答案:
第4题,数组A中含有元素的个数（ ）. `6 Q3 q: a& s% S/ u
A、55# x- b! H* E; L0 |8 z
B、45
C、36
D、16: D6 c. E: w& Q, M% o# I) `
正确答案:* Z6 \' E3 KH5 ~) Z( E; y
& {1 a0 V+ r; p3 Xs: B
9 V: C0 G2 O% h% _; j0 A
第5题,栈和队都是（ ）
A、顺序存储的0 w4 f3 X0 y+ T" E' E
B、线性结构
C、链式存储的
D、非线性结构
正确答案:
" V& O( X, p! Y) T: b
第6题,设给定权值总数有n 个，其哈夫曼树的结点总数为( )
A、不确定
B、2n
C、2n+1: f0 `1 B1 Z* O; a; l9 }. `
D、2n-18 y7 X; uz4 q/ Q0 f, w. r! k
正确答案:4 G( d2 r* q3 [, o9 m4 S; ^- B
8 v; ]6 U2 `' N0 k. y
第7题,以下属于 非容器类控件 的是?
A、Form
B、Label* C$ h3 ~) C+ Y@/ E
C、page$ D# C% b3 n- E) H+ j
D、Container
正确答案:4 \4 \0 ^$ s3 l
0 e( ]' q% I+ n^$ n5 d& J- y( h" J+ d
第8题,广义表运算式Tail(((a,b),(c,d)))的操作结果是（ ）。$ Y8 h. X9 v0 A9 D: m
A、(c,d)
B、c,d& `, `, {4 t2 P& I! I6 f# t) X; p
C、((c,d)), M' Q; x' h7 X5 [# n
D、d4 h0 |. w# U9 T4 o5 y9 p
正确答案:
( C( e: a2 x5 V( p2 g
第9题,假设以行序为主序存储二维数组A=array，设每个数据元素占2个存储单元，基地址为10，则LOC=（ ）。& c$ L+ u# k# m. d: |9 m. N& P
A、808
B、818
C、10107 |1 ]) o( U- s$ \. G. L
D、1020
正确答案:
6 C+ q- |9 Q/ z
第10题,为了使索引键的值在基本表中唯一，在建立索引语句中应使用下面哪个保留字？
A、UNIQUE
B、COUNT
C、DISDINCT
D、UNION
正确答案:
" G% ?0 k- _v6 ?
第11题,以下数据结构中（ ）是非线性数据结构
A、树. s- k+ H5 L, k) b; O+ I
B、字符串) H/ J8 HT1 E8 J5 _" ~3 i
C、队
D、栈" O. E0 O9 @* @/ q1 w
正确答案:+ R5 D" Y, i6 s4 l9 R: R
- z9 k. M$ M/ O
第12题,若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用( )遍历方法最合适。
A、前序) b# X* F) A" b6 {4 {3 J
B、中序5 bi' z1 T" qy
C、后序
D、按层次1 ~. |/ u' Q: s7 W; o$ O1 k
正确答案:5 L4 z3 g3 l$ G; ^/ {* ?4 e
& C( O& p( [4 _; F" V
( U3 t( [; W' N7 m
第13题,适用于折半查找的表的存储方式及元素排列要求为( )8 g* G3 t9 g9 l3 w
A、链接方式存储，元素无序( _|( [$ a$ p; T
B、链接方式存储，元素有序
C、顺序方式存储，元素无序
D、顺序方式存储，元素有序
正确答案:
~0 A9 H; Z5 E+ z1 b+ p* T. X
第14题,下面的程序段中，对x的赋值语句的频度为（ ）FOR i:=1 TO n DOFOR j:=1 TO n DO x:=x+1;$ M- Y, N4 \, }- Z: C* X
A、O(2n)4 O; A: h9 `* U+ ~! y4 I+ {
B、O(n)
C、O(n^2)
D、O(log2n)' q+ c' m! y! M& b1 ^+ _* U2 u* p
正确答案:/ j0 z% F; X- P4 Z, C3 ?9 k+ p$ S
- ?( `- }- ]" w# u$ N! p& H
5 N9 M2 r$ B8 u, o- k/ J3 F3 a; d
第15题,关键路径是事件结点网络中（ ）
A、从源点到汇点的最长路径
B、从源点到汇点的最短路径
C、最长回路
D、最短回路
正确答案:
& j; yP9 M! E0 U& ?; s# p. K
第16题,下列排序算法中，在待排序数据已有序时，花费时间反而最多的是( )排序
A、冒泡) F# T+ o% B- Z) J8 W7 Q* mI0 m
B、希尔
C、快速
D、堆
正确答案:
' P$ e5 f) o% ?% D8 j# G
第17题,设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ ）! a+ r9 g5 G/ l/ C* j' f^( u
A、求子串
B、联接
C、匹配
D、求串长( D4 Z1 ^. V: c0 p# ]8 p2 \9 T
正确答案:, m4 O# W& T6 K( Z0 |
第18题,下面有关算法说法错误的是（ ）
A、算法最终必须由计算机程序实现
B、为解决某问题的算法同为该问题编写的程序含义是相同的8 `/ s0 p" I4 |# _
C、算法的可行性是指指令不能有二义性
D、以上几个都是错误的
正确答案:
" a: r( n' m1 W' h% F' _
* w2 V; |8 u3 Y. r5 L/ F
第19题,串的长度是指（ ）
A、串中所含不同字母的个数
B、串中所含字符的个数; J$ q2 N, |# Y. X8 z0 ?
C、串中所含不同字符的个数
D、串中所含非空格字符的个数, Y% }! D' i1 @! Y7 c: @5 c3 X$ S
正确答案:
第20题,下面叙述正确的是（ ）. ^( k- l9 M* ^$ F: K
A、算法的执行效率与数据的存储结构无关+ ?8 p" \6 t( P) K
B、算法的空间复杂度是指算法程序中指令(或语句)的条数
C、算法的有穷性是指算法必须能在执行有限个步骤之后终止
D、以上三种描述都不对
正确答案:: }& u: S2 S9 a8 i
, k/ R8 I) U/ V2 j# @( v% |
; d; |9 l0 h# }9 c2 x" c
第21题,设有部门和职员两个实体，每个职员只能属于一个部门，一个部门可以有多名职员，则部门与职员实体之间的联系类型是+ M8 T- o4 W' j% G# ?3 E/ K& }
A、m:n
B、1:m
C、m:k3 d# b2 ?2 e8 h
D、1:1+ _; m* Q& _9 o
正确答案:
7 b8 K" e" N( O. T, o
第22题,有n个叶子的哈夫曼树的结点总数为（ ）。
A、不确定
B、2n
C、2n+1
D、2n-1: q7 @1 {% ~( h6 z+ k
正确答案:
2 f9 G. ~% B7 M/ u4 L7 F& s% s
第23题,下面关于关系数据模型的说法，正确的是哪一项？' x4 b) H, [) p: Q) S5 I" S
A、只能表示实体间的1：1联系
B、只能表示实体间的l：n联系
C、只能表示实体间的m：n联系
D、可以表示实体间的上述三种联系
正确答案:
: h7 r" u; w' @. X0 Q7 E. R" c
第24题,若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ ）(1=i=n+1)。
A、O(0)
B、O(1); p, V# o/ |) i/ @
C、O(n)
D、O(n2)
正确答案 K" S) c& ~$ o" I% O' J4 U
第25题,线索二叉树是一种（ ）构。
A、逻辑
B、逻辑和存储# X4 j8 w9 z( z6 Y& w
C、物理
D、线性- ~8 z, U+ u6 p- a; A, E) ?
正确答案:! r6 V' a9 w' t, e* Iv
- C: X) }% C$ G8 G3 f- F
[% u5 G% d9 F6 k1 T
第26题,当待排序记录已经从小到大排序或者已经从大到小排序时，快速排序的执行时间最省。3 N' _, u- \- ?- V& M5 Y8 v
A、错误4 g7 |1 T. F0 b3 l5 n, J0 B$ t
B、正确- n^: i# p9 M/ P9 r
正确答案:
% }( w8 [8 j/ r3 @9 |* X
第27题,通常使用队列来处理函数或过程的调用（ ）
A、错误" R7 Y3 |8 S) z# s
B、正确( V% {4 p0 f8 W3 j3 l
正确答案 A+ n$ y, Y* _! |1 y, ^4 B' z
( |+ X" F7 w' J1 @7 w' ?
第28题,对于有N个结点的二叉树，其高度为log2n。
A、错误
B、正确$ [+ o4 J8 w. L
正确答案:
第29题,在待排数据基本有序的情况下，快速排序效果最好（ ）
A、错误
B、正确
正确答案:3 i6 k( h+ C, A" ]
5 S* X( J# f7 N2 u
第30题,SQL语言的事务管理主要通过'事务提交COMMIT'和'事务撤消ROLLBACK（回滚）'两个命令来实现的。
A、错误1 ]3 D7 A3 g$ V1 t8 b8 k# E
B、正确7 b4 j0 M/ u) ]
正确答案:2 Z; [$ S6 G- x! I
( k+ T$ R/ i/ G
: x- _& N9 j" @- R% h
第31题,对一棵二叉树进行层次遍历时，应借助于一个栈
A、错误
B、正确
正确答案:
" W( o9 x; Y) W# m1 w8 K9 Z3 _
第32题,直接选择排序算法在最好情况下的时间复杂度为O（N）（ ）% t9 ^! l! K3 \- z; q3 s; ]
A、错误
B、正确. C2 ]' ?- `, J" w: @# b
正确答案:
8 P/ x9 G! [) j2 \: ?
第33题,一条没有指明去向的SQL SELECT语句执行之后，会把查询结果显示在屏幕上，要退出这个查询窗口，应按 ESC。
A、错误
B、正确
正确答案:' E8 @, K9 [: q$ r- y8 q
5 P! Q- H" K$ N& l" q% V; J, t: s
1 R7 Y% z: T1 a$ l
第34题,线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的（ ）- a! x4 L- x% a6 @- U
A、错误+ H( v& Z! K4 X6 Y, ~8 T
B、正确+ WA! D0 ?: J# [% i4 I# f) b
正确答案:& Wv! H0 H! u" u0 w' c: `: ^
3 V0 N5 n) k% _; k% [$ s. Tn& d
第35题,在查找树（二叉树排序树）中插入一个新结点，总是插入到叶结点下面（ ）
A、错误
B、正确
正确答案:
+ ~/ k9 U$ W( _# F# _# k' J
9 L) X! O* _9 @0 M7 z* J
第36题,对无序表用二分法查找比顺序查找快, Q( Q& j, w2 r7 j/ `: L
A、错误: H3 O. M! @. o6 P, b5 `0 ?+ m
B、正确
正确答案:% A6 t6 a3 m! m3 \# Y+ ?' P
v4 V7 x; E6 a; m6 \6 F
第37题,两分法插入排序所需比较次数与待排序记录的初始排列状态相关。' y+ @. s- k+ D6 T
A、错误
B、正确5 @6 Q5 x% ]& i8 x# PE0 d
正确答案:/ k0 N, L% J0 e. Q6 r
' ~% L+ c6 H- o2 e- C4 V* P
4 `: u, C0 J& D
第38题,循环链表不是线性表（ ）
A、错误
B、正确. w: w' x! P+ y( p- S' B, U/ W! x9 V
正确答案:
; J( p% z5 P) v- ^0 A* Q. L5 u
第39题,数据库结构设计包括：根据实际应用进行需求分析，根据需求分析的结果设计数据库的概念结构和逻辑结构，最后进行数据库（基本数据表）的物理设计。& K2 D. p& U& d6 U( w0 B
A、错误! C5 w+ p$ u" H7 D8 Z/ R
B、正确
正确答案:" U# {& y7 }- T) K
第40题,主键约束（primary key constraints）的含义是，要求表中在指定的列上没有两行具有相同的值,且不允许为空值。
A、错误
B、正确1 f3 _, F$ E! I+ _7 ~7 Y0 n. |
正确答案:√
V3 a* `% O) U, d2 ?9 d
# Q) m( M6 p3 B
第41题,基本关系，基本表和基表的含义是相同的
A、错误3 A9 D3 U: s_
B、正确: y9 V4 K8 |% t1 M
正确答案:√
+ A, k' x* f; o! M, w* \h
7 k; W- t0 |0 c6 {1 e
第42题,顺序存储结构的主要缺点是不利于插入或删除操作（ ）
A、错误1 F$ wM8 T. w! ?) a5 l6 k- T
B、正确, y$ ^+ @5 _0 k* H% `
正确答案:
# q1 ~( r1 l( R0 b4 u
5 d' d- I0 i3 W& E8 v* C3 Y5 f( @
第43题,在伙伴系统中的伙伴是指任意两块大小相同、位置相邻的内存块。6 V& V( J' u- r! N
A、错误
B、正确( wo+ o1 q, [
正确答案:N/ N* [- R" o' g2 B& s- n" h4 f
/ B# f+ J4 M8 Q( [: r' ^
6 D3 t+ M2 n2 J5 H/ F1 J* C
第44题,控件包括容器控件和标准控件两种，其中表单集、表单、表格、页框、页面等对象都属于容器控件。) b. c$ o) ^$ U& S% D! n* ^5 `
A、错误
B、正确! a# @: J/ vn/ K. q! _
正确答案:√. \, l: |* b6 g( r8 e2 A* z
) ~7 b' Q- s$ t" t9 ^6 l
9 p% F3 a( {8 n3 ~- |
第45题,采用二叉链表作存储结构，树的前序遍历和其相应的二叉树的前序遍历的结果是一样的。& W( L* a, S6 G( d0 T7 X+ r
A、错误1 K; ]8 BD% w6 u
B、正确& M4 L6 @8 Y+ yz* I/ y1 |" [% Q
正确答案:
; ~: b# p1 e) h7 a( ~6 l1 M! bz
, \# l1 {6 T' h: P" h
第46题,下面关于线性表的叙述中，正确的是（ ）
A、线性表采用顺序存储，必须占用一片连续的存储单元。2 E) L1 {- X! \2 g- e- L
B、线性表采用顺序存储，便于进行插入和删除操作。9 X/ c7 |) u+ [) s5 v& g
C、线性表采用链接存储，不必占用一片连续的存储单元。
D、线性表采用链接存储，便于插入和删除操作。, x: ]( A/ E, \$ Y$ o! s- M/ v' c* V7 s
正确答案:,C,D7 j/ ]- Yv2 e
6 D( \' V1 t( Z6 Q1 u
) p6 {. N' I+ G6 {, l% ]4 ^
第47题,下面关于求关键路径的说法正确的是（ ）1 p) g7 k$ G- _3 d6 p9 M) {5 A
A、求关键路径是以拓扑排序为基础的
B、一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同
C、一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差
D、关键活动一定位于关键路径上9 C. F2 P& s+ z* e& Y: J2 B' v
正确答案:,B,D
2 c$ n) {& g( a6 x
8 k9 T. k3 ~( A7 Y
第48题,下面说法正确的是( )。
A、广义表的表头总是一个广义表
B、广义表的表尾总是一个广义表F7 _9 P) T) i0 x& V
C、广义表难以用顺序存储结构
D、广义表可以是一个多层次的结构\5 U6 S% r5 i: x: r
正确答案:,B,C2 `+ Gb# M5 x4 K8 Q7 `
- g0 l- G/ i" F& K7 [4 P
0 M6 e, y0 K- F+ @9 C7 a
第49题,一个关系模式的定义主要包括?
A、关系名和属性名6 j9 p3 `+ p# v1 B# H8 y& K0 t
B、属性类型+ `4 Q5 y2 R. Z
C、属性长度
D、关键字
正确答案:,B,C,D- nq; |) S/ z0 x& A' J
) R0 G/ e0 M, R' m, |9 n
第50题,关系数据库管理系统能实现的专门关系运算项包括下面哪些项?
A、选择" S3 n2 U% H1 n$ N
B、连接
C、分隔
D、投影
正确答案:,B,D
页:
[1]