《计算机软件基础》考试题库及答案

《《计算机软件基础》考试题库及答案》由会员分享，可在线阅读，更多相关《《计算机软件基础》考试题库及答案（37页珍藏版）》请在金锄头文库上搜索。

1、计算机软件基础考试题库及答案 计算机软件基础复习题库带答案1.线性表的链式存储结构与顺序存储结构相比优点是 CD。A. 所有的操作算法实现简单B. 便于随机存取C. 便于插入和删除D. 便于利用零散的存储器空间2.线性表是具有n个 C的有限序列。A. 表元素B. 字符C. 数据元素D. 数据项E. 信息项3.若长度为n的线性表采用顺序存储结构,在其第I个位置插入一个新元素的算法的时间复杂度为C 。(1In+1)A. O0B. O1C. OnD. On24.设A是一个线性表a1,a2,an,采用顺序存储结构,则在等概率的前提下,平均每插入一个元素需要移动的元素个数为 B,平均每删除一个元素需要移

2、动的元素个数为 A;若元素插在ai与ai+1之间0In-1的概率为,则平均每插入一个元素所要移动的元素个数为 C;ABCD5.下列函数中,按它们在时的无穷大阶数,最大的是 D。A. lognB. nlognC. 2n/2D. n!6.将下图所示的s所指结点加到p所指的结点之后,其语句应为: D 。A. s-nextp+1; p-nexts;C. s-nextp-next; p-nexts-next;D. s-nextp-next; p-nexts;7.将两个各有n个元素的有序表归并为一个有序表时,其最少的比较次数是 A 。A. nB. 2n-1C. n-1D. 2n8.下面的程序段是合并两个无

3、头结点链表ha和 hb为一个无头结点链表ha的过程,作为参数的两个链表都是按结点的data域由大到小链接的。合并后新链表的结点仍按此方式链接。请填写下述空框,使程序能正确运行。#define NULL 0typedef struct nodeint data;struct node *next;node, linklisttype;void combinelinklisttype *ha, linklisttype *hblinklisttype *h, *p;h linklisttype *mallocsizeoflinklisttype;h-next NULL;p h;whileha !

4、NULL & hb ! NULL ifha-datahb-data/*较大的元素先插入*/ p-next 1 ; p 2 ; 3 ;else p-next 4 ; p 5 ; 6 ; ifhaNULL7 ;ifhbNULL8 ;ha h-next;freeh;参考答案:1 ha2 p-next3 haha-next4 hb5 p-next6 hbhb-next7 p-nexthb8 p-nextha9.如果表A中所有元素a1,a2,an与表B的一个顺序子表bk,bk+1,bk+n-1完全相同(即a1bk,a2bk+1,anbk+n-1),则称表A包含在表B中。设ha,hb为带头结点的单链表,分

5、别表示有序表A和B,下面的函数用于判别表A是否包含在表B中,若是,则返回true,否则返回false。(提示:用递归实现)#define true 1#define false 0#define NULL 0typedef struct nodeint data;struct node *next;node, linklisttype;int inclusionlinklisttype *ha, linklisttype *hblinklisttype *pa, *pb;pa ha-next;pb hb-next; 1 ;while2 ifpa-datapb-data 3 ;else 4 ;

6、5 ;参考答案:1 ifpaNULL returntrue2 pb!NULL & pa-datapb-data3 returninclusionpa, pb4 pb pb-next;5 returnfalse10.在本题的程序中,函数create_link_listn建立一个具有n个结点的循环链表;函数josephusn,I,m对由create_link_listn所建立的具有n个结点的循环链表按一定的次序逐个输出,并删除链表中的所有结点。参数nn0指明循环链表的结点个数,参数I1In指明起始结点,参数m(m0是步长),指明从起始结点或前次被删除并输出的结点之后的第m个结点作为本次被输出并删除

7、的结点。例如,对于下图所示的具有6个结点的循环链表,在调用josephus6,3,2后,将输出5,1,3,6,4,2。请在空框处填上适当内容,每框只填一个语句。#define NULL 0typedef struct nodeint data;struct node *next;node, linklisttype;linklisttype *create_link_listint nlinklisttype *head, *p, *q;int I;head NULL;ifn0 head linklisttype *mallocsizeoflinklisttype; p head; forI1

