已知二又树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／一，其前缀形式为( )。
在散列表上，每个地址单元所链接的同义词表的( )。
已知一棵满Z树的结点个数为20到40之间的素数，此二叉树的叶子结点有( )个。
假设某硬盘由 5 个盘片构成（共有 8 个记录面）， 盘面有效记录区域的外直径为 30cm， 内直径为 10cm，记录位密度为 250 位/mm， 磁道密度为 16 道/mm， 每磁道分 16 个扇区， 每扇区 512 字节， 则该硬盘的格式化容量约是（ ）。
已知一个二叉树有1025个结点，那么由此推断二叉树的高h为( )。