2016数据结构B试卷A-1

12015/2016学年第二学期课程代码：12000560课程名称:数据结构B试卷:A■B□考试形式：开卷□、闭卷■考试时间:120分钟…………………………………………………………………………………………………………学号姓名任课教师______专业得分一、选择题(每小题2分，共20分)()1.在单链表中，存储每个结点有两个域，一个是数据域，另一个是指针域，指针域指向该结点的.A．开始结点B.直接前趋C.直接后继D.终端结点()2.设二维数组a[0…m-1][0…n-1]按行优先顺序存储在首地址为loc(a00)的存储区域中，每个元素占d个单元，则aij的地址为________。A．loc(a00)+(i×n+j)×dB.loc(a00)+(j×m+i)×dC.loc(a00)+((j-1)×n+i-1)×dD.loc(a00)+((j-1)×m+i-1)×d()3.在有n个顶点和e条边的无向图的邻接矩阵中元素为1的个数为。A.eB.2eC.n2-eD.n2-2e()4.对线性表进行二分查找时，要求线性表必须是。A．顺序存储B．链式存储C．链式存储且按关键字有序D．顺序存储且按关键字有序()5.线性表的顺序存储结构是一种存储结构。A.随机存取B.顺序存取C.索引存取D.散列存取()6.五节车厢以编号1，2，3，4，5的顺序进入铁路调度站（入栈），可以得到的编组(出栈顺序，出栈可以穿插在入栈的过程中)为。A.3，4，5，1，2B.2，4，1，3，5C.3，5，4，2，1D.1，3，5，2，4()7.队列的删除操作是在。A.队首B.队尾C.队前D.队后2()8.在一个单链表head中，若要在指针p所指结点后插入一个q指针所指结点，则执行。A.p-next=q-next;q-next=p;B.q-next=p-next;p=q;C.p-next=q-next;p-next=q;D.q-next=p-next;p-next=q;()9.若长度为n的线性表(a1,a2,…,an)采用顺序存储，在第i＋1个位置上插入一个新元素，需要依次向后移动个数据元素。A.n-i-1B.n-iC.n+iD.n-i+1()10.无向图的邻接矩阵是一个。A.对称矩阵B.零矩阵C.上三角矩阵D.对角矩阵二、填空题(每个空2分，共16分)三、求解题（共44分）1．已知一棵二叉树的先根序列：ABDGJEHCFIKL；中根序列：DJGBEHACKILF。画出二叉树的形态。(7分)2．画出图1所示树所对应的二叉树，要求有连线，抹线和转向三个步骤（6分）A图1BCDEFGHIKLMJ33．给定如下图所示的无向图G=V,E,其中V={a,b,c,d,e,f},E={(a,b),(a,e),(b,c),(c,e),(e,d),(c,f)}。请画出图G的邻接矩阵,邻接表。从结点a出发,分别写出按深度优先搜索法和广度优先搜索法进行遍历的结点序列。(3＋3＋2＋2=10分)4．分别写出对序列25，23，12，8，3，1，29，5,50,32,18,22,15进行快速排序和冒泡排序的过程。(5＋5=10分)45．从空的二叉排序树开始依次插入30，18,11,17,5,13,41,29,37。画出该二叉排序树并写出中根遍历序列。（4＋2=6分）6.已知一个线性表（38，25，74，63，52，48），采用的散列函数为H(key)=keymod7,将元素散列到表长为7的哈希表中存储。若采用线性探测的开放定址法解决冲突，请将各数据按存储位置填入下表，并计算在该散列表上进行等概率成功查找的平均查找长度为多少？（5分）哈希表：0123456三、读程题（每题3分，共12分）1.画出用A=create(4)调用下列算法后的单链表，写出运行结果。typedefstructlnode{intdata;structlnode*next;}Lnode;Lnode*create(intn){Lnode*head,*p;inti;head=(Lnode*)malloc(sizeof(Lnode));p=head;5for(i=1;i=n;i++){p-next=(Lnode*)malloc(sizeof(Lnode));p=p-next;p-data=2*i;}p-next=NULL;p=head-next;while(p){printf(“%d”,p-data);p=p-next;}returnhead;}单链表为：。运行结果为：。2.voidfunc2（SeqStackS）//SeqStack为栈数据类型,CirQueue为队列数据类型{intk=0；Elemtypey;CirQueueQ；SeqStackT；InitQueue（&Q）；//初始化队列QInitStack（&T）；//初始化栈Twhile（!StackEmpty（&S））//StackEmpty（）是判断栈是否为空的函数{k++;if（k%2!=0）{Pop（&S，&y），Push（&T,y）;}else{Pop（&S，&y），EnQueue（&Q,y）;}}}设栈S=（1,2,3,4,5,6,7）,其中7为栈顶元素。调用函数func2（S）后,栈T中的内容是，队列Q中的内容是。五、读程填空（每个空格2分，共计8分）1.函数实现单链表的插入算法，请在空格处将算法补充完整。intListInsert(LinkListL,inti,ElemTypee){LNode*p,*s;intj;p=L;j=0;while((p!=NULL)&&(ji-1)){p=p-next;j++;}if(p==NULL||ji-1)returnERROR;s=(LNode*)malloc(sizeof(LNode));6s-data=e;(1);(2);returnOK;}/*ListInsert*/2、用二分法实现查找，请补齐空格处的语句。intfunc3(intr[],intn,intk){inti,low=0,high=n-1,mid,find=0;while(low=high&&find==0){mid=(low+high)/2;if(kr[mid])(3);elseif(kr[mid])(4);else｛i＝mid;find=1;｝}if(!find)return-1;returni;}