[北京语言大学]20春《数据结构》作业1(参考答案)

skystar

试卷名称:20春《数据结构》作业1
1.用不带头结点的单链表存储队列，其头指针指向队头结点，尾指针指向队尾结点，则在进行出队操作时___。
A.仅修改队头指针
B.仅修改队尾指针
C.队头、队尾指针都可能要修改
D.队头、队尾指针都要修改
答案:-

2.
A.A
B.B
C.C
D.D
答案:-

3.有一个长度为12的有序表R[0..11],按二分查找法对该表进行查找,在表内各元素等概率情况下查找成功所需的平均比较次数为____。
A.35/12
B.37/12
C.39/12
D.43/12
答案:-

4.设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有___个空指针域。
A.2m-1
B.2m
C.2m+1
D.4m
答案:-

5.若有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
答案:-

6.
A.A
B.B
C.C
D.D
答案:-

7.在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是___。
A.O（1）
B.O（n）
C.O（n2）
D.O（nlog2n）
答案:-

8.算法指的是___。
A.计算机程序
B.解决问题的计算方法
C.排序算法
D.解决问题的有限运算序列
答案:-

9.任何一棵二叉树的叶子结点在前序、中序和后序遍历序列中的相对次序___。
A.不发生改变
B.发生改变
C.不能确定
D.以上都不对
答案:-

10.
A.A
B.B
C.C
D.D
答案:-

11.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为___。
A.O（n）O（n）
B.O（n）O（1）
C.O（1）O（1）
D.O（1）O（n）
答案:-

12.组成数据的基本单位是___。
A.数据项
B.数据类型
C.数据元素
D.数据变量
答案:-

13.设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数为___。
A.3
B.4
C.5
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.24
B.71
C.48
D.53
答案:-

19.设二维数组A[6][10]，每个数组元素占用4个存储单元，若按行优先顺序存放数组元素，a[0][0]的存储地址为860，则a[3][5]的存储地址是___。
A.1000
B.860
C.1140
D.1200
答案:-

20.有一个有序表{1，4，6，10，18，35，42，53，67，71，78，84，92，99}，当用二分查找法查找键值为84的结点时，经____次比较后查找成功。
A.2
B.3
C.4
D.12
答案:-