2022年完整word版,2021《数据结构》期末考试试题及答案 .pdf

《2022年完整word版,2021《数据结构》期末考试试题及答案 .pdf》由会员分享，可在线阅读，更多相关《2022年完整word版,2021《数据结构》期末考试试题及答案 .pdf（23页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第 1 页 共 23 页2017数据结构期末考试试题及答案数据结构期末考试试题及答案1. 2 试题 1 答案. 7 数据结构期末考试试题及答案2. 9 试题 2 答案. 14 数据结构期末考试试题及答案3. 16 试题 3 答案. 21 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 23 页第 2 页 共 23 页数据结构期末考试试题及答案1 一、单选题（每题2 分，共 20 分）1.栈和队列的共同特点是 ( )。A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2.用链接方式存储的队列，在进行插入运算时(

2、 ). A. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改3.以下数据结构中哪一个是非线性结构？( ) A. 队列B. 栈C. 线性表D. 二叉树4.设有一个二维数组Amn，假设 A00 存放位置在 644(10)，A22 存放位置在 676(10)，每个元素占一个空间， 问 A33(10)存放在什么位置？脚注(10)表示用 10进制表示。A688 B678 C692 D696 5.树最适合用来表示 ( )。A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.二叉树的第 k 层的结点数最多为 ( ). A2k-1 B

