数据结构模拟试卷和答案.doc

北京语言大学网络教育学院数据结构模拟试卷一注意： 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)。A 插入排序B 希尔排序C 快速排序D 堆排序5、对二叉树从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一个结点的左、右孩子中，其左孩子编号小于右孩子编号。则可采用（ ）次序的遍历实现编号。A 先序B 中序C 后序D 从根开始的层次遍历6、若用数组Sn作为两个栈S1和S2的共用存储结构，对任何一个栈，只有当Sn全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是（ ）。A S1的栈底位置为0，S2的栈底位置为n B S1的栈底位置为1，S2的栈底位置为n/2 C S1的栈底位置为0，S2的栈底位置为n1 D S1的栈底位置为0，S2的栈底位置为n/2 7、对一棵二叉排序树进行（ ）遍历，可以得到该二叉树的所有结点按值从小到大排列的序列。A 前序B 后序C 中序D 按层次8、在下列排序算法中，（ ）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。A 堆排序B 冒泡排序C 快速排序D 插入排序9、采用邻接表存储的图的广度优先算法类似于二叉树的（ ）。A 先序遍历B 中序遍历C 后序遍历D 层次遍历10、具有6个顶点的无向图至少应有（ ）条边才能保证图的连通性。A 4B 5C 6D 7二、【判断题】(本大题共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、设一行优先顺序存储的数组A56，A00的地址为1100，且每个元素占2个存储单元，则A23的地址为（ ）。26、若某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点个数为（ ）。27、一棵具有5层满二叉树中节点总数为（ ）。28、从树中一个结点到另一个结点之间的分支构成这两个结点之间的（ ）。29、在无向图中，若从顶点A到顶点B存在（ ），则称A与B之间是连通的。30、若图的邻接矩阵是对称矩阵，则该图一定是（ ）。四、【应用题】（本大题共5小题，每小题8分，共40分）请将答案填写在答题卷相应题号处。31、已知序列（12，4，17，10，7，30），用直接选择排序法对其进行递增排序，写出每一趟的排序结果。32、单链表结点的类型定义如下：typedef struct LNode int data; struct LNode *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、已知如下图所示二叉树，分别写出其前序、中序和后序序列。 A B C D E F 数据结构模拟试卷一 答案一、【单项选择题】(本大题共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趟：4 12 17 10 7 30第2趟：4 7 17 10 12 30第3趟：4 7 10 17 12 30第4趟：4 7 10 12 17 30第5趟：4 7 10 12 17 30复习范围或考核目标：课件第十章第二节。 32、标准答案：Merge(Linklist A, Linklist B, Linklist &C )void Merge(Linklist A, Linklist B, 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-datadata) 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:10 c2:1111 c3:01 c4:1110 c5:110 c6:00复习范围或考核目标：课件第六章第八节。35、标准答案：前序：ABDECF 中序：DBEACF 后序：DEBFCA复习范围或考核目标：课件第六章第四节。北京语言大学网络教育学院数据结构模拟试卷二注意： 1.试卷保密，考生不得将试卷带出考场或撕页，否则成绩作废。请监考老师负责监督。2.请各位考生注意考试纪律，考试作弊全部成绩以零分计算。3.本试卷满分100分，答题时间为90分钟。4.本试卷分为试题卷和答题卷，所有答案必须答在答题卷上，答在试题卷上不给分。一、【单项选择题】(本大题共10小题，每小题2分，共20分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在答题卷相应题号处。1、程序段：sum=0; for (i=1;in*n;i+) Sum+;的平均情况下时间代价的Q表达式是（ ）。A Q(1)B Q(n)C Q(n2)D Q(nlogn)2、数据结构通常是研究数据的（ ）及它们之间的联系。A 存储和逻辑结构B 存储和抽象C 理想和抽象D 理想与逻辑3、将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子的编号为（ ）。A 98B 99C 50D 484、在有n个叶结点的Huffman树中, 其结点总数为（ ）。A 2n-1B 2n+1C 2nD 不确定5、设有100个元素，用折半查找法进行查找时，最大比较次数是（ ）。A 25B 50C 10D 76、若需要利用形参直接访问实参，则应把形参变量说明为（ ）参数。 A 指针B 引用C 传值D 常值7、已知单链表A长度为m，单链表B长度为n，若将B联接在A的末尾，其时间复杂度应为（ ）。A O(1)B O(m)C O(n)D O(m+n)8、在一棵高度为h(假定树根结点的层号为0)的完全二叉树中，所含结点个数不小于（ ）。A 2h-1B 2h+1C 2h-1D 2h9、假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为（ ）。A front = rearB front != NULLC rear != NULLD front = NULL10、在一棵树中，（ ）没有前驱结点。 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个元素(1in+1)之前插入一个元素时，需向后移动（ ）个元素。四、【应用题】（本大题共5小题，每小题8分，共40分）请将答案填写在答题卷相应题号处。31、已知某二叉树中序遍历的结果是ABC，试画出其可能的二叉树五种形态。32、一个一维整数数组Am中有n (nm)个非空整数，它们相继存放于数组的前端并已按非递减顺序排列，在数组Am中插入一个新的整数x，并使得插入后仍保持非递减有序。要求x 插在值相等的整数后面。编写相应的函数实现。33、假设字符A,B,C,D,E,F的使用频率分别是0.07,0.09,0.12,0.22,0.23,0.27，写出A,B,C,D,E,F的Huffman（哈夫曼）编码。34、一颗二叉树的中序序列和后序序列分别是DCBAEFG和DCBGFEA, 请画出该二叉树并给出先序序列。35、设有一个输入数据的序列是 46, 25, 78, 62, 12, 37, 70, 29 , 试画出从空树起，逐个输入各个数据而生成的二叉搜索树。数据结构模拟试卷二 答案一、【单项选择题】(本大题共10小题，每小题2分，共20分)题号12345678910答案CAAADBCDDC二、【判断题】(本大题共10小题，每小题2分，共20分)题号11121314151617181920答案FFFFFTFTFF三、【填空题】（本大题共10小空，每小空2分，共20分）21、( n )；22、( n/2 )；23、( 7 )；24、( n2+2n3+.+(m-1)nm+1 )；25、( 只有根节点的二叉树 )；26、( 9 )；27、( 1000000 )；28、( 大顶 )；29、( 顺序 )；30、( ni1 )；四、【应用题】（本大题共5小题，每小题8分，共40分）31、标准答案：二叉树图形如下图1：图1 二叉树的不同形态复习范围或考核目标：课件第六章第四节。32、标准答案：插入函数如下： void InsertSort (int A , int m , int & n , int x) if (nm) int I,j ; for (i=0 ; in&Ai=I ; j- )Aj+1 = A j ; A I =x ; n+; elsecerr”数组已满，不能插入！”=2B K=3C K=4D K=5二、【判断题】(本大题共10小题，每小题2分，共20分)正确的填T，错误的填F，填在答题卷相应题号处。11、树的父链表示就是用数组表示树的存储结构。 （ ）12、栈和队列逻辑上都是线性表。 （ ）13、单链表从任何一个结点出发，都能访问到所有结点。 （ ）14、AOE网中，只有一个入度为0的顶点（起始点），只有一个出度为0的顶点（结束点）。 （ ）15、关键路径可能不只一条，但缩短某一关键路径一定能够缩短工期。 （ ）16、有向图的邻接矩阵一定不是对称的。（ ）17、在AOE网中，关键路径是唯一的。（ ）18、若将一株树转换成二叉树，则该二叉树的根结点一定没有右子树。（ ）19、索引顺序存取方法ISAM是一种专门为磁盘存取设计的索引顺序文件的组织方法。（ ）20、基数分类只适用于以数字为关键字的情形，不适用以字符串为关键字的情形。（ ）三、【填空题】（本大题共10小空，每小空2分，共20分）请将答案填写在答题卷相应题号处。21、数据结构算法中，通常用时间复杂度和（ ）两种方法衡量其效率。22、若频繁地对线性表进行插入与删除操作，该线性表应采用（ ）存储结构。23、（ ）链表从任何一个结点出发，都能访问到所有结点。24、某带头结点的单链表的头指针head，判定该单链表非空的条件（ ）。25、已知指针p指向单链表中某个结点，则语句p-next=p-next-next的作用是（ ）。26、在栈的顺序实现中，栈顶指针top，栈为空条件（ ）。27、在长度为n的循环队列中，删除其节点为x的时间复杂度为（ ）。28、有三个结点的二叉树，最多有（ ）种形状。29、深度为90的满二叉树，第11层有（ ）个结点。30、设有10个值，构成哈夫曼树，则该哈夫曼树共有（ ）个结点。四、【应用题】（本大题共5小题，每小题8分，共40分）请将答案填写在答题卷相应题号处。31、已知一棵二叉树的先序序列是ABCDEFG，中序序列为CBEDAFG，请构造出该二叉树。32、有一组关键码序列（38，19，65，13，49，41，1，73），采用冒泡排序方法由小到大进行排序，请写出每趟排序的结果。33、设图G，V1，2，3，4，5，6，E=，。画出该图，并写出所有的拓扑序列。34、一个一维整数数组Am中有n (nm)个非空整数，它们相继存放于数组的前端并已按非递减顺序排列，要求删除数组中多余的值相等的整数（只保留第一次出现的那个整数）。编写相应的函数实现。35、试编写一个函数，在一个顺序表A中查找出具有最大值和最小值的整数。函数的原型如下所示，原型的参数表中给出顺序表对象为A，通过算法执行，从参数表中的引用参数Max中得到表中的最大整数，Min中得到表中的最小整数。注意，函数中可使用顺序表的如下两个公有函数： int Length( ); 求表的长度； int getData(int k); 提取第k个元素的值。 #include “SeqList.h”template void FindMaxMin(SeqList& A, int& Max, int& Min);数据结构模拟试卷三 答案一、【单项选择题】(本大题共10小题，每小题2分，共20分)题号12345678910答案CCAAACCBCC二、【判断题】(本大题共10小题，每小题2分，共20分)题号