数据结构模拟试卷及答案.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、若线性表中采用二分查找法查找元素，该线性表应该（ ）。A 元素按值有序B 采用顺序存储结构C 元素按值有序，且采用顺序存储结构D 元素按值有序，且采用链式存储结构7、对待排序数据的初始状态不作任何要求的排序方法有（ ）。A 插入和快速排序B 插入和归并排序C 归并和快速排序D 归并和选择排序8、已知数据表A中每个元素距其最终位置不远，则采用（ ）排序算法最节省时间。A 堆排序B 插入排序C 快速排序D 选择排序9、以下哪一个不是队列的基本运算？（ ）A 从队尾插入一个新元素B 从队列中删除第i个元素C 判断一个队列是否为空D 读取队头元素的值10、广度优先遍历类似于二叉树的（ ）。A 先序遍历B 中序遍历C 后序遍历D 层次遍历二、【判断题】(本大题共10小题，每小题2分，共20分)正确的填T，错误的填F，填在答题卷相应题号处。11、线性表的逻辑顺序与物理顺序总是一致的。（ ）12、在链式存储的栈的头部必须要设头结点。（ ）13、在二叉树中插入结点，则该项二叉树便不再是二叉树。（ ）14、由二叉树结点的先序序列和后序序列可以唯一确定一棵二叉树。（ ）15、栈和队列也是线性表。如果需要，可对它们中的任一元素进行操作。 （ ）16、有向图的邻接矩阵一定不是对称的。（ ）17、在AOE网中，关键路径是唯一的。（ ）18、若将一株树转换成二叉树，则该二叉树的根结点一定没有右子树。（ ）19、索引顺序存取方法ISAM是一种专门为磁盘存取设计的索引顺序文件的组织方法。（ ）20、基数分类只适用于以数字为关键字的情形，不适用以字符串为关键字的情形。（ ）三、【填空题】（本大题共10小空，每小空2分，共20分）请将答案填写在答题卷相应题号处。21、n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为（ ）。22、将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（ ）。23、设二叉树中结点的两个指针域分别为lchild和rchild，则判断指针变量p所指向的结点为叶子结点的条件是（ ）。24、设一棵二叉树的前序序列为ABC，则有（ ）种不同的二叉树可以得到这种序列。25、为了给n个字母编码而建立起来的Huffman树一共有（ ）个结点。26、n个顶点的连通图用相邻矩阵表示时，该矩阵至少有（ ）个非零元素。27、对于一个具有n个顶点和e条边的无向图，在其对应的邻接表中，所含边结点有（ ）个。28、冒泡排序在最好情况下的元素交换次数为（ ）。29、由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的外部路径权重为（ ）。30、栈是一种受限制的线性表，也叫LIFO结构，LIFO的含义是（ ）。四、【应用题】（本大题共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答案CDBCCCABBD二、【判断题】(本大题共10小题，每小题2分，共20分)题号11121314151617181920答案FFFFFFFTTF三、【填空题】（本大题共10小空，每小空2分，共20分）21、 ( O(n2) )； 22、 ( n )；23、 ( p-lchild = NULL & p-rchild = NULL； )；24、 ( 5 )；25、 ( 2n1 )；26、 ( n1 )；27、 ( 2e )；28、 ( 0 )；29、 ( 71 )；30、 ( 后进先出 )；四、【应用题】（本大题共5小题，每小题8分，共40分）31、考核排序方法，参考教材“第10章 内部排序”。32、考核有序单链表合并，参考教材“第2章 线性表”。33、考核非空二叉树的先序、中序、后序遍历，参考教材“第6章 树和二叉树”。34、考核根据权值构造霍夫曼树及霍夫曼编码，参考教材“第6章 树和二叉树”。35、考核已知二叉树结构，写出其前序、中序和后序序列。参考教材“第6章 树和二叉树”。北京语言大学网络教育学院数据结构模拟试卷二注意： 1.试卷保密，考生不得将试卷带出考场或撕页，否则成绩作废。请监考老师负责监督。2.请各位考生注意考试纪律，考试作弊全部成绩以零分计算。3.本试卷满分100分，答题时间为90分钟。4.本试卷分为试题卷和答题卷，所有答案必须答在答题卷上，答在试题卷上不给分。一、【单项选择题】(本大题共10小题，每小题2分，共20分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在答题卷相应题号处。1、在一个图中，所有顶点的度数之和等于图的边数的（ ）倍。A 1/2B 1C 2D 42、采用顺序查找方法查找长度为n的线性表，平均查找长度为（ ）。A nB n/2C (n+1)/2D (n-1)/23、线性链表不具有的特点是（ ）。A 随机访问B 不必事先估计所需存储空间大小C 插入与删除时不必移动元素D 所需空间与线性表长度成正比4、删除长度为n的非空顺序表的第i个数据元素之前需要移动表中（ ）个数据元素。A n-iB n+iC n-i+1D n-i-15、任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（ ）。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、在外部分类中使用K路平衡归并，采用选择树法时,归并效率与K有关。（ ）13、对于n个记录的集合进行归并分类，最坏情况下所需要时间为O(n)。 （ ）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)个非空整数，它们相继存放于数组的前端并已按非递减顺序排列，在数组A 中插入一个新的整数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答案CCAAACCDDB二、【判断题】(本大题共10小题，每小题2分，共20分)题号11121314151617181920答案FFFTFTFTFF三、【填空题】（本大题共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、考核根据二叉树中序遍历的结果，画出二叉树可能的形态。参考教材“第6章 树和二叉树”。32、考核数组元素的插入。参考教材“第5章 数组和广义表”。33、考核霍夫曼编码，参考教材“第6章 树和二叉树”。34、考核二叉树的先序、中序、后序遍历，参考教材“第6章 树和二叉树”。35、考核二叉搜索树，参考教材“第6章 树和二叉树”。北京语言大学网络教育学院数据结构模拟试卷三注意： 1.试卷保密，考生不得将试卷带出考场或撕页，否则成绩作废。请监考老师负责监督。2.请各位考生注意考试纪律，考试作弊全部成绩以零分计算。3.本试卷满分100分，答题时间为90分钟。4.本试卷分为试题卷和答题卷，所有答案必须答在答题卷上，答在试题卷上不给分。一、【单项选择题】(本大题共10小题，每小题2分，共20分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在答题卷相应题号处。1、数据结构在计算机内存中的表示是指（ ）。A 数据的存储结构B 数据结构C 数据的逻辑结构D 数据元素之间的关系2、若不带头结点的单循环链表的头指针为head，则该链表只有一个结点的判定条件是（ ）。A head=NULLB head-next=NULLC head!=NULLD head-next=head3、设listarraysize为一个顺序存储的栈, 变量top指示栈中第一个空闲位置, 栈为空的条件是（ ）。A top=-1 B top=0C top=sizeD top=size-14、在长度为n的顺序表的第i个位置上插入一个元素（1 i n+1），元素的移动次数为（ ）。A ni+1B niC iD i15、在数据结构中，与所使用的计算机无关的是数据的（ ）结构。A 逻辑B 存储C 逻辑和存储D 物理6、一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是（ ）。A edcbaB decbaC dceabD abcde7、若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为（ ）。A 4B 5C 8D 98、由同一关键字集合构造的各棵二叉排序树（ ）。A 其形态不一定相同，但平均查找长度相同。B 其形态不一定相同，平均查找长度也不一定相同。C 其形态均相同，但平均查找长度不一定相同。D 其形态均相同，平均查找长度也都相同。9、具有n个顶点的无向连通图最少有（ ）条边。A nB n+1C n-1D 2n10、若某文件经内部排序得到100个初始归并段，若使用K路归并三趟完成，则（ ）。A K=2B K=3C K=4D K=5二、【判断题】(本大题共10小题，每小题2分，共20分)正确的填T，错误的填F，填在答题卷相应题号处。11、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。（ ）12、任何二叉树都唯一对应一个森林，反之亦然。 （ ）13、有向图的邻接矩阵一定是对称的。 （ ）14、线性表的链式存储结构优于顺序存储结构。 （ ）15、关键路径可能不只一条，但缩短某一关键路径一定能够缩短工期。 （ ）16、顺序存储方式只能用于存储线性结构。 （ ）17、用循环链表作为存储结构的队列就是循环队列。 （ ）18、倒排文件的主要优点为便于节省空间。 （ ）19、一组记录的关键字为（46,79,56,38,40,84），则利用快速排序的方法，以第一个记录为基准元素得到的一次划分结果为40,38,46,56,79,84。 （ ）20、算法分析的目的是分析算法的易读性。 （ ）三、【填空题】（本大题共10小空，每小空2分，共20分）请将答案填写在答题卷相应题号处。21、图的逆邻接表存储结构只适用于（ ）图。22、设在等概率情形下, 对有127个元素的顺序表进行删除, 平均需要移动（ ）个元素。23、图的深度优先遍历序列（ ）惟一的。24、一棵高度为5的二叉树中最少含有（ ）个结点，最多含有（ ）个结点。25、在单链表中，若要在指针p所指结点后插入指针s所指结点，则需要执行下列两条语句：s-next=p-next；（ ）。26、一棵高度为h的满k叉树有如下性质：第h层上的结点都是叶结点, 其余各层上每个结点都有k棵非空子树, 如果按层次自顶向下, 同一层自左向右, 顺序从1开始对全部结点进行编号，编号为i的结点的第m个孩子结点(若存在)的编号是（ ）。27、在有序表A120中，采用折半查找算法查找元素值等于A12的元素，所比较过的元素的下标依次为（ ）。28、表示图的三种常用的存储结构为( )、( )和十字链表。四、【应用题】（本大题共5小题，每小题8分，共40分）请将答案填写在答题卷相应题号处。29、已知一棵二叉树的先序序列是ABCDEFG，中序序列为CBEDAFG，请构造出该二叉树。30、有一组关键码序列（38，19，65，13，49，41，1，73），采用冒泡排序方法由小到大进行排序，请写出每趟排序的结果。31、设图G，V1，2，3，4，5，6，E=，。画出该图，并写出所有的拓扑序列。32、一个一维整数数组Am中有n (nm)个非空整数，它们相继存放于数组的前端并已按非递减顺序排列，要求删除数组中多余的值相等的整数（只保留第一次出现的那个整数）。编写相应的函数实现。33、试编写一个函数，在一个顺序表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答案ADBAACCBCC二、【判断题】(本大题共10小题，每小题2分，共20分)题号11121314151617181920答案TTFFFFFFFF三、【填空题】（本大题共10小空，每小空2分，共20分）21、 ( 有向 )；22、 ( 63 )；23、 ( 不是 )；24、 ( 5 )；( 31 )；25、 ( p-next=s )；26、 ( (i-1)*k + m + 1 )；27、 ( 10,15,12 )；28、 ( 邻接矩阵 )； ( 邻接表 )；四、【应用题】（本大题共5小题，每小题8分，共40分）29、考核根据二叉树先序、中序遍历的结果，构造二叉树。参考教材“第6章 树和二叉树”。30、考核冒泡排序，参考教材“第10章 内部排序”。31、考核图及拓扑序列。参考教材“第7章 图”。32、考核数组元素的比较和删除。参考教材“第5章 数组和广义表”。33、考核顺序表中查找最大值和最小值。参考教材“第9章 查找”。北京语言大学网络教育学院数据结构模拟试卷四注意： 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下面关于线性表的叙述中，错误的为（ ）。A 顺序表是使用一维数组实现的线性表 B 顺序表必须占用一片连续的存储单元C 顺序表的空间利用率高于链表D 在链表中，每个结点只有一个链域5一棵树的广义表表示为a(b,c(e,f(g),d)，当用左子女-右兄弟链表表示时，右指针域非空的结点个数为（ ）。A 1B 2C 3D 46若需要利用形参直接访问实参，则应把形参变量说明为（ ）参数。 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.在单链表P指针所指结点之后插入S结点的操作是：P-next= S ; S- next = P-next。 （ ）14.假设B是一棵树，B是对应的二叉树。则B的后根遍历相当于B的中序遍历。（ ）15.对于任何待排序序列来说，快速排序均快于起泡排序。 （ ）16.直接选择排序是一种不稳定的排序方法。 （ ）17.顺序表用一维数组作为存储结构，因此顺序表是一维数组。 （ ）18.栈和队列都是顺序存取的的线性表，但它们对存取位置的限制不同。 （ ）19.闭散列法通常比开散列法时间效率更高。 （ ）20.一棵m阶B树中每个结点最多有m个关键码，最少有2个关键码。 （ ）三、【填空题】（本大题共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根据下面的字母/频率表构造一棵Huffman树, 并给出各字母的Huffman编码。 A B C D E F G H 25 10 36 4 5 6 11 3 32已知哈希表地址空间为010，哈希函数为H(k)=k%11，采用线性探查法处理冲突。将关键字8，12，18，25，40，16，7，17，100依次存入该散列表中，给出最后的结果散列表，并求出在等概率下的平均查找长度。搜索成功的平均搜索长度ASLsucc 是指搜索到表中已有表项的平均探查次数,它是找到表中各个已有表项的探查次数的平均值。33对下列数据表，写出采用Shell排序的每一趟的结果，增量序列为7，3，1。9, 8, 7, 6, 5, 4, 3, 2, 134设有一个关键码的输入序列 55， 88， 100， 120， 90， 150， 40， 20，95，从空树开始构造平衡二叉搜索树，画出每加入一个新结点时二叉树的形态。若发生不平衡，指明需做的平衡旋转的类型及平衡旋转的结果。35编写实现“直接插入排序”的子函数，入口参数是整型数组L 和数组长度n.数据结构模拟试卷四 答案一、【单项选择题】(本大题共10小题，每小题2分，共20分)题号12345678910答案CDBDCBCDDC二、【判断题】(本大题共10小题，每小题2分，共20分)题号11121314151617181920答案FFFTFTFTFF三、【填空题】（本大题共10小空，每小空2分，共20分）21、 ( 空间复杂度 )；22、 ( 链表 )；23、 ( 循环 )；24、 ( head-next!=Null )；25、 ( 删除p 的后继结点 )；26、 ( top=-1 )；27、 ( O(n) )；28、 ( 5 )；29、 ( 1024 )；30、 ( 19 )；四、【应用题】（本大题共5小题，每小题8分，共40分）31 考核“Huffman树和Huffman编码”，参考教材“第6章 树和二叉树”。32 考核“哈希表”，参考教材“第9章 查找”。33 考核“Shell排序”，参考教材“第10章 内部排序”。34 考核“构造平衡二叉搜索树”，参考教材“第9章 查找”。35 考核“直接插入排序”，参考教材“第10章 内部排序”。北京语言大学网络教育学院数据结构模拟试卷五注意： 1.试卷保密，考生不得将试卷带出考场或撕页，否则成绩作废。请监考老师负责监督。2.请各位考生注意考试纪律，考试作弊全部成绩以零分计算。3.本试卷满分100分，答题时间为90分钟。4.本试卷分为试题卷和答题卷，所有答案必须答在答题卷上，答在试题卷上不给分。一、【单项选择题】(本大题共10小题，每小题2分，共20分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在答题卷相应题号处。1程序段：sum=0; for (i=1;inext=p-next;p-next=s )；23、 ( 有序表 )；24、 ( 栈顶 )；25、 ( 1130 )；26、 ( 69 )；27、 ( 31 )；28、 ( 路径 )；29、 ( 路径 )；30、 ( 无向图 )；四、【应用题】（本大题共5小题，每小题8分，共40分）31 考核“顺序表和链表存储方式的区别”，参考教材“第2章 线性表”。32 考核“链表操作”，参考教材“第2章 线性表”。33 考核“最小生成树”，参考教材“第7章 图”。34 考核“二叉树的存储”，参考教材“第6章 树和二叉树”。35 考核“起泡排序”，参考教材“第10章 内部排序”。数据结构第一阶段导学资料一、本阶段学习内容概述本课程第一阶段学习的主要内容是第一章“绪论”和第二章“线性表”。第一章主要是为以后各章讨论的内容作基本知识的准备，介绍数据结构和算法等基本概念；第二章主要介绍了线性表的抽象数据类型的定义以及它的两种存储结构的实现。1、 第一章“绪论”数据是计算机操作对象的总称，它是计算机处理的符号的集合，集合中的个体为一个数据元素。数据元素可以是不可分割的原子，也可以由若干数据项合成，因此在数据结构中讨论的基本单位是数据元素，而最小单位是数据项。数据结构是由若干特性相同的数据元素构成的集合，且在集合上存在一种或多种关系。由关系不同可将数据结构分为四类：线性结构、树形结构、图状结构和集合结构。数据的存储结构是数据逻辑结构在计算机中的映象，由关系的两种映象方法可得到两类存储结构：一类是顺序存储结构，它以数据元素相对的存储位置表示关系，则存储结构中只包含数据元素本身的信息；另一类是链式存储结构，它以附加的指针信息（后继元素的存储地址）表示关系。数据结构的操作是和数据结构本身密不可分的，两者作为一个整体可用抽象数据类型进行描述。抽象数据类型是一个数学模型以及定义在该模型上的一组操作，因此它和高级程序设计语言中的数据类型具有相同含义，而抽象数据类型的范畴更广，它不局限于现有程序设计语言中已经实现的数据类型（它们通常被称为固有数据类型），但抽象数据类型需要借用固有数据类型表示并实现。抽象数据类型的三大要素为数据对象、数据关系和基本操作，同时数据抽象和数据封装是抽象数据类型的两个重要特性。算法是进行程序设计的另一不可缺少的要素。算法是对问题求解的一种描述，是为解决一个或一类问题给出的一种确定规则的描述。一个完整的算法应该具有下列五个要素：有穷性、确定性、可行性、有输入和有输出。一个正确的算法应对苛刻且带有刁难性的输入数据也能得出正确的结果，并且对不正确的输入也能做出正确的反映。算法的时间复杂度是比较不同算法效率的一种准则，算法时间复杂度的估算基于算法中基本操作的重复执行次数，或处于最深层循环内的语句的频度。算法空间复杂度可作为算法所需存储量的一种量度，它主要取决于算法的输入量和辅助变量所占空间，若算法的输入仅取决于问题本身而和算法无关，则算法空间复杂度的估算只需考察算法中所用辅助变量所占空间，若算法的空间复杂度为常量级，则称该算法为原地工作的算法。2、 第二章“线性表”线性表是 n(n0) 个数据元素的序列，通常写成( , , , )因此线性表中除了第一个和最后一个元素之外都只有一个前驱和一个后继。线性表中每个元素都有自己确定的位置，即位序，因此线性表也可以看成是由 n 个 (i,) 构成的集合。n=0时的线性表称为空表，它是线性表的一种特殊状态，因此在写线性表的操作算法时一定要考虑你的算法对空表的情况是否也正确。顺序表是线性表的顺序存储结构的一种别称。它的特点是以存储位置相邻表示两个元素之间的前驱后继关系。因此，顺序表的优点是可以随机存取表中任意一个元素，其缺点是每作一次插入或删除操作时，平均来说必须移动表中一半元素。常应用于主要是为查询而很少作插入和删除操作，表长变化不大的线性表。 链表是线性表的链式存储结构的别称。它的特点是以指针指示后继元素，因此线性表的元素可以存储在存储器中任意一组存储单元中。它的优点是便于进行插入和删除操作，但不能进行随机存取，每个元素的存储位置都存放在其前驱元素的指针域中，为取得表中任意一个数据元素都必须从第一个数据元素起查询。由于它是一种动态分配的结构，结点的存储空间可以随用随取，并在删除结点时随时释放，以便系统资源更有效地被利用。这对编制大型软件非常重要，作为一个程序员在编制程序时必须养成这种习惯。 由于线性表是一种应用很广的数据结构，链表的操作又很灵活，因此在C+等面向对象的程序设计语言中都已为程序员提供了链表类，读者在使用时应该首先充分了解它的操作接口。在自己实现链表类时，正如课程中所述，应该为链表结构设置合适的数据成员和恰当的操作接口，以便使每个基本操作的时间复杂度在尽可能低的级别上。二、重难点讲解链表是本章的重点和难点。扎实的指针操作和内存动态分配的编程技术是学好本