文档介绍：《计算机软件技术基础》试题 1. 线性表的链式存储结构与顺序存储结构相比优点是 CD。 A. 所有的操作算法实现简单 B. 便于随机存取 C. 便于插入和删除 D. 便于利用零散的存储器空间 2. 线性表是具有 n个C 的有限序列。 A. 表元素 B. 字符 C. 数据元素 D. 数据项 E. 信息项 3. 若长度为 n 的线性表采用顺序存储结构, 在其第 I 个位置插入一个新元素的算法的时间复杂度为 C。(1≤I≤ n+1 ) A. O(0) B. O(1) C. O(n) D. O(n 2) 是一个线性表(a 1 ,a 2,…,a n), 采用顺序存储结构, 则在等概率的前提下, 平均每插入一个元素需要移动的元素个数为 B ,平均每删除一个元素需要移动的元素个数为 A; 若元素插在 a i与a i+1 之间(0≤I≤ n-1) 的概率为)1( )(2??nn in , 则平均每插入一个元素所要移动的元素个数为 C; 1?n n 12?n 13?n 5. 下列函数中,按它们在?? n 时的无穷大阶数,最大的是 D。 A. log n B. nlog n n/2 D. n! 6. 将下图所示的 s 所指结点加到 p 所指的结点之后,其语句应为: D。 A. s->next=p+1; p->next=s; B. (*p).next=s; (*s).next=(*p).next; C. s->next=p->next; p->next=s->next; D. s->next=p->next; p->next=s; 7. 将两个各有 n 个元素的有序表归并为一个有序表时,其最少的比较次数是 A。 B. 2n-1 C. n-1 D. 2n 8. 下面的程序段是合并两个无头结点链表(ha 和 hb) 为一个无头结点链表 ha 的过程,作为参数的两个链表都是按结点的 data 域由大到小链接的。合并后新链表的结点仍按此方式链接。请填写下述空框,使程序能正确运行。 s p next next next #define NULL 0 typedef struct node{ int data; struct node *next; }node, linklisttype; bine(linklisttype *ha, linklisttype *hb){ linklisttype *h, *p; h= (linklisttype *)malloc(sizeof(linklisttype)); h->next = NULL; p= h; while(ha != NULL && hb != NULL) if(ha->data>=hb->data) { /* 较大的元素先插入*/ p->next = (1) ; p= (2) ; (3) ;} else{ p->next = (4) ; p= (5) ; (6) ;} if(ha==NULL) (7) ; if(hb==NULL) (8) ; ha= h->next; free(h); } 参考答案: (1) ha (2) p->next (3) ha=ha->next (4) hb (5) p->next (6) hb=hb->next (7) p->next=hb (8) p->next=ha 9. 如果表 A 中所有元素(a 1 ,a 2,…,a n) 与表 B 的一个顺序子表(b k ,b k+1,…b k+n-1 ) 完全相同( 即 a 1 =b k ,a 2 =b k+1,…a n =b k+n-1 ) ,则称表 A 包含在表 B 中。设 ha, hb 为带头结点的单链表,分别表示有序表 A和B, 下面的函数用于判别表 A 是否包含在表 B中, 若是, 则返回 true , 否则返回 false 。(提示:用递归实现) #define true 1 #define false 0 #define NULL 0 typedef struct node{ int data; struct node *next; }node, linklisttype; int inclusion(linklisttype *ha, linklisttype *hb){ linklisttype *pa, *pb; pa= ha->next; pb= hb->next; (1) ; while( (2) ) if(pa->data=pb->data) (3) ; else (4) ; (5) ;} 参考答案: (1) if(pa==NULL) return(true) (2) pb!=NULL && pa->data>=pb->data (3) ret