数据结构与算法复习题(专升本).docx

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

1、数据结构与算法复习题（专升本）一、填空题1、数据结构被形式地定义为（D, R）,其中D是 的有限集合，R是D上的 有限集合。2、数据结构包括数据的、数据的 和数据的 这三个方面的内容。3、写出带头结点的双向循环链表L为空表的条件。4、在具有n个元素的循环队列中，队满时具有 个元素。5、求子串在主串中首次浮现的位置的运算称为。6、由3个结点所构成的二叉树有 种形态。7、数据的逻辑结构是指 o8、数据结构按逻辑结构可分为两大类，它们分别是 和。9、线性结构中元素之间存在 关系，树形结构中元素之间存在 关系，图形结构中元素之间存在多对多关系。10、带头结点的单链表head为空的条件是 o11、两个串

2、相等的充分必要条件是两个串的长度相等且。12、二维数组，可以按照 和 两种不同的存储方式。13、一棵具有257个结点的彻底二叉树，它的深度为 o14、内部排序方法按排序采用的策略可划分为五类：、和基数排序。二、选择题1、若某线性表中最常用的操作是取第i个元素和找第i个元素的前驱，则采用（）存储 方法最节省时间。A.顺序表B.单链表C.双链表D.单循环链表2、二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。A.空或者惟独一个结点 B.高度等于其结点数 C.任一结点无左孩子 D.任一结点无右孩子3、计算机算法指的是：（）A.计算方法 B.排序方法C.解决问题的有限运算序列D.调度

3、方法 4、栈和队列的主要区别在于（）。A.它们的逻辑结构不一样B.它们的存储结构不一样C.所包含的运算不一样D.插入删除运算的限定不一样5、为5个使用频率不等的字符设计哈弗曼编码，不可能的方案是（）0A. 000, 001,010,011, 1B. 0000, 0001,001,01, 1C. 000, 001,01, 10, 11D. 00, 100, 101, 110, 1116、用深度优先遍历方法遍历一个有向无环图，并在深度优先遍历算法中按退栈次序打印出 相应的顶点，则输出的顶点序列是（）oA.逆拓扑有序B.拓扑有序 C.无序 D.顶点编号次序7、对如图所示的无向连通网图从顶点d开始用P

4、rim算法构造最小生成树，在构造过程中加 入最小生成树的前4条边挨次是（）oA.B.C.D.(d, f)4,(f, e)2,(f, e)2,(f, b)3,(d, f)4,(f, e)2,(d, f)4,(d, b)5,(f, b)3(b,a)5(a, c)3(f, d)4(a, c)3(b, a)5(f, e)2(b, a)58、在采用线性探测法处理冲突所构成的闭散列表上进行查找，可能要探测多个位置，在查 找成功的情况下，所探测的这些位置的键值（）oA. 一定都是同义词B. 一定都不是同义词 C.不一定都是同义词D.都相同9、二叉排序树中，最小值结点的（）oA.左指针一定为空B.右指针一定为

5、空C.摆布指针均为空D.摆布指针均不为空10、数据序列8, 9, 10, 4, 5, 6, 20, 1, 2只能是（）的两趟排序后的结果。A.选择排序B.冒泡排序C.插入排序D.堆排序11、计算机算法必须具备输入、输出和（ ）等5个特性。A.可行性、可移植性和可扩充性B.可行性、确定性和有穷性C.确定性、有穷性和稳定性D.易读性、稳定性和安全性12、串与普通的线性表相比较，它的特殊性体现在（）oA.顺序的存储结构B.链式存储结构C.数据元素是一个字符D.数据元素任意13、以下与数据的存储结构无关的术语是（）。A.循环队列B.链表C.哈希表D.栈14、以下属于逻辑结构的是（）oA.顺序表B.哈希

6、表C.有序表D.单链表15、将一棵有100个结点的彻底二叉树从根这一层开始，每一层上从左到右挨次对结点进行 编号，根结点的编号为1,则编号为49的结点的左孩子编号为（）。A. 98B. 99C. 50D. 4816、已知关键码序列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

