2022年数据结构试题试卷二含答案参照 .pdf

模拟试题二模拟试题二一、选择题（ 28 分） 1.设一数列的顺序为l ，2， 3，4，5，通过栈结构不可能排成的顺序数列为( )。 A)3,2,5,4,l B)1,5,4,2,3 C)2,4,3,5,l D)4,5,3,2,l 2.二叉树的第3 层最少有 ( )个结点。 A)0 B)1 C)2 D)3 3.-个 n 个顶点的连通无向图，其边的个数至少为( )。 A) n-l B)n C) n+l D) nlogn 4.下列排序方法中，( )的比较次数与记录的初始排列状态无关。 A)直接插入排序 B）起泡排序 C)快速排序 D）直接选择排序 5.-棵哈夫曼树总共有II 个结点，则叶子结点有( )个。 A)5 B)6 C)7 D)9 6.已知某算法的执行时间为(n+n2)+log2(n+2) ，n 为问题规模，则该算法的时间复杂度是 ( )。 A)O(n) B) O(n2) C) O(log2n) D) O(nlog2n) 7.如果一棵树有10 个叶子结点，则该树总共至少有( )个结点。 A) lO B) 11 C) 19 D) 21 8.-个 100 100 的三角矩阵a 采用行优先压缩存储后，如果首元素a00是第一个元素，那么 a42是第 ( )个元素。 A)13 B) 401 C) 402 D) 403 9.有一棵二叉树如题图1，该树是 ( )。 A)二叉平衡树 B）二叉排序树 C)堆的形状 D）以上都不是 10.对于含有 n 个顶点 e 条边的无向连通图，利用 Prim 算法生成最小代价生成树，其时间复杂度为 ( )，利用 Kruska 算法的时间复杂度为( )。 A) O(log2n) B)0(n2) C)O(ne) D)O(elog2ne) 11.具有 n 个顶点的完全有向图的边数为( )。 A)n(n-l)/2 B)n(n-l) C) n2 D) n2-1 12.设有 100 个元素，用折半查找时，最大比较次数为( )，最小比较次数为( )。 A) 25 B)7 C) 10 D)l 13.在内部排序中，排序时不稳定的有( )。 A)插入排序 B）冒泡排序 C）快速排序 D）归并排序 14.串是一种特殊的线性表，其特殊性体现在( )。 A)可以顺序存储 B）数据元素是一个字符 C)可以链接存储 D）数据元素可以是多个字符名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 6 页 - - - - - - - - - 二、填空题（30 分） 1.对于一个以顺序实现的循环队列QOm-1 ，队首、队尾指针分别为f 和 r ，其判空的条件是 _，判满的条件是_。 2.具有 64 个结点的完全二叉树的深度为_。 3.给定一个整数集合3 ，5，6，9，12），画出其对应的一棵哈夫曼树_。 4.如果指针p 指向一棵二叉树的一个结点，则判断p 没有左孩子的逻辑表达式为_。 5.下面为朴素的模式匹配算法，请在算法的下划线处填上正确的子句。 int index (String*s, String*t) String *S, *t; i=j=O; while（ ilen)&（jlen） if(s-ch i =t-chj) i=i+1： j=j+l; else i=_; j=_; if（j =t-len） return（i-t-len）; else return（-1 ） ; 6.-个 nxn 的对称矩阵，如果以行或列为主序存入内存，则其容量为_。 7.设 F是森林， B是由 F 转换得到的二叉树，F 中有 n 个非终端结点，B中右指针域为空的结点有 _。 8.先序序列和中序序列相同的二叉树为_。 9.已知一棵二叉树的中序遍历结果为DBHEAFICG ，后序遍历结果为DHEBIFGCA ，画出该二叉树 _。 lO.在进行直接插入排序时，其数据比较次数与数据的初始排列_关 ; 而在进行直接选择排序时，其数据比较次数与数据的初始排列_关。 II. 一个连通图的生成树是该图的连通子图。 若这个连通图有n 个顶点， 则它的生成树有 _条边。三、应用题（12 分） 1.设散列表的地址空间为0 16; ，开始时散列表为空，用线性探测开放地址法处理冲突，对于数据元素Jan，Feb，Mar，Jun，Aug，Sep，Oct，Nov，Dec，试构造其对应的散列表，H(key)=|_i/2_|，其中 i 为关键字中第一个字母在字母表中的序号。求搜索成功的平均搜索长度。 2.设有 5000 个无序的元素， 希望用最快的速度挑选出其中前10 个最大的元素， 在快速排序、堆排序和基数排序方法中，采用哪种方法最好？为什么？ 3.对于题图2，试给出： (1)每个顶点的入度和出度。 (2)邻接矩阵。 (3)逆邻接表。 (4)强连通分量。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 6 页 - - - - - - - - - 四、算法设计 (30 分 ) 1.有一个带首结点的单链表，编写在值为x 的结点之后插入m个结点的算法。 2.设计一个算法，求出指定结点在给定的二叉排序树中所在的层次。3.设计一个算法，建立无向图（n 个顶点， e 条边）的邻接表模拟试题二答案模拟试题二参考答案一、选择题1.B 2.A 3.A 4.D 5.B 6.B 7.B 8.D 9.B10.B 11.A 12.D 13.C 14.D 二、填空题 1.Ff， (r+l)% m=f 2. 7 3. 4.p-lchild=Null 5.i-j-l,0 6.n(n+l)/2 7.n+l 8.单右子树二叉树或孤立结点 9. 10.有，无 11.极小， n-l 三、应用题 1.使用散列函数H(key) =Li/21，有： H(Jan)=5, H(Feb)=3, H(Mar)=6, H(Jun)=5, H(Aug)=0, H(Sep)=8, H(Oct)=7, H(Nov)=7, H(Dec)=2 (l)利用线性探测开放地址法造表：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 6 页 - - - - - - - - - (2)搜索成功的平均搜索长度为： ASLsucc=(1+5+1+ 1+6+ 1+1+1+1)=2 2.从平均时间性能而言，快速排序最佳，所需时间最省O(nlogn) ，但在最坏情况下的时间性能为 O(VI2) 不如堆排序O(nlogn) 。基数排序最适合n 值较大而关键字较小的序列。一般来讲，当 n 比较大且要选的数据knext; while (p！=NULL p-data l=x) p=p-next; if (p=NULL) printf (%f x not foundn,x); else q=p-next; for(i=1;idata=b; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 6 页 - - - - - - - - - p-next=s; p=s; p-next=q; return head; 2.求指定结点在给定的二叉排序树中所在的层次的算法： void level (bitree *t, bitree *p, int h,int k) /*t为二叉树的指针，p 为待找的结点，h 为 p 结点的层数，k 为当前的层数 */ if (t=NULL) h=0; else if(p=t) h=k; /找到指定结点*p else level (p, -lchild,h，k+l); /在左子树中查找 if（h=-1） level (p, t-rchild,h，k+l); /在右子树中查找 3.建立无向图（n个顶点， e 条边）的邻接表的算法： #include #include #define Maxver n /*定义图的最大顶点数*/ #define MaxEdge e /*定义图的最大边数+/ typedef int Vertextype; /*定义顶点的数据类型*/ typedef int Vertextype vexlist Maxver; /*vexlist为存储顶点的数组*/ struct edgenode /*定义邻接表的边结点类型*/ int adjvex; /*邻接点域 */ struct edgenode *next; ; typedef struct edgenode *adjlist Maxver;/*定义adj list为存储表头指针的数组 */ void create (vexlist GV, adj list GL, int n，int e) /*从键盘输入n 和 e*/ int i，j ， k printf(”输入 %d个顶点数据n”， n); /*建立顶点数组 */ for (i=0;in; i+)scanf( ood, &GVi); for (i=0; in; i+) GVi =NULL; printf（ 输入 ood 条无向无权边n ，e）; /*建立邻接表 */ for (k=1;kadjvex=j; /*将 j 的值赋给新结点的邻接点域*/ p-next=GL i; GLi=p; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 6 页 - - - - - - - - - p=malloc (sizeof( struct edgenode); /*再分配新结点 */ p-adj vex=i; /*将 i 的值赋给新结点的邻接点域*/ p-next=GLj; GLj=p; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 6 页 - - - - - - - - -