2018年武汉科技大学信息科学与工程学院856数据结构(C语言版)考研核心题库
● 摘要
目录
2018年武汉科技大学信息科学与工程学院856数据结构（C 语言版）考研核心题库（一） . ... 2
2018年武汉科技大学信息科学与工程学院856数据结构（C 语言版）考研核心题库（二） . . 13
2018年武汉科技大学信息科学与工程学院856数据结构（C 语言版）考研核心题库（三） . . 23
2018年武汉科技大学信息科学与工程学院856数据结构（C 语言版）考研核心题库（四） . . 33
2018年武汉科技大学信息科学与工程学院856数据结构（C 语言版）考研核心题库（五） . . 44
一、单项选择题
1． 在无噪声情况下，若某通信链路的带宽为3kHz ，采用4个相位，每个相位具有4种振幅的QAM 调制技术，则该通信链路的最大数据传输速率是（ ）.
A.12kbps
B.24kbps
C.48kbps
D.96kbps
【答案】B
【解析】首先要根据信道有无噪声来确定是否采用奈奎斯特定理. 解题难点在于离散数值的确定，先确定调制技术的码元数，此处为4个相位乘以4种振幅，共16种，即该通信链路的最大数据传输速率＝2×3×log2(4×4) ＝6×4＝24kbps.
2． 已知待排序的n 个元素可分为n/k个组，每个组包含k 个元素，且任一组内的各元素均分别大干前一组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为（ ）。 A.
B.
C.
D.
【答案】B
【解析】因组与组之间己有序，故将n/k个组分别排序即可，基于比较的排序方法每组的时
，全部时间下界为间下界为
0 。
3． 内部异常(内中断) 可分为故障(fault)、陷阱(trap)和终止(abort)三类。下列有关内部异常的叙述中, 错误的（ ）。
A. 内部异常的产生与当前执行指令相关
B. 内部异常的检测由CPU 内部逻辑实现
C. 内部异常的响应发生在指令执行过程中
D. 内部异常处理后返回到发生异常的指令继续执行
【答案】D
【解析】内中断分为:
①由软中断指令启动的中断; ②在一定条件下由CPU 自身启动的中断。
D 项错误, 如突然掉电引发的内中断经处理后不会继续执行。
4． 在任意一棵非空二叉排序树T1中, 删除某结点v 之后形成二叉排序树T2, 再将v 插入T2形成二叉排序树T3。下列关于T1与T3的叙述中, 正确的是（ ）
Ⅰ. 若v 是T1的叶结点, 则T1与T3不同
Ⅱ. 若v 是T1的叶结点, 则T1与T3相同
Ⅲ. 若v 不是T1的叶结点, 则T1与T3不同
Ⅳ. 若v 不是T1的叶结点, 则T1与T3相同
A. 仅Ⅰ、Ⅲ
B. 仅Ⅰ、Ⅳ
c. 仅Ⅱ、Ⅲ
d. 仅Ⅱ、Ⅳ
【答案】C
【解析】在一棵二叉排序树中删除一个结点后再将此结点插入到二叉排序树中, 如果删除的结点是叶子结点那么在插入结点后, 后来的二叉排序树与删除结点之前相同。如果删除的结点不是叶子结点, 那么再插入这个结点后, 后来的二叉树可能发生变化, 不完全相同。
5． 连续存储设计时，存储单元的地址（ ）。
A. 一定连续
B. 一定不连续
C. 不一定连续
D. 部分连续，部分不连续
【答案】A
【解析】连续存储是指数据的物理存储相连，即存储单元的地址是连续的。
6． 偏移寻址通过将某个寄存器内容与一个形式地址相加而生成有效地址。下列寻址方式中, 不属于偏移寻址方式的是（ ）。
A. 间接寻址
B. 基址寻址
C. 相对寻址
D. 变址寻址
【答案】A
【解析】在四种不同的寻址方式中, 间接寻址按指令的形式地址从主存中取出操作数的有效地址, 然后再按此有效地址从主存中读出操作数。其余三种寻址方式可以统称为偏移寻址。
7． 已知字符串S 为“abaabaabacacaabaabcc ”, 模式串t 为“abaabc ”, 采用KMP 算法进行匹配, 第一次出现“失配”(
A.i=l, j=0 ) 时, i=j=5, 则下次开始匹配时, i 和j 的值分别是（ ）。
B.i=5, j=0
C.i=5, j=2
D.i=6, j=2
【答案】C
【解析】模式匹配(KMP)算法对普通的暴力匹配的改进在于:每当匹配过程中匹配失败时, 主串(本题为S) 的指针(i)不需要回溯, 而是利用已经得到的“部分匹配”的结果将模式串(t)向右“滑动”尽可能远的一段距离后, 继续进行比较。模式串“滑动”的距离是由模式串(t)本身决定的, 即t
的子串
中前缀串和后缀串相等的最长长度。本题中第一次失配i=5, 字串为“abaab”, 其相等且最长的前后缀为“ab”, 一次下一个j=2。
8． 求整数阶乘的算法如下, 其时间复杂度是（ ）。
A.
B.0(n) C. 2D.O(n)
【答案】B 。
【解析】设fact(n)的运行时间函数是T(n)。
该函数中语句①的运行时间是0(1), 语句②的运行时间是
算的时间。
因此, 当
则,
时
, ; 。
即fact(n)的时间复杂度为O(n)。 当11>1时, , 其中O(1)为乘法运
相关内容
相关标签