福建师范《数据结构概论》作业答案

福建师范大学试卷纸第1页共7页福建师范大学试卷纸第1页共7页福建师范大学试卷纸第1页共7页福建师范大学试卷纸第1页共7页数据结构概论期末考核试卷一、单项选择题（每小题2分，共30分）.下列编码中属前缀码的是（A）A.{1,01,000,001}B.{1,01,011,010}C.{0,10,110,11}D.{0,1,00,11}.设栈S和队列Q的初始状态为空，元素a,b,c,d,e,f依次进栈，一个元素退栈后即进入队列Q，若6个元素的出队的序列是b,d,c,f,e,a，则栈S的容量至少应当是（C）A.6B.4C.3D.2.在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是（B）A.O⑴B.O（n）C.O（nlogn）D.O（n2）.要表示省，市，区，街道的有关数据及其关系，选择（D）比较合适。A.线性结构B.树结构C.图结构D.集合结构.链栈与顺序栈相比，比较明显的优点是（D）A.插入操作更加方便B.删除操作更加方便C.不会出现下溢的情况D.不会出现上溢的情况.二叉树中第5层上的结点个数最多为（C）A.8B.15C.16D.32.在表长为n的链表中进行线性查找，查找成功时，它的平均查找长度为（B）A.ASL;nB.ASL=（n+1）/2C.ASL="n+1D.ASL心log2（n+1）-1.对22个记录的有序表进行折半查找，当查找失败时，至少需要比较（C）次关键字。A.3B.4C.5D.6.已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是（A）福建师范大学试卷纸第福建师范大学试卷纸第页共7页该二叉狗是af\bd/Ice/\f9h先序遍历是：abcdefgh5.已知闭散列表的长度为10(散列地址空间为0..9),散列函数为H(K)=K%8,采用线性重新散列技术解决冲突，将下列一组数据｛25,17,39,47,83,55,99,34｝依次插入到散列表中，请画出散列表。TOC\o"1-5"\h\z⑴H(25)=1H(16)=0⑶H(38)=6H(47)=7H(79)=7与(4)冲突，于是线性重新散列即查找7后面的空槽，此时8为空，因此将79放入(第九个位置)中H(82)=2H(51)=3H(39)=7与(4)冲突，于是线性重新散列即查找7后面的空槽，此时8已经有元素(5),9为空，因此将39放入9(第十个位置)中,所以最终闭散列表的存储情况如下所示：位置：(0)(1)(2)(3)(4)(5)(6)(7)(8)(9)值：16258251空空38477939。四、算法阅读、设计(共5分)1阅读下列函数algo,并回答问题：(5分)voidalgo(Queue*Q)｛StackS;InitStack(&S);while(!QueueEmpty(Q))Push(&S,DeQueue(Q));while(!StackEmpty(&S))EnQueue(Q,Pop(&S));}⑴假设队列q中的元素为(2,4,5,7,8)，其中“2”为队头元素。写出执行函数调用algo(&q)后的队列q；(2)简述算法algo的功能。答：(1)87542(2)队列倒置五、程序设计题(共10分)1、已知r□为一维数组，其中r[0]到r[n-1]为待排序的n个元素，排序好的元素仍放在r[0]到r[n-1]中，请写出对该数组进行非递归的直接插入排序算法，取名为insertsort(elemtyper[],intn)。(10分)voidTii5t?rtSort^tliJintj,p&r