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

《《数据结构与算法》复习题A（专升本）.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

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,1B.0000,0001,001,01,1C.000,001,01,10,11D.00,100,101,110

3、,1116、用深度优先遍历方法遍历一个有向无环图，并在深度优先遍历算法中按退栈次序打印出相应的顶点，则输出的顶点序列是（）。A.逆拓扑有序B.拓扑有序C.无序D.顶点编号次序7、对如图所示的无向连通网图从顶点d开始用Prim算法构造最小生成树，在构造过程中加入最小生成树的前4条边依次是（）。A.（d,f）4,(f,e)2,(f,b)3(b,a)5B.（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、在采用线性探测法处理冲突所构成的闭

4、散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置的键值（）。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、完全二叉树：五、简答题

6、1、由二叉树的中序序列及前序序列能唯一的建立二叉树，试问前序序列及后序序列是否也能唯一的建立二叉树，不能则举例说明理由。2、关键码集合{47,7,29,11,16,92,22,8,3}，散列函数为H(key)=keymod11，用拉链法处理冲突，构造开散列表，并求查找成功时的平均查找长度。3.已知数据序列为（12，5，9，20，6，31，24），对该数据序列进行排序，写出简单选择排序以及快速排序每趟的结果。4、程序分析填空题（1）函数GetElem实现返回单链表的第i个元素，请在空格处将算法补充完整。intGetElem(LinkListL,int

7、i,Elemtype*e){LinkListp;intj;p=L->next;j=1;while(p&&j

8、

9、j>i)returnERROR;*e=(2);returnOK;}（2）、函数实现单链表的插入算法，请在空格处将算法补充完整。intListInsert(LinkListL,inti,ElemTypee){LNode*p,*s;intj;p=L;j=0;while((p!=NULL)&&(jnext;j++;}if(p==NULL

10、

11、j>i-1)returnERROR;s=(LNo

12、de*)malloc(sizeof(LNode));s->data=e;(1);(2);returnOK;}/*ListI