[东北大学]21年12月考试《数据结构ⅡX》考核作业

奥鹏在线作业

东 北 大 学 继 续 教 育 学 院

) l/ Z' F. U. C7 j 数据结构II X 试 卷（作业考核 线上2）  A  卷

; O  d" D, C7 K" \4 N& |. L学习中心：            院校学号：             姓名            
6 k/ V1 e4 S2 g( J' m0 b0 \
0 B5 h+ _0 R  R6 z（共    6    页）         
总分        题号        一        二        三        四        五        六        七        八        九        十
        得分                                                                               
: A* @5 X% Z0 ]一、单选题（共30题，每题2分）
[ ]1．抽象数据类型的三个组成部分分别为
A．数据对象、数据关系和基本操作
      B．数据元素、逻辑结构和存储结构
! P, m6 d7 x  X5 P6 S  \      C．数据项、数据元素和数据类型
      D．数据元素、数据结构和数据类型
[ ]2．要求相同逻辑结构的数据元素具有相同的特性，其含义为
A. 数据元素具有同一的特点
B. 不仅数据元素包含的数据项的个数相同，而且其对应数据项的类型要一致
! I8 _: A8 S5 s/ m# qC. 每个数据元素都一样
D. 仅需要数据元素包含的数据项的个数相同
( T2 y4 _, }0 Y# B[ ]3．下列各式中，按增长率由小至大的顺序正确排列的是
A． ，n！，2n ，n3/2                    
& U: p; G% w2 YB．n3/2，2n，nlogn，2100
3 a# q( m) c' l+ i4 d0 j: P      C．2n，log n，nlogn，n3/2               
1 {; H  ?* p# c! u( D# ?$ G+ iD．2100，logn, 2n, nn
[ ]4. 在下列哪种情况下，线性表应当采用链表表示为宜
      A.经常需要随机地存取元素         
6 q  d% X5 \6 _' UB.经常需要进行插入和删除操作
! r8 S/ Z$ T2 w( K      C.表中元素需要占据一片连续的存储空间   
D.表中元素的个数不变
1 H1 E2 K0 F" C6 P: s. P. N: m# \! U[ ]5．设指针p指向双链表的某一结点，则双链表结构的对称性是
3 x' m- N, W' b- HA. p->prior->next=p->next->next;      
# L! K+ ], I' R% u( AB.  p->prior->prior=p->next->prior;
/ k  ^! a5 V, a* w! ~C. p->prior->next=p-> next->prior;     
D.  p->next->next= p->prior->prior;
2 A( O! f8 f' Z2 b6 [[ ]6. 已知指针p和q分别指向某带头结点的单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为
    A. s->next=q；p->next=s->next；
    B. s->next=p；q->next=s->next；
C. p->next=s->next；s->next=q；
D. q->next=s->next；s->next=p；
. g2 `5 f  d( I[ ]7. 栈和队列的共同特点是
1 i, ~1 q4 J( x' ]7 C0 Z: HA.只允许在端点处插入和删除元素
B.都是先进后出   
C.都是先进先出
D.没有共同点
% V6 |# r* z. ?+ j[ ]8. 对于链队列，在进行插入运算时.
) \7 l: t6 E' B  n$ R      A. 仅修改头指针         
B. 头、尾指针都要修改
7 I2 Q! n2 ]: L& @' l      C. 仅修改尾指针              
' A, b$ [  Z/ {: t* TD.头、尾指针可能都要修改
[ ]9．设有一个顺序栈的入栈序列是1、2、3，则3个元素都出栈的不同排列个数为
      A．4      B．5     C. 6     D. 7
[ ]10．设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是
A．A，B，C，D               B．D，C，B，A   
# ]1 L. o9 _, Y$ |C. A，C，D，B               D. D，A，B，C
- ]/ \) A& e/ `7 ?[ ]11．表达式a*(b+c)-d的后缀表达式是
      A．abcd*+-    B．abc*+d-  C．abc+*d-   D．-+*abcd
[ ]12．某二叉树的先序序列和后序序列正好相反，则该二叉树的特点一定是
A. 空或只有一个结点             B.高度等于其结点数
C. 任一结点无左孩子             D.任一结点无右孩子
[ ]13．下面的说法中正确的是
    (1)任何一棵二叉树的叶子结点在种遍历中的相对次序不变。
" N+ H, s/ u& p+ b! C' \, C' [    (2)按二叉树定义，具有三个结点的二叉树共有6种。
9 p7 {) G+ o0 C' _( eA．(1)，(2)                       B．(1)   
) a) R: g# u+ A  q* }7 eC．(2)                            D．(1)，(2)都错
/ l' B, J0 ?" m% I5 i& K3 u4 _, I[ ]14．树有先序遍历和后序遍历，树可以转化为对应的二叉树。下面的
, W, i2 K2 f8 z4 X  b说法正确的是
      A．树的后序遍历与其对应的二叉树的先序遍历相同     
0 E/ b8 [5 _4 s9 L! C9 c) }: d. rB．树的后序遍历与其对应的二叉树的中序遍历相同
C．树的先序序遍历与其对应的二叉树的中序遍历相同      
D．以上都不对
1 H0 T1 ~* ^. A[ ]15．下列说法正确的是
    (1)二又树按某种方式线索化后，任一结点均有前趋和后继的线索
