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

奥鹏在线作业

东 北 大 学 继 续 教 育 学 院
1 J7 x6 F" V( B/ W' W9 {! \4 ]
2 m$ N1 d, _. B; R& U8 p4 e- j+ c 数据结构II X 试 卷（作业考核 线上2）  A  卷

学习中心：            院校学号：             姓名            

9 V8 e. J" K8 I. ?（共    6    页）         
总分        题号        一        二        三        四        五        六        七        八        九        十
$ M& f; t" h" h# \/ u        得分                                                                               
7 M' S5 G2 |4 B$ C一、单选题（共30题，每题2分）
[ ]1．抽象数据类型的三个组成部分分别为
A．数据对象、数据关系和基本操作
6 V: g4 K$ {- J  C      B．数据元素、逻辑结构和存储结构
      C．数据项、数据元素和数据类型
7 d2 ^2 ]9 ?- _6 I      D．数据元素、数据结构和数据类型
[ ]2．要求相同逻辑结构的数据元素具有相同的特性，其含义为
( Z# ~+ P' l4 L" t6 r2 iA. 数据元素具有同一的特点
B. 不仅数据元素包含的数据项的个数相同，而且其对应数据项的类型要一致
9 T( o# m$ W3 H; P/ r3 ?; p  iC. 每个数据元素都一样
! j9 Y, K0 U; P8 RD. 仅需要数据元素包含的数据项的个数相同
[ ]3．下列各式中，按增长率由小至大的顺序正确排列的是
A． ，n！，2n ，n3/2                    
B．n3/2，2n，nlogn，2100
      C．2n，log n，nlogn，n3/2               
D．2100，logn, 2n, nn
1 N# d" ^# r% a, Q4 q[ ]4. 在下列哪种情况下，线性表应当采用链表表示为宜
/ ^! R; G' @6 S: R      A.经常需要随机地存取元素         
1 X0 t" p$ |6 ~# Q1 z" g; ]  ~B.经常需要进行插入和删除操作
4 M/ _- y" q1 W+ v0 n( j      C.表中元素需要占据一片连续的存储空间   
D.表中元素的个数不变
[ ]5．设指针p指向双链表的某一结点，则双链表结构的对称性是
A. p->prior->next=p->next->next;      
B.  p->prior->prior=p->next->prior;
( i' i# {# |- gC. p->prior->next=p-> next->prior;     
& f3 J1 `' B: }4 \; N* R3 g; b7 aD.  p->next->next= p->prior->prior;
[ ]6. 已知指针p和q分别指向某带头结点的单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为
    A. s->next=q；p->next=s->next；
    B. s->next=p；q->next=s->next；
$ i% S- ~: ]$ t1 X. c* QC. p->next=s->next；s->next=q；
D. q->next=s->next；s->next=p；
% ?: F( w3 |" F[ ]7. 栈和队列的共同特点是
A.只允许在端点处插入和删除元素
; t9 r, h. D! s" f, e6 lB.都是先进后出   
. d. D7 k' {3 v3 p1 D( VC.都是先进先出
D.没有共同点
& e$ c' @" m+ [9 U6 k% r[ ]8. 对于链队列，在进行插入运算时.
      A. 仅修改头指针         
8 p& B. m# I2 o4 N8 W4 GB. 头、尾指针都要修改
      C. 仅修改尾指针              
4 P: M- N. v- cD.头、尾指针可能都要修改
[ ]9．设有一个顺序栈的入栈序列是1、2、3，则3个元素都出栈的不同排列个数为
0 m, d* y( ^$ {8 M      A．4      B．5     C. 6     D. 7
[ ]10．设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是
( l9 X2 c+ ~& {- P; V& |1 b! a# b1 CA．A，B，C，D               B．D，C，B，A   
/ h- l7 d3 h1 eC. A，C，D，B               D. D，A，B，C
2 i! D% O5 z( L/ y- L2 Q0 M+ s& g7 C[ ]11．表达式a*(b+c)-d的后缀表达式是
      A．abcd*+-    B．abc*+d-  C．abc+*d-   D．-+*abcd
! x) _% }. c1 e+ M* e[ ]12．某二叉树的先序序列和后序序列正好相反，则该二叉树的特点一定是
: v" P+ J1 F, V' x$ x( ~8 \/ ~A. 空或只有一个结点             B.高度等于其结点数
C. 任一结点无左孩子             D.任一结点无右孩子
9 K8 h% k! W7 V5 G% ?[ ]13．下面的说法中正确的是
5 Y8 I/ }. h# K    (1)任何一棵二叉树的叶子结点在种遍历中的相对次序不变。
    (2)按二叉树定义，具有三个结点的二叉树共有6种。
A．(1)，(2)                       B．(1)   
* x1 d/ X$ K) X& ?C．(2)                            D．(1)，(2)都错
& Y1 p3 o. W5 m! J7 C% u# Q[ ]14．树有先序遍历和后序遍历，树可以转化为对应的二叉树。下面的
% Q; f2 C1 O' }) e+ L2 W# n2 C2 u说法正确的是
8 F3 _. e+ E4 H: G      A．树的后序遍历与其对应的二叉树的先序遍历相同     
3 Z  p4 Y  Y2 t- v+ B- D% LB．树的后序遍历与其对应的二叉树的中序遍历相同
( q* K/ G& ~3 F9 N0 v* h( B( C0 d+ dC．树的先序序遍历与其对应的二叉树的中序遍历相同      
D．以上都不对
+ @. j; ~/ W; N[ ]15．下列说法正确的是
, L. v+ [  i5 ?2 A    (1)二又树按某种方式线索化后，任一结点均有前趋和后继的线索
    (2)二叉树的先序遍历序列中，任意一个结点均处于其子孙结点前
    (3)二叉排序树中任一结点的值大于其左孩子的值，小于右孩子的值
4 H# o) D& \) n" OA．(1)(2)(3)                     B．(1)(2)   
C．(1)(3)                        D．都不对
[ ]16. 二叉树的第k层的结点数最多为
5 F: j5 ^0 f, u+ o7 N  o' y2 Z      A．2k-1                          B.2K+1      
+ c1 e  d# }* P( v% b, X( UC.2K-1                           D. 2k-1
[ ]17．以下说法不正确的是
, B/ H, o: D; {" E; U- z     A．无向图中的极大连通子图称为连通分量
- u5 u+ o! I9 M) y& j; H     B．连通图的广度优先搜索中一般采用队列来暂存刚访问过的顶点
     C．图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点
     D．有向图的遍历不可采用广度优先搜索
7 f5 A# [1 N3 f[ ]18．有向图G用邻接矩阵A存储，则顶点i的入度等于A中
6 d, I" Y- e& TA. 第i行1的元素之和            B. 第i列1的元素之和
C. 第i行0的元素个数            D. 第i列非0的元素个数
[ ]19. 设有6个结点的无向图，该图确保是一个连通图的有效边条数至
( o2 H' [7 u  j4 i0 C( j少应是
A.5              B.6              C.7             D.8
7 A. y1 B" a. o [ ]20．.下图的邻接表中，从顶点V1 出发采用深度优先搜索法遍历该图，则可能的顶点序列是
9 u' U% ^" D' a/ l* @6 |) J  
2 ~9 X# h7 H/ B4 TA. V1V2V3V4V5          B. V1V2V3V5V4
3 ]7 W0 D4 `/ l& e1 s2 MC. V1V4V3V5V2          D.V1V3V4V5V2
: E: h% V: X! e5 d" |/ R( }[ ]21．关键路径是事件结点网络中
1 R% D  p% }1 E5 P* [" o9 }0 U5 j( ?      A．从源点到汇点的最长路径    B．从源点到汇点的最短路径
      C．最长的回路                D．最短的回路
. R9 j! E# O" ^$ `# \[ ]22．设哈希表长为14，哈希函数H(key)=key％11，表中已有数据的关键字为15，38，61，84，四个，现将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是
      A．8       B．3        C．5        D．9
+ A! R8 u6 C" L2 V[ ]23．.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为0，右孩子的平衡因子为1，则应调整以使其平衡，所作的平衡旋转是
3 I$ I; |1 W& X- L1 L, gA. LL型           B. LR型       C. RL型       D. RR型
, n6 R6 [: C. k. ][ ]24．下列排序算法中，在待排序数据已基本有序时，效率最高的排序方法是
      A．插入排序                           B．选择排序   
C．快速排序                           D．堆排序
+ _# b3 {: E" o9 d0 a% @$ A& M[ ]25．下列排序算法中，时间复杂度不受数据初始状态影响，恒为0(nlog2n)是
A. 堆排序                              B. 冒泡排序   
' |$ U$ `2 h3 Y& {9 l% ?) I) kC. 直接选择排序                        D. 快速排序
. L* m6 ]/ H' m[ ]26. 有一程序段:i=1；WHILE(i<n) i=i*2;其中带下划线语句的执行次数的数量级是
A. O(n)                                 B. O(log2n)   
  C. O(nlog2n)                             D. O(n2)
[ ]27.无头结点的链队列Q为空的条件是
A. Q->front->next==Q->real=NULL                             
B. Q->front==Q->real<>NULL      
0 i+ A* _- ?) O4 j  }7 j! gC. Q->real==Q->front=NULL                              
D. Q->real->next==Q->front<>NULL
  V& T6 P9 u& ?$ v- F[ ]28. 有向图G可拓扑排序的判别条件是
