数据结构考试题库及答案.docx

1、数据结构考试题库及答案数据结构期末考试题库及答案 2018目 录第1章 绪论1选择题（1）数据结构是指（1. A ）。A.数据元素的组织形式 B.数据类型C.数据存储结构 D.数据定义（2）计算机内部数据处理的基本单位是（10. B ）。A.数据 B.数据元素 C.数据项 D.数据库（3）数据结构中，与所使用的计算机无关的是数据的 C 结构. A) 存储 B) 物理 C) 逻辑 D) 物理和存储【解析】解析 数据结构概念一般包括数据的逻辑结构、存储结构及数据上的运算集合等。数据的逻辑结构只抽象地反映数据元素之间的逻辑关系，而不管它在计算机中的存储形式。（4）算法分析的目的是_C_ A) 找出数

2、据结构的合理性 B) 研究算法中的输入和输出的关系 C) 分析算法的效率以求改进 D) 分析算法的易懂性和文档性 （5）计算机算法必须具备输入、输出和 B 等5个特性。 A) 可行性、可移植性和可扩充性 B) 可行性、确定性和有穷性 C) 确定性、有穷性和稳定性 D) 易读性、稳定性和安全性 （6）在数据结构中，从逻辑上可以把数据结构分成（ ）。A动态结构和静态结构 B紧凑结构和非紧凑结构C线性结构和非线性结构 D内部结构和外部结构答案：C（7）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（ ）。A存储结构 B存储实现C逻辑结构 D运算实现答案：C（8）通常要求同一逻辑结构中的所有

3、数据元素具有相同的特性，这意味着（ ）。 A数据具有同一特点B不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致C每个数据元素都一样D数据元素所包含的数据项的个数要相等答案：B（9）以下说法正确的是（ ）。A数据元素是数据的最小单位B数据项是数据的基本单位C数据结构是带有结构的各数据项的集合D一些表面上很不相同的数据可以有相同的逻辑结构答案：D解释：数据元素是数据的基本单位，数据项是数据的最小单位，数据结构是带有结构的各数据元素的集合。（10）算法的时间复杂度取决于（ ）。A问题的规模 B待处理数据的初态C计算机的配置 DA和B答案：D解释：算法的时间复杂度不仅与问题的规模有关

4、，还与问题的其他因素有关。如某些排序的算法，其执行时间与待排序记录的初始状态有关。为此，有时会对算法有最好、最坏以及平均时间复杂度的评价。（11）以下数据结构中，（ ）是非线性数据结构A树 B字符串 C队列 D栈答案：A2填空题01、数据结构是一门研究非数值计算的程序设计问题中计算机的(操作对象)以及它们之间的(关系和运算)等的学科。02、数据结构被形式地定义为(D,R)，其中D是(数据元素)的有限集合，R是D上的(关系)有限集合。03、数据结构包括数据的(逻辑结构)、数据的(存储结构)和数据的(运算)这三个方面的内容。04、数据结构按逻辑结构可分为两大类，它们分别是(线性结构)和(非线性结构

5、)。05、线性结构中元素之间存在(一对一)关系，树形结构中元素之间存在(一对多)关系，图形结构中元素之间存在(多对多)关系。06、在线性结构中，第一个结点(没有)前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点(没有)后续结点，其余每个结点有且只有1个后续结点。07、在树形结构中，树根结点没有(前驱)结点，其余每个结点有且只有(1)个前驱结点；叶子结点没有(后续)结点，其余每个结点的后续结点数可以(任意多个)。08、在图形结构中，每个结点的前驱结点数和后续结点数可以(任意多个)。09、对于给定的n个元素，可以构造出的逻辑结构有(集合)、(线性结构)、(树形结构)、(图状结构)四种。10

6、、数据的运算最常用的有5种，它们分别是(插入)、(删除)、(修改)、(查找)、(排序)。11、一个算法的效率可分为(时间)效率和(空间)效率。12、数据结构中评价算法的两个重要指标是算法的(时间复杂度)和(空间复杂度)。13、一个数据结构在计算机中的(映射)称为存储结构。14、算法的五个重要特性是(有穷性)、(确定性)、(可行性)、输入、输出。3判断题 01、数据元素是数据的最小单位。 02、数据的逻辑结构是指数据的各数据项之间的逻辑关系。 03、算法的优劣与算法描述语言无关，但与所用计算机有关。 04、健壮的算法不会因非法的输入数据而出现莫名其妙的状态。 05、算法可以用不同的语言描述，则算

