搜索
一、应用题（共8小题，共60分）1、根据栈的特性，如果进栈序列为ABCDEF，能否得到EFCDBA和CDEFBA的出栈序列，如果不能得到请说明原因，如果可以得到请写出入栈、出栈的过程。（8分）2、什么是二叉树的遍历？已知一棵二叉树如下图所示，请写出它的先序序列、中序序列和后序序列。（8分）3、设链表中结点的结构为typedefstructnode{ElemTypedata；//数据structnode*next;//结点后继指针}ListNode；已知ListNode类型指针p所指结点不是尾结点也不是头结点，若在p所指结点之后插入一新结点s，（如下图所示），请写出主要的操作语句。（8分）4、有一组数值{5，29，7，8，14，23，3，11}，画出哈夫曼树。（8分）5、已知森林如下图，请根据孩子兄弟法画出转换的二叉树。（8分）6、已知，用一维数组描述的静态线性链表如下图所示。现要求(1)在a2后插入a6后，画出静态链表表示。（4分）（2）再删除a4，画出该结果的静态链表表示。（4分）datacur011a122a233a344a455a5-17、已知一组键值序列为(41，66，73，52，40，37，65，43)，试采用起泡排序法对该组序列作升序排序，并给出每一趟的排序结果。（8分）8、设数组a[1…60,1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址是多少？（写出分析计算过程）（4分）二、简答题（本题4小题，共20分）1、简述队列的特点。（4分）2、假设按列下标优先存储整数数组A9*3时，第一个元素的字节地址是100，每个整数占四个字节，问a21元素的存储地址是什么？稀疏矩阵常采用的压缩方法是什么？（6分）3、简述线性表的顺序存储结构和链式存储结构的特点分别是什么？（4分）4、具有3个结点的二叉树可能有几种不同形态？请画图表示（6分）三、算法设计题（本题2小题，每题10分，共20分）1、用数组建立班级学生信息表。每个学生的信息包括姓名和学号两部分。班级人数10人。要求：（1）编写“建链”函数。建立学生信息表（2）编写“删除”函数。删除任意一个同学。2、写一个数值转换程序。（十进制转换为八进制）一、应用题（本题60分，共8小题）1、进栈序列为ABCDEF，得不到EFCDBA出栈序列，因为如果E在CD之前出栈，那么CD必然都已入栈，并且C先入栈，然后D入栈，根据栈特性，先入后出，因此D必然在C之前出栈。而EFCDBA中C在D之前，显然不符合栈特性。进栈序列为ABCDEF，可以得到CDEFBA的出栈序列，操作序列为：push(A)；push(B)；push(C)；pop(C)；push(D)；pop(D)；push(E);pop(E)；push(F);pop(F)；pop(B)；pop(A)；评分标准：答案正确并给出解释原因给8分；仅答案正确，没有解释原因或解释错误给4分；答案不正确0分；2、二叉树的特点是每个结点至多只有两棵子树，并且子树有左右之分，次序不能任意颠倒。先序序列：ABDEGCF中序序列：DBEGAFC后序序列：DGEBFCA评分标准：答案正确给8分。二叉树的特点解释正确得2分，每个序列各正确2分3、1)S-next=P-next;2)P-next=S;4、5、6、在a2后插入a6（4分）datacur011a122a263a344a455a5-16a63删除a4（4分）datacur011a121538781119234210015142929582a263a354a455a5-16a637、（初始序列2分，每一趟正确1分，共8分）41，66，73，52，40，37，65，43初始序列41，66，52，40，37，65，43，70第一趟41，52，40，37，65，43，66第二趟41，40，37，52，43，65第三趟40，37，41，43，52第四趟37，40，41，43第五趟37，40，41第六趟8、答：利用列优先通式：LOC(aij)=LOC(a1，1)+[(j-1)*m+（i-1)]*L得：LOC(a32,58)=2048+(58-1)*(60-1+1)+(32-1)]*2＝8950（4分）二、简答题1、答：队列的特点是先进的元素先出。（4分）2、答：a21的存储地址是120，稀疏矩阵常采用的压缩方法为三元组法。（每问3分。共6分。）3、线性表的顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。线性表的链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。（每问2分，共4分）4、共有五种形态。（1分）（每种形态正确得1分）三、算法设计题：1、参考答案(10分)//用数组建立班级学生信息表，初始人数10人。手动输入。完成删除操作。#includeiostream.hstructstudent{//定义结构体intnum;charname[20];};studentstu[10];//定义结构体数组inti;//定义各个全局变量intn=10;intj;voidinput(void)//定义“输入”函数{for(i=0;in;i++){cout输入第i+1个同学的学号和姓名：endl;cinstu[i].numstu[i].name;}};voidoutput(void)//定义“输出”函数{for(i=0;in;i++)cout学号：stu[i].num姓名:stu[i].nameendl;};voiddel(void)//定义“删除同学”函数{cout请输入要删除同学的位置编号：endl;cini;i=i-1;for(j=i;jn;j++)stu[j]=stu[j+1];n--;output();}voidmain()//主函数{input();output();del();};2、参考答案(10分)voidchange(inta)//十进制转换为八进制{inti=0;intyushu[100];intlength=0;printf(十进制数%d转换为8进制:\n,a);while(a!=0){yushu[length]=a%b;printf(yushu[%d]is%d\n,length,yushu[length]);length=length+1;a=a/8;}printf(8进制数是:);for(i=length-1;i=0;i--){printf(%d,yushu[i]);}printf(\n);}voidmain(void){inta;intb;printf(输入一个十进制整数:);scanf(%d,&a);change(a,8);printf(\n);}