. h' i9 }/ e  \! H# v3 S7 ?8 O% aA. 不存在环                  B. 存在环        
& H9 j+ s9 t1 }C. 存在入度为零的结点        D. 存在出度为零的结点   
[ ]29. 对n个记录的文件进行快速排序，所需要的辅助存储空间
      A. O（1）        B. O（n）      C. O（1og2n）       D. O（n2）
[ ]30. 下列排序算法中，在待排序数据已基本有序时，效率最高的排序方法是
2 x6 z# X: ~- k7 L       A．插入排序                    B．选择排序     
8 u! V# N+ u$ S8 I6 P9 x+ EC．快速排序                    D．堆排序
& B4 G; ]4 B1 \) S: Q二、综合题（共4题，每题10分）
' s9 s' O7 A( A4 A2 H3 L& s31、阅读算法，在横线处填入语句或注释。
void exchange_L( Linklist &L，int m ) {
3 D# a" b$ U6 s: {: B% f // 带头结点的单链表中前m个结点和后n个结点的整体互换
       if ( m && L->next ) { // 链表非空
' A3 d* ^. x8 j$ _3 T" O1 i: m            p = L->next;
            （1）// k取值
             while( k< m && p ) { //（2）
           p = p->next; ++k;
       } // while
             if (p && （3）) { // n!=0 时才需要修改指针
             ha = L->next;  //  以指针 ha 记a1结点的位置
6 N. D: B% U. b- ~4 Z2 \& z: n                 L->next= p->next; // 将 b1 结点链接在头结点后
                 p->next =（4）;  // 设am的后继
                 
9 Z& Y* U8 ^: g0 X  q = L->next; // 令q 指向 b1结点
                 while (q->next)
  Z9 X. D8 s9 N& l" e5 n                      q = q->next; // 查找 bn 结点
8 _( G( V1 S5 f                 q->next =（5）//将第 a1 结点链接到 bn 结点之后
; F( O+ ?9 h6 v* N+ w. v& @ } // if(p)
                              } // if(m)
2 z' X* T2 G, G! V2 u8 \. U                             } // exchange_L

& q" D& x2 E0 ~6 D& v
0 D0 a, Y& W' z+ t- G

( X5 k5 F4 C5 J$ H* ~4 E* b




9 G' V3 P3 R% f7 H1 t% g

# D; H( ^7 d6 a" z32．一个仅包含二元运算符的算术表达式，以二叉链表形式存储在二叉树T中，设计算法F1实现求值，并指出遍历的方式。


0 t, @0 Y3 m# G9 f9 f, H1 z



6 S0 D! y& B$ \7 T


) [, O; f  U# Z, `: [
5 ], J) Q& G: c6 s# f; i+ s
: J! Z4 `% r  L( r5 l  m, _$ ]


/ l4 X5 R# ?1 G, r1 _

33．设计算法实现以逆邻接表为存储结构的有向图的拓扑排序。
逆邻接表存储结构定义如下：
& k4 I* r0 i/ C  f7 V顶点结构                       表结点结构
vexdata        firstin
adjvex        nfo        firstarc

/ w7 p1 ~: x! V. N( q


& ]: ]. n5 S6 o$ h2 Z- Y( Z
% g. i, b3 M) T1 D$ ~

1 _  [, D2 w- e% U5 {
& G2 X) q! R0 |  s* x% a) C
. o, C: n2 z$ w- r  D
7 l6 i/ I% j  x& O) B: g4 r' q
; q8 C2 b) _. X8 O0 s  S



) Q) O2 i' S9 _& o8 I
34. 设哈希表长为13，采用线性探测法解决冲突，哈希函数定义为：H(key)=key%13。
试求：（1）填上依次插入关键字25，20，36，15，41，52，29，72，67后的哈希表。
& O8 B. `2 d) Z（2）计算等概率情况下，查找成功的平均查找长度。


/ A1 m4 ?, h% ~; C7 m( H

6 a+ E+ _  J/ h) Y" d& S, V

+ o; [$ N! c3 o7 @


. L2 d# E4 N/ i  K6 X



- @8 d/ v' I4 r# r# i
( ?2 `* r+ _9 S1 A" s) y  `' l$ X; A) f



3 t- k, z2 K+ L! e
  e6 v4 v* O$ Z- h6 Q. g0 P
6 ~' g- g8 m+ }: r/ m