2018年西北大学专业学位中心852数据结构[专业硕士]之数据结构考研基础五套测试题
● 摘要
一、单项选择题
1． 若某通信链路的数据传输速率为2400bps , 采用4相位调制, 则该链路的波特率是（ ）。
A.600波特
B.1200波特
C.4800波特
D.9600波特
【答案】B
【解析】注意无噪声下的码元速率极限值B 与信道带宽H 的关系:
特公式一无噪信道传输能力公式是
以得到波特率与数据传输速率的关系, 即, 而奈奎斯, N 为—个码元所取的离散值个数。从而可, 在本题中数据传输速率C=2400, N=4, 因此波特率是1200, 答案是B 。
2． 某计算机存储器按字节编址, 采用小端方式存放数据。假定编译器规定int 和short 型长度分别为32位和16位, 并且数据按边界对齐存储。某C 语言程序段如下:
若record 变量的首地址为0xC008, 则地址中内容及的地址分别为（ ）。 A. B. C. D.
【答案】D 。
32位整数a 需要占4个字节, 16位整数c 需要占2个字节, 而字符数据b 占一个字节。【解析】
a=273, 转换成十六进制是111H , 采用小端方式存放数据, 地址
边界对齐存储,
地址
中存放c 。
3． 若X 是后序线索二叉树中的叶结点, 且X 存在左兄弟结点Y , 则X 的右线索指向的是 （ ）
A.X 的父结点
中的内容为11H 。由于数据按中存放b ,
地址中空闲,
地址中存放a ,
地址
B. 以Y 为根的子树的最左下结点
C.X 的左兄弟结点Y
D. 以Y 为根的子树的最右下结点
【答案】A
【解析】根据后续线索二叉树的定义, X 结点为叶子结点且有左兄弟, 那么这个结点为右孩子结点, 利用后续遍历的方式可知X 结点的后继是其父结点, 即其右线索指向的是父结点。
4．
将一个的三对角矩阵，
按行优先存入一维数组中，A 中元素A 6665(即该元素下标i ＝66，j ＝65) ，在B 数组中的位置K 为（ ）。
A.198
B.195
C.197
【答案】B
【解析】将对角矩阵a[i][j]存入b[k]，三对角矩阵压缩地址计算公式如下:k ＝2i ＋j ﹣2。
5． 设图的邻接矩阵A 如下所示, 各顶点的度依次是（ ）
A.1, 2, 1, 2
B.2, 2, 1, 1
C.3, 4, 2, 3
D.4, 4, 2, 2
【答案】C
【解析】当图用邻接矩阵存储时, 各顶点的度是矩阵中此结点对应的横行和纵列非零元素之和。
6． 下列选项中，降低进程优先级的合理时机是（ ）.
A. 进程的时间片用完
B. 进程刚完成I/O，进入就绪队列
C. 进程长期处于就绪队列
D. 进程从就绪状态转为运行态
【答案】A
【解析】进程时间片用完可以降低其优先级，完成I/O的进程应该提升其优先级，处于就绪队列等待调度的进程一般不会改变其优先级. 进行这样的操作主要是为了改善交互式系统的响应时间，并均衡各个作业的公平性. 采用时间片轮转技术主要为改善交互式用户的感受，使其觉得是独享计算机(时间片轮转可以有效地防止计算繁忙型的进程独占计算机) ，时间片用完后降低其优
先级是为了改善新进程的响应时间(新进程优先级较高，老进程降低优先级可以保证新进程具有优先权) ，对于刚进入就绪队列的新进程，往往在创建时已经根据其特点和要求确定好优先级，不会随意改变. 而对于从阻塞状态唤醒的进程，由于阻塞带来了较长时间的等待，一般会根据阻塞队列的不同适当地提高优先级，以改善用户响应时间.
7． 某网络拓扑如下图所示, 路由器R1
只有到达子网
（ ）。
的路由。为使R1可以将IP 分组正确地路由到图中所有子网, 则在R1中需要增加一条路由(目的网络, 子网掩码, 下一跳) 是
A.
B.
C.
D.
【答案】D
因此是 【解析】首先从题目给出的路由表项可以确定下一跳肯定是路由器R1直接相连的R2的地址, , 此时可以排除A 和B 两个选项了。进而分析路由器R2所连接的网络特点, 注意
和, 但答案选项中只有一条信息, 因此这里其连接了2
个网络分别是
用到了超网的概念, 超网是与子网类似的概念一IP 地址根据子网掩码被分为独立的网络地址和主机地址。但是, 与子网把大网络分成若干小网络相反, 它是把一些小网络组合成一个大网络一超网,
这里
和
, 那么子网掩码就是前24位是相同的,
因此所构成的超网就是即, 因此答案是D 。
8． 设桟S 和队列Q 的初始状态为空，元素el ，e2，e3，e4，e5和e6依次通过栈S ，一个元素出栈后即进队列Q ，若6个元素出队的序列是e2，e4，e3，e6，e5，el ，则栈S 的容量至少应该是（ ）。
A.6
B.4
C.3
D.2
【答案】C
9． 对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（ ）。
A.(2，5，12，16)26(60，32，72)
B.(5，16，2，12)28(60，32，72)
C.(2，16，12，5)28(60，32，72)