数据结构与算法 试题及答案

绪论一、填空题1、数据的逻辑结构是数据元素之间的逻辑关系，通常有下列4类：集合 、线性结构、树型结构、图状结构。2、数据的存储结构是数据在计算机存储器里的表示，主要有4种基本存储方法：顺序存储 、链式存储、索引存储、散列存储。二、选择题1、一个算法必须在执行有穷步之后结束，这是算法的（ B ）。A、正确性 B、有穷性C、确定性 D、可行性2、算法的每一步必须有确切的定义，也就是说，对于每步需要执行的动作必须严格、清楚地给出规定，这是算法的（ A）。A、正确性 B、有穷性C、确定性 D、可行性3、算法原则上都是能够有机器或人所完成的。整个算法好象是一个解决问题的“工作序列”，其中的每一步都是我们力所能及的一个动作，这是算法的（D） A、正确性 B、有穷性C、确定性 D、可行性三、简单题1、什么是数据结构？什么是算法？两者有什么关系？什么是数据结构？数据结构是按某种逻辑关系组织起来的一批数据（或称带结构的数据元素的集合）应用计算机语言并按一定的存储表示 方式把它们存储在计算机的存储器中，并在其上定义了一个运算的集合。 什么是算法？广义地说,为解决一个问题而采取的方法和步骤,就称为“算法”两者有什么关系？算法与数据结构关系密切。选择的数据结构是否恰当直接影响算法的效率；而数据结构的优劣由算法的执行来体现。 2、什么是复杂度和空间复杂度？时间复杂度是指执行算法所需要的计算工作量；而空间复杂度是指执行这个算法所需要的内存空间。3、数据的逻辑结构分几种？存储结构又有哪几种？ 数据的逻辑结构：结构定义中的“关系”，描述的是数据元素之间的逻辑关系；包括线性结构（线性表、栈、队、串、数组）和非线性结构（图形结构、树形结构）；数据的存储结构（物理结构）：数据结构在计算机中的表示（又称映像），包括数据元素的表示和关系德表示。有顺序存贮（向量存贮）、链式存贮、索引存贮、散列存贮。 线性表1、一个线性表第一个元素的存储地址是 100，每个元素的长度 为 2， 则第 5 个元素的地址是 ( B)。 （A）110 （B）108（C）100 （D）120 2、向一个有 127 个元素的顺序表中插入一个新元素并保持原来 顺序不变，平均要移动（ C）个元素。 （A）64（B）63 （C）63.5（D）7 2、线性表采用链式存储结构时，其地址 ( D)。 (A) 必须是连续的 (B) 部分地址必须是连续的 (C) 一定是不连续的 (D) 连续与否均可以3、在一个单链表中，若 p 所指结点不是最后结点，在 p 之后插 入 s 所指结点，则执行 (B )。 （A）s-next=p;p-next=s; （B） s-next=p-next;p-next=s; （C）s-next=p-next;p=s; （D）p-next=s;s-next=p; 4、在一个单链表中，若删除 p 所指结点的后续结点，则执行 (A ) （A）p-next=p-next-next; （B）p=p-next; p-next=p-next-next; （C）p-next=p-next; （D）p =p-next-next; 5.在长度为n的顺序表的第i(1in+1)个位置上插入一个元素，元素的移动次数为 A_，删除第i个位置元素，元素的移动次数为 B 。A. n-i+1 B. n-i C. i D. i-16.算法分析的两个主要方面是_A_。A. 空间复杂性和时间复杂性 B. 正确性和简明性C. 可读性和文档性 D. 数据复杂性和程序复杂性7.写出顺序表插入、删除及就地逆置算法（见实验）/顺序表的逆置 void reverse(SqList L)int i,j,k;for(i=0,j=L.length-1;i0)个元素的顺序栈中插入1个元素的时间复杂度为(C)。A. O(nlog2n) B. O( ) C. O(1) D. O(n)5.在n(n0)个元素的顺序栈中删除1个元素的时间复杂度为(D)。A. O(n) B. O( ) C. O(nlog2n) D. O(1) 填空题部分 1、栈的特点是（后进先出（或LIFO），队列的特点是（先进先出（或FIFO ） ）。 2、线性表、栈和队列都是（线性 ）结构，可以在线性表的（任何 ）位置插入和删除元素，栈只能在（ 表尾）插入和删除元素， 队列只能在（ 表尾）插入元素和（表首 ）删除元素。 3、若队列的入队序列是 1, 2, 3, 4，则出队序列是（B）。 （A）4,3,2,1（B）1,2,3,4（C）1,4,3,2（D）3,2,4,1队列基础知识1、循环队列用数组 A0, m-1 存放其元素值，已知其头尾指 针分别是 front 和 rear 则当前队列中的元素个数是（A）。 (A) (rear-front+m)%m (B) rear-front+1 (C) rear-front-1 (D) rear-front 2、以数组 Q0 m1 存放循环队列中的元素，变量 rear 和 qulen 分别指示循环队列中队尾元素的实际位置和当前 队列中元素的个数，队列第一个元素的实际位置是（D）。 (A) rearqulen (B) rearqulenm (C) mqulen (D) 1(rearmqulen) % m 3.设循环队列中数组的下标范围是1n，其头尾指针分别为f和r，则判断循环队列满的条件为(B)A. r=f B. f=(r+1) % nC. r=(f+1) % (n+1) D. r=f+1一、填空题1、线性表、栈和队列都是_线性_结构，线性表可以在任意 位置插入和删除元素；对于栈只能在栈顶 插入和删除元素；对于队列只能在队尾插入和_队首删除元素。2、栈是一种特殊的线性表，允许插入和删除运算的一端称为栈顶，不允许插入和删除运算的一端称为栈底。3、 队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。4、向栈中压入元素的操作是先移动栈顶指针，后存入元素。5、在操作序列push(1),push(2),pop(),push(5),push(7),pop(),push(6)之后，栈顶元素是6，栈底元素是1。（push(k)表示整数k入栈，pop表示栈顶元素出栈。）6、用单链表表示的链式队列的队头是在链表的链尾_位置。二叉树和树1. 二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面， 这种说法（ A ） （A）正确 （B）错误 2. 由于二叉树中每个结点的度最大为 2，所以二叉树是一种特殊的树， 这种说法（ B ） （A）正确 （B）错误 3. 已知某二叉树的后序遍历序列是 dabec。中序遍历序列是 debac，它 的前序遍历序列是（ D ）。 （A）acbed （B）decab（C）deabc （D）cedba 4. 某二叉树的前序遍历结点访问顺序是 abdgcefh，中序遍历的结点访 问顺序是 dgbaechf，则其后序遍历的结点访问顺序是（ D ）。 （A）bdgcefha （B）gdbecfha （C）bdgaechf （D）gdbehfca 5. 在一非空二叉树的中序遍历序列中，根结点的右边（A） （A）只有右子树上的所有结点 （B）只有右子树上的部分结点 （C）只有左子树上的部分结点 （D）只有左子树上的所有结点 6. 任一二叉树的叶子结点在先、中和后序遍历序列中的相对次序 ( A ) 。 （A）不发生改变 （B）发生改变 （C）不能确定 （D）以上都不对 7.对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用_C_遍历实现编号。A. 无序 B. 中序 C. 后序D. 从根开始的层次遍历8.深度为k的二叉树的结点总数，最多为 C 个。)k-1 ) log2k ) k )k9. 深度为9的二叉树中至少有 9 个结点。)9 )8 ) )9110二叉树有n个叶子，没有度为1的结点，共有 2n-1 个结点分析：度为2的结点有n-1个，所以共2n-1个结点。11.设一棵完全二叉树具有1000个结点，则它有500 个叶子结点，有499个度为2的结点，有 1 个结点只有非空左子树，有 0 个结点只有非空右子树。12.一棵深度为6的满二叉树有 32 个叶子和 31 个分支结点。13、n个叶子结点的二叉树最少有 2n-1 结点。作业：1、一棵哈夫曼树有 19 个结点，则其叶子结点的个数是(10 )。 2、有七个带权结点，其权值分别为 3, 7, 8, 2, 6, 10, 14，试以它们为叶结点构造 一棵哈夫曼树（请按照每个结点的左子树根结点的权小于等于右子树根结点 的权的次序构造），并计算出带权路径长度WPL及该树的结点总数。例：50 21 29 11 10 15 14 5 6 7 82 3上图为树，所以带权路径长度为 2x4+3x4+6x3+10x2+7x3+8x3+14x2=1313、有一电文共使用五种字符 a, b, c, d, e，其出现频率依次为 4, 7, 5, 2, 9。 (1)、试画出对应的编码哈夫曼树（要求左子树根结点的权小于等于右子树 根结点的权）。 (2)、求出每个字符的哈夫曼编码。 (3)、求出传送电文的总长度。 (4)、并译出编码系列11000111000101011的相应电文。(P143)(1)27 | | 18 9 | | 11 7| 6 5| |2 4WPL=9*1+7*2+5*3+(2+4)*4=62(2)5种字符a、b、c、d、e的哈夫曼编码依次为011、10、00、010、114、对于给定的一组权值 W1, 3, 7, 8, 14, 20, 28 建立哈夫曼树，并计算带 权路径长度。 5、假定有 7 个字符 a, b, c, d, e, f, g 出现的概率分别为 0.07, 0.09, 0.14, 0.23, 0.44, 0.58, 0.77，求这 7 个字符的哈夫曼编码。 6、某通信过程中使用的编码有8个字符A,B,C,D,E,F,G,H，其出现的次数分别为20, 6, 34, 11, 9, 7, 8, 5。若每个字符采用3位二进制数编码，整个通信需要多少字节？请给出哈夫曼编码，以及整个通信使用的字节数？ 7、对右图所示的普通树，完成以下操作： (1)分别画出这棵树的双亲表示法、孩子表示法的存储结构图；(2)将这棵树转换成二叉树；(3)写出对上小题得到的二叉树分别进行前序、中序、后序遍历所得到的遍历序列。8、设一棵二叉树的先序、中序遍历序列分别为A B D F C E G H 和B F D A G E H C，请写出分析过程并画出这棵二叉树，然后写出该二叉树的后序遍历序列。第7章 图选择题 1. 在一个图中，所有顶点的度数之和等于所有边数的 ( C) 倍。 （A）1/2 （B）1 （C）2 （D）4 2. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 (B ) 倍。 （A）1/2 （B）1 （C）2 （D）4 3. 一个有 n 个顶点的无向图最多有 (C ) 条边。 （A）n （B）n(n -1) （C）n(n-1)/2 （D）2n 4. 具有 4 个顶点的无向完全图有 ( A) 条边。 （A）6 （B）12 （C）16 （D）20 5. 具有 6 个顶点的无向图至少应有 ( A) 条边才能确保是一个连通图。 （A）5 （B）6 （C）7 （D）86. 在一个具有 n 个顶点的无向图中，要连通全部顶点至少需要 ( C) 条边。 （A）n （B）n + 1 （C）n 1 （D）n/2 7. 对于一个具有 n 个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小 为 (D )。 （A）n （B）(n-1)2 （C）n -1 （D）n2 8. 对于一个具有 n 个顶点和 e 条边的无向图，若采用邻接表表示，则表头数 组的大小为 (A )，所有邻接表中的结点总数是 (C )。 （A）n （B）n+1 （C）n-1 （D）n+e （A）e/2 （B）e （C）2e （D）n+e 9.在含有n个项点有e条边的无向图的邻接矩阵中，零元素的个数为 （D）。 A.e B.2e C.n2-e D.n2-2e 10.图的深度优先遍历算法类似于树的（A ）。（A）先根遍历 （B）后根遍历 （C）按层遍历11.图的广度优先遍历算法类似于树的（C ）。（A）先根遍历 （B）后根遍历 （C）按层遍历填空题部分 1. n 个顶点的连通图至少 ( N-1) 条边。2. 在一个无向图的邻接表中，若表结点的个数是 m，则图中 边的条数是 ( M/2) 条。 3. 分别用普里姆和克鲁斯卡尔算法构造下图所示网络的最小 生成树。 V1V2V3V4V576986442 4. 分别求出图 4 从 v2 出发按深度优先搜索和广度优先搜 索算法遍历得到的顶点序列（假设图的存储结构采用邻 接矩阵表示）。 V1V2V3V5V6V4图 45. 已知一个有向图的邻接表如图 5 所示，求出根据深度优 先搜索算法从顶点 v1 出发遍历得到的顶点序列。 6、对右边所示的有向图邻接矩阵： 求出每个顶点的入度和出度。 画出图的邻接表； 分别写出自顶点1出发进行遍历所得的深度优先遍历序列和广度优先遍历序列。7.对右边所示的有向图：(1)画出图的邻接矩阵；(2)画出图的邻接表；(3) 分别画出由结点1出发得到的深度优先生成树和广度优先生成树。(要求每一步选取的结点为未访问过的且编号最小的邻接点。求优先生成树时忽略边的权值。) 深度优先遍历序列：1-2-4-3-6-5-7广度优先遍历序列：1-2-5-4-6-7-38.已知一个图的定点集V和边集E分别为； V=1，2，3，4，5，6，7；E=,；画出该图，并给出全部可能的拓扑排序序列。9、 如下图所示，计算出各事件（顶点）的ve(vi)和vl（vi）的值及各活动（弧）ee(ai)和el(ai)的值，并写出所有的关键路径。（8分）a8=424356a1=6a3=51a4=9a2=6a5=10a6=22a7=1710、 分别用普里姆算法和克鲁斯卡尔算法计算下图的最小生成树。 14652388766592 7311、对右边所示的有向图： (1)、求出带权邻接矩阵；(2)、用Dijkstra算法求从顶点1到其它各顶点的最短路径。查找 已知一组关键字19, 14, 23, 1, 68, 20, 85, 9，采用哈希函数H(key)=key MOD 13，请分别采用以下处理冲突的方法构造哈希表，并求各自的平均查找长度。 1) 采用线性探测再散列； 2) 采用二次探测再散列 3) 采用链地址法。