数据结构期末复习指导

《数据结构期末复习指导》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构期末复习指导考试题型及分值：1.单项选择题（每题3分，共15分）2.填空题（每空3分，共45分）3.运算题（每小题8分，共16分）4.算法应用题（每小题8分，共16分）5.编写算法（8分）一、单选题1.若需要利用形参胃接访问实参，则应把形参变量说明为（）参数。A指针B引用C值D函数2.假定利用数31a[N]顺序存储一个栈，用top表示栈顶指针，top==-1表示栈空，并已知栈未空，当退栈并返回栈顶元索时所执行的操作为（）。Areturna[—top];Breturna[top--];Creturna[++top];Dreturna[

2、top++];3.假定一个链队的队首和队尾指针分别为f和r,则判断队空的条件为（）。Af==rBf!=NULLCr!=NULLDf=NULL4.在一棵具有n个结点的二叉树屮，所有结点的空指针数等于（）。AnBn-1Cn+1D2n5.从堆中删除一个元素的时间复杂度为（）。A0（1）B0（n）C0（log2n）D0（nlog2n）6.利用n个值作为叶子结点的权牛成的哈夫曼树屮共包含有（）个结点。AnBn+1C2nD2n~l7.在一个带权连通图G'P，劝值最小的边一定包含在6的（）中。A最小生成树B生成树C广度优先生成树D深度优先生成树&一个有n

3、个顶点和n条边的无向图一定是（）A连通的B不连通的C无回路D有回路9.在一个长度为n的顺序存储的线性表屮，删除第i个元素（lWiWn）时，需要从前向后依次前移（）个元素。A.n-iB.n-i+1C.n-i-1D.i10.设一个广义表中结点的个数为n,则求广义表深度算法的时间复杂度为（）。A.0（1）B.0（n）C.0（n2）D.0（log2n）11.假定一个顺序队列的队首和队尾指针分别为f和“则判断队空的条件为（）。A.f+l==rB.r+l=fC.仁二0D.f=r12.从堆中删除一个元素的时间复杂度为（）。A.0（1）B.0（log2n）

4、C.0（n）D.0（/71og2/?）9.在一个单链表HL中，若耍向表头插入一个由指针p指向的结点，则执行（）。AHL=p;p->next=HL;Bp->next=HL;HL=p;Cp->next=IIL;p=HL;Dp->next=HL->next;HI厂〉next=p;9.在一个顺序队列屮，队尾指针指向队尾元素的()位置。A询一个元素B后-一个元素C当両10.从二叉搜索树中查找一个元素时，其时间复杂度大致为()。B0(1)A0(n)C0(log2n)D0(n2)11.由权值分别为3,&6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长

5、度为()。A24B48D72C5312.在一个长度为n的线性表中顺序査找值为x的元素时，在等概率情况下查找成功时的平均杏找长度为()。C.(n+l)/2)进行。C.任意位置D.(n-l)/2D.指定位置A.nB.n/213.栈的插入和删除操作在(A.栈顶B.栈底19.假定一个链队的队首和队尾指针分别为front和rear,则判断队空的条件为(A・frontearB.front!=NULLC.rear!二NULLD.front==NULL20.从堆中删除一个元素的吋间复杂度为()。A.0(1)B.0(log2n)C.0(n)D.0(/71og

6、2/?)二、填空题1.在线性结构、树结构和图结构屮，前驱和后继结点之间分别存在着、和的联系。2.在线性表的单链接存储中，若一个元素所在结点的地址为P，则其后继结点的地址为,若假定P为一个数组。中的下标，则其后继结点的下标为。3.在初始化一个稀疏矩阵的函数定义屮，矩阵形参应说明为参数。4.栈又称为表，队列又称为表。5.后缀表达式“45+3*74+*”的值为o6.假定一棵树的广义表表示为A(B(C,D(E,F,G),H(I,J))),则树中所含的结点数为个，树的深度为,树的度为07.对于一棵具有n个结点的二义树，对应二义链表小指针总数为个，具中

7、个用于指向孩子结点，个指针空闲着。8.对一棵二叉捜索树进行中序遍历时，得到的结点序列是一个o9.在一个图中，所有顶点的度数之和等于所有边数的倍。10.对于一个貝有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别为和条。11.以二分杳找方法从长度为n的顺序存储的线性表中杳找一个元素时，平均杏找长度小于等于，时间复杂度为。12.在索引表中，每个索引项至少包含有域和域这两项。13.在线性表的存储中，无法查找到一个元素的前驱或后继元素；在线性表的存储中，对每一个元索只能采用顺序查找。14.在一棵树屮，所有叶了结点都处在上，所有叶

8、了结点屮空指针数等于该树小所有的总数加1。1.在堆排序的过程中，对n个记录建立初始堆需耍进行次筛运算，由初始堆到堆排序结束，需要对树根结点进行次筛运算。2.对20个记录进行归并排