《数据结构01》复习题_答案

一选择题（每小题2分，共20分）1．数据结构中，与所使用的计算机无关的是数据的___c___结构；A）存储B）物理C）逻辑D）物理和存储2．算法分析的目的是：cA）找出数据结构的合理性B）研究算法中的输入和输出的关系C）分析算法的效率以求改进D）分析算法的易懂性和文档性3．计算机算法必须具备输入．输出和_b______等５个特性．Ａ）可行性、可移植性和可扩充性B)可行性、确定性和有穷性Ｃ）确定性、有穷性和稳定性Ｄ）易懂性、稳定性和安全性４．一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是___b____A）110B）108C）100D）1205设有两个串p和q,求q在p中首次出现的位置的运算称作:A)连接B)模式匹配C)求子串D)求串长6.向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变,平均要移动____b___个元素A)8B)63.5C)63D)77设矩阵A是一个对称矩阵,为了节省存储,将其下三角部分按行序存放在一维数组B[1,n(n-1)/2]中,对下三角部分中任一元素ai,j(i≤j),在一维数组B中下标K的值是:（矩阵是A[1][1]开始）BA)i(i-1)/2+j-1B)i(i_1)/2+jC)i(i+1)/2+j-1D)i(i+1)/2+j8.二叉树是非线性数据结构,所以__c_____A)它不能用顺序存储结构存储B）它不能用链式存储结构存储C）顺序存储结构和链式存储结构都能存储D）顺序存储结构和链式存储结构都不能使用9.有8个结点的无向连通图最少有__c_____条边（边数＝节点－1）A)5B)6C)7D)810.所有排序方法中,关键字比较的次数与记录的初始排列次数无关的是___d____A)希尔B)冒泡C)插入D)选择二.填空题(每小题2分,共20分)1.数据的存储结构可用四种基本的存储方法表示,它们分别是顺序_______、链式_______、索引_______和散列_______。2.在一个循环队列中,队首指针指向队首元素的前一个_______位置。3.向一个长度为n的向量的第i个元素(1≤i≤n=1)之前插入一个元素时,需向后移动____n-i+1__个元素,删除第i个元素(1≤i≤n)时,需向前移动_n-i_____个元素。4.向量、栈和队列都是__线性_____结构,可以在向量的任何_______位置插入和删除元素;对于栈只能在_栈顶______插入和删除元素;对于队列只能在__队尾____插入和_____队头__删除元素。5.在动态存储管理中的三种分配策略是首次拟合_______、_最佳拟合______和___最差拟合____。6.广义表(((a)))的表头是__（（A））_____,表尾是_____（）__。7.已知主串s=’ADBADABBAABADABBADADA’,模式串pat=’ADABBAD’。写出模式串的nextval函数值_______。P（77）8.一棵具有257个结点的完全二叉树，它的深度为不大于k=log2(n)最大整数8_____。9．n个顶点e条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为___O（n^2）____；若采用邻接表存储时，该算法的时间复杂度为O(n+e)_______。10．已知序列{32，17，18，60，40，7，73，65，85}，给出快速排序第一趟的结果（升序），并给出该序列的初始小根堆_______。(堆排序先右后左。先建树，快速排序：记位置，交换)三．判断题（每小题2分，共10分）1、线性表的每个结点只能是一个简单类型（栈和队列），而链表的每个结点可以是一个复杂类型。f2、顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。（说反了）f3、链表的每个结点中都恰好包含一个指针。（双向链表）f4、用二叉链表法（llink-rlink）存储包含n个结点的二叉树，结点的２ｎ个指针区域中有n＋1个为空指针。t５、二分查找同顺序查找一样，对数据表没有什么要求。F（有序）四．应用题（每小题５分，共３０分）１、已知一单向链表Ｌ，写出在指定的Ｐ结点前成功插入一个新结点的有关语句（包括产生一个新结点的有关语句，并画出链表结构图）。Link*q,q=(link*)malloc(sizeof(link));q-data=p-data;q-next=p-next;p-next=q;２、已知二叉树的先序、中序遍历序列分别为ＡＢＤＦＪＧＫＣＥＨＩＬＭ和ＢＦＪＤＧＫＡＣＨＥＬＩＭ，试写出后序遍历时得到的结点序列。３、设给定权集Ｗ＝｛２，３，４，７，８，９｝，试构造关于Ｗ的一棵哈夫曼树和哈夫曼编码，并求其加权路径长度ＷＰＬ。４、给出入如图Ｇ所示的无向图的邻接表，从１点出发的ＤＳＦ序列和使用Ｐrim算法构造的最小生成树。１２４３５６5、设关键字集合为：{10，20，30，50，40}，依次输入各结点，画出平衡二叉树的构造过程。6、已知一组关键字为{25，36，41，38，44，15，68，12，6，51，26}的数据，用线性探查法解决冲突，构造这关键字的散列表，并计算成功查找的平均找长度ASL。五．编程题（每小题10分，共20分）1、编写一个采用双冒泡进行升序排序的算法（即：上下交替进行）。2、编写一个计算二叉树中叶子结点的数目递归算法。试卷（参考答案）一、选择题（20分：每小题2分）1、C2、C3、B4、B5、B6、B7、B8、C9、C10、D二、填空题（20分：每小题2分）1、顺序、链式、索引和散列2、前一个3、n-i+1、n-i4、线性、任意、栈顶、队尾、队头5、首次拟合、最佳拟合、最差拟合6、（（a））、（）7、01021018、99、O（n2）、O（n+e）10、快速排序：71718324060736585堆排序：71718604032736585三、判断题（10分：每小题2分）1、×2、×3、×4、√5、×四、应用题（30分，每小题5分）1、s=(linklist)malloc(sizeof(linknode));s-data=x;s-next=NULL;s-next=p-next;p-next=s;p-data-s-data;2、LRD序列：JFKGDBHLMIECA2、WPL=2*4+3*4+4*3+7*2+8*2+9*2（哈夫曼树见右图）哈夫曼编码：2：00003：00014：0017：108：119：014、1263145＾2163553＾31125455664＾4153562＾5233666＾6344256＾DFS序列：123465331815952349781253645、（过程略）6、表长：m=11/0.75≈15成功查找的平均查找长度：ASL=（4+2+1+2+2+1+1+1+1+2+3）/11=20/11=1.82五、编程题（20分：每小题10分）【程序1】voidBubble_Sort(inta[],intn)//相邻两趟是反方向起的冒泡排序算法{low=0;hight=n-1;//冒泡的上下界change=1;while(lowhight&&change){change=0;for(i=low;ihight;i++)//从上向下起泡if(a[i]a[i+1]){a[i]-a[i+1];change=1;}high--;//修改上界for(i=high;ilow;i--)//从下向上起泡if(a[i]a[i-1]){a[i]-a[i-1];change=1;}2010403050散列地址：01234567891011121314关键字：512641156844636253812MOD13：1202235610121212比较次数：42122111123low++;//修改下界}}【程序2】intleafs(bitree*t){intnum1,num2;if(t==NULL)return(0);elseif(t-lchild==NULL&&rchild==NULL)return(1);else{num1=leafs(t-lchild);num2=leafs(t-rchild);return(num1+num2);}}