北京石油化工学院期末考试真题+解析

题目	题型
在包含有1000个元素的线性表中实现如下四个操作，所需要的执行时间最长的是 ( )	单选
( )在一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动元素的个数为	单选
不带头结点的单链表head为空的判定条件是	单选
( )一个栈的入栈序列为A，B，C，D，E，则不可能的输出序列是	单选
( )循环队列用数组A[0,m-1]存放其元素值，已知其头尾指针分别是fr	单选
( )设高度为h（根的层次为1）的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为	单选
数组A[8][10] 中（下标均从0开始），每个元素的长度为3个字节，按列存储时，元素A[4][7]的起始地址为（SA为数组存储时的首地址）	单选
设计一个算法时应考虑达到的目标有()，()等。	填空
下面程序段的程序复杂度为()，其中n为正整数。	填空
在下面的数组 a 中链接存储着一个线性表，表头指针为 a[0].next ，则该线性表为()	填空
假设一棵二叉树先序遍历序列是ABCEDFGHIJ和中序序列是ECDBFAIHJG，则该树中第二层最左边的结点为()（根的层次为1）。	填空
若线索二叉树中t所指结点满足条件t->ltag ==Thread，则t->lchild域指示结点的()；若t->rtag = =Link，则t->rchild域指示结点的()。	填空
在序列(2，8，15，16，24，35，50)中采用折半查找方法查找元素24，请写出查找过程中依次和给定值“24”比较的关键字()。	填空
设计递归问题的非递归算法一般需要用到()机制。	填空
排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为()排序。	填空
输入一个正整数序列{56，32，78，19，45，23，69，90，17，73}，（1）请建立一棵二叉排序树。（2）若各元素的查找概率相同，均为1/10，计算ASL（平均查找长度）。（3）请画出删除32后的二叉排序树	问答
已知待排序序列{56，32，78，19，45，23，69，90，17，73}，请用快速排序法对该序列进行升序排序，并写出排序过程。	问答
请写出程序执行到标号后栈的状态，并写出运行结果。	问答
已知一个图的顶点集 V 各边集 G 如下：（1）请画出该无向图。（2）请写出存储该图的邻接矩阵（3）写出从顶点V0出发进行深度优先遍历得到的顶点序列。	问答
已知一组可用字符及对应的频率值，请（1）构造哈夫曼树。（2）求出该哈夫曼树的WPL值。（3）写出相应的哈夫曼编码，并写出“CAD”的编码	问答

题目

题型

在包含有1000个元素的线性表中实现如下四个操作，所需要的执行时间最长的是 ( )

单选

( )在一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动元素的个数为

单选

不带头结点的单链表head为空的判定条件是

单选

( )一个栈的入栈序列为A，B，C，D，E，则不可能的输出序列是

单选

( )循环队列用数组A[0,m-1]存放其元素值，已知其头尾指针分别是fr

单选