2022年五套数据结构试题及答案.docx

《2022年五套数据结构试题及答案.docx》由会员分享，可在线阅读，更多相关《2022年五套数据结构试题及答案.docx（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选学习资料 - - - - - - - - - 数据结构试卷（一）二、填空题（每空 1 分,共 26 分）1. 通常从四个方面评判算法的质量：_、_、_和_；2. 一个算法的时间复杂度为 n 3+n 2log 2n+14n/n 2,其数量级表示为 _；3. 假定一棵树的广义表表示为 A（C,D（E,F,G）,H（I, J）,就树中所含的结点数为_个,树的深度为_,树的度为 _；4. 后缀算式 9 2 3 +- 10 2 / - 的值为 _；中缀算式（ 3+4X ）-2Y/3 对应的后缀算式为_ ；5.如用链表储备一棵二叉树时,每个结点除数据域外,仍有指向左孩子和右孩子的两个指针；在这种储备结

2、构中,n 个结点的二叉树共有_个指针域,其中有_ 个指针域是存放了地址,有_个指针是空指针；6. 7. 8. 9.对于一个具有n 个顶点和 e 条边的有向图和无向图,在其对应的邻接表中,所含边结点分别有 _个和 _个；AOV 网是一种 _ 的图；在一个具有n 个顶点的无向完全图中,包含有 _条边,在一个具有n 个顶点的有向完全图中,包含有_条边；假定一个线性表为12,23,74,55,63,40 ,如按 Key % 4 条件进行划分, 使得同一余数的元素 成 为 一 个 子 表 , 就 得 到 的 四 个 子 表 分 别 为 _ 、_ 、_和_ ；10.向一棵B_树插入元素的过程中,如最终引起

3、树根结点的分裂,就新树比原树的高度_；11.在堆排序的过程中,对任一分支结点进行筛运算的时间复杂度为_,整个堆排序过程的时间复杂度为_；12. 在快速排序、堆排序、归并排序中,三、运算题（每题 6 分,共 24 分）_排序是稳固的；1.2.3.在如下数组A 中链接储备了一个线性表,表头指针为A 0.next ,试写出该线性表； A 0 1 2 3 4 5 6 7 data 60 50 78 90 34 40 next 3 5 7 2 0 4 1 请画出下图的邻接矩阵和邻接表；已知一个图的顶点集V 和边集 E 分别为： V=1,2,3,4,5,6,7; E=1,23,1,35,1,48,2,51

4、0,2,36,3,415, 3,512,3,69,4,64,4,720,5,618,6,725; 用克鲁斯卡尔算法得到最小生成树,试写出在最小生成树中依次得到的各条边；4.四、阅读算法（每题7 分,共 14 分）1. LinkList mynoteLinkList L /L 是不带头结点的单链表的头指针 ifL&L-next q=L ；L=L next；p=L ；名师归纳总结 S1：whilep next p=p next；第 1 页,共 15 页- - - - - - -精选学习资料 - - - - - - - - - S2：pnext=q ；qnext=NULL ； return L；请回

5、答以下问题：（1）说明语句S1 的功能；a1,a2, ,an）,写出算法执行后的返回值所表示的线性（2）说明语句组S2 的功能；表；（3）设链表表示的线性表为（2. void ABCBTNode * BT if BT ABC BT-left; ABC BT-right; coutdatadata item=BST-data;/ 查找胜利 return _; else ifitemdata return Find_,item; else return Find_,item; /if 六、编写算法（共 8 分）统计出单链表 HL 中结点的值等于给定值 X 的结点数； int CountXLNode

6、* HL,ElemType x名师归纳总结 - - - - - - -第 2 页,共 15 页精选学习资料 - - - - - - - - - 数据结构试卷（二）二、填空题 24 分 1.为了能有效地应用HASH查找技术,必需解决的两个问题是_ 和_ ；2.下面程序段的功能实现数据x 进栈,要求在下划线处填上正确的语句；typedef struct int s100; int top; sqstack; void pushsqstack &stack,int x if stack.top=m- 1 printf“overflow”;else _;_; 3. 中序遍历二叉排序树所得到的序列是 _

7、序列（填有序或无序） ；4. 快速排序的最坏时间复杂度为 _,平均时间复杂度为 _；5. 设某棵二叉树中度数为 0 的结点数为 N0,度数为 1 的结点数为 N1,就该二叉树中度数为2 的结点数为 _；如采纳二叉链表作为该二叉树的储备结构,就该二叉树中共有_个空指针域；6. 设某无向图中顶点数和边数分别为 n 和 e,全部顶点的度数之和为 d,就 e=_；7. 设一组初始记录关键字序列为 55 ,63,44,38,75,80,31,56 ,就利用挑选法建立的初始堆为 _ ；8 已知一有向图的邻接表储备结构如下：从顶点,BFS 遍历的输出序列是三、应用题 36 分 1 动身, DFS 遍历的输出

