2018年天津大学软件学院901数据结构与程序设计之数据结构考研仿真模拟五套题
● 摘要
目录
2018年天津大学软件学院901数据结构与程序设计之数据结构考研仿真模拟五套题（一） ... 2 2018年天津大学软件学院901数据结构与程序设计之数据结构考研仿真模拟五套题（二） . 16 2018年天津大学软件学院901数据结构与程序设计之数据结构考研仿真模拟五套题（三） . 29 2018年天津大学软件学院901数据结构与程序设计之数据结构考研仿真模拟五套题（四） . 40 2018年天津大学软件学院901数据结构与程序设计之数据结构考研仿真模拟五套题（五） . 54
第 1 页，共 64 页
一、填空题
1． 堆是一种有用的数据结构。堆排序是一种_____排序，堆实质上是一棵_____结点的层次序列。对含有N 个元素的序列进行排序时，堆排序的时间复杂度是_____，所需的附加存储结点是_____。关键码序列05, 23, 16, 68, 94, 72, 71, 73是否满足堆的险质_____ 。
【答案】选择；完全二叉树；
；O(1)；满足堆的性质
2． 一棵有11个结点的满二叉树有_____个度为1的结点、有_____个分支(非终端) 结点和_____个叶子，该满二叉树的深度为_____。
【答案】
或
【解析】满二叉树没有度为1的结点，度为0的结点等于度为2的结点个数+1。
3． 在有n 个顶点的有向图中，每个顶点的度最大可达_____。
【答案】2(n－1)
【解析】当有向图为完全连通图时每个顶点的度达到最大，出度入度均为n －1。
4． 一个字符串中_____称为该串的子串。
【答案】任意个连续的字符组成的子序列
5． 设广义表L ＝(（ ），（ ）) ，则head(L)是_____tail(L)是_____L的长度是_____；深度是_____。
【答案】（ ）；(（ ）) ；2；2
【解析】广义表的表头是表的第一个元素，表尾是除了第一个元素外其余的所有的元素构成的表；表的长度指表中元素的个数；表的深度指展开后括号的层数。
6． 二进制地址为011011110000, 大小为和块的伙伴地址分别为:_____
【答案】011011110100；011011100000
【解析】011011110000是块的起始地址，大小分别为算公式如下:
当大小为4时，起始地址为011011110000+0100。当大小为16时，起始地址
第 2 页，共 64 页
和其伙伴块的起始地址计
为:011011110000-010000。
7． 假定查找有序表 中每个元素的概率相等，则进行折半查找时的平均查找长度为_____。
【答案】
表
平均查找次数为。
8． 若用n 表示图中顶点数目，则有_____条边的无向图成为完全图。
【答案】
【解析】无向完全图中任意一个顶点都和其他n －1个顶点都有一条边，即为n(n－1) 。又因. 。 为每条边重复出现两次，所有无向完全图的边数为
9． 设数组数组中任一元素A[i，j]均占内存48个二进制位，从首地址2000开始连续存放在主内存里，主内存字长为16位，那么
(1)存放该数组至少需要的单元数是_____；
(2)存放数组的第8列的所有元素至少需要的单元数_____； (3)数组按列存储时，元素A[5，8]的起始地址是_____。 【答案】270；27；2204
【解析】数组的元素个数为9*10＝90，因为每个元素占内存48个二进制位，即6个字节。故总需要90*6＝540个字节，因为主内存字长为16位，即2个字节，所以至少需要540/2＝270个单元数。第8列有9个元素，共占9*6＝54个字节，因此至少需要54/2＝27个单元数。由题知，每个元素占3个单元。按列存储时，A[5，8]的起始地址为2000＋[(8﹣1)*9＋(5﹣0)]*3＝2204。
10．设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长(也称增 量序列) 依次是4， 2， 1则排序需_____趟，写出第一趟结束后，数组中数据的排列次序_____。
【答案】3; (10，7，-9，0，47，23，1，8，98，36)
11．表达式23＋((12*3﹣2)/4＋34，5/7) ＋108/9的后缀表达式是_____。
【答案】
(表达式中的点(.)是数分隔符，如
是三个数)
【解析】折半查找时每个的次数如表所示:
第 3 页，共 64 页
12．设T 是一棵结点值为整数的二叉排序树，A 是一个任意给定的整数。在下面的算法中，free_tree(T)在对二叉排序树丁进行后序遍历时释放二又排序树T 的所有结点
；
，首先在二叉排序树T 中查找值为A 的结点，根据查找情况分别进行如下
处理:(1)若找不到值为A 的结点，则返回根结点的地址(2)若找到值为A 的结点，则删除以此结点为根的子树，并释放此子树中的所有结点，若值为A 的结点是查找树的根结点，删除后变成空的二叉树，则返NULL ; 否则返回根结点的地址。
【答案】
13．下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。
a 中存放待排序的关键字
第 4 页，共 64 页
相关内容
相关标签