《数据构造模拟试卷和答案_2.docx》由会员分享，可在线阅读，更多相关《数据构造模拟试卷和答案_2.docx（17页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据构造模拟试卷和答案北京语言大学网络教育学院（数据构造）模拟试卷一注意：1.试卷保密，考生不得将试卷带出考场或撕页，否则成绩作废。请监考教师负责监督。2.请各位考生注意考试纪律，考试作弊全部成绩以零分计算。3.本试卷满分100分，答题时间为90分钟。4.本试卷分为试题卷和答题卷，所有答案必须答在答题卷上，答在试题卷上不给分。一、【单项选择题】(本大题共10小题，每题2分，共20分)在每题列出的四个选项中只要一个选项是符合题目要求的，请将正确选项前的字母填在答题卷相应题号处。1、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则采用存储方式最节省时间。A顺序表B双链表
2、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作为两个栈
3、S1和S2的共用存储构造，对任何一个栈，只要当Sn全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是。AS1的栈底位置为0，S2的栈底位置为nBS1的栈底位置为1，S2的栈底位置为n/2CS1的栈底位置为0，S2的栈底位置为n1DS1的栈底位置为0，S2的栈底位置为n/27、对一棵二叉排序树进行遍历，能够得到该二叉树的所有结点按值从小到大排列的序列。A前序B后序C中序D按层次8、在下列排序算法中，算法可能会出现下面情况：在最后一趟开场之前，所有元素都不在其最终的位置上。A堆排序B冒泡排序C快速排序D插入排序9、采用邻接表存储的图的广度优先算法类似于二叉树的。A先序遍历B中序遍历C后序遍历D
4、层次遍历10、具有6个顶点的无向图至少应有条边才能保证图的连通性。A4B5C6D7二、【判定题】(本大题共10小题，每题2分，共20分)正确的填T，错误的填F，填在答题卷相应题号处。11、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。12、任何二叉树都唯一对应一个森林，反之亦然。13、有向图的邻接矩阵一定是对称的。14、线性表的链式存储构造优于顺序存储构造。15、关键途径可能不只一条，但缩短某一关键途径一定能够缩短工期。16、直接选择排序是一种不稳定的排序方法。17、顺序表用一维数组作为存储构造，因而顺序表是一维数组。18、栈和队列都是顺序存取的的线性表，但它们对存取位置
5、的限制不同。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层满
6、二叉树中节点总数为。28、从树中一个结点到另一个结点之间的分支构成这两个结点之间的。29、在无向图中，若从顶点A到顶点B存在，则称A与B之间是连通的。30、若图的邻接矩阵是对称矩阵，则该图一定是。四、【应用题】本大题共5小题，每题8分，共40分请将答案填写在答题卷相应题号处。31、已知序列12，4，17，10，7，30，用直接选择排序法对其进行递增排序，写出每一趟的排序结果。32、单链表结点的类型定义如下：typedefstructLNodeintdata;structLNode*next;LNode,*Linklist;写一算法，将带头结点的有序单链表A和B合并成一新的有序表C。注：不毁坏A
7、和B的原有构造33、已知一棵非空二叉树，其按中序和后序遍历的结果分别为：中序：CGBAHEDJFI后序：GBCHEJIFDA请画出这棵二叉树，并写出其前序遍历的结果。34、已知字符：C1，C2，C3，C4，C5，C6的权分别为：17，5，16，4，8，11，请构造相应的赫夫曼树，并给出相应字符的赫夫曼编码。35、已知如下列图所示二叉树，分别写出其前序、中序和后序序列。（数据构造）模拟试卷一答案一、【单项选择题】(本大题共10小题，每题2分，共20分)二、【判定题】(本大题共10小题，每题2分，共20分)三、【填空题】本大题共10小空，每小空2分，共20分21、(运算)；22、(s-next=p
8、-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=(Linkli
9、st)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;elsepc-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;温习范围
10、或考核目的：课件第二章第三节。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;i