1、i+） sum+=1; 2. 数据结构由数据的逻辑结构、存储结构和数据的（ ）三部分组成。3. 长度为11的有序表，采用折半查找，在等概率情况下查找成功的平均查找长度为（ ）。4. 使用一个100个元素的数组存储循环队列，如果采取少用一个元素空间的方法来区别循环队列的队空和队满，约定队头指针front等于队尾指针rear时表示队空。若为front=8，rear=6，则队列中的元素个数为（ ）。5. 将有关二叉树的概念推广到三叉树，一颗有244个结点的完全三叉树的深度为（ ）。6. 设一颗完全二叉树共有101个结点，它有（ ）叶子结点。7. 出栈操作时应判别栈是否（ ）。8. 带头结点的单链表H
2、ead为空的条件是（ ）。9. 快速排序的时间复杂度为（ ）。10. 某二叉树的先序和后序序列正好相反，则该二叉树一定是（ ）的二叉树。三、判断题（10小题，每题2分，共20分）1. 数据元素是数据的最小单位。2. 折半查找方法要求待查表必须是顺序存储结构的有序表。3. 当两个字符出现的频率相同时，则其哈夫曼编码也相同。4. 如果某种排序算法是不稳定的，则该算法是没有实际意义的。5. 将一棵树转换为二叉树后，根结点没有右子树。6. 串既可采用顺序存储，也可采用链式存储。7. 一个广义表的表尾总是一个广义表。8. 完全二叉树的叶子结点只可能在层次最大的一层上出现。9. 顺序存储结构的主要缺点是不
3、利于插入或删除操作。10. 算法是对特点问题求解步骤的一种描述，因此它可以没有输入和输出。四、综合应用题（6小题，每题10分，共60分）1. 下表列出了某工序之间的优先关系和各工序所需时间。要求： （1）画出AOE网 （2）列出各事件的最早开始时间、最迟开始时间（3）找出关键路径并指明完成该工程所需最短时间。工序代号所需时间前驱工序a16无a79a4, a5a24a87a35a9a2,a6a41a102a5a11a8, a9a6a1232. 若一棵完全二叉树中叶子结点的个数为n,且最底层结点数2，则此二叉树的深度H=？3. 已知一颗二叉树的中序序列为BJFKDGAELIMHC，后序序列为JKF
4、GDBLMIHECA，画出该二叉树的先序线索二叉树。4. 在nn矩阵A中，所有下标值满足关系式i+jn+l的元素aij（1i,jn）的值均为0，现将A中其它元素按行优先顺序依次存储到长一维数组sa中，其中元素a1，n存储在sa0。（1）设n=10，元素a4，9存储在sap，写出下标p的值；（2）设元素ai，j存储在sak中，写出由i,j和n计算k的一般公式。5. 假定对有序表（1,9,15,21,24,35,52,54,61,65,97）进行折半查找，试回答问题：（1）画出描述折半查找过程的判定树；（2）分别求等概率情况下查找成功和不成功时的平均查找长度。6. 已知待排记录的关键字序列为25，
5、96，11，63，57，78，44，请回答下列问题：（1）写出堆排序的初始堆（大根堆）关键字序列；写出堆排序1趟以后（交换与调整之后）的关键字序列；（2）写出快速排序1趟以后的关键字序列；写出快速排序2趟以后的关键字序列。（3）写出冒泡排序1趟以后的关键字序列；五、算法设计与编程（3小题，每题10分，共30分）1. 函数digit（n,k）的功能是求正整数n中从右端开始的第k（1）个数字的值（k从1开始），如果k超过了n的位数，则函数返回1；否则返回n中第k个数字。例如： digit（264539 , 3）=5 digit（7622 , 5）=-1要求分别用递归和非递归设计该函数。2. 设有一
6、个正整数序列组成的有序单链表（按递增次序有序，且允许有相等的整数存在），试编写能实现下列功能的算法 ：（要求用最少的时间和最小的空间） 确定在序列中比正整数x大的数有几个（相同的数只计算一次）。 在单链表中将比正整数x小的数按递减次序排列。 将比x大的偶数从单链表中删除。3. 在二叉树中查找值为x的结点，请编写一算法用以打印值为x的结点的所有祖先，假设值为x的结点不多于1个。二O 一四年招收硕士研究生入学考试试题1. 算法分析的主要内容是（ ）。A）正确性 B）可读性和稳定性 C）简单性 D）空间复杂性和时间复杂性2. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ ）。A）必须是
7、连续的 B）部分地址必须是连续的C）一定是不连续的 D）连续或不连续都可以3. 设有6个元素按1、2、3、4、5、6的顺序进栈，下列不合法的出栈序列是（ ）。A）234165 B）324651 C）431256 D）5463214. 设有二维数组A1.12,1.10，其每个元素占4个字节，数据按行优先顺序存储，第一个元素的存储地址为100，那么元素A5,5的存储地址为（ ）。A）76 B）176 C）276 D）3765. 已知一棵二叉树的先序序列为ABDGCFK，中序序列为DGBAFCK，则后序序列为（ ）。A）ACFKDBG B）GDBFKCA C）KCFAGDB D）ABCDFKG6.
8、在二叉树结点的先序，中序和后序序列中，所有叶子结点的先后顺序（ ）。A）都不相同 B）完全相同C）先序和中序相同，而与后序不同 D）中序和后序相同，而与先序不同7. 图的深度优先遍历类似于二叉树的（ ）。A）先序遍历 B）中序遍历 C）后序遍历 D）层次遍历8. 下面（ ）算法适合构造一个稠密图G的最小生成树。A） Prim算法 B）Kruskal算法 C）Floyd算法 D）Dijkstra算法9. 对关键码46,79,56,38,40,84采用堆排序,则初始化堆（小堆）后最后一个元素是（ ）。A）84 B）46 C）56 D）3810.在Hash函数H（k）=k MOD m中，一般来讲m应
9、取（ ）。A）奇数 B）偶数 C）素数 D）充分大的数1. 在单向链表某P结点之后插入S结点的操作是（ ）。2. 线性表用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是（ ）。3. 一个栈的输入序列是：1，2，3则不可能的栈输出序列是（ ）。4. 一棵二叉树高度为h,所有结点的度或为0，或为2，则该二叉树最少有（ ）结点。5. 在完全二叉树中，编号为i和j的两个结点处于同一层的条件是（ ）。6. 若无向图G=（V,E），其中V=a,b,c,d,e E=（a,b）,（a,d）,（a,c）,（d,c）,（b,e），现采用图的（ ）遍历方法从顶点a开始遍历图，得到的
10、序列为abecd。7. 求最短路径的Dijkstra算法的时间复杂度为（ ）。8. 假定有k个关键字互为同义词，若用线性探测再散列法把这k个关键字存入散列表中，至少要进行（ ）次探测。9. 设在已排序的线性表中共有元素n个，若用二分法查找表中的元素。若查找成功，至少要比较（ ）次10.对一组记录（54,38,96,23,15,2,60,45,83）进行直接插入排序，当把第7个记录60插入到有序表时，为寻找插入位置需比较（ ）次。三、综合应用题（7小题，每题10分，共70分）1. 已知A1.N是一棵顺序存储的完全二叉树，如何求出Ai和Aj的最近的共同祖先？2. 请给出一棵哈夫曼树中分支数B与叶子
11、节点数n0所满足关系式，并证明你的结论。3. 下面的排序算法的思想是：第一趟比较将最小的元素放在r0中，最大的元素放在rn-1中，第二趟比较将次小的放在r1中，将次大的放在rn-2中，,依次下去，直到待排序列为递增序。（注： 代表两个变量的数据交换）。void sort（SqList &r,int n） i=0;while（ （1） ） min=max=i; for （j=i+1; （2） ;+j） if（ （3） ） min=j; else if（rj.keyrmax.key） max=j; if（ （4） ） rminri; if（max!=n-i-1） if（ （5） ） rminrn-
12、i-1; else rmaxnext=NULL 9. O（nlogn）10. 空或一个结点或单分支1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 1.事件V1V2V3V4V5V6V7V8V9V10最早发生时间14161821最迟发生时间1019关键路径：a1-a4-a8-a11-完成该工程所需最短时间：2.设具有n个结点的完全二叉树的深度为H由完全二叉树的定义可知：第i（1iH1）层上的结点数将达到最大（2i-1）,第H层上的结点数将2且2k-1 122H-22n 122H-2 2H-12H-1+1n 2H-1 2H-1n 2HH-1log2nnext; pre=L; end=L
13、; while（p） if（p-datadata&status=0） count+; comp=p-data; if（status=0） if（p=L&p-data%2=0） t=p; L-next=p- free（t）; else if（p!=L&data%2=0） t=p; pre- p=pre- else pre=p; p=p- end=pre; if（status=1） t=pre-next=work; work=p; p=t; end-3 typedef structBiTree t;int tag; /tag=0表示左子女被访问，tag=1表示右子女被访问stack;void Se
14、arch（BiTree bt,ElemType x） stack s; top=0; while（bt!=null|top0） while（bt!=null & bt-data!=x） s+top.t=bt; stop.tag=0; bt=bt-lchild; if（bt-data=x） printf（“所查结点的所有祖先结点的值为:n”）; for（i=1;idata）;return; while（top!=0 & stop.tag=1） top-; if（top!=0） stop.tag=1; bt=stop.t-rchild; int Qiuzu（Node *Head） if （Head
15、=null） return 0; if （Head -data=x） return 1； if（Qiuzu（Head-Lchild）|Qiuzu（Head-Rchild） coutdate p-next=s; 2. （n-1）/2 3. 312 4. 2h-1 5. log2i=log2j6. 深度 7. O（n2） 8. k（k+1）/2 9. log2i+1 10.2 根据完全二叉树的性质，Ai的双亲是Ai/2，双亲的双亲是Ai/2/2，. 同理，Aj的双亲是Aj/2，双亲的双亲是Aj/2/2，. if（i=j） Ai和Aj的最近的共同祖先就是Ai/2;else while（i!=j） if（ij） i=i/2; else j=j/2; Ai和Aj的最近的共同祖先就是Ai;设总结点数为n，度为1和2的结点数分别为n1和n2n=B+1=n0+n1+n2 n1=0 n2=n0-1B=2n0-2（1）in-1-i （2）j=n-1-i （3）rj.key1-51-42-33-45-25-6最早开始时间e最迟开始时间l206-26-36-77-37-47-88-434366249（4）给出其
