2022年2022年海文计算机考研冲刺班课件-数据结构模拟试题及答案 .pdf

1统考计算机专业考研数据结构模拟试卷名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 12 页 - - - - - - - - - 2目录计算机专业数据结构科目模拟试题（一）.3计算机专业数据结构科目模拟试题（二）.5计算机专业数据结构科目模拟试题（三）.7计算机专业数据结构科目模拟试题（一）参考答案.9计算机专业数据结构科目模拟试题（二）参考答案.10计算机专业数据结构科目模拟试题（三）参考答案.11名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 12 页 - - - - - - - - - 3计算机专业数据结构科目模拟试题（一）一. 单项选择题： 140题，每小题2 分共 80 分。在每小题给出的四个选项中，请选出一项最符合题目要求的。1. 在一个单链表中，已知指针p 指向其中的某个结点，若在该结点前插入一个由指针s 指向的结点 ，则需执行（） 。As-next=p-next;p-next=s;Bp-next=s; s-next=p;Cr=p-next;p-next=s;s-next=r;D仅靠已知条件无法实现2. 设顺序表长度为n，从表中删除元素的概率相等。则在平均情况下，从表中删除一个元素需要移动的元素个数是（） 。A(n- 1)/2Bn/2Cn(n-1)/2Dn(n+1)/23. 在一个具有n个单元的顺序栈中，假定以高端（即第n- 1 单元）作为栈底，以top 为栈顶指针， 则当作出栈运算时， top变化为（） 。Atop 不变Btop=0Ctop-Dtop+4. 若一个栈以向量Vn 存储，设栈空时，栈顶指针top 为n- 1，则下面 x 进栈的正确操作是（） 。Atop=top+1；Vtop=xB Vtop=x； top=top+1Ctop=top-1；Vtop=xD Vtop=x； top=top-15. 经过以下栈运算后，x的值是（） 。InitStack(s);Push(s,a);Push(s,b);Pop(s,x);Push(s,c);Pop(s,x);GetTop(s,x);A. aBbCcDd6. 若一棵二叉树有126 个节点，在第7 层（根结点在第1 层）的结点个数至多有（） 。A32B64C63D不存在第7 层7. 具有n个顶点的有向图的边最多有（） 。AnBn(n- 1)Cn(n+1)Dn28. 设连通图G的顶点数为n，则G的生成树的边数为（） 。AnBn-1C2nD2n- 19. 散列查找中k个关键字具有同一哈希值，若用线性探测法将这k个关键字对应的记录存入哈希表中，至少要进行（）次探测。AkBk+1Ck(k+1)/2D1+k(k+1)/210. 一组记录的关键字为 (45，80，55，40，42，85)，则利用堆排序的方法建立的初始堆为（） 。A(80，45，55，40，42，85)B(85，80，55，40，42，45)C(85，80，55，45，42，40)D(85，55，80，42，45，40)11.假设某文件经内部排序得到100 个初始归并段，若要使多路归并三趟完成排序，则应取归并的路数至少为多少？（） 。A2B3C4D5二、综合应用题： 41-47小题，共 70 分1. 已知顺序表中有m个记录， 表中记录不依关键字有序。编写算法为该顺序表建立一个有序的索引表，索引表中每一项应含有记录关键字和记录在顺序表中的序号，要求算法的时间复杂度在最好的情况下能达到 O(m)。2. 在二叉链表的每个结点中添加一个域int depth，表示以该结点为根的子树的深度，即：typedefstructBiTNode /结点结构TElemTypedata;structBiTNode*lchild,*rchild;/左右孩子指针名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 12 页 - - - - - - - - - 4intdepth;/以该结点为根的子树的深度 BiTNode,* BiTree;（1）试编写一递归函数BiTreeDepth( BiTreeT ) ，计算二叉树T 中每个结点的depth 值，函数的返回值为树T 的深度。（2）在（1）的基础上 （即已求出二叉树中每个结点的depth 值） ， 编写一递归函数BiTreeBalance( BiTreeT ) ，判断二叉排序树T 是否为平衡二叉树，如果是平衡二叉树，则函数的返回值为真。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 12 页 - - - - - - - - - 5计算机专业数据结构科目模拟试题（二）一. 单项选择题： 140题，每小题2 分共 80 分。在每小题给出的四个选项中，请选出一项最符合题目要求的。1.判断带头结点的线性链表L 是否为空的条件是（） 。AL.elem=NULLBL.length = 0CL-next=NULLDL = NULL2. 设有多项式A 和 B 的项数分别为m和n，均采用单链表表示，进行A 加 B 运算的时间复杂度为（） 。AO(m)（当mn时）BO(n)（当nm时）CO(m+n)DO(m*n)3.若用一个大小为6 的数组来实现循环队列，且当前rear 和 front 的值分别为0 和 3。当从队列中删除一个元素，再加入两个元素后，rear 和 front 的值分别为（） 。A1 和 5B2 和 4C4 和 2D5 和 14.在具有n个单元的顺序存储的循环队列中，假定front 和 rear 分别为队头指针和队尾指针，则队空的条件为（） 。Arear=frontB(rear+1)%n=frontC(rear-1)%n=frontD(front+1)%n=rear5.将一个 A1.100 ，1.100的三对角矩阵以行序为主存入一维数组B1.298中，元素a66，65 B 数组中的位置k等于（） 。A198B197C 196D1956.由 3 个结点可以构造出（）种不同形态的二叉树。A3B4C 5D67.无向图G是一个连通图，有9 条边，则该图的顶点个量至少为（） 。A4B5C6D78.采用顺序检索的方法检索长度为n的线性表，则检索每个元素的平均比较次数为（） 。AnBn2C(n+ 1)/2Dlog2(n+ 1)9.表长为 25 的散列表，如果采用除留余数法，即按公式H(key) =keymodp建立哈希函数，则最适宜的p取值应为（） 。A23B24C 25D2610.一组记录的关键字为20 ，15，14，18，21，36，40，10 ，则利用快速排序的方法，以第一个记录为基准得到一次划分结果是（） 。A10， 15，14，18，20，40，36，21B10，15， 14，18，20，36，40，21C10，15，14，20，18，40，36，21D15，10，14，18，20，36，40，2111. 以下关于排序方法的描述，不正确的是（） 。A排序是将一组记录的任意序列，调整为按关键字“有序”的序列B排序方法都是不稳定的C排序方法可以分为内部排序和外部排序D排序中需要比较关键字的大小二、综合应用题： 41-47小题，共 70 分1.设哈希表为HT13 ，哈希函数为H(key) =key%13。对下列关键字序列（12, 23, 45, 57, 20, 03,78, 31, 15, 36）构造哈希表。（1）采用线性探测再哈希寻找下一个空位，画出相应的哈希表，并计算等概率下查找成功的平均查找长度和查找不成功的平均查找长度。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 12 页 - - - - - - - - - 6（2）采用双哈希法寻找下一个空位，再哈希函数为RH(key) = (7*key) % 10 + 1，寻找下一个空位的公式为Hi= (Hi- 1 +RH(key) % 13,H1 =H(key)。画出相应的哈希表，并计算等概率下查找成功的平均查找长度。2.铁路进行列车调度时，常把站台设计成栈式结构，如图1 所示。试问：（1）设有编号为1， 2，3，4，5，6 的 6 辆列车，顺序开入栈式结构的站台，则可能的出栈序列有多少种？（2）若进站的6 辆列车顺序如上所述，那么是否能够得到435612、325641、154623 和 135426 的出站序列，如果不能，说明为什么不能；如果能，说明如何得到（即写出“进栈”或“出栈”的序列）。图 1栈式结构站台示意图名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 12 页 - - - - - - - - - 7计算机专业数据结构科目模拟试题（三）一. 单项选择题： 140题，每小题2 分共 80 分。在每小题给出的四个选项中，请选出一项最符合题目要求的。1.对于线性链表，在p 所指向的结点后插入由q 指向的新结点的语句序列是（） 。Ap-next = q; q-next = p-next;Bq = p-next; p-next = q;Cq-next = p-next; p-next = q;Dp = p-next; q-next = p;2.向一个栈顶指针为h 的带头结点链栈中插入指针s 所指的结点时，应执行的语句序列是（） 。Ahnext = s；Bs-next = h；Csnext = h； h = hnext；Dsnext = hnext；hnext = s；3.设有一个栈，元素的进栈次序为A，B，C，D，E，下列中不可能的出栈序列是（） 。AA，B，C，D，EBB，C，D，E，ACE，A，B，C，DD E，D，C，B，A4.在一个无头结点的链队列中，假定 front 和 rear 分别为队头和队尾指针，则删除一个结点的主要操作为（） 。Afront = frontnextBrear = rearnextCrear = front nextDfront = rear next5.若用一维数组保存一个深度为5、结点个数10 的二叉树，数组的长度至少为（） 。A10B16C31D646.假定在一棵二叉树中，双分支结点数为15 个，单分支结点数为30 个，则叶子结点数为（）个。A15B16C 17D477.在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（） 。AG中有弧 BG中有一条从Vi到Vj的路径CG中没有弧 DG中有一条从Vj到Vi的路径8.在对长度为n的顺序存储的有序表进行折半查找，对应的折半查找判定树的高度为（） 。AnBn2C log2(n+ 1) - 1D(n+ 1)/29.若对n个元素进行堆排序，则在初始建堆的过程中需要进行（）次筛选。A1B?n/2?C(n-1)/2Dn10.有一组数据（ 15， 9，7，8，20，-1 ，7，4） ，用堆排序的筛选方法建立的初始堆为（） 。A-1 ， 4，8，9，20，7，15，7B-1 ，7，15，7，4，8，20，9C-1 ， 4，7，8，20，15，7，9DA、B、C 均不是11. 假设一次 I/O 的物理块大小为150，每次可对750 个记录进行内部排序，那么，对含有150000 个记录的磁盘文件进行4-路平衡归并排序时，需进行（）次 I/O 筛选。A5000B10000C15000D20000二、综合应用题： 41-47小题，共 70 分1.试对图 2 所示的 AOE 网络：（1）这个工程最早可能在什么时间结束；（2）求每个活动的最早开始时间e( )和最迟开始时间l( )；（3）确定哪些活动是关键活动。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 12 页 - - - - - - - - - 8图 22. Ha和 Hb 为两个带头结点链表的头指针，分别表示两个集合A 和 B，两个链表的元素值递增有序排列。现要求另辟空间构成一个新的带头结点链表，其头指针为Hc，链表的元素为A和 B 的交集， 且也是递增有序。试编写建立新链表的算法。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 12 页 - - - - - - - - - 9计算机专业数据结构科目模拟试题（一）参考答案答案仅供参考一、单项选择题： 140题，每小题2 分共 80 分。在每小题给出的四个选项中，请选出一项最符合题目要求的。1.D2.A3.C4.D5.A6.C7.B8.B9.C10.B11.D二、综合应用题： 41-47小题，共 70 分1.解答（参考算法） ：索引表的类型定义如下：typedefstructKeyTypekey;/关键字intid;/对应记录在顺序表中的序号IndexType,IdxTableMAXSIZE+1;顺序表类型定义如下：typedefstructKeyTypekey; RedType ;typedefstructRedTyperMAXSIZE+1;/r0 闲置或用作哨兵单元intlength;/顺序表长度 SqList;算法：voidcreateIdx(SqListL,IdxTableIdx)/顺序表 L 中有 m个记录，本算法为该顺序表建立一个有序的索引表，索引表中每一项包含记录/ 的关键字和记录在顺序表中的序号两个数据项Idx1.key=L.r1.key;Idx1.id=1;for( i=2;i0)&(Idxj.keyL.ri.key)Idxj+1.key=Idxj.key;Idxj+1.id=Idxj.id;j-;Idxj+1.key=L.ri.key;Idxj+1.id=i;试题分析： 本题考查考生是否掌握直接插入排序算法的应用。算法的核心思想是借助于直接插入排序，将顺序表中各记录的关键字以及记录在顺序表的序号插入到索引表中。2.（1）递归函数BiTreeDepth （BiTreeT）如下。intBiTreeDepth(BiTreeT)名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 12 页 - - - - - - - - - 10intldepth,rdepth;if( !T )return0;ldepth= BiTreeDepth( T-lchild);rdepth= BiTreeDepth( T-rchild);if( ldepth= rdepth)T-depth= ldepth+1;elseT-depth= rdepth+1;returnT-depth;（2）递归函数BiTreeBalance( BiTreeT ) 程序如下。StatusBiTreeBalance(BiTreeT)intldepth,rdepth;if( T = NULL )returnTRUE;if( T-lchild)ldepth= T-lchild-depth;elseldepth= 0;if( T-rchild)rdepth= T-rchild-depth;elserdepth= 0;lrdepth= ldepth rdepth;if( (lrdepth 1 ) |( lrdepthlchild)& BiTreeBalance(T-rchild) )returnTRUE;elsereturnFALSE;计算机专业数据结构科目模拟试题（二）参考答案答案仅供参考一、单项选择题： 140题，每小题2 分共 80 分。在每小题给出的四个选项中，请选出一项最符合题目要求的。1.C2.C3.B4.A5.D6.C7.B8.C9.A10.B11.B二、综合应用题： 41-47小题，共 70 分1.（1）采用线性探测再哈希，对应的哈希表如下：Index0123456789101112Key78150357452031233612Search1111114121在等概率的情况下，该表中查找成功时的平均查找长度为ASL=(1+1+1+1+1 + 1 + 4+1+2+1)/10=1.4（2）采用双哈希法，对应的哈希表如下：Index0123456789101112名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 12 页 - - - - - - - - - 11Key78150357452031362312Search1111113511在等概率的情况下，该表中查找成功时的平均查找长度为ASL=(1+1+1+1+1 + 1 + 3+5+1+1)/10=1.62.（1）可能的不同出栈序列有（1/ （6+ 1） ）*12!/(6!)2=132 种。（2）不能得到435612 和 154623 这样的出栈序列。因为若在4，3，5，6 之后再将 1，2 出栈，则 1，2必须一直在栈中，此时1 先进栈，2 后进栈，2 应压在 1 上面，不可能1 先于 2 出栈。154623 也是这种情况。出栈序列325641 和 135426 可以得到，如图3 所示。图 3计算机专业数据结构科目模拟试题（三）参考答案答案仅供参考一、单项选择题： 140题，每小题2 分共 80 分。在每小题给出的四个选项中，请选出一项最符合题目要求的。1.C2.D3.C4.A5.C6.B7.D8.C9.B10.C11.B11 题解释： 150000 个记录（ 1000 个物理块）经内部排序后得到200 个初始段，需进行=4 趟 4路平衡归并排序。所以，总的I/O 次数为： 1000*2+1000*2*4=10000。二、综合应用题： 41-47小题，共 70 分1.（1）这个工程最早可能在43 时间结束；（2）首先求出每个事件的最早发生时间ve 和最迟发生时间vl ：123456ve01915293843vl01915373843每个活动的最早开始时间e() 和最迟开始时间l () ：1-21-33-22-52-43-54-65-6权215419101165e00151919152938l170151927273738（3）关键活动： 1-3,3-2,2-5,5-62.voidjoin(LinkListHa, LinkListHb, LinkList&Hc )Hc=(Linklist) malloc(sizeof(Lnode );/为 Hc链表建立头结点。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 12 页 - - - - - - - - - 12pc=Hc;pa=Ha-next;pb=Hb-next;while(pa!=NULL)& ( pb!=NULL ) )/扫描单链表Ha 和 Hbif(pa-datadata)pa=pa-next;elseif(pb-datadata)pb=pb-next;else/两链表当前结点的值相等/在 Hc链表表尾增加一个新结点pc-next=( Linklist)malloc(sizeof(Lnode );pc=pc-next;pc-data=pa-data;/ 交集的数据pa =pa-next;pb=pb-next;pc-next=NULL;名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 12 页 - - - - - - - - -