数据结构案例教程（CC++版）第2版 试题

PAGE268数据结构期中试卷一、填空题（每空2分，共20分）1.你学过的线性数据结构有。2.稀疏矩阵的压缩存储方法有两种：分别是和。3.(a+b*c-d)/(e+f)的后缀表达式是。4.假设以一维数组S[n(n+1)/2]作为n阶对称矩阵A的存储空间，以行序为主序存储A的下三角，则元素A[5][8]的值存储在S[_______]中。5.设n>0，且有如下程序段：cin>>n;i=n;while(i>0)i=i/2;则该程序的时间复杂度为___________________。6.下列函数的功能是实现两个字符串的比较，试根据字符串比较运算的定义，完善该函数：intstrcmp(chars[],chart[]){inti=0;while(s[i]==t[i]&&s[i]!=’\0’)i;}7.设栈S和队列Q的初始状态均为空，元素abcdefg依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是bdcfeag，则栈S的容量至少是。8.若一棵树中度为1的结点有n1个，度为2结点有n2个……度为m的结点有nm个，则该树的叶结点有个。9.将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是。10.线索二叉树中的“线索”是指。二．简要回答下列问题（第1~5题每小题6分，第6、7题每题10分，共50分）1.什么是算法？如何评价算法的好坏？2.试比较顺序存储结构与链式存储结构的优缺点。3.请说明编写递归算法的思路。4.已知A、B、C、D、E、F的权值分别为10、30、8、12、15、25，按步骤求解它们的Huffman编码。5.已知某二叉树的中序遍历序列为ACBFDE，后序遍历序列为ABCDEF，试画出该二叉树，并写出前序遍历序列。6.设有一个广义表L=(x,(),(x,y),(x,(y,z)))，试画出它的存储结构，写出其结点的类型定义。7.树有哪些存储方法？设有一棵树T=（D，R），其中D=(A,B,C,X,E,F)，R={(A,B),(A,E),(A,F),((B,X),(F,C)}，分别画出它的各种存储结构。三、算法设计题（每题10分，共30分）1.设线索二叉树使用二叉链表存储，试编写算法：查找指针p所指结点的父结点。2.已知模式串的next数组，试编写串的模式匹配算法KMP。3.已知一个带表头结点的单链表，结点结构为data和link，假设该链表只给出头指针head，请设计一个尽可能高效的算法，查找链表中倒数第k个的结点。如查找成功，则输出该结点的data值，并返回1；否则返回0。数据结构期终试卷（A卷）一、填空题（每题2分，共20分）1.算法的健壮性是指。2.对一个线性表分别进行遍历和逆置运算，最好的时间复杂度分别为和。3.n个数入栈，所有可能的出栈序列共有种。4.下面程序段的时间复杂度为（n>1）。sum=1;for(i=0;sum<n;i++)sum+=i;5.若某二叉树有20个叶子节点，有30个节点仅有一个孩子，则该二叉树的总的结点数是。6.若以{4，5，6，7，8}作为叶子节点的权值构造Huffman树，则该Huffman树的根结点权值为。7.线索二叉树的左线索指向其，右线索指向其。8.若含n个顶点的图形成一个环，则它的生成树可能有种。9.对于具有300个记录的文件，采用分块索引查找法查找，其中用二分查找法查找索引表，用顺序查找法查找块内元素，假定每块长度均为30个元素，则平均查找长度为。10.有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值为82的结点时，经次比较后查找成功。二、回答问题（共56分）1.设一组记录的关键字为{4，5，7，2，1，3，6}，请回答相关问题：（1）按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成后的二叉排序树，并求出在等概率情况下查找成功的平均查找长度。（3分）（2）按表中元素的顺序进行插入生成一棵AVL树，画出该树。并求出在等概率情况下查找成功的平均查找长度。（4分）2.下图是一个四阶B树，请回答相关问题：（1）B+树和B树的主要区别是什么？（4分）（2）插入关键字87，画出插入调整后树的形状。（4分）2025202561707530608035508285903.已知记录关键字集合为（53，17，19，61，98，75，79，63，46，49），要求散列到地址区间[0，10]中，散列函数选用除留余数法(mod11)。请回答相关问题：（1）画出形成的散列表（若产生冲突，用开放定址的线性探测再散列法解决）。（4分）（2）计算在等概率情况下查找成功时的平均查找长度。（2分）4.有7个顶点(v1，v2，v3，v4，v5，v6，v7)的有向图的邻接矩阵如右图。请回答相关问题：（1）画出该有向图。（2分）（2）画出邻接表。（2分）（3）写出从v1出发的深度优先遍历和广度优先遍历序列。（4分）（4）将图看成AOE网，画出关键活动及相应的有向边，写出关键路径的长度。（4分）5.阅读下列函数，回答相关问题：intarrange(inta[],int1,inth,intx){//1和h分别为数据区的下界和上界inti,j,t;i=1;j=h;while(i<j){while(i<j&&a[j]>=x)j--;while(i<j&&a[i]<x)i++;if(i<j){t=a[j];a[j]=a[i];a[i]=t;}}if(a[i]<x)returni;elsereturni-1;}（1）写出该函数的功能。（4分）（2）写一个调用上述函数实现下列功能的算法：对一整型数组b[n]中的元素进行重新排列，将所有负数均调整到数组的低下标端，将所有正数均调整到数组的高下标端，若有零值，则置于两者之间，并返回数组中零元素的个数。（6分）6.数组a存储了N个整数，请回答相关问题：（1）请完善对数组a进行堆排序的程序。（6分）voidHeapAdjust(inta[],inth,ints){rc=a[h];for(j=;j<=s;j*=2){if((j<s)&&(a[j]<a[j+1]))++j;if(!(rc<=a[j]))break;;h=j;};}voidHeapSort(inta[],intn)//对a[1]，a[2]，…，a[n]进行堆排序{for(i=;i>0;--i)HeapAdjust(a,i,n);for(i=;i>1;--i){t=a[1];a[1]=a[i];a[i]=t;;}}（2）上面程序建成的堆是大顶堆还是小顶堆？（2分）（3）对n个元素进行初始建堆的过程中，最多进行次数据比较。（2分）（4）堆排序稳定吗？请举例说明。（3分）三、算法设计题（每题12分，共24分）1.已知一棵树T用二叉链表表示，其结点形式如下，试编写一算法求树T中各结点的度数。leftdatarightdegree（1leftdatarightdegree（2）编写算法。（8分）2.判断有向图是否存在回路。若存在返回1，否则返回0。（1）写出相应的结构定义。（4分）（2）编写算法。（8分）数据结构期终试卷（B卷）一、填空题（每题2分，共20分）1.算法是指。2.下面程序段的时间复杂度为（n>0）。i=n;while(i>0)i=i/2;3.设有2个顺序栈共享一个数组S[N]，其中第一个栈的栈顶指针top1的初值为–1，进栈时top1++；第二个栈的栈顶指针top2的初值为N，进栈时top2--，则判断该共享栈满的条件是。4.循环队列的元素存放在一维数组data[MaxSize]中，用变量front和rear分别表示队头元素和队尾元素后一个位置在数组中的下标，则该队列中元素的个数可表示为。5.假设以一维数组S[n(n+1)/2]作为n阶对称矩阵A的存储空间，以行序为主序存储A的下三角，则元素A[3][6]的值存储在S[]中。6.设源串S="bcdcdcb"，模式串P="cdcb"，按KMP算法进行模式匹配，当"S2S3S4"="P1P2P3"，而S5P4时，S5应与比较。7.一棵完全二叉树共有2023个结点，则该二叉树叶子结点个数为。8.具有n个结点的连通图中，至少有条边。9.有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值为82的结点时，经次比较后查找成功。10.时间复杂度为O(nlog2n)的排序方法请至少写出两种。二、简答题（共20分，每题5分）1.评价一个算法好坏的标准是什么？（5分）2.已知一棵二叉树的顺序存储如下（依照完全二叉树的结点编号次序，依次存放各个结点），请写出该二叉树的先序、中序和后序序列。（5分）123456789101112131415ABCDEFGHIJ3.请简述最短路径算法Dijkstra的基本思想。4.将序列{50，38，66，98，77，13，28，50}建立一个堆结构，试画出该堆，并标明其是大根堆或是小根堆。（5分）三、求解题（共30分，每题10分）1.假设给定一个电文“ADCEBDABDCEBDBCDCDCDE”，请根据各字符在该电文中出现的频率完成：（1）建立一棵Huffman树。（5分）（2）给出电文中各字符所对应的Huffman编码及平均码长。（5分）2.已知一个无向带权图G（含有结点1、2、3、4、5）的邻接矩阵如下：（1）画出图G。（3分）（2）画出图G的邻接表。（4分）（3）画出该图的最小生成树。（3分）3.已知记录关键字集合为{53，17，19，61，98，75，79，63，46，49}，要求散列到地址区间[0，10]中，散列函数选用除留余数法（mod11）。请回答相关问题：（1）画出形