《2017年南昌大学信息工程学院829数据结构考研题库.doc》由会员分享，可在线阅读，更多相关《2017年南昌大学信息工程学院829数据结构考研题库.doc（5页珍藏版）》请在金锄头文库上搜索。
1、2017年南昌大学信息工程学院829数据结构考研题库一、选择题1 若X 是二叉中序线索树中一个有左孩子的结点，且X 不为根，则X 的前驱为（ ）。A.X 的双亲B.X 的右子树中最左的结点C.X 的左子树中最右的结点D.X 的左子树中最右的叶结点【答案】C【解析】中序线索，只有把其左子树最右结点遍历完后，才会遍历自己，所以X 的前驱为X 的左子树中最右的结点。 2 在无噪声情况下，若某通信链路的带宽为3kHz ，采用4个相位，每个相位具有4种振幅的QAM 调制技术，则该通信链路的最大数据传输速率是（ ）。A.12kbpsB.24kbpsC.48kbpsD.96kbps【答案】B【解析】首先要根
2、据信道有无噪声来确定是否采用奈奎斯特定理。解题难点在于离散数值的确定，先确定调制技术的码元数，此处为4个相位乘以4种振幅，共16种，即该通信链路的最大数据传输速率=23（44）=64=24kbps。 3某系统正在执行三个进程和各进程的计算（CPUCPUCPU ）时间和例如下表所示。时间比 为提高系统资源利用率，合理的进程优先级设置应（ ） A. B. C. D.【答案】B【解析】为了合理地设置进程优先级，应该将进程的CPU 利用时间和故答案选B 。 第 2 页，共 40 页 时间做综合考虑，4 假定用若干个2Kx4位的芯片组成一个8Kx8位的存储器，则地址0B1FH 所在芯片的最小地址是（ ）
3、。A.0000HB.0600HC.0700HD.0800H【答案】D【解析】由若干芯片构成存储器，采用字和位同时扩展方法。8片2Kx4位的芯片分成4组，每组2个芯片，各组芯片的地址分配分别为：第1组，0000H ?07FFH ; 第2组，0800H ?0FFFH ; 第3组，1000H ?17FFH ; 第4组，1800H ?1FFFH 。地址0BIFH 处于第2组内，其芯片的最小地址为0800H 。 5 某计算机的Cache 共有16块，采用2路组相联映射方式（即每组2块）。每个主存块大小为32字节，按字节编址。主存129号单元所在主存块应装入到的Cache 组号是（ ）。A.0B.2C.4
4、D.6【答案】C【解析】首先根据主存地址计算所在的主存块号，然后根据组相联映射的映射关系K=ImodQ（K 代表Cache 的组号，I 代表主存的块号，Q 代表Cache 的组数）来计算Cache 的组号。由于每个主存块大小为32字节，按字节编址，那么主存129号单元所在的主存块号是4, Cache 共有16，故Cache 有8组，按照上面的公式可以计算得到块，采用2路组相联映射方式（即每组2块）Cache 的组号=4mod8=4。 6 若串其子串的数目是（ ）。A.8B.37C.36D.9【答案】B【解析】子串的定义是：串中任意个连续的字符组成的子序列，并规定空串是任意串的子串，任意串是其自
5、身的子串。若字符串长度为长为为：故选B 。 7 排序算法的稳定性是指（ ）。A. 经过排序之后，能使值相同的数据保持原顺序中的相对位置不变B. 经过排序之后，能使值相同的数据保持原顺序中的绝对位置不变C. 算法的排序性能与被排序元素的数量关系不大第 3 页，共 40 页 长为n 的子串有1个，长为的子串有2个，的子串有3个，长为1的子串有n 个。由于空串是任何串的子串，所以本题的答案D. 算法的排序性能与被排序元素的数量关系密切【答案】A【解析】假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，且在之前，而在排序后的序列中，仍在之前
6、，则称这种排序算法是稳定的；否则称为不稳定的。 8 若某通信链路的数据传输速率为采用4相位调制，则该链路的波特率是（ ）。A.600波特B.1200波特C.4800波特D.9600波特【答案】B【解析】注意无噪声下的码元速率极限值B 与信道带宽H 的关系：B = 2xH （Baud ）, 而奈奎斯特公式一无噪信道传输能力公式是而可以得到波特率与数据传输速率的关系，即N 为一个码元所取的离散值个数。从在本题中数据传输速率C = 2400, N=4，因此波特率是1200, 答案是B 。 9 对同一待排序列分别进行折半插入排序和直接插入排序， 两者之间可能的不同之处是（ ）。A. 排序的总趟数B.
7、元素的移动次数C. 使用辅助空间的数量D. 元素之间的比较次数【答案】D 。【解析】折半插入排序所需附加存储空间和直接插入排序相同，从时间上比较，折半插入排序仅减少了关键字间的比较次数，而记录的移动次数不变。折半插入排序的时间复杂度仍为所以两者之间的不同只可能是元素之间的比较次数。 10已知三叉树T 中6个叶结点的权分别是2，3, 4, 5，6，7, T的带权（外部）路径长度最小是（ ）A.27B.46C.54D.56【答案】B【解析】利用三叉树的6个叶子结点的权构建最小带权生成树，最小的带权路径长度为 11要连通具有n 个顶点的有向图，至少需要（ ）条边。A.n-1第 4 页，共 40 页一、选择题考研试题
