计算机考研数据结构试卷十四(练习题含答案)

共25套适用于计算机考研数据结构系统练习（PS：其他正在整理，敬请期待）数据结构试卷14一、填空题1、二维数组A[10][20]采用列序为主方式存储，每个元素占一个存储单元并且A[0][0]的存储地址是200，则A[6][12]的地址是____。2、二维数组A[10..20][5..10]采用行序为主方式存储，每个元素占4个存储单元，并且A[10][5]的存储地址是1000，则A[18][9]的地址是____。3、求下列广义表操作的结果：(1)GetTail[GetHead[((a,b),(c,d))]];(2)GetTail[GetHead[GetTail[((a,b),(c,d))]]]4、已知一个有向图的邻接矩阵表示，计算第i个结点的入度的方法是____。5、已知一个图的邻接矩阵表示，删除所有从第i个结点出发的边的方法是____。6、在利用快速排序方法对一组记录（54，38，96，23，15，72，60，45，83）进行快速排序时，递归调用而使用的栈所能达到的最大深度为____，共需递归调用的次数为____，其中第二次递归调用是对____一组记录进行快速排序。7、在堆排序，快速排序和归并排序中，若只从存储空间考虑，则应首先选取____方法，其次选取____方法，最后选取____方法；若只从排序结果的稳定性考虑，则应选取____方法；若只从平均情况下排序最快考虑，则应选取____方法；若只从最坏情况下排序最快并且要节省内存考虑，则应选取____方法。二、选择题1、二分查找和二叉排序树的时间性能【】。A.相同B.不相同2、采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为【】。A．O（n2）B.O(nlog2n)C.O(n)D.O(log2n)3、在待排序的元素序列基本有序的前提下，效率最高的排序方法是【】。A.插入排序B.选择排序C.快速排序D.归并排序4、下述几种排序方法中，要求内存量最大的是【】。A.插入排序B.选择排序C.快速排序D.归并排序5、设有两个串p和q，求q在p中首次出现的位置的运算称作【】。A.连接B.模式匹配C.求子串D.求串长6、二维数组A中，每个元素A[i][j]的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A[4][7]的起始地址为【】。A.SA+141B.SA+180C.SA+222D.SA+2257、某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是【】。A.bdgcefhaB.gdbecfhaC.bdgaechfD.gdbehfca8、在一非空二叉树的中序遍历序列中，根结点的右边【】。A.只有右子树上的所有结点B.只有右子树上的部分结点C.只有左子树上的部分结点D.只有左子树上的所有结点9、具有6个顶点的无向图至少应有【】条边才能确保是一个连通图。A.5B.6C.7D.810、二分查找和二叉排序树的时间性能【】。A.相同B.不相同C.可能相同D.不确定三、计算与算法应用题：1.已知一个有向图的顶点集V和边集G分别为：V={a,b,c,d,e,f,g,h}E={a,b,a,c,b,f,c,d,c,e,d,a,d,f,d,g,e,g,f,h};假定该图采用邻接矩阵表示，则分别写出从顶点a出发进行深度优先搜索遍历和广度优先搜索遍历得到的顶点序列。2.设散列表的长度为13，散列函数为H（h）=k%13，给定的关键码序列为19，14，23，01，68，20，84，27。试画出用线性探查法解决冲突时所构成的散列表。0123456789101112四、阅读下列算法，分析它的作用：1.voidAD(Lnode*&HL){Insert(HL,30);Insert(HL,50);Delete(HL,26);Delete(HL,55);}假定调用该算法时以HL为表头指针的单链表中的内容为（15，26，48，55），则调用返回后该单链表中的内容为：______________________________。2.voidAI(adjmatrrixGA,inti,intn){couti’’;visted[i]=true;for(intj=0;jn;j++)if(Ga[I][j]!=0&&GA[i][j]!=MaxValue&&!visited[j])AI(GA,j,n);}该算法的功能为：_____________________________________________________________________。五、算法设计1.已知深度为h的二叉树以一维数组BT(1:2h-1)作为其存储结构。请写一算法，求该二叉树中叶结点的个数。2.编写在以BST为树根指针的二叉搜索树上进行查找值为item的结点的非递归算法，若查找item带回整个结点的值并返回true，否则返回false。boolFind（BtreeNode*BST，ElemType&item）答案一、填空1.200+（6*20+12）=3262.1000+((18-10)*6+(9-5))*4=12083.(1).(b)(2).(d)4.求矩阵第i列非零元素之和5.将矩阵第i行全部置为零6.2.2;4;（23，38，15）7.堆排序、快速排序、归并排序、归并排序、快速排序、堆排序二、选择1-5BBADB6-10ABCBB三、计算与算法应用题：1、平均长度为4.8.深度优先搜索序列：a，b，f，h，c，d，g，e广度优先搜索序列：a，b，c，f，d，e，h，g7.四、阅读下列算法，分析其作用1.（15，30，48，50）2.从初始点vi出发深度优先搜索遍历由邻接距阵GA所表示的图五、算法设计1、二叉树采取顺序结构存储，是按完全二叉树格式存储的。对非完全二叉树要补上“虚结点”。由于不是完全二叉树，在顺序结构存储中对叶子结点的判定是根据其左右子女为0。叶子和双亲结点下标间的关系满足完全二叉树的性质。intLeaves(inth)//求深度为h以顺序结构存储的二叉树的叶子结点数{intBT[];intlen=2h-1,count=0;//BT是二叉树结点值一维数组，容量为2hfor(i=1;i=len;i++)//数组元素从下标1开始存放if(BT[i]!=0)//假定二叉树结点值是整数，“虚结点”用0填充if(i*2)len)count++;//第i个结点没子女，肯定是叶子elseif(BT[2*i]==0&&2*i+1=len&&BT[2*i+1]==0)count++;//无左右子女的结点是叶子return(count)}//结束Leaves8.boolFind（BtreeNode*BST，ElernType＆item）{while（BST！=NULL）{if（item==BST一data）{item=BST一data；returntrue;}elseif（item＜BST一data＝BST＝BST一left;elseBST=BST一right；}returnfalse;}