有一个不带头结点的单链表list，链表中结点都有两个域：数据域data和指针域link。已知初始时该单链表无序，请设计一个算法将该链表按结点数据域的值的大小，将其从小到大依次重新链接，在链接过程中不得使用除该链表以外的任何链结点空间。要求： (1)给出算法的基本设计思想。 (2)根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。
已知顺序表A，在不改变顺序表中奇数号元素与偶数号元素相对位置的前提下，设计算法，将所有奇数号元素移到所有偶数号元素前。 (1)给出算法的基本设计思想。 (2)根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。 (3)说明你所设计算法的时间复杂度和空间复杂度。
键树(Trie)，又称数字查找树，它是一棵度大于等于2的树，树中的每个结点中不是包含一个或几个关键字，而是只含有组成关键字的符号。请用类C语言或类PASCAL语言编写一个在键树T上查找关键字等于给定值KEP的记录的算法。若查找成功，返回指向该记录的指针；否则返回空指针。
已知二又树T的结点形式为(Uink，data，count，rlink)，在树中查找值为X的结点，若找到，则记数(count)加1：否则，作为一个新结点插入树中，插入后仍为二叉排序树，写出其非递归算法。
任何一个无向连通图( )最小生成树。
构建一个哈夫曼树，如果给定权值的个数为n，那么哈夫曼树的结点总数为( )。
下面的算法实现了将二叉树中每一个结点的左右子树互换。addQ(Q，bt)为进队的函数，delQ(Q)为出队的函数，empty(Q)为判别队列是否为空的函数，空白处应填的内容是( )。 typedef struct node{ int data； struct node*lchild，*rchild； }btnode； void exchange(t)tnode*bt){ btnode*p，*q； if(bt){ addQ(Q，bt)； while(!EMPTY(Q)){ p=delQ(Q)； q=p->rchild； p一>rchild=p一>lchild； ( (1) )=q； if(p->lchild) ( (2) )； if(p->rchild)addQ(Q，p->rchild)； } }}
设森林F中有三棵树，第一、第二、第三棵树的结点个数分别为M
1
、M
2
和M
3
。与森林F对应的二叉树根结点的右子树上的结点个数是( )。
简述栈、队列、循环队列的定义。
有n个叶结点的非满的完全二叉树的高度为( )。
已知两个长度分别为l和s的降序链表，若将它们合并为一个长度为l+s的升序链表，则最坏情况下的时间复杂度是( )。
若一组记录的关键码为(46，79，56，38，40，84)，则利用快速排序的方法，以第1个记录为基准得到的一次划分结果为( )。
设某二叉树中只有度为0和度为2的结点，如果此二叉树的高度为100，那么此二叉树中所包含的结点数最少为( )。
已知某哈夫曼树的度为m，其中叶结点个数为n，那么非叶结点的个数为()。
下列排序方法中，时间复杂性不受数据初始状态影响，恒为O(nlog
2
n)的是( )。
B综合应用题41-47小题。/B
在一棵高度为九的理想平衡二叉树中，最少含有( )个结点，最多含有( )个结点。
某个任务的数据模型可以抽象为给定的k个集合：S
1
，S
2
，…，S
k
。其中S
i
(1≤i≤k中的元素个数不定。在处理数据过程中将会涉及元素的查找和新元素的插入两种操作，查找和插入时用一个二元组(i，x)来规定一个元素，i是集合的序号，x是元素值。设计一种恰当的数据结构来存储这k个集合的元素，并能高效地实现所要求的查找和插入操作。
(1)构造数据结构，并且说明选择的理由。
(2)若一组数据模型为S
1
={10．2，1．7，4．8，16．2}，S
2
={1．7，8．4，0．5}，S
3
={4．8，4．2，3．6，2．7，5．1，3．9}，待插入的元素二元组为(2，11．2)和(1，5．3)，按你的设计思想画出插入元素前后的数据结构状态。
已知一算术表达式的中缀形式为A+B*C-D／E，后缀形式为ABC*+DE／一，其前缀形式为( )。
在散列表上，每个地址单元所链接的同义词表的( )。