资源描述：
《上海理工大学数据结构期末试卷》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、一、选择题（每题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.
2、只允许在两端进行插入和删除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
3、)+(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
4、）=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．已知二叉树的扩展前序序
5、列：FKHφφBEφφφGAφφDφCφφ.请画出该二叉树并写出该树的中序和后序序列。（12分）2．画出下列树对应的二叉树。（10分）3.给定无向图G=,其中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,2
6、3,19,25进行快速排序和冒泡排序的过程。(16分)三、写出下列算法的功能或输出结果1.typedefstructList{intnumber;structList*next;}Node，*Link;voidfunc1(Linkp)//p指向单链表{while(p!=NULL){printf(“%d”,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
7、(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(k
