数据结构与算法上机作业第二章线性表一、选择题1、若长度为n 的线性表采用顺序存储结构，在其第i 个位置插入一个新的元素算法的时间复杂度为c 。A. O(log 2n) 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(n 2) D. O(log 2n) 4、等概率情况下，在有n 个结点的顺序表上做插入结点操作，需平均移动的结点数目为d 。A. n B. (n-1)/2 C. n/2 D. (n+1)/2 5、在一个长度为n 的顺序存储的线性表中查找值为x 的元素时， 平均查找长度 (及 x 同元素的平均比较次数，假定查找每个元素的概率都相等)为b 。A. n B. n/2 C. (n+1)/2 D. (n-1)/2 6、在顺序表中，只要知道d ，就可以求出任一结点的存储地址。A. 基地址B. 结点大小C. 向量大小D. 基地址和结点大小7、将两个各有n 个元素的有序表归并为一个有序表，其最少的比较次数是a 。A. n B. 2n-1 C. 2n D. n-1 8、线性表采用链表存储时其存储地址要求d 。A. 必须是连续的B. 部分地址必须是连续的C. 必须是不连续的D. 连续的和不连续的都可以9、下面关于线性表的描述中，错误的是d 。A. 线性表采用顺序存储，必须占用一片连续的存储单元B. 线性表采用顺序存储，便于进行插入和删除操作C. 线性表采用链式存储，不必占用一片连续的存储单元D. 线性表采用链式存储，便于插入和删除操作10、向具有 n 个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是b A. O(1) B. O(n) C. O(n2) D. O(log 2n) 11、在一个带头结点的单链表HL 中，若要向表头插入一个由指针p 指向的结点，则执行的语句是B 。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 所指向结点的后继结点，则执行的语句是C 。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...
