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

《《数据结构与算法》复习题A（专升本）.doc》由会员分享，可在线阅读，更多相关《《数据结构与算法》复习题A（专升本）.doc（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构与算法复习题A（专升本） 一、填空题1、 数据结构被形式地定义为（ D, R），其中D 是 的有限集合， R 是D 上的 有限集合。2、 数据结构包括数据的 、数据的 和数据的 这三个方面的内容。3、 写出带头结点的双向循环链表L 为空表的条件 。4、 在具有n个元素的循环队列中，队满时具有 个元素。5、 求子串在主串中首次出现的位置的运算称为 。 6、 由3个结点所构成的二叉树有 种形态。7、 数据的逻辑结构是指 。二、 选择题1、若某线性表中最常用的操作是取第i 个元素和找第i个元素的前驱，则采用（ ）存储方法最节省时间。A.顺序表 B.单链表 C.双链表 D.单循环链表2、二叉树

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,

3、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) 5

4、8、在采用线性探测法处理冲突所构成的闭散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置的键值（ ）。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、对稀疏矩阵进行压缩存储是为

5、了节省存储空间。（ ）4、边数很少的稀疏图，适宜用邻接矩阵表示。（）5、二叉树是一棵无序树。()6、对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O(n)。()7、当待排序序列初始有序时，快速排序的时间复杂性为O(n)。（）8、顺序表的空间利用率高于链表。（）9、哈希查找法中解决冲突问题的常用方法是除留余数法。（）10、顺序查找法适用于存储结构为顺序或链接存储的线性表。（）四、名词解释1、数据：2、存储结构分为：3、算法的五个重要特性：4、 栈：5、 完全二叉树：五、简答题1、由二叉树的中序序列及前序序列能唯一的建立二叉树，试问前序序列及后序序列是否也能唯一的建立二

6、叉树，不能则举例说明理由。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&ji

7、) 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)&(jnext;j+;if(p=NULL|ji-1) return ERROR;s=(LNode *)malloc(sizeof(LNode);s-data=e;(1) ;(2) ;return OK;/*ListInsert*/数据结构与算法复习题B（专升本）一、填空题1、数据结构按逻辑结构可分为两

8、大类，它们分别是 和 。2、线性结构中元素之间存在 关系，树形结构中元素之间存在 关系，图形结构中元素之间存在多对多关系。3、带头结点的单链表head 为空的条件是 。4、两个串相等的充分必要条件是两个串的长度相等且 。5、二维数组，可以按照 和 两种不同的存储方式。6、一棵具有257个结点的完全二叉树，它的深度为 。7、内部排序方法按排序采用的策略可划分为五类： 、 、 、 和基数排序。二、选择题1、计算机算法必须具备输入、输出和（ ）等5 个特性。A. 可行性、可移植性和可扩充性B.可行性、确定性和有穷性C. 确定性、有穷性和稳定性D. 易读性、稳定性和安全性2、串与普通的线性表相比较，它

9、的特殊性体现在（ ）。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，

10、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 ，则二叉树最多有（

11、 ）个结点。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、线性表若采用链式

12、存储表示,在删除时不需要移动元素。（）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 实现顺序表删除算

13、法，请在空格处将算法补充完整。int ListDelete_sq(Sqlist *L,int i)int k;if(iL-length) return ERROR;for(k=i-1;klength-1;k+)L-slistk= （1） ;（2） ;return OK;（2）函数实现单链表的删除算法，请在空格处将算法补充完整。int ListDelete(LinkList L,int i,ElemType *s)LNode *p,*q;int j;p=L;j=0;while( （1） )&(jnext;j+;if(p-next=NULL|ji-1) return ERROR;q=p-next;（2） ;*s=q-data;free(q);return OK;/*listDelete*/