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

第12页共13页PAGE答案参见我的新浪博客：/s/blog_3fb788630100muda.html数据结构试卷试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-12.某个栈的输入序列为1，2，3，4，下面的四个序列中()不可能是它的输出序列A.1,2,3,4B.2,3,4,1C.4,3,2,1D.3,4,1,23.对二叉排序进行()遍历可以得到结点的排序序列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,则它的前遍历序列是（）。AacbedBdecabCdeabcDcedba9．若循环队列用数组A(0:m-1)存放其元素值，已知其头、尾指针分别是f和r,则当前队列中的元素个数是（）。A(r-f+m)modmBr-f+1Cr-f-1Dr-f10.一个二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）的二叉树（树中结点个数大于1）。A空或只有一个结点B高度等于其结点数C任一结点无左孩子D任一结点无右孩子判断题（每小题2分，对的打√，错的打×，共10分）1．若图G的最小生成树不唯一，则G的边数一定多于n-1，并且权值最小的边有多条（其中n为G的顶点数）。()2．对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先遍历可访到该图的每个顶点。()3．若某二叉树的叶子结点数为1（树中只有一个结点的情况除外），则其先序序列和后序序列一定相反。（）4．在队列中，队头指针总是指向第一个数据元素。（）5．线性表的唯一存储形式是链表。（）四，解答题（每小题6分，共24分）从一的平衡二叉树开始，把关键字（5，19，6，22，16，15，30）按出现的先后顺序逐一插入，从而构造一棵平衡二叉树排序树，每插入一个关键字后，若需要进行平衡旋转，则标明其旋转类型及旋转后的结果。满足下列条件的二叉树具有什么形状？前序和中序遍历次序相同；中序和后序遍历次序相同；前序和后序遍历次序相同；写出所给数据表，采用快速排序方法按升序排序的每一趟的结果：（25，10，20，31，5，28）。具有144个记录的文件，若采用分块查找法查找，则分成几块最好？每块的最佳长度是多少？假定每块的长度是8，确定所在块、块中均采用顺序查找法查找，则平均查找长度是多少？编写算法（共16分）写出，建立一个具有n个顶点的无向网的邻接矩阵的算法。提示：先将矩阵A的每个元素都初始化成0，然后，读入边及数值（i,j,w）,将A的相应元素置成w。（8分）线性表V采用顺序存储结构，试编写删除V中的第i个元素起的k个元素的算法。（8分）数据结构试卷试2一、填空题（共20分，每空1分）数据结构是研究数据元素之间抽象化的相互关系和这种关系在计算机中的存储结构表示，通常有下列四种存储结构：（1）、（2）、（3）和（4）。评价算法的标准很多，通常是以执行算法所需要的（5）和所占用的（6）来判别一个算法的优劣。队列操作的原则是（7），栈的插入和删除操作在（8）进行。对循环队列Q，它的最大存储空间是MAXSIZE，队头指针是front，队尾指针是rear，采用少用一个存储单元的方法解决假溢出时，队满的判断条件是（9），队空的判断条件是（10）。在以Head为表头指针的带有头结点的单链表和循环单链表中，判断链表为空的条件分别为（11）和（12）。假设二维数组A[6][8]，每个元素用相邻的4个字节存储，存储器按字节编址，已知A的开始存储位置为100，按行优先顺序存储的元素A[2][5]的第一个字节的地址为（13）。空格串的长度为串中所包含（14）字符的个数，空串的长度为（15）。有向图G用邻接矩阵A[n，n]存储表示，其第i行的所有元素之和等于顶点i的（16）。在关键字序列(12，23，34，45，56，67，78，89，91)中折半查找关键字为89和25的结点时，所需进行的比较次数分别为（17）和（18）。请说出两种处理哈希冲突的方法（19）、_（20）_。二、选择题（共20分，每题2分）对线性表，在下列哪种情况下应采用链式存储结构？（）A．经常需要随机存取元素B．经常需要进行插入和删除操作C．表中元素的个数不变D．表中元素需要占据一片连续的存储空间从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功情况下，则平均比较（）个结点。A．nB．n/2C．(n-1)/2若对某线性表最常进行的操作是在最后一个元素之后插入和删除第一个元素，则采用（）存储方式最节省运算时间。A．单链表B．双链表C．仅有头指针的单循环链表D．仅有尾指针的单循环链表在一个单链表中，若要删除p指针所指结点的后继结点，则执行（）。A．p->next;p->next=p->next->next；B．p->next=p->next->next；C．p=p->next；D．p=p->next->>next；在具有n个结点的二叉链表中，非空的链域个数为（）。A．n-1B．nC．n+1D．不确定有64个结点的完全二叉树的深度为（）（假设根结点的层次为1）。A．8B．7C．6边远山区的那个小村庄，现要为他们建成能互相通信的网，并且总的花费最少，这可以归结为什么问题（）。A．最短路径B．关键路径C．拓扑排序D．最小生成树折半查找法要求查找表中各元素的键值必须是（）。A．递增或递减B．递增C．递减D．无序下列排序算法中，（）算法在进行一趟相应的排序处理结束后不一定能选出一个元素放到其最终位置上。A．直选择排序B．冒泡排序C．归并排序D．堆排序对于键值序列（2，33，21，18，65，38，7，49，24，86），用筛选法建堆，必须从键值为（）的结点开始。A．86B．2C．65三、判断题（共10分，每题2分）已知指针P指向链表L中的某结点，执行语句P=P->next不会删除该链表中的结点。()如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串。()若一棵二叉树的任一非叶结点度均为2，则该二叉树为满二叉树。()任一AOE网中至少有一条关键路径，且是从源点到汇点的路径中最短的一条。()在采用线性探测法处理冲突的散列表中所有同义词在表中相邻。（）四、简答题（共24分,每题8分）二叉树的先序遍历序列为：ABCDEFGHI，中序遍历序列为：BCAEDGHFI，画出这棵二叉树。输入一个结点序列{300，100，80，52，40，64，350}，试画出构造平衡二叉树的过程，并说明平衡旋转类型。已知一组记录的排序码为（46，79，56，38，40，80，95，24），写出对其进行快速排序的每一趟排序的结果。五、算法设计题（共16分）试写一建立单链表的算法。（8分）已知一个非空线性链表第一个结点的指针为L，请写一算法，将链表中数据域值最大的那个结点移到链表最后面。（8分）数据结构试卷试3一、填空（20分，每小题2分）1、若用S[1]~S[m]作为顺序栈的存储空间，栈空的标志是栈顶指针t=m+1，则每进行一次（）操作，需将t的值加1。2、队列的特征是()。3、在单向链表中增加一个表头节点的目的是（）。４、3个结点可以构成（）种不同形状的树，可以构成（）种不同形状的二叉树。５、在平衡二叉排序树中，每个结点的平衡因子等于（）。６、可以进行拓扑排序的有向图一定是（）。７、为了实现折半查找，线性表必须采用（）方法存储。８、若以{4,5,6,7,8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是（）９、在排序过程中，任何情况下都不比较排序码大小的排序方法是（）。二、选择填空（20分，每小题2分）1、链表最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则采用（）

存储方式最省时间。

A.单链表B.双链表C.单循环链表D.带尾指针的单循环链表2、栈和队列都是()A．顺序存储的线性结构B．链式存储的非线性结构C．限制存取点的线性结构D．限制存取点的非线性结构３、若对有18个元素的有序表作折半查找。则查找A[3]的比较序列的下标为（）。A．1，2，3B．9，5，2，3C．9，4，2，3D．10，5，３，２4、设n，m为某二叉树上的两个结点，在中序遍历时，n在m前的条件是()A．n在m右方B．n是m祖先C．n在m左方D．n是m子孙5、对长度为10的有序表进行折半查找，设在等概率时查找成功的平均查找长度是()A．2.9B．3.1C．3.46、带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中第i()。

A行非∞的元素之和B.列非∞的元素之和

C.行非∞且非0的元素个数D.列非∞且非0的元素个数7.在有n个叶子结点的哈夫曼树中，其结点总数为()。

A不确定B2nC2n+1D2n-18、任何一个无向连通图的最小生成树()。

A只有一棵B有一棵或多棵C一定有多棵D可能不存在9、设有1000个无序的元素，希望用最快的速度挑出其中前10个最大元素，在以下排序方法中用哪一种最好（）。A、选择排序B、冒泡排序C、堆排序D、快速排序10、直接插入排序在最好情况下的时间复杂度为（）

A.O(logn)

B.O(n)

C.O(n*logn)

D(n2)三、判断正误（10分，每小题2分。对得打“√”，错的打“╳”）1、如果一个串中所有字符均在另一串中出现，则说前者是后者的子串。（）2、（101，88，46，70，34，39，45，58，66，10）是堆。（）3、

哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离很较近。（）4、用树的前序遍历和中序遍历可以导出树的后序遍历。（）5、在执行某个排序算法过程中，出现了排序码朝着最终排序序列相反的方向移动，从而可以认为该算法时不稳定的。（）四、简答题（35分）１、将关键字集合K={60，40，49，23，25，13，95，196，85}，创建平衡二叉排序树。2、设一数列的顺序是1、2、3、4、5、6，通过栈结构能否排成顺序为3、2、5、6、4、1的数列？2）能否排成顺序为1、5、4、6、2、3的数列？3、一棵共有n个结点的树，其中所有分枝结点的度均为k，求该树中叶子结点的个数。4、有关键字集合K{37，15，50，01，55，25，84，30，44，24，27，38}，α=0.75，采用除留余数法，解决冲突用线性探测，将K散列到哈希表。给定一组记录的关键词，其顺序是13、7、9、15、8、16、12、4、11、20、10、14，试写出：用快速排序算法操作时，第一趟结束后的状态。用希尔排序算法操作时（逐减增量序列是6、3、2、1），第一趟和第二趟结束后的状态。用选择排序算法操作时，第一趟和第二趟（即选择最大和次大者送到最后排序位置）结束后的状态（两趟分别写出）。五、算法（15分）１、写出一个将二叉树左、右孩子交换的算法。（7分）２、试写出一个利用遍历图的方法输出一条无向图G中从顶点Vi到Vj长度为L的简单路径的算法。（8分）数据结构试卷试4一、选择填空（每小题2分，共20分）（在每小题的4个备选答案中，选出一个正确的答案，多选少选均不得分）1．有64个结点的完全二叉树的深度为（）。A8B7C6D52．折半查找法的时间复杂度是()A.(n2)B.O(n)C.O(n㏒n)D.O(㏒n)3.在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时顺向后移动()个元素A.n-iB.n-i+1C.n-i-14.某个栈的输入序列为1，2，3，4，下面的四个序列中()不可能是它的输出序列A.1,2,3,4B.2,3,4,1C.4,3,2,1D.3,4,1,25.对二叉排序进行()遍历可以得到结点的排序序列A.前序B.中序C.后序D.按层次6．A(1:5,1:6)的每个元素占5个单元，将其按行优先次序储存在起始地址为1000的连续的内存单元中，则元素A[5，5]的地址为（）。A1140B1145C1120D11257.有n个叶子结点的哈夫曼树的结点总数为（）。A不确定B2nC2n+1D2n-18.一个二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）的二叉树（树中结点个数大于1）。A空或只有一个结点B高度等于其结点数C任一结点无左孩子D任一结点无右孩子9.已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,则它的前遍历序列是（）。AacbedBdecabCdeabcDcedba10．若循环队列用数组A(0:m-1)存放其元素值，已知其头、尾指针分别是f和r,则当前队列中的元素个数是（）。A(r-f+m)modmBr-f+1Cr-f-1Dr-f二、判断题（每小题2分，对的打√，错的打×，共8分）若某二叉树的叶子结点数为1（树中只有一个结点的情况除外），则其先序序列和后序序列一定相反。（）2．对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先遍历可访到该图的每个顶点。()3．线性表的唯一存储形式是链表。（）4．在队列中，队头指针总是指向第一个数据元素。（）三、解释下列术语（每小题5分，共25分）1.关键路径2树的路径长度3.头结点4.数据的存储结构5.排序方法的稳定性四、解答题（每小题6分，共24分）1.满足下列条件的二叉树具有什么形状？前序和中序遍历次序相同；中序和后序遍历次序相同；前序和后序遍历次序相同；2.有一组关键字，如果以不同的次序输入，这时建立起来的二叉排序树是否相同？当以中序遍序这些二叉排序树时，其遍序的结果是否相同？为什么？3.具有144个记录的文件，若采用分块查找法查找，则分成几块最好？每块的最佳长度是多少？假定每块的长度是8，确定所在块、块中均采用顺序查找法查找，则平均查找长度是多少？4.写出所给数据表，采用快速排序方法按升序排序的每一趟的结果：（25，10，20，31，5，28）。五，编写算法（共23分）写出，建立一个具有n个顶点的无向网的邻接矩阵的算法。提示：先将矩阵A的每个元素都初始化成0，然后，读入边及数值（I,j,w）,将A的相应元素置成w.（13分）线性表V采用顺序存储结构，试编写删除V中的第i个元素起的k个元素的算法。（10分）数据结构试卷试5一、解释下列术语（每小题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-12.某个栈的输入序列为1，2，3，4，下面的四个序列中()不可能是它的输出序列A.1,2,3,4B.2,3,4,1C.4,3,2,1D.3,4,1,23.对二叉排序进行()遍历可以得到结点的排序序列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,则它的前遍历序列是（）。AacbedBdecabCdeabcDcedba9．若循环队列用数组A(0:m-1)存放其元素值，已知其头、尾指针分别是f和r,则当前队列中的元素个数是（）。A(r-f+m)modmBr-f+1Cr-f-1Dr-f10.一个二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）的二叉树（树中结点个数大于1）。A空或只有一个结点B高度等于其结点数C任一结点无左孩子D任一结点无右孩子三、判断题（每小题2分，对的打√，错的打×，共10分）1．若图G的最小生成树不唯一，则G的边数一定多于n-1，并且权值最小的边有多条（其中n为G的顶点数）。()2．对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先遍历可访到该图的每个顶点。()3．若某二叉树的叶子结点数为1（树中只有一个结点的情况除外），则其先序序列和后序序列一定相反。（）4．在队列中，队头指针总是指向第一个数据元素。（）5．线性表的唯一存储形式是链表。（）四、解答题（每小题6分，共24分）从一的平衡二叉树开始，把关键字（5，19，6，22，16，15，30）按出现的先后顺序逐一插入，从而构造一棵平衡二叉树排序树，每插入一个关键字后，若需要进行平衡旋转，则标明其旋转类型及旋转后的结果。满足下列条件的二叉树具有什么形状？前序和中序遍历次序相同；中序和后序遍历次序相同；前序和后序遍历次序相同；写出所给数据表，采用快速排序方法按升序排序的每一趟的结果：（25，10，20，31，5，28）。具有144个记录的文件，若采用分块查找法查找，则分成几块最好？每块的最佳长度是多少？假定每块的长度是8，确定所在块、块中均采用顺序查找法查找，则平均查找长度是多少？五，编写算法（共16分）写出，建立一个具有n个顶点的无向网的邻接矩阵的算法。提示：先将矩阵A的每个元素都初始化成0，然后，读入边及数值（i,j,w）,将A的相应元素置成w。（8分）线性表V采用顺序存储结构，试编写删除V中的第i个元素起的k个元素的算法。（8分）数据结构试卷试6一、填空题（共20分，每空1分）数据结构是研究数据元素之间抽象化的相互关系和这种关系在计算机中的存储结构表示，通常有下列四种存储结构：（1）、（2）、（3）和（4）。评价算法的标准很多，通常是以执行算法所需要的（5）和所占用的（6）来判别一个算法的优劣。队列操作的原则是（7），栈的插入和删除操作在（8）进行。对循环队列Q，它的最大存储空间是MAXSIZE，队头指针是front，队尾指针是rear，采用少用一个存储单元的方法解决假溢出时，队满的判断条件是（9），队空的判断条件是（10）。在以Head为表头指针的带有头结点的单链表和循环单链表中，判断链表为空的条件分别为（11）和（12）。假设二维数组A[6][8]，每个元素用相邻的4个字节存储，存储器按字节编址，已知A的开始存储位置为100，按行优先顺序存储的元素A[2][5]的第一个字节的地址为（13）。空格串的长度为串中所包含（14）字符的个数，空串的长度为（15）。有向图G用邻接矩阵A[n，n]存储表示，其第i行的所有元素之和等于顶点i的（16）。在关键字序列(12，23，34，45，56，67，78，89，91)中折半查找关键字为89和25的结点时，所需进行的比较次数分别为（17）和（18）。请说出两种处理哈希冲突的方法（19）、_（20）_。二、选择题（共20分，每题2分）对线性表，在下列哪种情况下应采用链式存储结构？（）A．经常需要随机存取元素B．经常需要进行插入和删除操作C．表中元素的个数不变D．表中元素需要占据一片连续的存储空间从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功情况下，则平均比较（）个结点。A．nB．n/2C．(n-1)/2若对某线性表最常进行的操作是在最后一个元素之后插入和删除第一个元素，则采用（）存储方式最节省运算时间。A．单链表B．双链表C．仅有头指针的单循环链表D．仅有尾指针的单循环链表在一个单链表中，若要删除p指针所指结点的后继结点，则执