事业单位招录计算机专业知识（数据结构与算法）模拟试卷1

事业单位招录计算机专业知识（数据结构与算法）模拟试卷1一、单项选择题(本题共24题，每题1.0分，共24分。)1、双向链表中有两个指针域llink和rlink，分别指向前驱和后继，设p指向表中的一个结点，q指向一待插入结点，现要求在p前插入q，则正确的插入为()。A、p→llinkB、q→llink→—＞＜—p→llink；p—＞llink—＞dink—＞＜—q；q—＞llink—＞＜—p—＞llinkC、q→rlink→dink—－＞＜—q；p—＞rlink—＞＜q；p—＞llink—＞rlink—＞＜—p；D、p→link→rlink—－＞＜—q；q—＞rlink—＞＜—p；q—＞llink—＞＜—p—＞llink；p—＞1link—＞＜—q标准答案：D知识点解析：p→llink→rlink＝q；q→rlink＝p；q→link＝p→llink；p→link＝q。2、假设执行语句S的时间为0(1)，则执行下列程序段的时间为()。for(i＝1；i＜＝n；i＋＋)for(j＝1；j＜＝n；j＋＋)S：A、O(n)B、O(n^2)C、O(n＊i)D、O(n＋1)标准答案：B知识点解析：观察可知，程序段S的执行频度为T(n)＝n＾2，得时间复杂度T(n)＝O(n^2)。3、广义表中的元素可以是原子，也可以是表，因此广义表的适用存储结构是()。A、散列表B、静态数组C、动态数组D、链表标准答案：D知识点解析：暂无解析4、线性表采用链接存储时，其地址()。A、必须是连续的B、部分地址必须是连续的C、一定是不连续的D、连续与否均可以标准答案：D知识点解析：线性表的链接存储是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以连续，也可以不连续，甚至可以零散分布在内存中任意位置。5、在有n个结点的二叉链表中，值为非空的链域的个数为()。A、n－1B、2n－1C、n＋1D、2n＋1标准答案：A知识点解析：本题考查的是二叉树的链式存储。由于在有n个结点的二叉链表中，值为空的链域的个数为n＋1个，而总的链域为2n(在二叉树中每个结点头2个链域)。所以，非空的链域的个数为2n－(n＋1)＝n－1。6、下列与数据元素有关的叙述中，哪一项是不正确的()。A、数据元素是数据的基本单位，即数据集合中的个体B、数据元素是由独立含义的数据最小单位C、数据元素又称为节点D、数据元素又称为记录标准答案：B知识点解析：数据元素是数据的基本单位，即数据集合中的个体。有些情况下也把数据元素称为节点、记录、表目等。一个数据元素可由一个或多个数据项组成，数据项是由独立含义的数据最小单位。7、在一个单链表中，若p所指的结点不是最后结点，则删除p所指的结点的后继结点的正确操作是()。A、p＝p－＞nextB、p－＞next＝p－＞nextC、p－＞next＝p－＞next－＞nextD、p－＞next＝p标准答案：C知识点解析：本题考查的是单链表的删除操作。在已知链表中元素插入或删除确切位置的情况下，在单链表中插入或删除一个结点时，仅需修改指针而无须移动元素。8、对于只在表的首尾两端进行插入操作的线性表，宜采用的存储结构是()。A、顺序表B、用头指针表示的单循环链表C、用尾指针表示的单循环链表D、单链表标准答案：C知识点解析：本题考查的是线性表的插入与删除操作。当线性表用尾指针表示的单循环链表存储时，很容易找到线性表的首、尾元素。此时，尾指针的后继即是线性表的首端。9、链表不具有的特点是()。A、不必事先估计存储空间B、可随机访问任一元素C、插入删除不需要移动元素D、所需空间与线性表长度成正比标准答案：B知识点解析：链表采用的是链式存储结构，它克服了顺序存储结构的缺点：①它的结点空间可以动态申请和释放；②它的数据元素的逻辑次序靠结点的指针来指示，不需要移动数据元素。但是链式存储结构也有不足之处：①每个结点中的指针域需额外占用存储空间；②链式存储结构是一种非随机存储结构。10、链表不具有的特点是()。A、可随机访问任意元素B、不必事先估计存储空间C、插入数据元素时不需要移动数据元素D、删除数据元素时不需要移动数据元素标准答案：A知识点解析：顺序链表不可以随机访问任意元素。11、在向下生成的堆栈中，如果入栈指令PUSHX的操作定义为：S←(SP)＋1，M(SP)←M(X)，则出栈指令POPX应定义为()。A、SP←(SP)－1，M(X)←M(SP)B、SP←(SP)＋1，M(X)←M(SP)C、M(X)←M(SP)，SP←(SP)－1D、M(X)←M(SP)，SP←(SP)＋1标准答案：C知识点解析：入栈是先定位栈顶指针然后存储数据，出栈是先出数据，然后再定位栈顶指针。12、设一个栈的输入序列是1、2、3、4、5，则下列序列中，是栈的合法输出序列的是()。A、51234B、45123C、43125D、32154标准答案：D知识点解析：栈的进出原则是先进后出原则，要不就是先进先出原则。A选项中5最先出，说明1234都在栈里，这样说明1是在栈低，则先不出来。BD的原因一样，所以答案选择D。13、对于长度为m(m＞1)的指定序列，通过初始为空的一个栈、一个队列后，错误的叙述是()。A、入栈序列与出栈序列关系为1：1，而入队序列与出队序列关系是1：n(n≥1)B、若入栈和入队的序列相同，则出栈序列和出队序列可以互为逆序C、入队序列与出队序列关系为1：1，而入栈序列与出栈序列关系是1：n(n≥1)D、若入栈和入队的序列相同，则出栈序列和出队序列可能相同标准答案：A知识点解析：队列的元素按特点是先进先出。对于队列，元素的进入次序和出队的次序相同，例如，入队的序列为a、b、c，则出队的序列也为a、b、c。对于栈则不同，栈的运算特点是后进先出。若入栈序列为a、b、c，则出栈序列可能为a、b、c，a、c、b，b、a、c，b、c、a或者c、b、a，而c、a、b则不行，因此，入栈序列与出栈序列关系为1：1，而入队序列与出队序列关系为1：n(n≥1)。14、当利用大小为n的数组顺序存储一个栈时，假定top＝n表示栈空，则向这个栈插入一个元素时，首先应该执行下列哪个语句修改的top指针()。A、top＋＋1B、top－－C、top＝0D、top标准答案：B知识点解析：暂无解析15、设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，1个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3，e6，e5，e1，则栈S的容量至少应该是()。A、6B、4C、3D、2标准答案：C知识点解析：根据栈的性质(LIFO)得，e2出栈前，栈中存有e1和e2两个元素，e4出栈前，栈中存有e1、e3和e43个元素，e4和e3出栈以后，e5和e6入栈，栈中同样存在e1、e5和e63个元素，然后3个元素依次出栈，所以栈的容量至少应该为3。16、假设以S和X分别表示进栈和出栈操作，则对输入序列a，B，c，d，E进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为()。A、B，c，E，d，aB、B，E，e，a，dC、E，c，B，d，aD、c，E，B，a，d标准答案：A知识点解析：a，B进栈(SS)，B出栈(X)，输出“B”，c进栈(S)，c出栈(X)，输出“c”，d，E进栈(SS)，E，d，a出栈(XXX)，输出“E，d，a”，所以结果为B，c，E，d，a。17、若一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n，则第i个输出元素是()。A、不确定B、n－iC、n－i－1D、n－i＋1标准答案：D知识点解析：此时，输出序列一定是输入序列的逆序，故第i个输出元素为n－i＋1。18、以下哪一个不是栈的基本运算()。A、删除栈顶元素B、删除栈底元素C、判断栈是否为空D、将栈置为空栈标准答案：B知识点解析：栈的基本运算有入栈、出栈(删除栈顶元素)、初始化、置空、判断是否为空或满、提取栈顶元素等，对栈元素的操作都是在栈顶进行的。19、若一个栈以向量V[1..n]存储，初始栈顶指针top为n＋1，则下面x进栈的正确操作是()。A、top＝top＋1；V[top]＝xB、V[top]＝x；top＝top＋1C、top＝top－1；V[top]＝xD、V[top]＝x；top＝top－1标准答案：C知识点解析：栈是运算受限的线性表，只允许在栈顶进行插入和删除操作。本题中栈顶指针为n+1，该数组将栈顶放在了下标大的一端，所以在进行入栈操作时top指针应该进行减1操作。通常元素进栈的操作为：先移动栈顶指针后存人元素。20、单向链表中往往含有一个头结点。该结点不存储数据元素，一般令链表的头指针指向该结点，而该结点指针域的值为第一个元素结点的指针。以下关于单链表头结点的叙述中，错误的是()。A、若在头结点中存入链表长度值，则求链表长度运算的时间复杂度为O(1)B、在链表的任何一个元素前后进行插入和删除操作可用一致的方式进行处理C、加入头结点后，在链表中进行查找运算的时间复杂度为O(1)D、加入头结点后，代表链表的头指针不因为链表为空而改变标准答案：C知识点解析：在链表中加入头结点后，查找表中某一元素仍然要从头指针出发，顺序找到目标元素或失败时找到表尾为止，时间复杂度与表长成正比。故D项错误。21、Hash表是用于数据存储的一种有效的数据结构，Hash表的查找复杂度依赖于Hash值算法的有效性，在最好的情况下，Hash表的查找复杂度为()。A、O(nlogn)B、O(logn)C、O(n)D、O(1)标准答案：D知识点解析：O(1)，哈希表是通过计算hashcode来定位元素位置，所以只需一次即可。22、设循环队列的存储空间为Q(1：30)，初始状态front＝rear＝30，先经过一系列入队和退队运算后，front＝10，rear＝10，则循环队列中的元素个数为()。A、30B、0C、29D、0或30标准答案：D知识点解析：当frontrear时，循环队列中的元素个数为N－front＋rear(N为循环队列容量)。当front＝rear时，循环队列中的元素个数可能为空，也可能为满。23、若一个程序语言可以提供链表的定义和运算，则其运行时的()。A、数据空间必须采用堆存储分配策略B、指令空间需要采用栈结构C、指令代码必须放入堆区D、数据空间适合采用静态存储分配策略标准答案：A知识点解析：链表中的结点空间需要程序员根据需要申请和释放，因此，数据空间应采用堆存储分配策略。24、栈和队列的共同点是()。A、都是先进先出B、都是先进后出C、只允许在端点处插入和删除元素D、没有共同点标准答案：C知识点解析：栈和队列都是运算受限的线性表，只允许在表端点处进行操作。二、简答题(本题共9题，每题1.0分，共9分。)25、设计将带表头的链表逆置的算法。标准答案：设单循环链表的头指针为head，类型为LinkList。逆置时需将每一个结点的指针域进行修改，使其原前驱结点成为后继。如果更改Q结点的指针域时，设S指向其原前驱结点，p指向其原后驱结点，则只需进行Q－＞next＝S操作即可。算法描述如下：voidinvert(LinkList＊head){／／逆置head指针所指向的单循环链表Linklist＊p，＊Q，＊S；Q＝head；p＝head－＞next；while(p!＝head)／／当表不为空时，逐个结点逆置{S＝Q；Q＝p；p＝p－＞next；Q－＞next＝S；}p－＞next＝Q；}知识点解析：暂无解析26、阅读下面的算法：LinkListmynote(LinkListL){／／L是不带头结点的单链表的头指针if(L＆＆L－＞next){Q＝L；L＝L－＞next；p＝L；S1：while(p－＞next)；p＝p－＞next；S2：p－＞next＝Q；Q－＞next＝NULL；}returnL；}请回答下列问题：(1)说明语句S1的功能。(2)说明语句S2的功能。(3)设链表表示的线性表为(a1，a2，…，an)，写出算法执行语句S2后的返回值所表示的线性表。标准答案：(1)查询链表的尾结点。(2)将第一个结点链接到链表的尾部，作为新的尾结点。(3)返回的线性表为(a2，a3，…，an，a1)。知识点解析：暂无解析27、线性表有两种存储结构：一是顺序表，二是链表。试问：(1)如果有n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构?为什么?(2)若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构?为什么?标准答案：(1)选链式存储结构。它可动态申请内存空间，不受表长度(即表中元素个数)的影响，插入、删除时间复杂度为O。(2)选顺序存储结构。顺序表可以随机存取，时间复杂度为O。知识点解析：暂无解析28、试叙述头结点、首元结点、头指针这三个概念的区别。标准答案：在线性表的链式存储结构中，头指针指链表的指针，若链表有头结点则是链表的头结点的指针，头指针具有标识作用，故常用头指针冠以链表的名字。头结点是为了操作的统一、方便而设立的，放在第一元素结点之前，其数据域一般无意义(当然有些情况下也可存放链表的长度，用做监视哨等等)，有头结点后，对在第一元素结点前插入结点和删除第一结点，其操作与其它结点的操作统一。而且无论链表是否为空，头指针均不为空。首元结点也就是第一元素结点，它是头结点后边的第一个结点。知识点解析：暂无解析29、有线性表(a1，a2，…，an))，采用单链表存储，头指针为H，每个结点中存放线性表中一个元素，现查找某个元素值等于X的结点。分别写出下面三种情况的查找语句。要求时间尽量少。(1)线性表中元素无序。(2)线性表中元素按递增有序。(3)线性表中元素按递减有序。标准答案：(1)while(p!＝null&&p－＞data!＝X)p＝p－＞next；if(p＝＝null)return(null)；／／查找失败elsereturn(p)；＝查找成功(2)while(p!＝nuU＆＆p－＞data＜X)p＝p－＞ext，if(p＝＝null‖p－＞data＞X)return(null)；／／查找失败elsereturn(p)；(3)while(p!＝null＆＆p－＞data＞X)p＝p－＞next；if(p)＝＝null‖p－＞data＜X)return(null)；／／查找失败elsereturn(p)；／／查找成功知识点解析：暂无解析30、线性表的两种存储结构各有哪些优缺点?标准答案：线性表具有两种存储结构，即顺序存储结构和链接存储结构。线性表的顺序存储结构可以直接存取数据元素，方便灵活、效率高，但插入、删除操作时将会引起元素的大量移动，因而降低效率。在链接存储结构中内存采用动态分配，利用率高，但需增设指示结点之间关系的指针域，存取数据元素不如顺序存储方便，但结点的插入、删除操作较简单。知识点解析：暂无解析31、在数据结构中，如果元素的进栈序列为6个整数1，2，3，4，5，6，通过栈操作能否得到以下两个序列：4，3，5，6，1，2和1，3，5，4，2，6，如果不能则说明理由，如果能够也说明理由。标准答案：按照栈“后进先出”原则，对于序列(4，3，5，6，1，2)：1进栈、2进栈、3进栈、4进栈、4出栈、3出栈、5进栈、5出栈、6进栈、6出栈，2出栈、1出栈，得到的序列为(4，3，5，6，2，1)，因此得不到此序列。对于序列(1，3，5，4，2，6)：1进栈、1出栈、2进栈、3进栈、3出栈、4进栈、5进栈、5出栈、4出栈、2出栈、6进栈、6出栈，没有分后进先出原则，可以得到序列(1，3，5，4，2，6)。知识点解析：暂无解析32、设一数列的输入顺序为123456，若采用堆栈结构，并以A和D分别表示入栈和出栈操作，试问通过入出栈操作的合法序列。(1)能否得到输出顺序为325641的序列。(2)能否得到输出顺序为154623的序列。标准答案：(1)能得到325641。在123依次进栈后，3和2出栈，得部分输出序列32；然后4，5入栈，5出栈，得部分出栈序列325；6入栈并出栈，得部分输出序列3256；最后退栈，直到栈空。得输出序列325641。其操作序列为AAADDAADADDD。(2)不能得到输出顺序为154623的序列。部分合法操作序列为ADAAAADDAD，得到部分输出序列1546后，栈中元素为23，3在栈顶，故不可能2先出栈，得不到输出序列154623。知识点解析：暂无解析33、在一个算法中需要建立多个堆栈时可以选用下列三种方案之一，试问：这三种方案之间相比较各有什么优缺点?(1)分别用多个顺序存储空间建立多个独立的堆栈。(2)多个堆栈共享一个顺序存储空间。(3)分别建立多个独立的链接堆栈。标准答案：(1)每个栈仅用一个顺序存储空间时，操作简便，但分配存储空间小了，容易产生溢出，分配空间大了，容易造成浪费，各栈不能共享空间。(2)多个栈共享一个顺序存储空间，充分利用了存储空间，只有在整个存储空间都用完时才能产生溢出，其缺点是当一个栈满时要向左、右栈查询有无空闲单元。如果有，则要移动元素和修改相关的栈底和栈顶指针。当接近栈满时，查询空闲单元、移动元素和修改栈底栈顶指针的操作频繁，计算复杂并且耗费时间。(3)多个链栈一般不考虑栈的溢出(仅受用户内存空间限制)，缺点是栈中元素要以指针相链接，比顺序存储多占用了存储空间。知识点解析：暂无解析一、单项选择题(本题共24题，每题1.0分，共24分。)34、双向链表中有两个指针域llink和rlink，分别指向前驱和后继，设p指向表中的一个结点，q指向一待插入结点，现要求在p前插入q，则正确的插入为()。A、p→llinkB、q→llink→—＞＜—p→llink；p—＞llink—＞dink—＞＜—q；q—＞llink—＞＜—p—＞llinkC、q→rlink→dink—－＞＜—q；p—＞rlink—＞＜q；p—＞llink—＞rlink—＞＜—p；D、p→link→rlink—－＞＜—q；q—＞rlink—＞＜—p；q—＞llink—＞＜—p—＞llink；p—＞1link—＞＜—q标准答案：D知识点解析：p→llink→rlink＝q；q→rlink＝p；q→link＝p→llink；p→link＝q。35、假设执行语句S的时间为0(1)，则执行下列程序段的时间为()。for(i＝1；i＜＝n；i＋＋)for(j＝1；j＜＝n；j＋＋)S：A、O(n)B、O(n^2)C、O(n＊i)D、O(n＋1)标准答案：B知识点解析：观察可知，程序段S的执行频度为T(n)＝n＾2，得时间复杂度T(n)＝O(n^2)。36、广义表中的元素可以是原子，也可以是表，因此广义表的适用存储结构是()。A、散列表B、静态数组C、动态数组D、链表标准答案：D知识点解析：暂无解析37、线性表采用链接存储时，其地址()。A、必须是连续的B、部分地址必须是连续的C、一定是不连续的D、连续与否均可以标准答案：D知识点解析：线性表的链接存储是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以连续，也可以不连续，甚至可以零散分布在内存中任意位置。38、在有n个结点的二叉链表中，值为非空的链域的个数为()。A、n－1B、2n－1C、n＋1D、2n＋1标准答案：A知识点解析：本题考查的是二叉树的链式存储。由于在有n个结点的二叉链表中，值为空的链域的个数为n＋1个，而总的链域为2n(在二叉树中每个结点头2个链域)。所以，非空的链域的个数为2n－(n＋1)＝n－1。39、下列与数据元素有关的叙述中，哪一项是不正确的()。A、数据元素是数据的基本单位，即数据集合中的个体B、数据元素是由独立含义的数据最小单位C、数据元素又称为节点D、数据元素又称为记录标准答案：B知识点解析：数据元素是数据的基本单位，即数据集合中的个体。有些情况下也把数据元素称为节点、记录、表目等。一个数据元素可由一个或多个数据项组成，数据项是由独立含义的数据最小单位。40、在一个单链表中，若p所指的结点不是最后结点，则删除p所指的结点的后继结点的正确操作是()。A、p＝p－＞nextB、p－＞next＝p－＞nextC、p－＞next＝p－＞next－＞nextD、p－＞next＝p标准答案：C知识点解析：本题考查的是单链表的删除操作。在已知链表中元素插入或删除确切位置的情况下，在单链表中插入或删除一个结点时，仅需修改指针而无须移动元素。41、对于只在表的首尾两端进行插入操作的线性表，宜采用的存储结构是()。A、顺序表B、用头指针表示的单循环链表C、用尾指针表示的单循环链表D、单链表标准答案：C知识点解析：本题考查的是线性表的插入与删除操作。当线性表用尾指针表示的单循环链表存储时，很容易找到线性表的首、尾元素。此时，尾指针的后继即是线性表的首端。42、链表不具有的特点是()。A、不必事先估计存储空间B、可随机访问任一元素C、插入删除不需要移动元素D、所需空间与线性表长度成正比标准答案：B知识点解析：链表采用的是链式存储结构，它克服了顺序存储结构的缺点：①它的结点空间可以动态申请和释放；②它的数据元素的逻辑次序靠结点的指针来指示，不需要移动数据元素。但是链式存储结构也有不足之处：①每个结点中的指针域需额外占用存储空间；②链式存储结构是一种非随机存储结构。43、链表不具有的特点是()。A、可随机访问任意元素B、不必事先估计存储空间C、插入数据元素时不需要移动数据元素D、删除数据元素时不需要移动数据元素标准答案：A知识点解析：顺序链表不可以随机访问任意元素。44、在向下生成的堆栈中，如果入栈指令PUSHX的操作定义为：S←(SP)＋1，M(SP)←M(X)，则出栈指令POPX应定义为()。A、SP←(SP)－1，M(X)←M(SP)B、SP←(SP)＋1，M(X)←M(SP)C、M(X)←M(SP)，SP←(SP)－1D、M(X)←M(SP)，SP←(SP)＋1标准答案：C知识点解析：入栈是先定位栈顶指针然后存储数据，出栈是先出数据，然后再定位栈顶指针。45、设一个栈的输入序列是1、2、3、4、5，则下列序列中，是栈的合法输出序列的是()。A、51234B、45123C、43125D、32154标准答案：D知识点解析：栈的进出原则是先进后出原则，要不就是先进先出原则。A选项中5最先出，说明1234都在栈里，这样说明1是在栈低，则先不出来。BD的原因一样，所以答案选择D。46、对于长度为m(m＞1)的指定序列，通过初始为空的一个栈、一个队列后，错误的叙述是()。A、入栈序列与出栈序列关系为1：1，而入队序列与出队序列关系是1：n(n≥1)B、若入栈和入队的序列相同，则出栈序列和出队序列可以互为逆序C、入队序列与出队序列关系为1：1，而入栈序列与出栈序列关系是1：n(n≥1)D、若入栈和入队的序列相同，则出栈序列和出队序列可能相同标准答案：A知识点解析：队列的元素按特点是先进先出。对于队列，元素的进入次序和出队的次序相同，例如，入队的序列为a、b、c，则出队的序列也为a、b、c。对于栈则不同，栈的运算特点是后进先出。若入栈序列为a、b、c，则出栈序列可能为a、b、c，a、c、b，b、a、c，b、c、a或者c、b、a，而c、a、b则不行，因此，入栈序列与出栈序列关系为1：1，而入队序列与出队序列关系为1：n(n≥1)。47、当利用大小为n的数组顺序存储一个栈时，假定top＝n表示栈空，则向这个栈插入一个元素时，首先应该执行下列哪个语句修改的top指针()。A、top＋＋1B、top－－C、top＝0D、top标准答案：B知识点解析：暂无解析48、设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，1个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3，e6，e5，e1，则栈S的容量至少应该是()。A、6B、4C、3D、2标准答案：C知识点解析：根据栈的性质(LIFO)得，e2出栈前，栈中存有e1和e2两个元素，e4出栈前，栈中存有e1、e3和e43个元素，e4和e3出栈以后，e5和e6入栈，栈中同样存在e1、e5和e63个元素，然后3个元素依次出栈，所以栈的容量至少应该为3。49、假设以S和X分别表示进栈和出栈操作，则对输入序列a，B，c，d，E进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为()。A、B，c，E，d，aB、B，E，e，a，dC、E，c，B，d，aD、c，E，B，a，d标准答案：A知识点解析：a，B进栈(SS)，B出栈(X)，输出“B”，c进栈(S)，c出栈(X)，输出“c”，d，E进栈(SS)，E，d，a出栈(XXX)，输出“E，d，a”，所以结果为B，c，E，d，a。50、若一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n，则第i个输出元素是()。A、不确定B、n－iC、n－i－1D、n－i＋1标准答案：D知识点解析：此时，输出序列一定是输入序列的逆序，故第i个输出元素为n－i＋1。51、以下哪一个不是栈的基本运算()。A、删除栈顶元素B、删除栈底元素C、判断栈是否为空D、将栈置为空栈标准答案：B知识点解析：栈的基本运算有入栈、出栈(删除栈顶元素)、初始化、置空、判断是否为空或满、提取栈顶元素等，对栈元素的操作都是在栈顶进行的。52、若一个栈以向量V[1..n]存储，初始栈顶指针top为n＋1，则下面x进栈的正确操作是()。A、top＝top＋1；V[top]＝xB、V[top]＝x；top＝top＋1C、top＝top－1；V[top]＝xD、V[top]＝x；top＝top－1标准答案：C知识点解析：栈是运算受限的线性表，只允许在栈顶进行插入和删除操作。本题中栈顶指针为n+1，该数组将栈顶放在了下标大的一端，所以在进行入栈操作时top指针应该进行减1操作。通常元素进栈的操作为：先移动栈顶指针后存人元素。53、单向链表中往往含有一个头结点。该结点不存储数据元素，一般令链表的头指针指向该结点，而该结点指针域的值为第一个元素结点的指针。以下关于单链表头结点的叙述中，错误的是()。A、若在头结点中存入链表长度值，则求链表长度运算的时间复杂度为O(1)B、在链表的任何一个元素前后进行插入和删除操作可用一致的方式进行处理C、加入头结点后，在链表中进行查找运算的时间复杂度为O(1)D、加入头结点后，代表链表的头指针不因为链表为空而改变标准答案：C知识点解析：在链表中加入头结点后，查找表中某一元素仍然要从头指针出发，顺序找到目标元素或失败时找到表尾为止，时间复杂度与表长成正比。故D项错误。54、Hash表是用于数据存储的一种有效的数据结构，Hash表的查找复杂度依赖于Hash值算法的有效性，在最好的情况下，Hash表的查找复杂度为()。A、O(nlogn)B、O(logn)C、O(n)D、O(1)标准答案：D知识点解析：O(1)，哈希表是通过计算hashcode来定位元素位置，所以只需一次即可。55、设循环队列的存储空间为Q(1：30)，初始状态front＝rear＝30，先经过一系列入队和退队运算后，front＝10，rear＝10，则循环队列中的元素个数为()。A、30B、0C、29D、0或30标准答案：D知识点解析：当frontrear时，循环队列中的元素个数为N－front＋rear(N为循环队列容量)。当front＝rear时，循环队列中的元素个数可能为空，也可能为满。56、若一个程序语言可以提供链表的定义和运算，则其运行时的()。A、数据空间必须采用堆存储分配策略B、指令空间需要采用栈结构C、指令代码必须放入堆区D、数据空间适合采用静态存储分配策略标准答案：A知识点解析：链表中的结点空间需要程序员根据需要申请和释放，因此，数据空间应采用堆存储分配策略。57、栈和队列的共同点是()。A、都是先进先出B、都是先进后出C、只允许在端点处插入和删除元素D、没有共同点标准答案：C知识点解析：栈和队列都是运算受限的线性表，只允许在表端点处进行操作。二、简答题(本题共9题，每题1.0分，共9分。)58、设计将带表头的链表逆置的算法。标准答案：设单循环链表的头指针为head，类型为LinkList。逆置时需将每一个结点的指针域进行修改，使其原前驱结点成为后继。如果更改Q结点的指针域时，设S指向其原前驱结点，p指向其原后驱结点，则只需进行Q－＞next＝S操作即可。算法描述如下：voidinvert(LinkList＊head){／／逆置head指针所指向的单循环链表Linklist＊p，＊Q，＊S；Q＝head；p＝head－＞next；while(p!＝head)／／当表不为空时，逐个结点逆置{S＝Q；Q＝p；p＝p－＞next；Q－＞next＝S；}p－＞next＝Q；}知识点解析：暂无解析59、阅读下面的算法：LinkListmynote(LinkListL){／／L是不带头结点的单链表的头指针if(L＆＆L－＞next){Q＝L；L＝L－＞next；p＝L；S1：while(p－＞next)；p＝p－＞next；S2：p－＞next＝Q；Q－＞next＝NULL；}returnL；}请回答下列问题：(1)说明语句S1的功能。(2)说明语句S2的功能。(3)设链表表示的线性表为(a1，a2，…，an)，写出算法执行语句S2后的返回值所表示的线性表。标准答案：(1)查询链表的尾结点。(2)将第一个结点链接到链表的尾部，作为新的尾结点。(3)返回的线性表为(a2，a3，…，an，a1)。知识点解析：暂无解析60、线性表有两种存储结构：一是顺序表，二是链表。试问：(1)如果有n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构?为什么?(2)若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构?为什么?标准答案：(1)选链式存储结构。它可动态申请内存空间，不受表长度(即表中元素个数)的影响，插入、删除时间复杂度为O。(2)选顺序存储结构。顺序表可以随机存取，时间复杂度为O。知识点解析：暂无解析61、试叙述头结点、首元结点、头指针这三个概念的区别。标准答案：在线性表的链式存储结构中，头指针指链表的指针，若链表有头结点则是链表的头结点的指针，头指针具有标识作用，故常用头指针冠以链表的名字。头结点是为了操作的统一、方便而设立的，放在第一元素结点之前，其数据域一般无意义(当然有些情况下也可存放链表的长度，用做监视哨等等)，有头结点后，对在第一元素结点前插入结点和删除第一结点，其操作与其它结点的操作统一。而且无论链表是否为空，头指针均不为空。首元结点也就是第一元素结点，它是头结点后边的第一个结点。知识点解析：暂无解析62、有线性表(a1，a2，…，an))，采用单链表存储，头指针为H，每个结点中存放线性表中一个元素，现查找某个元素值等于X的结点。分别写出下面三种情况的查找语句。要求时间尽量少。(1)线性表中元素无序。(2)线性表中元素按递增有序。(3)线性表中元素按递减有序。标准答案：(1)while(p!＝null&&p－＞data!＝X)p＝p－＞next；if(p＝＝null)return(null)；／／查找