北航《算法与数据结构》在线作业三
试卷总分：100 测试时间：--
单选题

、单选题（共 25 道试题，共 100 分。）
1. 线性表的链接实现有利于（）运算。
A. 插入
B. 读表元
C. 查找
D. 定位
   满分：4 分
2. 用线性探测法查找闭散列表，可能要探测多个散列地址，这些位置上的键值（ ）
A. 一定都是同义词
B. 一定都不是同义词
C. 都相同
D. 不一定都是同义词
   满分：4 分
3. 若用冒泡排序法对序列（18，14，6，27，8，12，16，52，10，26，47，29，41，24）从小到大进行排序，共要进行（ ）次比较。
A. 33
B. 45
C. 70
D. 91
   满分：4 分
4. 设数组Data[0..m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为（ ）
A. front=front+1
B. front=(front+1)% m
C. rear=(rear+1)%m
D. front=(front+1)%(m+1)
   满分：4 分
5. 非空的循环单链表head的尾节点（由p所指向）满足（ ）。
A. p->next=NULL
B. p=NULL
C. p->next=head
D. p=head
   满分：4 分
6. 以下说法正确的是（ ）
A. 所谓数据的逻辑结构指的是数据元素之间的逻辑关系
B. 逻辑结构与数据元素本身的内容和形式无关
C. 顺序文件只适合于存放在磁带上，索引文件只能存放在磁盘上
D. 基于某种逻辑结构之上的运算，其实现是惟一的
   满分：4 分
7. 下述几种排序方法中,要求内存量最大的是（）。
A. 插入排序
B. 选择排序
C. 快速排序
D. 归并排序
   满分：4 分
8. 对线性表进行二分查找时,要求线性表必须（ ）。
A. 以顺序方式存储
B. 以链接方式存储
C. 以顺序方式存储,且结点按关键字有序排序
D. 以链接方式存储,且结点按关键字有序排序
   满分：4 分
9. 设深度为k的二叉树上只有度为0和度为2的节点，则这类二叉树上所含结点总数最少（ ）个
A. k+1
B. 2k
C. 2k-1
D. 2k+1
   满分：4 分
10. 两个串相等的充分必要条件是（ ）。
A. 两个串的长度相等
B. 两个串对应位置的字符相等
C. 两个串的长度相等且对应位置的字符相同
D. 以上条件都不正确
   满分：4 分
11. 快速排序的记录移动次数（　 ）比较次数，其总执行时间为O(nlog2n)。
A. 大于
B. 大于等于
C. 小于等于
D. 小于
   满分：4 分
12. 在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行（ ）。
A. HL=p;p->next=HL;
B. p->next=HL;HL=p;
C. p->next=HL;p=HL;
D. p->next=HL->next;HL->next=p;
   满分：4 分
13. 对于顺序表，以下说法错误的是（ ）
A. 顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址
B. 顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列
C. 顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻
D. 顺序表的特点是:逻辑上相邻的元素，存储在物理位置也相邻的单元中
   满分：4 分
14. 具有65个结点的完全二叉树的高度为（ ）。（根的层次号为0）
A. 8
B. 7
C. 6
D. 5
   满分：4 分
15. 如果结点A有3个兄弟，而且B为A的双亲，则B的度为（ ）。
A. 1
B. 3
C. 4
D. 5
   满分：4 分
16. 每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做（）排序.
A. 插入
B. 交换
C. 选择
D. 归并
   满分：4 分
17. 队列的插入操作是在（ ）进行。
A. 队首
B. 队尾
C. 队前
D. 队后
   满分：4 分
18. 堆是一个键值序列{k1,k2,…, kn},对i=1,2,…,|_n/2_|,满足( )
A. ki≤k2i≤k2i+1
B. ki C. ki≤k2i且ki≤k2i+1(2i+1≤n)
D. ki≤k2i 或ki≤k2i+1(2i+1≤n)
   满分：4 分
19. 队列操作的原则是（ ）。
A. 先进先出
B. 后进先出
C. 只能进行插入
D. 只能进行删除
   满分：4 分
20. 以下二叉树说法错误的是
A. 完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达
B. 在三叉链表上，二叉树的求双亲运算很容易实现
C. 在二叉链表上，求根，求左、右孩子等很容易实现
D. 在二叉链表上，求双亲运算的时间性能很好
   满分：4 分
21. 单链表的一个存储结点包含（ ）
A. 数据域或指针域
B. 指针域或链域
C. 指针域和链域
D. 数据域和链域
   满分：4 分
22. 下列关于树说法正确的是
A. 树的先根遍历序列与其对应的二叉树的先根遍历序列相同
B. 树的先根遍历序列与其对应的二叉树的后根遍历序列相同
C. 树的后根遍历序列与其对应的二叉树的先根遍历序列相同
D. 树的后根遍历序列与其对应的二叉树的后根遍历序列相同
   满分：4 分
23. 在一棵二叉树中，第4层上的结点数最多为（ ）。
A. 8
B. 15
C. 16
D. 31
   满分：4 分
24. 下列那种排序需要的附加存储开销最大（）。
A. 快速排序
B. 堆排序
C. 归并排序
D. 插入排序
   满分：4 分
25. 根据操作的效果，可将运算分成加工型运算、引用型运算两种基本类型。对于表格处理中的五种功能以下解释错误的是
A. 查找引用型运算，功能是找出满足某种条件的结点在s(线形结构)中的位置
B. 读取引用型运算 功能是读出s(线形结构)中某指定位置结点的内容
C. 插入引用型运算，功能是在s(线形结构)的某指定位置上增加一个新结点
D. 删除加工型运算，功能是撤消s(线形结构)某指定位置上的结点
   满分：4 分