《数据结构》-总复习提要

考试题型及分值分配,判断题（每小题1分，共10分） 单选题（每小题1分，共10分） 填空题（每小题2分，共20分） 程序阅读填空（每小题6分，共24分） 简答题（每小题6分，共24分） 算法编程（共12分),一. 选择题,1. 设单链表中结点的结构为(data, link)。 已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s,则应执行下列哪一个操作（ ）。 As-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的直接后继，则应执行下列哪一个操作（ ）。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. 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. 连通分量是无向图中的极小连通子图。,四、程序阅读填空,五、简答题,线性表可用顺序表或是链表存储，此两种存储表示各有哪些优缺点？ 设有一个输入数据的序列是 ，试画出