当前位置：问答库＞考研试题

一、填空题

1． 设T 和P 是两个给定的串，在T 中寻找等于P 的子串的过程称为_____，又称P 为_____。

【答案】模式匹配；模式串

2． 顺序查找n 个元素的顺序表，若查找成功，则比较关键字的次数最多为_____次；当使用监视哨时，若查找失败，则比较关键字的次数为_____。

【答案】n ; n+1

【解析】最多的情况就是把整个表遍历了一遍。使用监视哨时，需要多一个存储空间来存监视哨。

3． 对于一个具有n 个结点的单链表，在已知的结点半p 后插入一个新结点的时间. 复杂度为_____，在给定值为x 的结点后插入一个新结点的时间复杂度为_____。

【答案】O(1)；O(n)

【解析】第一种情况只需直接修改指针的指向。第二种情况必须从头结点遍历找到x 的结点。

4． —棵左子树为空的二叉树在前序线索化后，其中的空链域的个数为_____。

【答案】2

【解析】只有根结点的做指针为空和最右边的叶结点的右指针为空。

5． 当两个栈共享一存储区时，栈利用一维数组stack(1，，1) 表示，两栈顶指针为top[l]与top[2]，则当栈1空时，top[l]为_____，栈2空时，top[2]为_____，栈满时为_____。

【答案】0；n+1；top[l]+l＝top[2]

【解析】共享栈的栈底在共享存储区的两端，当栈满时栈顶相邻。

6． 空格串是指_____，其长度等于_____。

【答案】由空格字符(ASCII值32) 所组成的字符串；空格个数

7． —棵深度为k 的平衡二叉树， 其每个非终端结点的平衡因子均为0，则该树共有_____个结点。

【答案】

树。故结点个数为

。

【解析】每个非终端结点都是0表示该平衡二叉树没有高度落差。也就是说它是一棵满二叉

8．

给定一组数据

WPL 的值为_____。

【答案】5；96 以它构造一棵哈夫曼树，则树高为_____，带权路径长度

【解析】每次找两个最小的权值构建哈夫曼树:

9． 在基于关键字比较且时间为

【答案】归并；堆

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．文件可按其记录的类型不同而分成两类，即 _____和_____文件。

【答案】操作系统文件；数据库

12．

线性表

【答案】(n﹣1)/2

【解析】删除第一个元素需要移动n ﹣1次，以此类推，删除最后一个元素需要移动0次。平均次数为(n﹣l)*n/n/2＝(n﹣l)/2。

13．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_____存储结构。

【答案】顺序

【解析】顺序存储结构的存取操作比较方便，但插入和删除操作不如链式存储结构方便，而且需要连续的存储空间，由于该线性表的元素总数基本稳定，而且很少进行插入删除操作，为了更快的存取元素，顺序表更合适。

14．表达式23＋((12*3﹣2)/4＋34，5/7) ＋108/9的后缀表达式是_____。 【答案】

(表达式中的点(.)是数分隔符，如是三个数) 用数组表示，假定删除表中任一元素的概率相同，则删除一个元 _ 的排序中，若要求排序是稳定的，则可选用_____排序；若要求就地排序(及辅助空间为O(1))，则可选用_____排序。 素平均需要移动元素的个数是_____。