15秋学期奥鹏东大（本部）《数据结构Ⅰ》在线作业2

奥鹏网院作业

15秋学期《数据结构Ⅰ》在线作业2
试卷总分：100   测试时间：--
一、单选题（共20道试题，共100分。）
1.  
将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是
A. n
B. 2n-1
C. 2n
D. n-1
满分：5分
2.  
以下属于逻辑结构的是
A.
顺序表      
B.  哈希表      
C.  有序表         
D.   单链表
满分：5分
3.  
通常将链串的结点大小设置为大于1是为了
A.
提高串匹配效率                    
B. 提高存储密度
C.
便于插入操作                     
D. 便于删除操作
满分：5分
4.  
带行表的三元组表是稀疏矩阵的一种

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

C.  索引存储结构                     
D.  散列存储结构
满分：5分
5.  
如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是

A.   栈                                
B.  队列

C.    树                                 
D.  图
满分：5分
6.  
在关键字序列(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分
7.  
以下说法不正确的是

A.  无向图中的极大连通子图称为连通分量

B.  连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点

C.   图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点

D.   有向图的遍历不可采用广度优先搜索
满分：5分
8.  
有关二叉树下列说法正确的是

A.   二叉树的度为2                  
B. 一棵二叉树的度可以小于2                                                                                 

C.   二叉树中至少有一个结点的度为2   
D. 二叉树中任何一个结点的度都为2
满分：5分
9.  
能进行二分查找的线性表,必须以

A.  顺序方式存储,且元素按关键字有序

B. 链式方式存储,且元素按关键字有序

C.  顺序方式存储,且元素按关键字分块有序

D.  链式方式存储,且元素按关键字分块有序
满分：5分
10.  
下列数据结构中，属于非线性数据结构的是
A.
栈            
B.   队列      
C.     完全二叉树      
D.  堆
满分：5分
11.  
用有向无环图描述表达式(A+B)*((A+B)/A)，至少需要顶点的数目为
A. 5
B. 6
C. 8
D. 9
满分：5分
12.  
若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为

A. n-1                           
B.  n/m-1      
C.
  é(n-1)/(m-1)ù                  
D.   én/(m-1)ù-1   
满分：5分
13.  
下面哪一方法可以判断出一个有向图是否有回路
A.
深度优先遍历                    
B.   求关键路径   
C.
求最短路径                       
D.   A和C
满分：5分
14.  
执行下列程序段后，串X的值为
        S=〞abcdefgh〞;   T=〞xyzw〞;
        substr (X,S,2,strlen(T));
        substr (Y,S, stelen(T),2);
        strcat (X,Y);
A.
〞cdefgh〞               
B.  〞cdxyzw〞
C.
〞cdefxy〞               
D. 〞cdefef〞
满分：5分
15.  
对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为

A. O(n)  O(n)                  
B.    O(n)  O(1)      
C.
   O(1)  O(n)                  
D.   O(1) O(1)
满分：5分
16.  
栈是一种操作受限的线性结构，其操作的主要特征是
A.
先进先出                     
B.   后进先出
C.
进优于出                     
D.   出优于进
满分：5分
17.  
适宜进行批量处理的文件类型是

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

C.    散列文件                       
D.   多关键字文件
满分：5分
18.  
在一个带权连通图G中，权值最小的边一定包含在G的

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

C. 广度优先生成树中               
D. 深度优先生成森林中
满分：5分
19.  
在目标串T［0..n-1］=″xwxxyxy″中，对模式串P［0..m-1］=″xy″进行子串定位操作的结果是
A. 0
B. 2
C. 3
D. 5
满分：5分
20.  
二维数组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分