《《计算机软件基础》复习题库(带标准答案)[1]》由会员分享，可在线阅读，更多相关《《计算机软件基础》复习题库(带标准答案)[1]（37页珍藏版）》请在金锄头文库上搜索。
1、计算机软件基础复习题库(带答案)1.线性表的链式存储结构与顺序存储结构相比优点是 CD 。A. 所有的操作算法实现简单B. 便于随机存取C. 便于插入和删除D. 便于利用零散的存储器空间2.线性表是具有n个 C 的有限序列。A. 表元素B. 字符C. 数据元素D. 数据项E. 信息项3.若长度为n的线性表采用顺序存储结构，在其第I个位置插入一个新元素的算法的时间复杂度为 C 。（1In+1）A. O(0)B. O(1)C. O(n)D. O(n2)4.设A是一个线性表(a1,a2,an)，采用顺序存储结构，则在等概率的前提下，平均每插入一个元素需要移动的元素个数为 B (n/2) ，平均每删除
2、一个元素需要移动的元素个数为 A ；若元素插在ai与ai+1之间(0In-1)的概率为，则平均每插入一个元素所要移动的元素个数为 C ；A. B. C. D. 5.下列函数中，按它们在时的无穷大阶数，最大的是 D 。A. lognB. nlognC. 2n/2D. n!spnextnextnext6.将下图所示的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=
3、s;7.将两个各有n个元素的有序表归并为一个有序表时，其最少的比较次数是 A 。A. nB. 2n-1C. n-1D. 2n8.下面的程序段是合并两个无头结点链表(ha和 hb)为一个无头结点链表ha的过程，作为参数的两个链表都是按结点的data域由大到小链接的。合并后新链表的结点仍按此方式链接。请填写下述空框，使程序能正确运行。#define NULL 0typedef struct nodeint data;struct node *next;node, linklisttype;void combine(linklisttype *ha, linklisttype *hb)linklis
4、ttype *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) ;elsep-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、5) p-next(6) hb=hb-next(7) p-next=hb(8) p-next=ha9.如果表A中所有元素(a1,a2,an)与表B的一个顺序子表(bk,bk+1,bk+n-1)完全相同（即a1=bk,a2=bk+1,an=bk+n-1），则称表A包含在表B中。设ha，hb为带头结点的单链表，分别表示有序表A和B，下面的函数用于判别表A是否包含在表B中，若是，则返回true，否则返回false。（提示：用递归实现）#define true 1#define false 0#define NULL 0typedef struct nodeint data;struct node *
6、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) return(inclusion(pa, pb)(4) pb = pb-next;(5) return(f
7、alse)10.在本题的程序中，函数create_link_list(n)建立一个具有n个结点的循环链表；函数josephus(n,I,m)对由create_link_list(n)所建立的具有n个结点的循环链表按一定的次序逐个输出，并删除链表中的所有结点。参数n(n0)指明循环链表的结点个数，参数I(1In)指明起始结点，参数m（m0是步长），指明从起始结点或前次被删除并输出的结点之后的第m个结点作为本次被输出并删除的结点。例如，对于下图所示的具有6个结点的循环链表，在调用josephus(6,3,2)后，将输出5,1,3,6,4,2。请在空框处填上适当内容，每框只填一个语句。#define
8、 NULL 0typedef struct nodeint data;struct node *next;node, linklisttype;linklisttype *create_link_list(int n)linklisttype *head, *p, *q;int I;head = NULL;if(n0)head = (linklisttype *)malloc(sizeof(linklisttype);p = head;for(I=1;Idata = I;q = (linklisttype *)malloc(sizeof(linklistttype); (1) ; (2) ;p
9、-data = n; (3) ;/*建立从尾链到首的环形结构*/return(head);void Josephus(int n, int j, int m)linklisttype *p, *q;int j;p = create_link_list(n);for(;I1;I-)p = p-next; (4) ;while(jn)for(I=1;Inext; (5) ;printf(“%8d”,q-data); (6) ;free(q);j=j+1;参考答案：(1) p-next = q;(2) p = q;(3) p-next = head(4) j=0(5) q=p-next;(6) p-
10、next = q-next11.在下列程序中，函数difference(A,B)用于求两集合之差C=A-B，即当且仅当e是A中的一个元素，且不是B中的元素时，e是C中的一个元素。集合用有序链表实现，用一个空链表表示一个空集合，表示非空集合的链表根据元素之值按递增排列，执行C=A-B之后，表示集合A和B的链表不变，若结果集合C非空，则表示它的链表应根据元素之值按递增序排列。函数append()用于在链表中添加结点。#include #define NULL 0typedef struct nodeint data;struct node *next;NODE;NODE *append(NODE
11、*last, int x)last-next=(NODE *)malloc(sizeof(NODE);last-next-data=x;return(last-next);NODE *difference(NODE *A ,NODE *B)NODE *C,*last;C=last=(NODE *)malloc(sizeof(NODE);while( (1) )if(A-data data)last=append(last,A-data);A=A-next;elseif( (2) )A=A-next;B=B-next;else (3) ;while( (4) )last=append(last,
12、A-data);A=A-next; (5) ;last=C;C=C-next;free(last);return(C);参考答案：(1) A!=NULL & B!=NULL(2) A-data=B-data(3) B=B-next;(4) A!=NULL(5) last-next=NULL;12.阅读以下算法，填充空格，使其成为完整的算法。其功能是在一个非递减的顺序存储线性表中(从下标1处开始存储)，删除所有值相等的多余元素。#define MAXSIZE 30typedef structint elemMAXSIZE;int length;/*表长*/sqlisttype;void exam21(sqlisttype *L)int i,j;i=1,j=2;while( (1) )if(L-elemi!=L-elemj)if(j!=(i+1) (2) ;L-length=L-length-(j-i-1); (3) ;else (4) ;if(jL-length) (5) ;参考答案：(1) jlength(2) for(int k=j;klength;k+)L-elemk-(j-i-1)=L-elemk;(
