二、解答题（共70分）1.请简述渐进复杂度的定义，大O符号的数学定义。2.简述共享栈的结构，并回答下列问题：(1)写出从stack1和stack2的入栈操作和出栈操作的语句，(2)写出判断栈满和栈空的语句3.给出以下无向带权图，边上标”?”的代表边的权未知，现在给出这个AOE网的最小生成树的建立过程(采用prim算法)，试推算出未知边权值范围初始节点A加入过程为：A->B，A->E，B->D，E->F，B->C，C->G4.二叉排序树的先序遍历序列为（6，4，3，NULL，NULL，5，NULL，NULL，10，NULL，17，NULL，NULL），NULL表示空指针。(1)请根据此序列画出二叉排序树。(2)若删除10节点，请分别写出删除之后的中序和后序遍历序列（带NULL的）。(3)试对比二叉排序树与哈希算法，并指出前者的优势所在。5.给以下AOE网，求关键路径和A到其他点的最短路6.设有一组关键字{9,1,23,14,55,20,84,27}，采用哈希函数：H(key)=keymod7，表长为10，用开放地址法的二次探测再散列方法Hi=(H(key)+di)mod10(di=)解决冲突。要求：对该关键字序列构造哈希表，并计...3,2,1222西交软工19考研群号：636333189算查找成功的平均查找长度。7.给出一组关键字(12,2,16,30,8,28,4,10,20,6,18)，写出用希尔排序（增量为3）第一趟结果。8.有序列(29,18,25,47,58,12,51,10)，对此序列进行建堆，并画出其删除根节点后的堆结构。五．程序设计（每题10分，共40分）1.输入一串字符串，字符串以”#”结尾，判断输入的字符串中0-9的个数。2.输入学生的姓名和成绩，按学生成绩进行排序后输出。3.输入年月日，求这是当年第几天。4.把n个球放进m个盒子，允许盒子为空，共有多少种放法。西交软工19考研群号：636333189
