一、 判断题 1、 记录是数据处理的最小单位。 ( ) 2. 两维数组是一种非线性结构。( ) 3. 在某棵二叉树的一种序列中，如果发现其中每一结点的左孩子均是其前趋，则可判断定这种序列为中序序列( )。 4. 前序遍历和后序遍历结果相同的二叉树为只有根结点的二叉树( )。5. 在任一有向图中，所有顶点的入度之和一定等于所有顶点的出度之和( )。二、单选题 1. 若要求能快速地实现在链表的末尾插入结点和删除第一个结点的运算，则选择( )最合适。 A) 单链表 B) 带尾指针的单循环链表 C) 双链表 D) 双循环链表 2. 利用 n 个值生成的哈夫曼树中共有()个结点。 A.n B.n+1 C.2n D.2n-13. 在各种排序方法中，从未排序序列中依次取出元素与已排序序列(初始时为空)中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为( )。 A)希尔排序 B)冒泡排序 C)插入排序 D)选择排序4.一个栈的入栈序列是 a,b,c,d, 则下列序列中不可能的输出序列是( )。 A)acbd B)dcba C)acdb D)dbac5. ( )不是队列的基本运算。A. 判断一个队列是否为空 B. 从队头删除一个元素C. 在队列第 i 个元素之后插入一个元素 D. 读取队头元素的值6. 一个队列的入列序列是 1,2,3,4，则队列的输出序列是( )。A.4,3,2,1 B.3,2,4,1 C.1,4,3,2 D.1,2,3,47. 广义表((a), (b))的表尾是( )。A.( ) B.b C. ((b)) D. (b) 8. 若无向图中有 n 个结点，e 条边，则它的邻接表需要( )个表结点。A. n B. 2n C. 2e D. e9. 常对数组进行的两种基本操作是( )。A. 查找和插入 B. 插入和修改C. 查找和修改 D.建立和删除 10. 已知某二叉树的先序遍历为 A，B，D，C，E，则它可能的中序遍历序列为( )。 A.B，C，A，D，E B.C，B，A，D，E 1/4 C.B，D，A，E，C D.B，E，A，C，D 11. 下面关于图的存储的叙述中，( )是正确的。 A.用邻接表存储图，占用的存储空间数与图中结点个数有关，与边数无关B.用邻接表存储图，占用的存储空间数与图中边数有关，与结点个数无关C.用邻接矩阵法存储图，占用的存储空间数与图中结点个数有关，与边数无关D.用邻接矩阵法存储图，占用的存储空间数与图中边数有关，与结点个数无关12. 在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是( )。A. 冒泡排序 B. 快速排序C. 直接插入排序 D. 简单选择排序三、填空题 1.数据的逻辑结构可分为____和____两大类。 2.数据的存储结构被分为____，_____，_____和____4 种。 3.在下面的程序段中，s=s+p 语句被执行次数为____，p*=j 语句的执行次数为____,该程序的复杂度为____。 int i=0，s=0; while(++i<=n) { int p=1; for(int j=1;j<=i;j++) p*=j; s=s+p; } 4.一种数据结构的元素集合 K 和它的二元关系 R 为:K={a,b,c,d,e,f,g,h} R={<a,b>，<b,c>，<c,d>，<d,e>，<e,f>，<f,g>，<g,h>} 则该数据结构具有____结构。 5.线性表的两种存储结构分别为____和____。 6.栈又称为________________的线性表。四、解答题 1.简述线性结构，树形结构，网状结构的不同。 2.简述算法复杂度的评价方法。 3.设有两个算法在同一台机器上运行，其执行时间分别为 100n2 和 2n,要使前者快于后者，n 至少为多大, 4.在顺序表中插入和删除一个结点需平均移动多少个结点，具体移动的次数取决于哪些因素,5、在单链表，双向链表和单循环链表中，若仅知道指针 p 指向某结点，不知道头指针，能否将 p从相应的链表中删去,若可以，其时间复杂度分别为多少, 四、算法题 1. 下面算法的功能是：.设计一个算法，统计出二叉树中等于给定值 x 的结点个数，该统计值由变量 k 带回(k 的初值为 0)。请填空完成该程序。2/4 void count1(bitreptr r，datatype x，int &k) {if (（1）______________) {if(r—>data==x) （2）______________; count1(r—>lchild，x，k); count1(r—>rchild，x，k); } } 2. 阅读如下算法，给出该算法的功能。int SquareSum(int n) { if(n==0)return 0; else return n*n+Square(n-1); } 《数据结构与算法》模拟题五一、判断题 ×××√√ 二、单选题 （共 12 题,共 24 分）1. B 2. D 3.C 4.D 5. C 6. D 7. C 8. C 9.D 10.A 11.B 12.C三、填空题 1.线形;非线形 2.顺序;链式;索引;散列存储结构 3. n;n(n+1)/2;O(n) 4.线性 5.顺序;链式6.后进先出四、解答题 1、线性结构是指数据元素之间存在一对一的关系。 树型结构是指元素之间存在一对多的关系。 图或网状结构是指数据元素之间存在多对多的关系。 2、算法的复杂度分析可分为时间复杂度和空间复杂度。时间复杂度以基本操作重复执行的次数为算法的时间量度。空间复杂度指算发所存储空间的量度。 3/4 3.要使 100n2 快于 2n 时, 必须满足 100n2(2n, 可以算出 n 的值为 15 时, 2n 恰好大于 100n2, 所以至少应该是 15. 4.插入一个结点要平均移动 n/2 结点;删除一个结点要平均移动(n-1)/2 结点;具体的移动次数取决于 n 的大小和插入或删除的位置这两个因素。 5、(在单链表中不能删除，而在双链表和单循环莲表中可以删除 p 结点。双向链表的删除 p 结点的时间复杂度为 O(1)，单循链表删除 p 结点的时间复杂度为 O(1)五、算法题 1.（1） r!=NULL;(2)k++;2. 计算出返回 1 至 n 之间的所有整数平方和4/4