考试题型及分值分配壹.判断题（每小题1分，共10分）贰.单选题（每小题1分，共10分）叁.填空题（每小题2分，共20分）.肆程序阅读填空（每小题6分，共24分）.伍简答题（每小题6分，共24分）.陆算法编程（共12分)一.选择题1.设单链表中结点的结构为(data,link)。已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s,则应执行下列哪一个操作（）。A．s->link=p->link;p->link=s;B.q->link=s;s->link=p;C.p->link=s->link;s->link=q;D.p->link=s;s->link=q;2.设单链表中结点的结构为(data,link)。若想摘除结点*p的直接后继，则应执行下列哪一个操作（）。A．p->link=p->link->link;B.p=p->link;p->link=p->link->linkC.p->link=p->link;D.p=p->link->link;3.折半搜索与二叉搜索树（即二叉排序树）的时间性能（）。A．相同B.完全不同C.有时不相同D.不确定4．采用折半搜索算法搜索长度为n的有序表时，元素的平均搜索长度为（）。A．O(nlog2n)B.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中首次出现的位置的运算称作_____________。5.判定一个循环队列QU(最多元素为m)为满队列的条件是_____。6.在直接选择排序中，记录比较次数的时间复杂度为___________，记录移动次数的时间复杂度为___________。7．快速排序在平均情况下的空间复杂度为___________，在最坏情况下的空间复杂度为___________。三、判断题（）1.直接选择排序是一种不稳定的排序方法。（）2.折半搜索只适用于有序表，包括有序的顺序表和有序的链表。（）3.数据结构是指相互之间存在一种或多种关系的数据元素的全体。（）4.若有一个叶子结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点。（）5.若有一个叶子结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点。（）6.任一棵二叉搜索树的平均搜索时间都小于用顺序搜索法搜索同样结点的顺序表的平均搜索时间。（）7.对于同一组待输入的关键码集合，虽然各关键码的输入次序不同，但得到的二叉搜索树都是相同的。（）8.在二叉搜索树上插入新结点时，不必移动其它结点，仅需改动某个结点的指针，使它由空变为非空即可。（）9.连通分量是无向图中的极小连通子图。四、程序阅读填空五、简答题1.线性表可用顺序表或是链表存储，此两种存储表示各有哪些优缺点？2.设有一个输入数据的序列是{·····················}，试画出从空树起，逐个输入各个数据而生成的二叉排序树。六、算法编程1.用递归求已知数组中的最大值，平均值；2.编写单链表类的删除成员函数；数组元素逆置等。
