DS试题10套00.doc

《DS试题10套00.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第一部分选择题一、单项选择题（本大题共20小题，每小题1分，共20分）1．计算机算法指的是，它必须具备输入、输出和【】A．计算方法B．排序方法C．解决问题的有限运算步骤D．程序设计方法2．下列算法的时间复杂度是【】for（i=0；i

2、．向一个栈顶指针top的链栈中插入一个S所指节点时，执行【】A．top－＞next＝s；B．s－＞next＝top－＞next；top一＞next＝s；C．s－＞next＝top；top＝s；D．s－＞next＝top；top＝top－＞next；6．栈结构通常采用的两种存储结构是【】A．散列方式和索引方式B．顺序存储结构和链表存储结构C．链表存储结构和数组D．线性存储结构和非线性存储结构7．设s1＝””，则strlen(s1)＝【】A．0B．1C。2D．38．设目标串T＝”aabbccddbbaa”，模式P=”bb”，则该模

3、式匹配的有效位移为【】A．1B．2C．3D．49．数组与一般线性表的区别主要在【】A．存储方面B．元素类型一致C．逻辑结构方面D．不能进行插入、删除运算10设二线数组A［0。。。m-l］[0。。。n-1]按行优先顺序存储在内存中，每个元素占d个字节，则元素A[i][j]的地址为【】A．LOC（A[1][1]）＋［（i-1）*n＋j-l］*dB．LOC（A[0][0]）＋［（i-l）*n＋j-1］*dC．LOC（A[1][1]）＋［(j-l)*n＋i–1］*dD．LOC（A[0][0]）＋［（j-l）*n＋i-1］*d11具有n

4、个节点的完全二叉树的深度为【】A．log2n+1B．log2n＋lC．log2nD．log2n12在具有n（n>l）个节点的完全二叉树中，节点i（2i＞n）的左孩子节点是【】A．2iB．2i＋lC．不存在D．是2i-l13．在一个图中，所有顶点的度数之和等于图的边数的几倍。【】A．1/2B．1C．2D．414在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是【】A．希尔排序B．冒泡排序C．插入排序D．选择排序15．设有1000个无序的元素，希望以最快的速度挑选出其中前10个最大的元素，最好选用的排序法是【】A．起泡

5、排序B．快速排序C．堆排序D．基数排序16．二分查找要求节点【】A．有序、顺序存储B．有序、链接存储C．无序、顺序存储D．无序、链接存储17．VSAM文件采用哪种索引结构【】A．多级B．动态C．随机D。静态18．散列文件中的记录通常是成组存放的，存放一组数据的存储单位称为【】A．扇区B．柱面C．磁道D．桶19．索引表是指示逻辑记录和什么之间对应关系的表【】A．物理记录B．元素C．关键字D．结构20．有8个节点的无向连通图最少有多少条边【】A．14B。28C．56D．112第二部分非选择题二、填空题（本大题共15小题，每空1分，

6、井20分）l．数据结构的实质一般包括三个方面的内容：数据的＿＿＿＿，数据的＿＿＿＿及数据的运算。2．在双链表中每个节点有两个指针域，一个指向＿＿＿＿，另一个指向＿＿＿＿。3．当链满时再做进栈运算将产生＿＿＿＿。4栈S经过运算InitStake(S);Push(S,a);Push(S,b);后StakeTop(S)的值是＿＿＿＿。5．通常在程序中使用的串可分为两种，即＿＿＿＿和＿＿＿＿。6广义表（（a），((b),J,(((d))))的表头是＿＿＿＿，表尾是＿＿＿＿。7．由一棵二叉树的前序序列和＿＿＿＿可唯一确定这棵二叉树。8高

7、度为k的完全二叉树至少有＿＿＿＿个节点。9．如果n个顶点的图是一个环，则它有＿＿＿＿棵生成树。10．n个顶点e条边的图若采用邻接表存储，则空间复杂度为＿＿＿＿。11．在排序前，关键字值相等的不同记录间的前后相对位置保持＿＿＿＿的排序方法称为稳定的排序方法。12．对于n个记录的集合进行归并排序，所需要的平均时间为＿＿＿＿。13．文件有四种基本的存储结构组织方式：顺序组织、索引组织、＿＿＿＿和＿＿＿＿。14．对二叉排序树进行的查找方法是用待查的值与根节点的键值相比，若比根小则继续在＿＿＿＿子树中找。15．两个不同的元素存入同一个散

8、列表，当这两个元素的散列函数值相同时，称为＿＿＿＿。三、名词解释（本大题共5小题，每题3分，共15分）l．循环链表2．队列3．三角矩阵4．有序树5．生成树四、简答题（本大题共5小题，每题5分，共25分）l．简述线形结构与非线形结构的不同点。2．对于一个栈，如果输入项序列由A，