Question

数据结构

1.一个算法的时间复杂度为（3n2+2nlog2n+4n-7）/(5n),其数量级表示为 _______ 。
2.A，B,C三个结点为线性链表的相邻结点，P指针指向A结点，写出将B，C结点交换位置的操作序列：_________ ， ___________ ，___________ ， ___________
3.输入序列为ABCDE，通过一个堆栈，不可能得到的输出序列有__________，__________， ________ ， ____________
4.树（A（B（E（K），F），C（G），D（H，I，J（M）））转化成二叉树后，其二叉树中序遍历次序为 __________________________
5.在一棵二叉树中，假定度为2的结点有5个，度为1的结点有6个，则叶子结点数有 ___________ 个。
6.对于一个具有 n个顶点和e条边的无向连通图，其生成树中的边数为 __________________________ 。
7.广义表中的元素可分为 _________ 和 __________ 两种。
8.假定对长度为n=21的有序表进行折半查找，则对应的判定树高度为 __________
9.在无向图G的邻接矩阵A中，若A[i][j]等于1，则A[j][i] 等于 __________ 。
10.要将序列{50，16，23，68，94，70，73}建成堆，只需把16与 _________ 相互交换。

Answer 1

1.一个算法的时间复杂度为（3n2+2nlog2n+4n-7）/(5n),其数量级表示为 O(n) 。
2.A，B,C三个结点为线性链表的相邻结点，P指针指向A结点，写出将B，C结点交换位置的操作序列： ， ， ， 。
3.输入序列为ABCDE，通过一个堆栈，不可能得到的输出序列有 CDEAB ，DCEAB，
DECAB， EDCAB等。
4.树（A（B（E（K），F），C（G），D（H，I，J（M）））转化成二叉树后，其二叉树中序遍历次序为 KEFBAGCHIMJD 。
5.在一棵二叉树中，假定度为2的结点有5个，度为1的结点有6个，则叶子结点数有 6 个。
6.对于一个具有 n个顶点和e条边的无向连通图，其生成树中的边数为 n-1 。
7.广义表中的元素可分为单元素和 子表两种。
8.假定对长度为n=21的有序表进行折半查找，则对应的判定树高度为 6 。
9.在无向图G的邻接矩阵A中，若A[i][j]等于1，则A[j][i] 等于 1 。
10.要将序列{50，16，23，68，94，70，73}建成堆，只需把16与 50 相互交换。

Answer 2

3.EDBAC EABCD EACBD
5.6
6.N-1
7.原子 表
8.logn
9.1

Answer 3

log2n