计算机专业基础综合数据结构(栈和队列)历年真题试卷汇编6

计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编6(总分：88.00，做题时间：90分钟)一、单项选择题(总题数：33，分数：66.00)1.一棵完全二叉树又是一棵( )。

【华中科技大学2006一、7(2分)】A.平衡二叉树B.堆√C.二叉排序树D.哈夫曼(Huffman)树完全二叉树的叶子至多在下面两层上，且一个结点若无左子树，绝不能有右子树。

平衡二叉树任何结点的左右子树的高度差的绝对值不超过1，但其结点的值符合二叉排序树的定义。

平衡二叉树(包括二叉排序树)的树形不一定是完全二叉树。

堆是一个序列，有大堆和小堆，编号为i的结点，其父结点、左右子女结点之间位置的关系，符合完全二叉树父结点、左右子女结点之间的关系，从这点上说，可以把堆看成完全二叉树。

哈夫曼树是二叉树，但树形不一定满足完全二叉树的定义。

2.一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是( )。

【合肥工业大学1999一、5(2分)】A.不确定B.0C.1D.2 √左子树为空的二叉树的根结点的左线索为空(无前驱)，先序序列的最后结点的右线索为空(无后继)，共2个空链域。

3.一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是( )。

【合肥工业大学2000一、5(2分)】A.0B.1 √C.2D.不确定4.若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为( )。

【南京理工大学1996一、6(2分)】A.X的双亲B.X的右子树中最左的结点C.X的左子树中最右结点√D.X的左子树中最右叶结点5.引入二叉线索树的目的是( )。

【南京理工大学1998一、5(2分)】A.加快查找结点的前驱或后继的速度√B.为了能在二叉树中方便地进行插入与删除C.为了能方便地找到双亲D.使二叉树的遍历结果唯一6.线素二叉树是一种( )结构。

【西安电子科技大学1996一、9(2分)】A.逻辑B.逻辑和存储C.物理√D.线性7.甩个结点的线索二叉树上含有的线索数为( )。

计算机专业基础综合数据结构（集合）历年真题试卷汇编6(总分：58.00，做题时间：90分钟)一、填空题(总题数：7，分数：14.00)1.已知N元整型数组a存放N个学生的成绩，已按由大到小排序，以下算法是用对分(折半)查找方法统计成绩大于或等于x分的学生人数，请填空使之完善。

#define N／*学生人数*／intuprx(int a[N]，int x) ／*函数返回大于等于x分的学生人数*／ {int head=1，mid，rear=N; do{mid=(head+rear)／2；if(x<=a[mid]) (1) else(2); }while((3))； if(a[head]（分数：2.00）__________________________________________________________________________________________ 正确答案：(正确答案：(1)head=mid+1 (2)rear=mid-1 (3)head≤rear／／编者注：参数应为a[N+1])解析：2.下列程序段search(a，n，k)在数组a的前n(n≥1)个元素中找出第k(1≤k≤n)小的值。

这里假设数组a 中各元素的值都不相同，请填上适当的语句使得整个程序完整。