. L/ q% H0 b8 w" O& v$ J% n, o6 q! `  g    (2)二叉树的先序遍历序列中，任意一个结点均处于其子孙结点前
    (3)二叉排序树中任一结点的值大于其左孩子的值，小于右孩子的值
% C9 }9 s. l( k' FA．(1)(2)(3)                     B．(1)(2)   
C．(1)(3)                        D．都不对
[ ]16. 二叉树的第k层的结点数最多为
      A．2k-1                          B.2K+1      
' O4 D! ~3 r: J: ?C.2K-1                           D. 2k-1
[ ]17．以下说法不正确的是
     A．无向图中的极大连通子图称为连通分量
     B．连通图的广度优先搜索中一般采用队列来暂存刚访问过的顶点
     C．图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点
     D．有向图的遍历不可采用广度优先搜索
[ ]18．有向图G用邻接矩阵A存储，则顶点i的入度等于A中
A. 第i行1的元素之和            B. 第i列1的元素之和
C. 第i行0的元素个数            D. 第i列非0的元素个数
[ ]19. 设有6个结点的无向图，该图确保是一个连通图的有效边条数至
少应是
& K9 g: K4 D1 m; g3 ^9 K8 eA.5              B.6              C.7             D.8
[ ]20．.下图的邻接表中，从顶点V1 出发采用深度优先搜索法遍历该图，则可能的顶点序列是
  
- v7 j) A; ]+ K8 V0 V$ ^A. V1V2V3V4V5          B. V1V2V3V5V4
8 c" `  p% O$ r* d7 l* hC. V1V4V3V5V2          D.V1V3V4V5V2
[ ]21．关键路径是事件结点网络中
      A．从源点到汇点的最长路径    B．从源点到汇点的最短路径
+ i" O: B/ ]; o- w# `: L" D# F( ?      C．最长的回路                D．最短的回路
[ ]22．设哈希表长为14，哈希函数H(key)=key％11，表中已有数据的关键字为15，38，61，84，四个，现将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是
      A．8       B．3        C．5        D．9
