一、单项选择题

下列每题给出的四个选项中，只有一个选项最符合试题要求。

1、若栈S1中保存整数，栈S2中保存运算符，函数F()依次执行下述各步操作：

(1)从S1中依次弹出两个操作数a和b;

(2)从S2中弹出一个运算符op;

(3)执行相应的运算b op a;

(4)将运算结果压入S1中。

假定S1中的操作数依次是5,8,3,2(2在栈顶)，S2中的运算符依次是*，-，+(+在栈顶)。调用3次F()后，S1栈顶保存的值是______。

A.-15B.15C.-20D.20

2、现有队列Q与栈S，初始时Q中的元素依次是1,2,3,4,5,6(1在队头)，S为空。若仅允许下列3种操作：①出队并输出出队元素;②出队并将出队元素入栈;③出栈并输出出栈元素，则不能得到的输出序列是______。

A.1,2,5,6,4,3B.2,3,4,5,6,1

C.3,4,5,6,1,2D.6,5,4,3,2,1

3、设有一个12×12的对称矩阵M，将其上三角部分的元素mi,j(1≤i≤j≤12)按行优先存入C语言的一维数组N中，元素m6,6在N中的下标是______。

A.50B.51C.55D.66

4、设一棵非空完全二叉树T的所有叶结点均位于同一层，且每个非叶结点都有2个子结点。若T有k个叶结点，则T的结点总数是______。

A.2k-1B.2kC.k2D.2k-1

5、己知字符集{a,b,c,d,e, ……此处隐藏15190个字…… 机?

61、假设主机192.168.1.1向主机192.168.1.208发送一个总长度为1500B的IP分组，IP分组的头部长度为20B，路由器在通过接口F1转发该IP分组时进行了分片。若分片时尽可能分为最大片，则一个最大IP分片封装数据的字节数是多少?至少需要分为几个分片?每个分片的片偏移量是多少?

答案:

一、单项选择题

1、B　 　2、C　 　3、A　 　4、A　 　5、A　 　6、C　 　7、D　 　8、B　 　9、C　 　10、D　 　11、A　 　12、D　 　13、C　 　14、A　 　15、A　 　16、B　 　17、C　 　18、B　 　19、A　 　20、D　 　21、B　 　22、C　 　23、C　 　24、D　 　25、B　 　26、A　 　27、C　 　28、D　 　29、D　 　30、A　 　31、D　 　32、C　 　33、B　 　34、C　 　35、D　 　36、D　 　37、D　 　38、C　 　39、B　 　40、D

二、综合应用题

41、题目要求算法时间上尽可能高效，因此采用空间换时间的办法。分配一个用于标记的数组B[n]，用来记录A中是否出现了1～n中的正整数，B[0]对应正整数1，B[n-1]对应正整数n，初始化B中全部为0。由于A中含有n个整数，因此可能返回的值是1～n+1，当A中n个数恰好为1～n时返回n+1。当数组A中出现了小于等于0或者大于n的值时，会导致1～n巾出现空余位置，返回结果必然在1～n中，因此对于A中出现了小于等于0或者大于n的值可以不采取任何操作。 　 　42、经过以上分析可以得出算法流程：从A[0]开始遍历A，若0