1．在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为1，右孩子的平衡因子为0，则应作_型调整以使其平衡。
A.LL
B.LR
C.RL
D.RR

答案为a，错选了c。
平衡因子 = 左子树高度 - 右子树高度
错因:找到了最小不平衡子树为左孩子的左子树（LL）应做右单旋转，但这个操作的名称叫LL。

LL:右单旋转
RR:左单旋转
LR:左旋转再右旋转
RL:右旋转再左旋转

线性表中每个元素都有一个前驱和一个后继元素。

这个说法是不对的，第一个元素无前驱节点，最后一个元素无后继节点。

若从某顶点出发对无向图G进行深度优先搜索遍历,所得的遍历序列唯一，则可断定图中有两个顶点的度为1。

这个说法是正确的。（就算是环，也有两种序列，因为是无向图）

广义表A=(((a,b),(c,d),e))，取出A中的原子e的操作是_

在广义表中，head取出的是表中第一个元素，tail取出的是当前表的下一个元素。
因此答案为:head ( tail ( tail ( head(A) ) ) )

解答本题时，首先要清楚取表头和表尾运算 head 和 tail运算的含义: head(A)返回A表中的第一个元素;tail(A)则返回在A表中去掉第一个元素后所得到的表。
为取出元素e，首先要将e所在的元素（子表〉取出来，即执行head(A)，得到A的第一个元素((a,b).(c,d),e)，由于e是其中第三个元素，故要连续去掉其前面两个元素，即执行两次取表尾元素，然后再执行取表头运算，按由里到外的次序合成得到答案。
类似地，若要取出其中的原子b，其复合函数应是head(tail(head(head(A)))).

9．在有序表A[22]中，按二分查找方法进行查找，查找值为A[15]的元素依次比较的元素的下标是

第一次 mid = (0+21)/2 = 10
第二次
low = mid+1 = 11
mid = (11+21)/2 = 16
第三次
high = mid-1 = 15
mid = (15+11)/2 = 13
第四次
low = mid + 1 = 14
mid = (14+15)/2 = 14
第五次
low = mid + 1 = 15
mid = (15+15)/2 = 15

因此搜索下标应该为 10 16 13 14 15
关键在于更新时，若low更新因为low = mid - 1 若high更新应为high = mid+1，别把+1或者-1忘了

3．已知散列表的地址空间为0～13，散列函数为H(k)=k%13，用线性探查法处理冲突。
将下列元素依次插入到初值为空的散列表中，画出该表，并求出在等概率情况下，查找成功时的平均查找长度。
( 11,22,33,57,65,31,43,98,77,100,30,28)

注意要看清是如何解决冲突的，别想当然用拉链法去解决。最终答案为2.

2．设计算法按先序次序遍历先序线索二叉树。要求采用非递归形式，且不用栈。

BiTnode *NextNode(BiTnode *p){if(p->ltag == 0) return p->lchild;//如果有左孩子，后继是其左孩子else return p->rchild;//没有左孩子的话后继是右孩子或者后继线索
}void PreTraverse(BiTnode *t){BiTnode *p = t;//第一个节点为tfor(;p;p = NextNode(p))visit(p)
}

与之相对应的是中序线索二叉树的遍历，注意进行区分。

BiTnode *FirstNode(BiTnode *t){//找到中序的第一个节点while(p->tag == 0) p = p->lchild;return p;//最左下节点
}BiTnode *NextNode(BiTnode *t){//找到中序后继节点if(t->rtag == 1) return t->rchild;//右孩子是线索，直接返回else return FirstNode(t->rchild);//返回右子树的第一个节点
}void InTraverse(BiTnode *t){for(BiTnode *p = FirstNode(t);p;p = NextNode(p))visit(p);
}

注意上述代码第一个函数中while(p->ltag == 0) p = p->lchild;这个条件可不可以替换为while(p->lchild) p = p->lchild;显然是不可以的，因为在后续调用中， p = p->lchild有可能为线索这个条件一定要注意。

void swap(int *a,int *b){int tmp;tmp = *a;*a = *b;*b = tmp;
}
void sort(int a[],int n){int low = 0,high = n-1;while(lowwhile(a[low]%3 == 0)low++;while(a[high]%3 != 0) high--;if(low<=high) swap(&a[low],&a[high]);else break;}high = n-1;low++;while(lowwhile(a[low]%3 == 1)low++;while(a[high]%3 != 1) high--;if(low<=high) swap(&a[low],&a[high]);else break;}high = n-1;low++;while(lowwhile(a[low]%3 == 2)low++;while(a[high]%3 != 2) high--;if(low<=high) swap(&a[low],&a[high]);else break;}
}
int main()
{int num[] = {1,3,5,7,9,2,4,6,8,10};for(int i=0;i<10;i++){printf("%4d",num[i]);}printf("\n");sort(num,10);for(int i=0;i<10;i++){printf("%4d",num[i]);}return 0;
}

别忘了在swap前加一个判断是否low

struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;};struct TreeNode* Build(int *preorder,int p1,int p2,int *order,int o1,int o2){struct TreeNode *root = (struct TreeNode*)malloc(sizeof(struct TreeNode));root->val = preorder[p1];int mid;for(mid = o1;order[mid]!=root->val;mid++) ;int llen = mid - o1;int rlen = o2 - mid;if(llen){root->left = Build(preorder,p1+1,p1+llen,order,o1,o1+llen-1);}elseroot->left = NULL;if(rlen){root->right = Build(preorder,p2-rlen+1,p2,order,o2-rlen+1,o2);}elseroot->right = NULL;return root;
}
struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize){struct TreeNode *root;root = Build(preorder,0,preorderSize-1,inorder,0,inorderSize-1);return root;
}void traverse(struct TreeNode* t){if(!t) return;if(t->left)printf("( %d , %d )\n",t->val,t->left->val);traverse(t->left);traverse(t->right);}
int main()
{int pre[] = {3,9,20,15,7};int in[] = {9,3,15,20,7};struct TreeNode* t = buildTree(pre,5,in,5);traverse(t);return 0;
}