计算机软件基础模拟试题
一、选择题
1、在一个长度为a的顺序表的表尾插入一个新元素的渐进时间复杂度为（）
A、O（n）
B、O（1）
C、O（n2）
D、O（log2n）
2、设单链表中结点的结构为（data,，link）。
已知指针q所指结点是指针p所指结事业的直接前驱，若在*q和*p之间插入点*s，则应该执行下列哪个操作？（）
A、s->link=p->link; p->link=s
B、q->link=s; s->link=p
C、p->link=s->link; s->link=p
D、p->link=s; s->link=q
3、若让元素1，2，3依次进栈，则出栈次序不可能出现（）种情况。
A、3，2，1
B、2，1，3
C、3，1，2
D、1，3，2
4、一个递归的定义可以用递归过程求解，也可以用非递归过程求解，但单从运行时间来看，通常递归过程比非递归过程（）
A、较快
B、较慢
C、相同
5、树中所有结点的度等于所有结点数加（）
A、0
B、1
C、-1
D、2
6、在文件系统中采用多级目录的优点之一是（）
A、可以处理多任务
B、可以提高内存使用率
C、可以允许不同的用户对不同文化起相同的名字
D、可以提高访问文件的速度
7、对长度为a的有序单链表，若搜索每个元素的概率相等，则顺序搜索到表中任一元素的平均搜索长度为（）
A、n/2
B、(n+1)/2
C、(n-1)/2
D、n/4
8、在无向图中定义顶点Vi与Vj之间路径为从Vi到达Vj的一个（）
A、顶点序列
B、边序列
C、权值总和
D、边的条数
9、所谓“裸机”是指（）
A、单片机
B、单扳机
C、不装备任何软件的计算机
D、只装多操作系统的计算机
10、一个算法应该具有“确定性”等5个特征，下面另外4个特征的描述中错误的是（）
A、有零个或多个输入
B、有零个或多个输出
C、有穷性
D、可行性
二、填空题
11、进程的基本状态是__________、_________和________。
12、产生死锁的四个必要条件是________、_________、_________、________。
13、链表适用于_________查找。
14、队列的插入操作在队尾进行，删除操作在__________进行。
15、在一棵树中___________结点没有前驱结点。
三、判断题
16、二维数组可以被视为数组元素为一维数组的一维数组。
（）
17、链接存储表示的存储空间一般在程序的进行过程中动态分配和释放，通常存储中还有空闲存储空间，就不会产生存储溢出的问题。
（）
18、在用单链表示的链式队伍中，队头在链表的链尾位置。
（）
19、凡是递归定义的数据结构都可以用递归算法来实现它的操作。
（）
20、进程存在有封锁状态—运行态的直接转换。
（）
21、文件系统中采用多级目录的优点之一是可以提高内存使用率。
（）
22、进行折半查找的表必须是顺序存储的有序数。
（）
23、虚存的容量可以大雨主存与外存容量之和。
（）
24、采用顺序存储的线性表，必须占用一片连续的存储单元。
（）
25、进程是程序的执行过程，进程与程序是一一对应关系。
（）
四、运算题
26、什么叫算法？如何衡量一个算法的好坏？算法与程序有和不同？
27、已知一棵二叉树的中序列和前序序列如下，求该二叉树的后序序列。
中序序列：c，b，d，e，a，g，i，h，j，f，
前序序列：a，b，c，d，e，f，g，h，i，j，
后序序列：
28、什么是死锁？发生死锁时有哪些解决方法？
29、操作系统有哪几种基本类型？各有什么特点？
30、按增长率由小至大的顺序排列下列各函数：
2100，（3/2）n，lon2N，n n，n log2n，n!，n3/2，2n，n1/2
五、综合题
31、每行均要求加注该行的功能性注释
BITREE *creat ()
{ BIRTEE *tr; int x ;
Printf ( “\nInput the value of a tree node ; \n” ) ;
Scanf ( “%d ,&x );
If ( x= =0 ) tr=Null ; else
{ tr=(BITREE * )malloc (sizeof ( BITREE ) ) ;
tr->data=x ;
tr->lchild=creat () ;
tr->rchild=creat () ; }
return ( tr ) ; }
void InOrder ( BITREE * tr )
{ if (tr! = Null )
{ InOrder ( tr->Ichild ) ;
Printf ( “%4d” , tr->data ); InOrder( tr->rchild ); } }
32、对于给顶的一组关键字：
503，087，512，067，908，170，889，276，675，453
写出插入顺序、起泡顺序的各趟运行结果。
33、两个栈共享向量空间V[m]，它们的栈底分别设在向量的两端，每个元素占一个分量，试写出两个栈公用的栈操作算法：push ( i , x )，pop ( i )和top ( i )，其中i为0或1，用以指示栈号。
部分参考答案
一、
1、B
2、B
3、C
4、B
5、C
6、C
7、B
8、A
9、C 10、B
二
11、运行、就绪、封锁
13、折半
14、队头
15、根
三、16、× 17、× 18、√ 19、× 20、× 21、× 22、√ 23、×
24、√ 25、×。