东大14秋学期《数据结构Ⅱ》在线作业123

14秋学期《数据结构Ⅱ》在线作业1

一,单选题

1. 一棵具有 n个结点的完全二叉树的树高度（深度）是
   
A. ?logn?+1                        
B.  logn+1        
   
C.  ?logn?                          
D.  logn-1
      ?
正确答案：A

2. ALV树是一种平衡的二叉排序树，树中任一结点的
   
A.   左、右子树的高度均相同         
   
B.
左、右子树高度差的绝对值不超过1
   
C.   左子树的高度均大于右子树的高度  
   
D.  
   左子树的高度均小于右子树的高度
      ?
正确答案：B

3. 数据结构中所定义的数据元素，是用于表示数据的
   
A.  最小单位                 
B. 最大单位
   
C.
基本单位            
D.
不可分割的单位
      ?
正确答案：C

4. 在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是
A.
G中有弧<Vi，Vj>      
B.
G中有一条从Vi到Vj的路径                                            

C. G中没有弧<Vi,Vj>                    
D. G中有一条从Vj到Vi的路径
      ?
正确答案：D

5. 如果将矩阵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)))
正确答案：A

6. 在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为
   
A.  n-i+1        
B.  n-i
   
C.  i            
D.  i-1
      ?
正确答案：A

7. 下述哪一条是顺序存储结构的优点
A.
存储密度大                  
B.
插入运算方便  
C.
删除运算方便               
D.
可方便地用于各种逻辑结构的存储表示
      ?
正确答案：A

8. 若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为
     
A. 4
B. 5
C. 8
D. 9
      ?
正确答案：C

9. 若要在O(1)的时间复杂度上实现两个循环链表头尾相接，则应对两个循环链表各设置一个指针，分别指向
     
A. 各自的头结点
   
B.  各自的尾结点
     
C. 各自的第一个元素结点
     
D. 一个表的头结点，另一个表的尾结点
      ?
正确答案：B

10. 对有18个元素的有序表作二分查找，则查找A[3]的比较序列的下标为
   
A.   1，2，3                        
B.   9，5，2，3   
C.
9，5，3                        
D.   9，4，2，3
      ?
正确答案：D