数据结构期末14

数据结构期末考试试题及答案一、选择题1. 评价一个算法时间性能的主要标准是( )。

A、算法易于调试B、算法易于理解C、算法的稳定性和正确性D、算法的时间复杂度2. 计算机算法具备有输入、输出、（）等五个特性。

A、可行性、可移植性和可扩充性B、可行性、确定性和有穷性C、确定性、有穷性和稳定性D、易读性、稳定性和安全性3. 带头结点的单链表head为空的判定条件是（）。

A、head==NULLB、head->next==NULLC、head->next==headD、head！=NULL4. 以下关于线性表的说法不正确的是( )。

A、线性表中的数据元素可以是数字、字符、记录等不同类型。

B、线性表中包含的数据元素个数不是任意的。

C、线性表中的每个结点都有且只有一个直接前趋和直接后继。

D、存在这样的线性表：表中各结点都没有直接前趋和直接后继。

5. 在顺序表中，只要知道( )，就可在相同时间内求出任一结点的存储地址。

A、基地址B、结点大小C、向量大小D、基地址和结点大小6. ( )运算中，使用顺序表比链表好。

A、插入B、删除C、根据序号查找D、根据元素值查找7. 一个长度为n的顺序表中，向第i个元素之前插入一个新元素时，需要向后移动（）个元素A、n-iB、n-i+1C、n-i-1D、i8. ( )适合作为经常在首尾两端操作线性表的存储结构。

A、顺序表B、单链表C、循环链表D、双向链表9. 栈和队列的共同点是（）A、都是先进后出B、都是先进先出C、只允许在端点处插入和删除元素D、没有共同点10. 一个队列的入列序列是1 2 3 4，则队列的输出序列是( )。

A、4 3 2 1B、1 2 3 4C、1 4 3 2D、3 2 4 111. 队列与一般的线性表的区别在于( )。

A、数据元素的类型不同B、运算是否受限制C、数据元素的个数不同D、逻辑结构不同12. “假上溢”现象会出现在( )中。

A、循环队列B、队列C、链队列D、顺序队列二、填空题1．数据的逻辑结构被分为集合、线性结构、树形结构和图结构。

数据结构期末考试题及答案一、选择题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。

A．线性表的顺序存储结构优于链表存储结构B．二维数组是其数据元素为线性表的线性表C．栈的操作方式是先进先出D．队列的操作方式是先进后出12．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着B 。

一、单选题1、逻辑上通常可以将数据结构分为( )A.初等结构和组合结构B.顺序结构和链式结构C.线性结构和非线性结构D.动态结构和静态结构正确答案：C2、如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是()。

A.栈B. 队列C.图D.树正确答案：D3、在长度为n的顺序表的第i个位置上插入一个元素(1<=i<=n+1)，元素的移动次数为：（）A.n-iB.i-1C.n-i+1D.i正确答案：C4、在非空线性链表中由p所指结点的后面插入一个由q所指的结点，应依次执行（）A.q->next=p；p->next=q；B.p->next=q；q->next=p；C.q->next=p->next；p->next=q；D.q->next=p->next；p=q；正确答案：C5、已知栈的最大容量为4。

若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行,则可能出现的出栈序列为（）A.2，3，5，6，1，4B.1，4，6，5，2，3C.5，4，3，2，1，6D.3，2，5，4，1，6正确答案：D6、设栈S和队列Q初始均为空，若6个元素入栈的顺序为1、2、3、4、5、6，一个元素出栈以后立即入队列Q，若6个元素出队的顺序为2、4、3、6、5、1，则栈S的容量至少为（）A.3B.5C.4D.2正确答案：A7、在计算机内实现递归算法时所需的辅助数据结构是（）A.队列B.栈C.图D.树正确答案：B8、循环队列存储在数组A[0..m-1],则出队时的操作为（）A.front=(front mod m)+1B.ront=(front+1)mod mC.front=front+1D.front=(front+1)mod (m-1)正确答案：B9、若以S和X分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列合法的是（)A.SXXSXSSXB.SSSXXSXXC.SXSSXXXXD.SXSXXSSX正确答案：B10、在具有m个单元的循环队列中，队头指针为front，队尾指针为rear，则队满的条件是（）A.(front+1)%m==rearB.(rear+1)%m==frontC.front==rearD.rear+1==front正确答案：B11、在表长为n的顺序表上做插入运算，平均要移动的结点数为（）A.n/4B.nC.n/3D.n/2正确答案：D12、元素的进栈次序为A，B，C，D，E，则退栈中不可能的序列是（）A.E，D，C，B，AB.A，B，C，D，EC.E，A，B，C，DD.B，C，D，E，A正确答案：C13、下述二叉树中，（）满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序。