7、, 84, 55, 28, 78,19, 69, 8917、在一个长度为n的顺序表中，在第i个元素之前插入一个新元素时，需向后挪移（）个元素。A. n-i18、空串和空格串（A.相同B. n-i+1)oB.不相同19、常对数组进行两种基本操作是（）oA.建立和删除 B.索引和修改20、二叉树的深度为k ,则二叉树最多有（A. 2kB. 2 k-1C. n-i-1c.可能相同c.查找和修改 ）个结点。D. 2 k-1E. iD.无法确定D.查找与索引D. 2k-l三、判断题1、线性表的逻辑顺序总是与其物理顺序一致。（2、当待排序序列初始有序时，简单选择排序的时间复杂性为0（n）。（）3、对稀疏矩

8、阵进行压缩存储是为了节省存储空间。（）4、边数很少的稀疏图，适宜用邻接矩阵表示。（）5、二叉树是一棵无序树。（）6、对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为0（n）。 （）7、当待排序序列初始有序时，快速排序的时间复杂性为0（n）。（）8、顺序表的空间利用率高于链表。（）9、哈希查找法中解决冲突问题的常用方法是除留余数法。（）10、顺序查找法合用于存储结构为顺序或者链接存储的线性表。（）11、线性表的顺序存储优于链式存储。（）12、用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图 中的顶点个数有关，而与图的边数无关。 （）13、当向

9、一个最小堆插入一个具有最小值的元素时，该元素需要逐层向上调整，直到被调整 到堆顶位置为止。（）14、采用不同的遍历方法，所得到的无向图的生成树是不同的。（）15、有回路的有向图不能完成拓扑排序。（）16、若让元素1,2,3挨次进栈，则出栈次序1,3,2是不可能浮现的情况。（）17、在线性链表中删除中间的结点时，只需将被删结点释放。（）18、线性表若采用链式存储表示，在删除时不需要挪移元素。（）19、采用不同的遍历方法，所得到的无向图的生成树总是相同的。（）20、递归的算法简单、易懂、容易编写，而且执行效率也高。（）四、名词解释3、数据：4、存储结构分为：5、算法的五个重要特性：6、栈；7、彻底

10、二叉树：8、算法：9、队列：10、满二叉树：11、连通图：12、数据项：五、简答题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、程序分析填空题函数GetElem实现返回单链表的第i个元素，请在空格

11、处将算法补充完整。int GetElem(LinkList L, int i, Elemtype *e)LinkList p ;int j;p=L-next;j=l;while(p&ji) 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-l) return ERROR;s= (LNode *)

12、malloc(sizeof(LNode);s-data=e;(1) ；(2) ;return OK; AListlnsert*/5、已知一棵度为m的树中有：nl个度为1的结点，n2个度为2的结点，nm个度为m的结点，问该树中共有多少个叶子结点？6、 已知一个A0V网如图所示，写出所有的拓扑序列。7、已知数据序列为(12, 5, 9, 20, 6, 31, 24),对该数据序列进行排序，写出直接插入排序、堆 排序每趟的结果。8、程序分析填空题(1)、函数ListDelete_sq实现顺序表删除算法，请在空格处将算法补充完整。int ListDelete_sq(Sqlist *L, int i)i

13、nt k;if (iL-length) return ERROR;for (k=i-l;klength-l;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-l) return ERROR;q=p-next;(2)；*s=q-data;free (q);return OK;/*listDelet

14、e*/参考答案一、填空题1数据元素、关系2逻辑结构、存储结构、运算3 L-prior=L-next=L4 n-l5模式匹配。657反映数据元素之间逻辑关系的数据结构8线性结构和非线性结构。9 一对一、一对多10head-next二二NULL 。11对应位置字符相同。12行优先顺序和列优先顺序 13 9 o 14、插入排序、选择排序、交换排序、归并排序二、选择题1-5 ABCDD 6-10 AACAC11-15 BCDCA16-20 CBBCC8、J9、X 10、 V18、V19、 X 20、X三、判断题1、X 2、X 3、 J 4、 X 5、义 6、 J 7、 X 11、X 12、 V 13、 V 14、 V 15、 V 16、 X 17、X四、名词解释略 五、简答题略