北京言语大学20春《数据结构》作业1-复习资料答案

1、科目名称：20春数据结构作业1 一、单选题 (共 20 道试题,共 100 分) 1.用不带头结点的单链表存储队列，其头指针指向队头结点，尾指针指向队尾结 点，则在进行出队操作时_。 A.队头、队尾指针都要修改 B.队头、队尾指针都可能要修改 C.仅修改队尾指针 D.仅修改队头指针 -本题参考答案：B 2.图 A.D B.C C.B D.A -本题参考答案：C 3.有一个长度为 12 的有序表 R0.11,按二分查找法对该表进行查找,在表内各 元素等概率情况下查找成功所需的平均比较次数为_。 A.43/12 B.39/12 C.37/12 D.35/12 -本题参考答案：C 4.设哈夫曼树中的

2、叶子结点总数为 m，若用二叉链表作为存储结构，则该哈夫曼 树中总共有_个空指针域。 A.4m B.2m-1 C.2m+1 D.2m -本题参考答案：D 5.若有 18 个元素的有序表存放在一堆数组 A19中，第一个元素放 A1中，现进 行二分查找，则查找 A3的比较序列的下标依次为_。 A.9,5,3 B.9,5,2,3 C.9,4,2,3 D.1,2,3 -本题参考答案：C 6. A.D B.C C.B D.A -本题参考答案：C 7.在一个具有 n 个结点的有序单链表中插入一个新结点并仍然保持有序的时间复 杂度是_。 A.O（nlog2n） B.O（n2） C.O（n） D.O（1） 提示

3、：本题为必答题，请认真阅读题目后再作答-本题参考答案：C 8.算法指的是_。 A.计算机程序 B.解决问题的计算方法 C.解决问题的有限运算序列 D.排序算法 -本题参考答案：C 9.任何一棵二叉树的叶子结点在前序、中序和后序遍历序列中的相对次序_。 A.发生改变 B.以上都不对 C.不能确定 D.不发生改变 -本题参考答案：D 10. A.D B.C C.B D.A -本题参考答案：B 11.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为_。 A.O（n）O（n） B.O（n）O（1） C.O（1）O（n） D.O（1）O（1） -本题参考答案：D 12.组成数据的基本单位是_

4、。 A.数据项 B.数据类型 C.数据变量 D.数据元素 -本题参考答案：D 13.设结点 A 有 3 个兄弟结点且结点 B 为结点 A 的双亲结点，则结点 B 的度数为_。 A.5 B.4 C.3 D.1 -本题参考答案：B 14.对线性表进行折半查找时，要求线性表必须_。 A.以顺序方式存储，且结点按关键字有序排序 B.以顺序方式存储 C.以链式方式存储，且结点按关键字有序排序 D.以链式方式存储 -本题参考答案：A 15.图 A.非顺序文件 B.索引顺序文件 C.索引非顺序文件 D.哈希文件 -本题参考答案：B 16.采用邻接表存储的图的深度优先遍历算法类似于二叉树的_。 A.按层遍历

5、B.后序遍历 C.先序遍历 D.中序遍历 -本题参考答案：C 17.串是一种特殊的线性表，其特殊性体现在_。 A.数据元素是一个字符 B.数据元素可以是多个字符 C.可以顺序存储 D.可以链式存储 -本题参考答案：A 18.由权值分别为 11,8,6,2,5 的叶子结点生成一棵哈夫曼树，它的带权路径长度 为_。 A.71 B.53 C.48 D.24 -本题参考答案：A 19.设二维数组 A610，每个数组元素占用 4 个存储单元，若按行优先顺序存 放数组元素，a00的存储地址为 860，则 a35的存储地址是_。 A.860 B.1200 C.1140 D.1000 -本题参考答案：D 20.有一个有序表1，4，6，10，18，35，42，5