西交《数据结构》在线作业
试卷总分:100 得分:100
一、单选题 (共 30 道试题,共 60 分)
1.若有18个元素的有序表存放在一维数组A[19]中,第一个元素放A[1]中,现进行二分查找,则查找A[3]的比较序列的下标依次为()
A.1,2,3
B.9,5,2,3
C.9,5,3
D.9,4,2,3
2.利用直接插入排序法的思想建立一个有序线性表的时间复杂度为()。
A.O(n)
B.O(nlog2n)
C.O(n)
D.O(1og2n)
3.若一棵二叉树有10个度为2的结点,则该二叉树的叶子结点的个数为( )。
A.9
B.11
C.12
D.不能确定
4.已知二维数组A[4,6]采用行优先存储结构,每个元素占用3 个存储单元,并且A[1,1]的存储地址为1200,元素A[[2,4]的存储地址是( )。
A.1221
B.1227
C.1239
D.1257
5.设顺序线性表中有n个数据元素,则删除表中第i个元素需要移动()个元素。
A.n-i
B.n+l-i
C.n-1-i
D.i
6.设某棵三叉树中有40个结点,则该三叉树的最小高度为()。
A.3
B.4
C.5
D.6
7.对5个不同的数据元素进行直接插入排序,最多需要进行()次比较。
A.8
B.10
C.15
D.25
8.{图}
A.A
B.B
C.C
D.D
9.下列说法中,正确的是( )。
A.度为2的树是二叉树
B.度为2的有序树是二叉树
C.子树有严格的左、右之分的树是二叉树
D.子树有严格的左、右之分,且度不超过2的树是二叉树
10.设一个顺序有序表A[1:14]中有14个元素,则采用二分法查找元素A[4]的过程中比较元素的顺序为()
A.A[1],A[2],A[3],A[4]
B.A[1],A[14],A[7],A[4]
C.A[7],A[3],A[5],A[4]
D.A[7],A[5],A[3],A[4]
11.设一条单链表的头指针变量为head且该链表没有头结点,则其判空条件是()。
A.head==0
B.head->next==0
C.head->next==head
D.head!=0
12.设某棵二叉树的中序遍历序列为ABCD,前序遍历序列为CABD,则后序遍历该二叉树得到序列为()
A.BADC
B.BCDA
C.CDAB
D.CBDA
13.程序段s=i=0;do{i=i+1;s=s+i;}while(i<=n);的时间复杂度为()。
A.O(n)
B.O(nlog2n)
C.O(n)
D.O(n/2)
14.设某无向图中有n个顶点e条边,则该无向图中所有顶点的入度之和为()。
A.n
B.e
C.2n
D.2e
15.设一组权值集合W={2,3,4,5,6},则由该权值集合构造的哈夫曼树中带权路径长度之和为()
A.20
B.30
C.40
D.45
16.用二分(对半)查找表的元素的速度比用顺序法( )
A.必然快
B.必然慢
C.相等
D.不能确定
17.如下陈述中正确的是()
A.串是一种特殊的线性表
B.串的长度必须大于零
C.串中元素只能是字母
D.空串就是空白串
18.栈的插入和删除操作在()进行。
A.栈顶
B.栈底
C.任意位置
D.指定位置
19.如果要求频繁的对线性表进行插入和删除操作,则线性表应该采用( )存储结构。
A.散列
B.顺序
C.链式
D.任意
20.用链表表示线性表的优点是()
A.便于随机存取
B.花费的存储空间比顺序表少
C.便于插入与删除
D.数据元素的物理顺序与逻辑顺序相同
21.设完全无向图中有n个顶点,则该完全无向图中有()条边。
A.n(n-1)/2
B.n(n-1)
C.n(n+1)/2
D.(n-1)/2
22.设某链表中最常用的操作是在链表的尾部插入或删除元素,则选用下列()存储方式最节省运算时间。
A.单向链表
B.单向循环链表
C.双向链表
D.双向循环链表
23.判断一个图中是否存在回路可以利用( )方法。
A.求最小生成树
B.求最短路径
C.拓扑排序
D.图的遍历
24.{图}
A.A
B.B
C.C
D.D
25.栈和队列的共同特点是()。
A.只允许在端点处插入和删除元素
B.都是先进后出
C.都是先进先出
D.没有共同点
26.设有一组初始记录关键字序列为(34,76,45,18,26,54,92),则由这组记录关键字生成的二叉排序树的深度为()。
A.4
B.5
C.6
D.7
27.设有一个二维数组A[m][n],假设A[0][0]存放位置在644(10),A[2][2]存放位置在676(10),每个元素占一个空间,问A[3][3](10)存放在什么位置()?脚注(10)表示用10进制表示。
A.688
B.678
C.692
D.696
28.对一棵二叉排序树进行( )遍历,可以得到该二叉树的多有结点按值从小到大排列的序列。
A.前序
B.中序
C.后序
D.按层次
29.设哈夫曼树中的叶子结点总数为m,若用二叉链表作为存储结构,则该哈夫曼树中总共有()个空指针域。
A.2m-1
B.2m
C.2m+1
D.4m
30.程序段如下:s=i=0; do {i=i+1; s=s+i;} while(i<=n);其时间复杂度为( )。
A.O(n)
B.O(nlog2n)
C.O(n2)
D.O(n3/2)
二、判断题 (共 20 道试题,共 40 分)
31.有向图的邻接表和逆邻接表中表结点的个数不一定相等。
32.哈夫曼树中没有度数为2的结点。
33.设一棵树T可以转化成二叉树BT,则二叉树BT中一定没有右子树。
34.稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。
35.中序遍历二叉排序树可以得到一个有序的序列。
36.分块查找的平均查找长度不仅与索引表的长度有关,而且与块的长度有关。
37.{图}
38.二维数组是数组元素为一维数组的线性表,因此它是线性结构。
39.先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。
40.{图}
41.子串“ABC”在主串“AABCABCD”中的位置为3。
42.在拓扑排序序列中,任意两个相继结点Vi和Vj都存在从Vi到Vj的路径。( )
43.堆排序所需的时间与待排序的记录个数无关。( )
44.一棵m阶B树中每个结点最多有m个关键码,最少有2个关键码。
45.在链队列上做出队操作时,会改变front指针的值。( )
46.具有n个结点的完全二叉树的高度为┖log2n┘+1。
47.在拓扑排序序列中,任意两个相继结点Vi和Vj都存在从Vi到Vj的路径。
48.如果两个关键字的值不等但哈希函数值相等,则称这两个关键字为同义词。
49.对具有n个元素的序列来采用冒泡排序法进行排序,排序的趟数为n-1。( )
50.二维数组和多维数组均不是特殊的线性结构。
转载请注明:奥鹏作业之家 » 20年秋西交《数据结构》在线作业