16春学期《数据结构Ⅱ》在线作业1

李老师

16春学期《数据结构Ⅱ》在线作业1
试卷总分：100       测试时间：--
单选题  


一、单选题（共 20 道试题，共 100 分。）V 1.   
已知含6个顶点(v0，v1，v2，v3，v4，v5)的无向图的邻接矩阵如图所示，则从顶点v0出发进行深度优先遍历可能得到的顶点访问序列为



   

A. .(v0，v1，v2，v5，v4，v3)
   

B.
(v0，v1，v2，v3，v4，v5)

  

C.
   (v0，v1，v5，v2，v3，v4)

   

D.
.(v0，v1，v4，v5，v2，v3)

      满分：5  分
2.   
在下列存储形式中，哪一个不是树的存储形式

   

A. 双亲表示法                     
B. 孩子链表表示法
  

C.
孩子兄弟表示法                  

D.
顺序存储表示法

      满分：5  分
3.   
数组A[1..5，1..6]的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[5，5]的地址为

A.
1140                          

B.
1145   

C.
1120                          

D.
1125

      满分：5  分
4.   
一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为

   

A.  O(n)                           
B.  O(e)
   

C.
O(n+e)                           

D.
O(n2)

      满分：5  分
5.   
设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是

      

A.  A，B，C，D                    
B.  D，C，B，A   
      

C.
A，C，D，B         

D.  D，A，B，C
      满分：5  分
6.   
如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是

   

A.  有向完全图                    
B.  连通图
  

C.
强连通图                     

D.
有向无环图

      满分：5  分
7.   
在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系

      

A. 不一定相同                     
B. 都相同
     

C.
都不相同                       

D.
互为逆序

      满分：5  分
8.   
ISAM文件和VSAM文件的区别之一是

     

A.  前者是索引顺序文件，后者是索引非顺序文件
   

B.
前者只能进行顺序存取，后者只能进行随机存取

   

C.
前者建立静态索引结构，后者建立动态索引结构

   

D.
前者的存储介质是磁盘，后者的存储介质不是磁盘

      满分：5  分
9.   
若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为

A.
1和 5                              

B.
2和4         



C.
4和2                              

D.
5和1  

      满分：5  分
10.   
下列程序段 for(i=1;i<=n;i++) A[I,j]=0; 的时间复杂度是

A.
O(1)  

B.
O(0)   

C.  O(1+n)              
D.  O(n)  
      满分：5  分
11.   
下面关于数据结构正确的说法是

   

A.  一种数据类型  
   

B. 数据的存储结构
   

C. 一组性质相同的数据元素的集合
   

D.  相互之间存在一种或多种特定关系的数据元素的集合
      满分：5  分
12.   
当在二叉排序树中插入一个新结点时，若树中不存在与待插入结点的关键字相同的结点，且新结点的关键字小于根结点的关键字，则新结点将成为

   

A.  左子树的叶子结点               
B.  左子树的分支结点
   

C.
右子树的叶子结点               

D.
右子树的分支结点

      满分：5  分
13.   
若要在O(1)的时间复杂度上实现两个循环链表头尾相接，则应对两个循环链表各设置一个指针，分别指向

     

A. 各自的头结点
   

B.  各自的尾结点
     

C. 各自的第一个元素结点
     

D. 一个表的头结点，另一个表的尾结点
      满分：5  分
14.   
引入二叉线索树的目的是

  

A. 加快查找结点的前驱或后继的速度   
  

B.
为了能在二叉树中方便的进行插入与删除

   

C.
为了能方便的找到双亲      



D.        
   使二叉树的遍历结果唯一

      满分：5  分
15.   
已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>},G的拓扑序列是



A. V1,V3,V4,V6,V2,V5,V7                  
B. V1,V3,V2,V6,V4,V5,V7


C.
V1,V3,V4,V5,V2,V6,V7                  

D.
V1,V2,V5,V3,V4,V6,V7

      满分：5  分
16.   
若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是

A.
2，4，3，1，5，6                  

B.
3，2，4，1，6，5

C.
4，3，2，1，5，6               

D.
2，3，5，1，6，4

      满分：5  分
17.   
如果将矩阵An×n的每一列看成一个子表，整个矩阵看成是一个广义表L，即L=((a11,a21,…,an1),

( a12,a22,…,an2),…，（a1n,a2n,…,ann）),并且可以通过求表头head和求表尾tail的运算求

取矩阵中的每一个元素，则求得a21的运算是

   

A.  head (tail (head (L)))         
B.  head (head(head(L)))
   

C.
tail (head (tail (L)))         

D.
head (head (tail (L)))

      满分：5  分
18.   
若数组s[0..n-1]为两个栈s1和s2的共用存储空间，且仅当s[0..n-1]全满时，各栈才不能进行进栈操作， 则为这两个栈分配空间的最佳方案是：s1和s2的栈顶指针的初值分别为

   

A. 1和n+1                    
B.  1和n/2
   

C.
－1和n                    

D.  －1和n+1
      满分：5  分
19.   
在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用

     

A.  数据元素的相邻地址表示     
B.  数据元素在表中的序号表示
   

C.
指向后继元素的指针表示   

D.
数据元素的值表示

      满分：5  分
20.   
某二叉树的先序序列和后序序列正好相反，则该二叉树的特点一定是

  

A.  空或只有一个结点               
B. 高度等于其结点数


C.
任一结点无左孩子                 

D.
任一结点无右孩子

      满分：5  分