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

1、.计算机软件技术基础试题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(n 2)4. 设 A 是一个线性表 (a 1,a 2, ,a n) ，采用顺序存储结构，则在等概率的前提下，平均每插入一个元素需要移动的元素个数为B

2、，平均每删除一个元素需要移动的元素个数为A；若元素插在 ai 与 ai+1 之间 (0 I n-1) 的概率为 2(ni ) ，则平均每插入一个n(n1)元素所要移动的元素个数为C；A. n1B. n222n13n1C.D.3n45. 下列函数中，按它们在时的无穷大阶数，最大的是D。A. lognB. nlognC. 2 n/2D. n!6. 将下图所示的s 所指结点加到p 所指的结点之后，其语句应为：D。nextnextpsnextA. s->next=p+1; p->next=s;B. (*p).next=s; (*s).next=(*p).next;C. s->next

3、=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 *

4、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)

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 中所有元素 (a 1,a 2, ,a n) 与表 B 的一个顺序子表 (b k,b k+1, bk+n-1) 完全相同（即 a1=bk ,a 2=bk+1 , an=bk+n-1 ），则称表 A 包含在表 B 中。设 ha， hb

6、为带头结点的单链表，分别表示有序表 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)

7、;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

8、 个结点的循环链表按一定的次序逐个输出，并删除链表中的所有结点。参数n(n>0) 指明循环链表的结点个数，参数I(1I n) 指明起始结点，参数m（ m>0是步长），指明从起始结点或前次被删除并输出的结点之后的第m个结点作为本次被输出并删除的结点。例如，对于下图所示的具有6 个结点的循环链表，在调用josephus(6,3,2)后，将输出5,1,3,6,4,2。请在空框处填上适当内容，每框只填一个语句。#define NULL 0typedef struct nodeint data;struct node *next;node, linklisttype;linklisttype