8、序列是1 设一组初始记录关键字序列为45 ,80,48, 40,22,78 ,就分别给出第4 趟简洁挑选排序和第 4 趟直接插入排序后的结果；2 设一组有序的记录关键字序列为 二分查找,要求运算出查找关键字 度；13 ,18,24,35,47,50, 62,83,90 ,查找方法用 62 时的比较次数并运算出查找胜利时的平均查找长名师归纳总结 3 设有无向图G,要求给出用普里姆算法构造最小生成树所走过的边的集合；第 3 页,共 15 页- - - - - - -精选学习资料 - - - - - - - - - 4 设有一组初始记录关键字为 出构造过程；四、算法设计题 16 分 45 ,80,4

9、8,40,22,78 ,要求构造一棵二叉排序树并给名师归纳总结 1 设有一组初始记录关键字序列（K1,K2, , Kn）,要求设计一个算法能够在On 的时间第 4 页,共 15 页复杂度内将线性表划分成两部分,其中左半部分的每个关键字均小于Ki,右半部分的每个关键字均大于等于Ki；- - - - - - -精选学习资料 - - - - - - - - - 数据结构试卷（三）二、填空殖 每空 1 分 共 20 分 1.数据的物理结构主要包括_ 和_两种情形；2.设一棵完全二叉树中有500 个结点, 就该二叉树的深度为_；如用二叉链表作为该完全二叉树的储备结构,就共有_个空指针域；3. 设输入序列

10、为 1、2、3,就经过栈的作用后可以得到 _种不同的输出序列；4. 设有向图 G用邻接矩阵 Ann 作为储备结构, 就该邻接矩阵中第 i 行上全部元素之和等于顶点 i 的 _,第 i 列上全部元素之和等于顶点 i 的_；5. 设哈夫曼树中共有 n 个结点,就该哈夫曼树中有 _个度数为 1 的结点；6. 设有向图 G中有 n 个顶点 e 条有向边,全部的顶点入度数之和为 d,就 e 和 d 的关系为_；7._遍历二叉排序树中的结点可以得到一个递增的关键字序列（填先序、 中序或后序）；8. 设查找表中有 100 个元素,假如用二分法查找方法查找数据元素 X,就最多需要比较_次就可以肯定数据元素 X

11、是否在查找表中；9. 不论是次序储备结构的栈仍是链式储备结构的栈,其入栈和出栈操作的时间复杂度均为_；10. 设有 n 个结点的完全二叉树,假如依据从自上到下、从左到右从 1 开头次序编号, 就第i 个结点的双亲结点编号为 _,右孩子结点的编号为 _ ；11. 设一组初始记录关键字为 72 ,73,71,23,94,16,5 ,就以记录关键字 72 为基准的一趟快速排序结果为 _；12. 设有向图 G中有向边的集合 E=, ,就该图的一种拓扑序列为 _；13. 以下算法实现在次序散列表中查找值为 x 的关键字,请在下划线处填上正确的语句；struct recordint key; int ot

12、hers; int hashsqsearchstruct record hashtable ,int k int i,j; j=i=k % p; while hashtablej.key.=k&hashtablej.flag.=0j=_ %m; if i=j return-1; if _ returnj; else return-1; 14.以下算法实现在二叉排序树上查找关键值k,请在下划线处填上正确的语句；typedef struct nodeint key; struct node *lchild; struct node *rchild;bitree; bitree *bstsearch

13、bitree *t, int k if t=0 return0;else while t.=0 if t-key=k_; else if t-keyk t=t-lchild; else_; 三、运算题 每题 10 分,共 30 分 1. 名师归纳总结 2已知待散列的线性表为（36, 15,40,63,22）,散列用的一维地址空间为0.6,假定第 5 页,共 15 页- - - - - - -精选学习资料 - - - - - - - - - 选用的散列函数是 H（K）= K mod 7 ,如发生冲突采纳线性探查法处理,试：（1）运算出每一个元素的散列地址并在下图中填写出散列表： 0 1 2 3

14、4 5 6 （2）求出在查找每一个元素概率相等情形下的平均查找长度；3已知序列（ 10,18,4,3,6,12,1,9,18,8）请用快速排序写出每一趟排序的结果；四、算法设计题 每题 15 分,共 30 分 1 设计在单链表中删除值相同的余外结点的算法；名师归纳总结 - - - - - - -第 6 页,共 15 页精选学习资料 - - - - - - - - - 数据结构试卷（四）二、填空题 每空 1 分共 20 分 1 设有 n 个无序的记录关键字,就直接插入排序的时间复杂度为 _,快速排序的平均时间复杂度为 _；2 设指针变量 p 指向双向循环链表中的结点 X,就删除结点 X 需要执行

