《2022年十套数据结构试题及答案.docx》由会员分享，可在线阅读，更多相关《2022年十套数据结构试题及答案.docx（72页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选学习资料 - - - - - - - - - 数据结构试卷（一）学习必备欢迎下载. 28 . 1数据结构试卷（一）参考答案数据结构试卷（二） . 5数据结构试卷（二）参考答案. 29 数据结构试卷（三） . 8数据结构试卷（三）参考答案. 30 数据结构试卷（四） . 10 数据结构试卷（四）参考答案. 32 数据结构试卷（五） . 13 数据结构试卷（五）参考答案. 34 数据结构试卷（六） . 16 数据结构试卷（六）参考答案. 35 数据结构试卷（七） . 18 数据结构试卷（七）参考答案. 38 数据结构试卷（八） . 20 数据结构试卷（八）参考答案. 39 数据结构试卷（九）
2、. 22 数据结构试卷（九）参考答案. 40 数据结构试卷（十） . 25 数据结构试卷（十）参考答案. 41数据结构试卷（一）一、单项题（每题 2 分,共 20 分）1. 栈和队列的共同特点是 A ；A. 只答应在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2. 用链接方式储备的队列,在进行插入运算时 D . A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D. 头、尾指针可能都要修改3. 以下数据结构中哪一个是非线性结构？ D A. 队列 B. 栈 C. 线性表 D. 二叉树4. 设有一个二维数组 Am n,假设 A00 存放位置在 64410,A2
3、2 存放位置在67610,每个元素占一个空间,问 A33 10存放在什么位置？脚注 10表示用 10 进制表示； C A 688 B678 C 692 D696 5. 树最适合用来表示 C ；A.有序数据元素 B.无序数据元素C.元素之间具有分支层次关系的数据6. 二叉树的第 k 层的结点数最多为 D . A2 k-1 B.2K+1 C.2K-1 D.元素之间无联系的数据D. 2k-1名师归纳总结 7. 如有 18 个元素的有序表存放在一维数组A19 中,第一个元素放A1 中,现进行二第 1 页,共 42 页分查找,就查找A 3的比较序列的下标依次为 D C A. 1 ,2,3 B. 9 ,5
4、, 2,3 C. 9,5,3 D. 9 ,4, 2,38. 对 n 个记录的文件进行快速排序,所需要的帮助储备空间大致为 A. O（1）B. O （ n） C. O（1og2n） D. O（n2）- - - - - - -精选学习资料 - - - - - - - - - 学习必备 欢迎下载9. 对于线性表（ 7,34,55, 25,64,46,20,10）进行散列储备时,如选用 H（K）=K %9 作为散列函数,就散列地址为1 的元素有（ D ）个, A 1 B2 C3 D4 10. 设有 6 个结点的无向图,该图至少应有 A 条边才能确保是一个连通图；A.5 B.6 C.7 D.8 二、填空
5、题（每空 1 分,共 26 分）1. 通常从四个方面评判算法的质量：_正确性 _、_高效性 _、_强壮型_和_易读性 _；2. 一个算法的时间复杂度为 n 3+n 2log 2n+14n/n 2,其数量级表示为 _O（n）_；3. 假定一棵树的广义表表示为 A（C,D（E,F,G）,H（I, J）,就树中所含的结点数为_9_个,树的深度为 _3_,树的度为 _3_；4. 后缀算式 9 2 3 +- 10 2 / - 的值为 _；中缀算式（ 3+4X ）-2Y/3 对应的后缀算式为_ ；5. 如用链表储备一棵二叉树时,每个结点除数据域外,仍有指向左孩子和右孩子的两个指针；在这种储备结构中, n
6、个结点的二叉树共有 _2n_个指针域,其中有 _n-1_个指针域是存放了地址,有_n+1_ 个指针是空指针；6.对于一个具有n 个顶点和 e 条边的有向图和无向图,在其对应的邻接表中,所含边结点分别有 _e_个和 _2e_个；7. 8.9.AOV 网是一种 _有向无回路 _的图；在一个具有n 个顶点的无向完全图中,包含有_nn-1/2_ 条边,在一个具有n 个顶点的有向完全图中,包含有_nn-1_ 条边；假定一个线性表为12,23,74,55,63,40 ,如按 Key % 4 条件进行划分, 使得同一余数的元素成为一个子表,就得到的四个子表分别为_12,40_ 、_74_、_ _和_23,5
7、5,63_ ；10.向一棵B_树插入元素的过程中,如最终引起树根结点的分裂,就新树比原树的高度_+1_；11.在堆排序的过程中,对任一分支结点进行筛运算的时间复杂度为_ Olog2n _,整个堆排序过程的时间复杂度为_ Onlog2n _；12. 在快速排序、堆排序、归并排序中,三、运算题（每题 6 分,共 24 分）_归并 _排序是稳固的；1.在如下数组A 中链接储备了一个线性表,表头指针为A 0.next ,试写出该线性表； A 0 1 2 3 4 5 6 7 34 40 data 60 50 78 90 next 3 5 7 2 0 4 1 线性表为：（ 78,50,40,60,34,9
8、0）2. 请画出下图的邻接矩阵和邻接表；邻接矩阵：名师归纳总结 01110第 2 页,共 42 页10101110111010101110- - - - - - -精选学习资料 - - - - - - - - - 学习必备 欢迎下载邻接表：3.已知一个图的顶点集V 和边集 E 分别为： V=1,2,3,4,5,6,7; E=1,23,1,35,1,48,2,510,2,36,3,415, 3,512,3,69,4,64,4,720,5,618,6,725; 用克鲁斯卡尔算法得到最小生成树,试写出在最小生成树中依次得到的各条边；用克鲁1. 斯卡尔算法得到的最小生成树为：4.1,23, 4,64,
9、 1,35, 1,48, 2,510, 4,720 5 12 画出向小根堆中加入数据4, 2, 5, 8, 3 时,每加入一个数据后堆的变化；见图4 4 2 2 2 2 2 4 4 图 12 5 4 5 4 8 8 3 2 3 5 8 4 四、阅读算法（每题 7 分,共 14 分）1. LinkList mynoteLinkList L /L 是不带头结点的单链表的头指针 ifL&L-next q=L ；L=L next；p=L ；S1： whilep next p=p next；S2：pnext=q ；qnext=NULL ；return L；请回答以下问题：（1）说明语句 S1 的功能；查
10、询链表的尾结点（2）说明语句组 S2 的功能；将第一个结点链接到链表的尾部,作为新的尾结点（3）设链表表示的线性表为（表；返回的线性表为（a2,a3, ,an,a1）2. void ABCBTNode * BT if BT a1,a2, ,an）,写出算法执行后的返回值所表示的线性名师归纳总结 - - - - - - -第 3 页,共 42 页精选学习资料 - - - - - - - - - 学习必备 欢迎下载ABC BT-left; ABC BT-right; coutdatadata item=BST-data;/ 查找胜利 return _ true _; else ifitemdata
11、 return Find_BST-left _,item; else return Find_BST-right _,item; /if 六、编写算法（共 8 分）统计出单链表 HL 中结点的值等于给定值 X 的结点数； int CountXLNode* HL,ElemType x 名师归纳总结 int i=0; LNode* p=HL;/i为计数器x 结点个数第 4 页,共 42 页whilep.=NULL if P-data=x i+; p=p-next; /while, 出循环时 i 中的值即为return i; /CountX - - - - - - -精选学习资料 - - - - -
12、 - - - - 学习必备 欢迎下载数据结构试卷（二）一、挑选题 24 分 1下面关于线性表的表达错误选项（D ）；A 线性表采纳次序储备必需占用一片连续的储备空间 B 线性表采纳链式储备不必占用一片连续的储备空间 C 线性表采纳链式储备便于插入和删除操作的实现 D 线性表采纳次序储备便于插入和删除操作的实现2设哈夫曼树中的叶子结点总数为 有（ B ）个空指针域；m,如用二叉链表作为储备结构,就该哈夫曼树中总共A 2m-1 B 2m C 2m+1 D 4m 3设次序循环队列 Q0：M-1 的头指针和尾指针分别为 F 和 R,头指针 F 总是指向队头元素的前一位置,尾指针 R 总是指向队尾元素的
13、当前位置,就该循环队列中的元素个数为（ C ）；A R-F B F-R C R-F+M M D F-R+M M 4设某棵二叉树的中序遍历序列为 ABCD ,前序遍历序列为 CABD ,就后序遍历该二叉树得到序列为（A ）；A BADC B BCDA C CDAB D CBDA 5设某完全无向图中有 n 个顶点,就该完全无向图中有（ A ）条边；A nn-1/2 B nn-1 C n D n 2-1 26设某棵二叉树中有 2000 个结点,就该二叉树的最小高度为（ C ）；A 9 B 10 C 11 D 12 7设某有向图中有 n 个顶点,就该有向图对应的邻接表中有（B）个表头结点；A n-1
14、B n C n+1 D 2n-1 8设一组初始记录关键字序列 5 ,2,6,3,8 ,以第一个记录关键字 5 为基准进行一趟快速排序的结果为（ C ）；A 2 ,3,5, 8,6 B 3 ,2,5, 8,6 C 3 ,2,5, 6,8 D 2 ,3,6, 5,8 二、填空题 24 分 1.为了能有效地应用HASH查找技术,必需解决的两个问题是_构造一个好的HASH函数_和_确定解决冲突的方法_；2. 下面程序段的功能实现数据 x 进栈,要求在下划线处填上正确的语句；typedef struct int s100; int top; sqstack; void pushsqstack &stac
15、k,int x if stack.top=m- 1 printf“overflow”;else _ stack.top+_;_ stack.sstack.top=x _; 3. 中序遍历二叉排序树所得到的序列是_有序 _ 序列（填有序或无序） ；名师归纳总结 4. 快速排序的最坏时间复杂度为_ On2_ ,平均时间复杂度为_Onlog 2n_ ；第 5 页,共 42 页- - - - - - -精选学习资料 - - - - - - - - - 5. 设某棵二叉树中度数为学习必备欢迎下载N1,就该二叉树中度数为20 的结点数为N0,度数为 1 的结点数为的结点数为 _ N0-1_ ；如采纳二叉链
16、表作为该二叉树的储备结构,就该二叉树中共有_2N0+N1_个空指针域；6. 设某无向图中顶点数和边数分别为n 和 e,全部顶点的度数之和为d,就 e=_d/2_ ；7. 设一组初始记录关键字序列为55 ,63,44,38,75,80,31,56 ,就利用挑选法建立的初始堆为 _ 31 ,38,54,56,75,80,55,63_ ；8 已知一有向图的邻接表储备结构如下：从顶点1 动身, DFS 遍历的输出序列是1,3,4,5,2 ,BFS 遍历的输出序列是1,3,2,4,5 三、应用题 36 分 1 设一 组初始记录关键字序列为45 ,80,48, 40,22,78 ,就分别给出第4 趟简洁挑
17、选排序和第 4 趟直接插入排序后的结果；22 ,40,45,48,80,78 ,40 ,45,48,80,22,78 2 设指针变量p 指向双向链表中结点A,指针变量 q 指向被插入结点B,要求给出在结点A的后面插入结点B的操作序列（设双向链表中结点的两个指针域分别为llink和 rlink）；q-llink=p; q-rlink=p-rlink; p-rlink-llink=q; p-rlink=q; 3 设一组有序的记录关键字序列为 二分查找,要求运算出查找关键字 度；2,ASL=91*1+2*2+3*4+4*2=25/9 13 ,18,24,35,47,50, 62,83,90 ,查找方
18、法用 62 时的比较次数并运算出查找胜利时的平均查找长4 设一棵树 T 中边的集合为 A ,B,A,C,A ,D,B, E,C,F,C, G ,要求用孩子兄弟表示法（二叉链表）表示出该树的储备结构并将该树转化成对应的二叉树；名师归纳总结 5 设有无向图G,要求给出用普里姆算法构造最小生成树所走过的边的集合；第 6 页,共 42 页- - - - - - -精选学习资料 - - - - - - - - - 学习必备 欢迎下载E=1 ,3,1, 2, 3,5,5,6,6,4 6 设有一组初始记录关键字为 出构造过程；四、算法设计题 16 分 45 ,80,48,40,22,78 ,要求构造一棵二叉
19、排序树并给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; if ij ri=rj;i=i+1; while ij & rix i=i+1; if inext forq=hb;q.=0;q=q-next if q-data=p-data break; ifq.=0 t=lklist *ma
20、llocsizeoflklist; t-data=p-data;t-next=hc; hc=t; 名师归纳总结 - - - - - - -第 7 页,共 42 页精选学习资料 - - - - - - - - - 学习必备 欢迎下载数据结构试卷（三）一、挑选题 每题 1 分,共 20 分 1设某数据结构的二元组形式表示为A=D ,R,D=01 ,02,03, 04,05,06,07,08,09 ,R=r ,r=, ,就数据结构 A 是（）；A 线性结构 B 树型结构 C 物理结构 D 图型结构2下面程序的时间复杂为（）for（i=1 ,s=0； i=n ； i+ ） t=1 ；forj=1 ；j
21、next； p-data=q-data；p-next=q-next；freeq；B q=p-next； q-data=p-data；p-next=q-next；freeq；C q=p-next； p-next=q-next；freeq；D q=p-next； p-data=q-data；freeq；4设有 n 个待排序的记录关键字,就在堆排序中需要（）个帮助记录单元；A 1 B n C nlog2n D n25设一组初始关键字记录关键字为20 ,15,14,18,21,36,40,10 ,就以 20 为基准记录的一趟快速排序终止后的结果为 ；A 10 , 15,14,18,20,36,40,2
22、1 B 10 , 15,14,18, 20,40,36,21 C 10 , 15,14,20, 18,40,36,2l D 15 , 10,14,18, 20,36,40,21 6设二叉排序树中有 n 个结点,就在二叉排序树的平均平均查找长度为（）；A O1 B Olog 2n C D On 2 7设无向图 G中有 n 个顶点 e 条边,就其对应的邻接表中的表头结点和表结点的个数分别为（）；A n,e B e ,n C 2n , e D n ,2e 8. 设某强连通图中有 n 个顶点,就该强连通图中至少有（）条边；A nn-1 B n+1 C n D nn+1 9设有 5000 个待排序的记录
23、关键字,假如需要用最快的方法选出其中最小的 10 个记录关键字,就用以下（）方法可以达到此目的；A 快速排序 B 堆排序 C 归并排序 D 插入排序10. 以下四种排序中（）的空间复杂度最大；A 插入排序 B 冒泡排序 C 堆排序 D 归并排序二、填空殖 每空 1 分 共 20 分 1.数据的物理结构主要包括_ 和_两种情形；2.设一棵完全二叉树中有500 个结点, 就该二叉树的深度为_；如用二叉链表作为该完全二叉树的储备结构,就共有_个空指针域；名师归纳总结 3.设输入序列为1、2、3,就经过栈的作用后可以得到_种不同的输出序列；第 8 页,共 42 页4.设有向图 G用邻接矩阵Ann作为储
24、备结构, 就该邻接矩阵中第i 行上全部元素之和等于顶点 i 的 _,第 i 列上全部元素之和等于顶点i 的_；- - - - - - -精选学习资料 - - - - - - - - - 5.设哈夫曼树中共有学习必备欢迎下载_个度数为 1 的结点；n 个结点,就该哈夫曼树中有6.设有向图 G中有 n 个顶点 e 条有向边,全部的顶点入度数之和为d,就 e 和 d 的关系为_；7._遍历二叉排序树中的结点可以得到一个递增的关键字序列（填先序、 中序或后序）；8. 设查找表中有 100 个元素,假如用二分法查找方法查找数据元素 X,就最多需要比较_次就可以肯定数据元素 X是否在查找表中；9. 不论是
25、次序储备结构的栈仍是链式储备结构的栈,其入栈和出栈操作的时间复杂度均为_；10. 设有 n 个结点的完全二叉树,假如依据从自上到下、从左到右从 1 开头次序编号, 就第i 个结点的双亲结点编号为 _,右孩子结点的编号为 _ ；11. 设一组初始记录关键字为 72 ,73,71,23,94,16,5 ,就以记录关键字 72 为基准的一趟快速排序结果为 _；12. 设有向图 G中有向边的集合 E=, ,就该图的一种拓扑序列为 _；13. 以下算法实现在次序散列表中查找值为 x 的关键字,请在下划线处填上正确的语句；struct recordint key; int others; int hash
26、sqsearchstruct 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 *bstsearchbitree *t, int
27、 k if t=0 return0;else while t.=0 if t-key=k_; else if t-keyk t=t-lchild; else_; 三、运算题 每题 10 分,共 30 分 1.已知二叉树的前序遍历序列是AEFBGCDHIKJ ,中序遍历序列是EFAGBCHKIJD ,画出此二叉树,并画出它的后序线索二叉树；2已知待散列的线性表为（36, 15,40,63,22）,散列用的一维地址空间为 0.6,假定选用的散列函数是 H（K）= K mod 7 ,如发生冲突采纳线性探查法处理,试：（1）运算出每一个元素的散列地址并在下图中填写出散列表： 0 1 2 3 4 5 6
28、 （2）求出在查找每一个元素概率相等情形下的平均查找长度；3已知序列（ 10,18,4,3,6,12,1,9,18,8）请用快速排序写出每一趟排序的结果；四、算法设计题 每题 15 分,共 30 分 1 设计在单链表中删除值相同的余外结点的算法；名师归纳总结 2 设计一个求结点x 在二叉树中的双亲结点算法；第 9 页,共 42 页- - - - - - -精选学习资料 - - - - - - - - - 学习必备 欢迎下载数据结构试卷（四）一、挑选题 每题 1 分共 20 分 1设一维数组中有n 个数组元素,就读取第i 个数组元素的平均时间复杂度为（）；）A On B Onlog2n C O1
29、 D On2 2设一棵二叉树的深度为k,就该二叉树中最多有（）个结点；A 2k-1 B 2kC 2k-1D 2k-1 3设某无向图中有n 个顶点 e 条边,就该无向图中全部顶点的入度之和为（）；A n B e C 2n D 2e 4在二叉排序树中插入一个结点的时间复杂度为（）；A O1 B On C Olog2n D On2 5设某有向图的邻接表中有n 个表头结点和m个表结点,就该图中有（）条有向边；A n B n-1 C m D m-1 6设一组初始记录关键字序列为345 ,253,674,924,627 ,就用基数排序需要进行（趟的安排和回收才能使得初始关键字序列变成有序序列；A 3 B
30、4 C 5 D 8 7设用链表作为栈的储备结构就退栈操作（）；A 必需判别栈是否为满 B 必需判别栈是否为空C 判别栈元素的类型 D 对栈不作任何判别8以下四种排序中（）的空间复杂度最大；A 快速排序 B 冒泡排序 C 希尔排序 D 堆9设某二叉树中度数为 0 的结点数为 N0,度数为 1 的结点数为 Nl ,度数为 2 的结点数为 N2,就以下等式成立的是（）；A N 0=N1+1 B N 0=Nl+N2 C N 0=N2+1 D N 0=2N1+l 10. 设有序次序表中有 n 个数据元素,就利用二分查找法查找数据元素 X 的最多比较次数不超过（）；A log 2n+1 B log 2n-
31、1 C log 2n D log 2n+1 二、填空题 每空 1 分共 20 分 1 设有 n 个无序的记录关键字,就直接插入排序的时间复杂度为 _,快速排序的平均时间复杂度为 _；2 设指针变量 p 指向双向循环链表中的结点 X,就删除结点 X 需要执行的语句序列为_ （设结点中的两个指针域分别为 llink 和 rlink）；3 依据初始关键字序列 19 ,22,01,38,10 建立的二叉排序树的高度为 _；4 深度为 k 的完全二叉树中最少有 _个结点；5 设初始记录关键字序列为 K 1,K2, , Kn ,就用挑选法思想建堆必需从第 _个元素开头进行挑选；6 设哈夫曼树中共有 99
32、个结点, 就该树中有 _个叶子结点； 如采纳二叉链表作为储备结构,就该树中有 _个空指针域；7 设有一个次序循环队列中有 M个储备单元, 就该循环队列中最多能够储备 _个队列元素； 当前实际储备 _个队列元素 （设头指针 F 指向当前队头元素的名师归纳总结 前一个位置,尾指针指向当前队尾元素的位置）；第 10 页,共 42 页- - - - - - -精选学习资料 - - - - - - - - - 8 设次序线性表中有学习必备i欢迎下载n 个数据元素,就第个位置上插入一个数据元素需要移动表中_个数据元素；删除第i 个位置上的数据元素需要移动表中_个元素；9 设一组初始记录关键字序列为20,1
33、8,22,16,30,19,就以20 为中轴的一趟快速排序结果为 _ ；10设一组初始记录关键字序列为20,18,22,16,30,19,就依据这些初始关键字序列建成的初始堆为 _；11设某无向图 G 中有 n 个顶点,用邻接矩阵 A 作为该图的储备结构,就顶点 i 和顶点 j互为邻接点的条件是 _ ；12设无向图对应的邻接矩阵为A,就 A 中第 i 上非 0 元素的个数 _第 i 列上非 0元素的个数（填等于,大于或小于）；13设前序遍历某二叉树的序列为 ABCD ,中序遍历该二叉树的序列为 BADC ,就后序遍历 该二叉树的序列为 _；14设散列函数 Hk=k mod p ,解决冲突的方法为链地址法；要求在以下算法划线处填上正 确的语句完成在散列表 hashtalbe 中查找关键字值等于 k 的结点,胜利时返回指向关键 字的指针,不胜利时返回标志 0；