数据结构期末复习题

练习题：填空题1、元素项是数据的最小单位，数据元素是讨论数据结构时涉及的最小数据单位。2、设一棵完全二叉树具有100个结点，则此完全二叉树有49个度为2的结点。3、在用于表示有向图的邻接矩阵中，对第i列的元素进行累加，可得到第i个顶点的出度。4、已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有12个叶子的结点。n=n0+n1+n2+…+nm(1)又有除根结点外,树中其他结点都有双亲结点,且是唯一的(由树中的分支表示),所以,有双亲的结点数为：n-1=0*n0+1*n1+2*n2+…+m*nm(2)联立(1)(2)方程组可得：叶子数为：n0=1+0*n1+1*n2+2*n3+...+(m-1)*nm5、有一个长度为20的有序表采用二分查找方法进行查找，共有4个元素的查找长度为3。6、对于双向链表，在两个结点之间插入一个新结点需要修改的指针共4个。删除一个结点需要修改的指针共2个。7、已知广义表LS=(a,(b,c,d),e)，它的深度是2，长度是3。8、循环队列的引入是为了克服假溢出。9、表达式a*(b+c)-d/f的后缀表达式是abc+*df/-。10、数据结构中评价算法的两个重要指标是时间复杂度和空间复杂度。11、设r指向单链表的最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的三条语句是r->next=s;r=s;r->next=null;12、设有一个空栈，栈顶指针为1000H(十六进制)，现有输入序列为1，2，3，4，5，经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是23，而栈顶指针值是1012_H。设栈为顺序栈，每个元素占4个字节。13、模式串P=‘abaabcac’的next函数值序列为01122312。14、任意连通图的连通分量只有一个，即是自身。15、栈的特性是先进后出。16、串的长度是包含的元素个数。17、如果一个有向图中没有回路，则该图的全部顶点可能排成一个拓扑序列。18、在具有n个叶子结点的哈夫曼树中，分支结点总数为n-1。17619、在线性表的散列存储中，装填因子a又称为装填系数，若用m表示散列表的长度，n表示待散列存储的元素的个数，则a等于n/m。20、排序的主要目的是为了以后对已排序的数据元素进行查找。21、对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为O(1),在给定值为x的结点后插入一个新结点的时间复杂度为O(n)。22、线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是n/2。23、两个栈共享空间时栈满的条件top1=top2-1。24、深度为H的完全二叉树至少有H个结点；至多有2^H-1个结点；H和结点总数N之间的关系是H=[log2n]+1。15025、在有序表A[1…20]中，按二分查找方法进行查找，查找长度为4的元素的下标从小到大依次是13681113161926、设查找表中有100个元素，如果用二分法查找方法查找数据元素X，则最多需要比较7次就可以断定数据元素X是否在查找表中。26、数据结构被形式地定义为（D,R），其中D和R的含义是（D是数据元素的集合，R是数据关系的集合）。数据的逻辑结构包括哪四种类型（集合类型，线性结构，树形结构，图状结构）。从存储结构的概念上讲，顺序表是线性表的（顺序存储结构），链表是（链式存储结构）。27、根据初始关键字序列(17，25，3，39，12)建立的二叉排序树的高度为3。27、算法的五个重要特性有哪些。（有穷性、确定性、可行性、输入、输出）。抽象数据类型是指一个（数学模型）以及定义在该模型上的（一组操作）。28、设有一个n阶的下三角矩阵A，如果按照行的顺序将下三角矩阵中的元素（包括对角上元素）存放在n(n+1)个连续的存储单元中，则A[i][j]与A[0][0]之间有((i＋１)＊ｉ／２＋ｊ个数据元素。栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把栈称为FILO；队列的插入和删除运算分别在队列的两端进行，先进队列的元素必定先出队列，所以又把队列称为FIFO表。设一棵完全二叉树的顺序存储结构中存储数据元素为ABCDEF，则该二叉树的前序遍历序列为ABDEF，中序遍历序列为DBEAFC，后序遍历序列为DEBFCA。如果以链栈为存储结构，则出栈操作时(必须判别栈是否空)，与顺序栈相比，链栈有一个明显的优势是(通常不会出现栈满的情况)。循环队列采用数组data[1．．n]来存储元素的值，并用front和rear分别作为其头尾指针。为区分队列的满和空，约定：队中能够存放的元素个数最大为n-l，也即至少有一个元素空间不用，则在任意时刻，至少可以知道一个空的元素的下标是（front）；入队时，可用语句（rear=rear+1%n）求出新元素在数组data中的下标。设一棵完全二叉树有128个结点，则该完全二叉树的深度为8，有65个叶子结点。33、已知栈的输入序列为1，2，3…．，n，输出序列为a1，a2，…，an，a2=n的输出序列共有（n-1）种输出序列。设有向图G的存储结构用邻接矩阵A来表示，则A中第i行中所有非零元素个数之和等于顶点i的出度，第i列中所有非零元素个数之和等于顶点i的入度。35、将下三角矩阵A[l..8，1..8]的下三角部分逐行地存储到起始地址为1000的内存单元中，已知每个元素占4个单元，则A[7，5]的地址为（1100）。36、已知数组A[1..10，1..10]为对称矩阵，其中每个元素占5个单元。现将其下三角部分按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[5，6]对应的地址为（1095）。37、两个串相等的充要条件是，两个串的(长度)相等，且其所对应各个位置的（字符）也相等。39、在有n个结点的二叉链表中，值为非空的链域的个数为（n-1）。在有n个叶子结点的哈夫曼树中，总结点数是（2n-1）。在树形结构中，根结点数只有（1），其余每个结点有且仅有一个（前驱）元素结点。40、一棵二叉树L的高度为h，所有结点的度或为0，或为2，则这棵二叉树最少的结点数为(2h-1)。已知二叉树有50个叶子结点，则该二叉树的总结点数至少是（99）。将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为（98）。有64个结点的完全二叉树的深度为(7)。41、拓扑排序只能用于（有向无环图）。连通图是指图中任意两个顶点之间（都连通的无向图）。一个有n个顶点的无向连通图，它所包含的连通分量个数最多为(1)个。任何一个无向连通图的最小生成树（有一棵或多棵）。若含有n个顶点的图形成一个环，则它有（n）棵生成树。42、求图的最小生成树有两种算法，（普利姆）算法适合于求稠密图的最小生成树，（克鲁斯卡尔）算法适合于求稀疏图的最小生成树。设图G用邻接表存储，则拓扑排序的时间复杂度为(O(n+e))。44、从未排序序列中依次取出元素与已排序序列(初始时为空)中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为(插入排序)。对于关键字序列(12，13，11，18，60，15，7，18，25，100)，用筛选法建堆，则开始结点的键值必须为（60）。33、typedefstructnode{intkey;structnode*lchild;structnode*rchild;}bitree;bitree*bstsearch(bitree*t,intk){if(t==0)return(0);elsewhile(t!=0)if(t->key==k)t->lchild=t->rchild=0;elseif(t->key>k)t=t->lchild;elset=t->lchild;;}下面程序段的功能是实现冒泡排序算法，请在下划线处填上正确的语句。voidbubble(intr[n])272{for(i=1;i<=n-1;i++){for(exchange=0,j=0;jr[j+1]){temp=r[j+1];__r[j]=r[j+1]_;r[j]=temp;exchange=1;}if(exchange==0)return；}}下面程序段的功能是实现二分查找算法，请在下划线处填上正确的语句。structrecord{intkey;intothers;};intbisearch(structrecordr[],intk){intlow=0,mid,high=n-1;while(low<=high){mid=(low+high)/2;if(r[mid].key==k)return(mid+1);elseif(r[mid].key，<2,4>，<4,5>，<1,3>，<3,2>，<3,5>}，则给出该图的一种拓扑排序序列13245。38、设一组初始 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 关键字序列为(49，38，65，97，76，13，27，50)，则以d=4为增量的一趟希尔排序结束后的结果为4913275076386597。39、设二叉排序树的高度为h，则在该树中查找关键字key最多需要比较h次.二、选择题1、从逻辑上可以把数据结构分为（C）两大类。A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构2、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（C）(1<=i<=n+1)。A.O(0)B.O(1)C.O(n)D.O(n2)3、若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，pN,若pN是n，则pi是(A)。A.iB.n-iC.n-i+1D.不确定4、已知广义表L=（（x,y,z），a，（u，t，w）），从L表中取出原子项t的运算是（D）。A.head（tail（tail（L）））B.tail（head（head（tail（L））））C.head（tail（head（tail（L））））D.head（tail(head（tail（tail（L）））)）5、下列陈述中正确的是（D）。A.二叉树是度为2的有序树B.二叉树中结点只有一个孩子时无左右之分C.二叉树中必有度为2的结点D.二叉树中最多只有两棵子树，并且有左右之分6、设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（A）。173A．m-nB．m-n-1C．n+1D．条件不足，无法确定7、．算术表达式a+b*（c+d/e）转为后缀表达式后为（B）。A．ab+cde/*B．abcde/+*+C．abcde/*++D．abcde*/++8、关键路径是事件结点网络中（A）。A．从源点到终点的最长路径B．从源点到终点的最短路径C．最长回路D．最短回路9、具有12个关键字的有序表，二分查找的平均查找长度（C）。236A.2.5B.4C.3.1D.510、AVL树是一种平衡的二叉排序树，树中任一结点的（B）245A.左、右子树的高度均相同B.左、右子树高度差的绝对值不超过1C.左子树的高度均大于右子树的高度D.左子树的高度均小于右子树的高度11、线性表采用链接存储时，其地址（D）。A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续与否均可以12、栈和队列是两种特殊的线性表，只能在它们的（B）处添加或删除结点。 　Ａ．中间点 Ｂ．端点 Ｃ．随机存取点 Ｄ．结点13、输入序列为ABC，可以变为BAC时，经过的栈操作为（C）。A.push,pop,push,pop,push,popB.push,push,push,pop,pop,popC.push,push,pop,pop,push,popD.push,pop,push,push,pop,pop14、下面（C）不是算法所具有的特性。Ａ．有穷性Ｂ．确切性Ｃ．高效性 Ｄ．可行性15、下面关于串的的叙述中，（B）是不正确的？A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储16、数组A[6][7]的每个元素占五个字节，将其按行优先次序存储在起始地址为1000的内存单元中，则元素A[3][5]的地址是(A)。117A.1130B.1180C.1205D.121017、对于一个具有n个顶点的无向图，若采用邻接矩阵存储，则该矩阵的大小是（D）。195A．nB．(n-1)2　C．n-1D．n218、若广义表A满足Head(A)=Tail(A)，则A为（B）。A．（）B．（（））C．（（），（））D．（（），（），（））19、堆的形状是一棵(C)。A.二叉排序树B.满二叉树C.完全二叉树D.判定树20、若要在单链表中的结点*p之后插入一个结点*s，则应执行的语句是(A)A．s->next=p->next；p->next=s；　B．p->next=s；s->next=p->next；C．p->next=s->next；s->next=p；D．s->next=p；p->next=s->next；21、链表不具有的特点是（Ｂ）。A．插入、删除不需要移动元素B．可随机访问任一元素C．不必事先估计存储空间D．所需空间与线性长度成正比22、一个栈的输入序列为12345，则下列序列中不可能是栈的输出序列的是（B）。A.23415B.54132C.23145D.1543223、递归过程或函数调用时，处理参数及返回地址，要用一种称为（Ｃ）的数据结构。A．队列B．多维数组C．栈D.线性表24、设给定权值总数有n个，其哈夫曼树的结点总数为(Ｄ)。A．不确定B．2nC．2n+1D．2n-125、若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（Ｃ）。 课件 超市陈列培训课件免费下载搭石ppt课件免费下载公安保密教育课件下载病媒生物防治课件 可下载高中数学必修四课件打包下载 １０６　１０７A.快速排序B.堆排序C.归并排序D.直接插入排序26、设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。(Ｃ)A．688B．678C．692D．69627、若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为(D)A.1，2，3B.9，5，2，3C.9，5，3D.9，4，2，328、设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为（C）。(A)2，3，5，8，6(B)3，2，5，8，6(C)3，2，5，6，8(D)2，3，6，5，829、设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（A）。Aq=p->next；p->data=q->data；p->next=q->next；free(q)；Bq=p->next；q->data=p->data；p->next=q->next；free(q)；Cq=p->next；p->next=q->next；free(q)；Dq=p->next；p->data=q->data；free(q)；30、设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（C）。A．N0=N1+1B.N0=Nl+N2C.N0=N2+1D.N0=2N1+l31、设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为Nl，……，度数为m的结点数为Nm，则N0=（B）。A.Nl+N2+……+NmB.l+N2+2N3+3N4+……+(m-1)NmC.N2+2N3+3N4+……+(m-1)NmD.2Nl+3N2+……+(m+1)Nm32、设无向图G中的边的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为（A）。A.aedfcbB.acfebdC.aebcfdD.aedfbc26、某二叉树的先序序列和后序序列正好相反，则该二叉树的特点一定是（BB）。A.空或只有一个结点B.高度等于其结点数C.任一结点无左孩子D.任一结点无右孩子28、下面的说法中正确的是（B）。(1)任何一棵二叉树的叶子节点在三种遍历中的相对次序不变。(2)按二叉树定义，具有三个节点的二叉树共有6种。A．(1)，(2)B．(1)C．(2)D．(1)，(2)都错29、树有先根遍历和后根遍历，树可以转化为对应的二叉树。下面的说法正确的是（B）。A．树的后根遍历与其对应的二叉树的后根遍历相同B．树的后根遍历与其对应的二叉树的中根遍历相同C．树的先根遍历与其对应的二叉树的中根遍历相同D．以上都不对30、.下图的邻接表中，从顶点V1出发采用深度优先搜索法遍历该图，则可能的顶点序列是（D）。A.V1V2V3V4V5B.V1V2V3V5V4C.V1V4V3V5V2D.V1V3V4V5V231、以下说法不正确的是（D）。A．无向图中的极大连通子图称为连通分量B．连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点C．图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点D．有向图的遍历不可采用广度优先搜索32、设哈希表长为14，哈希函数H(key)=key％11，表中已有数据的关键字为15，38，61，84，四个，现将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是（DD）。A．8B．3C．5D．934、二维数组A的每个元素是由6个字符组成的串，其行下标i=0，l，…，8，列下标为j=1，2．…．10。设每个字符占一个字节,若按行先存储，元素A[8，5]的起始地址与A按列存储时起始地址相同的元素是（B）。A．A[8，5]B．A[3，10]C．A[5，8]D．A[0，9]35、.在n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为（B）。A.O(n)B.O(log2n)C.O(nlog2n)D.O(n2)37、关键路径是事件结点网络中（AA）。A．从源点到汇点的最长路径B．从源点到汇点的最短路径C．最长的回路D．最短的回路38、将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（AA）。A．nB．2n-1C．2nD．n-141、有向图G用邻接矩阵A存储，则顶点i的入度等于A中（BB）。A.第i行1的元素之和B.第i列1的元素之和C.第i行0的元素个数D.第i列0的元素个数42、用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下：20，15，21，25，47，27，68，35，8415，20，21，25，35，27，47，68，8415，20，21，25，27，35，47，68，84则所采用的排序方法是（DD）A．选择排序B．希尔排序C．归并排序D．快速排序43、设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为(AA)。(A)10，15，14，18，20，36，40，21(B)10，15，14，18，20，40，36，21(C)10，15，14，20，18，40，36，2l(D)15，10，14，18，20，36，40，2144、设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到HASH表中需要做（D）次线性探测。A.n2B.n(n+1)C.n(n+1)/2D.n(n-1)/2三、判断题1．如果两个串含有相同的字符，则这两个串相等。（　x）2．数组可以看成线性结构的一种推广，因此可以对它进行插入、删除等运算。（x　）3．二叉树是度为2的树。（　x）4．在顺序表中取出第i个元素所花费的时间与i成正比。（　x）5．在栈满情况下不能作进栈运算，否则产生“上溢”。　(v　）6．图G的生成树是该图的一个极小连通子图。（　v）7．所谓数据的逻辑结构指的是数据之间的逻辑关系。（x　）数据项8．二叉排序树的查找和折半查找的时间性能相同。（x）9．在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。（　x）10．一个有向图的邻接表和逆邻接表中表结点的个数一定相等。（v　）11、双向链表中至多只有一个结点的后继指针为空。（v）12、在循环队列中，front指向队列中第一个元素的前一位置，rear指向实际的队尾元素，队列为满的条件是front=rear。（x）13、对链表进行插入和删除操作时，不必移动结点。（v）14、栈可以作为实现程序设计语言过程调用时的一种数据结构。（v）15、在一个有向图的拓朴序列中，若顶点a在顶点b之前，则图中必有一条弧(x)。16、对有向图G，如果从任一顶点出发进行一次深度优先或广度优先搜索就能访问每个顶点，则该图一定是完全图。(x)17、“顺序查找法”是指在顺序表上进行查找的方法。（x）18、向二叉排序树插入一个新结点时，新结点一定成为二叉排序树的一个叶子结点。（v）19、二分查找要求序列顺序存储且关键字序列有序。（v）20、二路归并时，被归并的两个子序列中的关键字个数一定要相等。（x）21.调用一次深度优先遍历可以访问到图中的所有顶点。（x）21．分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。（v）22．冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。（v）23．满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。（v）24．设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。（x）25．层次遍历初始堆可以得到一个有序的序列。（x）26．设一棵树T可以转化成二叉树BT，则二叉树BT中一定没有右子树。（v）27．线性表的顺序存储结构比链式存储结构更好。（x）28．中序遍历二叉排序树可以得到一个有序的序列。（v）29.快速排序是排序算法中平均性能最好的一种排序。（v）30．不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。（v）31．当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。（v）32．设某堆中有n个结点，则在该堆中插入一个新结点的时间复杂度为O(log2n)。（v）33．完全二叉树中的叶子结点只可能在最后两层中出现。（v）34．哈夫曼树中没有度数为1的结点。（v）35．对连通图进行深度优先遍历可以访问到该图中的所有顶点。（v）36．先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。（v）37．由树转化成二叉树，该二叉树的右子树不一定为空。（x）38．线性表中的所有元素都有一个前驱元素和后继元素。（x）39.带权无向图的最小生成树是唯一的。（x）四、应用题1、已知一棵二叉树的中根序列和后根序列分别为CBEDAFIGH及CEDBIFHGA，请画出这棵二叉树，并给出其先序序列。ABCDEGFIH1、已知一棵二叉树的先根序列和中根序列分别为ABDGHECFIJ及GDHBEACIJF，请画出这棵二叉树，并给出其后序序列。GHDEBJIFCA2、将下列由三棵树组成的森林转换为二叉树。（只要求给出转换结果）3、已知无向图如下所示：（1）．给出从V1开始的广度优先搜索序列；（2）．画出它的邻接表；（3）．画出从V1开始深度优先搜索生成树。4.假定用于通讯的电文仅有8个字母C1，C2，…，C8组成，各个字母在电文中出现的频率分别为5，15，3，6，22，11，30，8，请先构建一棵哈夫曼树，计算其WPL值，并为这8个字母设计相应的哈夫曼编码4、假定用于通讯的电文仅有8个字母C1，C2，…，C8组成，各个字母在电文中出现的频率分别为5，25，3，6，10，11，36，4，请先构建一棵哈夫曼树，计算其WPL值，并为这8个字母设计相应的哈夫曼编码。5、已知一表为（Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec）,按表中顺序依次插入初始为空的二叉排序树，要求：(1)画出建立的二叉排序树（值的大小以字母顺序为准）。(2)对该二叉排序树作中序遍历，试写出遍历序列。(3)求出在等概率情况下查找成功的平均查找长度。6、已知一个图的顶点集V和边集G分别为：V={0,1,2,3,4,5,6,7};E={(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)25,(2,4)13,(3,5)9,(3,6)10,(4,6)4,(5,7)20};按照普里姆算法从顶点0出发得到最小生成树，试写出在最小生成树中依次得到的各条边。(0,1),(0,3),(0,2),(1,5),(3,6),(6,4),(5,7)。7、设一哈希表长为13，采用线性探测法解决冲突，哈希函数H(key)=key%13,（1）画出在空表中依次插入关键字25，20，34，15，21，32，29，82，57后的哈希表。（2）求在等概率情况下，查找成功和查找不成功的平均查找长度。7、已知散列函数为H(K)=Kmod11,健值序列为{47，7，29，11，16，92，22，8，3}哈希表长为11，采用线性探测法处理冲突，试构造闭散列表，并计算查找成功和不成功的平均查找长度。8、已知待排序的序列为（403，187，312，61，818，170，857，272，633，442），试完成下列各题。(1)根据以上序列建立一个堆（画出第一步和最后堆的结果图），希望先输出最小值。(2)输出最小值后，如何得到次小值。（并画出相应结果图）。8、已知待排序的序列为（503，87，512，61，908，170，897，275，653，462），试完成下列各题。(1)根据以上序列建立一个堆（画出第一步和最后堆的结果图），希望先输出最小值。(2)输出最小值后，如何得到次小值。（并画出相应结果图）。9、下图表示一个地区的交通网，顶点表示城市，边表示连结城市间的公路，边上的权表示修建公路花费的代价。怎样选择能够沟通每个城市且总造价最省的n-1条公路，画出一个方案。v2v4v1v5v3v61621111433619186510、已知图G=（V,E），其中V={v1,v2,v3,v4,v5},E={,,,,),}；画出这个图的图形并写出所有的拓扑序列。11、设有关键码序列{19，32，40，13，30，24，35}，请给出平衡二叉树的构造过程（只需要给出不平衡时到平衡的过程即可）。11、设有关键码序列{20，35，40，15，30，25，38}，请给出平衡二叉树的构造过程（只需要给出不平衡时到平衡的过程即可）。12、已知散列函数为H(K)=Kmod13,健值序列为12，31，15，54，04，78，22，29，34，54，29，47，采用拉链法处理冲突，试构造开散列表，并计算查找成功的平均查找长度。12、已知散列函数为H(K)=Kmod13,健值序列为13，41，15，44，06，68，12，25，38，64，19，49，采用拉链法处理冲突，试构造开散列表，并计算查找成功的平均查找长度。13、对于下列一组关键字36，48，25，55，80，17，11，72，试写出快速排序每一趟的排序结果。13、对于下列一组关键字46，58，15，45，90，18，10，62，试写出快速排序每一趟的排序结果。10,15,18,45,46,58,62,9014、对下面的关键字集（30，14，25，43，35，27，64，49），若查找表的装填因子为0.8，采用线性探测再散列解决冲突：（1）设计哈希函数；（2）画出哈希表；（3）求查找成功的平均查找长度。14、在如下数组A中链接存储了一个线性表，表头指针为A[0].next，试写出该线性表。A01234567data605078903440next3572041线性表为：（78，50，40，60，34，90）15、按顺序输入下列顶点对:(V1,V2)、(V1,V6)、(V2,V6)、(V1,V4)、(V6,V4)、(V1,V3)、(V3,V4)、(V6,V5)、(V4,V5)、(V1,V5)、(V3,V5)。（顶点序列为：V1，V2，V3，V4，V5，V6）（1）画出相应的邻接表。（2）写出在邻接表上，从顶点3开始（表下标从0开始）的DFS序列和DFS生成树五、算法与程序设计1、阅读算法完成题目要求：（1）说出下列算法的功能。templatestructBinnode{Tdata;Binnode*prior,*next;};boolUnknown(Binnode*first){Binnode*p,*q;p=first->next;q=first->prior;while(p!=q&&p->prior!=q)if(p->data==q->data){p=p->next;q=q->prior;}elsereturn0;return1;}//判断双链表的对称性算法功能：（2）根据下列算法和输入的数据画出生成的链表形式。templateLinkList::LinkList(intn){first=newNode;Node*s;Tx;first->next=NULL;;for(inti=0;i>x;s=newNode;s->data=x;s->next=first->next;first->next=s;}}输入数据为：123456输出结果为：（3）说出下列算法的功能，它是采用什么结构实现的。templatevoidBiTree::Unknown(BiNode*root){constintMaxSize=100;intfront=0;intrear=0;BiNode*Q[MaxSize];BiNode*q;if(root==NULL)return;else{Q[rear++]=root;while(front!=rear){q=Q[front++];cout<data<<"";if(q->lchild!=NULL)Q[rear++]=q->lchild;if(q->rchild!=NULL)Q[rear++]=q->rchild;}}}算法功能：二叉树的层序遍历对列（4）阅读下列算法求出调用该算法后输出结果。voidAE(Stack&S){InitStack(S);Push(S,30);Push(S,40);Push(S,50);intx=Pop(S)+2*Pop(S);Push(S,x);inti,a[4]={5,8,12,15};for(i=0;i<4;i++)Push(S,a[i]);while(!StackEmpty(S))cout<next;while(p&&p－>next－>data!=x){q=p;p=p－>next;}if(p){q－>next=p－>next;free(p);}}算法的功能：删除单链表L中值为X的结点的直接前驱结点2、程序设计(1)设有一单链表L，结点结构为data|next，编写算法判断该单链表L中的元素是否成等差关系，即：设各元素值次为a1,a2,a3,…,an，判断ai+1-ai=ai-ai-1是否成立。若是返回1，否则返回0。函数说明为：intdengcha(Node*L)；(2)写出二分查找的非递归算法。(要求统计查找过程中元素的比较次数)函数说明为：intbinsearch(intr[],intn,intk)；(3)设单链表以非递减有序排列，设计算法实现在单链表中删除值相同的多余结点。函数说明为：VoidLinklist::purge(Node*first)；（3）templateVoidpurge(Node*first){Node*p,*q;P=first->next;While(p->next)If(p->data==p->next->data){q=p->next;p->next=q->next;deleteq;}Elsep=p->next;}(4)写出图在邻接表存储结构下广度优先的遍历算法。函数说明为：template函数说明为：voidALGraph::BFSTraverse(intv)；（5）编写计算二叉树最大宽度的算法（二叉树的最大宽度是指二叉树所有层中结点个数的最大值）。（6）设计有向图（AOV网）在邻接表存储结构下的拓扑排序算法。template函数说明为：voidALGraph::TopSort()；（6）假设哈希函数为H（key）,编写用链地址法解决冲突的哈希表的插入和删除算法。voidF2(HashTable&H,keytypeKey){//哈希表插入，用链地址法解决冲突i=H(Key);;//获取哈希地址if(H[i]==Null){s=(Linklist)malloc(sizeof(Lnode));s→data=key;s→next=H[i];H[i]=s;}//ifelse{p=H[i];//查找while(p&&p→data!=key)p=p→next;if(p→data==key)exit(1);else{s=(Linklist)malloc(sizeof(Lnode));//产生新结点，插入表头s→next=H[i];H[i]=s;}//else}//else}//F2voidDelete_HS(HashTable&H,KeyTypekey){//哈希表删除，用链地址法解决冲突i=H(key);//获得哈希地址if(H[i]==Null)exit(1);p=H[i];q=p;//p为工作指针，q为p前趋while(p&&p→data!=key){//查找q=p;p=p→next;}//whileif(!p)exit(1);if(q==H[i]){//key为第一结点H[i]p→next;free(p);}//ifelse{q→next=p→next;free(p);}//else}//Delete_HS（7）设计在链式存储结构上交换二叉树中所有结点左右子树的算法。typedefstructnode{intdata;structnode*lchild,*rchild;}bitree;voidswapbitree(bitree*bt){bitree*p;if(bt==0)return;swapbitree(bt->lchild);swapbitree(bt->rchild);p=bt->lchild;bt->lchild=bt->rchild;bt->rchild=p;}（素材和资料部分来自网络，供参考。可复制、编制，期待您的好评与关注）