58、试问在直接插入排序、希尔排序、快速排序、归并排序、二分法排序、直接选择排序中，哪些排序是稳定的？哪些是不稳定的，哪个排序平均比较次数最少？哪个排序要求内存容量最多？
59、哈希表中使用哈希函数H（key）=3 * key % 11,并采用开放定址法处理冲突，随机探测再散列的下一地址公式为： d1=H (key )
di=( di-1 +7 * key ) % 11 （I=2,3…..）
试在0到10的散列地址空间中对关键字序列（22，41，53，46，30，13，01，67）画出Hash表示意图，并求在等概率情况下查找成功的平均查找长度。
60、什么是内部排序？什么是排序方法的稳定性？说出你所学过的三个稳定算法，一个不稳定算法。
61、何为队列上溢？一般用什么方法解决，简述之。 62、载入下图所示的有权图G，回答下列问题：
1） 给出从结点v1出发按深度优先搜索遍历图所得的结点序列； 2） 给出图的拓扑序列；
3） 给出从结点v1到结点v8的最短路径和关键路径。 63、对于下图，请给出
1） 对应的邻接矩阵，并给出A,B,C三个顶点的入度和出度； 2） 邻接表表示和逆邻接表表示； 3） 求其连同分量；
64、对于下图的树，分别用孩子链表和孩子兄弟链表法画出存储结构。 65、对于下图的树，请分别用中序、先序的方法写出其遍历结果。 66、已知一个表{jan,feb,mar,apr,may,june,july,aug,sep}
1) 使按表中元素的次序依次插入一棵初始为空的二叉排序树，画出表中元素构成的二叉排序树。
2) 求初等概率情况下查找july的查找长度。
67、数组a[1..10,-2..6,2..8]以行优先的顺序存储，设第一个元素的首地址为100，每个元素占3个存储长度的存储空间，则元素A[5,1,8]的存储地址为多少？
68、设有一组关键字（17，13，153，29，35，21）需插入到表长为12的表中，请回答下列问题：
1） 自己设计一个合理的散列函数
2） 用自己设计的函数将上述关键字插入到散列表中，画出其结构；并指出用线性探测法解决冲突构造散列表的装填因子为多少？
69、已知一棵三阶B-树如下图所示，假定依次从中删除关键字46，24，52，8，93和80试画出每次删除结点后树的情况：
70、已知一棵三阶的B-树如下图所示，假定依次插入关键字 50，83，10请画出插入个结点后树的情况：
71、令s=?aaab?,t=?abcaaa?,u=?abcaabbabcabaacbacbaaa?,分别求出他们的next值。 72、请画出下列二叉树的中序线索化前趋链树，后序线索化后继链树。 73、将下列结点按输入顺序构造一棵二叉平衡树。
{As，Bx，Ca，Dww，Ae，Cf ，Edd，Fap，Goi，Fab，Hre}
74、试在如图所示线索化的二叉树中，查找指定结点E的后继结点、C 的前驱结点，并说明找到结果的原因。 75、什么是数据结构？
76、试比较线性表的顺序存储结构和链式存储结构的优缺点。 77、堆栈和队列都是特殊线性表，其特殊性是什么？
78、将两个栈存入数组V[1..m]中应如何安排最好?这时栈空栈满的条件是什么?
79、内存中一片连续空间（不妨假设地址从1到m），提供给两个栈S1和S2使用，怎样分配这部分存储空间，使得对任一个栈，仅当这部分空间全满时才发生上溢。
80、给出数组 int A[3…8，2…6]；当它在内存中按行存放和按列存放时，分别写出数组元素A[i,j]的地址计算公式（设每个元素占两个存储单元）。
81、若一二叉树有2度结点100个，则其叶结点有多少个？该二叉树可以有多少个1度顶点？
82、如图所示的二叉树完成中序遍历、后续遍历、先序遍历，并画出后续线索化的二叉树。 83、将下图转换为二叉树，对转换后的二叉树进行先根、中根、后根遍历。 84、有一组数值14、21、32、15、28，画出哈夫曼树的生成过程及最后结果。 85、有n个顶点的有向连通图最多有多少条边?最少有多少条边？ 86、什么是哈夫曼（Huffman）树？ 87、已知图G={V , E} V={ a, b, c, d, e }
E={(a, b),(b, d),(c, d),(d, e),(e, a),(a, c)} 画出图G，画出图G的邻接表。
88、设一个有向图为G=(V,E),其中V={v1,v2,v3,v4}，E={
89、请给出下图的邻接矩阵和邻接表。 90、请画出下图中的极大连通子图。
91、对于如下图请画出其用prim和kruskal两种不同算法生成最小生成树的各条边的并入顺序。画出最小生成树。并写出广度优先和深度优先的结点遍历顺序。
92、什么是静态查找，什么时动态查找，什么叫平均查找长度。
93、用序列（46，88，45，39，70，58，101，10，66，34）建立一个二叉排序树，画出该树，并求在等概率情况下查找成功的平均查找长度。
94、已知一个线性表（38，25，74，63，52，48），假定采用h(k)=k%7计算散列地址进行散列存储，若引用线性探测的开放地址法解决冲突，则在该散列表上进行检索的平均检索长度为多少，若利用连地址法处理冲突，则在该散列表上进行检索的平均查找长度为多少？设地址空间为9。请画出算列表。
96、已知长度为12的表：（Jan , Fed , Mar , Apr , May , Jun , Aug , Sep , Oct , Nov , Dec）按表中元素的顺序，依次插入一棵初始为空的二叉排序树，画出插完之后的二叉排序树，并求其在等概率情况下，查找成功的平均查找长度。
98、有散列函数为h(k)=k,如果用二次探测在散列的方式解决冲突，49应放入哪？ 0 1 2 3 4 5 6 7 8 9 10 11 12 13
99、用增量序列{8、4、2、1}对下列关键字进行希尔排序，用图表示排序过程。 {56、37、59、41、98、47、94、50、63、52、42、54、60、72、86、90}
100、有一组关键字{14，15，30，28，5，10}，分别画出冒泡排序、快速排序过程的图示。 101、已知一组键值序列为(38，64，73，52，40，37，56，43)，试采用快速排序法对该组序列作升序排序，并给出每一趟的排序结果。
102、对关键字序列（72，87，61，23，94，16，5，58）进行堆排序、快速排序、直接选择排序，使之关键字递增有序，请写出每个排序的前三趟结果。 五、程序题 四、程序题
1、已知二叉树用下面的顺序结构存储，写出中序遍历该二叉树的算法。 left date right 2、下列算法为删除单链表中值为X的算法，将程序填完整
void del(struct node *head) { q=head; p=q->next; while(( )&&( )) { q=p; _________;}
if(p= = null) printf(“error”); else{______________; free(p);printf(“success!”);}}
3、以下函数中，h是带头结点的双向循环链表的头指针， （1） 写出下列程序的功能。
（2） 当链表中结点数分别为1和6（不包括头结点）时，请写出程序中while循环体的执行次数。
Int fox(struct node *h) { struct node p,q; int j=1; p=h->next; q=h->prior;
while(p!=q && p->prior!=q) { if (p->data= = q->data) {p=p->next;