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、试比较线性表的顺序存储结构和链式存储结构的优缺点。
B A D B C F E D F G E H G H aC 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、如图所示的二叉树完成中序遍历、后续遍历、先序遍历，并画出后续线索化的二叉树。
A B E C D F 83、将下图转换为二叉树，对转换后的二叉树进行先根、中根、后根遍历。
A
B C D
E F G J
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={
a
c
e
b
d
90、请画出下图中的极大连通子图。
f
1 2 3 4 5 6
91、对于如下图请画出其用prim和kruskal两种不同算法生成最小生成树的各条边的并入顺序。画出最小生成树。并写出广度优先和深度优先的结点遍历顺序。
3 3 10 6 24 4 5 8
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应放入哪
1
3
61
8
5 6 7 12 2 3 1 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;
数据结构试题及答案