7、法实际上就是程序了。 06、程序一定是算法。 07、数据的物理结构是指数据在计算机内的实际存储形式。 08、数据结构的抽象操作的定义与具体实现有关。 09、在顺序存储结构中，有时也存储数据结构中元素之间的关系。 10、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 11、数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。 12、数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构。第2章 线性表1选择题（1）顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ ）。A110 B108 C100 D120答案：B解释：顺序

8、表中的数据连续存储，所以第5个元素的地址为：100+2*4=108。（2）在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（ ）。A访问第i个结点（1in）和求第i个结点的直接前驱（2in） B在第i个结点后插入一个新结点（1in）C删除第i个结点（1in）D将n个结点从小到大排序答案：A解释：在顺序表中插入一个结点的时间复杂度都是O(n2)，排序的时间复杂度为O(n2)或O(nlog2n)。顺序表是一种随机存取结构，访问第i个结点和求第i个结点的直接前驱都可以直接通过数组的下标直接定位，时间复杂度是O(1)。（3） 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均

9、要移动 的元素个数为（ ）。A8 B63.5 C63 D7答案：B解释：平均要移动的元素个数为：n/2。（4）链接存储的存储结构所占存储空间（ ）。A分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B只有一部分，存放结点值C只有一部分，存储表示结点间关系的指针D分两部分，一部分存放结点值，另一部分存放结点所占单元数答案：A（5）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ ）。A必须是连续的 B部分地址必须是连续的C一定是不连续的 D连续或不连续都可以答案：D（6）线性表在（ ）情况下适用于使用链式结构实现。A需经常修改中的结点值 需不断对进行删除插入 C中含有大量的

10、结点 中结点结构复杂答案：B解释：链表最大的优点在于插入和删除时不需要移动数据，直接修改指针即可。（7）单链表的存储密度（ ）。A大于1 B等于1 C小于1 D不能确定答案：C解释：存储密度是指一个结点数据本身所占的存储空间和整个结点所占的存储空间之比，假设单链表一个结点本身所占的空间为D，指针域所占的空间为N，则存储密度为：D/(D+N)，一定小于1。（8）将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（ ）。An B2n-1 C2n Dn-1答案：A解释：当第一个有序表中所有的元素都小于（或大于）第二个表中的元素，只需要用第二个表中的第一个元素依次与第一个表的元素比较，总计

11、比较n次。（9）在一个长度为n的顺序表中，在第i个元素（1in+1）之前插入一个新元素时须向后移动（ ）个元素。An-i Bn-i+1 Cn-i-1 DI答案：B(10) 线性表L=(a1，a2,an)，下列说法正确的是（ ）。A每个元素都有一个直接前驱和一个直接后继B线性表中至少有一个元素C表中诸元素的排列必须是由小到大或由大到小D除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。答案：D(11) 创建一个包括n个结点的有序单链表的时间复杂度是（ ）。AO(1) BO(n) CO(n2) DO(nlog2n)答案：C解释：单链表创建的时间复杂度是O(n)，而要建立一

12、个有序的单链表，则每生成一个新结点时需要和已有的结点进行比较，确定合适的插入位置，所以时间复杂度是O(n2)。(12) 以下说法错误的是（ ）。 A求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低B顺序存储的线性表可以随机存取C由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活D线性表的链式存储结构优于顺序存储结构 答案：D解释：链式存储结构和顺序存储结构各有优缺点，有不同的适用场合。(13) 在单链表中，要将s所指结点插入到p所指结点之后，其语句应为（ ）。As-next=p+1; p-next=s;B(*p).next=s; (*s).next=

13、(*p).next;Cs-next=p-next; p-next=s-next;Ds-next=p-next; p-next=s; 答案：D (14) 在双向链表存储结构中，删除p所指的结点时须修改指针（ ）。Ap-next-prior=p-prior; p-prior-next=p-next;Bp-next=p-next-next; p-next-prior=p;Cp-prior-next=p; p-prior=p-prior-prior;Dp-prior=p-next-next; p-next=p-prior-prior;答案：A(15) 在双向循环链表中，在p指针所指的结点后插入q所指向

14、的新结点，其修改指针的操作是（ ）。Ap-next=q; q-prior=p; p-next-prior=q; q-next=q;Bp-next=q; p-next-prior=q; q-prior=p; q-next=p-next;Cq-prior=p; q-next=p-next; p-next-prior=q; p-next=q;Dq-prior=p; q-next=p-next; p-next=q; p-next-prior=q;答案：C2填空题1. 线性表是一种典型的_结构。1线性 2. 在一个长度为n的顺序表的第i个元素之前插入一个元素，需要后移_个元素。2n-i+1 3. 顺序表

