14秋北航《算法与数据结构》在线作业123

北航《算法与数据结构》在线作业一

一,单选题

1. 若给定的关键字集合为{20，15，14，18，21，36，40，10}，一趟快速排序结束时，键值的排列为( )。
A. 10，15，14，18，20，36，40，21
B. 10，15，14，18，20，40，36，21
C. 10，15，14，20，18，40，36，21
D. 15，10，14，18，20，36，40，21
      ?
正确答案：A

2. 以下不稳定的排序方法是
A. 直接插入排序
B. 冒泡排序
C. 直接选择排序
D. 二路归并排序
      ?
正确答案：C

3. 向堆中插入一个元素的时间复杂度为（ ）。
A. O(log2n)
B. O(n)
C. O(1)
D. O(nlog2n)
      ?
正确答案：A

4. 下列数据组织形式中，（ ）的各个结点可以任意邻接。
A. 集合
B. 树形结构
C. 线性结构
D. 图状结构
      ?
正确答案：D

5. 一组记录的排序码为(46,79,56,38,40,84),则利用堆排序的方法建立的初始堆为（ ）。
A. 79,46,56,38,40,80
B. 84,79,46,38,40,56
C. 84,79,56,46,40,38
D. 84,56,79,40,46,38
      ?
正确答案：B

6. 在一个顺序队列中，队首指针指向队首元素的（　　）位置。
A. 后一个
B. 前一个
C. 当前
D. 不确定
      ?
正确答案：B

7. 计算机的算法必须具备输入，输出和（ ）五个特性。
A. 可行性，可移植性和可扩充性
B. 可行性，确定性和有穷性
C. 确定性，有穷性和稳定性
D. 易读性，稳定性和安全性
      ?
正确答案：B

8. 下列关于栈的叙述正确的是（ ）。
A. 栈是非线性结构
B. 栈是一种树状结构
C. 栈具有先进先出的特征
D. 栈具有后进先出的特征
      ?
正确答案：D

9. 在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为()。
A. e
B. 2e
C. n的平方－e
D. n的平方－2e
      ?
正确答案：D

10. 以下二叉树说法错误的是
A. 完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达
B. 在三叉链表上，二叉树的求双亲运算很容易实现
C. 在二叉链表上，求根，求左、右孩子等很容易实现
D. 在二叉链表上，求双亲运算的时间性能很好
      ?
正确答案：D

11. 在一棵二叉树中，第4层上的结点数最多为（ ）。
A. 8
B. 15
C. 16
D. 31
      ?
正确答案：A

12. 非空的循环单链表head的尾节点（由p所指向）满足（ ）。
A. p->next=NULL
B. p=NULL
C. p->next=head
D. p=head
      ?
正确答案：C

13. 强连通分量是（ ）极大连通子图。
A. 有向图
B. 无向图
C. 树
D. 图
      ?
正确答案：B

14. 串是任意有限个（ ）
A. 符号构成的序列
B. 符号构成的集合
C. 字符构成的序列
D. 字符构成的集合
      ?
正确答案：C

15. 设深度为k的二叉树上只有度为0和度为2的节点，则这类二叉树上所含结点总数最少（ ）个
A. k+1
B. 2k
C. 2k-1
D. 2k+1
      ?
正确答案：C