数据结构与算法分析模拟试卷.docx

四川大学数据结构与算法分析课程考试模拟试卷模拟试卷一一、 单项选择题（每题2分，共20分）.以下数据结构中哪一个是线性结构？（）A.有向图B.队列 C.线索二叉树D.B树.在一个单链表HL中，假设要在当前由指针p指向的结点后面插入一个由q指向的结点， 那么执行如下（）语句序列。A. p=q; p-next=q;B. p-next=q; q-next=p;C. p-next=q-next; p=q;D. q-next=p-next; p-next=q;3 .以下哪一个不是队列的基本运算？（）A.在队列第i个元素之后插入一个元素B.从队头删除一个元素C.判断一个队列是否为空D.读取队头元素的值.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成 （）个不同的字符串？A. 14B. 5C. 6D. 85.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为（）o6.6.A. 11 B. 35 C. 19 D. 53以下68题基于图1。该二叉树结点的前序遍历的序列为（)A. E、 G、 F、 A、 C、 D、 BB. E、 A、 G、 C、 F、 B、 DC. E、 A、 C、 B、 D、 G、 FD. E、 G、 A、 C、 D、 F、 B该二叉树结点的中序遍历的序列为（A. A、 B、 C、 D、 E、 G、 FB. E、 A、 G、 C、 F B、 D)C. E、 A、 C、 B、 D、 G、 FE. B、 D、 C、 A、 F、 G、 E8.该二叉树的按层遍历的序列为（）o三、1.运算题(每题6分，共24分)一个6x5稀疏矩阵如右所示，试:7 .二叉树是指度为2的 树。一棵结点数为N的二叉树，其所有结点的度的总和是 o.对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个 o对一棵由算术表达式组成的二叉语法树进行后序遍历得到的结点序列是该算术表达式的.对于一棵具有n个结点的二叉树，用二叉链表存储时，其指针总数为 个,其中 个用于指向孩子，个指针是空闲的。8 .假设对一棵完全二叉树从0开始进行结点的编号，并按此编号把它顺序存储到一维数组A 中，即编号为0的结点存储到A0中。其余类推，那么A i 元素的左孩子元素为, 右孩子元素为，双亲元素为 O.在线性表的散列存储中，处理冲突的常用方法有 和9 .当待排序的记录数较大，排序码较随机且对稳定性不作要求时，宜采用排序；当待排序的记录数较大，存储空间允许且要求排序是稳定时，宜采用排序。(1)写出它的三元组线性表;(2)给出三元组线性表的顺序存储表示。000010 设有一个输入数据的序列是 46,25,78,62, 12,80 ,试画出从5000空树起，逐个输入各个数据而生成的二叉搜索树。11 对于图6所示的有向图假设存储它采用邻接表，并且每个顶点邻L0070接表中的边结点都是按照终点序号从小到大的次序链接的，试写出：(1)从顶点出发进行深度优先搜索所得到的深度优先生成树；(2)从顶点出发进行广度优先搜索所得到的广度优先生成树；一个图的顶点集V和边集E分别为：V=1,2, 3,4, 5,6, 7;伞_E=, , , , , , , , , x) return 1; else return 0;指出该算法的功能；(2)该算法的时间复杂度是多少？2. 写出下述算法的功能：void AJ(adjlist GL, int i, int n) (Queue Q;InitQueue (Q);coutiadjvex;if(!visitedj) (coutjnext; )i i算法填空(共8分)如下为二分查找的非递归算法，试将其填写完整。Int Binsch(ElemType A ,int n,KeyType K) (int low=0;int high=n-l;while (low=high) int mid=；if (K=Amid.key) return mid; /查找成功，返回元素的下标 else if (Kmid.key)；/在左子表上继续查找else;/在右子表上继续查找)return -1;查找失败，返回-1）六、编写算法（共8分）HL是单链表的头指针，试写出删除头结点的算法。ElemType DeleFront(LNode * & HL)模拟试卷三参考答案一、 单项选择题(每题2分，共20分)l.B 2.A 3.B 4.C 5.D 6.B 7.D8.A9.D10.C二、 填空题(每空1分，共26分)1. 联系图(或图结构)2. 尾首3. top=04. O (1) O (n)5. 128441086. 337. 有序 n-18. 有序序列后缀表达式(或逆波兰式)9.10.11.2n n-12i+l开放定址法n+12i+2(i-l)/2链接法12.快速归并运算题(每题6分，共24分)1 .(1)(1,5,1),(32-D,(45-2),(5,1,5),(6,3,7)(3 分)(2)三元组线性表的顺序存储表示如图7示。2 .如图8所示。3 . DFS：BFS：.拓朴排序为：4 3 6 5 7 2 1三、 阅读算法(每题7分，共14分)(1)判断n是否是素数(或质数)(2) O ( Vh )2.功能为：从初始点环出发广度优先搜索由邻接表GL所表示的图。四、 算法填空(8分)(low+high)/2(low+high)/2high=mid-llow=mid+l编写算法(8分)ElemType DeleFront(LNode * & HL)if(HL=NULL)cerr空表next;ElemType temp=p-data;delete p;return temp;)模拟试卷四一、 单项选择题（每题2分，共20分）.以下数据结构中哪一个是线性结构？（）A.有向图B.栈 C.二叉树 D.B树.假设某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，那么采B.双链表D.单循环链表B.从队头删除一个元素用（）存储方式最节省时间。A.单链表C带头结点的双循环链表1 .以下哪一个不是队列的基本运算？（） A.在队列第i个元素之后插入一个元素C.判断一个队列是否为空C.判断一个队列是否为空D.读取队头元素的值2 .字符A、B、C、D依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以 组成（）个不同的字符串？A. 15B. 14C. 16D. 215 .由权值分别为476,2的叶子生成一棵哈夫曼树，它的带权路径长度为（）oA. 11 B. 37 C. 19 D. 536 .由权值分别为476,2的叶子生成一棵哈夫曼树，它的带权路径长度为（）oA. 11 B. 37 C. 19 D. 53以下68题基于下面的表达：假设某二叉树结点的中序遍历的序列为A、B、C、D、E、F、G,后序遍历的序列为B、D、C、A、F、G、E。7 .那么该二叉树结点的前序遍历的序列为（）.A. E、 G、 F、 A、 C、 D、 BC. E、 A、 C、 B D、 G、 F7 .该二叉树有（）个叶子。A. 3B. 2C. 58 .该二叉树的按层遍历的序列为（）A. E、 G、 F、 A、 C、 D、 BC. E、 A、 G、 C、 F、 B、 D9 .下面的二叉树中，（）不是完全二叉树。B.E、A、G、C、F、B、DD.E、G、A、C、D、F、BD. 4B. E、A、C、B、D、G、FD. E、G、A、C、D、F、BA.A.B.C.D.10.设有关键码序列(q, g, m, z, a),下面哪一个序列是从上述序列出发建的小根堆的结 果?()A. a, g , m, q, zB. a, g , m, z, qC. g , m, q, a, zD. g, m, a, q, z填空题(每空1分，共26分)1 .数据结构是指数据及其相互之间的 o当结点之间存在1对N (1： N)的联系时，称这种结构为 O. 一个广义表中的元素分为 元素和 元素两类。2 .对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为， 在表尾插入元素的时间复杂度为 o.向一个由HS指向的链栈中插入一个结点时p时，需要执行的操作是删除一个结点时，需要执行的操作是 (假设栈不空而且 无需回收被删除结点)。3 .栈又称为 表，队列又称为 表。4 .在稀疏矩阵所对应的三元组线性表中，每个三元组元素按 为主序、为辅序的次序排列。5 .假设一棵二叉树中只有叶子结点和左、右子树皆非空的结点，设叶结点的个数为K,那么左、 右子树皆非空的结点个数是 o.以折半(或二分)查找方法从长度为8的有序表中查找一个元素时，平均查找长度为6 .表示图的三种常用的存储结构为、和 o.对于线性表(78, 4, 56, 30, 65)进行散列存储时，假设选用H (K)=K %5作为散列函数，那么散列地址为0的元素有 个，散列地址为4的有 个。7 .在归并排序中，进行每趟归并的时间复杂度为，整个排序过程的时间复杂度为 ，空间复杂度为 O.在n个带权叶子结点构造出的所有二叉树中，带权路径长度最小的二叉树称为 o WPL 称为 o8 .在索引表中，假设一个索引项对应主表的一个记录，那么此索引为 索引，假设对应主表的假设干条记录，那么称此索引为 索引。二、 运算题(每题6分，共24分).写出以下中缀表达式的后缀形式：(1) 3X/(Y-2H)+12+X*(Y+3)1 .假定一棵二叉树广义表表示为a(b(c),d(e,D)，分别写出对它进行先序、中序、后序、按 层遍历的结果。先序：中序：后序：按层：2 .一个无向图的顶点集为a, b, c, d, e，其邻接矩阵如下所示(1)画出该图的图形；(2)根据邻接矩阵从顶点a出发进行深度优先遍历和广度优先遍历，写出相应的遍历序 列。3 .一个图的顶点集V和边集E分别为：V= 0,1,2, 3,4, 5,6, 7);E= (0, 1)8, (0, 2)5, (0, 3)2, (1,5)6, (2, 3)25, (2, 4) 13, (3, 5)9, (3, 6) 10,(4,6)4, (5, 7)20);按照普里姆算法从顶点0出发得到最小生成树，试写出在最小生成树中依次得到的各条边。三、 阅读算法(每题7分，共14分)void AE(Stack& S) InitStack(S);Push(S, 3);Push (S, 4);int x=Pop(S)+2*Pop (S);Push(S, x);int i,a5 = 2, 5, 8, 22, 15);for(i=0;i5;i+) Push(S, ai);while(!StackEmpty(S) coutPop(S)?;)该算法被调用后得到的输出结果为：1. int akm ( unsigned m, unsigned n ) if ( m = 0 ) return n+1;else if ( n - 0 ) return akm ( m-1, 1 );else return akm ( m-1, akm ( m, n-1 );)该函数执行的功能是什么？四、 算法填空(共8分)二叉搜索树的查找一非递归算法bool Find(BTreeNode* BST, ElemTypefe item)while(BST(!=NULL)if (item=) item = BST-data; 查找成功return true;else if(itemdata)BST=BST-;else BST=BST-;/whilereturn ; 查找失败)编写算法(共8分)用递归的算法编写出对存入在an+l数组中的n个有序元素进行二分(又称折半)查找 (假定a0单元不用)的程序。int halfsearch(SSTable *a, KeyType k,int low,int high)模拟试卷四参考答案一、 单项选择题(每题2分，共20分)l.B 2.C 3.A 4.B 5.B 6.C 7.A 8.C 9.C 10.B二、 填空题(每空1分，共26分)1 .联系树(或树结构)2 .单 (子)表3 . 0(n) 0(1)4 , p-next=HS;HS=pHS=HS-next5 .先进后出先进先出6 .行歹U7 . k-18 . 2.6259 .邻接矩阵邻接表边集数组10 .2111 . 0(n)0 (nlog2n) 0 (n)12 .哈夫曼树带权路径长度13 .稠密稀疏运算题(每题6分，共24分)1. (1) 3 X *Y 2 H*-/l +2)2 X Y 3 + * +2 .先序：a,b,c,d,e,f中序：c, b, a, e, d, f后序: c, b, e, f, d, a 按层：a,b,d,c,e,f3 . (1)该图的图形如图9示：(2)深度优先遍历序列为：abdce 广度优先遍历序列为：abedc4.普里姆:(0,3)2, (0,2)5, (0)8, (1,5)6, (3,6)10, (6,4)4, (5,7)20阅读算法(每题7分，共14分)3 .15 22 8 5 2 10.该函数的功能是:h + 1求.akm(m,n) = data left right false六、 编写算法(8分)递归算法：int halfsearch(SSTable *a, KeyType k, int low, int high) if (lowhigh)return 0;else int mid=(low+high)/2if EQ(k, amid. key) return mid;else if LT(k, amid. key) return halfsearch(a, k, low, mid-1);else return halfsearch(a, k, mid+1, high);模拟试卷五单项选择题（每题2分，共20分）1 .栈和队列的共同特点是（ ）oA.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2 .用链接方式存储的队列，在进行插入运算时（）.A.仅修改头指针B.头、尾指针都要修改C.仅修改尾指针D.头、尾指针可能都要修改3 .以下数据结构中哪一个是非线性结构？（）A.队列B.栈 C.线性表 D.二叉树A. 688B. 678 C. 692 D. 6964 .设有一个二维数组A词，假设A00存放位置在644（io）, A存放位置在 676（0）,每个元素占一个空间，问433（存放在什么位置？脚注（表示用10进制 表示。B.无序数据元素D.元素之间无联系的数据D. 2k-15 .树最适合用来表示（）oA.有序数据元素C.元素之间具有分支层次关系的数据6 .二叉树的第k层的结点数最多为（）.A. 2-1 B. 2K+1 C. 2K-1.假设有18个元素的有序表存放在一维数组A19中，第一个元素放Al中，现进行二 分查找，那么查找A 3的比拟序列的下标依次为（）A. 1, 2, 3B. 9, 5, 2, 3C.9, 5, 3D.9, 4, 2, 37 .对n个记录的文件进行快速排序，所需要的辅助存储空间大致为A. 0(1) B. 0 (n) C. 0 (log2n) D. 0 (n2)8 .对于线性表(7, 34, 55, 25, 64, 46, 20, 10)进行散列存储时，假设选用H (K) 二K%9作为散列函数，那么散列地址为1的元素有()个，A. 1B. 2C. 3D. 49 .设有6个结点的无向图，该图至少应有()条边才能确保是一个连通图。A.5B.6C.7D.8填空题(每空1分，共26分)1 .通常从四个方面评价算法的质量：、和 o. 一个算法的时间复杂度为(+21og2+14)2,其数量级表示为 o2 .假定一棵树的广义表表示为A (C, D (E, F, G), H (I, J),那么树中所含的结点数 为 个，树的深度为，树的度为 o.后缀算式9 23 +- 10 2/ -的值为 o中缀算式(3+4X) -2Y/3对应的后缀算式为 O.假设用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指 针。在这种存储结构中，n个结点的二叉树共有 个指针域，其中有 个指针域是存放了地址，有 个指针是空指针。3 .对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点 分别有 个和 个O. AOV网是一种 的图。4 .在一个具有n个顶点的无向完全图中，包含有 条边，在一个具有n个顶点的有向完全图中，包含有 条边。5 .假定一个线性表为(12,23,74,55,63,40),假设按Key % 4条件进行划分，使得同一余数的元 素成为一个子表，那么得到的四个子表分别为、和 O.向一棵B_树插入元素的过程中，假设最终引起树根结点的分裂，那么新树比原树的高度6 .在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为，整个堆排序 过程的时间复杂度为 O.在快速排序、堆排序、归并排序中，排序是稳定的。二、 运算题(每题6分，共24分)请画出图10的邻接矩阵和邻接表。请画出图10的邻接矩阵和邻接表。2.3.1 .在如下数组A中链接存储了一个线性表，表头指针为A0.next,试写出该线性表。6050789034403572041A01234567data next图10一个图的顶点集V和边集E分别为：V二1,2, 3 4, 5, 6, 7;E=(1,2)3, (1,3)5, (1,4)8, (2, 5)10, (2,3)6, (3,4)15, (3, 5) 12, (3, 6) 9, (4, 6)4, (4, 7) 20, (5, 6) 18, (6, 7) 25);用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。4.画出向小根堆中加入数据4, 2, 5, 8, 3时，每加入一个数据后堆的变化。四、阅读算法（每题7分，共14分）1. LinkList mynote(LinkList L)/L是不带头结点的单链表的头指针if(L&L-next)q=L； L=Lnext； p=L；SI ：while(pnext) p=pnext；S2：pnext=q； q next=NULL；)return L； )请回答以下问题：(1)说明语句SI的功能；(2)说明语句组S2的功能；(3)设链表表示的线性表为(al9a2,即)，写出算法执行后的返回值所表示的线性 表。2. void ABC(BTNode * BT)(if BT (ABC (BT-left);ABC (BT-right);coutBT-data*)该算法的功能是：五、 算法填空(共8分)二叉搜索树的查找一递归算法：bool Find(BTreeNode* BST, ElemTypefe item)(if (BST二二NULL)return false; 查找失败else (if (item=BST-data) item=BST-data; 查找成功return; else if (itemdata)return Find(, item);else return Find(, item);/if)编写算法(共8分)统计出单链表HL中结点的值等于给定值X的结点数。int CountX(LNode* HL,ElemType x)A. E、 G、 F、 A、 C、 D、 BB. E、 G、 F、 A、 C、 D、 BC. E、A、C、B、 D、 G、 FD. E、 A、 G、 C、 F、 B、 DE. E、G、A、C、 D、 F、 B.下面关于图的存储的表达中正确的选项是()oA.用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关B.用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关C.用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关D.用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关.设有关键码序列(q, g, m, z, a, n, p, x, h),下面哪一个序列是从上述序列出发建 堆的结果?()A. a, g, h, m, n, p, q, x, zB.a, g, m, h, q, n, p, x, zC. g, m, q, a n, p, x, h, zD.h, g, m, p, a, n, q, x, z二、 填空题(每空1分，共26分).数据的物理结构被分为、和 四种。1 .对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为, 在表尾插入元素的时间复杂度为 O.向一个由HS指向的链栈中插入一个结点时p时，需要执行的操作是; 删除一个结点时，需要执行的操作是(假设栈不空而 且无需回收被删除结点)。2 .对于一棵具有n个结点的二叉树，一个结点的编号为i(lWiWn),假设它有左孩子那么左孩 子结点的编号为,假设它有右孩子，那么右孩子结点的编号为，假设它有双 亲，那么双亲结点的编号为 o.当向一个大根堆插入一个具有最大值的元素时，需要逐层 调整，直到被调整到 位置为止。3 .以二分查找方法从长度为10的有序表中查找一个元素时，平均查找长度为 o.表示图的三种常用的存储结构为、和 o4 .对于线性表(70, 34, 55, 23, 65, 41, 20)进行散列存储时，假设选用H (K) =K %7 作为散列函数，那么散列地址为。的元素有 个，散列地址为6的有 个。5 .在归并排序中，进行每趟归并的时间复杂度为,整个排序过程的时间复杂度为 ，空间复杂度为 O.在一棵m阶B_树上,每个非树根结点的关键字数目最少为 个,最多为个，其子树数目最少为，最多为运算题(每题6分，共24分)1 .写出以下中缀表达式的后缀形式：(1) 3X/(Y-2)+l2+X*(Y+3)2 .试对图2中的二叉树画出其：(1)顺序存储表示的示意图；(2)二叉链表存储表示的示意图。3 .判断以下序列是否是小根堆？如果不是，将它调 整为小根堆。(1) 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 05, 23, 20, 28, 40, 38, 29, 61, 35, 76, 47, 100 4. 一个图的顶点集V和边集E分别为：V二1,2, 3, 4, 5,6, 7);模拟试卷五参考答案单项选择题(每题2分，共20分)1 .A 2.D 3.D 4.C 5.C 6.D 7.D8.C9.D10,A二、填空题(每空1分，共26分)正确性易读性强壮性高效率1. 0(n)9332. -134X* + 2Y*3/-2nnTn+13. e2e有向无回路4. n(nT)/2 n(n-l)(12, 40)( )(74)(23,55, 63)5. 增加10(log2n) 0(nlog2n)6. 归并 运算题(每题6分，共24分)线性表为：(78, 50, 40, 60, 34, 90)1 01 0 12.邻接矩阵：1 1 00 11 10 11 0j邻接表如图11所示:图113.用克鲁斯卡尔算法得到的最小生成树为：(1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10 (4,7)20图113.用克鲁斯卡尔算法得到的最小生成树为：(1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)204.见图122图12四、 阅读算法(每题7分，共14分). (1)查询链表的尾结点(2)将第一个结点链接到链表的尾部，作为新的尾结点 (3)返回的线性表为(a2,a3,-an,ai).递归地后序遍历链式存储的二叉树。五、 算法填空(每空2分，共8分)true BST-left BST-right六、 编写算法(8分)int CountX(LNode* HL,ElemType x) int i=0; LNode* p=HL;i 为计数器 while(p!=NULL) if (P-data=x) i+;p=p-next;/while,出循环时i中的值即为x结点个数return i;/CountX模拟试卷六一、单项选择题(在每题的四个备选答案中，选出一个正确的答案，并将其号码填在 题干后的括号内。每题1分，共10分)1 .下面程序段for(i=l;i=n;i+)for(j=l；j=0）o（）6 . n阶下三角矩阵的非零元素的个数最多为智2。（）7 .二叉树只能采用二叉链表来存储。（）8 .图G的某一最小生成树的代价一定小于其它生成树的代价。（）9 . B+树是一种特殊的二叉树。（）10 .所有的简单排序（即时间复杂度为0（/）的排序）都是稳定排序。（）四、简答题（每题4分，共20分）1.对于以下双向链表，设结构为（prior,data,next）,结点类型为Inode,试写出在p所指 结点之前插入元素x的语句序列。2.对于以下图，用Prim算法从结点 变化情况。出发构造出一棵最小生成树，要求图示出每一步的3 .一棵二叉树的先序序列与中序序列分别如下，试画出此二叉树。先序序歹U： ABCDEFGHIJ中序序歹U： CBEDAGHFJI4 .给定一组权值3, 4, 7, 14, 15, 20,试画出相应的哈夫曼树，并计算带树路径长 度WPL的值。5 .有关键字序列7,23,6,9,17,19,21,22,5, Hash函数为H(key尸key % 5,采用链地址法 处理冲突，试构造哈希表。五、算法题(共25分)1 .程序填空题(每空2分，共8分)下面程序的功能是二叉树的中序遍历的非递归算法，其中二叉树的结点结构为 (lchild,data,rchild),栈的常用方法有：入栈Push,出栈Pop,判空StackEmpty；试将程序补 充完整。templateBiTreeNode ：liBiTree:GoFarLeft(BiTreeNode *T, Stack BiTreeNode *& S) if(!T) return NULL;while (T-lchild)Push(S, T);T 二； ) return T;)templatevoid BiTree:Inorder(BiTreeNode *T, void (*visit)(Type & e)Stack BiTreeNode *& S;t = GoFarLeft(T, S); /找到最左下的结点while(t)visit(t-data);if (t-rchild)t = GoFarLeft(, S);else if ( ! StackEmpty(S )t=；elset=;/栈空说明遍历结束 / while/ Inorder2 .程序填空题(每空2分，共8分)下面程序的功能是用线性探测再散列处理冲突(即Hi=(H(key)+i)%m),哈希函数为 H(key)=kcy % m,进行哈希表的插入算法。(如表中已存在关键字相同的记录或无插入位置, 那么不进行插入)，试将程序补充完整。typedef enum SUCCESS,UNSUCCESS,OVERFLOW Status;templatetypedef struct Type *elem;int m;JHashTable;templateStatus SerchHashTable(HashTable H,Type e)int i=O,k=; /i为冲突的次数,k为哈希函数的值while(ielem.key!=e.key)p=(p+i)%m;/whileif(i=m)return OVERFLOW;else if(p-elem.key!=e.key)return ;elseH.elemp.elem=;return SUCCESS;/if /Serch