15、的语句序列为_ （设结点中的两个指针域分别为 llink 和 rlink）；3 依据初始关键字序列 19 ,22,01,38,10 建立的二叉排序树的高度为 _；4 深度为 k 的完全二叉树中最少有 _个结点；5 设初始记录关键字序列为 K 1,K2, , Kn ,就用挑选法思想建堆必需从第 _个元素开头进行挑选；6 设哈夫曼树中共有 99 个结点, 就该树中有 _个叶子结点； 如采纳二叉链表作为储备结构,就该树中有 _个空指针域；7 设有一个次序循环队列中有 M个储备单元, 就该循环队列中最多能够储备 _个队列元素； 当前实际储备 _个队列元素 （设头指针 F 指向当前队头元素的前一个位置,

16、尾指针指向当前队尾元素的位置）；8 设次序线性表中有 n 个数据元素,就第 i 个位置上插入一个数据元素需要移动表中_个数据元素；删除第 i 个位置上的数据元素需要移动表中 _个元素；9 设一组初始记录关键字序列为 20,18,22,16,30,19,就以 20 为中轴的一趟快速排序结果为 _ ；10设一组初始记录关键字序列为20,18,22,16,30,19,就依据这些初始关键字序列建成的初始堆为 _；11设某无向图 G 中有 n 个顶点,用邻接矩阵 A 作为该图的储备结构,就顶点 i 和顶点 j互为邻接点的条件是 _ ；12设无向图对应的邻接矩阵为A,就 A 中第 i 上非 0 元素的个数

17、 _第 i 列上非 0元素的个数（填等于,大于或小于）；13设前序遍历某二叉树的序列为 ABCD ,中序遍历该二叉树的序列为 BADC ,就后序遍历 该二叉树的序列为 _；14设散列函数 Hk=k mod p ,解决冲突的方法为链地址法；要求在以下算法划线处填上正 确的语句完成在散列表 hashtalbe 中查找关键字值等于 k 的结点,胜利时返回指向关键 字的指针,不胜利时返回标志 0；typedef struct node int key; struct node *next; lklist; void createlkhashlklist *hashtable int i,k; lkli

18、st *s; fori=0;im;i+_; fori=0;ikey=ai; k=ai % p; s-next=hashtablek;_; 名师归纳总结 - - - - - - -第 7 页,共 15 页精选学习资料 - - - - - - - - - 三、运算题 每题 10 分,共 30 分3、设散列表的地址范畴是 0.9 ,散列函数为H（key ）= （key 2 +2）MOD 9,并采纳链表处理冲突,请画出元素二、填空题 共 20 分 7、 4、5、3、6、 2、8、9 依次插入散列表的储备结构；数据结构试卷（五）1.设有一个次序共享栈S0 ：n-1 ,其中第一个栈项指针top1 的初值为

19、 -1 ,其次个栈顶指针 top2 的初值为 n,就判定共享栈满的条件是_；2. 在图的邻接表中用次序储备结构储备表头结点的优点是 _ ；3. 设有一个 n 阶的下三角矩阵 A,假如依据行的次序将下三角矩阵中的元素（包括对角线上元素）存放在 nn+1 个连续的储备单元中,就 Aij 与 A00 之间有 _个数据元素；4. 栈的插入和删除只能在栈的栈顶进行,后进栈的元素必定先出栈,所以又把栈称为_表；队列的插入和删除运算分别在队列的两端进行,出队列,所以又把队列称为 _表；先进队列的元素必定先5. 设一棵完全二叉树的次序储备结构中储备数据元素为 ABCDEF,就该二叉树的前序遍历 序列为 _,中

20、序遍历序列为 _,后序遍历序列为 _；128 个结点,就该完全二叉树的深度为 _,有 _ 6. 设一棵完全二叉树有 个叶子结点；7. 设有向图 G的储备结构用邻接矩阵 A 来表示,就 A 中第 i 行中全部非零元素个数之和等 于顶点 i 的_,第 i 列中全部非零元素个数之和等于顶点 i 的_；8. 设一组初始记录关键字序列 k 1,k 2, , k n 是堆,就对 i=1 ,2, , n/2 而言满意 的条件为 _ ；9. 下面程序段的功能是实现冒泡排序算法,请在下划线处填上正确的语句；void bubbleint rn fori=1;i=n-1; i+ forexchange=0,j=0;

21、 jrj+1temp=rj+1;_;rj=temp;exchange=1; if exchange=0 return ； 10. 下面程序段的功能是实现二分查找算法,请在下划线处填上正确的语句；struct recordint key; int others; int bisearchstruct record r , int k int low=0,mid,high=n-1; whilelowleft BST-right六、编写算法（8 分）int CountXLNode* HL,ElemType x 名师归纳总结 int i=0; LNode* p=HL;/i为计数器第 10 页,共 15

