2017年辽宁石油化工大学计算机与通信工程学院951数据结构考研仿真模拟题
● 摘要
一、填空题
1． 起始地址为480，大小为8的块，其伙伴块的起始地址是_____；若块大小为32，则其伙伴块的起始地址为_____。
【答案】
【解析】起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下：
根据上述公式起始地址就为488。
2． 顺序存储结构是通过_____表示元素之间的关系的；链式存储结构是通过_____表示元素之间的关系的。
【答案】物理上相邻；指针
【解析】顺序存储结构是通过物理位置表示元素之间的关系的，链式存储结构通过指针表示元素之间的关系。
3． 从平均时间性能而言，_____排序最佳。
【答案】快速
【解析】快速算法的平均时间复杂度为nlogn 。
4． —个字符串中_____称为该串的子串。
【答案】任意个连续的字符组成的子序列
5． —棵有个结点的满二叉树有_____个度为1的结点、有_____个分支（非终端）结点和_____个叶子，该满二叉树的深度为_____。
【答案】
或
【解析】满二叉树没有度为1的结点，度为0的结点等于度为2的结点个数+1。
6． 实现字符串拷贝的函数strcpy 为：
【答案】
7． 执行顺序查找时，存储方式可以是_____，折半查找时，要求线性表_____，分块查找时要求线性表_____，而哈希表的查找，要求线性表的存储方式是_____。
【答案】顺序存储或链式存储；顺序存储且有序；块内顺序存储，块间有序；散列存储
8． 若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的_____和记录的_____，
【答案】比较；移动
9． 对于双向链表，在两个结点之间插入一个新结点需修改的指针共_____个，单链表为_____个。
【答案】4; 2
10．串是一种特殊的线性表，其特殊性表现在_____; 串的两种最基本的存储方式是_____、_____; 两个串相等的充分必要条件是_____。
【答案】其数据元素都是字符；顺序存储；链式存储；串的长度相等且两串中对应位置的字符也相等
二、算法设计题
11．假定用两个一维数组L 【N 】和R 【N 】作为有N 个结点1，2, ... ，N 的二叉树的存储结构L[i]和R[i] 分別指示结点i 的左儿子和右儿子L[i]=0 （R[i]=0）表示i 的左（右）儿子为空。试写一个算法，由L 和R 建立一个维数组T[n]，使T[i]存放结点i 的父亲：然后再写一个判别结点u 是否为结点V 的后代的算法。
【答案】算法如下：
int Generation （int U, V , N , L[], R[], T[]}
//L[ ]和R[ ]是含N 个元素且指示二叉树结点i 左儿子和右儿子的一维数组 //本算法据此建立结点i 的双亲数组T , 并判断结点U 是否是结点V 的后代 {for（i=l; i<=N; i++） T[i]=0; //T数组初始化
for （i=l; i<=N; i++） if （L[i]!=0） T[L[i]]=i; //若结点i 的左子女是L , 则结点的双亲是结点i for （i=l; i<=N; i++） if （R[i]!=0> T[R[i]]=i; //若结点i 的右子女是R , 则R 的双亲是i int parent=U; //判断U 是否是V 的后代 while （
parent!=V
parent!=0） parent=T[parent];
if （parent==V）{printf（“结点U 是结点V 的后代”）; return （l ）:} else{printf（“结点U 不是结点V 的后代”）; return （0）; } }结束 Generation
12．有二叉排序树采用二叉链表方式存放，树中结点值各不相同，欲得到一个由大到小的结点值递减序列，简述处理方法思路，用非递归形式写出算法。
【答案】算法如下：
13．假设串的存储结构如下所示，编写算法实现串的置换操作。
【答案】算法如下：
和t 是用一维数组存储的串，本算法将s 串第i 个字符开始连续j 个字符用t 串置换，操作
成功返回1, 否则返回0表示失败
14．假设以I 和O 分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I 和O 组成的序列，称可以操作的序列为合法序列，否则称为非法序列。
（1）下面所示的序列中哪些是合法的？
（2）通过对（1）的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true ,