计算机专业基础综合数据结构栈和队列历年真题试卷汇编6_真题-无答案

计算机专业基础综合数据结构（栈、队列和数组）-试卷1(总分：70.00，做题时间：90分钟)一、单项选择题(总题数：21，分数：42.00)1.单项选择题1-40小题。

下列每题给出的四个选项中，只有一个选项是最符合题目要求的。

__________________________________________________________________________________________2.栈和队列的主要区别在于( )。

A.它们的逻辑结构不一样B.它们的存储结构不一样C.所包含的运算不一样D.插入和删除运算的限定不一样√栈和队列的逻辑结构都是线性的，都有顺序存储和链式存储，有可能包含的运算不一样，但不是其主要区别。

任何数据结构在针对具体问题时所包含的运算都可能不同。

所以正确答案是D。

3.若循环队列以数组Q[0.，m—1]作为其存储结构，变量rear表示循环队列中的队尾元素的实际位置，其移动按rear=(rear+1)MOD m进行，变量length表示当前循环队列中的元素个数，则循环队列的队首元素的实际位置是( )。

A.reat一lengthB.(rear—length+m)MOD mC.(rear—length+1+m)MOD m √D.m—length按照循环队列的定义，因为元素移动按照rear=(rear+1)MOD m进行，则当数组Q[m—1]存放了元素之后，下一个入队的元素将存放到Q[O]中，因此队列的首元素的实际位置是(rear—length+1+m)MOD m。

4.一个以向量V[n]存储的栈，其初始栈顶指针top为n+1，则对于x，其正确的进栈操作是( )。

A.top=top+1；V[top]=xB.V[top]=x；top=top+1C.top=top一1；V[top]=x √D.V[top]=x；top=top一1此题考查的知识点是入栈的具体操作。

操作时要看栈顶的地址，先取得空间，再入栈。

栈和队列习题及答案【篇一：栈和队列练习题答案】xt>一、填空题1. 线性表、栈和队列都是结构，可以在线性表的在栈顶插入和删除元素；对于队列只能在队尾插入和队首删除元素。

2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为。

不允许插入和删除运算的一端称为栈底。

3. 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。

二、判断正误（√）1. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。

（√）2. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。

正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。

错，他们都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。

（√）4. 栈和队列的存储方式既可是顺序方式，也可是链接方式。

（√）5. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。

错，有可能。

三、单项选择题（b）1.栈中元素的进出原则是Ａ．先进先出Ｂ．后进先出Ｃ．栈空则进Ｄ．栈满则出（c）2.若已知一个栈的入栈序列是1，2，3，?，n，其输出序列为p1，p2，p3，?，pn，若p1=n，则pi为Ａ．i Ｂ．n-iＣ．n-i+1 Ｄ．不确定解释：当p1=n，即n是最先出栈的，根据栈的原理，n必定是最后入栈的（事实上题目已经表明了），那么输入顺序必定是1，2，3，?，n，则出栈的序列是n，?，3，2，1。

（若不要求顺序出栈，则输出序列不确定）（d）3．数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为（Ａ）r－f; （Ｂ）（n＋f－r）% n; （Ｃ）n＋r－f;（Ｄ）（n＋r －f）% n e：①1 ②2 ③ 3 ④ 0四、阅读理解1. 【严题集3.3②】写出下列程序段的输出结果（栈的元素类型selem type为char）。

计算机专业基础综合数据结构（栈和队列）历年真题试卷汇编2(总分：64.00，做题时间：90分钟)一、单项选择题(总题数：15，分数：30.00)1.某表达式的前缀形式为：+-*ABCD／E／F+GH，它的中缀形式为( )。

【中国科学技术大学1992八、7(1分)】A.A B *C-D+E／F／G+HC.A B* C-D+E／(F／(G+H)) √D.A B*(C-D) +E/(G+H)2.表达式a * (b+c)一d的后缀表达式是( )。

【南京理工大学2001一、2(1．5分)】A.abcd * +一B.abc+ * d- √C.abc * +d-D.-+ * abcd3.与中缀表达式a * b+c／d-e等价的前缀表达式是( )。

【华中科技大学2006一、5(2分)】A.一+*ab／cde √B.*+／-abcdeC.abcde*+／一D.+*ab-／cde4.利用栈求表达式的值时，设立操作数栈OPND，设OPND只有两个存储单元，在下列表达式中，不发生上溢的是( )。

【四川大学2005】A.A-B*(C-D)B.(A-B)*C-D √C.(-B*C)一DD.(A一B)*(C-D)5.有六个元素6，5，4，3，2，1的顺序进栈，问下列哪一个不是合法的出栈序列?( )【北方交通大学2001一、3(2分)】A.5 4 3 6 12B.4 5 3 1 2 6C.3 4 6 5 2 1 √D.2 3 4 1 5 66.设栈的输入序列是1，2，3，4，则( )不可能是其出栈序列。

