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