北京语言大学网络教育学院《数据结构》模拟试卷五注意：1.试卷保密，考生不得将试卷带出考场或撕页，否则成绩作废。请监考老师负责监督。2.请各位考生注意考试纪律，考试作弊全部成绩以零分计算。3.本试卷满分100分，答题时间为90分钟。4.本试卷分为试题卷和答题卷，所有答案必须答在答题卷上，答在试题卷上不给分。一、【单项选择题】(本大题共10小题，每小题2分，共20分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在答题卷相应题号处。1．程序段：sum=0;for(i=1;i<n*n;i++)Sum++;的平均情况下时间代价的表达式是（）。[A](1)[B](n)[C](n2)[D](nlogn)2．数据结构通常是研究数据的（）及它们之间的联系。[A]存储和逻辑结构[B]存储和抽象[C]理想和抽象[D]理想与逻辑3．将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子的编号为（）。[A]98[B]99[C]50[D]484．在有n个叶结点的Huffman树中,其结点总数为（）。[A]2n-1[B]2n+1[C]2n[D]不确定5．设有100个元素，用折半查找法进行查找时，最大比较次数是（）。[A]25[B]50[C]10[D]76．快速排序在（）情况下最易发挥其长处。[A]被排序数据中含有多个相同排序码[B]被排序数据已基本有序[C]被排序数据完全无序[D]被排序数据中最大值和最小值相差悬殊7．由两个栈共享一个向量空间的好处是（）。[A]减少存取时间,降低下溢发生的机率[B]节省存储空间,降低上溢发生的机率[C]减少存取时间,降低上溢发生的机率[D]节省存储空间,降低下溢发生的机率8．对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为（）。[A]顺序表[B]用头指针表示的循环单链表[C]用尾指针表示的循环单链表[D]单链表9．图的深度优先遍历类似于二叉树的（）。[A]先序遍历[B]中序遍历[C]后序遍历[D]层次遍历10．设长度为n的链队列用单循环链表表示，若只设头指针，则入队操作的时间复杂度为（）。[A]O(1)[B]O(log2n)[C]O(n)[D]O(n2)二、【判断题】(本大题共10小题，每小题2分，共20分)正确的填T，错误的填F，填在答题卷相应题号处。11．树的父链表示就是用数组表示树的存储结构。（）12．栈和队列逻辑上都是线性表。（）13．单链表从任何一个结点出发，都能访问到所有结点。（）14．AOE网中，只有一个入度为0的顶点（起始点），只有一个出度为0的顶点（结束点）。（）15．关键路径可能不只一条，但缩短某一关键路径一定能够缩短工期。（）16．删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。（）17．一般树和二叉树的结点数目都可以为0。（）18．堆栈在数据中的存储原则是先进先出。（）19．线性表的顺序存储结构是通过数据元素的存储地址直接反映数据元素的逻辑关系。（）20．非空线性表中任意一个数据元素都有且仅有一个直接后继元素。（）三、【填空题】（本大题共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．一棵具有５层满二叉树中节点总数为（）。28．从树中一个结点到另一个结点之间的分支构成这两个结点之间的（）。29．在无向图中，若从顶点A到顶点B存在（），则称A与B之间是连通的。30．若图的邻接矩阵是对称矩阵，则该图一定是（）。四、【应用题】（本大题共5小题，每小题8分，共40分）请将答案填写在答题卷相应题号处。31．简述顺序表和链表存储方式的特点。32．对链表设置头结点的作用是什么？（至少说出两条好处）33．一个带权无向图如下所示,画出该图的一棵最小生成树，该图最小生成树是否唯一，为什么？34．若用二叉链表作为二叉树的存储表示，试编写算法统计二叉树中叶结点的个数。35．编写实现“起泡排序”的子函数，入口参数是整型数组L[]和数组长度n.