数据结构试卷A1、在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x与元素的平均比较次数，假定查找每个元素的概率都相等）为（）。Bn/2C(n+1)/2D(n-1)/22、在一个单链表中，若q所指结点是p所指结点的前驱结点,若在q与p之间插入一个s所指的结点，则执行（）。As—next=p—next;p—next=s;Bp—next=s;s—next=q;Cp—next=s—next;s—next=p;Dq—next=s;s—next=p;3、栈的插入和删除操作在（）进行。A栈顶B栈底C任意位置D指定位置4、由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）A24B71C48D53二、填空题（每空1分，共30分）1、数据的逻辑结构被分为和四种。2、一种抽象数据类型包括和两个部分。3、在下面的数组a中链接存储着一个线性表，表头指针为a[0].next，则该线性表为012345678data605642387425next4「3762014、在以HL为表头指针的带表头附加结点的单链表和循环单链表中,判断链表为空的条件分别为和5、用具有n个元素的一维数组存储一个循环队列，则其队首指针总是指向队首元素的，该循环队列的最大长度为6、当堆栈S采用顺序存储结构时，栈顶元素的值可用表示；当堆栈采用链接存储结构时，栈顶元素的值可用表示。7、一棵高度为5的二叉树中最少含有个结点，最多含有个结点。8、在无向图的邻接表中，每个结点被称为，通常它包含三个域：一是；二是；三是9、在一个索引文件的索引表中，每个索引项包含对应记录的和两项数据。10、假定一棵树的广义表表示为A(B(C，D(E，F，G)，H(I，J)))，则树中所含的结点数为个，树的深度为,树的度为,结点H的双亲结点为,孩子结点为。11、在堆排序的过程中，对任一分支结点进行筛选运算的时间复杂度为,整个堆排序过程的时间复杂度为12、二维数组A[10][5](下标从0开始)采用行序为主方式存储，每个元素占4个存储单元，并且A[5][3]的存储地址是1000,则TOC\o"1-5"\h\zA[8][2]的地址是。13、设广义表A=(x,((a,b),c,d))，则Head(Head(Ta订(A)))=。三、简答与运算题(每小题6分，共30分)1、已知一组记录的排序码为(46，79，56，38，40，80,95，24)，写出对其进行快速排序的每一次划分结果2、一个线性表为B=（12，23，45，57，20，03，78，31，15，36），设散列表为HT[0..12]，散列函数为H（key）=key%13并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。3、已知一棵二叉树的前序遍历的结果序列是ABECDFGHIJ，中序遍历的结果是EBCDAFHIGJ，试写出这棵二叉树的后序遍历结果。4、已知一个图的顶点集V和各边集E如下：V=｛0，1，2，3，4，5，6，7，8，9｝；E=｛（0，1），（0，4），（1，2），（1，7）（2，8），（3，4），（3，8），（5，6），（5，8），（5，9），（6，7），（7，8），（8，9）｝当它用邻接矩阵表示和邻接表表示时，分别写出从顶点V0出发0按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历等到的顶点序列。假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的。图深度优先序列广度优先序列邻接矩阵表示时邻接表表示时5、已知一个图如下，则由该图得到全部可能的拓扑序列。四、阅读算法，回答问题(8分)假定从键盘上输入一批整数，依次为：786345309134-1,请分析程序功能，回答注释并写出输出结果。#include#includeconstintstackmaxsize=30;typedefintelemtype;structstack{/*从此开始的4行什么作用?*/elemtypestack[stackmaxsize];inttop;};#include“stack.h”voidmain(){stacka;initstack(a);intx;scanf(“%d”,&x);while(x!=-1){/*循环的功能是什么?*/push(a,x);scanf(“%d”,&x);}while(!stackempty(a))/*这个循环的功能是什么?*/printf(“%d,”,pop(a));printf(“\n”);}该算法的输出结果为：五、算法设计（每题12分，共24分）1、对于二维数组A[m][n],分别编写相应函数实现如下功能：（1）求数组A靠边元素之和；（2）求从A[0][0]开始的互不相邻的各元素之和；（3）当m=n时分别求两条对角线上的元素之和，否则打印出mHn的信息。2、采用堆存储串s,设计函数删除s中第i个字符开始的j个字符。
本文档为【北京理工大学珠海学院计算机专业数据结构培训资料A卷】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483