数据结构与算法作业.pptxVIP

作业 1计算下列各片断程序中@语句的执行次数及其大O形式：（1） for i=1 to n for j=1 to i for k=1 to j @ x=x+1 end end end (2) for i=1 to n j=1 for k=j+1 to n @x=x+1 end end（3） i=1; while (i100)@ x=x+1 i=i+1 end (4) i=1 while (i=n)@ x=x+1 i=2*i end（5） x=91 ; y=100 ; while (y0) { @ if (x100) {x - = 10 ; y--} else x++ ; } 2. 设数据元素的集合为D=｛d1, d2, d3, d4, d5｝,试指出下列关系R所对应的数据结构B=（D，R）中哪些是线性结构，哪些是非线性结构。(1) R={(d1,d2), (d2,d4),(d4,d2),(d2,d5),(d4,d1)}(2) R={(di, di+1)|i=4,3,2,1}(3) R={(di, dj)|j=(5i2+4i+1}3. 为一个课题组定义一个数据结构。每组一位教师，1～3名研究生，1～6名本科生，关系是教师指导研究生，每名研究生指导1～2名本科生，画出该数据结构的逻辑结构图。4.按增长率由小至大的顺序排列下列各函数： 2100, (3/2)n, (4/3)n, nn, n3/2, n2/3, n1/2, n!, n, log2n, n/log2n, log22n, log2(log2n), nlog2n, nlog2n作业 2已知线性表L(x1, x2,…,xn)各元素按递增有序排列，用向量方式做存储结构。试编写算法，删除表中值分布在c与d(cd)之间的元素编写一算法，将向量L(x1, x2,…,xn)倒置试编写算法，求已知单链表的长度，并考虑表空情况已知一循环链表中各数值已按递增有序排列，现要求插入一结点后，链表仍有序缩写单链表倒置算法在双向链表的值为a、b的两个结点之间插入值为x的结点7. 简述以下算法的功能: Sample(head) //head是无表头结点的单链表 { if(head next(head)){ q-head; head-next(head); p-head; while(next(p)) p-next(p); next(p)-q; next(q)-nil; } return; }作业 3Q［0：10］为循环队列，初态front=rear=1，画出下列操作后，队的头、尾指示器状态：d,e,b,g,h入队；d, e出队；i,j,k,l,m入队；b出队；n,o,p,q,r入队2. 试画出表达式：A*(B-C)+D**(E/F)执行过程中NS，OS栈的变化情况，并给出相应的后缀表达式结果3. 设置一个单元，作为队满或队空的标志，写出循环队列插入和删除的算法d,e,b,g,h入队；4.一个栈的输入序列为ABCDEF，经一次退压栈能否得到如下序列，若不能，则经过两次退压栈能否得到？I: CBEFDA II: AEDFBC作业 41. 设一个二维数组A［1：m; 1：n]，假设A[3，2]地址为1110，A[2，3]地址为1115，若每个单元占一个空间，求A[1,4]的地址。2. 采用三元组和带行辅助向量形式，表示下列稀疏矩阵：3. 二维数组Aij, 0=i=5, 2=j=9,问按行存储A24和按列存储哪一个矩阵元素在相同位置？作业 5设一棵完全二叉树，共有1001个结点，试问：(1)有多少个叶子结点；(2)有多少度为2的结点；(3)有多少结点只有非空左子树。2. 设一棵二叉树，其中序和后序遍历为：中序：BDCEAFHG；后序：DECBHGFA画出该二叉树的逻辑结构，并写出先序遍历结果。3. 给出一组元素｛17，28，36，54，30，27，94，15，21，83，40，17｝，要求画出由此生成的二叉排序树4. 给出一组权值W=｛8，2，5，3，2，17，4｝，画出由此生成的huffman树5. 将下列一般树转为二叉树ABCDFGIJEKL6. 三个结点A、B、C 可以构造多少种不同的树？7. 深度为4的只有4个结点的单支二叉树共有几 种？画出只有左子树的深度为4的单支二叉树的顺序存储结构。8. 已知二叉树的先序序列为abdgcefh，中序序 列为：dgbaechf，画出二叉树并求后序序列。9. 满足下列条件的二叉树是什么样的二叉树？ 1) 先序序列和中序序列相同； 2) 中序序列和后序序列相同。10. 已知信源符号a、b、c、d、e的出现频率分别为10、5、20、10、18，求1)huffman编码；2)画出huffman码树；3)求