3、.2K+1 C.2K-1 D. 2k-17.若有 18个元素的有序表存放在一维数组A19 中， 第一个元素放 A1 中，现进行二分查找，则查找A3的比较序列的下标依次为( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 8.对 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 的元素有（）个，精选学习资料 - - - - - - - - - 名师归纳总

4、结 - - - - - - -第 2 页，共 23 页第 3 页 共 23 页A1 B2 C3 D4 10. 设有 6 个结点的无向图，该图至少应有 ( )条边才能确保是一个连通图。A.5 B.6 C.7 D.8 二、填空题（每空 1 分，共 26 分）1.通常从四个方面评价算法的质量：_、_、_和_。2.一个算法的时间复杂度为 (n3+n2log2n+14n)/n2，其数量级表示为 _。3.假定一棵树的广义表表示为A（C，D（E，F，G） ，H（I，J） ） ，则树中所含的结点数为 _个，树的深度为 _ ，树的度为 _。4.后缀算式 9 2 3 +- 10 2 / -的值为 _ 。中缀算式（

5、 3+4X）-2Y/3 对应的后缀算式为 _ 。5.若用链表存储一棵二叉树时， 每个结点除数据域外， 还有指向左孩子和右孩子的两个指针。在这种存储结构中，n 个结点的二叉树共有 _个指针域，其中有 _个指针域是存放了地址，有_ 个指针是空指针。6.对于一个具有 n 个顶点和 e 条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有 _个和_个。7.AOV 网是一种 _ 的图。8.在一个具有 n 个顶点的无向完全图中，包含有_条边，在一个具有 n个顶点的有向完全图中，包含有_条边。9.假定一个线性表为 (12,23,74,55,63,40) ，若按 Key % 4 条件进行划分， 使得同一

6、 余 数 的 元 素 成 为 一 个 子 表 ， 则 得 到 的 四 个 子 表 分 别 为_、_、_ 和_ 。10. 向一棵 B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度 _ 。11. 在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为_，整个堆排序过程的时间复杂度为_。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 23 页第 4 页 共 23 页12. 在快速排序、堆排序、归并排序中，_排序是稳定的。三、运算题（每题6 分，共 24 分）1.在如下数组 A 中链接存储了一个线性表，表头指针为A 0.n

7、ext，试写出该线性表。A 0 1 2 3 4 5 6 7 data 60 50 78 90 34 40 next 3 5 7 2 0 4 1 2.请画出图 10 的邻接矩阵和邻接表。3. 已 知 一 个 图 的 顶 点 集V和 边 集E分 别 为 ：V=1,2,3,4,5,6,7; E=(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18, (6,7)25; 用克鲁斯卡尔算法得到最小生成树， 试写出在最小生成树中依次得到的各条边。4.画出向小根堆中加入数据4, 2, 5, 8, 3时

8、，每加入一个数据后堆的变化。图 10 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 23 页第 5 页 共 23 页四、阅读算法（每题7 分，共 14分）1.LinkList mynote(LinkList L) /L 是不带头结点的单链表的头指针if(L&L-next) q=L；L=Lnext；p=L；S1：while(pnext) p=pnext；S2：pnext=q；qnext=NULL ；return L； 请回答下列问题：（1）说明语句 S1的功能；（2）说明语句组 S2的功能；（3）设链表表示的线性表为（a1,a2, ,a

9、n）,写出算法执行后的返回值所表示的线性表。2.void ABC(BTNode * BT) if BT ABC (BT-left); ABC (BT-right); coutdatadata) item=BST-data;/查找成功return _; else if(itemdata) return Find(_,item); else return Find(_,item); /if 六、编写算法（共 8 分）统计出单链表 HL 中结点的值等于给定值X 的结点数。int CountX(LNode* HL,ElemType x) 精选学习资料 - - - - - - - - - 名师归纳总结

10、- - - - - - -第 6 页，共 23 页第 7 页 共 23 页试题 1 答案一、单选题（每题2 分，共 20 分）1.A 2.D 3.D 4.C 5.C 6.D 7.D 8.C 9.D 10.A 二、填空题（每空1 分，共 26 分）1.正确性易读性强壮性高效率2.O(n) 3.9 3 3 4.-1 3 4 X * + 2 Y * 3 / - 5.2n n-1 n+1 6.e 2e 7.有向无回路8.n(n-1)/2 n(n-1) 9.（12，40）（）（74）（23,55，63）10. 增加 1 11. O(log2n) O(nlog2n) 12. 归并三、运算题（每题6 分，共

11、 24 分）1.线性表为：（78，50，40，60，34，90）2.邻接矩阵：0111010101110111010101110邻接表如图11 所示：图 11 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 23 页第 8 页 共 23 页3.用克鲁斯卡尔算法得到的最小生成树为：(1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20 4.见图 12 图 12 四、阅读算法（每题7 分，共 14 分）1.（1）查询链表的尾结点（ 2）将第一个结点链接到链表的尾部，作为新的尾结点（ 3）返回的线性表

12、为（a2,a3,an,a1）2.递归地后序遍历链式存储的二叉树。五、算法填空（每空2 分，共 8 分）true BST-left BST-right 六、编写算法（ 8 分）int CountX(LNode* HL,ElemType x) int i=0; LNode* p=HL;/i为计数器while(p!=NULL) if (P-data=x) i+; p=p-next; /while, 出循环时i 中的值即为x 结点个数return i; /CountX 4 4 4 4 4 2 2 2 5 5 5 2 2 8 8 4 3 5 2 8 3 4 精选学习资料 - - - - - - - -

13、- 名师归纳总结 - - - - - - -第 8 页，共 23 页第 9 页 共 23 页数据结构期末考试试题及答案2一、单选题（每小题2 分，共 8 分）1、在一个长度为n 的顺序线性表中顺序查找值为x 的元素时，查找成功时的平均查找长度 （即 x 与元素的平均比较次数， 假定查找每个元素的概率都相等）为( )。A n B n/2 C (n+1)/2 D (n-1)/2 2、 在一个单链表中 ,若 q 所指结点是 p 所指结点的前驱结点 ,若在 q 与 p 之间插入一个 s 所指的结点 ,则执行 ( )。A slink=p link; plink=s; B plink=s; slink=q

14、; C plink=slink; slink=p; D q link=s; slink =p; 3、栈的插入和删除操作在（）进行。A 栈顶B 栈底C 任意位置D 指定位置4、由权值分别为 11，8，6，2，5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）A 24 B 71 C 48 D 53 二、填空题（每空 1 分，共 32 分）1、 数据的逻辑结构被分为 _、_ 、 _和_四种。2、一种抽象数据类型包括_ 和_ 两个部分。3、在下面的数组 a中链接存储着一个线性表， 表头指针为 ao.next，则该线性表为 _。0 1 2 3 4 5 6 7 8 data next 4、在以 HL

15、为表头指针的带表头附加结点的单链表和循环单链表中，判断链表为空的条件分别为 _ 和_ 。5、用具有 n 个元素的一维数组存储一个循环队列，则其队首指针总是指向队首元素的 _ ，该循环队列的最大长度为_。60 56 42 38 74 25 4 3 7 6 2 0 1 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 23 页第 10 页 共 23 页6、当堆栈采用顺序存储结构时，栈顶元素的值可用 表示；当堆栈采用链接存储结构时，栈顶元素的值可用_ 表示。7、一棵高度为 5 的二叉树中最少含有 _个结点，最多含有 _个结点；一棵高度为5 的理

16、想平衡树中，最少含有_个结点，最多含有_个结点。8、在图的邻接表中，每个结点被称为_ ，通常它包含三个域：一是_ ；二是 _ ；三是 _ 。9、在一个索引文件的索引表中，每个索引项包含对应记录的_和_ 两项数据。10、假定一棵树的广义表表示为A（B（C，D（E，F，G） ，H（I，J） ） ） ，则树 中所 含的结点数为_个，树的深度为_,树的度为_, 结点 H 的双亲结点为 _, 孩子结点为 _ 。11、在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为_,整个堆排序过程的时间复杂度为_ 。12、 在对 m 阶的 B_树插入元素的过程中， 每向一个结点插入一个索引项 （叶子结点中的索引

17、项为关键字和空指针）后，若该结点的索引项数等于_个，则必须把它分裂为 _个结点。三、运算题（每小题6 分，共 24 分）1、已知一组记录的排序码为（46，79，56，38，40，80, 95，24） ，写出对其进行快速排序的每一次划分结果。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 23 页第 11 页 共 23 页2、一个线性表为B=（12，23，45，57，20，03，78，31，15，36） ，设散列表为 HT0.12，散列函数为 H（key）= key % 13 并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找

18、成功的平均查找长度。3、已知一棵二叉树的前序遍历的结果序列是ABECKFGHIJ，中序遍历的结果是 EBCDAFHIGJ ，试写出这棵二叉树的后序遍历结果。4、已知一个图的顶点集V 各边集 G 如下：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出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历等到的顶点序列。假定每个顶点邻

19、接表中的结点是按顶点序号从大到小的次序链接的。四、阅读算法，回答问题（每小题8 分，共 16 分）1、假定从键盘上输入一批整数，依次为：78 63 45 30 91 34 1，请写出输出结果。# include # include const int stackmaxsize = 30; typedef int elemtype; struct stack elemtype stack stackmaxsize; 图深度优先序列广度优先序列邻接矩阵表示时邻接表表示时精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 23 页第 12 页

20、共 23 页int top; ; # include “stack.h”void main ( ) stack a; initstack(a); int x; cin x; while (x! = -1) push (a, x ); cin x; while (!stackempty (a) cout pop (a) ” ” ; cout end1; 该算法的输出结果为：_ 2、阅读以下二叉树操作算法，指出该算法的功能。Template void BinTree ： ：unknown (BinTreeNode*t) BinTreeNode *p =t, *temp; if (p!=NULL)

21、temp = pleftchild; pleftchild = p rightchild; prightchild = temp; unknown(pleftchild); undnown(prightchild); 该算法的功能是： _ 五、算法填空，在画有横线的地方填写合适的内容（10 分）对顺序存储的有序表进行二分查找的递归算法。int Binsch( ElemType A ,int low ,int high,KeyType K ) if (low = high) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 23 页第 1

22、3 页 共 23 页int mid = 1 if ( K= = A mid .key ) return mid; else if ( K =0 ；i-) for(j=0 ；jnext; p-next= Q.front-next; （B） 、p=Q.front-next; Q.front-next=p-next; （C） 、p=Q.rear-next; p-next= Q.rear-next; （D） 、p=Q-next; Q-next=p-next; 9 Huffman 树的带权路径长度WPL等于（）（A） 、除根结点之外的所有结点权值之和（B） 、所有结点权值之和b c d a front

23、精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 16 页，共 23 页第 17 页 共 23 页（C） 、各叶子结点的带权路径长度之和（D） 、根结点的值10线索二叉链表是利用（）域存储后继结点的地址。（A） 、lchild （B） 、data （C） 、rchild （D） 、root 二、填空题1逻辑结构决定了算法的，而存储结构决定了算法的。2栈和队列都是一种的线性表，栈的插入和删除只能在进行。3线性表（ a1,a2, ,an）的顺序存储结构中，设每个单元的长度为L，元素ai的存储地址LOC(ai) 为4已知一双向链表如下( 指针域名为next

24、 和 prior)：q p 现将 p 所指的结点插入到x和y结点之间，其操作步骤为：；5n 个结点无向完全图的的边数为， n个结点的生成树的边数为。6已知一有向无环图如下：任意写出二种拓扑排序序列：、。7已知二叉树的中序遍历序列为BCA ，后序遍历序列为CBA ，则该二叉树的先序遍历序列为，层序遍历序列为。三、应用题1设散列函数H(k)=k % 13, 设关键字系列为22,12,24,6,45,7,8,13,21,要求用线性探测法处理冲突。 (6 分) (1) 构造 HASH 表。(2) 分别求查找成功和不成功时的平均查找长度。x ye B ACDFEG精选学习资料 - - - - - - -

25、 - - 名师归纳总结 - - - - - - -第 17 页，共 23 页第 18 页 共 23 页2 给定表（ 19,14,22,15,20,21,56,10） . （8 分）（1）按元素在表中的次序，建立一棵二叉排序树（2）对(1) 中所建立的二叉排序树进行中序遍历，写出遍历序列。（3）画出对 (2) 中的遍历序列进行折半查找过程的判定树。3 已知二个稀疏矩阵A和 B的压缩存储三元组表如下： A B i j V i j V 1 3 -5 2 5 2 2 4 6 3 3 7 2 5 2 4 1 3 4 2 -1 5 2 -9 5 2 9 5 5 8 写出 A-B 压缩存储的三元组表。 （5

26、 分）4 已知一维数组中的数据为（18,12,25,53,18）, 试写出插入排序（升序）过程。并指出具有 n 个元素的插入排序的时间复杂度是多少？(5 分 ) 5 已知一网络的邻接矩阵如下，求从顶点A开始的最小生成树。(8 分，要有过程) A B C D E F （1）求从顶点A开始的最小生成树。64266346751275356156FEDCBA精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 18 页，共 23 页第 19 页 共 23 页（2）分别画出以A为起点的DFS生成树和BFS生成树。6已知数据六个字母及在通信中出现频率如下表：A B

27、C D E F 0.15 0.15 0.1 0.1 0.2 0.3 把这些字母和频率作为叶子结点及权值，完成如下工作(7 分，要有过程 ) 。（1）画出对应的Huffman 树。（2）计算带权路径长度WPL 。（3）求 A、B、C、D、E、 F的 Huffman 编码。7 已知有如下的有向网：求顶点 A到其它各顶点的最短路径（采用Dijkstra算法，要有过程） 。 （6 分）四、设计题（30 分，每题 10 分, 用 C语言写出算法，做在答题纸上）1 已知线性表（ a1,a2, ,an）以顺序存储结构为存储结构，其类型定义如下：#define LIST_INIT_SIZE 100 /顺序表初

28、始分配容量typedef struct Elemtype *elem; /顺序存储空间基址int length; /当前长度（存储元素个数）SqList; 设计一个算法，删除其元素值为x 的结点（假若x 是唯一的）。并求出其算法的平均时间复杂度。其算法函数头部如下：2 5 3 6 4 10 6 1 2 2 A B C D E 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 19 页，共 23 页第 20 页 共 23 页 S tatus ListDelete(Sqlist &L,Elemtype x) 2设顺序栈如左图所示。其中结点定义如下：top

29、 typedef struct Elemtype *base; /栈底指针Elemtype *top; /栈顶指针Stack; 设计算法，将栈顶元素出栈并存入e 中base 3设二叉链树的类型定义如下：typedef int Elemtype; typedef struct node Elemtype data; struct node *lchild, *rchild; BinNode, *BinTree; 试写出求该二叉树叶子结点数的算法: S tatus CountLeaves(BinTree &root,int &n) /n is the number of leaves ana2a1

30、精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 20 页，共 23 页第 21 页 共 23 页试题 3 答案一、选择题（每题1 分）1、C 2、D 3、 A 4、D 5、C 6、D 7、A 8、B 9、C 10、C 二、填空题1设计、实现2特殊、栈顶3LOC （a1）+(i-1)*L 4p-next=q-next;q-next-prior=p; q-next=p;p-prior=q;5n(n-1)/2 、n-1 6ADCBFEG 、ABCDEFFG 7ABC 、ABC 三、应用题1. （1） Hash表（ 4分）地址0 1 2 3 4 5 6 7

31、 8 9 10 11 12 关键安13 21 6 45 7 22 8 24 12 探测次数1 7 1 2 3 1 3 1 1 （2）查找成功的平均查找长度：（1 分）（5*1+1*2+2*3+1*7） /9=20/9 查找不成功的平均查找长度：（1 分）（ 2+1+9+8+7+6+5+4+3+2+1 ） /13= 2.（1） 、构造（ 3 分）(2)、10 14 15 19 20 21 22 56（2 分）（3） 、（3 分）3、(5 分，每行0.5) i j v 1 3 -5 2 4 6 3 3 7 4 1 3 19 14 22 10 15 20 56 21 精选学习资料 - - - - -

32、 - - - - 名师归纳总结 - - - - - - -第 21 页，共 23 页第 22 页 共 23 页4 2 -1 5 2 18 5 5 8 4、初始关键字：18 12 25 53 18 第一趟： 12 18 25 53 18 第二趟： 12 18 25 53 18 第三趟： 12 18 25 53 18 第四趟： 12 18 18 25 53 （4 分）O（n2） （ 1分） 。5、7 分（1）4 分（2）4 分6、(1) 3 分（2）WPL=0.1*3+0.1*3+0.2*2+0.15*3+0.15*3+03*21= (1 分) （3）A：010 B： 011 C：110 D：11

33、1 E： 00 F；10 （ 3 分）7、A-B ： （A、B）1 分A-C ： （A、D、C） 2 分A-D ： （A、D）1 分A-E： （A、D、E）2 分A B 1 C 3 2 5 D 4 E F E F A B C D 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 22 页，共 23 页第 23 页 共 23 页四、设计题（ 30 分）1、(10 分) Status ListDelete(Sqlist &L,ElemType x) int i,j; for(i=0;ilength;i+) if(L-elemi=x) break; if(

34、i=L-length) return ERROR; for(j=i;jlengthi-1;j+) L-elemj=L-elemj+1; L-length-; （8 分）平均时间复杂度： （2 分）设元素个数记为n，则平均时间复杂度为：nininnE121)(12、 （ 10 分）void pop(Stack &S, Elemtype &e) if(S.top=S.base) return ERROR; S.top-; e=*s.top; 3、 （ 10 分）voidCountLeaves(BinTree T,int &n) if(T) if(!(T-lchild)&!( T-rchild) n+; CountLeaves (T-lchild,n); CountLeaves (T-rchild,n); 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 23 页，共 23 页