9、 *create_link_list(int n)linklisttype *head, *p, *q;int I;head = NULL;if(n>0)head = (linklisttype *)malloc(sizeof(linklisttype);p = head;for(I=1;I<=n-1;I+)/* 此循环用于建立一个链表，链表的内容从1 至 n-1*/p->data = I;q = (linklisttype *)malloc(sizeof(linklistttype);(1) ;(2) ;p->data = n;(3);/* 建立从尾链到首的环形结构*

10、/.return(head);void Josephus(int n, int j, int m)linklisttype *p, *q;int j;p = create_link_list(n);for(;I>1;I-)p = p->next;(4) ;while(j<n)for(I=1;I<=m-1;I+) p = p->next;(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)

11、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 <stdio.h>#define NULL 0typ

12、edef 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 < B->data)last=appen

13、d(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. 阅读以下算法，填充空格，使其成

14、为完整的算法。其功能是在一个非递减的顺序存储线性表中 ( 从下标 1 处开始存储 ) ，删除所有值相等的多余元素。#define MAXSIZE 30typedef structint elemMAXSIZE;int length;/*表长 */sqlisttype;void exam21(sqlisttype *L)int I,j;I=2,j=1;while(1)if(L->elemI<>L->elemj).(2) ;(3) ;I+;(4) ;参考答案：(1) i<=L->length(2)(3) j+;(4)13.用单链表表示的链式队列的队头在链表的A位

15、置。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和 5

16、B. 2和 4C. 4和 2D. 5和 117.设栈的输入序列为1,2，,10 ，输出序列为 a ,a, ,a10，若 a =10，则 a 为C。1257A. 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

17、: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. 2 h-1F. 2 h-1G. 2 h+1-1H. 2 h+123.一棵有124 个叶结点的完全二叉树，最多有B个结点。A. 247B.248C. 249D. 25124. 若从二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序，则该二叉.elseif(e

18、lse#define MAXSIZE 30 typedef struct btnodeint data;struct btnode *lchild, *rchild; BTN;.树是C。A.满二叉树B.哈夫曼树C.堆D. 二叉查找树25.前序遍历和中序遍历结果相同的二叉树为F；前序遍历和后序遍历结果相同的二叉树为B。A.一般二叉树B.只有根结点的二叉树C.根结点无左孩子的二叉树D. 根结点无右孩子的二叉树E.所有结点只有左孩子的二叉树F.所有结点只有右孩子的二叉树26.具有 n 个结点的完全二叉树，已经顺序存储在一维数组A1.n 中，下面的算法是将 A中顺序存储变为二叉链表存储的完全二叉树。请

19、填写适当语句在下面的空格内，完成上述算法。void createtree(BTN *p,int A, int I,int n)(1);p->data=AI;if(2)(3);p->lchild=NULL;(4)createtree(5);p->rchild=NULL;void btree(BTN * p ,int A,int n)createtree(p,A,1,n);参考答案：(1) p=(BTN *)malloc(sizeof(BTN)(2) 2*I<=n(3) createtree(p->lchild,A,2*I,n)(4) 2*I+1<=n(5) p

20、->rchild,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 个记录的有序顺序表中进行折半查找，最大的比较次数是log 2 n1 。31.Hash

21、 技术广泛应用于查找过程，选择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.希尔排

22、序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排

23、序法。A.插入排序B. 交换排序C.选择排序D. 归并排序40.直接插入排序在最好情况下的时间复杂度为B。A. O(logn)B. O(n)C. O(nlogn)D. O(n2)41. 下面函数是将任意序列调整为最大堆的算法，请将空白部分填上：将任意序列调整为最大堆通过不断调用adjust 函数，即for(i=n/2;i>0;i-) adjust(list, i, n);其中 list为待调整序列所在数组（从下标1 开始）， n 为序列元素的个数。void adjust(int list, int root, int n)/* 将以 root为下标的对应元素作为待调整堆的根，待调整元素放

24、在list数组中， 最大元素下标为 n*/int child,rootkey;.rootkey =(1) ;child = 2*root;while(child < n)if(child<n) && (listchild<listchild+1)(2) ;if(rootkey > listchild) break;elselist (3) =listchild;(4) ;list(5)=rootkey;参考答案：(1) listroot(2) child+;(3) child/2(4) child *= 2;(5) child/241. 表是一种数据结构

25、，链表是一种(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. 操作系统

26、主要是对计算机系统全部(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.

27、汇编D. C(5):A. 网络B. 分时C. 批处理D. 实时答案： CBBDD43. 本程序从键盘读入整数，并按从大到小的顺序输出输入整数中互不相等的那些整数。程序一边读入整数， 一边构造一个从大到小顺序链接的链表，直至不能从键盘读入整数，然后顺序输出链表上各表元的整数值。主函数每读入一个整数，就调用函数insert()，函数 insert() 将还未出现在链表上的整数按从大到小的顺序插入到链表中。为了插入方便，链表在表首有一个辅助表元。阅读下列C代码，在(n)处填入相应的字句以完成上述功能。#include <stdio.h>#include <malloc.h>#

28、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 < v->val)/* 寻找插入位置*/u=v;v=u->next;if(v=NULL |(2)/* 判断是否要插入表元*/p = (NODE *)malloc(sizeof(NODE);p->val = x;/* 生成新表元 */(3)= v;(4)= p; /*插

29、入新表元 */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

30、(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. 数据

31、值与符号B. 数据与指针C. 数据与表名D. 头地址与尾地址(4):A. 随机查找B. 顺序查找C. 二分法查找D. 浏览(5):A. 随机查找B. 顺序查找C. 二分法查找D. 浏览答案： CDBBC45. 本程序用于从链盘读入整数，插入到链表，或从链表删除一个整数。阅读下面的C 代码，将应填入(n)处的字名写在答卷的对应栏内。#include <stdio.h>#include <malloc.h>typedef struct nodeint val;struct node * next;NODE;NODE * ins(NODE *list, int x)/* 将

32、x 按从小到大的次序插入链表*/NODE *u, *v=list, *p;for(; v != NULL && x < v->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,

33、 int x) /*从链表中删除值为x 的表元 */NODE *u, *v;for(v = list; v != NULL && x < v->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)p

34、rintf(“ 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->ne

35、xt = 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

36、.交换C. 比较D. 散列(4):A. 外部B.内部C. 外存D. 内存(5):A. 运算量大小与占用存储多少B. 运算量大小与处理的数据量大小C. 并行处理能力和占用存储多少D. 占用存储多少和处理的数据量大小答案： BAABA47. 操作系统是对计算机资源进行的(1)系统软件，是(2)的接口。在处理机管理中， 进程是一个重要的概念， 它由程序块、(3)和数据块三部分组成，它有3 种基本状态，不可能发生的状态转换是(4)。虚拟存储器的作用是允许程序直接访问比内存更大的地址空间，它通常使用(5)作为它的一个主要组成部分。供选答案：(1):A.输入和输出B.键盘操作C.管理和控制D. 汇编和执行

37、(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;i<n;i+)y=y+1;for(j=0;j<=(2*n);j+)x+;供选答案：A. O(n-1)B. O(2n)C. O

38、(n 2)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;i<=n;i+)s=a+b;b=a;a=s;供选答案：A. O(1)B. O(n)C. O(log 2n)D. O(n 2)52.数据结构是一门研究非数值计算的程序设计问题中，计算机的A以及它们之间的关系和运算等的学科。A. 操作对象B. 计算方法C. 逻辑存储D. 数据映象53.在数据结构中，从逻辑上可以把数据结构分成C。A.动态

39、结构和静态结构B. 紧凑结构和非紧凑结构C.线性结构和非线性结构D. 内部结构和外部结构54.算法分析的目的是C。A. 找出数据结构的合理性B. 研究算法中输入和输出的关系C. 分析算法的效率以求改进D. 分析算法的易懂性和文档性55.算法分析的两个主要方面是(4)。A.间复杂性和时间复杂性B. 正确性和简明性C.可读性和文档性D. 数据复杂性和程序复杂性56.一个线性顺序表第一个元素的存储地址是100，每个元素的长度为2，则第 5 个元素的地址为B。A. 110B. 108C. 100D. 12057.若已知一个栈的入栈序列是1,2,3, ,n ，其输出序列为 P1,P 2,P 3, ,P

40、n，若 P1=n，则 Pi为C。A. iB. n-iC. n-i+1D. 不确定58.对于一个栈，给出输入项A,B,C 。如果输入项序列由A,B,C 所组成，则不可能产生的输出序列是A。A. CABB. CBAC. ABCD. ACB59. 设有如下的单链表的按序号查找的算法，其时间复杂度为B。LinkNode *GetNode(Linklist head, int i)int j;ListNode *p;P = head; j=0;while(p->next && j<i)p = p->next;j+;if(i=j).return(p);elsereturn

41、(NULL);供选答案：A. O(n 2)B. O(2n)C. O(n 3)D. O(logn)60. 二维数组Amn按行序为主顺序存放在内存中，每个数组元素占1 个存储单元，则元素aij的地址计算公式是C。A. LOC(aB. LOC(aC. LOC(aD. LOC(aijijijij) = LOC(a 11)+(i-1)*m+(j-1) = LOC(a 11)+(j-1)*m+(i-1) = LOC(a 11)+(i-1)*n+(j-1) = LOC(a 11)+(j-1)*n+(i-1)61.以下哪一个不是队列的基本运算C。A.从队尾插入一个新元素B.从队列中删除第i个元素C.判断一个队

42、列是否为空D. 读取队头元素的值62.在一个长度为n 的顺序表中， 向第 i个元素之前插入一个新元素，需向后移动B个元素。A. n-iB. n-i+1C. n-i-1D. i63.从一个长度为n 的顺序表中删除第i个元素时，需向前移动A个元素。A. n-iB. n-i+1C. n-i-1D. i64.在具有 n 个单元的顺序存储的循环队列中， 假定 front和 rear分别为队首指针和队尾指针，则判断队空的条件是B。A. front=rear+1B. front=rearC. front+1=rearD. front=065.从一个具有 n 个结点的单链表中查找其值等于x 的结点时，在查找成

43、功的情况下，需平均比较D个结点。A. nB. n/2C. (n-1)/2D. (n+1)/266.一个栈的入栈序列是a,b,c,d,e ，则栈不可能的输出序列是C。A. edcbaB. decbaC. dceabD. abcde67.栈结构通常采用的两种存储结构是A。A.顺序存储结构和链表存储结构B.散列方式和索引方式C.链表存储结构和数组D. 线性存储结构和非线性存储结构68.判断一个顺序栈 ST（最多元素为mo）为空的条件是B。A. ST->top<>0B. ST->top=0C. st->top<>moD. st->top=mo69.不带头结点的单链表head 为空表的判定条件是A。A. head=NILLB. head->next=NULL C. head->next=head D. head