资源描述：
《大数据结构复习题.docx》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、2017～2018学年度第2学期《数据结构》复习提纲一、单项选择题题号12345678910答案CADCABABCD题号11121314151617181920答案AADAADCBAB1．在数据结构中，从逻辑上可以把数据结构分为_________两类。A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．部结构和外部结构2．链表不具有的特点是_________。A．可随机访问任一元素B．插入、删除不需要移动的元素C．不必事先估计存储空间D．所需空间与线性表长度成正比3．若线性表最常用的运算是
2、存取第i个元素及其前驱元素，则采用_________存储方式节省时间。A．单链表B．双链表C．循环单链表D．顺序表4．算法分析的目的是_________。A．找出数据结构的合理性B．研究算法中的输入和输出关系C．分析算法的效率以求改进D．分析算法的易读性和文档性5．若一个栈用数组data[1..n]存储，初始栈顶指针top为0，则以下元素x进栈的操作正确的是_________。A．top++;data[top]=x;B．data[top]=x;top++;C．top--;data[top]=x;D．data[t
3、op]=x;top--;6．表达式a*(b+c)-d的后缀表达式是_________。A．abcd*+-B．abc+*d-C．abc*+d-D．-+*abcd7．递归函数f(1)=1，f(n)=f(n-1)+n(n＞1)的递归出口是_________。A．f(1)=1B．f(1)=0C．f(0)=0D．f(n)=n8．将递归算法转换成对应的非递归算法时，通常需要使用_________保存中间结果。A．队列B．栈C．链表D．树9．对稀疏矩阵采用压缩存储，其缺点之一是_________。A．无法判断矩阵有多少行、多
4、少列B．无法根据行、列号查找某个矩阵元素C．无法根据行、列号直接计算矩阵元素的存储地址D．使矩阵元素之间的逻辑关系更加复杂10．一个n阶上三角矩阵a按行优先顺序压缩存放在一维数组b中，则b中的元素个数是_________。A．nB．n2C．n(n+1)/2D．n(n+1)/2+111．度为4，高度为h的树_________。A．至少有h+3个结点B．最多有4h-1个结点C．最多有4h个结点D．至少有h+4个结点12．用双亲存储结构表示树，其优点之一是比较方便_________。A．找指定结点的双亲结点B．找指定
5、结点的孩子结点C．找指定结点的兄弟结点D．判断某结点是不是叶子结点13．设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有_________个结点。A．13B．12C．26D．2514．无向图的邻接矩阵是一个_________。A．对称矩阵B．零矩阵C．上三角矩阵D．对角矩阵15．在图的广度优先遍历算法中用到一个队列，每个顶点最多进队_________次。A．1B．2C．3D．不确定16．在用Prim和Kruskal算法构造最小生成树时，前者更适合于_________。A．有向图B．无向图C．稀疏图D．稠密
6、图17．有一个有序表R[1..13]={1,3,9,12,32,41,45,62,75,77,82,95,100}，当用二分查找法查找值为82的节点时，经过_________次比较后查找成功。A．1B．2C．4D．818．在采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块，则每块分为_________个结点最佳。A．9B．25C．6D．62519．若R中有10000个元素，如果仅要求求出其中最大的10个元素，则采用_________方法最节省时间。A．堆排序
7、B．希尔排序C．快速排序D．基数排序20．有一组序列（48,36,68,99,75,24,28,52）进行快速排序，要求结果从小到大排序，则进行一次划分之后的结果为_________。A．[242836]48[52687599]B．[283624]48[75996852]C．[366899]48[75242852]D．[283624]48[99756852]二、填空题题号答案题号答案题号答案1问题规模2O(n)3假溢出42855462h-17关键活动8无环图9RL10基数排序1．在分析算法的时间复杂度时，通常认
8、为算法的执行时间是_________的函数。2．求一个双链表长度的算法的时间复杂度为_________。3．在实现顺序队的时候，通常将数组看成是一个首尾相连的环，这样做的目的是为了避免产生_____现象。4．有如下递归过程：voidreverse(intm){printf("%d",n%10);if(n/10!=0)reverse(n/10);}调用语句reverse(582)的结果是
