if(L->elem[I]<>L->elem[j]){ (2) ; (3) ; } I++;
}
(4) ;
}
参考答案：
(1) i<=L->length (2) (3) j++; (4)
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和5 B. 2和4 C. 4和2 D. 5和1 17.设栈的输入序列为1,2，…,10，输出序列为a1,a2,…,a10，若a5=10，则a7为 C 。 A. 4 B. 8 C.不确定
18.设栈的输入序列是1,2,3,4，则 D 不可能是其出栈序列。 A． 1243 B. 2134 C. 1432 D. 4312 19.以下 D 是C语言中”abcd321ABCD”的子串。
A. abcd B. 321AB C. “abcABC” D. “21AB” 20.若串S=”software”，其子串的数目是 C 。
A. 8 B. 37 C. 36 D. 9
21.将一个A[1:100,1:100]的三对角矩阵，按行优先存入一维数组B[1:298]中，A中元素A66,65(即该元素的下标)在B数组中位置k为 B 。
A. 198 B. 195 C. 197 D. 196 22.设高为h的二叉树只有度为0和2的结点，则此类二叉树的结点数至少为 B ，至多为 F 。高为h的完全二叉树的结点数至少为 E ，至多为 F 。 A． 2h B. 2h-1 C. 2h+1 +1
h-1hh+1h
E. 2 F. 2-1 G. 2-1 H. 2+1 23.一棵有124个叶结点的完全二叉树，最多有 B 个结点。 A. 247 B. 248 C. 249 D. 251
24.若从二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序，则该二叉树是 C 。
A. 满二叉树 B. 哈夫曼树 C. 堆 D. 二叉查找树
25.前序遍历和中序遍历结果相同的二叉树为 F ；前序遍历和后序遍历结果相同的二叉树为 B 。
A. 一般二叉树 B. 只有根结点的二叉树 C. 根结点无左孩子的二叉树 D. 根结点无右孩子的二叉树 E. 所有结点只有左孩子的二叉树 F. 所有结点只有右孩子的二叉树
26.具有n个结点的完全二叉树，已经顺序存储在一维数组A[1..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=A[I];
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*I<=n
(3) createtree(p->lchild,A,2*I,n) (4) 2*I+1<=n
(5) p->rchild,A,2*I+1,n
27.若在线性表中采用折半查找法查找元素，该线性表应该 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个记录的有序顺序表中进行折半查找，最大的比较次数是?log2n??1。
技术广泛应用于查找过程，选择Hash函数的标准是 和 。处理冲突的技术有优有劣，其共同标准是 。
32.在下述排序算法中，所需辅助存储空间最多的是 B ，所需辅助存储空间最小的是 C ，平均速度最快的是 A 。
A.快速排序 B. 归并排序 C. 堆排序
33.在文件局部有序或文件长度较小的情况下，最佳内部排序的方法是 A 。 A. 直接插入排序 B. 冒泡排序 C. 简单选择排序
2
34.快速排序在最坏情况下时间复杂度是O(n)，比 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,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)
2
C. O(nlogn) D. O(n)
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为下标的对应元素作为待调整堆的根，待调整元素放在list数组中，最大元素下标为n*/
}
参考答案： (1) list[root] (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. 非顺序存储非线性表 C. 顺序存储线性表 D. 顺序存储非线性表 (2): A. 随机进出 B. 先进后出 C. 先进先出 D. 出优于进 (3): A. 随机进出 B. 先进后出 C. 后进后出 D. 进优于出 (4): A. f B. c C. a D. b (5): A. b B. c C. a D. d 答案：ABCBC
42.操作系统主要是对计算机系统全部 (1) 进行管理，以方便用户、提高计算机使用效率的一种系统软件。它的主要功能有：处理机管理、存储管理、文件管理、 (2) 管理和设备管理等。Windows和Unix是最常用的两类操作系统。前者是一个具有图形界面的窗口式的 (3) 系统软件，后者是一个基本上采用 (4) 语言编制而成的的系统软件。在 (5) 操作系统控制下，计算机能及时处理由过程控制反馈的信息并作出响应。 供选答案：
int child,rootkey;
rootkey = (1) ; child = 2*root; while(child < n){
if((child if(rootkey > list[child]) break; else{ list[ (3) ]=list[child]; (4) ; } } list[ (5) ]=rootkey; (1): A. 应用软件 B. 系统软硬件 C. 资源 D. 设备 (2): A. 数据 B. 作业 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()将还未出现在链表上的整数按从大到小的顺序插入到链表中。 为了插入方便，链表在表首有一个辅助表元。 阅读下列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 < v->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;
计算机软件技术基础试题答案
