求高手做下数据结构的题！一套试题额 急！完事追加分 谢谢各位大虾！

Question

选择：
1．下列数据组织形式中，（ ）的结点按逻辑关系依次排列形成一个“锁链”。
A.集合 B.树形结构
C.线性结构 D.图状结构
2．数据结构可以形式化地定义为（S，△），其中S指某种逻辑结构，△是指（ ）
A.S上的算法 B.S的存储结构
C.在S上的一个基本运算集 D.在S上的所有数据元素
3．设非空单链表的数据域为data，指针域为next，指针p指向单链表中第i-1个结点，s指向已生成的新结点，现将s结点插入到单链表中，使其成为第i个结点，下列算法段能正确完成上述要求的是（ ）
A.s->next=p->next;p->next=s；
B.p->next=s;s->next=p->next；
C.s=p,p=s->next
D.p=s;s->next=p；
4．一个仅能在表尾进行插入和删除操作的线性表是一种特殊类型的表，我们称之为（ ）
A.顺序表 B.单链表 C.队列 D.栈
5.一个栈的输入序列为12345，则下列序列中是栈的输出序列的是（ ）。
A.23415 B.54132 C.31245 D.14253
6.已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t到s。若字符串S=″SCIENCESTUDY″，则调用函数Scopy(P,Sub(S,1,7))后得到( )

A.P=″SCIENCE″ B.P=″STUDY″
C.S=″SCIENCE″ D.S=″STUDY″
7.循环队列中判定队列已满的条件是（ ）
A. Q.rear=Q.front B.(Q.rear+1)%maxQsize==Q.front
C.Q.rear==null D.Q.front==null
8.下列陈述中正确的是( )
A.二叉树中所有结点均有左右两个孩子
B.二叉树中结点只有一个孩子时无左右之分
C.二叉树中必有度为2的结点
D.二叉树中最多只有两棵子树，并且有左右之分
9.树作为一种数据结构，最直观的体现了（ ）、
A.一对一的关系 B.集合关系 C.一对多的关系 D.多对多的关系
10.对四个电报文A，B，C，D进行赫夫曼编码，得到A（0），B（10），
C（110），D（ ）
A.001 B.010 C.101 D.111二、填空
1.若一个算法中的语句频度之和为则算法的时间复杂度为________。
2.单链表中，已知当前数据的指针为P，则其后继的指针q=_________。
3.假设以S和X分别表示进栈和退栈操作，则对输入序列a,b,c,d,e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为________。
4.串S=”I am a worker″的长度是________。
5.深度为20的满二叉树上，第6层有________个结点。
6.在一棵完全二叉树上存在着64个结点,则结点序号为22的结点的左孩子的序号为_________。
7.一个拥有n个顶点的图，最多存在________条边。
8.串“abc”最多可以有_________个子串。
9.判定循环队列为空的条件是__________。
10对一个表长为n的顺序表在i个元素前进行插入操作，则需要移动_______个元素。
三、简述：
1.给定先序遍历二叉树的顺序为ABDEFGCH,中序为DBFEGACH，请还原该二叉树。
2．将下列森林转化为二叉树，

3. 设有一个顺序栈S，元素s1, s2, s3, s4, s5, s6依次进栈，如果6个元素的出栈顺序为s2, s3, s4, s6, s5, s1，则计算该顺序栈的容量至少应为多少？

四．算法分析
1. 给出从结点v1出发按深度优先搜索遍历图所得的结点序列；给出图的拓扑序列（要求描述算法）；

2.已知网如下，请给出h点到任意一点的最短路径和权值，要注意求解的顺序

五、程序设计：
现在有两个单链表和这两个链表均按照数据元素非递减排列，要求将这两个链表归并为一个非递减排列的单链表，请写出该算法的C语言程序，并对关键语句进行注释。
第四题 图片

Answer 1

第四题的图呢？把图发出来！