2021年计算机软件基础复习题库带答案.doc

计算机软件基本复习题库(带答案)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) ，平均每删除一种元素需要移动元素个数为 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=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)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) ;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) 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 *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(false)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 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-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-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 *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,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;(3) i+,j=i+1;(4)j+;(5)L-length=L-length-(j-i-1);break;13.用单链表表达链式队列队头在链表 A 位置。A. 链头B. 链尾C. 链中14.若用单链表表达队列，则应当选用 B 。A. 带尾指针非循环链表B. 带尾指针循环链表C. 带头指针非循环链表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，若a5=10，则a7为 C 。A. 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. 249D. 25124.若从二叉树任一结点出发到根途径上所通过结点序列按其核心字有序，则该二叉树是 C 。A. 满二叉树B. 哈夫曼树C. 堆D. 二叉查找树25.前序遍历和中序遍历成果相似二叉树为 F ；前序遍历和后序遍历成果相似二叉树为 B 。A. 普通二叉树B. 只有根结点二叉树C. 根结点无左孩子二叉树D. 根结点无右孩子二叉树E. 所有结点只有左孩子二叉树F. 所有结点只有右孩子二叉树26.具备n个结点完全二叉树，已经顺序存储在一维数组A1.n中，下面算法是将A中顺序存储变为二叉链表存储完全二叉树。请填写恰当语句在下面空格内，完毕上述算法。#define MAXSIZE 30typedef struct btnodeint data;struct btnode *lchild，*rchild;BTN;void createtree(BTN *p,int A，int I,int n) (1) ;p-data=AI;if( (2) ) (3) ;elsep-lchild=NULL;if( (4) )createtree( (5) );elsep-rchild=NULL;void btree(BTN * p ,int A,int n)createtree(p,A,1,n);参照答案：(1) p=(BTN *)malloc(sizeof(BTN)(2) 2*Ilchild,A,2*I,n)(4) 2*I+1rchild,A,2*I+1,n27.若在线性表中采用折半查找法查找元素，该线性表应当 C 。A. 元素按值有序B. 采用顺序存储构造C. 元素按值有序，且采用顺序存储构造D. 元素按值有序，且采用链式存储构造28.在分块检索中，对256个元素线性表提成 16 块最佳，每块最佳长度是 16 ；若每块长度为8，其平均检索长度为 21 。29.假定有K个核心字互为同义词，若用线性探测法把这K个核心字存入散列表中，至少要进行 D 次探测。A. K-1次B. K次C. K+1次D. K(K+1)/2次30.在n个记录有序顺序表中进行折半查找，最大比较次数是。31.Hash技术广泛应用于查找过程，选取Hash函数原则是 和 。解决冲突技术有优有劣，其共同原则是 。32.在下述排序算法中，所需辅助存储空间最多是 B ，所需辅助存储空间最小是 C ，平均速度最快是 A 。A.迅速排序B. 归并排序C. 堆排序33.在文献局部有序或文献长度较小状况下，最佳内部排序办法是 A 。A. 直接插入排序B. 冒泡排序C. 简朴选取排序34.迅速排序在最坏状况下时间复杂度是O(n2)，比 A 性能差。A. 堆排序B. 冒泡排序C. 简朴选取排序35.若需在O(nlogn)时间内完毕对数组排序，且规定排序是稳定，则可选取排序办法是 C 。A. 迅速排序B. 堆排序C. 归并排序D. 希尔排序36.如果只想得到1000个元素构成序列中第5个最小元素之前某些排序序列，用 B 办法最快。A. 冒泡排序B. 迅速排序C. 希尔排序D. 堆排序E. 简朴选取排序37.如下结点序列是堆为 A 。A. 100,90,80,60,85,75,20,25,10,70,65,50B. 100,70,50,20,90,75,60,25,10,85,65,8038.若要尽量快地完毕对实数数组排序，且规定排序是稳定，则应选 C 。A. 迅速排序B. 堆排序C. 归并排序D. 希尔排序39.从未排序序列中依次取出一种元素与已排序序列中元素依次进行比较，然后将其放在已排序序列适当位置，该排序办法称为 A 排序法。A. 插入排序B. 互换排序C. 选取排序D. 归并排序40.直接插入排序在最佳状况下时间复杂度为 B 。A. O(logn)B. O(n)C. O(nlogn)D. O(n2)41.下面函数是将任意序列调节为最大堆算法，请将空白某些填上：将任意序列调节为最大堆通过不断调用adjust函数，即for(i=n/2;i0;i-) adjust(list，i，n);其中list为待调节序列所在数组（从下标1开始），n为序列元素个数。void adjust(int list，int root，int n)/*将以root为下标相应元素作为待调节堆根，待调节元素放在list数组中，最大元素下标为n*/int child,rootkey;rootkey = (1) ;child = 2*root;while(child n)if(childn) & (listchild listchild)break;elselist (3) =listchild; (4) ;list (5) =rootkey;参照答案：(1) listroot(2) child+;(3) child/2(4) child *= 2;(5) child/241.表是一种数据构造，链表是一种 (1) 。队列和栈都是线性表，栈操作特性是 (2) ，队列操作特性是 (3) 。今有一空栈S，对下列待进栈数据元素序列a,b,c,d,e,f依次进栈、进栈、出栈、进栈、进栈、出栈操作，则此操作完毕后，栈S栈顶元素为 (4) ，栈底元素为 (5) 。供选答案：(1):A. 非顺序存储线性表B. 非顺序存储非线性表C. 顺序存储线性表D. 顺序存储非线性表(2):A. 随机进出B. 先进后出C. 先进先出D. 出优于进(3):A. 随机进出B. 先进后出C. 后进后出D. 进优于出(4):A. fB. cC. aD. b(5):A. bB. cC. aD. d答案：ABCBC42.操作系统重要是对计算机系统所有 (1) 进行管理，以以便顾客、提高计算机使用效率一种系统软件。它重要功能有：解决机管理、存储管理、文献管理、 (2) 管理和设备管理等。Windows和Unix是最惯用两类操作系统。前者是一种具备图形界面窗口式 (3) 系统软件，后者是一种基本上采用 (4) 语言编制而成系统软件。在 (5) 操作系统控制下，计算机能及时解决由过程控制反馈信息并作出响应。供选答案：(1):A. 应用软件B. 系统软硬件C. 资源D. 设备(2):A. 数据B. 作业C. 中断D. I/O(3):A. 分时B. 多任务C. 多顾客D. 实时(4):A. PASCALB. 宏C. 汇编D. C(5):A. 网络B. 分时C. 批解决D. 实时答案：CBBDD43.本程序从键盘读入整数，并按从大到小顺序输出输入整数中互不相等那些整数。程序一边读入整数，一边构造一种从大到小顺序链接链表，直至不能从键盘读入整数，然后顺序输出链表上各表元整数值。主函数每读入一种整数，就调用函数insert()，函数insert()将尚未出当前链表上整数按从大到小顺序插入到链表中。为了插入以便，链表在表首有一种辅助表元。阅读下列C代码，在 (n) 处填入相应字句以完毕上述功能。#include #include #define NULL 0typedef struct nodeint val;struct node *next;NODE;void insert(NODE *list,int x)NODE *u，*v，*p;u = list；v = u-next;while( (1) & x val)/*寻找插入位置*/u=v;v=u-next;if(v=NULL | (2) )/*判断与否要插入表元*/p = (NODE *)malloc(sizeof(NODE);p-val = x;/*生成新表元*/ (3) = v； (4) = p;/*插入新表元*/main()int x;NODE *head，*p;/*一方面建立只有辅助表元空链表*/head = (NODE *)malloc(sizeof(NODE); (5) =NULL;printf(“Enter Integers:n”);while(scanf(“%d”,&x) = 1)/*重复读入整数插入链表*/insert(head,x);for(p=head-next;p!=NULL;p=p-next)/*输出链表*/printf(“%dt”,p-val);printf(“n”);答案：(1) v != NULL或v(2) x v-val 或 x != v-val(3) p-next(4) u-next(5) head-next44.计算机数据解决对象是具备不同构造各种数据，可以访问最小数据信息单位是 (1) ，可以引用最小命名数据单位是 (2) 。线性表是最简朴一种数据构造，有顺序和链接两种存储方式。线性表按链接方式存储时，每个结点涉及 (3) 两某些。线性表查找有 (4) 和 (5) 两种，但 (5) 只能用于顺序存储状况。供选答案：(1):A. 数字B. 字符C. 数据元素D. 数据项(2):A. 结点B. 记录C. 数据元素D. 数据项(3):A. 数据值与符号B. 数据与指针C. 数据与表名D. 头地址与尾地址(4):A. 随机查找B. 顺序查找C. 二分法查找D. 浏览(5):A. 随机查找B. 顺序查找C. 二分法查找D. 浏览答案：CDBBC45.本程序用于从链盘读入整数，插入到链表，或从链表删除一种整数。阅读下面C代码，将应填入 (n) 处字名写在答卷相应栏内。#include #include typedef struct nodeint val;struct node * next;NODE;NODE * ins(NODE *list，int x)/*将x按从小到大顺序插入链表*/NODE *u，*v=list，*p;for(；v != NULL & x val ；v = v-next);/*寻找插入位置*/if(v != NULL & x = v-val) return(list); /*已有，被忽视*/p = (NODE *)malloc(sizeof(NODE);p-val=x；/*生成新表元*/if(v = list) list = p;else (1) ; (2) ;return list;NODE * del(NODE * list，int x)/*从链表中删除值为x表元*/NODE *u，*v;for(v = list；v != NULL & x valu；u=v;v=v-next);if(v != NULL & x = v-val)/*找到值为x表元*/if(v = list)list = list-next;else (3) ; (4) ;/*释放空间*/elseprintf(“没有找到!n”);return(list);main()int x,ans;NODE * list=NULL，*p;while(1)printf(“n输入1：将整数插入到链表。n输入2：从链表删除一种整数。n”);printf(“其他整数，结束程序。nt请输入选取！”);scanf(%d,&ans);if( (5) )return;printf(“输入整数：”);scanf(“%d”,&x);if(ans=1)list=ins(list,x);elselist=del(list,x);for(p=list;p!=NULL;p=p-next)printf(“%4d”,p-val);答案：(1) u-next = p;(2) p-next = v(3) u-next = v-next(4) free(v)(5) ans != 1 & ans != 246. 从未排序序列中，依次取出元素，与已排序序列元素比较后，放入已排序序列中恰当位置上，这是 (1) 排序。从未排序序列中，挑选出元素，放在已排序序列某一端位置，这是 (2) 排序。逐次将待排序序列中相邻元素两两比较，凡是逆序则进行互换，这是 (3) 排序。如果整个排序过程都在内存中进行，称为 (4) 排序。排序算法复杂性与排序算法 (5) 关于。供选答案：(1):A. 选取B. 插入C. 比较D. 归并(2):A. 选取B. 插入C. 比较D. 归并(3):A. 冒泡B. 互换C. 比较D. 散列(4):A. 外部B. 内部C. 外存D. 内存(5):A. 运算量大小与占用存储多少B. 运算量大小与解决数据量大小C. 并行解决能力和占用存储多少D. 占用存储多少和解决数据量大小答案：BAABA47.操作系统是对计算机资源进行 (1) 系统软件，是 (2) 接口。在解决机管理中，进程是一种重要概念，它由程序块、 (3) 和数据块三某些构成，它有3种基本状态，不也许发生状态转换是 (4) 。虚拟存储器作用是容许程序直接访问比内存更大地址空间，它普通使用 (5) 作为它一种重要构成某些。供选答案：(1):A. 输入和输出B. 键盘操作C. 管理和控制D. 汇编和执行(2):A. 软件和硬件B. 主机和外设C. 高档语言和机器语言D. 顾客和计算机(3):A. 进程控制块B. 作业控制块C. 文献控制块D. 设备控制块(4):A. 运营态转换为就绪态B. 就绪态转换为运营态C. 运营态转换为等待态D. 等待态转换为运营态(5):A. 软盘B. 硬盘C. CDROMD. 寄存器答案：CDADB48. A 是信息载体，它可以被计算机辨认、存储和加工解决。A. 数据B. 数据元素C. 结点D. 数据项49.下列程序段时间复杂度为 C 。for(i=1;in;i+)y=y+1;for(j=0;j=(2*n);j+)x+;供选答案：A. O(n-1)B. O(2n)C. O(n2)D. O(2n+1)50.下面程序段时间复杂度为 D 。i=1;while(i=n)i=i*2;供选答案：A. O(1)B. O(n)C. O(n2)D. O(log2n)51.下面程序段时间复杂度为 B 。a=0;b=1;for(i=2;inext & jnext;j+;if(i=j)r