[ ]23．.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为0，右孩子的平衡因子为1，则应调整以使其平衡，所作的平衡旋转是
A. LL型           B. LR型       C. RL型       D. RR型
6 a( X9 Q2 ^8 }& c6 P, Q[ ]24．下列排序算法中，在待排序数据已基本有序时，效率最高的排序方法是
( m# M  d/ ^* w0 C+ Q4 ^8 E      A．插入排序                           B．选择排序   
' d9 f' m% M2 HC．快速排序                           D．堆排序
  @" g- B8 C/ R: w0 c  t8 Z[ ]25．下列排序算法中，时间复杂度不受数据初始状态影响，恒为0(nlog2n)是
2 v3 H( b2 I6 N# jA. 堆排序                              B. 冒泡排序   
C. 直接选择排序                        D. 快速排序
# W1 V$ ?6 n( N- p/ j[ ]26. 有一程序段:i=1；WHILE(i<n) i=i*2;其中带下划线语句的执行次数的数量级是
* o7 ~4 N3 J2 \9 C8 M$ DA. O(n)                                 B. O(log2n)   
7 q# w  D0 u; ^5 j  C. O(nlog2n)                             D. O(n2)
# y8 g2 }- \: s* V# i8 m. ?[ ]27.无头结点的链队列Q为空的条件是
! D/ r/ I; R4 P/ A0 H+ O9 y4 aA. Q->front->next==Q->real=NULL                             
6 P2 A' p- S. H% s$ r2 W4 ]% @/ s* N0 yB. Q->front==Q->real<>NULL      
$ M* q8 r5 }1 k6 rC. Q->real==Q->front=NULL                              
7 W: L' t' [3 ID. Q->real->next==Q->front<>NULL
+ h, D) }0 F: X$ s[ ]28. 有向图G可拓扑排序的判别条件是
0 k+ {$ _5 x! C& @7 M+ p, eA. 不存在环                  B. 存在环        
* n9 e4 T* c7 KC. 存在入度为零的结点        D. 存在出度为零的结点   
[ ]29. 对n个记录的文件进行快速排序，所需要的辅助存储空间
# |6 B4 C' S( ?3 C      A. O（1）        B. O（n）      C. O（1og2n）       D. O（n2）
[ ]30. 下列排序算法中，在待排序数据已基本有序时，效率最高的排序方法是
: q8 R8 \4 z4 S- P       A．插入排序                    B．选择排序     
8 k7 V: H8 F4 qC．快速排序                    D．堆排序
二、综合题（共4题，每题10分）
31、阅读算法，在横线处填入语句或注释。
void exchange_L( Linklist &L，int m ) {
// 带头结点的单链表中前m个结点和后n个结点的整体互换
: m& o/ p4 v1 `       if ( m && L->next ) { // 链表非空
            p = L->next;
4 ~( [* O$ ]/ u, s$ F! G( s            （1）// k取值
4 r/ B3 w+ K' l+ A- F             while( k< m && p ) { //（2）
           p = p->next; ++k;
( x+ O4 V4 i! I; S8 o       } // while
             if (p && （3）) { // n!=0 时才需要修改指针
6 W: R4 N% W1 W. ^  J/ [             ha = L->next;  //  以指针 ha 记a1结点的位置
                 L->next= p->next; // 将 b1 结点链接在头结点后
                 p->next =（4）;  // 设am的后继
                 
  q = L->next; // 令q 指向 b1结点
) }3 t$ U+ P/ p0 Z                 while (q->next)
                      q = q->next; // 查找 bn 结点
                 q->next =（5）//将第 a1 结点链接到 bn 结点之后
& ^' x$ T  Y$ W! p+ x2 r+ x: i7 \ } // if(p)
                              } // if(m)
                             } // exchange_L
. v# P" e! M% F5 m( q% @

6 [& N# b- A! L! T
7 r7 E  l# n" p- \: M
. m& U& j/ G5 w# ?+ Y* m7 c9 C

( }3 V) R; _! H5 D- P
/ F9 g0 s% `1 {4 y
. i. k+ j7 n+ ^/ z/ T. c


4 h" J+ V0 b# D; Q, W: i32．一个仅包含二元运算符的算术表达式，以二叉链表形式存储在二叉树T中，设计算法F1实现求值，并指出遍历的方式。

4 o; \" K% ^/ R& C: I8 A& n" |& C
; {# f5 j  N* l: Q/ C
2 U8 ?7 b# ]4 P4 u

2 [% ~! t+ [) }" j, l



2 [; F* V& h3 a+ W# B% B1 b
- b, A. X$ t( F, u! I, Z1 _
- U( k( ~/ n4 c! x0 d' K' `* _
' b4 f' W3 u  Z* ]

9 W0 w9 o2 b) ]2 b; C  D
9 f. U: [5 V9 q8 D3 K
9 M5 m( V6 f0 N1 a% ^& @6 @33．设计算法实现以逆邻接表为存储结构的有向图的拓扑排序。
逆邻接表存储结构定义如下：
' f, X9 _$ U( O1 q& q: Q6 v顶点结构                       表结点结构
vexdata        firstin
0 Q6 _3 Z) ]. J. l: r& iadjvex        nfo        firstarc




% z5 w" P/ P. K1 Y* s. D
; D0 x8 F4 d  y) q3 I6 f
5 `4 O# E. T; r  g8 Z) B) B& h# q



! @% p8 t# {4 V1 }* K

6 v, [) w+ c& z+ e/ J6 I* C
1 m# y% [2 h- f$ N. q# b
$ A6 @. T) d+ m2 o4 J

) S; z$ I9 k0 q5 O5 Y34. 设哈希表长为13，采用线性探测法解决冲突，哈希函数定义为：H(key)=key%13。
6 m* G7 ^6 _1 c5 h试求：（1）填上依次插入关键字25，20，36，15，41，52，29，72，67后的哈希表。
（2）计算等概率情况下，查找成功的平均查找长度。
0 i- D; H# P* O  A- f3 B; l  x




# u9 r; d% L+ B8 |/ U! W
8 A3 @  \1 M- e' O# h

) H7 f$ B. x5 ]! s

- N% w- ]0 g. p7 L5 ]% I! u7 j

) x9 I( }% z. C: p# {4 k, V
3 Y* H/ b6 _" R9 j( T

+ \5 ]+ f9 _& G9 g& I( c2 u( C+ L
1 c) ?; b, O0 Z( M$ q
7 B- F* F, n1 c* b* A0 M
; o. e) Y! }8 z4 ?5 I1 G