数据结构模拟试卷和答案

北京语言大学网络教育学院《数据结构》模拟试卷一注意：1.试卷保密，考生不得将试卷带出考场或撕页，否则成绩作废。请监考老师负责监督。2.请各位考生注意考试纪律，考试作弊全部成绩以零分计算。3.本试卷满分100分，答题时间为90分钟。4.本试卷分为试题卷和答题卷，所有答案必须答在答题卷上，答在试题卷上不给分。一、【单项选择题】(本大题共10小题，每小题2分，共20分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在答题卷相应题号处。1、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则采用（）存储方式最节省时间。[A]顺序表[B]双链表[C]带头结点的双循环链表[D]单循环链表2、队列操作的原则是（）。[A]只能进行删除[B]后进先出[C]只能进行插入[D]先进先出3、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。[A]空或只有一个结点[B]高度等于其结点数[C]任一结点无左孩子[D]任一结点无右孩子4、在下列排序方法中，（）方法平均时间复杂度为0(nlogn)，最坏情况下时间复杂度为0(n2)。5、对二叉树从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一个结点的左、右孩子中，其左孩子编号小于右孩子编号。则可采用（）次序的遍历实现编号。[A]先序[B]中序[C]后序[D]从根开始的层次遍历6、若用数组S[n]作为两个栈S1和S2的共用存储结构，对任何一个栈，只有当S[n]全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是（）。[A]S1的栈底位置为0，S2的栈底位置为n[B]S1的栈底位置为－1，S2的栈底位置为n/2[C]S1的栈底位置为0，S2的栈底位置为n－1[D]S1的栈底位置为0，S2的栈底位置为n/27、对一棵二叉排序树进行（）遍历，可以得到该二叉树的所有结点按值从小到[A]插入排序[B]希尔排序[C]快速排序[D]堆排序大排列的序列。8、在下列排序算法中，（）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。9、采用邻接表存储的图的广度优先算法类似于二叉树的（）。10、具有6个顶点的无向图至少应有（）条边才能保证图的连通性。二、【判断题】(本大题共10小题，每小题2分，共20分)正确的填T，错误的填F，填在答题卷相应题号处。11、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。（）12、任何二叉树都唯一对应一个森林，反之亦然。（）13、有向图的邻接矩阵一定是对称的。（）14、线性表的链式存储结构优于顺序存储结构。（）15、关键路径可能不只一条，但缩短某一关键路径一定能够缩短工期。（）16、直接选择排序是一种不稳定的排序方法。（）17、顺序表用一维数组作为存储结构，因此顺序表是一维数组。（）18、栈和队列都是顺序存取的的线性表，但它们对存取位置的限制不同。（）19、闭散列法通常比开散列法时间效率更高。（）20、一棵m阶B树中每个结点最多有m个关键码，最少有2个关键码。（）三、【填空题】（本大题共10小空，每小空2分，共20分）请将答案填写在答题卷相应题号处。21、《数据结构》课程讨论的主要内容是数据的逻辑结构、存储结构和（）。22、若要在单链表结点*P后插入一结点*S，执行的语句（）。23、折半搜索只适合用于（）。24、栈结构允许进行删除操作的一端为（）。25、设一行优先顺序存储的数组A[5][6]，A[0][0]的地址为1100，且每个元素占2个存储单元，则A[2][3]的地址为（）。26、若某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点个数为（）。27、一棵具有5层满二叉树中节点总数为（）。28、从树中一个结点到另一个结点之间的分支构成这两个结点之间的（）。[A]前序[B]后序[C]中序[D]按层次[A]堆排序[B]冒泡排序[C]快速排序[D]插入排序[A]先序遍历[B]中序遍历[C]后序遍历[D]层次遍历[A]4[B]5[C]6[D]729、在无向图中，若从顶点A到顶点B存在（），则称A与B之间是连通的。30、若图的邻接矩阵是对称矩阵，则该图一定是（）。四、【应用题】（本大题共5小题，每小题8分，共40分）请将答案填写在答题卷相应题号处。31、已知序列（12，4，17，10，7，30），用直接选择排序法对其进行递增排序，写出每一趟的排序结果。32、单链表结点的类型定义如下：typedefstructLNode{intdata;structLNode*next;}LNode,*Linklist;写一算法，将带头结点的有序单链表A和B合并成一新的有序表C。（注：不破坏A和B的原有结构）33、已知一棵非空二叉树，其按中序和后序遍历的结果分别为：中序：CGBAHEDJFI后序：GBCHEJIFDA请画出这棵二叉树，并写出其前序遍历的结果。34、已知字符：C1，C2，C3，C4，C5，C6的权分别为：17，5，16，4，8，11，请构造相应的赫夫曼树，并给出相应字符的赫夫曼编码。35、已知如下图所示二叉树，分别写出其前序、中序和后序序列。ABCDEF《数据结构》模拟试卷一答案一、【单项选择题】(本大题共10小题，每小题2分，共20分)题号12345678910答案CDBCCCCDDB二、【判断题】(本大题共10小题，每小题2分，共20分)题号11121314151617181920答案TTFFFTFTFF三、【填空题】（本大题共10小空，每小空2分，共20分）21、(运算)；22、(s-next=p-next;p-next=s)；23、(有序表)；24、(栈顶)；25、(1130)；26、(69)；27、(31)；28、(路径)；29、(路径)；30、(无向图)；四、【应用题】（本大题共5小题，每小题8分，共40分）31、标准答案：第1趟：4121710730第2趟：4717101230第3趟：4710171230第4趟：4710121730第5趟：4710121730复习范围或考核目标：课件第十章第二节。32、标准答案：Merge(LinklistA,LinklistB,Linklist&C)voidMerge(LinklistA,LinklistB,Linklist&C){C=(Linklist)malloc(sizeof(LNode));pa=A-next;pb=B-next;pc=C;while(pa&&pb){pc-next=(Linklist)malloc(sizeof(LNode));pc=pc-next;if(pa-data=pb-data){pc-data=pa-data;pa=pa-next;}else{pc-data=pb-data;pb=pb-next;}}if(!pa)pa=pb;while(pa){pc-next=(Linklist)malloc(sizeof(LNode));pc=pc-next;pc-data=pa-data;pa=pa-next;}pc-next=NULL;}复习范围或考核目标：课件第二章第三节。33、标准答案：前序遍历结果:ACBGDEHFJI复习范围或考核目标：课件第六章第四节。34、标准答案：c1:10c2:1111c3:01c4:1110c5:110c6:00复习范围或考核目标：课件第六章第八节。35、标准答案：前序：ABDECF中序：DBEACF后序：DEBFCA复习范围或考核目标：课件第六章第四节。北京语言大学网络教育学院《数据结构》模拟试卷二注意：1.试卷保密，考生不得将试卷带出考场或撕页，否则成绩作废。请监考老师负责监督。2.请各位考生注意考试纪律，考试作弊全部成绩以零分计算。3.本试卷满分100分，答题时间为90分钟。4.本试卷分为试题卷和答题卷，所有答案必须答在答题卷上，答在试题卷上不给分。一、【单项选择题】(本大题共10小题，每小题2分，共20分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在答题卷相应题号处。1、程序段：sum=0;for(i=1;in*n;i++)Sum++;的平均情况下时间代价的表达式是（）。2、数据结构通常是研究数据的（）及它们之间的联系。[A]存储和逻辑结构[B]存储和抽象[C]理想和抽象[D]理想与逻辑3、将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子的编号为（）。4、在有n个叶结点的Huffman树中,其结点总数为（）。5、设有100个元素，用折半查找法进行查找时，最大比较次数是（）。6、若需要利用形参直接访问实参，则应把形参变量说明为（）参数。7、已知单链表A长度为m，单链表B长度为n，若将B联接在A的末尾，其时间复杂度应为（）。8、在一棵高度为h(假定树根结点的层号为0)的完全二叉树中，所含结点个数不小于（）。9、假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为（）。10、在一棵树中，（）没有前驱结点。[A](1)[B](n)[C](n2)[D](nlogn)[A]98[B]99[C]50[D]48[A]2n-1[B]2n+1[C]2n[D]不确定[A]25[B]50[C]10[D]7[A]指针[B]引用[C]传值[D]常值[A]O(1)[B]O(m)[C]O(n)[D]O(m+n)[A]2h-1[B]2h+1[C]2h-1[D]2h[A]front==rear[B]front!=NULL[C]rear!=NULL[D]front==NULL[A]分支结点[B]叶结点[C]树根结点[D]空结点二、【判断题】(本大题共10小题，每小题2分，共20分)正确的填T，错误的填F，填在答题卷相应题号处。11、线性表的逻辑顺序与物理顺序总是一致的。（）12、在链式存储的栈的头部必须要设头结点。（）13、在二叉树中插入结点，则该项二叉树便不再是二叉树。（）14、由二叉树结点的先序序列和后序序列可以唯一确定一棵二叉树。（）15、栈和队列也是线性表。如果需要，可对它们中的任一元素进行操作。（）16、用树的前序遍历序列和中序遍历序列可以导出树的后序遍历序列。（）17、即使对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作，所得到的序列也一定相同。（）18、哈夫曼(Huffman)树是带权路径长度最短的树。路径上权值较大的结点离根较近。（）19、对于任一个图，从某顶点出发进行一次深度或广度优先搜索，可以访问图中每一个顶点。（）20、带权的无向连通图的最小生成树是唯一的。（）三、【填空题】（本大题共10小空，每小空2分，共20分）请将答案填写在答题卷相应题号处。21、如果n个顶点的图是一个环，则它有（）棵生成树。22、设在等概率情形下,对有n个元素的顺序表进行插入（插入位置i取0到n范围内的整数）,平均需要移动（）个元素。23、具有96个结点的完全二叉树的高度为（）。24、如果一棵树有n1个度为1的结点,有n2个度为2的结点,…,nm个度为m的结点,则度为0的结点有（）个。25、若二叉树的中序序列与后序序列相同，则该二叉树是空树或（）。26、若一棵完全二叉树有500个结点，则该二叉树的深度为（）。27、用邻接矩阵表示无向图时，若图中有1000个顶点，1000条边，则形成的邻接矩阵有（）矩阵元素。28、给定序列{100，86，48，73，35，39，42，57，66，21}，按堆结构的定义，则它一定是（）堆。29、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表的元素是，应采用（）存储结构。30、向一个长度为n的顺序表的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动（）个元素。四、【应用题】（本大题共5小题，每小题8分，共40分）请将答案填写在答题卷相应题号处。31、已知某二叉树中序遍历的结果是ABC，试画出其可能