数据结构模拟试卷一.doc

《数据结构模拟试卷一.doc》由会员分享，可在线阅读，更多相关《数据结构模拟试卷一.doc（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

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

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

3、n+1），元素的移动次数为（ ）。A ni+15、在数据结构中，与所使用的计算机无关的是数据的（ ）结构。A 逻辑6、一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是（ ）。C dceab7、若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为（ ）。C 88、由同一关键字集合构造的各棵二叉排序树（ ）。B 其形态不一定相同，平均查找长度也不一定相同。9、具有n个顶点的无向连通图最少有（ ）条边。C n-110、若某文件经内部排序得到100个初始归并段，若使用K路归并三趟完成，则（ ）。C K=41算法分析的目的是（ ）。C 分析算法的效率以求改进2散列文件

4、使用散列函数将记录的关键字值计算转化为记录的存放地址。因为散列函数不是一对一的关系，所以选择好的（ ）方法是散列文件的关键。 D 散列函数和冲突处理3在需要经常查找结点的前驱与后继的场合中，使用（ ）比较合适。B 双链表4下面关于线性表的叙述中，错误的为（ ）。D 在链表中，每个结点只有一个链域5一棵树的广义表表示为a(b,c(e,f(g),d)，当用左子女-右兄弟链表表示时，右指针域非空的结点个数为（ ）。C 36若需要利用形参直接访问实参，则应把形参变量说明为（ ）参数。 B 引用7已知单链表A长度为m，单链表B长度为n，若将B联接在A的末尾，其时间复杂度应为（ ）。C O(n)8在一棵高

5、度为h(假定树根结点的层号为0)的完全二叉树中，所含结点个数不小于（ ）。D 2h9假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为（ ）。D front = NULL10在一棵树中，（ ）没有前驱结点。 C 树根结点二、【判断题】11、线性表的逻辑顺序与物理顺序总是一致的。F12、在链式存储的栈的头部必须要设头结点。F13、在二叉树中插入结点，则该项二叉树便不再是二叉树。F14、由二叉树结点的先序序列和后序序列可以唯一确定一棵二叉树。F15、栈和队列也是线性表。如果需要，可对它们中的任一元素进行操作。F16、有向图的邻接矩阵一定不是对称的。F17、在AOE网中，

6、关键路径是唯一的。F18、若将一株树转换成二叉树，则该二叉树的根结点一定没有右子树。T19、索引顺序存取方法ISAM是一种专门为磁盘存取设计的索引顺序文件的组织方法T20、基数分类只适用于以数字为关键字的情形，不适用以字符串为关键字的情形。F11树的父链表示就是用数组表示树的存储结构。T12栈和队列逻辑上都是线性表。 T13单链表从任何一个结点出发，都能访问到所有结点。F14AOE网中，只有一个入度为0的顶点（起始点），只有一个出度为0的顶点（结束点）。 T 15关键路径可能不只一条，但缩短某一关键路径一定能够缩短工期。F 16删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序

7、树。F17一般树和二叉树的结点数目都可以为0。 T18堆栈在数据中的存储原则是先进先出。F 19线性表的顺序存储结构是通过数据元素的存储地址直接反映数据元素的逻辑关系。T20非空线性表中任意一个数据元素都有且仅有一个直接后继元素。F11、线性表的顺序存储表示优于链式存储表示。F12、在外部分类中使用K路平衡归并，采用选择树法时,归并效率与K有关。F13、对于n个记录的集合进行归并分类，最坏情况下所需要时间为O(n)。F14、倒排文件与多重表文件的次关键字索引结构不同。T15、将一棵树转换成二叉树后，根结点没有左子树。F16、用树的前序遍历序列和中序遍历序列可以导出树的后序遍历序列。T17、即使

8、对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作，所得到的序列也一定相同。18、哈夫曼(Huffman)树是带权路径长度最短的树。路径上权值较大的结点离根较近。T19、对于任一个图，从某顶点出发进行一次深度或广度优先搜索，可以访问图中每一个顶点。F20、带权的无向连通图的最小生成树是唯一的。F11、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。T12、任何二叉树都唯一对应一个森林，反之亦然。T 13、有向图的邻接矩阵一定是对称的。F 14、线性表的链式存储结构优于顺序存储结构。F15、关键路径可能不只一条，但缩短某一关键路径一定能够缩短工期。F16、顺

9、序存储方式只能用于存储线性结构。F17、用循环链表作为存储结构的队列就是循环队列。F18、倒排文件的主要优点为便于节省空间。F19、一组记录的关键字为（46,79,56,38,40,84），则利用快速排序的方法，以第一个记录为基准元素得到的一次划分结果为40,38,46,56,79,84。F20、算法分析的目的是分析算法的易读性。F11. 线性表中的每个结点最多只有一个前驱和一个后继。 F 12. 每种数据结构都应具备三种基本运算：插入、删除和搜索。 F 13.在单链表P指针所指结点之后插入S结点的操作是：P-next= S ; S- next = P-next。 F 14.假设B是一棵树，B

10、是对应的二叉树。则B的后根遍历相当于B的中序遍历。T15.对于任何待排序序列来说，快速排序均快于起泡排序。 F16.直接选择排序是一种不稳定的排序方法。 T 17.顺序表用一维数组作为存储结构，因此顺序表是一维数组。 F 18.栈和队列都是顺序存取的的线性表，但它们对存取位置的限制不同。T19.闭散列法通常比开散列法时间效率更高。 F 20.一棵m阶B树中每个结点最多有m个关键码，最少有2个关键码。F三、【填空题】21、n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为（ O(n2) ）。22、将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（ n ）。23、设二叉树中结点的

11、两个指针域分别为lchild和rchild，则判断指针变量p所指向的结点为叶子结点的条件是（ p-lchild = NULL & p-rchild = NULL； ）。24、设一棵二叉树的前序序列为ABC，则有（ 5 ）种不同的二叉树可以得到这种序列。25、为了给n个字母编码而建立起来的Huffman树一共有（ 2n1 ）个结点。26、n个顶点的连通图用相邻矩阵表示时，该矩阵至少有（ n1 ）个非零元素。27、对于一个具有n个顶点和e条边的无向图，在其对应的邻接表中，所含边结点有（ 2e ）个。28、冒泡排序在最好情况下的元素交换次数为（ 0 ）。29、由权值分别为11，8，6，2，5的叶子结

12、点生成一棵哈夫曼树，它的外部路径权重为（ 71 ）。30、栈是一种受限制的线性表，也叫LIFO结构，LIFO的含义是（ 后进先出 ）。21数据结构课程讨论的主要内容是数据的逻辑结构、存储结构和（运算）。22若要在单链表结点*P后插入一结点*S，执行的语句（s-next=p-next;p-next=s）。23折半搜索只适合用于（有序表）。24栈结构允许进行删除操作的一端为（栈顶）。25设一行优先顺序存储的数组A56，A00的地址为1100，且每个元素占2个存储单元，则A23的地址为（1130）。26若某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点个数为（69）。27一棵具

13、有层满二叉树中节点总数为（31）。28从树中一个结点到另一个结点之间的分支构成这两个结点之间的（路径）。29在无向图中，若从顶点A到顶点B存在（路径），则称A与B之间是连通的。30若图的邻接矩阵是对称矩阵，则该图一定是（无向图）。21、如果n个顶点的图是一个环，则它有（ n ）棵生成树。22、设在等概率情形下, 对有n个元素的顺序表进行插入（插入位置i取0到n范围内的整数）, 平均需要移动（ n/2 ）个元素。23、具有96个结点的完全二叉树的高度为（ 7 ）。24、如果一棵树有n1个度为1的结点, 有n2个度为2的结点, , nm个度为m的结点, 则度为0的结点有（ n2+2n3+.+(m-

14、1)nm+1 ）个。25、若二叉树的中序序列与后序序列相同，则该二叉树是空树或（ 只有根节点的二叉树 ）。26、若一棵完全二叉树有500个结点，则该二叉树的深度为（ 9 ）。27、用邻接矩阵表示无向图时，若图中有1000个顶点，1000条边，则形成的邻接矩阵有（ ）矩阵元素。28、给定序列100，86，48，73，35，39，42，57，66，21，按堆结构的定义，则它一定是（ 大顶 ）堆。29、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表的元素是，应采用（ 顺序 ）存储结构。30、向一个长度为n的顺序表的第i个元素(1in+1)之前插入一个元素时，需向后

15、移动（ ni1 ）个元素。21、图的逆邻接表存储结构只适用于（ 有向 ）图。22、设在等概率情形下, 对有127个元素的顺序表进行删除, 平均需要移动（ 63 ）个元素。23、图的深度优先遍历序列（ 不是 ）惟一的。24、一棵高度为5的二叉树中最少含有（ 5 ）个结点，最多含有（ 31 ）个结点。25、在单链表中，若要在指针p所指结点后插入指针s所指结点，则需要执行下列两条语句：s-next=p-next；（ p-next=s ）。26、一棵高度为h的满k叉树有如下性质：第h层上的结点都是叶结点, 其余各层上每个结点都有k棵非空子树, 如果按层次自顶向下, 同一层自左向右, 顺序从1开始对全部

16、结点进行编号，编号为i的结点的第m个孩子结点(若存在)的编号是（ (i-1)*k + m + 1 ）。27、在有序表A120中，采用折半查找算法查找元素值等于A12的元素，所比较过的元素的下标依次为（ 10,15,12 ）。28、表示图的三种常用的存储结构为( 邻接矩阵 )、( 邻接表 )和十字链表。21.数据结构算法中，通常用时间复杂度和（空间复杂度）两种方法衡量其效率。22.若频繁地对线性表进行插入与删除操作，该线性表应采用（链表）存储结构。23. （循环）链表从任何一个结点出发，都能访问到所有结点。24.某带头结点的单链表的头指针head，判定该单链表非空的条件（head-next!=N

17、ull）。25.已知指针p指向单链表中某个结点，则语句p-next=p-next-next的作用是（删除p 的后继结点）。26.在栈的顺序实现中，栈顶指针top，栈为空条件（top=-1）。27.在长度为n的循环队列中，删除其节点为x的时间复杂度为（O(n)）。28.有三个结点的二叉树，最多有（ 5 ）种形状。29.深度为90的满二叉树，第11层有（ 1024 ）个结点。30.设有10个值，构成哈夫曼树，则该哈夫曼树共有（ 19 ）个结点。四、【应用题】31简述顺序表和链表存储方式的特点。顺序表的优点是可以随机访问数据元素；缺点是大小固定，不利于增删结点。链表的优点是采用指针方式增减结点，非常

18、方便（只需要改变指针指向，不移动结点）；缺点是不能进行随机访问，另外，每个结点上增加指针域，造成额外存储空间增大。32对链表设置头结点的作用是什么？（至少说出两条好处）(1) 对带头结点的链表，在表的任何结点之前插入结点或删除表中任何结点，所要做的都是修改前一结点的指针域，因为任何元素结点都有前驱结点。若链表没有头结点，则首元素结点没有前驱结点，在其前插入结点或删除该结点时操作会复杂些。(2) 对带头结点的链表，表头指针是指向头结点的非空指针，因此空表与非空表的处理是一样的。35编写实现“直接插入排序”的子函数，入口参数是整型数组L 和数组长度n.void sort(L, n) int L, n; int i, x;for(i=1; i0 & Li-1x) Li=Li-1; i+; Li-1=x;