2018年南昌航空大学软件学院817数据结构考研核心题库

专注考研专业课13年，提供海量考研优质文档！

第 1 页，共 62 页

目录

2018年南昌航空大学软件学院817数据结构考研核心题库（一） (2)

2018年南昌航空大学软件学院817数据结构考研核心题库（二） (15)

2018年南昌航空大学软件学院817数据结构考研核心题库（三） (27)

2018年南昌航空大学软件学院817数据结构考研核心题库（四） (41)

2018年南昌航空大学软件学院817数据结构考研核心题库（五） (51)

专注考研专业课13年，提供海量考研优质文档！

第 2 页，共 62 页 2018年南昌航空大学软件学院817数据结构考研核心题库（一）

说明：本套核心题库按照考试大纲、历年真题、指定参考书等结合考试侧重点和难度，精心整理编写。核心题库更突出针对性和实战性，考研冲刺必备资料。

——————————————————————————————————————————

一、填空题

1． 在单链表L 中，指针P 所指结点有后继结点的条件是_____

【答案】P ﹣＞next!＝NULL

【解析】指针所指节点的指针域所指向的元素非空，说明该指针所指节点有后继结点。

2． 设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长(也称增

量序列)依次是4， 2， 1则排序需_____趟，写出第一趟结束后，数组中数据的排列次序_____。

【答案】3; (10，7，-9，0，47，23，1，8，98，36)

3． 对单链表中元素按插入方法排序的C 语言描述算法如下，其中L 为链表头结点指针。请填充算法中标出的空白处，完成其功能。

:_____:

{_____)

(_____、

:_____；_____；p ＝u ；

【答案】(1)L ﹣＞next ＝NULL //置空链表，然后将原链表结点逐个插入到有序表中

(2)p!＝NULL //当链表尚未到尾，p 为工作指针

(3)q!＝NULL //查P 结点在链表中的插入位置，这时q 是工作指针

(4)p ﹣＞next ＝r ﹣＞next //将P 结点链入链表中

(5)r ﹣＞next ＝p //r 是q 的前驱，u 是下个待插入结点的指针

4． 已知；；ASSIGN(S ，U)；ASSIGN(V ，SUBSTR(S ，INDEX(S ，t)，LEN(t)＋1))

:

，求REPLACE(S ，V ，m)＝_____。 【答案】

专注考研专业课13年，提供海量考研优质文档！

第 3 页，共 62 页 5．

＝_____

【答案】5

6． 完善算法:求KMP 算法.next 数组。

k :＝_____；next[1]:＝0；

k :＝_____；

END ；

【答案】0；next[k]

7． 试利用下列栈和串的基本操作完成下述填空题。

initstack(S)置S 为空栈；

push(S ，X)元素X 入栈；

pop(S)出栈操作；

gettop(S)返回栈顶元素；

sempty(S)判栈空函数；

setnull(St)置串St 为空串；

length(st)返回串st 的长度；

equal(S 1，S 2)判串S 1并S 2是否相等的函数；

concat(S 1，S 2)返回联接S 1和S 2之后的串；

sub(S ，i ，1)返回S 中第i 个字符；

empty(st)判串空函数

FUNCinvert(pre :string ；V ARexp :string):boolean ；

{若给定的表达式的前缀式pre 正确，本过程求得和它相应的表达式exp 并返回true ，否则exp 为空串，并返回false 。已知原表达式中不包含括弧，opset 为运算符的集合。

)

_____；_____；

_____THEN_____

IF_____THEN_____

(_____，_____)；

(_____，_____)；

专注考研专业课13年，提供海量考研优质文档！

第 4 页，共 62 页

_____

_____THEN

注意:每个空格只填一个语句。

【答案】(1)initstack(S)//栈s 初始化为空栈

(2)setnull(exp)//串exp 初始化为空串

(3)chinopset//判取出字符是否是操作符

(4)push(s ，ch)//如ch 是运算符，则入操作符栈s

(5)sempty(s)//判栈s 是否为空

(6)succ :＝false//若读出ch 是操作数且栈为空，则按出错处理

(7)exp

(8)ch//若ch 是操作数且栈非空，则形成部分中缀表达式

(9)exp

(10)gettop(s)//取栈顶操作符

(11)pop(s)//操作符取出后，出栈

(12)sempty(s)//将pre 的最后一个字符(操作数)加入到中缀式exp 的最后

8． G 是一个非连通无向图，共有28条边，则该图至少有_____个顶点。

【答案】9

【解析】求该非连通无向图的最少顶点数，则该图为一个孤立的顶点和一个完全连通图。

9． 如某二叉树有20个叶结点，有30个结点仅有一个孩子，则该二叉树的总结点数为_____。

【答案】69

【解析】二叉树叶结点数为20,则度为2的结点数为19,所以总的结点数为20+19+30=69。

10．—个有2001个结点的完全二叉树的高度是_____。

【答案】11

【解析】完全二叉树的高度

二、单项选择题

11．在无噪声情况下，若某通信链路的带宽为3kHz ，采用4个相位，每个相位具有4种振幅的QAM 调制技术，则该通信链路的最大数据传输速率是（ ）.

A.12kbps

B.24kbps

本文来源：https://www.bwwdw.com/article/j7bq.html