数据结构 练习 答案.doc

《数据结构 练习 答案.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数据结构测验一、填空题1、数据结构一般包括　逻辑结构　、　物理结构　和数据操作三个方面的内容。2、无向图的三种常存储表示方法　邻接矩阵、　邻接表　、　邻接多重表　。3、广义表((a)，((b)，j，(((d))))的表头是　(a)　，表尾是　(((b)，j，(((d))))　。4、由一棵二叉树的前序序列和　中序序列　可唯一确定这棵二叉树。5、栈顶的位置是随着　入栈　和　出栈操作而变化的。6、用7，5，2，4作为四个叶结点a，b，c，d的权值，构造赫夫曼树，其带权路径长度为　　35　　。7、对称矩阵的下三角元素a[i，j]的值存放在一维数组V的元素V

2、[k]中，k与i，j的关系是k=i´(i-1)/2+j－1，i≥j；j´(j-1)/2+i－1，inext=sb）s->next=top->next；top->next=sc）s->next=top；top=sa）s->next=top；to

3、p=top->next2、在非空的线性表中，有且只有一个直接前驱和一个直接后继的结点是（B）a)开始结点b)内部结点c)终端结点d)所有结点3、有m个叶结点的赫夫曼树所具有的结点数为（C）a)mb)m+1c)2m-1d)2m4、某二叉树的前序遍历序列为ABDGCEFH，中序遍历序列为DGBAECHF，则后序遍历序列为（D）a)BDGCEFHAb)GDBECFHAc)BDGAECHFd)GDBEHFCA5、二维数组A[4][4]，数组起始地址loc[0][0]=1000，数组元素的长度为2，则loc[2][2]是（D）a)1002b)1010c)10

4、08d)10206、对于一个具有n个节点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（D）a)nb)(n+1)2c)n-1d)n27、二叉树和度为2的树的相同之处是（D）a）每个结点都有一个或两个孩子结点b）至少有一个根结点c）至少有一个度为2的结点d）每个结点至多只有一个双亲结点8、某个图的邻接表中有奇数个链表结点，则该图（C）a）一定有奇数个顶点a）一定有偶数个顶点b）一定是有向图c）可能是无向图三、分析题1、从顶点V3开始利用普里姆算法构造无向网络的最小生成树。画出最小生成树的构造过程并写出算法执行过程中closedge数组状态和最终状态。

5、BCDEHFIA2、写出下列二叉树的前序、中序和后序遍历的顺序。前序序列：ABDEHCFI中序序列：DBHEACIF后序序列：DHEBIFCA四、设有链式存储结构的二叉树，写一算法计算其中树叶结点的数目。假设二叉树以二叉链表方式存储。count=0;intCountLeaf(BiTreeT){if(T){if(T->lchild==NULL&&T->rchild==NULL)count++;　returnOK;CountLeaf(T->lchild);CountLeaf(T->rchild);　　　　　　　　　　　　　　　　　　　　　}}