数据结构试卷试卷及答案5套

《数据结构试卷试卷及答案5套》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第12页共12页数据结构试卷试1一、解释下列术语（每小题4分，共20分）1.头指针2.二叉排序树的定义3.头结点4.数据的逻辑结构5.排序方法的稳定性二、选择填空（每小题2分，共20分）（在每小题的4个备选答案中，选出一个正确的答案，多选少选均不得分）1.在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时顺向后移动()个元素A.n-iB.n-i+1C.n-i-1D.i2.某个栈的输入序列为1，2，3，4，下面的四个序列中()不可能是它的输出序列A.1,2,3,4B.2,3,4,1C.4,3,2,1D.3,4,1,23.对二叉排序进行()遍历

2、可以得到结点的排序序列A.前序B.中序C.后序D.按层次4．有64个结点的完全二叉树的深度为（）。A8B7C6D55．折半查找法的时间复杂度是()A.(n2)B.O(n)C.O(n㏒n)D.O(㏒n)6．A(1:5,1:6)的每个元素占5个单元，将其按行优先次序储存在起始地址为1000的连续的内存单元中，则元素A[5，5]的地址为（）。A1140B1145C1120D11257.有n个叶子结点的哈夫曼树的结点总数为（）。A不确定B2nC2n+1D2n-18.已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,则它的前遍历序列是（）。AacbedBdec

3、abCdeabcDcedba9．若循环队列用数组A(0:m-1)存放其元素值，已知其头、尾指针分别是f和r,则当前队列中的元素个数是（）。A(r-f+m)modmBr-f+1Cr-f-1Dr-f10.一个二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）的二叉树（树中结点个数大于1）。A空或只有一个结点B高度等于其结点数C任一结点无左孩子D任一结点无右孩子三，判断题（每小题2分，对的打√，错的打×，共10分）答案参见我的新浪博客：http://blog.sina.com.cn/s/blog_3fb788630100muda.html第12页共12页1．若图G的

4、最小生成树不唯一，则G的边数一定多于n-1，并且权值最小的边有多条（其中n为G的顶点数）。()2．对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先遍历可访到该图的每个顶点。()3．若某二叉树的叶子结点数为1（树中只有一个结点的情况除外），则其先序序列和后序序列一定相反。（）4．在队列中，队头指针总是指向第一个数据元素。（）5．线性表的唯一存储形式是链表。（）四，解答题（每小题6分，共24分）a)从一的平衡二叉树开始，把关键字（5，19，6，22，16，15，30）按出现的先后顺序逐一插入，从而构造一棵平衡二叉树排序树，每插入一个关键字后，若需要进行平衡旋转

5、，则标明其旋转类型及旋转后的结果。b)满足下列条件的二叉树具有什么形状？i.前序和中序遍历次序相同；ii.中序和后序遍历次序相同；iii.前序和后序遍历次序相同；c)写出所给数据表，采用快速排序方法按升序排序的每一趟的结果：（25，10，20，31，5，28）。d)具有144个记录的文件，若采用分块查找法查找，则分成几块最好？每块的最佳长度是多少？假定每块的长度是8，确定所在块、块中均采用顺序查找法查找，则平均查找长度是多少？五、编写算法（共16分）a)写出，建立一个具有n个顶点的无向网的邻接矩阵的算法。提示：先将矩阵A的每个元素都初始化成0，然后，读入边及数值（i

6、,j,w）,将A的相应元素置成w。（8分）b)线性表V采用顺序存储结构，试编写删除V中的第i个元素起的k个元素的算法。（8分）答案参见我的新浪博客：http://blog.sina.com.cn/s/blog_3fb788630100muda.html第12页共12页数据结构试卷试2一、填空题（共20分，每空1分）1．数据结构是研究数据元素之间抽象化的相互关系和这种关系在计算机中的存储结构表示，通常有下列四种存储结构：（1）、（2）、（3）和（4）。2．评价算法的标准很多，通常是以执行算法所需要的（5）和所占用的（6）来判别一个算法的优劣。3．队列操作的原则是（7）

7、，栈的插入和删除操作在（8）进行。4．对循环队列Q，它的最大存储空间是MAXSIZE，队头指针是front，队尾指针是rear，采用少用一个存储单元的方法解决假溢出时，队满的判断条件是（9），队空的判断条件是（10）。5．在以Head为表头指针的带有头结点的单链表和循环单链表中，判断链表为空的条件分别为（11）和（12）。6．假设二维数组A[6][8]，每个元素用相邻的4个字节存储，存储器按字节编址，已知A的开始存储位置为100，按行优先顺序存储的元素A[2][5]的第一个字节的地址为（13）。7．空格串的长度为串中所包含（14）字符的个数，空串的长度为（15）