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,a n)，采用顺序存储结构，则在等概率的前提下，平均每插入一个元素需要移动的元素个数为 B ，平
2、均每删除一个元素需要移动的元素个数为word 文档 可自由编辑 A ；若元素插在 ai 与ai+1 之间(0In-1)的概率为2(nn(ni)，则平均每插入一个1)元素所要移动的元素个数为 C ；n1A.2nB.22n 1C.33n 1D.45. 下列函数中，按它们在n 时的无穷大阶数，最大的是 D 。A. lognB. nlognC. 2n/2D. n! next next p s next 6. 将下图所示的 s 所指结点加到p 所指的结点之后，其语句应为： D 。A. s-next=p+1; p-next=s; B. (*p).next=s; (*s).next=(*p).next; C
3、. s-next=p-next; p-next=s-next; D. s-next=p-next; p-next=s; 7. 将两个各有 n 个元素的有序表归并为一个有序表时，其最少的比较次数是 A 。A. nB. 2n-1 C. n-1D. 2n 8. 下面的程序段是合并两个无头结点链表(ha 和hb) 为一个无头结点链表 ha 的过程，作为参数的两个链表都是按结点的data 域由大到小链接的。合并后新链表的结点仍按此方式链接。请填写下述空框，使程序能正确运行。#define NULL 0 typedef struct node int data; struct node *next; no
4、de, 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) ; else p-next = (4) ; p = (5) ; (6) ; if(ha=NULL)
5、 (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=ha 9. 如果表 A 中所有元素(a1,a2,a n )与表 B 的一个顺序子表(bk,bk+1,b k+n-1)完全相同（即 a1 =bk ,a2=bk+1 ,a n=bk+n-1 ），则称表 A 包含在表B 中。设 ha，hb 为带头结点的单链表，分别表示有序表A 和 B，下面的函数用于判别表A 是
6、否包含在表B 中，若是，则返回true，否则返回 false。（提示：用递归实现）#define true 1 #define false 0 #define NULL 0 typedef struct node int 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)
7、; 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)指明循环链表的结点个数，参
8、数 I(1In)指明起始结点，参数m（m0 是步长），指明从起始结点或前次被删除并输出的结点之后的第m 个结点作为本次被输出并删除的结点。例如，对于下图所示的具有6 个结点的循环链表，在调用josephus(6,3,2)后，将输出 5,1,3,6,4,2。请在空框处填上适当内容，每框只填一个语句。#define NULL 0 typedef struct node int data; struct node *next; node, linklisttype; linklisttype *create_link_list(int n) linklisttype *head, *p, *q; i
9、nt 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
10、(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-next 11. 在下列程序中，函数 difference(A,B)用于求两集合之差C=A-B，即当且仅当 e 是A 中的一个元素，且不是B 中的元素时，e 是 C 中的一个元素。集合用有序链表实现，用一个
11、空链表表示一个空集合，表示非空集合的链表根据元素之值按递增排列，执行 C=A-B 之后，表示集合A 和 B 的链表不变，若结果集合C 非空，则表示它的链表应根据元素之值按递增序排列。函数 append()用于在链表中添加结点。#include #define NULL 0 typedef struct node int data; struct node *next; NODE; NODE *append(NODE *last, int x) last-next=(NODE *)malloc(sizeof(NODE); last-next-data=x; return(last-next);
12、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; else if( (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
13、) A!=NULL & B!=NULL (2) A-data=B-data (3) B=B-next; (4) A!=NULL (5) last-next=NULL; 12. 阅读以下算法，填充空格，使其成为完整的算法。其功能是在一个非递减的顺序存储线性表中(从下标 1 处开始存储)，删除所有值相等的多余元素。#define MAXSIZE 30 typedef struct int elemMAXSIZE; int length;/*表长*/ sqlisttype; void exam21(sqlisttype *L) int I,j; I=2,j=1; while( (1) ) if(L-
14、elemIL-elemj) (2) ; (3) ; I+; (4) ; 参考答案：(1) ilength (2) (3) j+; (4) 13. 用单链表表示的链式队列的队头在链表的 A位置。A. 链头B. 链尾C. 链中14. 若用单链表表示队列，则应该选用 B。A. 带尾指针的非循环链表B. 带尾指针的循环链表C. 带头指针的非循环链表D. 带头指针的循环链表15. 在解决计算机主机与打印机之间速度不匹配问题时，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印，先放入打印缓冲区的数据先被打印。该缓冲区应该是一个 B结构。A. 堆栈B. 队列
15、C. 数组D. 线性表16. 若用一个大小为6 的数组来实现循环队列，且当前rear 和 front 的值分别为0 和 3。当从队列中删除一个元素，再加入两个元素后，rear 和 front 的值分别为 B。 A. 1 和 5B. 2 和 4 C. 4 和 2D. 5 和 1 17.设栈的输入序列为1,2，,10， 输出序列为a1,a2,a 10，若 a5=10，则 a7 为 C 。A. 4B. 8C.不确定D.7 18. 设栈的输入序列是1,2,3,4，则 D不可能是其出栈序列。A1243B. 2134C. 1432D. 4312 19. 以下 D是 C 语言中”abcd321ABCD”的子
16、串。A. abcdB. 321ABC. “abcABC”D. “21AB”20. 若串 S=”software”，其子串的数目是 C。A. 8B. 37C. 36D. 9 21. 将一个 A1:100,1:100的三对角矩阵，按行优先存入一维数组 B1:298中，A 中元素A66,65(即该元素的下标)在 B 数组中位置k 为 B。A. 198B. 195C. 197D. 196 22. 设高为 h 的二叉树只有度为0 和 2 的结点，则此类二叉树的结点数至少为 B ， 至多为 F 。高为h 的完全二叉树的结点数至少为 E ，至多为 F 。A2hB. 2h-1 C. 2h+1D.h+1 E.
17、2h-1F. 2h-1 G. 2h+1-1 H. 2h+1 23. 一棵有 124 个叶结点的完全二叉树，最多有 B个结点。A. 247B. 248C. 249D. 251 24. 若从二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序，则该二叉树是 C。A. 满二叉树B. 哈夫曼树C. 堆D. 二叉查找树25. 前序遍历和中序遍历结果相同的二叉树为 F；前序遍历和后序遍历结果相同的二叉树为 B。A. 一般二叉树B. 只有根结点的二叉树C. 根结点无左孩子的二叉树D. 根结点无右孩子的二叉树E. 所有结点只有左孩子的二叉树F. 所有结点只有右孩子的二叉树26. 具有 n 个结点的完
18、全二叉树，已经顺序存储在一维数组A1.n中，下面的算法是将 A 中顺序存储变为二叉链表存储的完全二叉树。请填写适当语句在下面的空格内，完成上述算法。#define MAXSIZE 30 typedef struct btnode int data; struct btnode *lchild, *rchild; BTN; void createtree(BTN *p,int A, int I,int n) (1) ; p-data=AI; if( (2) ) (3) ; else p-lchild=NULL; if( (4) ) createtree( (5) ); else p-rchild
19、=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,n 27. 若在线性表中采用折半查找法查找元素，该线性表应该 C。A. 元素按值有序B. 采用顺序存储结构C. 元素按值有序，且采用顺序存储结构D. 元素按值有序，且采用链式存储结构28. 在分块检索中，对256 个元素的线性表分成 16块最好，每块的最佳长度是 16；若每块的长度为8，其平均检索长度为 21
20、。29. 假定有 K 个关键字互为同义词，若用线性探测法把这K 个关键字存入散列表中，至少要进 行 D A. K-1 次次探测。B. K 次C. K+1 次D. K(K+1)/2 次30. 在 n 个记录的有序顺序表中进行折半查找，最大的比较次数是log 2 n1 。31. Hash 技术广泛应用于查找过程，选择 Hash 函数的标准是和。处理冲突的技术有优有劣，其共同标准是。32. 在下述排序算法中，所需辅助存储空间最多的是 B，所需辅助存储空间最小的是 C，平均速度最快的是 A。A.快速排序B. 归并排序C. 堆排序33. 在文件局部有序或文件长度较小的情况下，最佳内部排序的方法是 A。A
21、. 直接插入排序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,6
22、5,50 B. 100,70,50,20,90,75,60,25,10,85,65,80 38. 若要尽可能快地完成对实数数组的排序，且要求排序是稳定的，则应选 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. 下面函数是将任意序列调整为最大堆的算法，请将空白部分
23、填上： 将任意序列调整为最大堆通过不断调用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 listchi
24、ld) break; else list (3) =listchild; (4) ; list (5) =rootkey; 参考答案：(1) listroot (2) child+; (3) child/2 (4) child *= 2; (5) child/2 41. 表是一种数据结构，链表是一种 (1)。队列和栈都是线性表，栈的操作特性是 (2)，队列的操作特性是 (3)。今有一空栈S，对下列待进栈的数据元素序列a,b,c,d,e,f 依次进栈、进栈、出栈、进栈、进栈、出栈的操作，则此操作完成后，栈S 的栈顶元素为 (4)，栈底元素为 (5)。供选答案：(1) :A. 非顺序存储线性表B.
25、 非顺序存储非线性表C. 顺序存储线性表D. 顺序存储非线性表(2) :A. 随机进出B. 先进后出C. 先进先出D. 出优于进(3) :A. 随机进出B. 先进后出C. 后进后出D. 进优于出(4):A. fB. c C. aD. b (5):A. bB. c C. aD. d 答案：ABCBC 42. 操作系统主要是对计算机系统全部 (1) 进行管理，以方便用户、提高计算机使用效率的一种系统软件。它的主要功能有：处理机管理、存储管理、文件管理、 (2) 管理和设备管理等。Windows 和 Unix 是最常用的两类操作系统。前者是一个具有图形界面的窗口式的 (3) 系统软件，后者是一个基本
26、上采用 (4) 语言编制而成的的系统软件。在 (5) 操作系统控制下，计算机能及时处理由过程控制反馈的信息并作出响应。供选答案：(1):A. 应用软件B. 系统软硬件C. 资源 D. 设备(2): A. 数据 C. 中断 B. 作业D. I/O (3): (4): A. 分 时 C. 多用户A. PASCAL B. 多任务D. 实时B. 宏(5): C. 汇编 A. 网络 D. C B. 分时C. 批处理D. 实时答案：CBBDD 43. 本程序从键盘读入整数，并按从大到小的顺序输出输入整数中互不相等的那些整数。 程序一边读入整数，一边构造一个从大到小顺序链接的链表，直至不能从键盘读入整数，然
27、后顺序输出链表上各表元的整数值。主函数每读入一个整数，就调用函数insert()，函数 insert()将还未出现在链表上的整数按从大到小的顺序插入到链表中。为了插入方便，链表在表首有一个辅助表元。阅读下列C 代码，在 (n)处填入相应的字句以完成上述功能。#include #include #define NULL 0 typedef struct node int 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