15、中逻辑上相邻的元素的物理位置_。3相邻 4. 要从一个顺序表删除一个元素时，被删除元素之后的所有元素均需_一个位置，移动过程是从_向_依次移动每一个元素。4前移，前，后5. 在线性表的顺序存储中，元素之间的逻辑关系是通过_决定的；在线性表的链接存储中，元素之间的逻辑关系是通过_决定的。5物理存储位置，链域的指针值 6. 在双向链表中，每个结点含有两个指针域，一个指向_结点，另一个指向_结点。6前趋，后继7. 当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用_存储结构为宜。相反，当经常进行的是插入和删除操作时，则采用_存储结构为宜。7顺序，链接 8. 顺序表中逻辑上相邻的元素，

16、物理位置_相邻，单链表中逻辑上相邻的元素，物理位置_相邻。8一定，不一定9. 在单链表中设置头结点的作用是_。9使空表和非空表统一；算法处理一致3判断题（ ）1. 链表的每个结点中都恰好包含一个指针。 （ ）2. 链表的物理存储结构具有同链表一样的顺序。 （ ）3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动将后续各个单元向前移动。 （ ）4. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 （ ）5. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 （ ）6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 （ ）7. 线性表在

17、物理存储空间中也一定是连续的。 （ ）8. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。 （ ）9. 顺序存储方式只能用于存储线性结构。 （ ）10. 线性表的逻辑顺序与存储顺序总是一致的。 第3章 栈和队列1选择题（1）设有一个栈，元素的进栈次序为A, B, C, D, E,下列是不可能的出栈序列（C）。 AA, B, C, D, E BB, C, D, E, ACE, A, B, C, D DE, D, C, B, A （2）若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（ ）种情况。A5，4，3，2，1 B2，1，5，4，3 C4，3，1，2，5 D2

18、，3，5，4，1答案：C解释：栈是后进先出的线性表，不难发现C选项中元素1比元素2先出栈，违背了栈的后进先出原则，所以不可能出现C选项所示的情况。（3）若已知一个栈的入栈序列是1，2，3，n，其输出序列为p1，p2，p3，pn，若p1=n，则pi为（ ）。Ai Bn-i Cn-i+1 D不确定答案：C解释：栈是后进先出的线性表，一个栈的入栈序列是1，2，3，n，而输出序列的第一个元素为n，说明1，2，3，n一次性全部进栈，再进行输出，所以p1=n，p2=n-1，pi=n-i+1。（4）栈中元素的进出原则是（ B ） 先进先出 后进先出 栈空则进 栈满则出 （5）在一个具有n个单元的顺序栈中，假

19、定以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为（C ）。 Atop不变 Btop=0 Ctop- Dtop+（6） 向一个栈顶指针为hs的链栈中插入一个s结点时，应执行（B）。 Ahs-next=s; Bs-next=hs; hs=s;Cs-next=hs-next;hs-next=s; Ds-next=hs; hs=hs-next; （7） 在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为（D）。Arearn= = front B（front+l）n= = rearCrearn -1= = fro

20、nt D(rear+l)n= = front（8）在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为（C）。 Arearn= = front Bfront+l= rearCrear= = front D(rear+l)n= front（9）在一个链队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操作为（A）。Afront=front-next Brear=rear-nextCrear=front-next Dfront=rear-next（10）数组用来表示一个循环队列，为当前队列头元素的前一位置，为队尾元素的位置，

21、假定队列中元素的个数小于，计算队列中元素个数的公式为（ ）。Ar-f B(n+f-r)%n Cn+r-f D（n+r-f)%n答案：D解释：对于非循环队列，尾指针和头指针的差值便是队列的长度，而对于循环队列，差值可能为负数，所以需要将差值加上MAXSIZE（本题为n），然后与MAXSIZE（本题为n）求余，即（n+r-f)%n。（11）链式栈结点为：(data,link)，top指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作（ ）。Ax=top-data;top=top-link； Btop=top-link;x=top-link； Cx=top;top=top-link

22、； Dx=top-link；答案：A解释：x=top-data将结点的值保存到x中，top=top-link栈顶指针指向栈顶下一结点，即摘除栈顶结点。（12）栈在（ ）中有所应用。A递归调用 B函数调用 C表达式求值 D前三个选项都有答案：D解释：递归调用、函数调用、表达式求值均用到了栈的后进先出性质。（13）为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ ）。A队列 B栈 C 线性表 D有序表答案：A解释：解决缓冲区问题应利用一种先进先出的线性表，而队列正是一种先进先出的线

