数据结构(java)复习题及答案

一、选择题1、数据结构在计算机内存中的表示是指____A__A．数据的存储结构B.数据结构C.数据的逻辑结构D.数据元素之间的关系2、若一个算法的时间复杂度用T(n)表示，其中n的含义是（A）A．问题规模B．语句条数C．循环层数D．函数数量3、下列选项中与数据存储结构无关的术语是（D）A.顺序表B.链表C.链队列D.栈4、已知循环队列的存储空间大小为m，队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置，则向队列中插入新元素时，修改指针的操作是（D）A.rear=(rear-1)%m;B.front=(front+1)%m;C.front=(front-1)%m;D.rear=(rear+1)%m;5、栈和队列的共同点是__C______A.都是先进后出B.都是先进先出C.只允许在端点处插入和删除元素D.没有共同点6、已知一堆栈的进栈序列为1234,则下列哪个序列为不可能的出栈序列______D__A.1234B.4321C.2143D.41237、具有线性结构的数据结构是（C）A．树B．图C．栈和队列D．广义表8、假设以数组A[60]存放循环队列的元素，其头指针是front=47，当前队列有50个元素，则队列的尾指针值为（B）A．3B．37C．50D．979、若栈采用链式存储结构，则下列说法中正确的是（B）A．需要判断栈满且需要判断栈空B．不需要判断栈满但需要判断栈空C．需要判断栈满但不需要判断栈空D．不需要判断栈满也不需要判断栈空10、若一棵具有n(n0)个结点的二叉树的先序序列与后序序列正好相反，则该二叉树一定是（C）A.结点均无左孩子的二叉树B.结点均无右孩子的二叉树C.高度为n的二叉树D.存在度为2的结点的二叉树11、若一棵二叉树中度为l的结点个数是3，度为2的结点个数是4，则该二叉树叶子结点的个数是（B）A.4B.5C.7D.812、在n个结点的线索二叉树中，线索的数目为_C_______A．n-1B.nC.n+1D.2n13、一棵完全二叉树有1001个结点,其中有____B_____叶子结点A.500B.501C.503D.50515、一个有n个顶点的无向图最多有___C____条边。A.nB.n(n-1)C.n(n-1)/2D.2n16、以v1为起始结点对下图进行深度优先遍历，正确的遍历序列是（D）A．v1，v2，v3，v4，v5，v6，v7B．v1，v2，v5，v4，v3，v7，v6C．v1，v2，v3，v4，v7，v5，v6D．v1，v2，v5，v6，v7，v3，v4二、填空题1、一个算法具有5个特性：__有穷性_____、__可行性____、确定性、输入和输出4、队列的存储方式有__顺序队列__________和____链式队列_______。5、递归过程或函数调用时，处理参数及返回地址，需要一种称为__栈_____的数据结构。7、在单链表中某结点后插入一个新结点，需要修改___2____________个结点指针域的值。8、设栈S的初始状态为空，若元素a、b、c、d、e、f依次进栈，得到的出栈序列是b、d、c、f、e、a，则栈S的容量至少是_____3___________。10、设一个顺序循环队列容量为60，当front=47，rear=23时，该队列有______36____个元素。11、已知二维数组a[10][8]采用行主序存储，数组首地址是1000，每个元素占用4字节，则数组元素a[4][5]的存储地址是____________1176______________。12、已知一棵完全二叉树的根（第0个）结点层次为1，则第100个结点的层次为_____7___。12、中根遍历序列和后根遍历序列相反的二叉树是_______________结构均无左孩子的二叉树____________________。13、由256个权值构造一棵哈夫曼树，则该二叉树共有___256+255_______结点。14、用6个权值分别为6、13、18、30、7和16的结点构造一棵哈夫曼(Huffman)树，该树的带权路径长度为_____219____。15、深度为5的二叉树至多有___2^5-1___个结点。17、一个有n个顶点的无向连通图，最少有______n-1__________条边。18、交换排序法是对序列中的元素进行一系列比较，当被比较的两元素逆序时，进行交换。______和_____是基于这类方法的两种排序方法。19、在长度为n的顺序表L中查找指定元素值的元素，其时间复杂度为__________有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,99},当采用二分查找法查找关键字为82的元素时，_______次比较后查找成功。20、设用希尔排序对{98,36,-9,0,47,23,1,8,10,7}进行排序，给出的步长（也称增量序列）为5,则第一趟排序后的结果是__________________________________________。三、应用题1、将下列稀疏矩阵的非零元素表示成三元组的形式。2、画出下列广义表的双链表示：中国（北京，上海，江苏（南京，苏州），浙江（杭州），广东（广州））3、已知一棵二叉树的中根和后根遍历序列如下，画出据此构造的二叉树。中根遍历序列：DBHEIAFKCG后根遍历序列：DHIEBKFGCA4.已知一棵二叉排序树（结点值大小按字母顺序）的前序遍历序列为EBACDFHG，0200000000000210010070003A请回答下列问题：(1)画出此二叉排序树；(2)若将此二叉排序树看作森林的二叉链表存储，请画出对应的森林5、已知有向图的邻接表如图所示，请回答下面问题：(1)给出该图的邻接矩阵；(2)从结点A出发，写出该图的深度优先遍历序列。6、设用于通信的电文仅由5个字母{A,B,C,D,E}组成，字母在电文中出现的次数分别是2，4，5，7，8。为这五个字母设计哈夫曼编码。7、（1）分别以prim、kruscal算法构造下图的最小生成树。（2）Dijkstra算法求下图中顶点1到其他所有顶点的最短路径及长度。四、程序阅读题1、顺序循环队列中，出队方法如下，请补全空出的部分。PublicEdequeue(){If(!isEmpty()){Etemp=(E)this.value[this.front];This.front=___(this.front+1)%this.valuelegth()________________;return_______temp____;}returnnull;}2、以下是顺序栈类的声明，其中成员变量Value数组存储栈的数据元素，top表示当前栈顶元素的下标，请补充以下空白。importdataStructure.linearList.SStack;publicclassSeqStackEimplementsSStackE{privateObjectvalue[];privateinttop;publicSeqStack(intcapacity){this.value=newObject[Math.abs(capacity)];this.top=-1;}publicSeqStack(){this(10);}publicbooleanisEmpty(){//判断栈是否为空，若空栈返回truereturnthis.top__==-1________;}publicbooleanpush(Eelement){//元素element入栈，若操作成功返回trueif(element==null)return__false_______;if(this.top==value.length-1){Object[]temp=this.value;this.value=newObject[temp.length*2];for(inti=0;itemp.length;i++)this.value[i]=temp[i];}this.top___++_______;this.value[this.top]=___element________;return___true_____;}}