北语20春《数据结构》作业1[答案]答案
20春《数据结构》作业1
试卷总分:100 得分:100
一、单选题 (共 20 道试题,共 100 分)
1.用不带头结点的单链表存储队列，其头指针指向队头结点，尾指针指向队尾结点，则在进行出队操作时___。
A.队头、队尾指针都要修改
B.队头、队尾指针都可能要修改
C.仅修改队尾指针
D.仅修改队头指针
2.{图}
A.D
B.C
C.B
D.A
3.有一个长度为12的有序表R[0..11],按二分查找法对该表进行查找,在表内各元素等概率情况下查找成功所需的平均比较次数为____。
A.43/12
B.39/12
C.37/12
D.35/12
4.设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有___个空指针域。
A.4m
B.2m-1
C.2m+1
D.2m
5.若有18个元素的有序表存放在一堆数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A[3]的比较序列的下标依次为___。
A.9,5,3
B.9,5,2,3
C.9,4,2,3
D.1,2,3
6.
A.D
B.C
C.B
D.A
7.在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是___。
A.O（nlog2n）
B.O（n2）
C.O（n）
D.O（1）
8.算法指的是___。
A.计算机程序
B.解决问题的计算方法
C.解决问题的有限运算序列
D.排序算法
9.任何一棵二叉树的叶子结点在前序、中序和后序遍历序列中的相对次序___。
A.发生改变
B.以上都不对
C.不能确定
D.不发生改变
10.
A.D
B.C
C.B
D.A
11.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为___。
A.O（n）O（n）
B.O（n）O（1）
C.O（1）O（n）
D.O（1）O（1）
12.组成数据的基本单位是___。
A.数据项
B.数据类型
C.数据变量
D.数据元素
13.设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数为___。
A.5
B.4
C.3
D.1
14.对线性表进行折半查找时，要求线性表必须___。
A.以顺序方式存储，且结点按关键字有序排序
B.以顺序方式存储
C.以链式方式存储，且结点按关键字有序排序
D.以链式方式存储
15.{图}
A.非顺序文件
B.索引顺序文件
C.索引非顺序文件
D.哈希文件
16.采用邻接表存储的图的深度优先遍历算法类似于二叉树的___。
A.按层遍历
B.后序遍历
C.先序遍历
D.中序遍历
17.串是一种特殊的线性表，其特殊性体现在___。
A.数据元素是一个字符
B.数据元素可以是多个字符
C.可以顺序存储
D.可以链式存储
18.由权值分别为11,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为___。
A.71
B.53
C.48
D.24
19.设二维数组A[6][10]，每个数组元素占用4个存储单元，若按行优先顺序存放数组元素，a[0][0]的存储地址为860，则a[3][5]的存储地址是___。
A.860
B.1200
C.1140
D.1000
20.有一个有序表{1，4，6，10，18，35，42，53，67，71，78，84，92，99}，当用二分查找法查找键值为84的结点时，经____次比较后查找成功。
A.4
B.3
C.2
D.12
北语20春《数据结构》作业1[答案]历年真题如下：