23、性表。（14）设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（）。A2 B3 C4 D 6答案：B解释：元素出队的序列是e2、e4、e3、e6、e5和e1，可知元素入队的序列是e2、e4、e3、e6、e5和e1，即元素出栈的序列也是e2、e4、e3、e6、e5和e1，而元素e1、e2、e3、e4、e5和e6依次进入栈，易知栈S中最多同时存在3个元素，故栈S的容量至少为3。（15）若一个栈以向量V1.n存储，初始栈顶指针top设为n+1，则元素x进栈的正确操

24、作是( )。Atop+; Vtop=x; BVtop=x; top+;Ctop-; Vtop=x; DVtop=x; top-;答案：C解释：初始栈顶指针top为n+1，说明元素从数组向量的高端地址进栈，又因为元素存储在向量空间V1.n中，所以进栈时top指针先下移变为n，之后将元素x存储在Vn。（16）设计一个判别表达式中左，右括号是否配对出现的算法，采用（）数据结构最佳。A线性表的顺序存储结构 B队列 C. 线性表的链式存储结构 D. 栈答案：D解释：利用栈的后进先出原则。（17）用链接方式存储的队列，在进行删除运算时（）。A. 仅修改头指针 B. 仅修改尾指针C. 头、尾指针都要修改 D

25、. 头、尾指针可能都要修改答案：D解释：一般情况下只修改头指针，但是，当删除的是队列中最后一个元素时，队尾指针也丢失了，因此需对队尾指针重新赋值。（18）循环队列存储在数组A0.m中，则入队时的操作为（）。A. rear=rear+1 B. rear=(rear+1)%(m-1) C. rear=(rear+1)%m D. rear=(rear+1)%(m+1) 答案：D解释：数组A0.m中共含有m+1个元素，故在求模运算时应除以m+1。（19）最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（）。 A. (rear+1)%n=front B. rear=front

26、 Crear+1=front D. (rear-l)%n=front答案：B解释：最大容量为n的循环队列，队满条件是(rear+1)%n=front，队空条件是rear=front。（20）栈和队列的共同点是（）。A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点答案：C解释：栈只允许在栈顶处进行插入和删除元素，队列只允许在队尾插入元素和在队头删除元素。（21）一个递归算法必须包括（）。A. 递归部分 B. 终止条件和递归部分C. 迭代部分 D. 终止条件和迭代部分答案：B2填空题1. 线性表、栈和队列都是（线性）结构，可以在线性表的（任何）位置插入和

27、删除元素；对于栈只能在（栈顶）位置插入和删除元素，不允许插入和删除运算的一端称为（栈底）。；对于队列只能在（队尾）位置插入元素和在（队头）位置删除元素。 2. 对于一个栈作进栈运算时，应先判别栈是否为（栈满），作退栈运算时，应先判别栈是否为（栈空），当栈中元素为m时，作进栈运算时发生上溢，则说明栈的可用最大容量为（m）。为了增加内存空间的利用率和减少发生上溢的可能性，由两个栈共享一片连续的内存空间时，应将两栈的（栈底）分别设在这片内存空间的两端，这样只有当（两个栈的栈顶在栈空间的某一位置相遇）时才产生上溢。3. 设有一空栈，现有输入序列1，2，3，4，5，经过push, push, pop,

28、push, pop, push, push后，输出序列是（2、3）。4.（队列）是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。 5.在具有 n 个单元的循环队列中，队满时共有（ n - 1） 个元素。 解析：因为如果放置n个元素，首尾指针指向同一位置，与空队列无法区别，所以循环队列中认为当尾指针的后一个指针为首指针时，判定队列为满队列，即只能保存n-1个元素6.带表头结点的空循环双向链表的长度等于（ 0）。 3判断题（ ）1. 在表结构中最常用的是线性表，栈和队列不太常用。 （ ）2. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （

29、 ）3. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。 （ ）4. 栈和链表是两种不同的数据结构。 （ ）5. 栈和队列是一种非线性数据结构。 （ ）6. 栈和队列的存储方式既可是顺序方式，也可是链接方式。 （ ）7. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。 （ ）8. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 （ ）9. 一个栈的输入序列是 12345，则栈的输出序列不可能是 12345。第4章 串、数组和广义表1选择题（1）串是一种特殊的线性表，其特殊性体现在（ ）。 A可以顺序存储 B数据元素是一个字符 C可以链式存储 D数据元素可以是多个字符若 答案：B（2）串下面关于串的的叙述中，（ ）是不正确的？ A串是字符的有限序列 B空串是由空格构成的串C模式匹配是串的一种重要运算 D串既可以采用顺序存储，也可以采用链式存储答案：B解释：空格常常