20年秋西交《数据结构》在线作业[答案]满分答案
西交《数据结构》在线作业
试卷总分: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
正确答案:----
