一、单项选择题1.逻辑关系是指数据元素间的（）A．类型 B．存储方式 C．结构 D．数据项2.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( )A．顺序表 B.用头指针表示的单循环链表C. 用尾指针表示的单循环链表D. 单链表3.设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（）A．front=front+1 B．front= (front+1)%(m-1)C．front=(front-1)%m D．front=(fro nt+1)%m4.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为( )。
A．rear％n==front B．(front+l)％n==rearC．rear％n-1==front D．(rear+l)％n==front5.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为( )。
A．rear％n==front B．front+l=rearC．rear==front D．(rear+l)％n=front6.已知一颗二叉树上有92个叶子结点，则它有____个度为2的结点。
( )A. 90B. 91C. 92D. 937.在一棵非空二叉树的中序遍历序列中，根结点的右边_____。
A. 只有右子树上的所有结点B. 只有右子树上的部分结点C. 只有左子树上的所有结点D. 只有左子树上的部分结点8.有n条边的无向图的邻接表存储法中，链表中结点的个数是( )个。
A. nB. 2nC. n/2D. n*n9.判断有向图是否存在回路，除了可利用拓扑排序方法外，还可以利用（）。
A. 求关键路径的方法B.求最短路径的方法C. 深度优先遍历算法D.广度优先遍历算法10.对线性表进行二分查找时，要求线性表必须( )。
A.键值有序的顺序表B.键值有序的链接表C.链接表但键值不一定有序D.顺序表但键值不一定有序11.下列时间复杂度中最好的是（）。
A．O(1) B．O(n) C．O(log2n) D．O(n2) 12.若某线性表的常用操作是取第i个元素及其前趋元素，则采用( )存储方式最节省时间？A．顺序表B．单链表C．双链表D．单向循环13.在一个单链表HL中，若要向q所指结点之后插入一个由指针p指向的结点，则执行（）A．HL=p;p->next=HL B．p->next=HL;HL=pC．p->next=q->next;q->next=p D．p->next=q->next;q=p>next 14.栈和队列是两种特殊的线性表，只能在它们的（）处添加或删除结点。
A．中间点 B．端点C．随机存取点 D．结点15.一个栈的输入序列为1，2，3，4，5，则下列序列中不可能是站的输出序列的是___A. 2,3,4,1,5B.5,4,1,3,2C. 2,3,1,4,5D.1,5,4,3,216.广义表((a),a)的表尾是。
（）A．a B．∧ C．(a) D． ((a)) 17.将含100个结点的完全二叉树从根这一层开始，每层从左至右依次对结点编号，根结点的编号为1。
编号为47的结点X的双亲的编号为( )A．24 B．25 C．23 D．无法确定18.有n个顶点的无向图的邻接矩阵是用______数组存储。
A. n行n列B.一维C.任意行n列D.n行任意列19.如图所示有向图的一个拓扑序列是（）A．ABCDEF B．FCBEAD C．FEDCBA D．DAEBCF 20.有一个有序表{1，4，6，10，18，35，42，53，67，71，78，84，92，99}，当用二分查找法查找键值为84的结点时，经_____比较后查找成功。
A.2B.3C.4D.1221.在一个带有附加表头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行（）A. HL=p; p->next=HL;B. p->next=HL->next;HL->next=p;C. p->next=HL; p=HL;D. p->next=HL; HL=p;22.若采用单链表表示循环队列，则应该选用（）A. 带尾指针的非循环链表B. 带尾指针的循环链表C. 带头指针的非循环链表D. 带头指针的循环链表23.栈和队列是两种特殊的线性表，只能在它们的处添加或删除结点。
（）A. 中间点B. 端点C. 随机存取点D. 结点24.首先访问结点的左子树，然后访问该结点，最后访问结点的右子树，这种遍历称为()A.前序遍历B.后序遍历C.中序遍历D.层次遍历25.树最适合用来表示（）A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据26.已知一颗二叉树上有92个叶子结点，则它有____个度为2的结点。
（）A. 90B. 91C. 92D. 9327.对一棵查找树根结点而言，左子树中所有结点与右子树中所有结点的关键字大小关系是()A、小于B、大于C、等于D、不小于28.对关键字序列19，11，27，18，33进行快速排序，则要进行多少次关键字比较？（）A. 5次B. 6次C. 7次D. 8次1.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。
( C )A.688B.678C.692D.6962.设有6个结点的无向图，该图至少应该有( A )条边才能确保是一个连通图。
A.5B. 6C. 7D. 83.根据二叉树的定义可知二叉树共有( B )种不同的形态。
A.4B.5C.6D.74. 假设在一棵二叉树中，双分支结点数为15，单分支结点数为30 个，则叶子结点数为( B )个。
A．15 B．16 C．17 D．475. 任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序( A )。
A．不发生改变B．发生改变C．不能确定D．以上都不对6.在一个具有n个顶点的无向完全图中，所含的边数为( C )。
A．n B．n(n-1) C．n(n-1)/2 D．n(n+1)/27.若一个图的边集为{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)}，则从顶点A开始对该图进行深度优先搜索，得到的顶点序列可能为( B )。
A．A,B,C,F,D,E B．A,C,F,D,E,BC．A,B,D,C,F,E D．A,B,D,F,E,C8.假定对元素序列(7,3,5,9,1,12)进行堆排序，采用小顶堆，则初始数据构成的初始堆为( B )。
A．1,3,5,7,9,12 B．1,3,5,9,7,12C．1,7,3,5,9,12 D．1,3,5,7,9,12二、填空题1.根据值的不同特性，高级程序语言中的数据类型可分为两类：_______和__________。
2.线性表有两种存储结构：_________和___________。
3.在以HL为表头指针的循环单链表中，链表为空的条件为_______。
4.设栈S和队列Q的初始状态皆为空，元素a1,a2,a3,a4,a5和a6一次通过一个栈后即进入队列Q，若6个元素出对的顺序是a3,a5,a4,a6,a2,a1，则栈S至少可以容纳_____个元素。
5.对于一棵具有30个结点的二叉树，若一个结点的编号为5，则它的左孩子结点的编号为_______，右孩子结点的编号为______，双亲结点的编号为_________。
6.对于一个具有n个结点的二叉树，当它存储在二叉链表中时，其指针字段的总数为_________个，其中_________个用于链接孩子结点，_________个空闲。
7.设图中有n 个顶点，e条边，则含有e=____ __条边的无向图称作完全图，含有e=_________条弧的有向图称作有向完全图。
8.对于线性表（78，4，56，30，65）进行哈希存储时，若选用H（K）=K %5作为哈希函数，则哈希地址为0的元素有______个。
9.在单链表上难以实现的排序方法有_______和________ 。
10.根据值的不同特性，高级程序语言中的数据类型可分为两类：_______和__________。
11.在单链表中，删除指针P所指节点的后继结点的语句是________。
12.栈又称为____________的线性表，队列又称为___________的线性表。
13.N个结点的二叉树采用二叉链表存放，共有空链域个数为________________。
14.一棵深度为k的满二叉树的结点总数为___________，一棵深度为k的完全二叉树的结点总数的最小值为___________，最大值为___________。
15.具有80个结点的完全二叉树，若按层次从上到下、从左到右对其编号(根结点为1号)，则编号最大的分支结点序号为___________，编号最小的分支结点序号为___________，编号最大的叶子结点序号为___________，编号最小的叶子结点序号为___________。
16.采用二分法进行查找的查找表，应选择_________的存储结构。
17.假设在有序表A[ 0…19]中进行二分查找，比较二次查找成功的结点数为______，比较三次查找成功的结点数为________。
18.一个有向图G中若有弧<Vj,Vi>、<Vi,Vk>和<Vj,Vk>，则在图G的拓朴序列中，顶点Vi,Vj和Vk的相对位置为______。
19.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为_________，在表尾插入元素的时间复杂度为____________。
20.栈又称为____________的线性表，队列又称为___________的线性表。
21.对于一棵具有n个结点的二叉树，用二叉链表存储时，其指针总数为__________个，其中___________个指针是空闲的。
22.在稀疏矩阵所对应的三元组线性表中，每个三元组元素按_________为主序、_________为辅序的次序排列。
23.一颗深度为K且有____________个结点的二叉树称为满二叉树。
24.若对一棵完全二叉树从0开始进行结点的编号，并按此编号把它顺序存储到一维数组A中，即编号为0的结点存储到A[0]中。
其余类推，则A[i]元素的左孩子元素为________，双亲元素为____________。