数据结构期末考试复习题资料一．单项选择题1.算法指的是（）。

A．计算方法B．排序方法C．特定问题求解步骤的描述D．调度方法2．下列数据结构中，（）是非线性结构。

A．栈B．队列C．完全二叉树D．堆3.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。

A．顺序表B．双向链表C．单循环链表D．带头结点的双循环链表4．队列的操作原则是（）A．先进先出B．后进先出C．先进后出D．不分顺序5．栈和队列的共同特点是（）。

A．都是先进先出B．都是先进后出C．都是只允许在端点处插入和删除D．没有共同点6．在一棵高度为k 的满二叉树中，结点总数为（）。

A．2k-1 B．2k C．2k-1 D．⎣log 2 k ⎦+ 17.在下列存储形式中，哪一个不是树的存储形式？（）A．双亲链表表示法B．孩子链表表示法C．孩子兄弟链表表示法D．顺序存储表示法8．n 个结点的完全有向图含有边的数目为（）。

A．n*n B．n*(n+1) C．n/2 D．n*(n-1）9．n 个顶点的强连通图至少有（）条边。

A．n B．n-1 C．n+1 D．n(n-1)10、高度为k 的二叉树的最大结点数为（）。

A、2kB、2k-1C、2k–1D、2k-1–111、下列哪一种图的邻接矩阵是对称矩阵？（）A、有向图B、无向图C、AOV 网D、AOE 网12、在下列存储形式中，哪一个不是树的存储形式？（）A、双亲表示法B、孩子表示法C、孩子兄弟表示法D、顺序存储表示法13、下面哪一方法可以判断出一个有向图是否有环。

（）A、深度优先遍历B、拓扑排序C、求最短路径D、广度优先遍历14.适用于折半查找的表的存储方式及元素排列要求为（）。

A．链接方式存储，元素无序B．链接方式存储，元素有序C．顺序方式存储，元素无序D．顺序方式存储，元素有序15、一个算法应该是（）。

A、程序B、特定问题求解步骤的描述C、要满足五个基本特性D、A 和C16、算法分析的两个主要方面是（）。

数据结构复习题（课程代码 252259）一、填空题（本大题共40小题）1.队列中是按照______先进先出______的原则进行数据元素的增删。

2.___栈__又称为LIFO表。

3.在顺序存储的完全二叉树中，若编号为i的结点有左孩子结点，则其右孩子结点的编号为___2i+1___。

4.存储地址与关键字之间存在某种映射关系的存储结构为_______散列存储结构_______。

5.在串S=“structure”中，以r为首字符的子串有_9_个。

6.设有整型二维数组M[4][3]，每个元素（整数）占2个存储单元，元素按行的顺序存储，数组的起始地址为200，元素M[1][1]的地址是___208____。

7.在一个具有n个顶点的无向完全图中，包含有___ n(n-1)/2_____条边，在一个具有n个顶点的有向完全图中，包含有__ n(n-1)______条边。

8.假定一个线性表为(12,23,74,55,63,40)，若按Key % 4条件进行划分，使得同一余数的元素成为一个子表，则得到的四个子表分别为_____（12，40）（）（74）（23,55，63）____。

9.向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度____增加1______。

10.在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为__ O(log2n)______，整个堆排序过程的时间复杂度为__ O(nlog2n)______。

11.在快速排序、堆排序、归并排序中，____归并_____排序是稳定的。

12.一棵深度为5的满二叉树中的结点数为_______31_______个。

13.在含n个顶点和e条边的无向图的邻接矩阵中,非零元素的个数为__2e __。

14.从一棵二叉排序树中查找一个元素时，若元素的值大于根结点的值，则继续向____右子树____查找。

15._____拓朴排序______可以判断出一个有向图中是否有环。

《数据结构》试题（A卷）（考试时间： 90分钟）一、单项选择题（本大题共15小题，每小题2分，共30分）（每题只有一个选项是正确的,将答案填写在括号内，错选、多选不得分）1.（）是组成数据的基本单位，是一个数据整体中相对独立的单元。

A．数据 B.数据元素 C.数据对象 D.数据结构2.算法计算量的大小称为算法的（）。

A.效率B.复杂度C.数据元素之间的关系D.数据的存储方法3.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入或删除运算，则采用以下（）方式最节省时间。

A.链式存储B. 索引存储C.顺序存储D.散列存储4.下述哪一条是顺序存储结构的优点？（）A.存储密度大B.插入运算方便C.删除运算方便D.可方便地用于各种逻辑结构的存储表示5.在一个单链表中，若删除p所指结点的后续结点，则执行（）。

A.p->next=p->next->nextB.p->next=p->nextC.p=p->next;p->next=p->next->nextD.p=p->next->next6.带头结点的单链表head为空的判定条件是（）。

A.head==NULLB.head->next==NULLC.head->next==headD.head!==NULL7.非空的循环单链表head的尾结点(由p所指向)满足（）。

A.p->head==NULLB.p==NULLC.p->next==headD.p==head8.下面关于线性表的叙述中，错误的是哪一个？（）A.线性表采用顺序存储，必须占用一片连续的存储单元。

B.线性表采用顺序存储，便于进行插入和删除操作。

C.线性表采用链式存储，不必占用一片连续的存储单元。

D.线性表采用链式存储，便于插入和删除操作。

9.队列操作的原则是（）。

A.后进先出B.先进先出C.只能进行插入D.只能进行删除10.栈中允许进行插入和删除的一端称为（）。

数据结构的基本概念选择题（1）顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。

A．线性结构B．非线性结构C．存储位置D．指针（2）假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产，子女可以继承父亲或母亲的遗产；子女间不能相互继承，则表示该遗产继承关系的最合适的数据结构应该是（）。

A．树B．图C．线性表D．集合（3）计算机所处理的数据一般具有某种内在联系，这是指（）。

A．数据和数据之间存在某种关系B．元素和元素之间存在某种关系C．元素内部具有某种结构D．数据项和数据项之间存在某种关系（4）在数据结构中，与所使用的计算机无关的是数据的（）。

A．树B．图C．线性表D．集合（5）在存储数据时，通常不仅要存储各数据元素的值，还要存储（）。

A．数据的处理方法B．数据元素的类型C．数据元素之间的关系D．数据的存储方法（6）在链接存储结构中，要求（）。

A．每个结点占用一片连续的存储区域B．所有结点占用一片连续的存储区域C．结点的最后一个域是指针类型D．每个结点有多少个后继就设多少个指针（7）下列说法不正确的是（）。

A．数据元素是数据的基本单位B．数据项是数据中不可分割的最小单位C．数据可由若干个数据项构成D．数据元素可由若干个数据项构成（8）以下与数据的存储结构无关的术语是（）。

A．循环队列B．链表C．散列表D．栈（9）以下术语属于逻辑结构的是（）。

A．顺序表B．哈希表C．有序表D．单链表（10）可以用（）定义一个完整的数据结构。

A．数据元素B．数据对象C．数据关系D．抽象数据类型（11）对于数据结构的描述，下列说法中不正确的是（）。

A．相同的逻辑结构对应的存储结构也必相同B．数据结构由逻辑结构、存储结构和基本操作三方面组成C．数据结构基本操作的实现与存储结构有关D．数据的存储结构是数据的逻辑结构的机内实现（12）以下关于链接存储结构的叙述中，（）是不正确的。

数据结构期末测验1. 使用双链表存储线性表，其优点是可以（） [单选题] *A.提高查找速度(正确答案)B.更方便数据的插入和删除C.节约存储空间D.很快回收存储空间2. 下面几种算法时间复杂度中，时间复杂度最高的是（）。

[单选题] *A.O(nlog2n)B.O(n2)C.O(n)D.O(2n)(正确答案)3. 线性表（a1,a2,…,an）以链接方式存储时，若指针指向头结点，则访问第i个元素的时间复杂度为( ) [单选题] *A.O（i）B.O（1）C.O（n）(正确答案)D.O（i-1）4. 串是一种（） [单选题] *A.链式存储的线性结构B.链式存储的非线性结构C.限制元素类型的线性结构(正确答案)D.限制存取点的非线性结构5. 设顺序线性表中有n个数据元素，则删除表中第i个（从1开始计数）元素需要移动（）个元素。

[单选题] *A.n-i(正确答案)B.n+1-iC.n-1-iD.i6. 从19个元素中查找其中某个元素，如果最多进行5次元素之间的比较，则采用的查找方法只可能是（）。

[单选题] *A.折半查找(正确答案)B.分块查找C.顺序查找D.都不可能7. 在含有12个结点的平衡二叉树上，查找关键字为35（存在该结点）的结点，则依次比较的关键字有可能是（）。

[单选题] *A.46，36，18，20，28，35B.47，37，18，27，36C.27，48，39，43，37D.15，45，25，35(正确答案)8. 一个递增表为R[0..11]，采用折半查找方法，在某次成功查找到指定的记录时，以下（）是可能的记录比较序列。

[单选题] *A.R[0]、R[5]、R[2]B.R[0]、R[6]、R[9]C.R[5]、R[8]、R[10](正确答案)D.R[5]、R[2]、R[4]9. 当采用分块查找时，数据的组织方式为（）。

[单选题] *A.数据分成若干块，每块内数据有序B.数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块(正确答案)C.数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块D.数据分成若干块，每块中的数据个数必须相同10. 设待查找元素为47，且已存入变量k中，如果在查找过程中，和k进行比较的元素依次是47、32、46、25、47，则所采用的查找方法（）。

数据结构期末考试题及答案一、选择题（每题2分，共10题）1. 数据结构是指（）A. 存储和组织数据的方式B. 对数据进行计算和处理的方法C. 数据的物理表示形式D. 数据的逻辑结构答案：A. 存储和组织数据的方式2. 在数据结构中，栈是一种（）A. 先进先出的数据结构B. 后进先出的数据结构C. 随机存取的数据结构D. 按键值查找的数据结构答案：B. 后进先出的数据结构3. 下列哪种数据结构不支持随机访问？（）A. 队列B. 栈C. 数组D. 链表答案：D. 链表4. 在二叉树中，每个节点最多可以有几个子节点？（）A. 0B. 1C. 2D. 无限多答案：C. 25. 在图的表示方法中，邻接矩阵适用于（）A. 稠密图B. 稀疏图C. 有向图D. 无向图答案：A. 稠密图6. 下列排序算法中，最坏情况时间复杂度为O(nlogn)的是（）A. 冒泡排序B. 插入排序C. 快速排序D. 选择排序答案：C. 快速排序7. 广度优先搜索算法用于（）A. 求最短路径B. 求全排列C. 求最小生成树D. 求图的连通分量答案：A. 求最短路径8. 哈希表的查找时间复杂度为（）A. O(1)B. O(n)C. O(logn)D. O(n^2)答案：A. O(1)9. AVL树是一种（）A. 无序树B. 有序树C. 平衡树D. 非平衡树答案：C. 平衡树10. 以下哪个不属于基本的查找算法？（）A. 二分查找B. 插值查找C. 散列查找D. 顺序查找答案：C. 散列查找二、填空题（每题4分，共4题）11. 下列不是线性表的是（）答案：二叉树12. 在冒泡排序中，每一轮的比较次数是________答案：n-113. 在堆排序中，堆的建立时间复杂度为________答案：O(n)14. 从一个顶点到其余各顶点的最短路径算法是________答案：Dijkstra算法三、简答题（每题10分，共3题）15. 请简要说明栈的应用场景，并给出一个具体实例。

第一章绪论一，选择题1．组成数据的基本单位是（）A．数据项B．数据类型C．数据元素D．数据变量2．数据结构是研究数据的（）以及它们之间的相互关系。

A．理想结构，物理结构B．理想结构，抽象结构C．物理结构，逻辑结构D．抽象结构，逻辑结构3．算法分析的两个主要方面是（）A．正确性和简单性B．可读性和文档性C．数据复杂性和程序复杂性D．时间复杂度和空间复杂度4．算法分析的目的是（）。

A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进D．分析算法的易懂性和文档性5. 算法的时间复杂度取决于（）A．问题的规模 B. 待处理数据的初态 C. A和B Ｄ．以上都不是6．一个算法应该是（）。

A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C.7. 下面关于算法说法错误的是（）A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的8．从逻辑上可以把数据结构分为（）两大类。

A．动态结构、静态结构 B．顺序结构、链式结构C．线性结构、非线性结构 D．初等结构、构造型结构9．程序段 for ( i=n-1;i>=1;i--)for (j=1j<=i;j++)if( A[j]>A[j+1])A[j]与A[j+1]对换；其中 n为正整数，则最后一行的语句频度在最坏情况下是（）A．O（n）B．O(nlogn) C.．O(n3) D．O(n2)10．连续存储设计时，存储单元的地址（）。

A．一定连续 B．一定不连续 C．不一定连续 D．部分连续，部分不连续二，判断题1．数据结构的抽象操作的定义与具体实现有关。

( )2．数据结构是数据对象与对象中数据元素之间关系的集合。

3．在顺序存储结构中，有时也存储数据结构中元素之间的关系。

( )4．数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用的需要建立的。