大学现代远程教育课程《数据结构》期末考试复习题及参考答案

[]A.first==NULL4.在系统实现递归调用时需利用递归工作记录保存实际参数的值。在传值参数情形，需为对应形式参数分配空间，以存放实际参数的副本；在引用参数情形，需保存实际参数的[]， 2iA.2，4，3，1，5，6B.3，2，4，1，6，5C.4，3，2，1，5，6D.2，3，5，1，6，420.二维数组A［1218］采用列优先的存储方法，若每个元素各占A.(19，23，56，34，78，67，88，92)B.23，56，78，66，88，92，19，34)C.(19，23，34，56，67，78，88，92)D.(19，23，67，56，34，78，92，88)25.若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为[]}InitQueue(Q);EnQueue(QA．Q->rear==Q->frontB.(Q->rear+1)%maxsize==Q->frontC.Q->rear==0[]A.BDGCEFHAB.GDBECFHAC.BDGAECHFD.GDBEHFCA43.排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一45.散列查找是由键值确定散列表中的位置，进行存储或查找C.使用抽象数据类型的用户可以自己定义对抽象数据类型中数据的各种操作D.抽象数据类型的一个特点是使用与实现分离A.(i+3)*i／2D.(i+1)*i／2C.(2n—i+1)*i／2}A．O(1)Bintf(unsignedintn){}搜索后面5个元素的概率相同，均为3／40，则搜索任一元素的平均搜索长度为[]A．5.5B．5C.39／8D.19／4下，搜索成功时间元素的平均比较次数为[]68.带头结点的单链表first为空A.first==NULL;B.first->link==NULLC.first->link==first70.设有一个广义表A((x，(n，b))，intfront,rear;A.Q.from==Q,rear;B.Q.fro则时间复杂度为_；6.设线性表中元素的类型是实型，其首地址为1024，则线性表中第7.对于顺序存储的栈，因为栈的空间是有限的，在进行运算时，可能发生栈的上溢,在进} 24.在树中存在唯一的一个结点，我们把这个结点称为。25.线性表的两种存储结构一种为顺序存储，另一种为。29.在线性结构中，第一个结点30.在树形结构中，树根结点没有结点，其余每个结点有且只有个直接前驱结点，叶子31.在图形结构中，每个结点的前驱结点数和后续结点数可以。32.线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之while(q->next!=p)q=q->ne36.两个串相等的充分必要条件是。38.二维数组A[10..20][5..143.已知一个图的邻接矩阵表示，删除所有从第i个结点出发的边的方法是54.一个无序序列可以通过构造一棵树而变成一个有序树，构造树的过程即为对无序序列进行排____56.在堆排序，快速排序和归并排序中，若只从存储空间考虑，则应首先选取方法，其次选取方法，最后选取方法；若只从排序结果的稳定性考虑，则应选取方法；若只从平均情况下排序57.属性与服务相同的对象构成类，类中的每个对象称为该类的·58.在类的继承结构中，位于上层的类叫做，其下层的类则叫做类.68.在一棵二叉搜索树中，每个分支结点的左子树上所有的结点的值一定该结点的值，右子69.当向一个小根堆插入一个具有最一小值的元素时，该元素需要逐层调整，直到被调整到 71.对用邻接距阵表示的具有n个顶点和e条边的图形进行任一种遍历时，其时间复杂度为对用邻接表表示的图进行任一种遍历时，其时间复杂度为 75.n个(n>o)顶点的连通无向图中各77.给定一组数据对象的关键码为{46，79，56，38，40，78.在索引表中，若一个索引项对应数据对象表中的一个表项，则称此索引为稠密索引；若对应数V2V8E={<a,b>,<a,c>,<b,f>,<c,d>,<c,e>,<d,a>,假定该图采用邻接矩阵表示，则分别写出从顶点a出发进行深度优先搜索遍历和广度优先搜索遍历4.已知一棵二叉树的中序和后序序列如下，求该二叉树的高度(假定空树的高度为-1)和度V={0，l，2，3，4，5，6}；E={(0，1)19，(0，2)10，(0，024685914.假定对线性表(38，25，74，52，48，65，36)进行散列存储，采用H(K)=K％9作为散列函数，若分别采用线性探查法和链接法处理冲突，则对应的平均查找长度分别为和。广度遍历图G所得结点序列为（BG的一个拓扑序列是（C从结点V1到结点V8的最短路径为（DV={0，1，2，3，4，5，6，7}；E={(0，1)8，(0，2)5，( 22.假定一组记录的排序码为（46，79，56，38，40，80，25，34在对其进行快速排序的过程中，进行第一次划分后得到的排序码序列为。）；boolFind（BtreeNode*BST，ElemType&3.根据下面函数原型，编写一个递归算法，统计并返回以BT为树根指针的二叉树中所有6.编写递归算法，对于二叉树中每一个元素值为x的结点，删去以它为根的79{intBTreeEqual(BinTreeNOde*T1，BinTreeNode*T2)；(3)从单链表中查找出所有元素的最大{intx;NodeType*p;p=Head->next;}}3.下列函数是二叉排序树的什么算法？如果K值为5，针对下图所示二叉树，运行下列算法，输出是什while((q!=NULL)&&(flag==}}42278typedefintelemtype;#include“stack.h”{}}.14.逻辑结构和物理结构数据元素O(n)、O(m*n)233.有穷性、确定性、可行性、输入、输出36.两个串的长度相等且对应位置的字符相同37.200+（6*20+12）=326252.2、4、356.堆排序、快速排序、归并排序、归并排序、快速排序、堆排序61.p一>Link=toptoph65.3x2.45／6－*+l／12*(1+2+l+l+l+l+2+4+5+2+5+6)：3l／1210.在这个AVL树中删除根结点时有两种方案:1234561111122.（40，34，25，38，46，80，56，79）01015001 000006-----0001 123456101001120010013000100401000050001010V1V4^V2V6^V3V5V6V1V2于不是完全二叉树，在顺序结构存储中对叶子结点的判定是根据其左右子女为0。叶子和双亲结点if(i*2)>len)councount++;//无左右子女的结点是叶子boolFind（BtreeNode*BST，ElernType＆item）{while（BST！=NULL）{}}elseif(BT->left==NULL&&BT->rigwhile(i<=a.length-1)&&(i<=b}c=a;p=a->next;q=b->next;}}while(p){pn=p->next;p->next=c->while(q){qn=q->next;q->next=c->next;c->next=q;q=q//删除bt