Question

数据结构的题目！！不知如何做啊！数据结构高手帮帮忙，急

1\向一个长度为N的顺序表中插入一个新元素的平均时间复杂度为()

2\根据一个长度为N的单链表的表头指针HL，向其表尾插入一个新结点的时间复杂度为()

3\在一个单链表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\当利用大小为N的数组顺序存储一个栈时，假定用top==N表标栈空，用top==0表示栈满，则向这个栈插入一个元素时，首先应执行()操作修改top指针

5\在具有N个顶点的强连通图中至少含有()条有向边

6\从一棵二叉树搜索中查找一个元素时，其时间复杂度大致为
O(1)
O(n)
O(log2n)
O(n2)

7\由权值分别为3,8,6,2的四叶子结点生成一棵哈夫曼树，它的带权路径长度为

8\在一棵5阶B＿树中，每个结点最多允许有（）个关键字．

9\若根据数据集合{23,44,36,48,52,73,64,58}建立散列表，采用h(K)=K%13计算散列地址，并采用链接法处理冲突，则元素64的散列地址为

在（）结构中，前驱和后继结点之间存在着1对N的联系
在线性表的单链接存储中，假定每个结点的结构为(data,next),若一个结点的地址为P，则其后继结点的地址为（）
栈又称为（）表，队列又称为先进先出表.
假定一棵树的广义表示为A(B,C(I,J),D(E,F(H,G))),则树的深度为（）
在一棵具有N个结点的二叉树所对应的二叉链表中，必定包含有（）个空指针．
对于一个具有N个顶点和E条边的连通图，存储它所用邻接表的空间复杂度为（）
在一个索引表中，每个索引项至少包含有索引值域和子表的（）域这两项．
在线性表的（）存储中，无法查找到一个元素的前驱和后继元素．
在一棵B＿树中，所有（）结点都处在同一层上，即最低层上．
在对N个记录进行排序的过种中，由初始堆到堆排序结束，需要对树根结点进行（）次筛选．

运算题
1：假定一棵二叉树广义为a(b(c),d(e,f(,g))),试分别写出对它进行先序，中序，后序遍历的结果：
先序：
中序：
后序：

2：
已知一个图的顶点集V和边集G分别为：
V={0,1,2,3,4,5};
E=p{(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)10,(2,4)13,(3,5)9};
试写出按照普姆算法从顶点1出发得到最小生成树的过种中，依次选取的各条边，并求出其最小生成树的权.
各条边:(),(),(),(),(),
最小生成树的权:

3已知一个图的顶点集V和边集G分别为:
V={0,1,2,3,4,5,6,7}
E={ <0,2 >, <1,3 >, <1,4 >, <2,4 >, <2,5 >, <3,6 >, <4,7 >, <5,7 >, <6,7 >};
若存储它采用相邻接表，并且每个顶点邻接表中的边结点都是按照出边顶点序号从小到大的次序链接的，则按照主教材中介绍的进行拓扑排序的算法，写出得到的拓扑序列

4\有5个带权结点，其权值分别为3,7,2,6,14,以它们为叶子结点生成一棵霍夫曼树，求出该树的带权路径长度和树的高度．
带权路径长度：

高度：

Answer 1

1)2) o(n)
3) B
4)top--;
6)o(logn)
9)12