数据结构模拟试卷一

《数据结构模拟试卷一》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构一、【单项选择题】1、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则采用（）存储方式最节省时间。[C]带头结点的双循环链表2、队列操作的原则是（）。[D]先进先出3、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。[B]高度等于其结点数4、在下列排序方法中，（）方法平均时间复杂度为0(nlogn)，最坏情况下时间复杂度为0(n2)。[C]快速排序5、对二叉树从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一个结点的左、右孩子中，其左孩子编号小于右孩子编号。则可采用（）次序的遍历实现编号。[C]后序

2、6、若线性表中采用二分查找法查找元素，该线性表应该（）。[C]元素按值有序，且采用顺序存储结构7、对待排序数据的初始状态不作任何要求的排序方法有（）。[A]插入和快速排序8、已知数据表A中每个元素距其最终位置不远，则采用（）排序算法最节省时间。[B]插入排序9、以下哪一个不是队列的基本运算？（）[B]从队列中删除第i个元素10、广度优先遍历类似于二叉树的（）。[D]层次遍历1．程序段：sum=0;for(i=1;i

3、构通常是研究数据的（）及它们之间的联系。[A]存储和逻辑结构3．将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子的编号为（）。[A]984．在有n个叶结点的Huffman树中,其结点总数为（）。[A]2n-15．设有100个元素，用折半查找法进行查找时，最大比较次数是（）。[D]76．快速排序在（）情况下最易发挥其长处。[C]被排序数据完全无序7．由两个栈共享一个向量空间的好处是（）。[B]节省存储空间,降低上溢发生的机率8．对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为（）。[C]用尾指针

4、表示的循环单链表9．图的深度优先遍历类似于二叉树的（）。[A]先序遍历10．设长度为n的链队列用单循环链表表示，若只设头指针，则入队操作的时间复杂度为（）。[C]O(n)1、在一个图中，所有顶点的度数之和等于图的边数的（）倍。[C]22、采用顺序查找方法查找长度为n的线性表，平均查找长度为（）。[C](n+1)/23、线性链表不具有的特点是（）。[A]随机访问4、删除长度为n的非空顺序表的第i个数据元素之前需要移动表中（）个数据元素。[A]n-i5、任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（）。[A]不发生改变6、若用数组S[n]作为两个栈S1和S2的

5、共用存储结构，对任何一个栈，只有当S[n]全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是（）。[C]S1的栈底位置为0，S2的栈底位置为n－17、对一棵二叉排序树进行（）遍历，可以得到该二叉树的所有结点按值从小到大排列的序列。[C]中序8、在下列排序算法中，（）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。[D]插入排序9、采用邻接表存储的图的广度优先算法类似于二叉树的（）。[D]层次遍历10、具有6个顶点的无向图至少应有（）条边才能保证图的连通性。[B]51、数据结构在计算机内存中的表示是指（）。[A]数据的存储结构2、若不带头结点的

6、单循环链表的头指针为head，则该链表只有一个结点的判定条件是（）。[D]head->next==head3、设listarray[size]为一个顺序存储的栈,变量top指示栈中第一个空闲位置,栈为空的条件是（）。[B]top=04、在长度为n的顺序表的第i个位置上插入一个元素（1≤i≤n+1），元素的移动次数为（）。[A]n–i+15、在数据结构中，与所使用的计算机无关的是数据的（）结构。[A]逻辑6、一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是（）。[C]dceab7、若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为（）。

7、[C]88、由同一关键字集合构造的各棵二叉排序树（）。[B]其形态不一定相同，平均查找长度也不一定相同。9、具有n个顶点的无向连通图最少有（）条边。[C]n-110、若某文件经内部排序得到100个初始归并段，若使用K路归并三趟完成，则（）。[C]K>=41．算法分析的目的是（）。[C]分析算法的效率以求改进2．散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址。因为散列函数不是一对一的关系，所以选择好的（）方法是散列文件的关键。[D]散列函数和冲突处理3．在需要经常查找结点的前驱与后继的场合中，使用（）比较合适。[B