1、单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,考试题型及分值分配,判断题（每小题1分，共10分）,单选题（每小题1分，共10分）,填空题（每小题,2,分，共,20,分）,程序阅读填空（每小题6分，共,24,分）,简答题（每小题,6,分，共,24,分）,算法编程（共1,2,分),一.选择题,1.,设单链表中结点的结构为(,data,link)。,已知指针,q,所指结点是指针,p,所指结点的直接前驱，若在*,q,与*,p,之间插入结点*,s,则应执行下列哪一个操作（）。,As-link=p-link;p-link=s;B.q-link=s;s-link=p
2、C.p-link=s-link;s-link=q;D.p-link=s;s-link=q;,2.,设单链表中结点的结构为(,data,link)。,若想摘除结点*,p,的直接后继，则应执行下列哪一个操作（）。,Ap-link=p-link-link;B.p=p-link;p-link=p-link-link,C.p-link=p-link;D.p=p-link-link;,3.,折半搜索与二叉搜索树（即二叉排序树）的时间性能（）。,A,相同,B.,完全不同,C.,有时不相同,D.,不确定,4,采用折半搜索算法搜索长度为,n,的有序表时，元素的平均搜索长度为（）。,AO(nlog2n)B.,
3、O(n,)C.O(log2n)D.,O(n,),5,采用邻接表存储的图的广度优先遍历算法类似于二叉树的（）。,A,中序遍历,B.,前序遍历,C.,后序遍历,D.,按层次遍,二.填空题,1.算法是一个有穷的指令集，它为解决某一特定任务规定了一个运算序列。它应具有输入、输出、_、有穷性和可执行性等特性。,2.,在一个堆的顺序存储中，若一个结点的下标为,i，,则它的左子女结点的下标为_，右子女结点的下标为_。,3.,请指出在顺序表2、5、7、10、14、15、18、23、35、41、52中，用折半查找关键码12需做_次关键码比较。,4.,设有两个串,p,和,q，,求,q,在,p,中首次出现的位置的运
4、算称作_。,5.,判定一个循环队列,QU(,最多元素为,m),为满队列的条件是_。,6.,在直接选择排序中，记录比较次数的时间复杂度为_，记录移动次数的时间复杂度为_。,7,快速排序在平均情况下的空间复杂度为_，在最坏情况下的空间复杂度为_。,三、判断题,（）1.直接选择排序是一种不稳定的排序方法。,（）2.折半搜索只适用于有序表，包括有序的顺序表和有序的链表。,（）,3.,数据结构是指相互之间存在一种或多种关系的数据元素的全体。,（）,4.,若有一个叶子结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点。,（）,5.,若有一个叶子结点是二
5、叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点。,（）,6.,任一棵二叉搜索树的平均搜索时间都小于用顺序搜索法搜索同样结点的顺序表的平均搜索时间。,（）,7.,对于同一组待输入的关键码集合，虽然各关键码的输入次序不同，但得到的二叉搜索树都是相同的。,（）,8.,在二叉搜索树上插入新结点时，不必移动其它结点，仅需改动某个结点的指针，使它由空变为非空即可。,（）,9.,连通分量是无向图中的极小连通子图。,四、程序阅读填空,五、简答题,线性表可用顺序表或是链表存储，此两种存储表示各有哪些优缺点？,设有一个输入数据的序列是,，试画出从空树起，逐个输入各个数据而生成的二叉排序树。,六、算法编程,用递归求已知数组中的最大值，平均值；,2.,编写单链表类的删除成员函数；数组元素逆置等。,
浙ICP备2021020529号-1 | 浙B2-20240490 
