南昌大学2008～2009学年第二学期数据结构期末考试评分标准c

《南昌大学2008～2009学年第二学期数据结构期末考试评分标准c》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、南昌大学2008～2009学年第二学期期末考试试卷试卷编号：(C)卷课程编号：H61030006课程名称：数据结构考试形式：闭卷适用班级：计算机系07级姓名：学号：班级：学院：信息工程学院专业：计算机科学与技术考试日期：题号一二三四五六七八九十总分累分人签名题分30202030100得分考生注意事项：1、本试卷共7页，请查看试卷中是否有缺页或破损。如有立即举手报告以便更换。2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。一、填空题(每空2分，共30分)得分评阅人1.若要在一个单链表的*p结点之前插入一个*s结点，可执行以下操作：s->next=p->next；p->n

2、ext=s;t=p->date;p->data=s->data;s->data=t。2.在计算机软件系统中，有两种处理字符长度的方法，一种是固定长度，第二种是长度指针。3.假定对线性表R[059]进行分块检索，共分10块，每块长度等于6。若假定检索索引和块均用顺序检索的方法，则检索每个元素的平均检索时间为9。4.一组记录（50,40,95,20,15,70,60,45,80）进行冒泡排序时，第一趟需进行相邻记录的交换次数为6，在整个排序过程中共需进行7趟才可完成。5.在堆排序、快速排序和归并排序中，若从节省存储空间角度考虑，应首先选取堆排序方法，其次选快速排序方法，最后选择归

3、并排序方法；若从排序结构的稳定性角度考虑，应选取归并排序方法；若从平均情况下排序的速度来考虑，则选择快速排序方法；若从最坏情况下排序最快并且要节省内存角度考虑，则应该取堆排序方法。6、一个算法，如果不管问题规模大小，运行所需时间都是一样，则该算法的时间复杂度是O(1)。第6页共6页一、判断题（每题1分，共20分，对的打√，错的打×）得分评阅人1.具有线性关系集合中，若a,b是集合中的任意两个元素，则必定有a

4、是一棵平衡树。（×）5.即使某排序算法是不稳定的，但该方法仍可能有实际应用价值。（√）6.连通分量是无向图中的极小连通子图。（×）7.先序遍历一棵二叉搜索树所的结点访问序列不可能是键值递增序列。（×）8.不管adt栈是用数组实现，还是用指针实现，Pop(s)与Push(x,s)的耗时均为O(n)。（×）9.表中的每一个元素都有一个前驱元素和一个后继元素。（×）10.作为解决一类特定问题的算法，不能没有输入运算项。（×）11.数据元素是数据的最小单元。（×）12.在单链表中任何两个元素的存储位置之间都有固定的联系，因此可以从头结点进行查找任何一个元素。（×）13.设有两个串p和

5、q，其中q是p的子串，把q在p中首次出现的位置作为q在p中的位置的算法称为匹配。（√）14.若有一个叶子结点是某子树的中序遍历的最后一个结点，则它必是该子树的先序遍历的最后一个结点。（×）15.对于n个记录的集合进行冒泡排序，在最坏的情况下的时间复杂度是O(n2)。（√）16.用相邻矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中结点的个数有关，而与图的边数无关。（√）17.哈希表的查找效率主要取决于哈希建表时所选取的哈希函数和处理冲突的方法。（×）18.因为算法和程序没有区别，所以在数据结构中二者是通用的。（×）19.按中序遍历一棵二叉排序树所得的中

6、序遍历序列是一个递增序列。（√）20.进栈操作push(x,s)作用于链接栈时，无须判满。（×）第6页共6页一、解答题（共20分）得分评阅人1、已知一棵二叉树的中序遍历结果为DBHEAFICG，后序遍历结果为DHEBIFGCA，画出该二叉树。（10分）解答：2．设哈希表的地址空间为0..16，开始时哈希表为空，用线性探测再散列法处理冲突，对于数据元素Jan，Feb，Mar,Jun，Aug，Sep，Oct，Nev，Dev，试构造其对应的散列表，H(key)=i/2,其中i为关键字第一个字母在字母表中的序号。（10分）解答：依题意m=17，线性探测开放地址法下一地址计算公式为：d

7、1=H(key)dj+1=(dj+1)%m;j=1,2,…..其计算函数如下：H(Jan)=10/2=5;H(Feb)=6/2=3H(Mar)=13/2=6H(Jun)=10/2=5冲突H(Jun)=(5+1)%17=6仍冲突H(Jun)=(6+1)%17=7H(Aug)=1/2=0H(Sep)=19/2=9H(Oct)=15/2=7冲突H(Oct)=(7+1)%17=8H(Nev)=14/2=7冲突H(Nev)=(7+1)%17=8仍冲突H(Nev)=(8+1)%17=9仍冲突H(Nev)=(9+1)