2018年福建师范大学软件学院842软件工程专业基础综合之数据结构考研核心题库
● 摘要
目录
2018年福建师范大学软件学院842软件工程专业基础综合之数据结构考研核心题库（一） ... 2 2018年福建师范大学软件学院842软件工程专业基础综合之数据结构考研核心题库（二） . 13 2018年福建师范大学软件学院842软件工程专业基础综合之数据结构考研核心题库（三） . 25 2018年福建师范大学软件学院842软件工程专业基础综合之数据结构考研核心题库（四） . 37 2018年福建师范大学软件学院842软件工程专业基础综合之数据结构考研核心题库（五） . 49
第 1 页，共 58 页
一、填空题
1． 以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。
h 为附加头结点指针
(_____)
_____；
【答案】(1)p!＝NULL //链表未到尾就一直进行 (2)q //将当前结点作为头结点后的第一元素结点插入
2． 顺序存储结构是通过_____表示元素之间的关系的；链式存储结构是通过_____表示元素之间的关系的。
【答案】物理上相邻；指针
【解析】顺序存储结构是通过物理位置表示元素之间的关系的，链式存储结构通过指针表示元素之间的关系。
3． 在双向循环链表中，向P 所指的结点之后插入指针f 所指的结点，其操作是_____、_____、_____、_____。
【答案】f ﹣＞next ＝p ﹣＞next ；f ﹣＞prior ＝p ；p ﹣＞next ﹣＞prior ＝f ；p ﹣＞next ＝f ；
4． 属于不稳定排序的有_____。
【答案】希尔排序、简单选择排序、快速排序、堆排序等
5． 空格串是指_____，其长度等于_____。
【答案】由空格字符(ASCII值32) 所组成的字符串；空格个数
6． 对于一个具有n 个结点的单链表，在已知的结点半p 后插入一个新结点的时间. 复杂度为_____，在给定值为x 的结点后插入一个新结点的时间复杂度为_____。
【答案】O(1)；O(n)
【解析】第一种情况只需直接修改指针的指向。第二种情况必须从头结点遍历找到x 的结点。
第 2 页，共 58 页
7． 下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括n 个顶点
用相邻矩阵A 表示，边的权全是正数。请在下列划线处填上正确叙述。
(1)若
是边，则
的值等于_____，若
不是边，则A(i, j) 的值是一个比任何
置
边的权_____，矩阵的对角线元素全为0。
(2)构造最小生成树过程中，若顶点已包括进生成树，就把相邻矩阵的对角线元素成_____，若
【答案】(1)
已包括进生成树，就把矩阵元素
置成_____。
(3)算法结束时，相邻矩阵中_____的元素指出最小生成树的_____。
边上的权值；都大的数；(2)1; 负值；(3)为负；边
8． 设有一个空枝，栈顶指针为1000H(十六进制) ，现有输入序列为1，2，3，4，5，经过PUSH ，PUSH ，POP ，PUSH ，POP ，PUSH ，PUSH 之后，输出序列是_____，而栈顶指针值是_____。设栈为顺序找，每个元素占4个字节。
【答案】23；100CH
9． 在图G 的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的_____; 对于有向图来说等于该顶点的_____。
【答案】度；出度
10．在哈希函数
中，p 值最好取_____。
【答案】小于等于表长的最大素数或不包含小于20的质因子的合数
【解析】在使用除留余数法时，对除数P 的选择很重要。若P 选的不好，容易产生同义词。一般情况下，可以选P 为质数或不包含小于20的质因素的合数。
11．用循环链表表示的队列长度为n ，若只设头指针，则出队和入队的时间复杂度分别是_____和_____；若只设尾指针，则出队和入队的时间复杂度分别是_____和_____。
【答案】O(1)；O(n)；O(1)；O(1)
【解析】队列的出队操作即删除队头的元素，队列的入队操作即在队尾添加元素，循环链表只设头指针，出队时，只要把头结点的下一个结点删除就好了，入队时，要把新的结点插入队尾，必须把队列遍历，找到队尾指针，才能插入。循环队列只设尾指针，出队时只要把为指针的下一个结点或者下下个结点删除即可，入队时，只要在尾指针的后面插入新的结点，并更新尾结点即可。
12．
给定一组数据WPL 的值为_____。
【答案】5；96
【解析】每次找两个最小的权值构建哈夫曼树:
第 3 页，共 58 页
以它构造一棵哈夫曼树，则树高为_____，带权路径长度
二、单项选择题
13．某系统正在执行三个进程P1、P2和P3, 各进程的计算(CPUCPUCPU)时间和如下表所示。
时间比例
为提高系统资源利用率, 合理的进程优先级设置应（ ） A. B. C. D. 【答案】B
【解析】为了合理地设置进程优先级, 应该将进程的CPU 利用时间和
时间做综合考虑, 故
答案选B 。
14．浮点数加、减运算一般包括对阶、尾数运算、规格化、舍入和判溢出等步骤. 设浮点数的阶码
7
和尾数均采用补码表示，且位数分别为5位和7位(均含2位符号位). 若有两个数X ＝2×29/32，Y 5
＝2×5/8，则用浮点加法计算X ＋Y 的最终结果是（ ）.
A.001111100010 B.001110100010 C.010000010001 D. 发生溢出
【答案】D
【解析】浮点数加、减运算一般包括对阶、尾数运算、规格化、舍入和判溢出等步骤，难点在对阶、规格化、判溢出这三步.X 和Y 的阶码不同，所以应该先对阶，对阶原则为：小阶向大阶看齐. 因此将Y 对阶后得到：Y ＝2×5/32，然后将尾数相加，得到尾数之和为：34/32.因为这是两
7
个同号数相加，尾数大于1，则需要右规，阶码加1. 由于阶码的位数为5位，且含两位符号位，即阶码的表示范围在之间. 而阶码本身等于7，再加1就等于8. 因此，最终结果发生溢出.
15．若用户1与用户2之间发送和接收电子邮件的过程如题40图所示, 则图中①、②、③阶段分别使用的应用层协议可以是（ ）。
第 4 页，共 58 页