《数据结构与算法试题及答案》由会员分享，可在线阅读，更多相关《数据结构与算法试题及答案（12页珍藏版）》请在金锄头文库上搜索。
1、绪论一、填空题1、数据的逻辑结构是数据元素之间的逻辑关系，通常有下列4类：集合_、线性结构_、树型结构_、图状结构2、数据的存储结构是数据在计算机存储器里的表示，主要有4种基本存储方法：顺序存储_、链式存储_、索引存储、散列存储二、选择题1、一个算法必须在执行有穷步之后结束，这是算法的（B）。A、正确性B、有穷性C、确定性D、可行性2、算法的每一步必须有确切的定义，也就是说，对于每步需要执行的动作必须严格、清楚地给出规定，这是算法的（A）oA、止确性B、有穷性C、确定性D、可行性3、算法原则上都是能够有机器或人所完成的。整个算法好象是一个解决问题的“工作序列”，其中的每一步都是我们力所能及的一
2、个动作，这是算法的（D）A、正确性B、有穷性C、确定性D、可行性三、简单题1、什么是数据结构？什么是算法？两者有什么关系？什么是数据结构？费据结构是按某种逻辑关系组织起来的一批数据（或称带结构的数据元素的集合）应用计算机语言并按一定的存储表示方式把它们存储在讣算机的存储器也并在其上定义了一个运算的集合。什么是算法？广义地说，为解决个问题而采取的方法和步骤,就称为“算法”两者有什么关系？算法与数据结构关系密切。选择的数据结构是否恰当直接影响算法的效率；而数据结构的优劣由算法的执行来体现。2、什么是复杂度和空间复杂度？时间复杂度是指执行算法所需要的计算工作疑：而空间复杂度是指执行这个算法所需要的内
3、存空间。3、数据的逻辑结构分几种？存储结构又有哪几种？数据的逻辑结构：结构左义中的关系”，描述的是数据元素之间的逻借关系；包括线性结构（线性表、栈、队、串、数组）和非线性结构（图形结构、树形结构）；数据的存储结构（物理结构）：数据结构在计算机中的表示（又称映像），包括数据元素的表示和关系德表示。有顺序存贮（向量存贮）、链式存贮、索引存贮、散列存贮。线性表1、一个线性表第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是（B）o（A）110（B）108（C）100（D）1202、向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（C）个元素。（A）64（
4、B）63（C）63.5（D）72、线性表采用链式存储结构时，其地址（D）o（A）必须是连续的（B）部分地址必须是连续的(C)一定是不连续的(D)连续与否均可以3 .在一个单链表中，若p所指结点不是最后结点，在P之后插入s所指结点，则执行但)。(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)
5、p-next=p-next;(D)p=p-next-next;5 .在长度为n的顺序表的第i(IWiWn+l)个位置上插入一个元素，元素的移动次数为一，删除第i个位置元素，元素的移动次数为旦。A.n-i+1B.n-iC.iD.i-16 .算法分析的两个主要方面是_A_。A.空间复杂性和时间复杂性B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性7 .写出顺序表插入、删除及就地逆置算法(见实验)顺序表的逆置voidreverse(SqListL)inti,j,k;for(i=0,j=L.length-1;i0)个元素的顺序栈中插入1个元素的时间复杂度为(C)。A.O(nlog2n)B
6、.0()C.0(1)D.O(n)5、 在n(n0)个元素的顺序栈中删除1个元素的时间复杂度为(D)。A.0(n)B.0()C.O(nlog2n)D.0(1)填空题部分1、栈的特点是(后进先出(或UFO),队列的特点是(先进先出(或FIFO)o2、线性表、栈和队列都是(线性)结构，可以在线性表的(任何)位置插入和删除元素，栈只能在(表尾)插入和删除元素，队列只能在(表尾)插入元素和(表首)删J除元素。3、若队列的入队序列是1,2,3,4,则出队序列是(B)。(A)4,3,2,1(B)1,2,3,4(01,4,3,2(0)3,2,4,1队列基础知识1、循环队列用数组存放其元素值，已知其头尾指针分别
7、是front和rear则当前队列中的元素个数是(A)。(A)(rear-front+m)%m(B)rear-front+1(C)rear-front-1(D)rear-front2、以数组Q0m-1存放循环队列中的元素，变量rear和qulen分别指示循环队列中队尾元素的实际位置和当前队列中元素的个数，队列第一个元素的实际位置是(D)。(A)rear-qulen(B)rear-qulen+m(C)/riqulen(D)I+(rear+mqulen)%m3.设循环队列中数组的下标范围是其头尾指针分别为f和r,则判断循环队列满的条件为但)A.r=fB.f=(r+l)%nC.r=(f+l)%(n+1
8、)D.r=f+l一、填空题1、线性表、栈和队列都是一线性一结构，线性表可以在_任意位卷插入和删除元素：对于栈只能在栈顶插入和删除元素；对于队列只能在一队尾插入和一队首删除元素。2、栈是一种特殊的线性表，允许插入和删除运算的一端称为一栈去，不允许插入和删除运算的一端称为.栈底。3、队列一是被限泄为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。4、向栈中压入元素的操作是先移动栈顶指针，后一存入元素。5、在操作序列push(l),push(2)Jpop(),push(5)Jpush(7),pop(),push(6)ZJn,栈顶元素是_6,栈底元素是(push(k)表示整数k入栈，po
9、p表示栈顶元素出栈。)6、用单链表表示的链式队列的队头是在链表的一链尾一位置。二叉树和树1 .二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法(A)(A)正确(B)错误2 .由于二叉树中每个结点的度最大为2,所以二叉树是一种特殊的树，这种说法(B)(A)正确(B)错误3 .已知某二叉树的后序遍历序列是dabeco中序遍历序列是debac,它的前序遍历序列是(D(A)acbed(B)decab(C)deabc(D)cedba4 .某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbaechf,则其后序遍历的结点访问顺序是(D(A)bdgcefha(
10、B)gdbeefha(C)bdgaechf(D)gdbehfea5 .在一非空二叉树的中序遍历序列中，根结点的右边(A)(A)只有右子树上的所有结点(B)只有右子树上的部分结点(C)只有左子树上的部分结点(D)只有左子树上的所有结点6 .任一二叉树的叶子结点在先、中和后序遍历序列中的相对次序(A)。(A)不发生改变(B)发生改变(C)不能确定(D)以上都不对7、对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用_J遍历实现编号。A.无序B.中序C.后序D.从根开始的层次遍历8深度为k的二叉树的结点总数，最多为
11、个。A)2klB)log2kC)2k.iD)2k9 .深度为9的二叉树中至少有2个结点。A)29B)28C)9D)29-l10 .二叉树有n个叶子，没有度为1的结点，共有2nI个结点分析：度为2的结点有nl个，所以共2n1个结点。11 .设一棵完全二叉树具有1000个结点，则它有500个叶子结点，有型个度为2的结点，有L个结点只有非空左子树，有一。个结点只有非空右子树。12一棵深度为6的满二叉树有丝个叶子和31个分支结点。13.n个叶子结点的二叉树最少有2rv：L结点。作业：K一棵哈夫曼树有19个结点，则其叶子结点的个数是(10)02、有七个带权结点，其权值分别为3,7,826,10,14,试
12、以它们为叶结点构造一棵哈夫曼树(请按照每个结点的左子树根结点的权小于等于右子树根结点的权的次序构造)，并计算出带权路径长度WPL及该树的结点总数。例：50291514782111105623上图为树,所以带权路径长度为2x4+3x4+6x3+10x2+7x3+8x3+14x2=1313、有一电文共使用五种字符a,b,c,d其出现频率依次为4,7,5,2,9(1)、试画出对应的编码哈夫曼树(要求左子树根结点的权小于等于右子树根结点的权)。(2)、求出每个字符的哈夫曼编码。(3)、求出传送电文的总长度。(4).并译出编码系列11000111000101011的相应电文。(P143)(1)27II1
13、89II117II651I24WPL=9*1+严2+5*3+(2+4)*4=62(2)5种字符a、b、c、d、e的哈夫曼编码依次为011、10、00、010.114、对于给定的一组权值W=1,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个字符AbCQEFGH,英出现的次数分别为20,6,34,11,9,7,8,5o若每个字符采用3位二进制数编码，整个通信需要多少字节？请给出哈夫曼编码，以及整个通信使用的字节数？7、对右图所示的普通树，完成以下操作：分别画出这棵树的双亲表示法、孩子表示法的存储结构图：将这棵树转换成二叉树：(3)写出对上小题得到的二叉树分别进行前序、中序、后序遍历所得到的遍历序列。8,设一棵二叉树的先序、中序遍历序歹lj分别为ABDFCEGH和
