15秋学期奥鹏东大(本部)《数据结构Ⅰ》在线作业3

奥鹏网院作业

15秋学期《数据结构Ⅰ》在线作业3
试卷总分：100   测试时间：--
一、单选题（共20道试题，共100分。）
1.  
采用ISAM或VSAM组织的文件是

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

C.  索引顺序文件                    
D.  散列文件
满分：5分
2.  
. 对长度为15的有序顺序表进行二分查找，在各记录的查找概率均相等的情况下，查找成功时所需进行的关键字比较次数的平均值为

A.  39/15                              
B.   49/15.

C. 51/15                              
D.  55/15
满分：5分
3.  
假设一棵完全二叉树按层次遍历的顺序依次存放在数组BT[m]中，其中根结点存放在BT[0]，若BT[i]中的结点有左孩子，则左孩子存放在

A.  BT[i/2]                     
B.    BT[2*i-1]

C.   BT[2*i]                       
D.   BT[2*i+1]
满分：5分
4.  
for（i=0；i<m；i++）
        for（j=0；j<t；j++）
c［i］［j］=0；
for（i=0；i<m；i++）
for（j=0；j<t；j++）
for（k=0；k<n；k++）
c［i］［j］=c［i］［j］+a［i］［k］*b［k］［j］；
    上列程序的时间复杂度为

A.    O（m+n×t）                    
B.   O（m+n+t）

C.   O（m×n×t）                  
D.   O（m×t+n）
满分：5分
5.  
BFS算法可用来解决单源最短路径问题的条件是当各边上的权值
A.
均相等                             
B.  均互不相等     
C.
不一定相等                          
D. 任意值
满分：5分
6.  
高度为5的完全二叉树中含有的结点数至少为

A. 16
B. 17
C. 31
D. 32
满分：5分
7.  
下列序列中，不构成堆的是
A.
（1，2，5，3，4，6，7，8，9，10）
B.
（10，5，8，4，2，6，7，1，3）
C.
（10，9，8，7，3，5，4，6，2）
D.
（1，2，3，4，10，9，8，7，6，5）
满分：5分
8.  
多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为
A.
数组的元素处在行和列两个关系中   
B. 数组的元素必须从左到右顺序排列
C.
数组的元素之间存在次序关系      
D.  数组是多维结构，内存是一维结构
满分：5分
9.  
用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为

A. n-1
B. n
C. n+1
D. 2n
满分：5分
10.  
在线性表的下列运算中，不改变数据元素之间结构关系的运算是

A.   插入                        
B. 删除

C. 排序                        
D.  查找
满分：5分
11.  
导致栈上溢的操作是
A.
栈满时执行的出栈                  
B.   栈满时执行的入栈
C.
栈空时执行的出栈                  
D.   栈空时执行的入栈
满分：5分
12.  
判断两个串大小的基本准则是
A.
两个串长度的大小              
B.   两个串中首字符的大小
C.
两个串中大写字母的多少        
D.   对应的第一个不等字符的大小
满分：5分
13.  
可有效提高次关键字查找效率的文件是

A.  顺序文件                        
B.   倒排文件

C.  散列文件                        
D.  VSAM文件
满分：5分
14.  
若<vi, vj>是有向图的一条边，则称

A.  vi邻接于vj                  
B.  vj邻接于vi

C.  vi和vj相互邻接               
D. vi与vj-不相邻接
满分：5分
15.  
某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E 则该二叉树对应的森林包括的树的棵树是

A. 1
B. 2
C. 3
D. 概念上是错误的
满分：5分
16.  
在一个单链表中，已知q结点是p结点的前驱结点，若在q 和p之间插入结点s，则执行操作

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

C.   q->next=s;s->next=p;          D. p->next=s;s->next=q;
D.   q->next=s;s->next=p;          D. p->next=s;s->next=q;
满分：5分
17.  
下面说法错误的是
    (1）算法原地工作的含义是指不需要任何额外的辅助空间
   （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法
   （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界
   （4）同一个算法，实现语言的级别越高，执行效率就越低
A.
(1)                 
B.   (1),(2)   
C.
(1),(4)                 
D.  (3)
满分：5分
18.  
n个顶点的有向完全图中含有向边的数目最多为
A.
n-1                                
B.     n           
C.
n(n-1)/2                              
D.  n(n-1)
满分：5分
19.  
对有18个元素的有序表作二分查找，则查找A[3]的比较序列的下标为

A.  1，2，3                        
B.   9，5，2，3   

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

A.  1和 5                              
B.  2和4         
C.
  4和2                              
D.   5和1  
满分：5分