工大数据结构第二章作业.docx

数据结构与算法上机作业第二章 线性表一、选择题1、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新的元素算法的时间复杂度为 。A. O(log2n)B. O(1)C. O(n)D. O(n2)2、以下关于线性表的说法中，不正确的是 。A. 线性表中的数据元素可以是数字、字符、结构等不同类型B. 线性表中包含的数据元素个数不是任意的C. 线性表中的每一个结点都有且只有一个直接前驱和直接后继（单项链表）D. 存在这样的线性表：表中各结点都没有直接前驱和直接后继（数组实现）3、在有n个结点的顺序表上做插入、删除结点运算的时间复杂度为 。A. O(1)B. O(n)C. O(n2)D. O(log2n)4、等概率情况下，在有n个结点的顺序表上做插入结点操作，需平均移动的结点数目为 。A. nB. (n-1)/2C. n/2D. (n+1)/2已经有N个点了,再加一个就是N+1个.假设新加的结点插在第i位,那么后面N+1-i个结点都要往后移动.i的取值服从1到N+1的平均分布,即概率是1/(N+1).求期望得N/2,即平均要移动N/2个结点 期望有计算公式，这里等于(N+1-1)*1/(N+1)+(N+1-2)*1/(N+1)+(N+1-3)*1/(N+1)+...+(N+1-N-1)*1/(N+1)=N/25、在一个长度为n的顺序存储的线性表中查找值为x的元素时，平均查找长度(及x同元素的平均比较次数，假定查找每个元素的概率都相等)为 。A. nB. n/2C. (n+1)/2D. (n-1)/26、在顺序表中，只要知道 ，就可以求出任一结点的存储地址。A. 基地址B. 结点大小C. 向量大小D. 基地址和结点大小7、将两个各有n个元素的有序表归并为一个有序表，其最少的比较次数是 。A. nB. 2n-1C. 2nD. n-18、线性表采用链表存储时其存储地址要求 。A. 必须是连续的B. 部分地址必须是连续的C. 必须是不连续的D. 连续的和不连续的都可以9、下面关于线性表的描述中，错误的是 。A. 线性表采用顺序存储，必须占用一片连续的存储单元B. 线性表采用顺序存储，便于进行插入和删除操作C. 线性表采用链式存储，不必占用一片连续的存储单元D. 线性表采用链式存储，便于插入和删除操作10、向具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是 A. O(1)B. O(n)C. O(n2)D. O(log2n)11、 语句是 。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;HL为链表的头指针。HL指示链表中第一个节点的存储位置，在表头插入一个由指针p指向的节点后，头指针指向p，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辆列车，顺序进入一个栈结构的站台，下列不可能的出栈顺序为 。A. 1234B. 1243C. 1324D. 1423至少有14种。①全进之后再出情况只有1种：4，3，2，1②进3个后再出的情况有3种3,4,2,1 3,2,4,1 3,2,1,4③进2个后再出的情况有5种2,4,3,1 2,3,4,1 2,1, 3,4 2,1,4,3 2,1,3,4④进1个后再出的情况，有5种1,4,3,2 1,3,2,4 1,3,4,2 1, 2,3,4 1,2,4,314、4个元素按A, B, C, D顺序进入S栈，执行两次Pop(S, x)运算后，栈顶元素的值是 。A. AB. BC. CD. D15、从一个栈顶指针为top的链栈中删除一个结点时，用x保存被删除的结点，应执行下列 命令。A. x=top; top=top-next;B. top=top-next; x=top-data;C. x=top-data;D. x=top-data; top=top-next;16、向顺序栈中输入元素时 。A. 先存入元素，后移动栈顶指针B. 先移动栈顶指针，后存入元素C. 谁先谁后无关紧要D. 同时进行17、设有一个顺序栈，元素A, B, C, D, E, F依次进栈，如果6个元素出栈的顺序是B, D, C, F, E, A，则栈的容量至少为 。A. 3B. 4C. 5D. 6顺序如下A入栈B入栈然后B出栈,C入栈D入栈,D出栈,C出栈,