东大15春学期《数据结构Ⅱ》在线作业1-3答案

李老师

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


一、单选题（共 20 道试题，共 100 分。）V 1.   
在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next=

  head,则

   

A.   p指向头结点               
B.   p指向尾结点
     

C.   p的直接后继是头结点      
D.  P的直接后继是尾结点
      满分：5  分
2.   
对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为



A. O(n)  O(n)                 
B.  O(n)  O(1)      
C.
O(1)  O(n)                    

D.
O(1) O(1)

      满分：5  分
3.   
链栈与顺序栈相比，比较明显的优点是

A.
插入操作更加方便              

B.
删除操作更加方便

C.
不会出现下溢的情况         

D.
不会出现上溢的情况

      满分：5  分
4.   
文件中，主关键字能唯一标识

   

A. 一个记录         
B.  一组记录
   

C.  一个类型                     
D.
一个文件

      满分：5  分
5.   
数据元素及其关系在计算机存储器内的表示，称为数据的

   

A. 逻辑结构               
B. 存储结构
   

C.
线性结构                  

D.
非线性结构

      满分：5  分
6.   
一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是

  

A.  不确定                     
B. 0
C. 1
D. 2
      满分：5  分
7.   
下述哪一条是顺序存储结构的优点

A.
存储密度大                  

B.
插入运算方便  

C.
删除运算方便               

D.
可方便地用于各种逻辑结构的存储表示

      满分：5  分
8.  
  

连通网的最小生成树是其所有生成树中

   

A.   顶点集最小的生成树              
B.   边集最小的生成树
   

C.
顶点权值之和最小的生成树        

D.   边的权值之和最小的生成树
      满分：5  分
9.   
在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为

A.
  O(n)                              

B.
  O(n+e)      

C.
O(n2)                          

D.
O(n3)

      满分：5  分
10.   
下列排序算法中，时间复杂度不受数据初始状态影响，恒为0(nlog2n)的是

A.
堆排序                        

B.
冒泡排序   

C.
直接选择排序                 

D.
快速排序

      满分：5  分
11.   
在关键字序列(12，23，34，45，56，67，78，89，91)中二分查找关键字为45、89和12的结点时，所需进行的比较次数分别为

   

A.  4，4，3                        
B.  4，3，3
   

C.
3，4，4                       

D.  ．3，3，4
      满分：5  分
12.   
带行表的三元组表是稀疏矩阵的一种

   

A.   顺序存储结构                  
B. 链式存储结构
   

C.
索引存储结构                  

D.
散列存储结构

      满分：5  分
13.   
已知一组关键字为{25,48,36,72,79,82,23,40,16,35}，其中每相邻两个为有序子序列。对这些子序列进行一趟两两归并的结果是

A.
.{25,36,48,72,23,40,79,82,16,35}

B.
.{25,36,48,72,16,23,40,79,82,35}

C.
.{25,36,48,72,16,23,35,40,79,82}

D.
.{16,23,25,35,36,40,48,72,79,82}

      满分：5  分
14.   
对于哈希函数H(key)=key%13,被称为同义词的关键字是

   

A.   35和41                       
B.   23和39
   

C.  15和44                     
D.   25和51
      满分：5  分
15.   
已知含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  分
16.   
在平衡二叉树中插入一个结点后引起了不平衡，设最低(最接近于叶子)的不平衡点是A，并已知A的左、右孩子的平衡因子分别为-1和0，则应进行的平衡旋转是

      

A.  LL型                       
B. LR型      
      

C.
RL型                        

D.  RR型
      满分：5  分
17.   
对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用遍历方式是

     

A.  先序                             
B.  中序      
      

C.  后序                             
D.  从根开始的层次遍历
      满分：5  分
18.   
如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是

      

A.  栈                                
B.  队列
      

C.
树                                 

D.
图

      满分：5  分
19.   
栈是一种操作受限的线性结构，其操作的主要特征是

A.
先进先出                    

B.
后进先出

C.
进优于出               

D.
出优于进

      满分：5  分
20.   
在按层次遍历二叉树的算法中，需要借助的辅助数据结构是

   

A.  队列                       
B.  栈
   

C.  线性表                     
D.  
   有序表

      满分：5  分