2017年上海市培养单位声学研究所东海研究站866计算机原理之数据结构考研题库
● 摘要
目录
2017年上海市培养单位声学研究所东海研究站866计算机原理之数据结构考研题库（一）.... 2 2017年上海市培养单位声学研究所东海研究站866计算机原理之数据结构考研题库（二）.. 14 2017年上海市培养单位声学研究所东海研究站866计算机原理之数据结构考研题库（三）.. 26 2017年上海市培养单位声学研究所东海研究站866计算机原理之数据结构考研题库（四）.. 37 2017年上海市培养单位声学研究所东海研究站866计算机原理之数据结构考研题库（五）.. 51
一、填空题
1． 线性表
【答案】（n －1）/2
【解析】删除第一个元素需要移动n －i 次，以此类推，删除最后一个元素需要移动0次。平 均次数为
2． 当广义表中的每个元素都是原子时，广义表便成了_____。
【答案】线性表
【解析】如果每个元素都是原子，则元素不可分。此时的元素是只有一对一的关系，所以广义表变成了线性表。
3． 无用单元是指_____，例_____
【答案】用户不再使用而系统没有回收的结构和变量；
4． 一个有2001个结点的完全二叉树的高度是_____。
【答案】11
【解析】完全二叉树的高度
5． 完善算法：求KMP 算法.next 数组。
用数组表示，假定删除表中任一元素的概率相同，则删除一个元素
平均需要移动元素的个数是_____。
END ； 【答案】
6． 下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空：
【答案】
【解析】通过递归算法，首先找到最高位的值，将其放到str 对应的数组中，依次反向获取从高位到地位的值，将其放到数组中，完成了将整数逆序放到一个字符数组中。
7． 设有一个空找，栈顶指针为1000H （十六进制），现有输入序列为1，2，3, 4, 5，经过PUSH ，PUSH , POP , PUSH , POP ，PUSH ，PUSH 之后，输出序列是_____，而栈顶指针值是_____。设栈为顺序栈，每个元素占4个字节。
【答案】23; 100CH
8． 起始地址为480，大小为8的块，其伙伴块的起始地址是_____；若块大小为32，则其伙伴块的起始地址为_____。
【答案】
【解析】起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下：
根据上述公式起始地址就为488。
9． 设正文串长度为n ，模式串长度为m ，则串匹配的KMP 算法的时间复杂度为_____。
【答案】
10．分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间的是_____算法，最费时间的是_____算法。
【答案】起泡；快速
，【解析】当初态为有序表时，冒泡排序只需要进行一趟比较即可，此时时间复杂度为〇（n ） 而快速排序算法需要比较的次数达到最大，时间复杂度为
11．有五个数据依次入栈：1，2, 3, 4, 5。在各种出栈的序列中，以3, 4先出栈的序列有_____。（3在4之前出栈）
【答案】3个
【解析】以3, 4先出栈的序列有34521、34215、34251共3个。
12．在一棵m
阶的个数是_____。
【答案】【解析】m
阶
树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的
关键字的个数是_____；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字
树除根结点和叶子结点外，结点中关键字个数最多是
最少
二、选择题
13．为支持
A. 连续结构 B. 链式结构 C. 直接索引结构 D. 多级索引结钩 【答案】A
【解析】为了实现快速随机播放，要保证最短的查询时间，即不能选取链表和索引结构，因此连续结构最优。
14．静态链表中指针表示的是（ ）。
A. 下一元素的地址 B. 内存储器的地址 C. 下一元素在数组中的位置 D. 左链或右链指向的元素的地址 【答案】C
【解析】静态链表的一般结构为：
这种结构是预先分配一个较大的空间，类似于一次申请一个较大的数组，但是元素的增删操作都不会移动元素，只需要移动next 成员就行。因此，静态链表中的指针实际上表示的就是下一个元素在数组中的位置。
15．5个字符有如下4种编码方案，不是前缀编码的是（ ）
A.
B.
C.
D. 【答案】D
【解析】在一个字符集中，任何一个字符的编码都不是另一个字符编码的前缀。约定左分支
表示字符
右分支表示字符
则可以用从根结点到叶子结点的路径上的分支字符串作为该叶
子结点字符的编码。如此得到的编码必是前缀编码。D 选项中，编码110是编码1100的前缀，故不符合前缀编码的定义。
中视频文件的快速随机播放，播放性能最好的文件数据块组织方式是（ ）