资源描述：
《数据结构第二次作业》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二次作业一、选择题1、设有编号为1,2,3,4的4辆列车，顺序进入一个栈结构的站台，下列不可能的出栈顺序为D。A.1234B.1243C.1324D.14232、4个元素按A,B,C,D顺序进入S栈，执行两次Pop(S,x)运算后，栈顶元素的值是B。A.AB.BC.CD.D3、从一个栈顶指针为top的链栈中删除一个结点时，用x保存被删除的结点，应执行下列A命令。A.x=top;top=top->next;B.top=top->next;x=top->data;C.x=top->data;D.x=top
2、->data;top=top->next;//题中说用x保存被删除的结点，应该是保存的结点位置而不是元素4、向顺序栈中输入元素时B。A.先存入元素，后移动栈顶指针B.先移动栈顶指针，后存入元素C.谁先谁后无关紧要D.同时进行5、设有一个顺序栈，元素A,B,C,D,E,F依次进栈，如果6个元素出栈的顺序是B,D,C,F,E,A，则栈的容量至少为A。A.3B.4C.56.6//ABCDEF进栈时栈的最大高度分别为：1223236、设已将元素A,B,C依次入栈，元素D正等待进栈。那么下列4个序列中不可能出现的
3、出栈顺序为A。A.CADBB.CBDA（B出栈后D入栈）C.CDBA（C出栈后D入栈）D.DCBA（D先入栈然后一起出栈）7、栈和队列的相同之处是C。A.元素的进出满足先进后出B.元素的进出满足后进先出C.只允许在端点进行插入和删除操作D.无共同点8、设栈S和队列Q的初始状态为空,元素e1，e2，e3，e4，e5和e6依次通过栈，一个元素出栈后即进入队列Q,若6个元素出队的序列是e2，e4，e3，e6，e5，e1，则栈S的容量至少应该是C。A.6B.4C.3D.29、队列通常采用的两种存储结构是AA.顺
4、序存储结构和链式存储结构B.散列方式和索引方式C.链表存储结构和线性存储结构D.线性存储结构和非线性存储结构10、循环队列SQ队满的条件是。A.SQ->rear==SQ->frontB.(SQ->rear+1)%MAXLEN==SQ->frontB.SQ->rear==0D.SQ->front==0//选项B应该是队空的情况，队满时应该满足：(SQ->rear+2)%MAXLEN==SQ->front11、若用一个大小为6的数组来实现循环队列，且当前front和rear的值分别为3和0，当从队列中删除一
5、个元素，再加入两个元素后，front和rear的值分别为B。A.5和1B.4和2C.2和4D.1和5//循环队列中，删除操作front指针后移，插入操作rear指针后移12、链栈与顺序栈相比，有一个较为明显的优点是A。A.通常不会出现满栈的情况B.通常不会出现栈空的情况C.插入操作更加方便D.删除操作更加方便13、设用一个大小为M=60的顺序表A[M]表示一个循环队列，如果当前的尾指针rear=32，头指针front=15，则当前循环队列的元素的个数为。A.42B.16C.17D.41//循环队列中，f
6、ront指向第一个元素，rear指向最后一个元素，因此本题中元素个数应该为32-15+1=18个（rear-front+n+1）%n14、串是一种特殊的线性表，其特殊性体现在B。A.可以顺序存储B.数据元素是一个字符C.可以链式存储D.数据元素可以是多个字符15、设主串的长度为n，模式串的长度为m，则串匹配的KMP算法的时间复杂度为C。A.O(m)B.O(n)C.O(m+n)D.O(m×n)16、已知串S=“abab”，其Next数组值为。A.0123B.0121C.0112D.0122//010117
7、、若字符串“ABCDEFG”采用不带表头的链式存储，每个结点保存一个字符。假设每个字符占用1个字节，每个指针占用两个字节，则该字符串的存储密度为D。A.20%B.40%C.50%D.33.3%存储密度：结点数据本身所占的存储量/结点结构所占的存储总量本题中存储密度=1/（1+2）=33.3%18、在双向链表中，在指针p所指的结点前插入一个指针q所指向的结点，操作是C。//注意最后的时候再让p的prior指向qA.p->Prior=q;q->Next=p;p->Prior->next=q;q->Prior
8、=q;B.p->Prior=q;p->Prior->next=q;q->next=p;q->Prior=p->Prior;C.q->Next=p;q->Prior=p->Prior;p->Prior->Next=q;p->Prior=q;D.q->Prior=p->Prior;q->Next=q;p->Prior=q;p->Next=q;19、已知循环队列存储在一维数组A[0…n-1]中，且队列非空时front和rear分别指向对头元素和队
