数据结构与算法-考研(北京航空航天大学 1998 链表)

/ 知识库 / 试卷库

填空题（1998北京航空航天大学）

在非空双向循环链表中q所指的结点后面插入p所指的结点的过程已经依次进行了以下3步：p->llink=q；p->rlink=q->rlink；q->rlink=p；第4步应该是____________________；（写出该步对应的语句）。

答案解析

点击查看答案

关键词

链表；插入；算法；线性表；表链；循环；llink；指针；结点；

北京航空航天大学

若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法时间复杂度为【】。（1≤i≤n+1）

在解决计算机主机与打印机之间速度不匹配问题时，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印。该缓冲区应念是一个【】结构。

中缀表达式 A-(B + c/d) * E的后缀形式是【】

一般情况下，将递归转换成等价的非递归算法应该设置【】

一个深度为 h 的满 m 叉树有如下性质：第 h 层上的结点都是叶结点，其各层上每个结点有 m 棵非空子树。问：（1）第 k 层最多有多少个结点？（k≤h )（2）整棵树最多有多少个结点？（3）若按层次从上到下，每层从左到右的顺序从1开始对全部结点编号，编号为 i 的结汽的双亲结点的编号是什么？编号为 i 的结点的第 j 个孩子结点（若存在）的编号是什么？

对二叉排序树进行【】遍历，可以得到该二叉树所有结点构成的排序序列。

若二叉树采用二叉链表存储结构，要交换其所有分支结点左右子树的位置，利用【】遍历方法最合适。

若在线性表中采用折半查找元素，该线性表应该【】。

利用逐点插入法建立序列（50，72，43，85，75，20，35，45，65，30）对应的二叉排序树以后，查找元素35要进行【】次元素间的比较。

若杂凑表（Hash）的地址范围为[0,9]，杂凑函数为H(key)=(key2+2) MOD 9，并采用链地址法处理冲突，请画出元素7、4、5、3、6、2、8、9依次插入杂凑表的状态。

链表

将下图所示的s所指点加到p所指点之后，其语句应为【】

双向链表的优势是____________________。

线性表选用顺序存储结构表示的适用场合是____________________。

将长度为n的单链表接在长度为m的单链表之后的算法时间复杂度为__________。

在含有n个元素的顺序表中，算法时间复杂度为O(1)的操作是【】

表长为n的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均个数为_______，删除一个元素需要移动元素的平均个数为_______。供选择的答案：A.(n-1)/2 B.n C.n+1 D.n-1 E.n/2 F.(n+1)/2 G.(n-2)/2

线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。【】

线性表是具有n个【】的有限序列。

假设线性表的长度为n，且采用顺序存储结构存储。当在线性表的任何位置上插入一个数据元素的概率相同时，插入一个数据元素需要移动元素的平均个数为【】。

设A是一个线性表（a1,a1,...,an），采用顺序存储结构，则在等概率的前提下，平均每插入一个元素需要移动的元素个数为多少？若元素插在ai与ai+1之间（0≤i≤n-1）的概率为，则平均每插入一个元素所要移动的元素个数又是多少？

填空题

某二叉树中度为2的结点有18个，则该二叉树中有__________个叶子结点。

对长度为10的线性表进行冒泡排序，最坏情况下需要比较的次数为__________。

设栈 S 和队列 Q 的初始状态为空，元素 a 、 b 、 c 、 d 、e、 f 依次通过栈 S ，一个元素出栈后即进入队列 Q 。若这 6 个元素出队列的顺序是 b 、 d 、 c 、f、 e 、 a ，则栈 S 的容量至少应该是__________。

用数组 Q（其下标在 0 . . n-1 中，共有n个元素）表示一个环形队列， f 为当前队头元素的前一位置， r 为队尾元素的位置。假定队列中元素个数总小于 n ,求队列中元素个数的公式是__________。

对于正整数n ，输出其和等于n且满足以下限制条件的所有正整数的和式，组成和式的数字自左至右构成一个非递增的序列。如 n = 4 ，程序输出为：4 = 44 = 3 + 14 = 2 + 24 = 2 ＋ 1 ＋ 1 4 = 1 ＋ 1 ＋ 1 ＋ 1test 是实现该功能的 C 程序段，请将未完成的部分补足，使之完整。test 函数为一递归函数，参数 n 为被分解和式的数， k 为当前的分解深度。算法思想是对 n 的所有合理的和式分解，将分解出的数（称为和数）存于二数组 a[]中。当其中一个分解己不再需要进一步进行时，即找到一个解，将存于 a[] 中的一个完整和式的和数输出。当还需要进一部分解时，以要进一部分解的数及分解深度为参数，递归调用 test 函数。#define MAXN 100 int a[MAXN]; test(int n,int k){ int i,j; for (j=__________；j>=1；j--）{ a[k]=j; if (__________）{ printf ( "%d = %d" , a[0]，a[l]); for (i = 2 ; i < = k ; i + + ) printf ( " + % d " , a[i]); printf ( " n " ); }else test(__________，k + l ); } }

一棵二叉树的中序遍历结果为DBEAFC，前序遍历结果为ABDECF，则后序遍历结果为 __________。

深度为5的满二叉树有__________个叶子结点。

对于前序遍历和中序遍历结果相同的二叉树为__________；对于前序遍历和后序遍历结果相同的二叉树是为__________。一般二叉树只有根结点的二叉树要结点无左孩子的二叉树根结点无右孩子的二叉树所有结点只有左子树的二叉树所有结点只有右子树的二叉树

具有7个结点的互不相识的二叉树共有__________棵。

具有n个叶子的二叉树，每个叶子的权值为wi（1≤i≤n），其中带权路径长度最小的二叉树称为__________。