《《计算机软件技术基础》试题答案》由会员分享，可在线阅读，更多相关《《计算机软件技术基础》试题答案（38页珍藏版）》请在金锄头文库上搜索。
1、计算机软件技术基础试题1 .线性表的链式存储结构与顺序存储结构相比优点是CD 。A.所有的操作算法实现简单B.便于随机存取C.便于插入和删除D.便于利用零散的存储器空间2 .线性表是具有n个C的有限序列。A.表元素B.字符C.数据元素D.数据项E.信息项3 .若长度为n的线性表采用顺序存储结构，在其第I个位置插入一个新元素的算法的时间复杂度为 C 。(iwiwn+l)A. O(0)B. O(1)C. O(n)D. O(n 2)4.设A是一个线性表(ai,a2,an),采用顺序存储结构，则在等概率的前提下，平均每插入 一个元素需要移动的元素个数为 B,平均每删除一个元素需要移动的元素个数为；若兀
2、素插在则平均每插入一个a与ai+1之间(0 w I w n-1)的概率为2(n i)n(n 1)元素所要移动的元素个数为A.C.n 122n 1B.D.n23n 135.下列函数中，按它们在A. log n4时的无穷大阶数，最大的是n/2C. 26.将下图所示的B. nlog nD. n!s所指结点加到p所指的结点之后，其语句应为:nextnextnextA. 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.
3、将两个各有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) linklisttyp
4、e *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 = _(3)(2)elsep-next =(4);(8) if(ha=NULL) if(hb=NULL) ha = h-next; free(h);参考答案ha(4) hb p-next=hb(2) p-next(5) p-next9.如果表中所有元素(a i,a 2,a n)与表(3) ha
5、=ha-next(6) hb=hb-next(8) p-next=ha的一个顺序子表(b k,b k+1,力k+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 *next;node, linklisttype;int inc
6、lusion(linklisttype *ha, linklisttype *hb) linklisttype *pa, *pb;pa = ha-next;pb = hb-next; ； while( (2)if(pa-data=pb-data)(3);else(4);； 参考答案：(1) if(pa=NULL) return(true)(2) pb!=NULL & pa-data=pb-data (3) return(inclusion(pa, pb)(4) pb = pb-next;(5) return(false)10.在本题的程序中，函数 create_link_list(n) 建立一
7、个具有 n个结点的循环链表；函数 josephus(n,I,m) 对由create_link_list(n) 所建立的具有 n个结点的循环链表按一定的次 序逐个输出，并删除链表中的所有结点。参数 n(n0)指明循环链表的结点个数，参数 I(1 w I w n)指明起始结点，参数m (m0是步长)，指明从起始结点或前次被删除并输出的结点之后的第m个结点作为本次被输出并删除的结点。 例如，对于下图所示的具有 6个结点的循 环链表，在调用josephus(6,3,2) 后，将输出5,1,3,6,4,2。请在空框处填上适当内容，每框只填一个语句。#define NULL 0typedef struct
8、 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); ；p-data = n;；/*建立从尾链到首的环形结构*/ret
9、urn(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-next = q-next11.在下列程序中，函数difference(A,
10、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 *last, int x)last-next=(NODE *)mall
11、oc(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( )if(A-data data)last=append(last,A-data); A=A-next; else if( (2)A=A-next; B=B-next; else ； while( (4)last=append(last,A-data); A=A-next; ；last=C; C=C-next; f
12、ree(last); return(C); 参考答案：(1) A!=NULL & B!=NULL(2) A-data=B-data B=B-next;(4) A!=NULL(5) last-next=NULL;12.阅读以下算法，填充空格，使其成为完整的算法。其功能是在一个非递减的顺序存储线 性表中(从下标1处开始存储)，删除所有值相等的多余元素。#define MAXSIZE 30 typedef structint elemMAXSIZE;int length;/* 表长 */ sqlisttype;void exam21(sqlisttype *L) int I,j;I=2,j=1; w
13、hile()if(L-elemIL-elemj)(2)；I+;(4)；参考答案：(1) ilength(2) j+；(4)13 .用单链表表示的链式队列的队头在链表的A位置。A.链头B.链尾C.链中14 .若用单链表表示队列，则应该选用B。A.带尾指针的非循环链表B.带尾指针的循环链表C.带头指针的非循环链表D.带头指针的循环链表15 .在解决计算机主机与打印机之间速度不匹配问题时，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印，先放入打印缓冲区的数据先被打印。该缓冲区应该是一个B 结构。A.堆栈B.队列C.数组D.线性表16.若用一个大小为
14、6的数组来实现循环队列, 从队列中删除一个元素，再加入两个元素后，且当前rearrear和 front和front的值分别为0和3。当的值分别为_B。A. 1 和 5B. 2 和 4C. 4 和 2D. 5 和 117.设栈的输入序列为1,2 ,10,输出序列为a1,a2,，a io,若 a5=10,则a7 为 CcA. 4B. 8C.不确定D.718.设栈的输入序列是1,2,3,4 ,则 D不可能是其出栈序列。A. 1243B.2134C.1432D.431219.以下 D是C语言中 abcd321ABCD的子串。A. abcdB. 321ABC. abcABCD.“21AB20.右用S= software ,其子串的数目是A. 8B. 37C。C. 36D.921.将一个 A1:100,1:100 的三对角矩阵,A66,65(即该元素
