10数据结构试卷B

《10数据结构试卷B》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、东南大学考试卷(B卷)数据结构考试学期09「0・3得分适用专业吴健雄学院电类考试形式半开卷考试时间长度120分钟1.遵守考场纪A・O(log2n)B・O(n)C.O(nlog2n)2)D・0(n、选择题(每题1分，共5分)1.下面算法的时间复杂度是(intsum(intn){intp,s=0,i;for(i=1;i<=n;i++){P=1；for(j=1;j<=i;j++)p*=j；s+二p;}returns;}2.(执行A.f・>link=s;f=s;B.r->link=s;r=s;C.s->link=r;r=s;D・s->link=f;仁s;3.为判

2、断一个循环队列(最多元素为()m,队头指针为front,队尾指针为rear)为空的条件在一个链队中，设f和r分别为队首和队尾指针，则s所指向的新结点入队时,)front二=rear;.front!=rear;・Cfront==(rear+1)%m;・Dfront!=(rear+1)%m;・4.是对于含有()n个顶点和e条边的无向图若采用邻接表表示，则所有邻接表中的结点总数A.e/2B.C.2eD.n+e对于含有复杂度为(5.n个顶点和)2A.0(n)C.O(nlog2fi)e条边的无向连通图，利用Kruskal算法产生最小生成树，其时间B・O(rTe)D

3、・O(elog2e)二、判断题（每题1分，共5分）1.对于一组待输入的关键码集合，虽然各关键码的输入次序不同，但得到的二叉搜索树的形状都是一样的。（）2.最优的二叉搜索树一定是平衡的二叉搜索树。（）3.连通分量是无向图中的极小连通子图。（）4.对任何用顶点表示活动的网络（AOV）进行拓扑排序的结果都是唯一的。（）5.数据的逻辑结构与数据元素本身的内容和形式无关。（）三、填空题（每空1分，共10分）1.含有40个结点的理想平衡二叉树的高度为H）o2.若对一棵二叉树从0开始进行结点编号，并按此编号把它顺序存储到一维数组a中，编号为0的结点存储到a[0]中，其

4、余类推，则a[i]元素的左子女结点为（2）,右子女结点为L_3）,双亲结点为X4）o3.对于折半搜索所对应的判断树，它既是一棵（,又是一棵（6）o4.在一个具有n个顶点的无向和有向完全图中，分别有C_ZJ和（8）条边。5.建立一棵树应该采用（遍历，删除一棵树应该采用（遍历。四、简答简述题（第1题8分，第2、3题各10分，共24分）1.画出下列广义表的图形表示和它们的链式存储表示：D（A（c）,B⑹,C（a,L（b,c,d）））3.采用最低位优先（LSD）基数排序的序列为：123,018,456,382,258,992,655,789,857,394,91

5、1o用图示法给出各趟分配和收集的过程和结果。五、综合算法题（每空2.5,共55分）算法程序o1.完成三元组存储的稀疏矩阵的快速转置templatestructTriple{〃三元组introw,col;〃非零元素行号/列号Evalue;〃非零元素的值}；templateSparseMatrixSparseMatrix::FastTranspos(){//快速转置int*rowSize=newint[Cols];〃行元素数量数组int*rowStart=newint[Cols];〃行起始位置数组Spa

6、rseMatrixB(maxTerms,Cols,Rows);//建立一个稀疏矩阵，放置转置矩阵共8页第4页B.Terms=Terms;〃稀疏矩阵项数if(Terms>0){inti,j;for(i=0;i

7、rray[j].col=(5);B.smArray[j].value=smArray[i].value;(6);〃放置一个元素后，〃对应行起始位置项++,指出该行下一个元素位置}}B.Terms=Terms;delete[]rowSize;delete[]rowStart;returnB;}1.完成利用栈的二叉树后序遍历非递归算法操作。后序遍历情况复杂，在遍历完左子树时还不能访问根结点，待右子树遍历完才可以访问根结点。所以在栈中需记录刚才是在左子树还是右子树。templatestructstkNode{//遍历吋所用栈结点类定义Bi

8、nTreeNode*ptr;〃树结点指针enum{L,R}tag;〃退栈标