下载文档原格式
《数据结构与算法》一、选择题1. 组成数据的基本单位是( )。
(A) 数据项 (B)数据类型 (C)数据元素 (D)数据变量2. 线性表的链接实现有利于( )运算。
(A) 插入 (B)读表元 (C)查找 (D)定位3. 串的逻辑结构与( )的逻辑结构不同。
(A) 线性表 (B)栈 (C)队列 (D)树4. 二叉树第i（i≥1）层最多有( )个结点。
(A) 2i (B)2i (C) 2i-1 (D) 2i-15. 设单链表中指针p指向结点A，若要删除A后结点（若存在），则需要修改指针的操作为( )(A) p->next = p->next->next (B)p=p->next(C)p=p->next->next (D)p->next=p6、栈和队列的共同特点是( )。
(A)只允许在端点处插入和删除元素 (B)都是先进后出(C)都是先进先出 (D)没有共同点7、二叉树的第k层的结点数最多为( ).(A)2k+1 (B)2K+1 (C)2K-1(D) 2k-18、设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（）。
(A) BADC (B) BCDA (C) CDAB (D) CBDA9、设某完全无向图中有n个顶点，则该完全无向图中有（）条边。
(A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-110、下面程序的时间复杂为（）for（i=1,s=0; i<=n; i++）{t=1;for(j=1;j<=i;j++)t=t*j;s=s+t;}(A) O(n) (B) O(n2) (C) O(nlog2n) (D) O(n3)11、设某强连通图中有n个顶点，则该强连通图中至少有（）条边。
(A) n(n-1) (B) n+1 (C) n (D) n(n+1)12、设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（）条有向边。
数据结构与算法试题+答案一、单选题（共86题，每题1分，共86分）1.栈和队列的共同点是（）。
A、只允许在端点处插入和删除元素B、都是先进后出C、都是先进先出D、没有共同点正确答案：A2.数据元素在计算机存储器内表示时，物理相对位置和逻辑相对位置相同并且是连续的，称之为（）。
A、逻辑结构B、顺序存储结构C、链式存储结构D、以上都不对正确答案：B3.假设我们只有2条磁带Ta和Tb用于做外部排序。
假设内存可以一次处理M条记录。
初始状态下Ta上存有N条记录。
下列简单算法的执行步骤为：第1步：从Ta一次读入M条记录到内存，做内部排序，然后将有序的结果写到Tb。
第2步：从Ta一次读入M条记录到内存，做内部排序，然后将其与Tb上存储的有序列做归并，将有序的（2M条记录）结果写到Ta。
第3步：从Ta一次读入M条记录到内存，做内部排序，然后将其与Tb上存储的2M条记录的有序列做归并，将有序的（3M条记录）结果写到Tb。
重复第2、3步，直到全部记录有序。
上述算法需要执行__轮。
A、⌈N/M⌉B、logNC、⌈log(N/M)⌉D、logMN正确答案：A4.对任意给定的含 n (n>2) 个字符的有限集 S，用二叉树表示 S 的哈夫曼编码集和定长编码集，分别得到二叉树 T1 和 T2。
下列叙述中，正确的是：A、出现频次不同的字符在 T2 中处于相同的层B、出现频次不同的字符在 T1 中处于不同的层C、T1 与 T2 的结点数相同D、T1 的高度大于 T2 的高度正确答案：A5.对初始数据序列{ 8, 3, 9, 11, 2, 1, 4, 7, 5, 10, 6 }进行希尔排序。
若第一趟排序结果为（ 1, 3, 7, 5, 2, 6, 4, 9, 11, 10, 8 ），第二趟排序结果为（ 1, 2, 6, 4, 3, 7, 5, 8, 11, 10, 9 ），则两趟排序采用的增量（间隔）依次是：A、3, 1B、5, 2C、3, 2D、5, 3正确答案：D6.从一个具有N个结点的单链表中查找其值等于X的结点时，在查找成功的情况下，需平均比较多少个结点？A、N/2B、(N+1)/2C、ND、(N−1)/2正确答案：B7.下面代码段的时间复杂度是（）。
数据结构与算法复习题库含答案1. 问题描述：给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
答案：可以使用哈希表来解决此问题。
首先初始化一个空的哈希表，然后遍历数组中的每个元素。
对于每个元素，首先计算目标值与当前元素的差值，然后在哈希表中查找该差值。
如果找到了该差值，则说明存在两个数的和等于目标值，返回这两个数的下标；否则，将当前元素插入到哈希表中。
时间复杂度为O(n)，其中n为数组的长度。
2. 问题描述：给定一个字符串，找出其中不含重复字符的最长子串的长度。
答案：可以使用滑动窗口来解决此问题。
维护一个窗口，其中包含没有重复字符的子串。
遍历字符串中的每个字符，如果该字符不在窗口中，将其加入窗口；如果该字符在窗口中，移动窗口的左边界直到窗口中不包含重复字符。
记录窗口的最大长度。
时间复杂度为O(n)，其中n为字符串的长度。
3. 问题描述：给定一个字符串和一个单词列表，找出字符串中可以由单词列表中的单词组成的所有子串的起始位置。
答案：可以使用滑动窗口和哈希表来解决此问题。
首先统计单词列表中每个单词的出现次数。
然后遍历字符串中的每个位置作为子串的起始位置，维护一个滑动窗口。
在窗口中依次取出长度和单词列表中单词总长度相等的子串，在哈希表中统计子串中每个单词出现的次数。
如果窗口中的子串与单词列表中的单词出现次数一致，则记录该子串的起始位置。
时间复杂度为O(n*m)，其中n为字符串的长度，m为单词列表中的单词个数。
4. 问题描述：给定一个无序的整数数组，找出其中缺失的第一个正整数。
答案：可以使用原地哈希表来解决此问题。
遍历数组中的每个元素，将每个正整数放到数组中对应的位置上。
遍历数组中的每个元素，如果该位置上的数不等于数组索引加一，则该索引加一即为缺失的第一个正整数。
时间复杂度为O(n)，其中n为数组的长度。
5. 问题描述：给定一个字符串s，找到s中最长的回文子串。
答案：可以使用动态规划来解决此问题。
数据结构复习题第一章概论一、选择题1、研究数据结构就是研究( D )。
A. 数据的逻辑结构B. 数据的存储结构C. 数据的逻辑结构和存储结构D. 数据的逻辑结构、存储结构及其基本操作2、算法分析的两个主要方面是( A )。
A. 空间复杂度和时间复杂度 B. 正确性和简单性C. 可读性和文档性 D. 数据复杂性和程序复杂性3、具有线性结构的数据结构是( D )。
A. 图B. 树C. 广义表D. 栈4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、( B )等5个特性。
A. 可执行性、可移植性和可扩充性B. 可执行性、有穷性和确定性C. 确定性、有穷性和稳定性D. 易读性、稳定性和确定性5、下面程序段的时间复杂度是( C )。
fori0;im;i++forj0;jn;j++a[i][j]i*j;A. Om2B. On2C. Om*nD. Om+n6、算法是( D )。
A. 计算机程序B. 解决问题的计算方法C. 排序算法D. 解决问题的有限运算序列7、某算法的语句执行频度为(3n+nlog2n+n2+8),其时间复杂度表示( C )。
A. OnB. Onlog2nC. On2D. Olog2n8、下面程序段的时间复杂度为( C )。
i1;whileinii*3;A. OnB. O3nC. Olog3nD. On39、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的( B )和运算等的学科。
A. 结构B. 关系C. 运算D. 算法10、下面程序段的时间复杂度是( A )。
is0;whilesni++;s+i;A. OnB. On2C. Olog2nD. On311、抽象数据类型的三个组成部分分别为( A )。
A. 数据对象、数据关系和基本操作B. 数据元素、逻辑结构和存储结构C. 数据项、数据元素和数据类型D. 数据元素、数据结构和数据类型12、通常从正确性、易读性、健壮性、高效性等4个方面评价算法的质量,以下解释错误的是(D)。
可编辑修改精选全文完整版《数据结构与算法》复习题一、选择题。
1．在数据结构中，从逻辑上可以把数据结构分为 C 。
C．线性结构和非线性结构2．数据结构在计算机内存中的表示是指 A 。
A．数据的存储结构3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。
A．逻辑4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。
C．数据元素之间的关系5．在决定选取何种存储结构时，一般不考虑 A 。
A．各结点的值如何6．以下说法正确的是 D 。
D．一些表面上很不相同的数据可以有相同的逻辑结构7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。
（1）C．分析算法的效率以求改进（2）A．空间复杂度和时间复杂度8．下面程序段的时间复杂度是O(n2) 。
s =0;for( I =0; i<n; i++)for(j=0;j<n;j++)s +=B[i][j];sum = s ;9．下面程序段的时间复杂度是O(n*m) 。
for( i =0; i<n; i++)for(j=0;j<m;j++)A[i][j] ＝0;10．下面程序段的时间复杂度是O(log3n) 。
i ＝0；while（i<=n）i = i * 3；11．在以下的叙述中，正确的是 B 。
B．二维数组是其数据元素为线性表的线性表12．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 B 。
B．不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致13．链表不具备的特点是 A 。
A．可随机访问任一结点14．不带头结点的单链表head为空的判定条件是 A 。
A．head == NULL15．带头结点的单链表head为空的判定条件是 B 。
B head->next ==NULL16．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用D 存储方式最节省运算时间。
数据结构与算法试题库及参考答案一、单选题（共100题，每题1分，共100分）1.循环队列的存储空间为 Q(1:50),初始状态为空。
经过一系列正常的入队与退队操作后，Front=25,rear=24。
此时该循环队列中的元素个数为A、25第 48 组B、50C、49D、1正确答案：C2.小梅想要了解当前 Excel 2010 文档中的工作表最多有多少行，最快捷的操作方法是：A、按下 Ctrl 键的同时连续按向下光标键↓，光标跳到工作表的最末一行，查看行号或名称框中的地址即可B、按 Ctrl+Shift+End 组合键，选择到最后一行单元格，查看行号或名称框中的地址即可C、操作工作表右侧的垂直滚动条，直到最后一行出现，查看行号即可D、选择整个工作表，通过查找和选择下的正确答案：A3.若将一幅图片以不同的文件格式保存，占用空间最大的图形文件格式是：A、BmpB、PngC、JpgD、Gif正确答案：A4.如果希望为一个多页的Word文档添加页面图片背景，最优的操作方法是：A、利用水印功能，将图片设置为文档水印。
B、执行“插入”选项卡中的“页面背景”命令，将图片设置为页面背景。
C、利用页面填充效果功能，将图片设置为页面背景。
D、在每一页中分别插入图片，并设置图片的环绕方式为衬于文字下方。
正确答案：C5.能够直接反映一台计算机的计算能力和精度的指标参数是：A、字符编码B、位C、字节D、字长正确答案：D6.在 PowerPoint 2010 中，要修改应用了某个主题的演示文稿中幻灯片编号的位置，最优的操作方法是：A、应用其他主题B、将每一张幻灯片中的幻灯片编号分别调整到所需要的位置C、在幻灯片母版中，将幻灯片编号调整到所需要的位置D、在特定的位置插入幻灯片编号第 30 组正确答案：C7.计算机中组织和存储信息的基本单位是：A、位B、字节C、字长D、编码正确答案：B8.不属于对象构成成份的是A、属性B、方法（或操作）C、标识第 33 组D、规则正确答案：D9.小张的毕业论文设置为 2 栏页面布局，现需在分栏之上插入一横跨两栏内容的论文标题，最优的操作方法是：A、在两栏内容之上插入一个艺术字标题。
数据结构与算法试题库（含参考答案）一、单选题（共86题，每题1分，共86分）1.在快速排序的一趟划分过程中，当遇到与基准数相等的元素时，如果左指针停止移动，而右指针在同样情况下却不停止移动，那么当所有元素都相等时，算法的时间复杂度是多少？A、O(N2)B、O(N)C、O(NlogN)D、O(logN)正确答案：A2.在一个不带头结点的非空链式队列中,假设f和r分别为队头和队尾指针,则插入s所指的结点运算是( )。
A、f->next=s; f=s;B、s->next=s; r=s;C、s->next=f; f=s;D、r->next=s; r=s;正确答案：D3.若借助堆栈将中缀表达式a+b*c+(d*e+f)*g转换为后缀表达式，当读入f时，堆栈里的内容是什么（按堆栈自底向上顺序）？A、++(+B、+(*+C、+(+D、abcde正确答案：C4.二叉树的高度若根节点为高度1，一棵具有 1025 个结点的二叉树的高度为▁▁▁▁▁ 。
A、11～1025 之间B、10～1024 之间C、11D、10正确答案：A5.已知一个长度为16的顺序表L，其元素按关键字有序排列。
若采用二分查找法查找一个L中不存在的元素，则关键字的比较次数最多是：A、7B、5C、6D、4正确答案：B6.设有图的数据逻辑结构 B=(K,R)，其中顶点集 K={k1,k2,⋯,k9}，有向边集R={<k1,k3>,<k1,k8>,<k2,k3>,<k2,k4>,<k2,k5>,<k3,k9>,<k5,k6>,<k8, k9>,<k9,k7>,<k4,k7>,<k4,k6>}。
以下哪个选项不是对应DAG图的拓扑序列？A、k1,k2,k3,k4,k5,k6,k8,k9,k7B、k2,k5,k1,k4,k6,k8,k3,k9,k7C、k2,k4,k5,k6,k7,k1,k3,k8,k9D、k1,k8,k2,k3,k9,k4,k7,k5,k6正确答案：C7.一棵满二叉树中127个节点，其中叶子节点的个数是（）A、64B、不确定C、65D、63正确答案：A8.具有5个顶点的有向完全图有多少条弧？A、20B、16C、25D、10正确答案：A9.设有一组关键字 { 29，01， 13，15，56，20，87，27，69，9，10，74 }，散列函数为 H(key)=key%17，采用线性探测方法解决冲突。
数据结构与算法复习题+参考答案一、单选题（共100题，每题1分，共100分）1、设栈的顺序存储空间为 S(1:m)，初始状态为 top=0。
现经过一系列正常的入栈与退栈操作后，top=m+1，则栈中的元素个数为A、m+1B、mC、不可能D、0正确答案：C2、小张完成了毕业论文，现需要在正文前添加论文目录以便检索和阅读，最优的操作方法是：A、利用 Word 提供的“手动目录”功能创建目录。
B、不使用内置标题样式，而是直接基于自定义样式创建目录。
C、将文档的各级标题设置为内置标题样式，然后基于内置标题样式自动插入目录。
D、直接输入作为目录的标题文字和相对应的页码创建目录。
正确答案：C3、赵老师在 Excel 中为 400 位学生每人制作了一个成绩条，每个成绩条之间有一个空行分隔。
他希望同时选中所有成绩条及分隔空行，最快捷的操作方法是：A、直接在成绩条区域中拖动鼠标进行选择B、单击成绩条区域的某一个单元格，然后按Ctrl+A 组合键两次C、单击成绩条区域的第一个单元格，然后按Ctrl+Shift+End 组合键D、单击成绩条区域的第一个单元格，按下Shift 键不放再单击该区域的最后一个单元格正确答案：C4、设某棵树的度为 3，其中度为 3,1,0 的结点个数分别为 3,4,15。
则该树中总结点数为A、35B、不可能有这样的树C、30D、22正确答案：C5、在商场购物时，顾客可以购买不同的商品，而同样的商品也销售给不同的顾客，则实体顾客和实体商品之间的联系是A、一对一B、一对多C、多对多D、多对一正确答案：C6、在具有 2n 个结点的完全二叉树中，叶子结点个数为A、n/2B、n-1C、nD、n+1正确答案：C7、PowerPoint 演示文稿包含了 20 张幻灯片，需要放映奇数页幻灯片，最优的操作方法是：A、将演示文稿的偶数张幻灯片删除后再放映。
B、将演示文稿的偶数张幻灯片设置为隐藏后再放映。
C、将演示文稿的所有奇数张幻灯片添加到自定义放映方案中，然后再放映。
数据结构与算法题库（附参考答案）一、单选题（共86题，每题1分，共86分）1.在快速排序的一趟划分过程中，当遇到与基准数相等的元素时，如果左右指针都不停止移动，那么当所有元素都相等时，算法的时间复杂度是多少？A、O(NlogN)B、O(N)C、O(N2)D、O(logN)正确答案：C2.一棵有 1001 个结点的完全二叉树，其叶子结点数为▁▁▁▁▁ 。
A、254B、250C、501D、500正确答案：C3.对于一个具有N个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是：A、(N−1)2B、NC、N2D、N−1正确答案：C4.在有n（>1）个元素的最大堆（大根堆）中，最小元的数组下标可以是：A、⌊n/2⌋−1B、⌊n/2⌋+2C、1D、⌊n/2⌋正确答案：B5.一棵非空二叉树，若先序遍历与中序遍历的序列相同，则该二叉树▁▁▁▁▁ 。
A、所有结点均无左孩子B、所有结点均无右孩子C、只有一个叶子结点D、为任意二叉树正确答案：A6.度量结果集相关性时，如果准确率很高而召回率很低，则说明：A、大部分检索出的文件都是相关的，但还有很多相关文件没有被检索出来B、大部分相关文件被检索到，但基准数据集不够大C、大部分检索出的文件都是相关的，但基准数据集不够大D、大部分相关文件被检索到，但很多不相关的文件也在检索结果里正确答案：A7.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。
则采用哪种存储方式最节省运算时间？A、单循环链表B、带头结点的双循环链表C、单链表D、双链表正确答案：B8.设数组 S[ ]={93, 946, 372, 9, 146, 151, 301, 485, 236, 327, 43, 892}，采用最低位优先（LSD）基数排序将 S 排列成升序序列。
第1 趟分配、收集后，元素 372 之前、之后紧邻的元素分别是：A、43，892B、236，301C、301，892D、485，301正确答案：C9.在快速排序的一趟划分过程中，当遇到与基准数相等的元素时，如果左指针停止移动，而右指针在同样情况下却不停止移动，那么当所有元素都相等时，算法的时间复杂度是多少？A、O(NlogN)B、O(N2)C、O(N)D、O(logN)正确答案：B10.在快速排序的一趟划分过程中，当遇到与基准数相等的元素时，如果左右指针都会停止移动，那么当所有元素都相等时，算法的时间复杂度是多少？A、O(NlogN)B、O(N)C、O(logN)D、O(N2)正确答案：A11.如果AVL树的深度为6（空树的深度定义为−1），则此树最少有多少个结点？A、12B、20C、33D、64正确答案：C12.已知指针ha和hb分别是两个单链表的头指针，下列算法将这两个链表首尾相连在一起，并形成一个循环链表（即ha的最后一个结点链接hb 的第一个结点，hb的最后一个结点指向ha），返回ha作为该循环链表的头指针。
数据结构与算法试题库含答案一、单选题（共100题，每题1分，共100分）1.在 Word 2010 中，关于文档自动保存的正确说法是：A、如果不进行特别设置，Word 2010 不会自动保存文档第 32 组B、默认的自动保存时间间隔为 10 分钟C、自动保存时间间隔越短越好D、自动保存时间间隔越长越好正确答案：B2.设一棵树的度为 3，其中没有度为 2的结点，且叶子结点数为 5。
该树中度为 3 的结点数为A、3B、不可能有这样的树C、2D、1正确答案：C3.下面属于应用软件的是A、人事管理系统B、Oracle 数据库管理系统C、C++编译系统D、ios 操作系统第 24 组正确答案：A4.树的度为 3，且有 9 个度为 3 的结点，5 个度为 1 的结点，但没有度为 2 的结点。
则该树中的叶子结点数为A、19B、32C、33D、18正确答案：A5.下列叙述错误的是：A、Microsoft Windows 7 属于应用软件B、把高级语言源程序转换为机器语言目标程序的过程，称为编译C、计算机内部对数据的传输、存储和处理都使用二进制D、把数据从内存传输到硬盘的操作称为写盘正确答案：A6.在 Word 文档中，学生“张小民”的名字被多次错误地输入为“张晓明”、“张晓敏”、“张晓民”、“张晓名”，纠正该错误的最优操作方法是：A、从前往后逐个查找错误的名字，并更正。
B、利用Word“查找”功能搜索文本“张晓”，并逐一更正。
C、利用Word“查找和替换”功能搜索文本“张晓*”，并将其全部替换为“张小民”。
D、利用Word“查找和替换”功能搜索文本“张晓?”，并将其全部替换为“张小民”。
第 10 组正确答案：D7.对软件系统总体结构图描述正确的是A、深度等于控制的层数B、扇入是一个模块直接调用的其他模块数C、结构图是描述软件系统功能的D、从属模块一定是原子模块正确答案：A8.计算机中组织和存储信息的基本单位是：A、位B、字长C、字节D、编码正确答案：C9.软件按功能可以分为应用软件、系统软件和支撑软件(或工具软件)。
