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

《上海理工大学数据结构期末试卷.pdf》由会员分享，可在线阅读，更多相关《上海理工大学数据结构期末试卷.pdf（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、一一、选选择择题题（每每题题2 2分分共共2 20 0分分）1若长度为 n 的线性表(a1,a2,an)采用顺序存储，删除它的第 i 个数据元素，需要依次向前移动个数据元素。A.n-i B.n+i C.n-i+1 D.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算术表达式 ab+c/d 的逆波兰式是_。A.abcd+/B.abc/d+C.abcd/+D.ab+cd/5循环队列用数组 A0，m-1存放其元素值，已知其头尾指针分别是front 和 rear，则当前队列中的元素个数是（）。A(rear-front+m)%mBread-front+1Cread-front-1 Dread-front6 设二维数组 a0m-10n-1按行优先顺序存储在首地址为loc(a00)的存储区域中，每个元素占 d 个单元，则 aij的地址为_。A.loc(a00)+(in+j)d B.loc(a00)+(jm

3、+i)dC.loc(a00)+(j-1)n+i-1)d D.loc(a00)+(j-1)m+i-1)d7对于二叉树来说,第 i 层上至多有_个结点。ii-1ii-1 A2 B 2 C2-1 D2-18 有一个有序表为1,3,9,12,32,41,45,62,75,77,82,95,100，当二分查找值为 82 的结点时，（）次比较后查找成功。A1 B2 C4 D89设哈希表长 m=11，哈希函数 H（key）=key%11。表中已有 4 个结点：addr（15）=4，addr（38）=5，addr（61）=6，addr（84）=7，其余地址为空，如果线性探测再散列处理冲突，关键字为 49 的结

4、点地址是。A3 B5 C8 D910用某种排序方法对线性表（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,8415,20,21,25,27,35,47,68,84则采用的排序方法是（）。A冒泡排序 B快速排序 C归并排序 D选择排序二、求解题二、求解题1已知二叉树的扩展前序序列：FKHBEGADC.请画出该二叉树并写出该树的中序和后序序列。（12 分

5、）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,23,19,25 进行快速排序和冒泡排序的过程。(16 分)三、写出下列算法的功能或输出结果三、写出下列算法的

6、功能或输出结果1.typedef struct List int number;struct List*next;Node，*Link;void func1(Link p)/p指向单链表 while(p!=NULL)printf(“%dn”,p-number);p=p-next;功能是。2.写出下列程序段的运行结果（栈中的元素类型是char）：main()SEQSTACK s,*p;char x,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(

7、p)y=pop(p);printf(%c,y);printf(%cn,x);运行结果是。3int func3(int r,int n,int k)int i,low=0,high=n-1,mid,find=0;while(low=high&find=0)mid=(low+high)/2;if(krmid)low=mid+1;elseimid;find=1;if(!find)return-1;return i;功能是。四、读程填空四、读程填空1下列算法创建 n 个元素的带头单链表.typedef struct lnode int data;struct lnode*next;lnode,*lin

8、klist;void create(linklist&head,int n)linklist p;int i;head=(linklist)malloc(sizeof(lnode);A ;for(i=n;i0;i-)p=(linklist)malloc(sizeof(lnode);scanf(“%d”,&p-data);B ;C ;2完成下列插入排序算法。typedef struct nodeint key;int data;NODE;void insert(NODE r,int n)/r0为哨兵int i,j;for(i=2;inext=NULL B:p-next=head-next C:head-next=p 2.A:ri.keyri-1.key B:r0.keyrj.key C:rj+1=r0