《计算机软件技术基础》试题及答案

《计算机软件技术基础》试题 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(n2) 4.设 A是一个线性表(a1,a2,„,an)，采用顺序存储结构，则在等概率的前提下，平均每插入一个元素需要移动的元素个数为 B ，平均每删除一个元素需要移动的元素个数为 A ；若元素插在ai与ai+1之间(0≤I≤n-1)的概率为 )1()(2nnin，则平均每插入一个元素所要移动的元素个数为 C ； A. 21n B. 2n C. 312n D. 413n 5.下列函数中，按它们在n时的无穷大阶数，最大的是 D 。 A. logn B. nlogn C. 2n/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 。 A. n 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; void combine(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->nex...