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

奥鹏在线作业

东 北 大 学 继 续 教 育 学 院
$ b: m7 B6 {; D( [/ k  j# k
数据结构II X 试 卷（作业考核 线上2）  A  卷
  p1 U7 |* m2 p$ I
2 D0 C' v$ \) L9 `, S: D学习中心：            院校学号：             姓名            
: K0 y) Z$ R$ u$ H1 P5 |! ^
8 [7 i( N( B1 K6 |# g（共    6    页）         
总分        题号        一        二        三        四        五        六        七        八        九        十
  |" H/ Z9 p( G        得分                                                                               
一、单选题（共30题，每题2分）
[ ]1．抽象数据类型的三个组成部分分别为
A．数据对象、数据关系和基本操作
      B．数据元素、逻辑结构和存储结构
4 `. _! B! r5 H7 J7 b      C．数据项、数据元素和数据类型
5 X: m. \/ M% ]$ T& l5 T      D．数据元素、数据结构和数据类型
% s! T. J5 f/ c[ ]2．要求相同逻辑结构的数据元素具有相同的特性，其含义为
! P  ~1 e( e/ S7 `1 t" WA. 数据元素具有同一的特点
B. 不仅数据元素包含的数据项的个数相同，而且其对应数据项的类型要一致
C. 每个数据元素都一样
- a( S0 F4 g9 ?* h4 y! r9 ?  E* w, WD. 仅需要数据元素包含的数据项的个数相同
/ \# j$ q' A& z& x  V  W[ ]3．下列各式中，按增长率由小至大的顺序正确排列的是
A． ，n！，2n ，n3/2                    
) D6 g' r  o4 u  o" fB．n3/2，2n，nlogn，2100
      C．2n，log n，nlogn，n3/2               
D．2100，logn, 2n, nn
[ ]4. 在下列哪种情况下，线性表应当采用链表表示为宜
+ F4 m2 T  f9 w/ K1 P      A.经常需要随机地存取元素         
B.经常需要进行插入和删除操作
      C.表中元素需要占据一片连续的存储空间   
# A& Y2 D9 S" U) G& d# O( T" n0 _D.表中元素的个数不变
[ ]5．设指针p指向双链表的某一结点，则双链表结构的对称性是
A. p->prior->next=p->next->next;      
% a3 n8 n+ \% r& a3 s1 \B.  p->prior->prior=p->next->prior;
C. p->prior->next=p-> next->prior;     
D.  p->next->next= p->prior->prior;
9 P' V) _6 h: q3 {" m[ ]6. 已知指针p和q分别指向某带头结点的单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为
& v1 t9 H4 |# `    A. s->next=q；p->next=s->next；
    B. s->next=p；q->next=s->next；
; P9 L" H0 {0 eC. p->next=s->next；s->next=q；
D. q->next=s->next；s->next=p；
[ ]7. 栈和队列的共同特点是
A.只允许在端点处插入和删除元素
; f% T+ [% b  AB.都是先进后出   
C.都是先进先出
9 j; Y) T% H6 O7 Y. o' T7 t4 UD.没有共同点
[ ]8. 对于链队列，在进行插入运算时.
      A. 仅修改头指针         
B. 头、尾指针都要修改
      C. 仅修改尾指针              
D.头、尾指针可能都要修改
/ a6 c3 F8 H3 p9 G) w/ Z- L6 I[ ]9．设有一个顺序栈的入栈序列是1、2、3，则3个元素都出栈的不同排列个数为
/ p5 S7 O8 u4 T: B# W      A．4      B．5     C. 6     D. 7
[ ]10．设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是
A．A，B，C，D               B．D，C，B，A   
C. A，C，D，B               D. D，A，B，C
[ ]11．表达式a*(b+c)-d的后缀表达式是
      A．abcd*+-    B．abc*+d-  C．abc+*d-   D．-+*abcd
[ ]12．某二叉树的先序序列和后序序列正好相反，则该二叉树的特点一定是
A. 空或只有一个结点             B.高度等于其结点数
/ Q) l% d/ G. R% D9 ^) U/ uC. 任一结点无左孩子             D.任一结点无右孩子
9 q/ g- d1 q/ u) d9 w( e+ E[ ]13．下面的说法中正确的是
8 d- X$ A. g1 {! t9 o9 _% q' N9 p  G    (1)任何一棵二叉树的叶子结点在种遍历中的相对次序不变。
    (2)按二叉树定义，具有三个结点的二叉树共有6种。
: ]% N7 i  W3 q: P- K/ l: MA．(1)，(2)                       B．(1)   
- l' n2 N  i# l- ~* D& o( |! `C．(2)                            D．(1)，(2)都错
7 A7 k/ }& ?+ r- Q+ L! b[ ]14．树有先序遍历和后序遍历，树可以转化为对应的二叉树。下面的
, g+ B% _4 F7 P4 B说法正确的是
2 a" a* N% r. f      A．树的后序遍历与其对应的二叉树的先序遍历相同     
B．树的后序遍历与其对应的二叉树的中序遍历相同
C．树的先序序遍历与其对应的二叉树的中序遍历相同      
$ X4 }! r- a( a* V8 FD．以上都不对
7 H' ^" `4 t+ o[ ]15．下列说法正确的是
' A1 p+ @2 {& L/ a! f& H+ B    (1)二又树按某种方式线索化后，任一结点均有前趋和后继的线索
    (2)二叉树的先序遍历序列中，任意一个结点均处于其子孙结点前
    (3)二叉排序树中任一结点的值大于其左孩子的值，小于右孩子的值
+ u# n4 f( q7 O) s. GA．(1)(2)(3)                     B．(1)(2)   
( L; S8 K: N* ]: o9 @& x; w1 k& i1 rC．(1)(3)                        D．都不对
[ ]16. 二叉树的第k层的结点数最多为
      A．2k-1                          B.2K+1      
C.2K-1                           D. 2k-1
/ N$ W& K; B5 a. E[ ]17．以下说法不正确的是
     A．无向图中的极大连通子图称为连通分量
8 [; u( K4 Y& n7 W" N! c/ {0 i! v" E     B．连通图的广度优先搜索中一般采用队列来暂存刚访问过的顶点
! K: @* C- _; R: \+ ^) |     C．图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点
     D．有向图的遍历不可采用广度优先搜索
[ ]18．有向图G用邻接矩阵A存储，则顶点i的入度等于A中
A. 第i行1的元素之和            B. 第i列1的元素之和
8 I7 S/ M' c2 p. ?0 J* \C. 第i行0的元素个数            D. 第i列非0的元素个数
[ ]19. 设有6个结点的无向图，该图确保是一个连通图的有效边条数至
少应是
A.5              B.6              C.7             D.8
, \' Z. T* y# k$ l' y [ ]20．.下图的邻接表中，从顶点V1 出发采用深度优先搜索法遍历该图，则可能的顶点序列是
  
A. V1V2V3V4V5          B. V1V2V3V5V4
3 [: t; c" K* y5 `+ L( p# iC. V1V4V3V5V2          D.V1V3V4V5V2
[ ]21．关键路径是事件结点网络中
      A．从源点到汇点的最长路径    B．从源点到汇点的最短路径
; T/ p$ M2 }3 G      C．最长的回路                D．最短的回路
3 r$ c! e' r3 [+ M8 j+ W; i[ ]22．设哈希表长为14，哈希函数H(key)=key％11，表中已有数据的关键字为15，38，61，84，四个，现将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是
      A．8       B．3        C．5        D．9
8 D8 A% F+ w! r. s, [/ t[ ]23．.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为0，右孩子的平衡因子为1，则应调整以使其平衡，所作的平衡旋转是
( O7 N/ F  _" O  z9 ?! ~# S6 S& x( FA. LL型           B. LR型       C. RL型       D. RR型
6 h; F0 S5 S; x# u: |[ ]24．下列排序算法中，在待排序数据已基本有序时，效率最高的排序方法是
3 }1 {6 O2 x/ X$ F0 {5 c      A．插入排序                           B．选择排序   
" j8 j7 v3 A" ZC．快速排序                           D．堆排序
( a( \+ y' W* e2 F8 s[ ]25．下列排序算法中，时间复杂度不受数据初始状态影响，恒为0(nlog2n)是
A. 堆排序                              B. 冒泡排序   
C. 直接选择排序                        D. 快速排序
; b, `4 o0 w# Y% M( h  c[ ]26. 有一程序段:i=1；WHILE(i<n) i=i*2;其中带下划线语句的执行次数的数量级是
! O. p; B/ k$ E8 B: rA. O(n)                                 B. O(log2n)   
" l7 P; i" Z: z5 }6 d  C. O(nlog2n)                             D. O(n2)
[ ]27.无头结点的链队列Q为空的条件是
6 z& l7 T; X3 @$ EA. Q->front->next==Q->real=NULL                             
2 b* i$ L# ?" ]B. Q->front==Q->real<>NULL      
C. Q->real==Q->front=NULL                              
D. Q->real->next==Q->front<>NULL
* ]5 k/ i# C/ T! x' m$ S( @1 h[ ]28. 有向图G可拓扑排序的判别条件是
( R" d: S/ S" I8 I8 H# _A. 不存在环                  B. 存在环        
C. 存在入度为零的结点        D. 存在出度为零的结点   
0 v+ R8 ]; q; I* K9 ?  b# ]4 e[ ]29. 对n个记录的文件进行快速排序，所需要的辅助存储空间
$ F1 V9 _5 m& C  c      A. O（1）        B. O（n）      C. O（1og2n）       D. O（n2）
1 h) W: i) n4 y5 x# O+ Q[ ]30. 下列排序算法中，在待排序数据已基本有序时，效率最高的排序方法是
1 `: _, F( _5 F  C       A．插入排序                    B．选择排序     
! ^6 O$ f! \8 j. D+ p$ K( j5 P) vC．快速排序                    D．堆排序
' P, Y& ?0 x; h* }. [二、综合题（共4题，每题10分）
31、阅读算法，在横线处填入语句或注释。
void exchange_L( Linklist &L，int m ) {
/ a4 l) Z) \  G& \1 o // 带头结点的单链表中前m个结点和后n个结点的整体互换
$ I+ p" R4 e- c       if ( m && L->next ) { // 链表非空
            p = L->next;
            （1）// k取值
             while( k< m && p ) { //（2）
           p = p->next; ++k;
" \6 `* [6 \9 y/ L, X  ], q5 l1 y8 z: {       } // while
             if (p && （3）) { // n!=0 时才需要修改指针
             ha = L->next;  //  以指针 ha 记a1结点的位置
4 U: S, b' x8 R" b  }' B, b9 O. _                 L->next= p->next; // 将 b1 结点链接在头结点后
                 p->next =（4）;  // 设am的后继
) V0 T5 }  h6 W5 q; h) d                 
) X( d+ d4 H( J& ?' k  q = L->next; // 令q 指向 b1结点
0 r1 F$ K$ P+ x  T0 a6 m                 while (q->next)
* ~! _0 o2 m3 J1 ]1 _( }, j, ]: A                      q = q->next; // 查找 bn 结点
                 q->next =（5）//将第 a1 结点链接到 bn 结点之后
} // if(p)
; C3 m% C' {3 T- j                              } // if(m)
                             } // exchange_L




, o; L& w6 y: z2 ?8 j' i0 C& s

( J$ Y4 K7 z+ q$ a" p* C
6 H9 |% x4 f( j8 Q1 c$ l

" ~$ N4 j$ \7 M0 h

3 J6 x( v% ?% v, R& O$ w7 {0 M32．一个仅包含二元运算符的算术表达式，以二叉链表形式存储在二叉树T中，设计算法F1实现求值，并指出遍历的方式。

9 Q* Q3 T! r; ~6 i- A5 J



- }1 s( l& `* s+ X, q0 ~! U/ _  `" g  n









6 _* T' a) e$ ^/ E" x5 f8 f
  ~% n  j6 _+ i) `- O( G4 X/ g33．设计算法实现以逆邻接表为存储结构的有向图的拓扑排序。
+ i1 _1 c8 D+ b# N7 e/ R逆邻接表存储结构定义如下：
- c' e7 A$ K* e, d6 }顶点结构                       表结点结构
& y) J2 |9 e8 p, F& G- ?) uvexdata        firstin
7 U8 g4 ^9 z9 l9 u+ l6 badjvex        nfo        firstarc
. ]8 H; H" Q9 K0 t9 x- [


, Y4 _  W' U& Q" t

, U; ^# k; O, Q3 }+ a

% E6 w) I: `& k$ ]5 q
4 h/ l& j- ^0 g+ R: Y# R



- z8 y: [* T/ m

/ M* f! C0 n) u! z3 F+ O

" x- y( \7 ]1 ^5 }4 I" _0 F34. 设哈希表长为13，采用线性探测法解决冲突，哈希函数定义为：H(key)=key%13。
试求：（1）填上依次插入关键字25，20，36，15，41，52，29，72，67后的哈希表。
  Z1 [- }' g2 |( w- [) @（2）计算等概率情况下，查找成功的平均查找长度。
, I" I2 [& ?6 G4 }


5 A0 D  T- T" k

- k& t$ X, g: e8 ^; J
7 n+ u, u& K# V0 S; ?, v
; g( o/ o* J" E5 }5 D9 l! [
1 M1 Y. T9 @% Q0 u

: J5 X  }# u: j" v
4 |/ C7 C' H) L- K+ x* @) Q+ [0 G

8 Q- J7 h" A# b: G$ R9 [  s
& U' R! x3 V4 g- z
! E# Y  C+ ]. E; Y+ B1 t
4 v# C1 z' X8 g- [1 ?
( l" F5 ]. @1 b* f
3 y# B( h2 Z$ h) ~/ P( }8 `7 @  x
7 F. O5 S. u  }! o3 `
# f0 Y  g; @" b% B3 K