12秋北京邮电大学《数据结构》在线作业一

北邮《数据结构》在线作业一
试卷总分：100
单选题
一、单选题（共 20 道试题，共 100 分。）
V
1. 具有64个结点的完全二叉树的深度为
A. 8
B. 7
C. 6
D. 5
满分：5 分
2. 串是一种特殊的线性表，其特殊性表现在
A. 可以顺序存储
B. 数据元素是一个字符
C. 可以链接存储
D. 数据元素可以是多个字符
满分：5 分
3. 非空的循环单链表head的尾结点（由P所指向）满足
A. P→next==NULL
B. P==NULL
C. P→next==head
D. P==head
满分：5 分
4.
A. O(i*j*k)；
B. O(n*m*k)；
C. O(n*j*k)；
D. O(n*m*w)。
此题选: D 满分：5 分
5. 如果T2是由有序树T转换来的二叉树，则T中结点的后序排列是T2结点的
A. 先序排列；
B. 中序排列；
C. 后序排列；
D. 层序排列。
满分：5 分
6. 对长度为3的顺序表进行查找，若查找第一个元素的概率为1/2，查找第二个元素的概率为1/3，查找第三个元素的概率为1/6，则查找任一个元素的平均查找长度为
A. 5/3
B. 2
C. 7/3
D. 4/3
满分：5 分
7. 深度为5的二叉树至多有（ ）个结点。
A. 16
B. 32
C. 31
D. 10
满分：5 分
8. 有500个元素，用折半查找法进行查找时，最大比较次数为
A. 7
B. 6
C. 8
D. 9
此题选: D 满分：5 分
9. 一个长度为15的有序表，按二分查找法对该表进行查找，在表内每个元素等概率情况下查找成功所需的平均比较次数为
A. 53/15
B. 59/15
C. 57/15
D. 64/15
满分：5 分
10. 常对数组进行的两种基本操作是
A. 建立与删除；
B. 索引和修改；
C. 查找和修改；
D. 查找和索引。
满分：5 分
11. 若一棵二叉树有2003个结点，且无度为1的结点，则叶结点的个数为
A. 1001
B. 1002
C. 1003
D. 1004
满分：5 分
12. 设n为哈夫曼树的叶子结点数目，则该哈夫曼树共有（ ）个结点。
A. n+1
B. 2n-1
C. 2n
D. 2n+1
满分：5 分
13. 基本线性表的顺序存储中，数据元素的逻辑位置与物理位置的关系是
A. 不一致的
B. 一致的
C. 大致相同
D. 个别情形相同
满分：5 分
14. 利用3，6，8，12，5，7这六个值作为叶子结点的权，生成一棵哈夫曼树，该树的深度为
A. 3
B. 4
C. 5
D. 6
满分：5 分
15. 一个顺序队列的第1个元素的存储地址是100，第4个元素的存储地址是112，每个元素的长度是4，则第6个元素的地址是
A. 110
B. 120
C. 124
D. 130
满分：5 分
16. 深度为5的二叉树其结点数最多为
A. 16；
B. 30
C. 31
D. 32
满分：5 分
17. 二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法
A. 正确；
B. 错误。
满分：5 分
18. 具有10个叶结点的二叉树中有（ ）度为2的结点。
A. 8
B. 9
C. 10
D. 11
满分：5 分
19. 若二叉树采用二叉链表的存储结构，要交换其所有分支结点左右子树的位置，利用（ ）遍历方法最合适。
A. 前序
B. 中序
C. 后序
D. 按层次
满分：5 分
20. 在一个长度为n的线性表中，删除值为x的元素时需要比较元素和移动元素的总次数为
A. （n+1）/2；
B. n/2；
C. n；
D. n+1。
满分：5 分