第二章 线性表 答案VIP免费

数据结构与算法上机作业第二章线性表、选择题1、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新的元素算法的时间复杂度为C。A.O(log2n)B.O(1)C.O(n)D.O(n2)2、以下关于线性表的说法中，不正确的是C。A.线性表中的数据元素可以是数字、字符、结构等不同类型B.线性表中包含的数据元素个数不是任意的C.线性表中的每一个结点都有且只有一个直接前驱和直接后继D.存在这样的线性表：表中各结点都没有直接前驱和直接后继3、在有n个结点的顺序表上做插入、删除结点运算的时间复杂度为B。A.O(1)B.O(n)C.O(n2)D.O(log2n)4、等概率情况下，在有n个结点的顺序表上做插入结点操作，需平均移动的结点数目为—C。提示：插入的位置有n+1个，移动总数为：1+2+3++nA.nB.(n-1)/2C.n/2D.(n+1)/25、在一个长度为n的顺序存储的线性表中查找值为x的元素时，平均查找长度(及x同元素的平均比较次数，假定查找每个元素的概率都相等)为C。A.nB.n/2C.(n+1)/2D.(n-1)/26、在顺序表中，只要知道一D，就可以求出任一结点的存储地址。A.基地址B.结点大小C.向量大小D.基地址和结点大小7、将两个各有n个元素的有序表归并为一个有序表，其最少的比较次数是A。A.nB.2n-1C.2nD.n-18、线性表采用链表存储时其存储地址要求D。A.必须是连续的B.部分地址必须是连续的C.必须是不连续的D.连续的和不连续的都可以9、下面关于线性表的描述中，错误的是B。A.线性表采用顺序存储，必须占用一片连续的存储单元B.线性表采用顺序存储，便于进行插入和删除操作C.线性表采用链式存储，不必占用一片连续的存储单元D.线性表采用链式存储，便于插入和删除操作10、向具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是BA.O(1)B.O(n)C.O(n2)D.O(log2n)11、在一个带头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行的语句是D。A.HL=p;p->next=HL;B.p->next=HL;HL=p;C.p->next=HL;p=HL;D.p->next=HL->next;HL->next=p;12、在一个单链表HL中,若要删除由指针q所指向结点的后继结点，则执行的语句是仝。A.p=q->next;p->next=q->next;B.p=q->next;q->next=p;C.p=q->next;q->next=p->next;D.q->next=q->next->next;q->next=q;13、设有编号为1,2,3,4的4辆列车，顺序进入一个栈结构的站台，下列不可能的出栈顺序为D。A.1234B.1243C.1324D.142314、4个元素按A,B,C,D顺序进入S栈，执行两次Pop(S,x)运算后，栈顶元素的值是B。A.x=top;top=top->next;C.x=top->data;C.谁先谁后无关紧要D.同时进行A.AB.BC.CD.D15、从一个栈顶指针为top的链栈中删除一个结点时，用x保存被删除的结点，应执行下列A命令。B.top=top->next;x=top->data;D.x=top->data;top=top->next;16、向顺序栈中输入元素时B。A.先存入兀素，后移动栈顶指针B.先移动栈顶指针，后存入兀素17、设有一个顺序栈，元素A,B,C,D,E,F依次进栈，如果6个元素出栈的顺序是B,D,C,F,E,A,则栈的容量至少为A。A.3B.4C.56.618、设已将元素A,B,C依次入栈，元素D正等待进栈。那么下列4个序列中不可能出现的出栈顺序为A。A.CADBB.CBDAC.CDBAD.DCBA19、栈和队列的相同之处是C。A.元素的进出满足先进后出B.元素的进出满足后进先出C.只允许在端点进行插入和删除操作D.无共同点20、设栈S和队列Q的初始状态为空,元素e1，e2，e3，e4，e5和e6依次通过栈，一个元素出栈后即进入队列Q,若6个元素出队的序列是e2,e4，e3,e6，e5，e1，则栈S的容量至少应该是C。A.6B.4C.3D.221、队列通常采用的两种存储结构是A。A.顺序存储结构和链式存储结构B.散列方式和索引方式C.链表存储结构和线性存储结构D.线性存储结构和非线性存储结构22、循环队列SQ队满的条件是D。A.SQ->rear==SQ->frontB.(SQ->rear+1)%MAXLEN==SQ->frontC.SQ->rear+2==SQL->frontD.(SQ->rear+2)%MAXLEN==SQL->front23、若用一个大小为6的数组来实现循环队列，且当前front和rear的值分别为3和0，当从队列中删除一个元素，再加入两个元素后，front和rear的值分别为B。A.5和1B.4和2C.2和4D.1和524、链栈与顺序栈相比，有一个较为明显的优点是。A.通常不会出现满栈的情况B.通常不会出现栈空的情况C.插入操作更加方便D.删除...