11、有一个完全二叉树按层次顺序存放在一维数组中，如下所示： 请指出结点P的父结点，左子女，右子女。 12、给出下列二叉树的先序序列。
13、已知某非空二叉树采用顺序存储结构，树中结点的数据信息依次存放在一个一维数组中，即
ABC□DFE□□G□□H□□，该二叉树的中序遍历序列为：
14、设一棵二叉树的前序序列为1,2,3,4,5,6,7,8,9,其中序序列为2,3,1,5,4,7,8,6,9,试画出该二叉树。
15、已知一组元素为（46，25，78，62，12，37，70，29），试画出按元素排列次序插入生成的一棵二叉树。
16、由于元素插入的次序不同，所构成的二叉排序树也有不同的状态，请画出一棵含有1，2，3，4，5，6六个结点且以1为根，深度为4的二叉排序树。 17、什么是线索二叉树？为什么要线索化？
18、有n个顶点的有向连通图最多有多少条边?最少有多少条边？ 19、下图中给出由7个顶点组成的无向图。从顶点1出发， 对它进行深度优先遍历得到的顶点序列是： 进行广度优先遍历得到的顶点序列是： 20、什么是连通图的生成树？ 21、什么是哈夫曼（Huffman）树？
22、已知结点a,b,c,d及其权值写出哈夫曼树的构造过程。 a b c d 7 5 2 4
23、已知图G={V , E} V={ a, b, c, d, e }
E={(a, b),(b, d),(c, d),(d, e),(e, a),(a, c)} 画出图G，画出图G的邻接表。 24、考虑下图：
1）从顶点A出发，求它的深度优先生成树。 2）从顶点E出发，求它的广度优先生成树。 3）根据普里姆（Prim）算法，求它的最小生成树。 25、设有关键码序列（Q，H，C，Y，Q，A，M，S，R，D，F，X），要按照关键码值递增的次序进行排序。
若采用初始步长为4的Shell排序法，则一趟扫描的结果是：
若采用以第一个元素为分界元素的快速排序法，则一趟扫描的结果是：
26、一个对象序列的排序码为{46，79，56，38，40，84}，采用快速排序以位于最左位置的对象为基准而得到的第一次划分结果为：
27、用二分法对一个长度为10的有序表进行查找，填写查找每个元素需要的比较次数。 下标： 0 1 2 3 4 5 6 7 8 9 比较次数：
28、若对序列(49,38,27,13,97,76,50,65)采用泡排序法(按照值的大小从小到大)进行排序，请分别在下表中写出每一趟排序的结果。 原始序列 49 38 27 13 97 76 50 65 第1趟的结果
第2趟的结果 第3趟的结果 第4趟的结果
29、给出一组关键字：29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排序时的变化过程：
1）归并排序 每归并一次书写一个次序。 2）快速排序 每划分一次书写一个次序。
3）堆排序 先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。
30、给出一组关键字T=（12，2，16，30，8，28，4，10，20，6，18）。写出用下列算法从小到大排序时第一趟结束时的序列： 1）希尔排序（第一趟排序的增量为5） 2）快速排序(选第一个记录为枢轴(分隔)) 3）链式基数排序（基数为10）
31、若杂凑表的地址范围为[0:9]，杂凑函数为H(key)=(key2+2)MOD 9，并且采用链地址方法处理冲突，请画出元素7,4,5,3,6,2,8,9,1依次插入该杂凑表以后，该杂凑表的状态。 32、已知二叉树采用二叉链表存储结构，链结点的构造为lchild | data | rchild ，根结点的指针为T。下面是利用中序遍历的方法统计二叉树中度为1的结点的个数的算法，算法中设置了一顺序存储结构的堆栈STACK [1:M]，栈顶指针为top，请在算法的空缺处填入适当内容，使之能正常工作。
33、设有一个顺序栈S，元素s1, s2, s3, s4, s5, s6依次进栈，如果6个元素的出栈顺序为s2, s3, s4, s6, s5, s1，则顺序栈的容量至少应为多少？
34、设有一个关键码的输入序列 { 55, 31, 11, 37, 46, 73, 63, 02, 07} ,
(1) 从空树开始构造平衡二叉搜索树, 画出每加入一个新结点时二叉树的形态。若发生不平衡, 指明需做的平衡旋转的类型及平衡旋转的结果。
(2) 计算该平衡二叉搜索树在等概率下的查找成功的平均查找长度和查找不成功的平均查找长度。
35、关键码的输入序列 { 55, 31, 11, 37, 46, 73, 63, 02, 07 }请计算在二分法查找、二叉排序树两种的情况下等概率下查找成功的平均查找长度。
36、 广义表A=（a,b,(c,d),(e,(f,g))）,计算下面式子的值Head(Tail(Head(Tail(Tail(A))))) 37、 下图是用邻接表存储的图，画出此图，并写出从C点开始按深度优先、广度优先遍历该图的结果。
38、 用序列（46，88，45，39，70，58，101，10，66，34）建立一个排序二叉树，画出该树，并求在等概率情况下查找成功的平均查找长度。
39、 判断下列序列是否为堆，如果不是请调整为堆，如果是请判断是什么类型的堆（101，88，46，70，34，39，45，58，66，10）
40、 假设一棵二叉树的层序序列是ABCDEFGHIJ和中序序列是DBGEHJACIF,请画出该树。
41、 找出所有满足下列条件的二叉树
a) 它们在先序遍历和中序遍历时,得到的结点访问序列相同； b) 它们在后序遍历和中序遍历时,得到的结点访问序列相同； c) 它们在先序遍历和后序遍历时,得到的结点访问序列相同。
42、 已知L是无表头结点的单链表,其中P结点既不是首元结点,也不是尾元结点。 a)在P结点后插入S结点的语句序列是______ b)在P结点前插入S结点的语句序列是______ c)在表首插入S结点的语句序列是______ d)在表尾插入S结点的语句序列是______ (1) P->next=S;
相关推荐：
loading