2022年数据结构试题 2.pdf
数据结构试题一、选择题（每小题 2分，共30分）1 若某线性表中最常用的操作是取第i 个元素和找第 i 个元素的前趋元素，则采用（ ）存储方式最节省时间。A、单链表 B、双链表 C、单向循环 D、顺序表2 串是任意有限个（ ）A、符号构成的序列 B、符号构成的集合C 、字符构成的序列 D、字符构成的集合3 设矩阵A（aij ，l i,j 10 ）的元素满足：aij 0(i j, li, j 10)aij=0 (ij, li, j 10)现将A的所有非 0元素以行序为主序存放在首地址为2000的存储区域中，每个元素占有 4个单元，则元素 A95的首址为A、2340 B、2336 C、2164 D、21604 如果以链表作为栈的存储结构，则退栈操作时（ ）A、 必须判别栈是否满B、 对栈不作任何判别C 、 必须判别栈是否空D 、 判别栈元素的类型5 设数组Data0.m 作为循环队列 SQ 的存储空间， front 为队头指针，rear 为队尾指针，则执行出队操作的语句为（ ）A、front=front+1 B、front=(front+1)% mC 、rear=(rear+1)%m D 、front=(front+1)%(m+1)6 深度为6（根的层次为 1）的二叉树至多有（ ）结点。A、 64 B 、32 C、31 D、637 将含100个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号，根结点的编号为1。编号为 49的结点X的双亲编号为（）A、24 B、25 C、23 D、无法确定8 设有一个无向图 G= （V，E）和G =（V，E）如果 G 为G 的生成树，则下面不正确的说法是（ ）A、G 为G 的子图 B、G 为G 的边通分量C 、G 为G 的极小连通子图且 V=V D、G 为G 的一个无环子图9 用线性探测法查找闭散列表，可能要探测多个散列地址，这些位置上的键值（ ）A、 一定都是同义词 B、一定都不是同义词C 、都相同 D、不一定都是同义词名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 6 页 - - - - - - - - - 10 二分查找要求被查找的表是（ ）A、 键值有序的链接表 B、链接表但键值不一定有序C 、 键值有序的顺序表 D、顺序表但键值不一定有序11 当初始序列已经按键值有序，用直接插入算法对其进行排序，需要循环的次数为（ ）A、n2 B、nlog2n C 、log2n D 、n-112 堆是一个键值序列 k1,k2, , kn,对i=1,2, ,|_n/2_|,满足( )A、ki k2i k2i+1 B 、kik2i+1k2iC 、ki k2i 且ki k2i+1(2i+1 n) D 、ki k2i 或ki k2i+1(2i+1 n)13一个具有 n个顶点的无向完全图的边数为（ ）A、n(n+1)/2 B 、n(n-1)/2 C、n(n-1) D 、n(n+1)14在索引顺序表中查找一个元素，可用的且最快的方法是（ ）A、用顺序查找法确定元素所在块，再用顺序查找法在相应块中查找B、用顺序查找法确定元素所在块，再用二分查找法在相应块中查找C 、用二分查找法确定元素所在块，再用顺序查找法在相应块中查找D 、用二分查找法确定元素所在块，再用二分查找法在相应块中查找15若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用（ ）存储方式最节省运算时间。A、 单链表 B、双链表C 、带头结点的双循环链表D 、容量足够大的顺序表二、判断题（每小题 1分，共10分）1双链表中至多只有一个结点的后继指针为空。（ ）2在循环队列中， front 指向队列中第一个元素的前一位置，rear 指向实际的队尾元素，队列为满的条件是front=rear。（ ）3对链表进行插入和删除操作时，不必移动结点。（ ）4栈可以作为实现程序设计语言过程调用时的一种数据结构。（ ）5在一个有向图的拓朴序列中，若顶点a在顶点b之前，则图中必有一条弧。( )i6对有向图 G ，如果从任一顶点出发进行一次深度优先或广度优先搜索就能访问每个顶点，则该图一定是完全图。( )7“顺序查找法”是指在顺序表上进行查找的方法。（ ）8向二叉排序树插入一个新结点时，新结点一定成为二叉排序树的一个叶子结点。（）9键值序列 A，C ，D ，E，F，E，F是一个堆。10二路归并时，被归并的两个子序列中的关键字个数一定要相等。（）三、填空题（每小题 2分，共20分）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 6 页 - - - - - - - - - 1在带有头结点的单链表 L中，若要删除第一个结点，则需执行下列三条语句：；L-next=U-next ；free(U) ；2有一个长度为 20的有序表采用二分查找方法进行查找，共有个元素的查找长度为3。3采用冒泡排序对有 n个记录的表 A按键值递增排序，若 L的初始状态是按键值递增，则排序过程中记录的比较次数为。若A的初始状态为递减排列，则记录的交换次数为。4在无头结点的双链表中，指针P所指结点是第一个结点的条件是。5G 为无向图，如果从 G 的某个顶点出发，进行一次广度优先搜索，即可访问图的每个顶点，则该图一定是图。6如果一个有向图中没有，则该图的全部顶点可能排成一个拓扑序列。7深度为 8（根的层次号为 1）的满二叉树有个叶子结点。8将一棵有 100个结点的完全二叉树按层编号，则编号为49的结点X，其双亲PARENT（X）的编号为。9设某闭散列表 HT 未满，散列函数 H （KEY ）为键值第一字母在字母表中的序号，处理冲突方法为线性探测法，请在下列算法划线处填上适当内容，以实现按键值第一字母的顺序输出闭散列表中所有键值的算法。void printword(keytype HTm) for(i=1;idata=x; p-next=NULL ；四、简答题：（每小题 4分，共20分）1. 对于一个有 10000个结点的二叉树，树叶最多有多少个？最少有多少个？名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 6 页 - - - - - - - - - 2. 已知一棵二叉树的中序序列和后序序列分别为： DBGEACHF和DGEBHFCA，则该二叉树的前序序列是什么？3. 设有1000个无序的元素，需排出前 10个最大（小）的元素，你认为采用哪种排序方法最快？为什么？4. 在KMP 算法中，已知模式串为 ADABCADADA ，请写出模式串的 nextj函数值。5. 中序遍历的递归算法平均空间复杂度为多少？五、 算法设计题（每小题 10分，共20分）1. 试编写一个算法，判断一给定的整型数组an 是不是一个堆。2. 一棵二叉树的繁茂度定义为各层结点数的最大值与树的高度的乘积。试写一高效算法，求二叉树的繁茂度。参考答案一、选择题1、D 2、C 3、D 4、C 5、D 6、D 7、A 8、B 9、D 10、C 11、D 12、C13、B14、C 15、D 二、判断题1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 三、填空题1U=L - next24。3n-1、n(n-1)/2 。4p - prior = NULL。5连通6回路或环728-1 = 27 = 1288249HTj!=NULL 或HTj 不为空、 H(HTj)=I10rear - next = p、rear = p四、简答题：1. 答： 最多是完全二叉树的形态，即5000个叶子；最少是单支树的形态，即1个叶子。2. 答：是： ABDEGCFH3. 答：用锦标赛排序或堆排序很合适，因为不必等全部元素排完就能得到所需结果，时间效率为 O(nlog2n) ； 即O （1000log21000）=O(10000)锦标赛排序的准确比较次数为：n-1+9log2n=999+9log21000=999+9 10=1089名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 6 页 - - - - - - - - - 堆排序的准确比较次数为：n-1+9log2n=999+9log21000=999+9 10=1089若用冒泡排序也较快，最多耗费比较次数为（n-1+n-2+ n-10）=10n-55=10000-55=9945（次）4. 答： 01121123435. 答： 要考虑递归时占用了栈空间，但递归次数最多不超过树的高度，所以空间复杂度为 O(log2n)五、 算法设计题1. 解：提示：堆的定义是：kik2i和K2i 1void SortA(sqlist &A, int n) if(n=0) return(0); /空表if (a1a2) for( i=1; ia2*i|aia2*i+1)return(-1);return(minleap);else for( i=1; i=n/2; i+) if (aia2*i| ailchild) EnQueue(Q,r.node-lchild, r.layer+1);if(r.node-rchild) EnQueue(Q,r.node-rchild, r.layer+1);名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 6 页 - - - - - - - - - /按层序入队时要随时标注结点所在层号h=r.layer; /最后一个队列元素所在层就是树的高度for(maxn=count0, i=1; h; i+)if(countimaxn) maxn=counti; /求出哪一层结点数最多return (h*maxn) / Width名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 6 页 - - - - - - - - -
