数据结构题库

题库练习第一章概论习题一、填空题1.数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科。2.数据结构被形式地定义为（D,R），其中D是数据元素的有限集合，R是D上的关系有限集合。3.数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。4.数据结构按逻辑结构可分为两大类，它们分别是线性结构和非线性结构。5.线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。6．在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有1个后续结点。7.在树形结构中，树根结点没有前驱结点，其余每个结点有且只有1个前驱结点；叶子结点没有后续结点，其余每个结点的后续结点数可以任意多个。8.在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。9.数据的运算最常用的有5种，它们分别是插入、删除、修改、查找、排序。10.一个算法的效率可分为时间效率和空间效率。二、单项选择题（B）1.非线性结构是数据元素之间存在一种：A）一对多关系B）多对多关系C）多对一关系D）一对一关系（C）2.数据结构中，与所使用的计算机无关的是数据的结构；A)存储B)物理C)逻辑D)物理和存储（C）3.算法分析的目的是：A)找出数据结构的合理性B)研究算法中的输入和输出的关系C)分析算法的效率以求改进D)分析算法的易懂性和文档性（A）4.算法分析的两个主要方面是：A)空间复杂性和时间复杂性B)正确性和简明性C)可读性和文档性D)数据复杂性和程序复杂性（C）5.计算机算法指的是：A)计算方法B)排序方法C)解决问题的有限运算序列D)调度方法（B）6.计算机算法必须具备输入、输出和等5个特性。A)可行性、可移植性和可扩充性B)可行性、确定性和有穷性C)确定性、有穷性和稳定性D)易读性、稳定性和安全性三、简答题2.【严题集1.2②】数据结构和数据类型两个概念之间有区别吗？答：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素。数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。3.简述线性结构与非线性结构的不同点。答：线性结构反映结点间的逻辑关系是一对一的，非线性结构反映结点间的逻辑关系是多对多的。四、【严题集1.8④】分析下面各程序段的时间复杂度2.s=0;fori=0;in;i++)for(j=0;jn;j++)s+=B[i][j];sum=s;答：O（n2）1.for(i=0;in;i++)for(j=0;jm;j++)A[i][j]=0;答：O（m*n）第二章线性表习题1、选择题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字符构成的序列2、判断题1、逻辑结构相同的数据其存储结构一定相同。（）2、线性表采用链表存储后，线性表长度一定等于链表所有结点的个数。（）3、双循环链表中，任一结点的前趋指针均不空。（）4、对链表进行插入和删除操作时，不必移动结点。（）（×）1.链表的每个结点中都恰好包含一个指针。答：错误。链表中的结点可含多个指针域，分别存放多个指针。例如，双向链表中的结点可以含有两个指针域，分别存放指向其直接前趋和直接后继结点的指针。（×）2.链表的物理存储结构具有同链表一样的顺序。错，链表的存储结构特点是无序，而链表的示意图有序。（×）3.链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。错，链表的结点不会移动，只是指针内容改变。（×）4.线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。错，混淆了逻辑结构与物理结构，链表也是线性表！且即使是顺序表，也能存放记录型数据。（×）5.顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。错，正好说反了。顺序表才适合随机存取，链表恰恰适于“顺藤摸瓜”（×）6.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。错，前一半正确，但后一半说法错误，那是链式存储的优点。顺序存储方式插入、删除运算效率较低，在表长为n的顺序表中，插入和删除一个数据元素，平均需移动表长一半个数的数据元素。（×）7.线性表在物理存储空间中也一定是连续的。错，线性表有两种存储方式，顺序存储和链式存储。后者不要求连续存放。（×）8.线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。错误。线性表有两种存储方式，在顺序存储时，逻辑上相邻的元素在存储的物理位置次序上也相邻。（×）9.顺序存储方式只能用于存储线性结构。错误。顺序存储方式不仅能用于存储线性结构，还可以用来存放非线性结构，例如完全二叉树是属于非线性结构，但其最佳存储方式是顺序存储方式。（后一节介绍）（×）10.线性表的逻辑顺序与存储顺序总是一致的。错，理由同7。链式存储就无需一致。3、填空题1、在带头结点的单链表L中，若要删除第一个元素，则需要执行下列三条语句：_______________；L→next＝U→next；free（U）。2、在单链表L中，若要在指针P所指结点之后插入由指针S所指的结点，则需执行下列语句：S-next=P-next；______________；3、在带有头结点的单链表L中，第一个元素结点的指针是_____________。4、双循环链表L中由指针P所指向的某结点为尾结点的条件是_______________。datanext1.【严题集2.2①】在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与表长和该元素在表中的位置有关。2.线性表中结点的集合是有限的，结点间的关系是一对一的。3.向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动n-i+1个元素。4.向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动n-i个元素。5.在顺序表中访问任意一结点的时间复杂度均为O(1)，因此，顺序表也称为随机存取的数据结构。6.【严题集2.2①】顺序表中逻辑上相邻的元素的物理位置必定相邻。单链表中逻辑上相邻的元素的物理位置不一定相邻。7.【严题集2.2①】在单链表中，除了首元结点外，任一结点的存储位置由其直接前驱结点的链域的值指示。8．在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O（n）。4、算法设计题1、设有两个单链表L和L1，各结点结构如下：试画出该链表的结构图，并编写算法，判断单链表L1是否与单链表L相同，相同返回1，不同返回0。五、简答题1.【严题集2.3②】试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？答：①顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。优点：存储密度大（＝1？），存储空间利用率高。缺点：插入或删除元素时不方便。②链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（1），存储空间利用率低。顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。2.【严题集2.1①】描述以下三个概念的区别：头指针、头结点、首元结点（第一个元素结点）。在单链表中设置头结点的作用是什么？答：首元结点是指链表中存储线性表中第一个数据元素a1的结点。为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理。头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空。否则表示空表的链表的头指针为空。这三个概念对单链表、双向链表和循环链表均适用。是否设置头结点，是不同的存储结构表示同一逻辑结构的问题。头结点headdatalink头指针首元结点简而言之，头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针；头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息（内放头指针？那还得另配一个头指针！！！）首元素结点是指链表中存储线性表中第一个数据元素a1的结点。第三章栈、队列和数组习题1、选择题1、一个栈的输入序列是12345，则下列序列中是栈的输出序列的是________。a2,3,4,1,5b5,4,1,3,2c3,1,2,4,5d1,4,2,5,32、栈和队列都是______。a顺序存储的线性结构b限制存储点的线性结构c链式存储的线性结构d限制存储点的非线性结构3、队列操作的原则是_______。a先进先出b后进先出c只能进行插入d只能进行删除4、数组A[0..5,0..6]的每个元素占5个单元，将其按列优先次序存储在起始地址为1000的连续的内存单元中，则元素A[5,5]的地址为_______。a1175b1180c1205d12005、对矩阵压缩存储是为了____。a方便运算b节省空间c方便存储d提高运算速度2、判断题1、在循环队列中，front指向队列中第一个元素的前一位置，rear指向实际的队尾元素，则队列为满的条件是front＝＝rear。（）2、在栈空的情况下，不能做退栈运算，否则产生下溢出。（）3、用一个带头结点的链表表示队列Q，front指向表头结点，rear指向表尾，则执行出队操作时front不变。（）4、循环队列只能用数组实现，而不能用链表实现。（）（×）1.线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。错，线性表是逻辑结构概念，可以顺序存储或链式存储，与元素数据类型无关。（×）2.在表结构中最常用的是线性表，栈和队列不太常用。错，不一定吧？调用子程序或函数常用，CPU中也用队列。（√）3.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。（√）4.对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。（×）5.栈和链表是两种不同的数据结构。错，栈是逻辑结构的概念，是特殊殊线性表，而链表是存储结构概念，二者不是同类项。（×）6.栈和队列是一种非线性数据结构。错，他们都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。（√）7.栈和队列的存储方式既可是顺序方式，也可是链接方式。）8.两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。（×）9.队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。错，后半句不对。（×）10.一个栈的输入序列是12345，则栈的输出序列不可能是12345。错，有可能。3、填空题1、设sq[0..maxsize]为一个顺序存储的栈，变量top指示栈顶元素的位置。能作入栈操作的条件是_______________。如要把栈顶元素弹出并送到