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

共25套适用于计算机考研数据结构系统练习（PS：其他正在整理，敬请期待）数据结构试卷12一、填空题1.已知数组A［１０］［１０］为对称矩阵，其中每个元素占5个单元。现将其下三角部分按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A［５，６］对应的地址是_______。2.在有n个结点的无向图中，其边数最多为_______。3.取出广义表A=(x,(a,b,c,d))中原子x的函数是_______。4.对矩阵采用压缩存储是为了_______。5.带头结点的双循环链表L为空表的条件是_______。6.设线性表中元素的类型是实型，其首地址为1024，则线性表中第6个元素的存储位置是。7.对于顺序存储的栈，因为栈的空间是有限的，在进行运算时，可能发生栈的上溢，在进行运算时，可能发生栈的下溢。8.在双向链表中，每个结点有两个指针域，一个指向______，另一个指向_____。9.由一棵二叉树的前序序列和可唯一确定这棵二叉树。10.折半查找的存储结构仅限于____，且是____。二、选择题1.对n个记录的文件进行快速排序，所需要的辅助存储空间为【】。AO（1）BO（log2n）CO（n）DO（n2）2.哈夫曼树中一定不存在【】。A度为0的结点B度为1的结点C度为2的结点D带权的结点3.下述哪一条是顺序存储方式的优点？【】A存储密度大B插入和删除运算方便C获取符合某种条件的元素方便D查找运算速度快4.有一个二维数组A[m][n]，假设A[0][0]存放位置在600(10)，A[3][3]存放位置在678(10)，每个元素占一个空间，问A[2][3](10)存放在什么位置？（脚注(10)表示用10进制表示，m3）【】。A658B648C633D6535.列关于二叉树遍历的叙述中，正确的是【】。A若一个叶子是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历最后一个结点B若一个结点是某二叉树的前序遍历最后一个结点，则它必是该二叉树的中序遍历的最后一个结点C若一个结点是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序最后一个结点D若一个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的中序遍历最后一个结点6.层二叉树的结点总数最多为【】。A2k-1B2k+1C2K-1D2k-17.线性表进行二分法查找，其前提条件是【】。A线性表以链接方式存储，并且按关键码值排好序B线性表以顺序方式存储，并且按关键码值的检索频率排好序C线性表以顺序方式存储，并且按关键码值排好序D线性表以链接方式存储，并且按关键码值的检索频率排好序8.n个记录进行堆排序，所需要的辅助存储空间为【】。AO(1og2n)BO(n)CO(1)DO(n2)9.线性表（7，34，77，25，64，49，20，14）进行散列存储时，若选用H（K）=K%7作为散列函数，则散列地址为0的元素有【】个。A1B2C3D410.列关于数据结构的叙述中，正确的是【】。A数组是不同类型值的集合B递归算法的程序结构比迭代算法的程序结构更为精炼C树是一种线性结构D用一维数组存储一棵完全二叉树是有效的存储方法三、计算与算法应用题：1.画出下列树对应的二叉树，并写出其先根遍历序列：2.将关键字序列为{54，29，37，86，71，91，8，31，44，26}进行归并排序，写出各趟详细过程。四、阅读下列算法，分析其作用1.假定从键盘上输入一批整数，依次为：786345309134–1，请写出输出结果。#includeiostream.h#includestdlib.hconstintstackmaxsize=30;typedefintelemtype;structstack{elemtypestack[stackmaxsize];inttop;BDFCAEG};#include“stack.h”voidmain【】{stacka;initstack(a);intx;cinx;while(x!=-1){push(a,x);cinx;}while(!stackempty(a))coutpop(a)””;coutend1;}该算法的输出结果为：_________________________________.2.读下述算法，说明本算法完成什么功能。templatecalsstypevoidBinTreeType：：unknown(BinTreeNodeType*t){BinTreeNodeType*p=t,*temp;if(p!=NULL){temp=p→leftchild;p→leftchild=p→rightchild;p→rightchild=temp;unknown(p→leftchild);undnown(p→rightchild);}}该算法的功能是：___________________________五、算法设计1.试用递归法编写输出从n个数中挑选k个进行排列所得序列的算法。2.编写一个算法，交换单链表中p所指向的结点和其后续结点的两个结点，Head指向该链表的表头，P指向链表中的某一结点。aHeadbbc^ed答案一、填空1、12252、n(n-1)/23、head(A)4、节省空间5、L-next=L-prior或L-next=L6、10447、入栈（插入），出栈（删除）8、前驱结点，后继结点9、中序序列10、顺序存储结构，有序的二、选择1-5BBADA6-10ACCDD三、计算与算法应用题画出下列树对应的二叉树，并写出其先根遍历序列：先根遍历序列：ABDEGFC4.将关键字序列为{54，29，37，86，71，91，8，31，44，26}进行归并排序，写出各趟详细过程。542937867191831442629543786719183126442937548683171912644BEGDFCA82931375471869126448262931374454718691四、阅读下列算法，分析它的作用1.该算法的输入结果是：3491304563782.该算法的功能是：交换二叉树的左右子树的递归算法。五、算法设计题：1.对于排列的解空间可构造一个虚拟的解空间树，比如n=5，k=3时的解空间树如下图所示，可采用对此树进行先序遍历方式进行遍历，并用递归法进行递归输出从n个数中挑选k个进行排列所得序列。具体算法实现如下：//文件路径名:exam7\alg.htemplateclassElemTypevoidArrage(ElemTypea[],intk,intn,intoutlen=0)//操作结果:回溯法输出排列序列，a[0..k-1]为k个数的排列序列outlen为当前所求排列//序列的长度，其中outlen=k时的排列序列为所求；n为list数组长度{if(k0||k=n)return;//此时无排列inti;//临时变量if(outlen==k+1){//得到一个排列for(i=0;ik;i++){//输出一个排列couta[i];//输出a[i]}cout;//用空格分隔不同排列}else{//对解空间进行前序遍历，a[outlen..n]有多个排列，递归的生成排列for(i=outlen;in;i++){//处理a[i]Swap(a[outlen+1],a[i]);//交换a[outlen+1]与a[i]Arrage(a,k,n,outlen+1);//对序列长度outlen+1递归Swap(a[outlen+1],a[i]);//交换a[outlen+1]与a[i]}}}2.编写一个算法，交换单链表中p所指向的结点和其后续结点的两个结点，Head指向该链表的表头，P指向链表中的某一结点。aHeadbbd^ecvoidLink::swap(NodeType*p)//0.5分{NodeType*q,*r,*s;q=p-next;//0.5分if(q!=NULL)//1分{if(p==Head)//4分{Head=Head-next;s=Head-next;Head-next=p;p-next=s;}Else//4分{r=Head;while(r-next!=p)r=r-next;r-next=q;p-next=q-next;q-next=p;}}}