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

李老师

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


一、单选题（共 20 道试题，共 100 分。）V 1.   
在一个带权连通图G中，权值最小的边一定包含在G的

     

A. 最小生成树中                  
B.  深度优先生成树中
   

C. 广度优先生成树中               
D. 深度优先生成森林中
      满分：5  分
2.   
高度为5的完全二叉树中含有的结点数至少为

      

A. 16
B. 17
C. 31
D. 32
      满分：5  分
3.   
已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于

   

A. 1.0
B. 2.9
C. 3.4
D. 5.5
      满分：5  分
4.   
对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为



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

D.   O(1) O(1)
      满分：5  分
5.   
某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E 则该二叉树对应的森林包括的树的棵树是

   

A. 1
B. 2
C. 3
D. 概念上是错误的
      满分：5  分
6.   
除第一层外，满二叉树中每一层结点个数是上一层结点个数的

      

A. 1/2倍                     
B.      1倍
      

C. 2倍                           
D.  3倍
      满分：5  分
7.   
二维数组A的每个元素是由6个字符组成的串，其行下标i=0，l，…，8，列下标为j=1，2．…．10。设每个字符占一个字节,若按行先存储，元素A[8，5]的起始地址与A按列存储时起始地址相同的元素是

     

A. A[8，5]                     
B. A[3，10]   
C.
A[5，8]                     

D.  A[0，9]
      满分：5  分
8.   
设数组A[m]为循环队列Q的存储空间，front为队头指针，rear为队尾指针，则判定Q为空队列的条件是

   

A.  (rear-front)%m= =1               
B.   front= =rear
     

C. (rear-front)%m= =m-1               
D. front= =(rear+1)%m
      满分：5  分
9.   
按排序过程中依据的原则分类，快速排序属于

A.
插入类的排序方法            

B.      选择类的排序方法
C.
交换类的排序方法               

D.  . 归并类的排序方法
      满分：5  分
10.   
设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1  则T中的叶子数为



A. 5
B. 6
C. 7
D. 8
      满分：5  分
11.   
对关键字序列(56，23，78，92，88，67，19，34)进行增量为3的一趟希尔排序的结果为

A.
(19，23，56，34，78，67，88，92)        

B.  (23，56，78，66，88，92，19，34)
C.
(19，23，34，56，67，78，88，92)        

D.   (19，23，67，56，34，78，92，88)
      满分：5  分
12.   
下列排序算法中，时间复杂度不受数据初始状态影响，恒为0(nlog2n)的是

A.
堆排序                        

B.   冒泡排序   
C.
直接选择排序                  

D.   快速排序
      满分：5  分
13.   
深度为h的满m叉树的第k层的结点(1=<k=<h)数有



A.   mk-1                                
B.  mk-1         
  

C.  mh-1                                 
D. mh-1
      满分：5  分
14.   
在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是

A.
G中有弧<Vi，Vj>  

B. G中有一条从Vi到Vj的路径                                             


C. G中没有弧<Vi,Vj>                    
D.  G中有一条从Vj到Vi的路径   
      满分：5  分
15.   
若要在单链表中的结点p之后插入一个结点s，则应执行的语句是

     

A.  s->next=p->next; p->next=s;      
B.   p->next=s; s->next=p->next;
     

C.  p->next=s->next; s->next=p;        
D. s->next=p; p->next=s->next;
      满分：5  分
16.   
树有先根遍历和后根遍历，树可以转化为对应的二叉树。下面的说法正确的是

     

A.  树的后根遍历与其对应的二叉树的后根遍历相同     
B.
树的后根遍历与其对应的二叉树的中根遍历相同

C.
树的先根遍历与其对应的二叉树的中根遍历相同      

D.
以上都不对

      满分：5  分
17.   
带行表的三元组表是稀疏矩阵的一种

     

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

C.  索引存储结构                     
D.  散列存储结构
      满分：5  分
18.   
当采用分快查找时，数据的组织方式为



A. 数据分成若干块，每块内数据有序


B. 数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块
C.
  数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块

D.
  数据分成若干块，每块（除最后一块外）中数据个数需相同

      满分：5  分
19.   
在平衡二叉树中插入一个结点后引起了不平衡，设最低(最接近于叶子)的不平衡点是A，并已知A的左、右孩子的平衡因子分别为-1和0，则应进行的平衡旋转是

      

A.  LL型                          
B. LR型      
     

C.   RL型                        
D.  RR型
      满分：5  分
20.   
适宜进行批量处理的文件类型是

   

A.   顺序文件                       
B.   索引顺序文件
   

C.    散列文件                       
D.   多关键字文件
      满分：5  分