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

同学情

东 北 大 学 继 续 教 育 学 院

数据结构II X 试 卷（作业考核 线上2）  A  卷
# @& S$ B- G6 T: m
学习中心：            院校学号：             姓名            

( A2 C( A& L8 n8 r（共    6    页）         
总分        题号        一        二        三        四        五        六        七        八        九        十
$ t- K" ]# G6 s/ b( z, W6 E# E        得分                                                                               
一、单选题（共30题，每题2分）
[ ]1．抽象数据类型的三个组成部分分别为
A．数据对象、数据关系和基本操作
      B．数据元素、逻辑结构和存储结构
3 Q; e* [- s7 q+ K- t* t9 T      C．数据项、数据元素和数据类型
1 v! e- |: X5 M( j: k. X# u      D．数据元素、数据结构和数据类型
[ ]2．要求相同逻辑结构的数据元素具有相同的特性，其含义为
A. 数据元素具有同一的特点
& G6 \! q9 m# {8 N$ wB. 不仅数据元素包含的数据项的个数相同，而且其对应数据项的类型要一致
C. 每个数据元素都一样
D. 仅需要数据元素包含的数据项的个数相同
+ D; V1 W9 p1 g* {% b% r5 G" S( Q! M[ ]3．下列各式中，按增长率由小至大的顺序正确排列的是
A． ，n！，2n ，n3/2                    
B．n3/2，2n，nlogn，2100
      C．2n，log n，nlogn，n3/2               
" d& J5 l' Z& C8 w0 }# gD．2100，logn, 2n, nn
$ l7 Z: H% G! O: q! h; ^" g9 O[ ]4. 在下列哪种情况下，线性表应当采用链表表示为宜
3 e; M' P+ D7 f7 ~+ ^6 u' _      A.经常需要随机地存取元素         
B.经常需要进行插入和删除操作
+ n) f& ]3 c5 _8 S8 r      C.表中元素需要占据一片连续的存储空间   
) M& |% Q- u5 S5 M& R; X' m+ LD.表中元素的个数不变
[ ]5．设指针p指向双链表的某一结点，则双链表结构的对称性是
" M. A6 i: u& h5 YA. p->prior->next=p->next->next;      
B.  p->prior->prior=p->next->prior;
C. p->prior->next=p-> next->prior;     
6 |" E- C5 |# tD.  p->next->next= p->prior->prior;
" D' ]+ V. E. e5 a& w: q. l& Q[ ]6. 已知指针p和q分别指向某带头结点的单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为
    A. s->next=q；p->next=s->next；
    B. s->next=p；q->next=s->next；
  P( b* z. Q5 n# R. }& _# hC. p->next=s->next；s->next=q；
D. q->next=s->next；s->next=p；
[ ]7. 栈和队列的共同特点是
9 m. x9 e4 I9 p7 AA.只允许在端点处插入和删除元素
B.都是先进后出   
C.都是先进先出
' k( ~8 q) ?" YD.没有共同点
0 O" ~* U, L% A% I9 a4 }[ ]8. 对于链队列，在进行插入运算时.
      A. 仅修改头指针         
; H+ X; S2 l9 jB. 头、尾指针都要修改
      C. 仅修改尾指针              
5 L& L" ^% F& R( {' y0 J( mD.头、尾指针可能都要修改
[ ]9．设有一个顺序栈的入栈序列是1、2、3，则3个元素都出栈的不同排列个数为
0 u) U, I% @: p7 `      A．4      B．5     C. 6     D. 7
6 p4 \- ?! Y' l) L- m6 H: _$ b& n[ ]10．设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是
! n: A7 @* N: i( p& `A．A，B，C，D               B．D，C，B，A   
C. A，C，D，B               D. D，A，B，C
; {# _: ?8 K; s[ ]11．表达式a*(b+c)-d的后缀表达式是
      A．abcd*+-    B．abc*+d-  C．abc+*d-   D．-+*abcd
8 |$ a3 Z- o& G9 N' w[ ]12．某二叉树的先序序列和后序序列正好相反，则该二叉树的特点一定是
A. 空或只有一个结点             B.高度等于其结点数
C. 任一结点无左孩子             D.任一结点无右孩子
[ ]13．下面的说法中正确的是
    (1)任何一棵二叉树的叶子结点在种遍历中的相对次序不变。
7 j2 H3 X$ {- o1 _, R$ P    (2)按二叉树定义，具有三个结点的二叉树共有6种。
7 k! m% {4 E' fA．(1)，(2)                       B．(1)   
/ ?) B! J  a9 b/ GC．(2)                            D．(1)，(2)都错
& Q1 M8 F0 e$ t  e4 U[ ]14．树有先序遍历和后序遍历，树可以转化为对应的二叉树。下面的
说法正确的是
      A．树的后序遍历与其对应的二叉树的先序遍历相同     
+ X5 |8 R* b  W6 GB．树的后序遍历与其对应的二叉树的中序遍历相同
9 {0 i, ~2 W6 ~  eC．树的先序序遍历与其对应的二叉树的中序遍历相同      
) ?! e! O# \& l2 C2 D0 S9 fD．以上都不对
[ ]15．下列说法正确的是
    (1)二又树按某种方式线索化后，任一结点均有前趋和后继的线索
, p% b$ B, M# O1 O3 ~- ]$ x    (2)二叉树的先序遍历序列中，任意一个结点均处于其子孙结点前
    (3)二叉排序树中任一结点的值大于其左孩子的值，小于右孩子的值
; p( ^8 Y" N/ b8 q; uA．(1)(2)(3)                     B．(1)(2)   
# Y! Z4 q& Z" p9 k8 dC．(1)(3)                        D．都不对
4 d: Z. J; G% I! @3 s[ ]16. 二叉树的第k层的结点数最多为
      A．2k-1                          B.2K+1      
7 n- S: ?4 Y- s/ fC.2K-1                           D. 2k-1
0 L% E  U; s6 x[ ]17．以下说法不正确的是
     A．无向图中的极大连通子图称为连通分量
     B．连通图的广度优先搜索中一般采用队列来暂存刚访问过的顶点
     C．图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点
. w2 s6 J, G2 q$ j& y     D．有向图的遍历不可采用广度优先搜索
[ ]18．有向图G用邻接矩阵A存储，则顶点i的入度等于A中
4 Y# e1 l1 [7 ?A. 第i行1的元素之和            B. 第i列1的元素之和
C. 第i行0的元素个数            D. 第i列非0的元素个数
* H4 I' I; J4 L0 Z$ s* ]% E& o& y[ ]19. 设有6个结点的无向图，该图确保是一个连通图的有效边条数至
少应是
) A  t3 b2 B, z" }! yA.5              B.6              C.7             D.8
[ ]20．.下图的邻接表中，从顶点V1 出发采用深度优先搜索法遍历该图，则可能的顶点序列是
9 E% \9 [& e6 c( @8 F& g9 l+ W' e  
A. V1V2V3V4V5          B. V1V2V3V5V4
C. V1V4V3V5V2          D.V1V3V4V5V2
3 S& ]/ B! Q" @' U% R& y% A) {) c) C[ ]21．关键路径是事件结点网络中
9 ^( q7 s5 N( D3 ^; T* Z      A．从源点到汇点的最长路径    B．从源点到汇点的最短路径
      C．最长的回路                D．最短的回路
2 Z) X( P% {$ h) ?7 c" `$ ?+ I[ ]22．设哈希表长为14，哈希函数H(key)=key％11，表中已有数据的关键字为15，38，61，84，四个，现将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是
( d  c6 J1 k% G: }8 t      A．8       B．3        C．5        D．9
[ ]23．.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为0，右孩子的平衡因子为1，则应调整以使其平衡，所作的平衡旋转是
A. LL型           B. LR型       C. RL型       D. RR型
[ ]24．下列排序算法中，在待排序数据已基本有序时，效率最高的排序方法是
2 P" D0 W, B1 k+ S7 S: G9 C4 q" V      A．插入排序                           B．选择排序   
C．快速排序                           D．堆排序
6 _* ]% ]! W% s6 c+ ^[ ]25．下列排序算法中，时间复杂度不受数据初始状态影响，恒为0(nlog2n)是
$ }! H0 _/ b8 cA. 堆排序                              B. 冒泡排序   
C. 直接选择排序                        D. 快速排序
4 P4 l/ e3 K1 |3 L6 U5 `/ _[ ]26. 有一程序段:i=1；WHILE(i<n) i=i*2;其中带下划线语句的执行次数的数量级是
$ |2 Z1 U$ y0 b7 s: v( v  n  oA. O(n)                                 B. O(log2n)   
  C. O(nlog2n)                             D. O(n2)
& K# L+ E+ t" i[ ]27.无头结点的链队列Q为空的条件是
A. Q->front->next==Q->real=NULL                             
B. Q->front==Q->real<>NULL      
6 a5 {5 i: X7 T1 K& P. a7 pC. Q->real==Q->front=NULL                              
3 M7 p3 A$ o7 W! T8 X3 e" zD. Q->real->next==Q->front<>NULL
[ ]28. 有向图G可拓扑排序的判别条件是
8 X/ T, K. I( _  Q. A; \A. 不存在环                  B. 存在环        
C. 存在入度为零的结点        D. 存在出度为零的结点   
[ ]29. 对n个记录的文件进行快速排序，所需要的辅助存储空间
      A. O（1）        B. O（n）      C. O（1og2n）       D. O（n2）
[ ]30. 下列排序算法中，在待排序数据已基本有序时，效率最高的排序方法是
       A．插入排序                    B．选择排序     
C．快速排序                    D．堆排序
, ^  _% b& Z$ ~二、综合题（共4题，每题10分）
- v7 V! D- W/ w! K+ ], d31、阅读算法，在横线处填入语句或注释。
void exchange_L( Linklist &L，int m ) {
; r/ y: `3 R  K; V' O( ~9 N# L // 带头结点的单链表中前m个结点和后n个结点的整体互换
       if ( m && L->next ) { // 链表非空
            p = L->next;
            （1）// k取值
             while( k< m && p ) { //（2）
* c2 b& Z% G$ d: t4 T: g           p = p->next; ++k;
       } // while
% U+ w0 L" f% d             if (p && （3）) { // n!=0 时才需要修改指针
             ha = L->next;  //  以指针 ha 记a1结点的位置
                 L->next= p->next; // 将 b1 结点链接在头结点后
                 p->next =（4）;  // 设am的后继
# b" ?. F% d8 q5 X$ F2 [! _4 Y4 o                 
  q = L->next; // 令q 指向 b1结点
                 while (q->next)
                      q = q->next; // 查找 bn 结点
- H# b# `4 X" I. T) |                 q->next =（5）//将第 a1 结点链接到 bn 结点之后
} // if(p)
- N, p" {. P+ X8 T                              } // if(m)
                             } // exchange_L

$ |+ `! Q, G8 z/ e


  |( J, j' I; [: m
; q5 K8 R8 ?4 g" Q/ k
0 E0 A/ Z5 |2 P9 {+ M# X
1 @& o" O2 e  E% c! p

1 x  a$ a3 l! p6 `$ }/ j
, }7 }6 ?4 ?: d* }
! v3 L* r) _8 n& @4 N32．一个仅包含二元运算符的算术表达式，以二叉链表形式存储在二叉树T中，设计算法F1实现求值，并指出遍历的方式。
2 s9 {, P/ Q: f9 P* |

' n: s* r% Y, G
" O! L" `! g- Y5 B0 t1 ^, @





- m- N- \( F: G2 L7 @* p# Q& R
9 U: z9 T( n9 ~5 H4 R  s9 U, L/ y1 S
) ], f9 a- K# f. {( ]


3 o) ?+ l% p% P9 }2 a+ Y3 r5 V
0 T! f! F" k( @. d) l3 _
2 E% ]) H; z" H. T33．设计算法实现以逆邻接表为存储结构的有向图的拓扑排序。
逆邻接表存储结构定义如下：
+ M7 X+ j0 ?  b$ S/ k! h7 Y顶点结构                       表结点结构
vexdata        firstin
adjvex        nfo        firstarc
6 s6 n2 u7 ~1 D




; m6 x+ P; k9 X



- O/ M  b3 N2 c. p9 q5 `
* q6 F) R2 R$ p+ g1 R" a
' B- d  K( E% e
" o& t7 x( l6 x/ {6 a, z1 Y



34. 设哈希表长为13，采用线性探测法解决冲突，哈希函数定义为：H(key)=key%13。
试求：（1）填上依次插入关键字25，20，36，15，41，52，29，72，67后的哈希表。
; R2 j* [; s1 h8 w（2）计算等概率情况下，查找成功的平均查找长度。


( `6 l; i" l3 }; J5 C5 d  @" V


% W  N. j5 k* n3 F: T5 }3 l/ W" N  a
5 \* ]- U7 f7 h2 q* p
2 W1 `3 T" r, F/ v


4 @0 \: @6 ?% s) H' x& ~! K/ w6 r
/ X! u/ p8 D. `5 c5 R7 j* a

) z) v3 Z4 r+ y1 I
( c4 ~5 Q8 S7 K0 X) t' A3 e
. ^2 ~2 c* `  V) ?6 q
( r$ r$ ]7 m* h+ y
$ p. m' m+ s9 L, r- X" X


/ r. J4 E) z* e  \1 t1 J# c