define NAXN 100 int a[MAXN]，n，k；int search(int a[]，int n，int k) {intlow，high，i，j，m，t；k--，low=0；j=high；do(t=a[ltow]；i=low j=high； do{while(i<j＆&t<j&&t>=a[j])i++； if(i（分数：2.00）__________________________________________________________________________________________ 正确答案：(正确答案：(1)il=k (2)i+1 (3)i一1 (4)il=k)解析：3.下列算法是利用折半查找算法在一个有序表中插入一个元素X，并保持表的有序性。

栈和队列习题及答案【篇一：栈和队列练习题答案】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。

计算机专业基础综合数据结构（栈和队列）历年真题试卷汇编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。

计算机专业基础综合数据结构（栈和队列）历年真题试卷汇编7(总分：74.00，做题时间：90分钟)一、单项选择题(总题数：19，分数：38.00)1.若循环队列使用C数组A[m]存放其数据元素，已知头指针front指向队首元素，尾指针rear指向队尾元素后的空单元，则当前队列中的元素个数为( )。

【华中科技大学2007一、3(2分)】A.(rear—front+m)％m √B.rear-front+1C.rear-frontD.rear-front-12.设顺序队列的容量为MaxSize，其头指针为front，尾指针为rear，空队列的条件为( )。

【电子科技大学2008一、4(2分)】A.front=rear √B.front=-MaxSizeC.front+1=rearD.rear=03.循环队列存储在数组A[0．m]中，则入队时的操作为( )。

【中山大学1999一、6(1分)】A.rear=rear+1B.rear=(rear-H)mod(m一1)C.rear=(rear+1)modmD.rear=(rear+1)mod(m+1) √4.若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少?( )【浙江大学1999四、1(4分)】A.1和5B.2和4 √C.4和2D.5和15.已知输入序列为abcd，经过输出受限的双向队列后能得到的输出序列有( )。

【西安交通大学1996三、3(3分)】A.dacbB.cadbC.dbcaD.bdacE.以上答案都不对√双端队列的输出序列求解见四、36。

6.若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是( )。

【西安电子科技大学1996一、5(2分)】【烟台大学2007一、5(2分)】A.1234B.4132C.4231 √D.42137.最大容量为n的循环队列，队尾指针是rear，队头是frunt，则队空的条件是( )。

计算机专业基础综合数据结构（栈和队列）历年真题试卷汇编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)=( )。

数据结构历年真题1. 题目描述：数据结构是计算机科学中的基础课程之一，掌握好数据结构对于编写高效、可维护和可扩展的程序至关重要。

为了帮助大家更好地准备数据结构考试，下面将介绍一些历年的真题，并提供相应的解答和讲解，希望能对大家有所帮助。

2. 栈和队列问题：真题1：给定一个整数数组，按照先入后出的原则，设计一个栈，实现获取最小值的操作。

解答：可以使用一个辅助栈来保存当前栈中的最小值。

每次入栈操作时，将当前元素与辅助栈栈顶元素进行比较，如果更小，则将当前元素入栈到辅助栈中；如果更大，则将辅助栈栈顶元素再次入栈到辅助栈中。

出栈操作时则同时将辅助栈中的元素也出栈。

真题2：给定一个整数数组，要求使用队列实现一个栈。

解答：可以使用两个队列来实现一个栈。

首先将元素入队到其中一个队列中，然后将另一个队列中的元素全部出队并入队到第一个队列中，这样第一个队列中的最后一个元素即为栈顶元素。

入栈操作时，将元素直接入队到非空的队列中。

出栈操作时，则将非空队列中的元素全部除最后一个元素外出队并入队到另一个队列中，最后一个元素即为出栈元素。

3. 链表问题：真题3：给定一个链表，要求实现一个算法，删除链表中倒数第n个节点。

解答：可以使用双指针法来解决该问题。

首先定义两个指针slow和fast，初始时都指向链表的头节点。

然后将fast指针向后移动n个位置，此时slow和fast之间的距离为n。

接着同时移动slow和fast指针，直到fast指针到达链表末尾。

此时slow指针所指向的节点即为要删除的节点的前一个节点，将其与要删除的节点的下一个节点相连即可。

真题4：给定两个链表，求它们的交点。

解答：可以使用双指针法来解决该问题。

首先定义两个指针p1和p2，分别指向两个链表的头节点。

然后同时移动p1和p2指针，当某个指针到达链表末尾时，将其重新指向另一个链表的头节点。

继续移动指针直到两个指针指向同一个节点或者都指向NULL。

若两个指针指向同一个节点，则该节点即为交点；若两个指针都指向NULL，则说明两个链表没有交点。

计算机专业基础综合数据结构（栈和队列）历年真题试卷汇编5(总分：80.00，做题时间：90分钟)一、单项选择题(总题数：28，分数：56.00)1.对于栈操作数据的原则是____。

【青岛大学2001年】A.先进先出B.后进先出√C.后进后出D.不分顺序考查栈的概念。

栈是一种后进先出的数据结构。

2.在初始为空的堆栈中依次插入元素f，e，d，c，b，a以后，连续进行了三次删除操作，此时栈项元素是____。

【北京航空航天大学2002年】A.cB.d √C.bD.e考查栈的基本性质。

数据入栈时，先入栈的元素后出栈，只需简单地画图即可看出栈顶元素应是d。

3.六个不同元素依次进栈，能得到____种不同的出栈序列。

【北京邮电大学2007年】A.42B.82C.132 √D.192考查栈的基本性质。

设有n个不同元素时，有f(n)种出栈序列。

若第一个元素是第i个出栈的，则在这个元素之前是编号为2～i的元素出栈，之后是编号为i+1～n的元素出栈。

所以第一个元素是第i个出栈对应f(i-1)*f(n—i)种出栈顺序。

f(1)=1 f(2)=2 f(3)=f(2)+f(1)*f(1)+f(2)=5 f(4)=f(3)+f(1)+f(2)十f(2)+f(1)+f(3)=14 f(5)=f(4)+(1)+f(3)+“2)+f(2)+f(3)*(1)+f(4)=42f(6)=f(5)+(1)+f(4)+f(2)+f(3)+f(3),f(2)+f(4)+f(1)+f(5)=42+14+10+10+14+42=1324.入栈序列为1，2，3，4，5，则可能得到的出栈序列是____。

【上海交通大学2005】A.12534B.31254C.32541 √D.14235考查栈的性质。

C的情况是由以下操作得到：1、2、3先入栈，接着3弹栈，2弹栈，然后4、5入栈，5弹栈，4弹栈，最后1弹栈。

其他各种情况，都不可能由栈的操作得到。

5.一个栈的输入序列为1，2，3，4，5，则下列序列中不可能是栈的输出序列的是____。

计算机专业基础综合数据结构（图）历年真题试卷汇编6(总分60,考试时间90分钟)1. 单项选择题1. 有n个顶点、e条边的图G采用邻接表存储，则拓扑排序算法的时间复杂度为( )。

【南京理工大学2005一、2(1分)】A. O(n)B. O(n+e)C. O(n*e)D. O(n2)2. 在下列网中，( )是边不带权值的图。

【华南理工大学2007】A. 邮电图B. AOV网C. 公路网D. AOE网3. 关键路径是AOE网中( )。

【中南大学2003一、10(1分)】A. 从始点到终点的最短路径B. 从始点到终点的最长路径C. 从始点到终点的边数最多的路径D. 从始点到终点的边数最少的路径4. 下面关于求关键路径的说法不正确的是( )。

【南京理工大学1998一、12(2分)】A. 求关键路径是以拓扑排序为基础的B. 一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同C. 一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差D. 关键活动一定位于关键路径上5. 下列关于AOE网的叙述中，不正确的是( )。

【北方交通大学1999一、7(3分)】【北京工业大学1999一、1(2分)】【哈尔滨工业大学2004二、3(1分)】A. 关键活动不按期完成就会影响整个工程的完成时间B. 任何一个关键活动提前完成，那么整个工程将会提前完成C. 所有的关键活动提前完成，那么整个工程将会提前完成D. 某些关键活动若提前完成，那么整个工程将会提前完成6. 下列有关图的说法错误的是( )。

【中南大学2003二、19(1分)】A. 在有向图中，出度为0的结点称为叶子B. 用邻接矩阵表示图，容易判断任意两个结点之间是否有边相连，并求得各结点的度C. 按深度方向遍历图和先根次序遍历树类似，得到的结果是唯一的D. 若有向图G中从结点Vi到结点Vj有一条路径，则在图G的结点的线性序列中结点Vi 必在结点Vj之前的话，则称为一个拓扑序列2. 填空题1. 若一个具有n个顶点、e条边的无向图是一个森林，则该森林中必有__________棵树。

计算机专业基础综合数据结构（图）历年真题试卷汇编6(总分：60.00，做题时间：90分钟)一、单项选择题(总题数：6，分数：12.00)1.有n个顶点、e条边的图G采用邻接表存储，则拓扑排序算法的时间复杂度为( )。

【南京理工大学2005一、2(1分)】（分数：2.00）A.O(n)B.O(n+e)C.O(n * e)D.O(n 2 )2.在下列网中，( )是边不带权值的图。

【华南理工大学2007】（分数：2.00）A.邮电图B.AOV网C.公路网D.AOE网3.关键路径是AOE网中( )。

【中南大学2003一、10(1分)】（分数：2.00）A.从始点到终点的最短路径B.从始点到终点的最长路径C.从始点到终点的边数最多的路径D.从始点到终点的边数最少的路径4.下面关于求关键路径的说法不正确的是( )。

【南京理工大学1998一、12(2分)】（分数：2.00）A.求关键路径是以拓扑排序为基础的B.一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同C.一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差D.关键活动一定位于关键路径上5.下列关于AOE网的叙述中，不正确的是( )。

【北方交通大学1999一、7(3分)】【北京工业大学1999一、1(2分)】【哈尔滨工业大学2004二、3(1分)】（分数：2.00）A.关键活动不按期完成就会影响整个工程的完成时间B.任何一个关键活动提前完成，那么整个工程将会提前完成C.所有的关键活动提前完成，那么整个工程将会提前完成D.某些关键活动若提前完成，那么整个工程将会提前完成6.下列有关图的说法错误的是( )。

【中南大学2003二、19(1分)】（分数：2.00）A.在有向图中，出度为0的结点称为叶子B.用邻接矩阵表示图，容易判断任意两个结点之间是否有边相连，并求得各结点的度C.按深度方向遍历图和先根次序遍历树类似，得到的结果是唯一的D.若有向图G中从结点Vi到结点Vj有一条路径，则在图G的结点的线性序列中结点V i必在结点V j之前的话，则称为一个拓扑序列二、填空题(总题数：10，分数：20.00)7.若一个具有n个顶点、e条边的无向图是一个森林，则该森林中必有__________棵树。

计算机专业基础综合数据结构（栈和队列）历年真题试卷汇编6(总分：60.00，做题时间：90分钟)一、单项选择题(总题数：14，分数：28.00)1.为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。

该缓冲区的逻辑结构应该是( )。

【2009年全国试题1(2)分】（分数：2.00）A.栈B.队列√C.树D.图解析：2.设栈S和队列Q的初始状态均为空，元素a，b，c，d,e,j,g=g依次进入栈S。

若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是b，d，c，f，e，a，g，则栈S的容量至少是( )。

【2009年全国试题2(2)分】（分数：2.00）A.1B.2C.3 √D.4解析：解析：按元素出队顺序计算栈的容量。

b进栈时栈中有a，b出栈，cd进栈，栈中有acd，dc出栈，ef进栈，栈中有aef,fea出栈，栈空，g进栈后出栈。

所以栈S的容量至少是3。

3.若元素a，b，c，d,e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是( )。

【2010年全国试题1(2)分】（分数：2.00）A.d,c，e，b，f,aB.c，b，d,a，e，fC.b，c，a，e，f，dD.a,f，e,d,c，b √解析：4.某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作。

若元素a，b，c，d，e依次入此队列后再进行出队操作，则不可能得到的出队序列是( )。

【2010年全国试题2(2)分】（分数：2.00）A.b，a，c，d, eB.d,b，a，c，eC.d，b,c，a，e √D.e，c，b，a，d解析：解析：a先入队，b和c可在a的任一端入队，选项A、B、D都符合要求，只有选项C不可能出现。

双端队列出队结果的分析可参见四、36。

5.元素a，b，c，d,e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是( )。

数据构造试卷〔一〕一、单项选择题〔每题 2 分，共20分〕1.栈和队列的共同特点是( a )。

A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2.用链接方式存储的队列，在进展插入运算时( d ).A. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改3.以下数据构造中哪一个是非线性构造？( d )A. 队列B. 栈C. 线性表D. 二叉树4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。

cA．688 B．678 C．692 D．6965.树最适合用来表示( c )。

A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.二叉树的第k层的结点数最多为( d ).A．2k-1 B.2K+1 C.2K-1 D. 2k-17.假设有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进展二分查找，那么查找A［3］的比拟序列的下标依次为( c d)A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，38.对n个记录的文件进展快速排序，所需要的辅助存储空间大致为 cA. O〔1〕B. O〔n〕C. O〔1og2n〕D. O〔n2〕9.对于线性表〔7，34，55，25，64，46，20，10〕进展散列存储时，假设选用H〔K〕=K %9作为散列函数，那么散列地址为1的元素有〔 c d〕个，A．1 B．2 C．3 D．410.设有6个结点的无向图，该图至少应有( a )条边才能确保是一个连通图。

二、填空题〔每空1分，共26分〕1.通常从四个方面评价算法的质量：____时间正确性_____、____占用内存_易读性____、____复杂度__强壮性___和_____准确度_ 高效率___。