22、 页- - - - - - -精选学习资料 - - - - - - - - - whilep.=NULL if P-data=x i+; p=p-next; /while, 出循环时 i 中的值即为x 结点个数return i; /CountX 数据结构试卷（二）参考答案二、填空题1. 构造一个好的 HASH函数,确定解决冲突的方法 2. stack.top+,stack.sstack.top=x 3. 有序 4. On 2 ,Onlog 2n 5. N0-1 ,2N0+N1 6. d/2 7. 31 ,38,54,56,75, 80,55,63 8. 1 ,3, 4,5,2 ,1 , 3,2

23、,4,5 三、应用题 1. 22 ,40,45,48,80, 78 ,40 ,45, 48,80,22,78 2. 2,ASL=91*1+2*2+3*4+4*2=25/9 3. E=1 , 3, 1,2,3,5,5,6,6,4 4. 略四、算法设计题1.设有一组初始记录关键字序列（K1,K2, , Kn）,要求设计一个算法能够在On 的时间复杂度内将线性表划分成两部分,其中左半部分的每个关键字均小于Ki,右半部分的每个关键字均大于等于Ki；void quickpassint r, int s, int t int i=s, j=t, x=rs; whileij while ix j=j-1;

24、if ij ri=rj;i=i+1; while ij & rix i=i+1; if irchild 第 8 小题分析：二分查找的过程可以用一棵二叉树来描述,该二叉树称为二叉判定树；在有序表上进行二分查找时的查找长度不超过二叉判定树的高度 1+log 2n；三、运算题1、H36=36 mod 7=1; H22=1+1 mod 7=2; .冲突H15=15 mod 7=1; .冲突 H222=2+1 mod 7=3; H15=1+1 mod 7=2; H40=40 mod 7=5; H63=63 mod 7=0; H22=22 mod 7=1; .冲突（1）10 11 2 3 4 5 6 63

25、 36 15 22 40 （2）ASL=2131 6.52、8,9,4,3,6,1,10,12,18,18 1,6,4,3,8,9,10,12,18,18 1,3,4,6,8,9,10,12,18,18 1,3,4,6,8,9,10,12,18,18 1,3, 4,6,8,9,10,12,18,18 四、算法设计题名师归纳总结 - - - - - - -第 12 页,共 15 页精选学习资料 - - - - - - - - - 1. 设计在单链表中删除值相同的余外结点的算法；typedef int datatype; typedef struct node datatype data; str

26、uct node *next;lklist; void delredundantlklist *&head lklist *p,*q,*s; forp=head;p.=0;p=p-next forq=p-next,s=q;q.=0; if q-data=p-data s-next=q-next; freeq;q=s-next; else s=q,q=q-next; 数据结构试卷（四）参考答案二、填空题1.2. 3. 4. 5. 6.7.8.9.10. 11. 12. 13. 14.On 2 ,Onlog2n pllink-rlink=p-rlink; p-rlink-llink=p-rlink

27、 3 k-1 2 n/2 50,51 m-1,R-F+M%M n+1-i,n-i 19 ,18,16,20,30, 22 16 ,18,19,20,32, 22 Aij=1 等于 BDCA hashtablei=0 ,hashtablek=s三、运算题 1LS1-1-11名师归纳总结 10e10a-1010-10第 13 页,共 15 页1-bcd- - - - - - -精选学习资料 - - - - - - - - - 21 ABCDEF; BDEFCA ；2 ABCDEFGHIJK; BDEFCAIJKHG林转换为相应的二叉树；ABDCIHGKEFJ3H4=H5=0,H3=H6=H9=2,

28、H8=3,H2=H7=6 045936123842756789数据结构试卷（五）参考答案二、填空题1. top1+1=top2 2. 可以随机拜访到任一个顶点的简洁链表3. ii+1/2+j-1 4. FILO ,FIFO 5. ABDECF ,DBEAFC ,DEBFCA 6. 8,64 7. 出度,入度8. ki=k 2i & k ik三、应用题名师归纳总结 1.DEBCA 第 14 页,共 15 页2.ASL=1*1+2*2+3*4/7=17/7 3.ASL1=7/6 ,ASL2=4/3 - - - - - - -精选学习资料 - - - - - - - - - 四、算法设计题1. 设计两个有序单链表的合并排序算法；void mergelklistlklist *ha,lklist *hb,lklist *&hc lklist *s=hc=0; whileha.=0 & hb.=0 ifha-datadataifs=0 hc=s=ha; else s-next=ha; s=ha;ha=ha-next; else ifs=0 hc=s=hb; else s-next=hb; s=hb;hb=hb-next; ifha=0 s-next=hb; else s-next=ha; 名师归纳总结 - - - - - - -第 15 页,共 15 页