【中科院计算所2000一、10(2分)】【烟台大学2007一、4(2分)】A.1，2，4，3B.2，1，3，4C.1，4，3，2D.4，3，1，2 √E.3，2，1，47.四个元素1，2，3，4依次进栈，出栈次序不可能出现( )种情况。

【北京邮电大学2005一、1(2分)】A.1，2，3，4B.4，1，3，2 √C.1，4，3，2D.4，3，2，18.如进栈序列1，2，3，4，5。

计算机专业基础综合数据结构（栈和队列）历年真题试卷汇编2(总分：64.00，做题时间：90分钟)一、单项选择题(总题数：15，分数：30.00)1.某表达式的前缀形式为：+-*ABCD／E／F+GH，它的中缀形式为( )。

【中国科学技术大学1992八、7(1分)】A.A B *C-D+E／F／G+HC.A B* C-D+E／(F／(G+H)) √D.A B*(C-D) +E/(G+H)2.表达式a * (b+c)一d的后缀表达式是( )。

【南京理工大学2001一、2(1．5分)】A.abcd * +一B.abc+ * d- √C.abc * +d-D.-+ * abcd3.与中缀表达式a * b+c／d-e等价的前缀表达式是( )。

【华中科技大学2006一、5(2分)】A.一+*ab／cde √B.*+／-abcdeC.abcde*+／一D.+*ab-／cde4.利用栈求表达式的值时，设立操作数栈OPND，设OPND只有两个存储单元，在下列表达式中，不发生上溢的是( )。

【四川大学2005】A.A-B*(C-D)B.(A-B)*C-D √C.(-B*C)一DD.(A一B)*(C-D)5.有六个元素6，5，4，3，2，1的顺序进栈，问下列哪一个不是合法的出栈序列?( )【北方交通大学2001一、3(2分)】A.5 4 3 6 12B.4 5 3 1 2 6C.3 4 6 5 2 1 √D.2 3 4 1 5 66.设栈的输入序列是1，2，3，4，则( )不可能是其出栈序列。

【中科院计算所2000一、10(2分)】【烟台大学2007一、4(2分)】A.1，2，4，3B.2，1，3，4C.1，4，3，2D.4，3，1，2 √E.3，2，1，47.四个元素1，2，3，4依次进栈，出栈次序不可能出现( )种情况。

【北京邮电大学2005一、1(2分)】A.1，2，3，4B.4，1，3，2 √C.1，4，3，2D.4，3，2，18.如进栈序列1，2，3，4，5。

计算机专业基础综合数据结构（排序）历年真题试卷汇编1(总分72,考试时间90分钟)1. 单项选择题1. 下列序列中，( )是执行第一趟快速排序后所得的序列。

【福州大学1998一、9(2分)】A. [68，11，18，69] [23，93，73]B. [68，11，69，23] [18，93，73]C. [93，73][68，11，69，23，18]D. [68，11，69，23，18] [93，73]2. 适合并行处理的排序算法是( )。

【西安电子科技大学2005一、8(1分)】【电子科技大学2005一、8(1分)】A. 选择排序B. 快速排序C. 希尔排序D. 基数排序3. 一组记录的关键字为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为( )。

【北京交通大学2005一、8(2分)【燕山大学2001一、4(2分)】A. (38，40，46，56，79，84)B. (40，38，46，79，56，84)C. (40，38，46，56，79，84)D. (40，38，46，84，56，79)4. 下列排序算法中，( )算法可能会出现下面的情况：初始数据有序时，花费的时间反而最多。

【中南大学2005一、4(2分)】A. 快速排序B. 堆排序C. 希尔排序D. 冒泡排序5. 将一组无序的数据重新排列成有序序列，其方法有：( )。

【武汉理工大学2004一、8(3分)】A. 拓扑排序B. 快速排序C. 堆排序D. 基数排序6. 就平均性能而言，目前最好的内排序方法是( )排序法。

【西安电子科技大学1998一、9(2分)】A. 冒泡B. 希尔插，AC. 交换D. 快速7. 如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用( )方法最快。

【清华大学1998一、2(2分)】A. 起泡排序B. 快速排列C. Shell排序D. 堆排序E. 简单选择排序8. 若要从1000个元素中选出前10个最小的元素，( )是最适合的算法。

