2016年武汉纺织大学数学与计算机学院数据结构复试笔试最后押题五套卷
● 摘要
一、选择题
1． 一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（ ）个不同的码字。
A.107 B.108 C.214 D.215 答:B
【解析】此题可转化为一棵哈夫曼树共有215个结点，共有多少叶子结点。又有以
2． 下列选项中，对正确接收到的数据帧进行确认的MAC 协议是（ ）。
A.CSMA B.CDMA C.CSMA/CD D.CSMA/CA 答:D
【解析】可采用排除法。CDMA 是码分多址复用，是物理层的内容；CSMA/CD即带冲突检测的载波监听多 路访问，接收方并不需要确认；CSMA/CD是CSMA 的加强版，故CSMA 也无确定；CSMA/CD是802.11中的 协议，其利用ACK 信号来避免冲突的发生，也就是说，只有当 客户端收到网络上返回的ACK 信号后才确认送 出的数据已经正确到达目的地址，因此答案是D 。
3． 设与某资源相关联的信号量初值为3, 当前为1，若M 表示该资源的可用个数，N 表示等待该资源的进程数，则M ，N 分别是（ ）。
A.0、1 B.1、0 C.1、2 D.2、0 答:B
【解析】信号量初值是3表示资源数有3个，当前为1表示已经用掉2个，剩余可用的资源数就只有1个了，由于资源有剩余，可见没有其他进程等待使用该资源，故进程数为0。
4． 主机甲与乙之间已建立一个TCP 连接，双方持续有数据传输，且无差错与丢失。若甲收到1个来自乙的TCP 段，该段的序号为1913、确认序号为2046、有效载荷为100字节，则甲立即发送给乙的TCP 段的序号和确认分别是（ ）
A.2046、 2012
所
也就是说若对其进行哈夫曼编码，共能得到108个码字。
B.2046、 2013 C.2047、 2012 D.2047、 2012 答:B
【解析】若甲收到1个来自乙的TCP 段，该段的序号seq=1913、确认序号ack=2046、有效载荷为100字节，则甲立即发送给乙的TCP 段的序号seql=ack=2046和确认序号ackl =seq+100=2013, 答案为B 。
5． 程序P 在机器M 上的执行时间是20秒，编译优化后，P 执行的指令数减少到原来的CPI 増加到原来的1.2倍，则P 在M 上的执行时间是（ ）
A.8.4 秒 B.11.7 秒 C.14 秒 D.16.8 秒 答:D
【解析】
6． 对给定的关键字序列110, 119, 007, 911，114，120, 122进行基数排序，则第2趟分配收集后得到的关键字序列是（ ）
A. B. C. D. 答:C
而
【解析】基数排序的第1趟排序是按照个位数字来排序的，第2趟排序是按然十位数字的大小进行排序的，故答案是C 选项。
7． 若一棵二叉树的前序遍历序列为a ，e ，b ，d ，c ，后序遍历序列为b , c, d, e, a, 则根结点的孩子结点（ ）。
A. 只有e B. 有 e 、b C. 有 e 、c D. 无法确定 答:A 。
b , d, c, 后序遍历序列为b ，c , d, 【解析】由题目可知，若一棵二叉树的前序遍历序列为a , e，e , a , 其中a 为这棵二叉树的根结点，接下来，在前序遍历的第二个结点为e , 而后序遍历的倒数第二个结点为e , 说 明a 的孩子结点只有e 。
8． 循环队列元素数是（ ）。
存放其元素值，用front 和rear 分别表示队头和队尾，则当前队列中的
答:A
【解析】对于循环队列，需要深刻理解队头在队尾进行进队操作。
和队尾
的概念，在队头进行出队操作，
如果为负则元
可能为正也可能为负，为正时元素个数=
素的个数=所以统一的公式就是
9． float 型数据通常用IEEE754单精度浮点数格式表示。若编译器将float 型变量x 分配在一个32位浮点寄存器FR1中，且x=-8.25, 则FR1的内容是（ ）。
A.C1040000H B.C2420000H C.C1840000H D.C1C20000H 答:A
【解析】首先将十进制数转换为二进制数-1000.01，接着把它写成规格化形式
（按
IEEE754标准），然后计算阶码的移码=偏置值+阶码真值=127+3 = 130, 最后短浮点数代码：数符位=1, 阶码= 10000010, 尾数00001000000000000000000, 写成十六进制为C1040000H 。选项D 是一 个很容易被误选的选项，其错误在于没有考虑IEEE754标准中隐含最高位1的情况，偏置值是128。
10．假设栈初始为空，将中缀表达式
当扫描到f 时，栈中的元素依次是（ ）
A.
B. C. D. 答:B
【解析】中缀表达式转后缀表达式遵循以下原则： （1）遇到操作数，直接输出； （2）栈为空时，遇到运算符，入栈； （3）遇到左括号，将其入栈；
（4）遇到右括号，执行出栈操作，并将出桟的元素输出，直到弹出栈的是左括号， 左括号不输出； （5）遇到其他运算符运算符入栈；
（6）最终将栈中的元素依次出栈，输出。 所以扫描到优先级比
入栈‘描到
由于
优先级比
低，所以将
弹出，
入栈；扫描到
，
高，入栈；扫描到
入栈; 扫描到
将栈中优先级更高的
弹出，入栈; 扫描到
时，弹出所有优先级大于或等于该运算符的栈顶元素，然后将该
转换为等价后缀表达式的过程中，
相关内容
相关标签