8、;In-1;I+/*此循环用于建立一个链表,链表的内容从1至n-1*/ p-data I; q linklisttype *mallocsizeoflinklistttype; 1 ; 2 ; p-data n; 3 ;/*建立从尾链到首的环形结构*/ returnhead;void Josephusint n, int j, int mlinklisttype *p, *q;int j;p create_link_listn;for;I1;I-p p-next; 4 ;whilejnforI1;Im-1;I+p p-next; 5 ;printf“%8d”,q-data; 6 ;freeq;

9、jj+1; 参考答案:1 p-next q;2 p q;3 p-next head4 j05 qp-next;6 p-next q-next11.在下列程序中,函数differenceA,B用于求两集合之差CA-B,即当且仅当e是A中的一个元素,且不是B中的元素时,e是C中的一个元素。集合用有序链表实现,用一个空链表表示一个空集合,表示非空集合的链表根据元素之值按递增排列,执行CA-B之后,表示集合A和B的链表不变,若结果集合C非空,则表示它的链表应根据元素之值按递增序排列。函数append用于在链表中添加结点。#include #define NULL 0typedef struct nod

10、eint data;struct node *next;NODE;NODE *appendNODE *last, int xlast-nextNODE *mallocsizeofNODE;last-next-datax;returnlast-next;NODE *differenceNODE *A ,NODE *BNODE *C,*last;ClastNODE *mallocsizeofNODE;while1 ifA-data B-data lastappendlast,A-data; AA-next;elseif2 AA-next;BB-next;else 3 ;while4 lastapp

11、endlast,A-data; AA-next; 5 ; lastC; CC-next; freelast; returnC;参考答案:1 A!NULL & B!NULL2 A-dataB-data3 BB-next;4 A!NULL5 last-nextNULL;12.阅读以下算法,填充空格,使其成为完整的算法。其功能是在一个非递减的顺序存储线性表中从下标1处开始存储,删除所有值相等的多余元素。#define SIZE 30typedef struct int elemSIZE; int length;/*表长*/sqlisttype;void exam21sqlisttype *Lint

12、i,j;i1,j2;while1 ifL-elemi!L-elemj ifj!i+1 2 ; L-lengthL-length-j-i-1; 3 ; else 4 ; ifjL-length 5 ; 参考答案:1 jL-length2 forint kj;kL-length;k+L-elemk-j-i-1L-elemk;3 i+,ji+1;4j+;5L-lengthL-length-j-i-1;break;13.用单链表表示的链式队列的队头在链表的A 位置。A. 链头B. 链尾C. 链中14.若用单链表表示队列,则应该选用B 。A. 带尾指针的非循环链表B. 带尾指针的循环链表C. 带头指针的

13、非循环链表D. 带头指针的循环链表15.在解决计算机主机与打印机之间速度不匹配问题时,通常设置一个打印数据缓冲区,主机将要输出的数据依次写入该缓冲区,而打印机则从该缓冲区中取出数据打印,先放入打印缓冲区的数据先被打印。该缓冲区应该是一个B 结构。A. 堆栈B. 队列C. 数组D. 线性表16.若用一个大小为6的数组来实现循环队列,且当前rear和front的值分别为0和3。当从队列中删除一个元素,再加入两个元素后,rear和front的值分别为B 。A. 1和5B. 2和4C. 4和2D. 5和117.设栈的输入序列为1,2,10,输出序列为a1,a2,a10,若a510,则a7为 C 。A.

14、 4B. 8C.不确定D.718.设栈的输入序列是1,2,3,4,则D 不可能是其出栈序列。A. 1243B. 2134C. 1432D. 431219.以下D 是C语言中”abcd321ABCD”的子串。A. abcdB. 321ABC. “abcABC”D. “21AB”20.若串S”software”,其子串的数目是C 。A. 8B. 37C. 36D. 921.将一个A1:100,1:100的三对角矩阵,按行优先存入一维数组B1:298中,A中元素A66,65即该元素的下标在B数组中位置k为B 。A. 198B. 195C. 197D. 19622.设高为h的二叉树只有度为0和2的结点,则此类二叉树的结点数至少为B ,至多为 F 。高为h的完全二叉树的结点数至少为 E ,至多为 F 。A. 2hB. 2h-1C. 2h+1D.h+1E. 2h-1F. 2h-1G. 2h+1-1H. 2h+123.一棵有124个叶结点的完全二叉树,最多有B 个结点。A. 247B. 248C. 2