《数据结构与算法》习题：选择题、判断题

2022年安徽工业大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、下列排序算法中，占用辅助空间最多的是（）。

A.归并排序B.快速排序C.希尔排序D.堆排序2、无向图G=(V，E)，其中：V={a，b，c，d，e，f}，E={(a，b)，(a， e)，(a，c)，(b，e)，(c，f)，(f，d)，(e，d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（）。

A.a，b，e，c，d，fB.a，c，f,e，b，dC.a，e，b，c，f, dD.a，e，d，f，c，b3、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。

A.单链表B.仅有头指针的单循环链表C.双链表D.仅有尾指针的单循环链表4、最大容量为n的循环队列，队尾指针是rear，队头：front，则队空的条件是（）。

A.（rear+1）MOD n=frontB.rear=frontC.rear+1=frontD.（rear-1）MOD n=front5、有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（）。

A.543612B.453126C.346521D.2341566、下列叙述中，不符合m阶B树定义要求的是（）。

A．根结点最多有m棵子树 B．所有叶结点都在同一层上C．各结点内关键字均升序或降序排列 D．叶结点之间通过指针链接7、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。

下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。

Ⅰ．简单选择排序Ⅱ．希尔排序Ⅲ．快速排序Ⅳ．堆排Ⅴ．二路归并排序A．仅Ⅰ、Ⅲ、Ⅳ B．仅Ⅰ、Ⅱ、Ⅲ C．仅Ⅱ、Ⅲ、Ⅳ D．仅Ⅲ、Ⅳ、Ⅴ8、下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序（）。

A.二叉排序树B.哈夫曼树C.AVL树D.堆9、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。

数据结构c语言版期末考试复习试题[1]《数据结构与算法》复习题一、选择题。

1．在数据结构中，从逻辑上可以把数据结构分为CA．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．内部结构和外部结构2．数据结构在计算机内存中的表示是指AA．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系3．在数据结构中，与所使用的计算机无关的是数据的A结构。

A．逻辑B．存储C．逻辑和存储D．物理4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储C。

A．数据的处理方法B．数据元素的类型C．数据元素之间的关系D．数据的存储方法5．在决定选取何种存储结构时，一般不考虑A。

A．各结点的值如何B．结点个数的多少C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。

6．以下说法正确的是D。

A．数据项是数据的基本单位数据元素是数据的基本单位B．数据元素是数据的最小单位数据项是数据的最小单位C．数据结构是带结构的数据项的集合D．一些表面上很不相同的数据可以有相同的逻辑结构7．算法分析的目的是C，算法分析的两个主要方面是A。

（1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进D．分析算法的易读性和文档性（2）A．空间复杂度和时间复杂度B．正确性和简明性C．可读性和文档性D．数据复杂性和程序复杂性8．下面程序段的时间复杂度是O(n2)。

=0;for(I=0;ium=;9．下面程序段的时间复杂度是O(n某m)for(i=0;i10．下面程序段的时间复杂度是O(log3n)i＝0；while（i<=n）i=i某3；11．在以下的叙述中，正确的是BA．线性表的顺序存储结构优于链表存储结构B．二维数组是其数据元素为线性表的线性表C．栈的操作方式是先进先出桟—先进后出队—先进先出D．队列的操作方式是先进后出12．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着B。

《数据结构与算法》复习题一、选择题。

1．在数据结构中，从逻辑上可以把数据结构分为 C 。

A．动态结构和静态结构 B．紧凑结构和非紧凑结构C．线性结构和非线性结构 D．内部结构和外部结构2．数据结构在计算机内存中的表示是指 A 。

A．数据的存储结构 B．数据结构 C．数据的逻辑结构 D．数据元素之间的关系3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。

A．逻辑 B．存储 C．逻辑和存储 D．物理4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。

A．数据的处理方法 B．数据元素的类型C．数据元素之间的关系 D．数据的存储方法5．在决定选取何种存储结构时，一般不考虑 A 。

A．各结点的值如何 B．结点个数的多少C．对数据有哪些运算 D．所用的编程语言实现这种结构是否方便。

6．以下说法正确的是 D 。

A．数据项是数据的基本单位B．数据元素是数据的最小单位C．数据结构是带结构的数据项的集合D．一些表面上很不相同的数据可以有相同的逻辑结构7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。

（1）A．找出数据结构的合理性 B．研究算法中的输入和输出的关系C．分析算法的效率以求改进 C．分析算法的易读性和文档性（2）A．空间复杂度和时间复杂度 B．正确性和简明性C．可读性和文档性 D．数据复杂性和程序复杂性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 。

2022年池州学院计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、将线性表的数据元素进行扩充，允许带结构的线性表是（）。

A.串B.树C.广义表D.栈2、将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是（）。

A.NB.2N-1C.2ND.N-13、线性表的顺序存储结构是一种（）。

A.随机存取的存储结构B.顺序存取的存储结构C.索引存取的存储结构D.Hash存取的存储结构4、下列关于AOE网的叙述中，不正确的是（）。

A.关键活动不按期完成就会影响整个工程的完成时间B.任何一个关键活动提前完成，那么整个工程将会提前完成C.所有的关键活动提前完成，那么整个工程将会提前完成D.某些关键活动若提前完成，那么整个工程将会提前完成5、已知串S='aaab'，其next数组值为（）。

A.0123B.1123C.1231D.12116、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（）。

A．i＝1，j＝0 B．i＝5，j＝0 C．i＝5，j＝2 D．i＝6，j＝27、下列选项中，不能构成折半查找中关键字比较序列的是（）。

A．500，200，450，180 B．500，450，200，180C．180，500，200，450 D．180，200，500，4508、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。

A.107B.108C.214D.2159、已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历结果为（）。

A.CBEFDAB.FEDCBAC.CBEDFAD.不定10、在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A 的左孩子的平衡因子为0，右孩子的平衡因子为l，则应作（）型调整以使其平衡A.LLB.LRC.RLD.RR二、填空题11、在有n个顶点的有向图中，每个顶点的度最大可达______。

一、选择题1. 在逻辑上能够把数据结构分红（A）A. 线性结构和非线性结构B. 动向结构和静态结构C.紧凑结构和非紧凑结构D.内部结构和外面结构2. 单链表中各结点之间的地点（C）A. 一定连续B.部分一定连续C.不必定连续D.以上均不对3. 在一个长度为 n 的次序表中向第 i 个元素（ 0<i<=n+1 ）以前插入一个新元素时，需向后挪动（B ）个元素。

A 、n-iB、n-i+1C、n-i-1D、 i4. 插入和删除操作只好在一端进行的线性表，称为（C ）。

A. 行列B. 线性表C. 栈D.循环行列5、行列是仅同意在（）进行插入，而在（）进行删除。

(A )A. 队尾，队首B. 队尾，队尾C. 队首，队尾D. 队首，队首6. 链表合适于（A ）查找。

A. 次序B.二分C.随机D.次序或二分7. 数据的基本单位是（A ）。

A. 数据元素B.数据结构C.数据项D.数据对象8. 以下哪个不是算法的特征（B ）。

A. 有穷性B. 可数性C.可行性D.确立性9. 在表长为 n 的次序表中进行线性查找，它的均匀查找长度为（B ）。

A.ASL=nB.ASL=(n+1)/2C.ASL=n+1 D.ASL=log2n10. 一个线性表第一个元素的储存地点是 320，每个元素的长度为 3，则第五个元素的地点是(C ）。

11. 设 front 、rear 分别为循环双向链表结点的左指针和右指针，则指针 P 所指的元素是双循环链表 L 的尾元素的条件是（D ）。

A.P==LB.P->front==LC.P==NULLD.P->rear==L12. 已知 P 为单链表中的非首尾结点，删除 P 结点的后继结点 Q 的语句为（A ）。

A.P->NEXT=Q->NEXT;FREE(Q);B.Q->NEXT=P; FREE(Q);C.Q->NEXT=P->NEXT;FREE(Q);D.P->NEXT=S;S->NEXT=P; B第1页共16页 1A.SQ->rear==SQ->frontB. (SQ->rear+1)%MAXLEN==SQ->frontC.SQ->rear==0D. SQ->front==014. 一组记录的排序码为（ 46， 79，56， 38， 40， 84），则利用堆排序的方法成立的初始堆 为(B )。

2022年广州大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、将线性表的数据元素进行扩充，允许带结构的线性表是（）。

A.串B.树C.广义表D.栈2、无向图G=(V，E)，其中：V={a，b，c，d，e，f}，E={(a，b)，(a， e)，(a，c)，(b，e)，(c，f)，(f，d)，(e，d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（）。

A.a，b，e，c，d，fB.a，c，f,e，b，dC.a，e，b，c，f, dD.a，e，d，f，c，b3、连续存储设计时，存储单元的地址（）。

A.一定连续B.一定不连续C.不一定连续D.部分连续，部分不连续4、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（）。

A.仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都可能要修改D.队头、队尾指针都要修改5、已知串S='aaab'，其next数组值为（）。

A.0123B.1123C.1231D.12116、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。

下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。

Ⅰ．简单选择排序Ⅱ．希尔排序Ⅲ．快速排序Ⅳ．堆排Ⅴ．二路归并排序A．仅Ⅰ、Ⅲ、Ⅳ B．仅Ⅰ、Ⅱ、Ⅲ C．仅Ⅱ、Ⅲ、Ⅳ D．仅Ⅲ、Ⅳ、Ⅴ7、下列选项中，不能构成折半查找中关键字比较序列的是（）。

A．500，200，450，180 B．500，450，200，180C．180，500，200，450 D．180，200，500，4508、有n（n>0）个分支结点的满二叉树的深度是（）。

A.n2-1B.log2（n+1）+1C.log2（n+1）D.log2（n-l）9、一个具有1025个结点的二叉树的高h为（）。

A.11B.10C.11至1025之间D.10至1024之间10、若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为（）。

2022年北京工商大学嘉华学院计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、将线性表的数据元素进行扩充，允许带结构的线性表是（）。

A.串B.树C.广义表D.栈2、下列排序算法中，占用辅助空间最多的是（）。

A.归并排序B.快速排序C.希尔排序D.堆排序3、连续存储设计时，存储单元的地址（）。

A.一定连续B.一定不连续C.不一定连续D.部分连续，部分不连续4、最大容量为n的循环队列，队尾指针是rear，队头：front，则队空的条件是（）。

A.（rear+1）MOD n=frontB.rear=frontC.rear+1=frontD.（rear-1）MOD n=front5、动态存储管理系统中，通常可有（）种不同的分配策略。

A.1B.2C.3D.46、循环队列放在一维数组A中，end1指向队头元素，end2指向队尾元素的后一个位置。

假设队列两端均可进行入队和出队操作，队列中最多能容纳M－1个元素。

初始时为空，下列判断队空和队满的条件中，正确的是（）。

A．队空：end1＝＝end2；队满：end1＝＝（end2＋1）mod MB．队空：end1＝＝end2；队满：end2＝＝（end1＋1）mod （M－1）C．队空：end2＝＝（end1＋1）mod M；队满：end1＝＝（end2＋1） mod MD．队空：end1＝＝（end2＋1）mod M；队满：end2＝＝（end1＋1） mod （M－1）7、若元素a，b，c，d，e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（）。

8、设X是树T中的一个非根结点，B是T所对应的二叉树。

在B中，X是其双亲的右孩子，下列结论正确的是（）。

A.在树T中，X是其双亲的第一个孩子B.在树T中，X一定无右兄弟C.在树T中，X一定是叶结点D.在树T中，X一定有左兄弟9、在下述结论中，正确的有（）。

习题一一、选择题1、数据结构是一门研究非数值计算的程序设计问题中的操作对象以及它们之间的（B）和运算的学科。

A．结构B．关系C．运算D．算法2、在数据结构中，从逻辑上可以把数据结构分成（C）。

A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．逻辑结构和存储结构3、线性表的逻辑顺序和存储顺序总是一致的，这种说法（B）。

A．正确B．不正确C．无法确定D．以上答案都不对4、算法分析的目的是（C）。

A．找出算法的合理性B．研究算法的输人与输出关系C．分析算法的有效性以求改进D．分析算法的易懂性二、填空题1、数据是信息的载体，是对客观事物的符号表示，它能够被计算机识别、存储、加工和处理，数据是对能够有效的输人到计算机中并且能够被计算机处理的符号的总称。

例如，数学中所用到的整数和实数，文本编辑所用到的字符串等。

2、数据元素是数据的基本单位，有些情况下也称为元素、结点、顶点、记录等。

3、数据项是数据不可分割的最小单元，是具有独立含义的最小标识单位。

例如构成一个数据元素的字段、域、属性等都可称之为_数据项。

4、简而言之，数据结构是数据之间的相互关系，即数据的组织形式。

5、数据的逻辑结构是指数据之间的逻辑关系。

逻辑结构是从逻辑关系上描述数据，它与具体存储无关，是独立于计算机的。

因此逻辑结构可以看作是从具体问题抽象出来的数学模型。

6、数据的存储结构指数据元素及其关系在计算机存储器内的表示。

存储结构是逻辑结构在计算机里的实现，也称之为映像。

7、数据的运算是指对数据施加的操作。

它定义在数据的逻辑结构之上，每种逻辑结构都有一个数据的运算。

常用的有：查找、排序、插人、删除、更新等操作。

8、数据逻辑结构可以分为四种基本的类型，集合结构中的元素除了仅仅只是同属于一个集合_，不存在什么关系。

9、数据逻辑结构的四种基本类型中，线性结构_中的元素是一种一对一的关系，这种结构的特征是：若结构是非空集，则有且只有一个开始结点和一个终端结点，并且所有结点最多只能有一个直接前驱和一个直接后继。

《数据结构与算法》复习题（专升本）一、填空题1、数据结构被形式地定义为（ D, R），其中D 是的有限集合， R 是D 上的有限集合。

2、数据结构包括数据的、数据的和数据的这三个方面的内容。

3、写出带头结点的双向循环链表L 为空表的条件。

4、在具有n个元素的循环队列中，队满时具有个元素。

5、求子串在主串中首次出现的位置的运算称为。

6、由3个结点所构成的二叉树有种形态。

7、数据的逻辑结构是指。

8、数据结构按逻辑结构可分为两大类，它们分别是和。

9、线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在多对多关系。

10、带头结点的单链表head 为空的条件是。

11、两个串相等的充分必要条件是两个串的长度相等且。

12、二维数组，可以按照和两种不同的存储方式。

13、一棵具有257个结点的完全二叉树，它的深度为。

14、内部排序方法按排序采用的策略可划分为五类：、、、和基数排序。

二、选择题1、若某线性表中最常用的操作是取第i 个元素和找第i个元素的前驱，则采用（）存储方法最节省时间。

A.顺序表B.单链表C.双链表D.单循环链表2、二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。

A.空或只有一个结点B.高度等于其结点数C.任一结点无左孩子D.任一结点无右孩子3、计算机算法指的是：（）A. 计算方法B. 排序方法C. 解决问题的有限运算序列D. 调度方法4、栈和队列的主要区别在于（）。

A.它们的逻辑结构不一样B.它们的存储结构不一样C.所包含的运算不一样D.插入删除运算的限定不一样5、为5个使用频率不等的字符设计哈弗曼编码，不可能的方案是（）。

A.000,001,010,011,1B. 0000,0001,001,01,1C.000,001,01,10,11D.00,100,101,110,1116、用深度优先遍历方法遍历一个有向无环图，并在深度优先遍历算法中按退栈次序打印出相应的顶点，则输出的顶点序列是（）。

2022年河海大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、用有向无环图描述表达式(A+B)*((A+B)／/A)，至少需要顶点的数目为（）。

A.5B.6C.8D.92、下述文件中适合于磁带存储的是（）。

A.顺序文件B.索引文件C.哈希文件D.多关键字文件3、连续存储设计时，存储单元的地址（）。

A.一定连续B.一定不连续C.不一定连续D.部分连续，部分不连续4、向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应执行（）。

A.h->next=sB.s->next=hC.s->next=h;h->next=sD.s->next=h-next;h->next=s5、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（）。

A.仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都可能要修改D.队头、队尾指针都要修改6、循环队列放在一维数组A中，end1指向队头元素，end2指向队尾元素的后一个位置。

假设队列两端均可进行入队和出队操作，队列中最多能容纳M－1个元素。

初始时为空，下列判断队空和队满的条件中，正确的是（）。

A．队空：end1＝＝end2；队满：end1＝＝（end2＋1）mod MB．队空：end1＝＝end2；队满：end2＝＝（end1＋1）mod （M－1）C．队空：end2＝＝（end1＋1）mod M；队满：end1＝＝（end2＋1） mod MD．队空：end1＝＝（end2＋1）mod M；队满：end2＝＝（end1＋1） mod （M－1）7、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。

下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。

Ⅰ．简单选择排序Ⅱ．希尔排序Ⅲ．快速排序Ⅳ．堆排Ⅴ．二路归并排序A．仅Ⅰ、Ⅲ、Ⅳ B．仅Ⅰ、Ⅱ、Ⅲ C．仅Ⅱ、Ⅲ、Ⅳ D．仅Ⅲ、Ⅳ、Ⅴ8、一个具有1025个结点的二叉树的高h为（）。