计算机专业基础综合数据结构（栈和队列）历年真题试卷汇编3(总分：48.00，做题时间：90分钟)一、综合题(总题数：3，分数：6.00)1.给出循环队列中元素个数的计算式(设队最大长度为N，队首指针FRONT，队尾指针REAR)【西北大学2000二、7(5分)】__________________________________________________________________________________________正确答案：(正确答案：循环队列中元素个数为(REAR—FRONT+N)％N。

其中FRONT是队首指针，指向队首元素的前一位置；REAR是队尾指针，指向队尾元素；N是队列最大长度。

)2.顺序队列一般应该组织成为环状队列的形式，而且一般队列头或尾其中之一应该特殊处理。

例如，队列为listarray[0,n一1】，队列头指针为front，队列尾指针为rear，则listarray[rear]表示下一个可以插入队列的位置。

请解释其原因。

【北京大学1999一、3(20／3分)】__________________________________________________________________________________________正确答案：(正确答案：循环队列解决了用向量表示队列所出现的“假溢出”问题，但同时又出现了如何判断队列的满与空问题。

例如：在队列长10的循环队列中，若假定队头指针front指向队头元素的前一位置，而队尾指针指向队尾元素，则ffon=3，rear=7的情况下，连续出队4个元素，则front==rear为队空；如果连续入队6个元素，则front==rear为队满。

如何判断这种情况下的队满与队空，一般采取牺牲一个单元的做法或设标记法。

即假设front==rear为队空，而(rear+1)％表长==front为队满，或通过设标记tag。

数据结构试题及答案(10套)数据结构试题及答案(10套)根据您的需求，我为您准备了10套数据结构试题及答案。

每套试题包含以下几个部分：选择题、填空题、编程题及答案解析。

下面是试题的具体内容：第一套试题：选择题：1. 在数据结构中，什么是栈？A. 先进先出（FIFO）的数据结构B. 后进先出（LIFO）的数据结构C. 随机访问的数据结构D. 无序排列的数据结构2. 以下哪种操作与队列的特性不相符？A. 入队操作B. 出队操作C. 查找操作D. 获取队首元素填空题：1. ______ 是一种动态集合，支持插入、删除和查找等操作。

2. 在二叉搜索树中，中序遍历的结果是________。

编程题：实现一个栈的数据结构，并包含以下操作：- push(x)：将元素 x 压入栈中- pop()：删除栈顶的元素并返回该元素- top()：获取栈顶元素的值- empty()：检查栈是否为空答案解析：选择题：B、C填空题：1. 集合 2. 升序序列编程题：略第二套试题：选择题：1. 以下哪个数据结构是一种广度优先搜索的应用？A. 栈B. 队列C. 堆D. 链表2. 在链表中，如果要删除一个节点，只给出该节点的指针，那么需要通过什么方式完成删除操作？A. 直接删除该节点B. 指向该节点的前一个节点的指针C. 指向该节点的后一个节点的指针D. 无法完成删除操作填空题：1. 树是一种________的数据结构。

2. 二叉树每个节点最多有______个子节点。

编程题：实现一个队列的数据结构，并包含以下操作：- enqueue(x)：将元素 x 入队- dequeue()：删除队首的元素并返回该元素- peek()：获取队首元素的值- is_empty()：检查队列是否为空答案解析：选择题：B、B填空题：1. 分层组织 2. 2编程题：略（以下部分省略）通过以上的题目，您可以对数据结构的知识点进行综合练习和复习。

每套试题包含了不同难度和类型的题目，能够帮助您全面了解和掌握数据结构的概念和操作。

数据结构历年真题及解析题一、选择题1. 下列关于数组的描述，正确的是（）。

A. 数组在内存中是连续存放的。

B. 数组一经定义，其长度不可改变。

C. 数组的每个元素可以是不同的数据类型。

D. 数组可以通过下标随机访问元素。

答案：A、B、D2. 链表相比于数组的优势在于（）。

A. 内存使用更高效。

B. 插入和删除操作更加方便。

C. 可以通过下标随机访问元素。

D. 存储空间可以动态分配。

答案：B、D3. 栈（Stack）的特点是（）。

A. 先进先出（FIFO）。

B. 后进先出（LIFO）。

C. 只能在一端进行插入和删除。

D. 可以通过索引随机访问元素。

答案：B、C4. 队列（Queue）与栈的主要区别在于数据的（）。

A. 存取方式。

B. 存储结构。

C. 操作速度。

D. 内存占用。

答案：A5. 二叉树的前序遍历的顺序是（）。

A. 根-左-右。

B. 左-根-右。

C. 右-根-左。

D. 根-右-左。

答案：A6. 快速排序算法的时间复杂度在最坏情况下是（）。

A. O(n)B. O(nlogn)C. O(n^2)D. O(n^3)答案：C7. 哈希表的冲突解决方法中，开放定址法的特点是（）。

A. 通过增加哈希表的大小来解决冲突。

B. 通过链表来链接具有相同哈希值的元素。

C. 寻找表中下一个空闲位置来存储冲突元素。

D. 重新计算哈希值，直到找到空闲位置。

答案：C8. 图的遍历算法中，深度优先搜索（DFS）与广度优先搜索（BFS）的主要区别在于（）。

A. DFS使用递归，BFS使用队列。

B. DFS使用栈，BFS使用递归。

C. DFS使用队列，BFS使用栈。

D. DFS和BFS都使用链表。

答案：A9. 堆（Heap）结构中，最大堆的性质是（）。

A. 父节点的值小于子节点。

B. 父节点的值大于子节点。

C. 父节点的值等于子节点。

D. 没有固定的大小关系。

答案：B10. 动态规划算法通常用于解决（）类型的问题。

A. 排序。

计算机专业基础综合数据结构（栈和队列）历年真题试卷汇编1(总分：56.00，做题时间：90分钟)一、综合题(总题数：24，分数：56.00)1.将两个栈S1和S2存入数组V[1．m]应如何安排最好?请写出栈顶指针top的初始值和判断栈空、栈满的条件是什么?【东南大学1998一、5(6分)】【烟台大学2007四、1(5分)】（分数：2.00）__________________________________________________________________________________________正确答案：(正确答案：设栈S1和栈S2共享向量V[1一m]，初始时，栈S1的栈顶指针top[0]=0，栈S2的栈顶指针top[1]=m+1，当top[0]=0时为左栈空，top[1]=m+1时为右栈空；当top[0]=0并且top[1]=m+1时为全栈空。

当top[1]-top[0]=1时为栈满。

)解析：2.若有一个一维数组A，它的元素下标从1开始到MAX。

要在数组A中建立两个栈共享同一空间，栈S1的栈顶指针为top1，栈S2的栈顶指针为top2，为了最大限度地利用数组A的空间，则应该如何共享?栈满和栈空的条件是什么?【北京理工大学2006十一、3(5分)】（分数：2.00）__________________________________________________________________________________________正确答案：(正确答案：两栈共享数组A，top1=0时S1栈空，top2=MAX+1时，S2栈空；top2一top1=1时栈满。

)解析：3.设输入序列为a，b，c，d，试写出借助一个栈可得到的两个输出序列和两个不能得到的输出序列。

【北京科技大学2001一、4(2分)】（分数：2.00）__________________________________________________________________________________________正确答案：(正确答案：n个元素的排列有n!种，但借助栈结构，n个入栈元素只可得到1／(n+1)((2n)!／(n!*n!))种出栈序列，这个数小于，l!。

计算机专业基础综合数据结构（栈和队列）历年真题试卷汇编4(总分：60.00，做题时间：90分钟)一、单项选择题(总题数：15，分数：30.00)1.当字符序列工作为下图输入时，输出长度为3的，且可用作C语言标识符的序列的有( )。

【浙江大学2004二(5分)】A.4个B.5个C.3个√D.6个2.和顺序栈相比，链栈有一个比较明显的优势是( )。

【北京理工大学2006五、6(1分)A.通常不会出现栈满的情况√B.通常不会出现栈空的情况C.插入操作更容易实现D.删除操作更容易实现3.若一个栈以向量V[1,n]存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是( )【南京理工大学1998一、13(2分)】A.top=top+1； V[top]=xB.V[top]=x；top=top+1C.top=top—1； V[top]=x √D.V[top]=x；top=top一14.若栈采用顺序存储方式存储，现两栈共享空间V[1，m]，top[i]代表第i个栈(i=1，2)栈顶栈1的底在V[1]，栈2的底在V[m]，则栈满的条件是( )。

【南京理工大学1999一、14(1分)】【江苏大学2005一、2(2分)】A.1top[2]一top[1]1=0B.top[1]+1=top[2] √C.top[1]+top[2]=mD.top[1]=top[2]5.栈在( )中应用。

【中山大学1998二、3(2分)】A.递归调用B.子程序调用C.表达式求值D.A，B，C √6.向一个栈顶指针为h的带头结点的链栈中插入指针S所指的结点时，应执行( )。

【北京理工大学2005十一、6(1分)】A.h->next=s；B.s一>next=h；C.s一>next=h；h一>next=s；D.s一>next=-h一>next；h一>next=s；√7.一个递归算法必须包括( )。

【武汉大学2000二、21A.递归部分B.终止条件和递归部分√C.迭代部分D.终止条件和迭代部分8.function calc(x，y：integer)：integer； begin if y=1 then calc：=x else calc：=calc(x，y一1)+x end；a、b均为正整数，则cale(a，b)=( )。