上海理工大学数据结构期末试卷

整理文档很辛苦,赏杯茶钱您下走!

免费阅读已结束,点击下载阅读编辑剩下 ...

阅读已结束,您可以下载文档离线阅读编辑

资源描述

一、选择题(每题2分共20分)1.若长度为n的线性表(a1,a2,…,an)采用顺序存储,删除它的第i个数据元素,需要依次向前移动个数据元素。A.n-iB.n+iC.n-i+1D.n-i-12.在一个单链表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;3.栈是一种的线性表。A.只允许在一端进行插入和在另一端进行删除B.只允许在一端进行插入和删除C.只允许在两端进行插入和删除D.允许在中间部位进行插入和删除4.算术表达式a×b+c/d的逆波兰式是______。A.ab×cd+/B.ab×c/d+C.ab×cd/+D.ab+×cd/5.循环队列用数组A[0,m-1]存放其元素值,已知其头尾指针分别是front和rear,则当前队列中的元素个数是()。A.(rear-front+m)%mB.read-front+1C.read-front-1D.read-front6.设二维数组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)×d7.对于二叉树来说,第i层上至多有____个结点。A.2iB.2i-1C.2i-1D.2i-1-18.有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当二分查找值为82的结点时,()次比较后查找成功。A.1B.2C.4D.89.设哈希表长m=11,哈希函数H(key)=key%11。表中已有4个结点:addr(15)=4,addr(38)=5,addr(61)=6,addr(84)=7,其余地址为空,如果线性探测再散列处理冲突,关键字为49的结点地址是。A.3B.5C.8D.910.用某种排序方法对线性表(25,84,21,47,15,27,68,35,20)进行排序时,元素序列的变化情况如下:25,84,21,47,15,27,68,35,2015,84,21,47,25,27,68,35,2015,20,21,47,25,27,68,35,8415,20,21,25,47,27,68,35,84..15,20,21,25,27,35,47,68,84则采用的排序方法是()。A.冒泡排序B.快速排序C.归并排序D.选择排序二、求解题1.已知二叉树的扩展前序序列:FKHφφBEφφφGAφφDφCφφ.请画出该二叉树并写出该树的中序和后序序列。(12分)2.画出下列树对应的二叉树。(10分)3.给定无向图G=V,E,其中V={a,b,c,d,e},E={(a,b),(a,e),(b,e),(b,c),(c,e),(e,d)}.请画出图G的邻接矩阵,邻接表。从结点a出发,分别写出按深度优先搜索法和广度优先搜索法进行遍历的结点序列。(12分)4.从空的二叉排序树开始依次插入30,18,11,17,7,5,13,41,29,37,23,19。画出该二叉排序树。(9分)5.分别写出对序列10,18,11,17,7,5,13,41,29,37,23,19,25进行快速排序和冒泡排序的过程。(16分)三、写出下列算法的功能或输出结果1.typedefstructList{intnumber;structList*next;}Node,*Link;voidfunc1(Linkp)//p指向单链表{while(p!=NULL){printf(“%d\n”,p-number);p=p-next;}}功能是。2.写出下列程序段的运行结果(栈中的元素类型是char):main(){SEQSTACKs,*p;charx,y;p=&s;initstack(p);x=‘c’;y=‘k’;push(p,x);push(p,’a′);push(p,y);x=pop(p);push(p,’t′);push(p,’s′);while(!empty(p)){y=pop(p);printf(″%c″,y);}printf(″%c\n″,x);}运行结果是。3.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])high=mid-1;elseif(kr[mid])low=mid+1;else{i=mid;find=1;}}if(!find)return-1;returni;}功能是。四、读程填空1.下列算法创建n个元素的带头单链表.typedefstructlnode{intdata;structlnode*next;}lnode,*linklist;voidcreate(linklist&head,intn){linklistp;inti;head=(linklist)malloc(sizeof(lnode));A;for(i=n;i0;i--){p=(linklist)malloc(sizeof(lnode));scanf(“%d”,&p-data);B;C;}}2.完成下列插入排序算法。typedefstructnode{intkey;intdata;}NODE;voidinsert(NODEr[],intn)//r[0]为哨兵{inti,j;for(i=2;i=n;i++)if(A){r[0]=r[i];j=i-1;while(B)r[j+1]=r[j--];C;}}参考答案一、ADBCAABCCD二、1.F1分KG2分HBAD2分EC1分中序序列:HKEBFAGDC3分后序序列:HEBKACDGF3分2.3.邻接矩阵:0100110101010010000111110邻接表:abcdebÙeaceÙbÙeÙeabcdÙDfs:abced其他:aedcbbfs:abecd其他:aebdc,aebcdBAECFJDIGHKbaecd4,5.快速排序:10,18,11,17,7,5,13,41,29,37,23,19,255,7,10,17,11,18,13,41,29,37,23,19,255,7,10,13,11,17,18,41,29,37,23,19,255,7,10,11,13,17,18,41,29,37,23,19,255,7,10,11,13,17,18,25,29,37,23,19,415,7,10,11,13,17,18,19,23,25,37,29,415,7,10,11,13,17,18,19,23,25,29,37,41冒泡排序:10,18,11,17,7,5,13,41,29,37,23,19,25i=1:10,11,17,7,5,13,18,29,37,23,19,25,41i=2:10,11,7,5,13,17,18,29,23,19,25,37i=3:10,7,5,11,13,17,18,23,19,25,29i=4:7,5,10,11,13,17,18,19,23,25i=5:5,7,10,11,13,17,18,19,23三、1.打印p所指的无头单链表2.stack3.用二分查找方法在r数组中查找k四、1.A:head-next=NULLB:p-next=head-nextC:head-next=p2.A:r[i].keyr[i-1].keyB:r[0].keyr[j].keyC:r[j+1]=r[0]1321175112143

1 / 7
下载文档,编辑使用

©2015-2020 m.777doc.com 三七文档.

备案号:鲁ICP备2024069028号-1 客服联系 QQ:2149211541

×
保存成功