《数据结构与算法》复习题A（专升本）

数据结构与算法复习题A（专升本） 一、填空题1、 数据结构被形式地定义为（ D, R），其中D 是 的有限集合， R 是D 上的 有限集合。2、 数据结构包括数据的 、数据的 和数据的 这三个方面的内容。3、 写出带头结点的双向循环链表L 为空表的条件 。4、 在具有n个元素的循环队列中，队满时具有 个元素。5、 求子串在主串中首次出现的位置的运算称为 。 6、 由3个结点所构成的二叉树有 种形态。7、 数据的逻辑结构是指 。二、 选择题1、若某线性表中最常用的操作是取第i 个元素和找第i个元素的前驱，则采用（ ）存储方法最节省时间。A.顺序表 B.单链表 C.双链表 D.单循环链表2、二叉树的前序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树。A.空或只有一个结点 B.高度等于其结点数 C.任一结点无左孩子 D.任一结点无右孩子3、计算机算法指的是：（ ）A. 计算方法 B. 排序方法C. 解决问题的有限运算序列D. 调度方法4、栈和队列的主要区别在于（ ）。A.它们的逻辑结构不一样 B.它们的存储结构不一样 C.所包含的运算不一样 D.插入删除运算的限定不一样5、为5个使用频率不等的字符设计哈弗曼编码，不可能的方案是（ ）。A.000,001,010,011,1 B. 0000,0001,001,01,1 C.000,001,01,10,11 D.00,100,101,110,1116、用深度优先遍历方法遍历一个有向无环图，并在深度优先遍历算法中按退栈次序打印出相应的顶点，则输出的顶点序列是（ ）。A.逆拓扑有序 B.拓扑有序 C.无序 D.顶点编号次序7、对如图所示的无向连通网图从顶点d开始用Prim算法构造最小生成树，在构造过程中加入最小生成树的前4条边依次是（ ）。 A. （d,f）4, (f,e) 2 , (f,b) 3 (b,a) 5 B. （f,e）2, (f,b) 3 , (a,c) 3 (f,d) 4C. （d,f）4, (f,e) 2 , (a,c) 3 (b,a) 5D. （d,f）4, (d,b) 5 , (f,e) 2 (b,a) 58、在采用线性探测法处理冲突所构成的闭散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置的键值（ ）。A.一定都是同义词 B.一定都不是同义词 C.不一定都是同义词 D.都相同9、二叉排序树中，最小值结点的（ ）。A左指针一定为空 B右指针一定为空 C左右指针均为空 D左右指针均不为空10、数据序列8，9，10，4，5，6，20，1，2只能是（ ）的两趟排序后的结果。A.选择排序 B.冒泡排序 C.插入排序 D.堆排序三、判断题1、线性表的逻辑顺序总是与其物理顺序一致。（  ）2、当待排序序列初始有序时，简单选择排序的时间复杂性为O(n)。（   ）3、对稀疏矩阵进行压缩存储是为了节省存储空间。（ ）4、边数很少的稀疏图，适宜用邻接矩阵表示。（   ）5、二叉树是一棵无序树。(  ) 6、对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O(n)。(  ) 7、当待排序序列初始有序时，快速排序的时间复杂性为O(n)。（    ）8、顺序表的空间利用率高于链表。（  ）9、哈希查找法中解决冲突问题的常用方法是除留余数法。（    ）10、顺序查找法适用于存储结构为顺序或链接存储的线性表。（    ） 四、名词解释1、数据：2、存储结构分为：3、算法的五个重要特性：4、 栈：5、 完全二叉树：五、简答题1、由二叉树的中序序列及前序序列能唯一的建立二叉树，试问前序序列及后序序列是否也能唯一的建立二叉树，不能则举例说明理由。2、关键码集合 47, 7, 29, 11, 16, 92, 22, 8, 3，散列函数为H(key)=key mod 11，用拉链法处理冲突，构造开散列表，并求查找成功时的平均查找长度。3. 已知数据序列为（12，5，9，20，6，31，24），对该数据序列进行排序，写出简单选择排序以及快速排序每趟的结果。4、程序分析填空题（1）函数GetElem 实现返回单链表的第i 个元素，请在空格处将算法补充完整。int GetElem(LinkList L,int i,Elemtype *e)LinkList p ;int j;p=L->next;j=1;while(p&&j<i)(1) ;+j; if(!p|j>i) return ERROR;*e= (2) ; return OK;（2）、函数实现单链表的插入算法，请在空格处将算法补充完整。int ListInsert(LinkList L,int i,ElemType e)LNode *p,*s; int j;p=L;j=0;while(p!=NULL)&&(j<i-1) p=p->next;j+;if(p=NULL|j>i-1) return ERROR;s=(LNode *)malloc(sizeof(LNode);s->data=e;(1) ;(2) ;return OK;/*ListInsert*/数据结构与算法复习题B（专升本）一、填空题1、数据结构按逻辑结构可分为两大类，它们分别是 和 。2、线性结构中元素之间存在 关系，树形结构中元素之间存在 关系，图形结构中元素之间存在多对多关系。3、带头结点的单链表head 为空的条件是 。4、两个串相等的充分必要条件是两个串的长度相等且 。5、二维数组，可以按照 和 两种不同的存储方式。6、一棵具有257个结点的完全二叉树，它的深度为 。7、内部排序方法按排序采用的策略可划分为五类： 、 、 、 和基数排序。二、选择题1、计算机算法必须具备输入、输出和（ ）等5 个特性。A. 可行性、可移植性和可扩充性B.可行性、确定性和有穷性C. 确定性、有穷性和稳定性D. 易读性、稳定性和安全性2、串与普通的线性表相比较，它的特殊性体现在（ ）。A. 顺序的存储结构B. 链式存储结构C. 数据元素是一个字符D. 数据元素任意3、以下与数据的存储结构无关的术语是（  ）。A循环队列     B. 链表     C. 哈希表      D.  栈4、以下属于逻辑结构的是（    ）。A顺序表     B. 哈希表     C.有序表     D.单链表5、将一棵有100 个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49 的结点的左孩子编号为（ ）。A. 98 B. 99 C. 50 D. 486、已知关键码序列78，19，63，30，89，84，55，69，28，83采用基数排序，第一趟排序后的关键码序列为（）A. 19，28，30，55，63，69，78，83，84，89B. 28，78，19，69，89，63，83，30，84，55C. 30，63，83，84，55，78，28，19，89，69D. 30，63，83，84，55，28，78，19，69，897、在一个长度为n 的顺序表中，在第i 个元素之前插入一个新元素时，需向后移动（ ）个元素。A. n-i B. n-i+1 C. n-i-1 D. i8、空串和空格串（ ）。A. 相同 B. 不相同 C. 可能相同 D. 无法确定9、常对数组进行两种基本操作是（ ）。A. 建立和删除 B. 索引和修改 C. 查找和修改 D. 查找与索引10、二叉树的深度为k ，则二叉树最多有（ ）个结点。A. 2k B. 2 k-1 C. 2 k-1 D. 2k-1三、判断题1、 线性表的顺序存储优于链式存储。（  ） 2、用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数有关，而与图的边数无关。 (  )3、当向一个最小堆插入一个具有最小值的元素时，该元素需要逐层向上调整，直到被调整到堆顶位置为止。（ ）4、采用不同的遍历方法，所得到的无向图的生成树是不同的。（  ） 5、有回路的有向图不能完成拓扑排序。(  ) 6、若让元素1,2,3依次进栈，则出栈次序1,3,2是不可能出现的情况。（  ）7、在线性链表中删除中间的结点时，只需将被删结点释放。（  ）8、线性表若采用链式存储表示, 在删除时不需要移动元素。（  ）9、采用不同的遍历方法，所得到的无向图的生成树总是相同的。（   ）10、递归的算法简单、易懂、容易编写，而且执行效率也高。（  ）四、名词解释1、算法：2、队列：3、满二叉树：4、 连通图：5、数据项：五、简答题1、已知一棵度为m的树中有：n1个度为1的结点，n2个度为2的结点，nm个度为m的结点，问该树中共有多少个叶子结点？2、 已知一个AOV网如图所示，写出所有的拓扑序列。3、已知数据序列为(12,5,9,20,6,31,24)，对该数据序列进行排序，写出直接插入排序、堆排序每趟的结果。4、程序分析填空题（1）、函数ListDelete_sq 实现顺序表删除算法，请在空格处将算法补充完整。int ListDelete_sq(Sqlist *L,int i)int k;if(i<1|i>L->length) return ERROR;for(k=i-1;k<L->length-1;k+)L->slistk= （1） ;（2） ;return OK;（2）函数实现单链表的删除算法，请在空格处将算法补充完整。int ListDelete(LinkList L,int i,Elem