2017年大连大学国家863空间信息技术初试辅导(2016年)之数据结构考研强化模拟题
● 摘要
一、填空题
1． 设正文串长度为n ，模式串长度为m ，则串匹配的KMP 算法的时间复杂度为_____。
【答案】
表示，两栈顶指针为
则
2． 当两个栈共享一存储区时，栈利用一维数组当栈1空时
，
【答案】
为_____，栈2空时
，
为_____，栈满时为_____。
【解析】共享栈的栈底在共享存储区的两端，当栈满时栈顶相邻。
3． 表达式的后缀表达式是_____。
【答案】
4． 对于一个具有n 个结点的单链表，在已知的结点半p 后插入一个新结点的时间. 复杂度为_____，在给定值为x 的结点后插入一个新结点的时间复杂度为_____。
【答案】
【解析】第一种情况只需直接修改指针的指向。第二种情况必须从头结点遍历找到x 的结点。
5． 在单链表中设置头结点的作用是_____。
【答案】方便运算
6． 设有一个空找，栈顶指针为1000H （十六进制），现有输入序列为1，2，3, 4, 5，经过PUSH ，PUSH , POP , PUSH , POP ，PUSH ，PUSH 之后，输出序列是_____，而栈顶指针值是_____。设栈为顺序栈，每个元素占4个字节。
【答案】23; 100CH
7． 对于给定的元素，可以构造出的逻辑结构有_____，_____，_____，_____四种。
【答案】集合；线性结构；树形结构；图状结构（网状结构）
8． 数据结构中评价算法的两个重要指标是_____。
【答案】算法的时间复杂度和空间复杂度
9． 已知链队列的头尾指针分别是f 和r , 则将值x 入队的操作序列是_____。
【答案】
【解析】队列采用链式存储结构，先分配一个节点的内存，然后在队尾添加该节点。
10．在顺序存储的二叉树中，编号为i 和j 的两个结点处在同一层的条件是_____。
【答案】要加“虚结点”。
设编号为
和
的结点在顺序存储中的下标为
和
。
，
则结点
和
在同一层上的条件是
【解析】用顺序存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，
二、算法设计题
11．已知无向图采用邻接表存储方式，试写出删除边（i ，j ）的算法。
【答案】算法如下：
//在用邻接表方式存储的无向图g 中，刪除边（i , j ）
//删顶点i 的边结点（i , j ）pre 是前驱指针
释
放空间
//
//释
放空间
//沿链表继续査找
12．设整数序列
【答案】算法如下：
给出求解最大值的递归程序。
沿
链
表
继
续
查
找
//删顶点j 的边结点（j , i ）
13．设表达式以字符形式已存入数组E 中，
【答案】算法如下：
为表达式的结束符，试写出判断表达式中括号
是否配对的C 语言描述算法：EXYX （E ）（注：算法中可调用栈操作的基本算法）。
14．输入一个字符串，内有数字和非数字字符，如：作为一个整体，依次存放到一数组a 中，例如123放入多少个整数，并输出这些数。
【答案】算法如下：
456放入
将其中连续的数字编程统计其共有
15．设记录
的关键字为
树结点
的败者树，要求除
指向败者记录，
和
为全胜记以外，只用
录下标。写一算法产生对应上述
辅助空间。 【答案】算法如下：