数据结构复习题集一、判断题1.线性表的长度是线性表所占用的存储空间的大小。

( F )2.双循环链表中，任意一结点的后继指针均指向其逻辑后继。

( F )3.在对链队列做出队操作时，不会改变front指针的值。

( F )4.如果两个串含有相同的字符，则说它们相等。

( F )5.如果二叉树中某结点的度为1，则说该结点只有一棵子树。

(T )6.已知一棵树的先序序列和后序序列，一定能构造出该树。

( F )7.图G的一棵最小代价生成树的代价未必小于G的其它任何一棵生成树的代价。

(T )8.图G的拓扑序列唯一，则其弧数必为n-1（其中n为顶点数）。

( F )9.对一个堆按层次遍历，不一定能得到一个有序序列。

(T )10.直接选择排序算法满足：其时间复杂度不受数据的初始特性影响，为O(n2)。

(T )11. 线性表的逻辑顺序与物理顺序总是一致的。

( F )12. 线性表的顺序存储表示优于链式存储表示。

( F )13.线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。

(T )14. 二维数组是其数组元素为线性表的线性表。

( F )15. 每种数据结构都应具备三种基本运算：插入、删除和搜索。

(T )16.（101，88，46，70，34，39，45，58，66，10）是堆；(T )17.将一棵树转换成二叉树后，根结点没有左子树；( F )18.对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作，所得的输出序列也一定相同；(F)19.哈夫曼树是带权外部路径长度最短的树，路径上权值较大的结点离根较近( T )20.用一组地址连续的存储单元存放的元素一定构成线性表。

(F)21.堆栈、队列和数组的逻辑结构都是线性表结构。

( T )22.给定一组权值，可以唯一构造出一棵哈夫曼树。

( F)23.相对于索引文件的基本数据，索引表包含的信息量相对少得多，因此。

索引表可以常驻内存。

( T)24.在平均情况下，快速排序法最快，堆积排序法最节省空间。

( T)25.快速排序法是一种稳定性排序法。

( F )二.选择题:1.一个栈的输入序列为12345，则下列序列中是栈的输出序列的是（A）。

A.23415B.54132C.31245D.1425 32．设循环队列中数组的下标范围是1~n，其头尾指针分别为f和r，则其元素个数为（D）。

A.r-fB.r-f+1C.(r-f) mod n +1D.(r-f+n) mod n3．二叉树在线索化后，仍不能有效求解的问题是（D）。

A.先序线索二叉树中求先序后继B. 中序线索二叉树中求中序后继C.中序线索二叉树中求中序前驱D. 后序线索二叉树中求后序后继4．求最短路径的FLOYD算法的时间复杂度为（D）。

A.O(n)B.O(n+e)C.O(n2)D.O(n3)5．一棵左右子树不空的二叉树在先序线索化后，其空指针域数为（B）。

A.0B.1C.2D.不确定6．数组A[1..5,1..6]的每个元素占5个单元，将其按行优先顺序存储在起始地址为1000的连续的内存单元中，则元素A[5,5]的地址为（A）。

A.1140B.1145C.1120D.11257．在下列排序算法中，在待排序的数据表已经为有序时，花费时间反而最多的是（A）。

A.快速排序B.希尔排序C.冒泡排序 D.堆排序8. 某算法的空间花费s(n)=100nlog2n+1000n+2000,其空间复杂度为[ D ]A.O(1)B.O(n)C.O(n1.5)D.O(nlog2n)9．下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是（D）。

A.堆排序B.冒泡排序C.快速排序 D.直接插入排序10．在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡点为A，并已知A的左孩子的平衡因子为-1，右孩子的平衡因子为0，则做（B）型调整以使其平衡。

A.LLB.LRC.RLD.RR设单链表中结点的结构为typedef struct node { //链表结点定义ElemType data; //数据struct node * Link; //结点后继指针} ListNode;11. 已知指针p所指结点不是尾结点，若在*p之后插入结点*s，则应执行下列哪一个操作？[B]A. s->link = p; p->link = s;B. s->link = p->link; p->link = s;C. s->link = p->link; p = s;D. p->link = s; s->link = p;12. 非空的循环单链表first的尾结点（由p所指向）满足：[C ]A. p->link == NULL;B. p == NULL;C. p->link == first;D. p == first;13.在单项链表中删除一个指定结点的后继的时间复杂度为 [ C ]A.O(n)B.O(nlog2n)C.O(1)D.O(√n)14.在n(n>0)个元素的顺序栈中删除1个元素的时间复杂度为 [ D ]A.O(1)B.O(√n)C.O(nlog2n)D.O(n)15.广义表的深度是 [ C ]A.广义表中子表个数B.广义表括号个数C.广义表展开后所含的括号层数D.广义表中元素个数16.高度为h(h>0)的二叉树最少有________个结点 [ C ]A.hB.h-1C.h+1D.2h17.n个顶点的带权无向连通图的最小生成树包含___A_____个顶点 [ ]A.n-1B.nC.n/2D.n+118.冒泡排序在最好情况下时间复杂度为 [ C ]A.O(1)B.O(nlog2n)C.O(n)D.O(n2)19.采用拉链法解决冲突的散列表中，查找的平均查找长度 [ C ]A.直接与关键字个数有关B.直接与装填因子a有关C.直接与表的容量有关D.直接与散列函数有关20. 下列图示的顺序存储结构表示的二叉树是(A )21. n个顶点的连通图中至少含有(A )A. n-1条边B. n条边C. n(n-1)/2条边D. n(n-1)条边22. 对关键字序列(56，23，78，92，88，67，19，34)进行增量为3的一趟希尔排序的结果为( D)A. (19，23，56，34，78，67，88，92)B. 23，56，78，66，88，92，19，34)C. (19，23，34，56，67，78，88，92)D. (19，23，67，56，34，78，92，88)23.某二叉树的先序序列和后序序列正好相同，则该二叉树一定是( A )的二叉树。

A.空或只有一个结点B.高度等于其结点数C.任一结点无左孩子D.任一结点无右孩子24.下列排序算法中，时间复杂度不受数据初始状态影响，恒为O(nlog2n)的是( A )A.堆排序B.冒泡排序C.直接选择排序D.快速排序25.广义表A=（a,b,(c,d),(e,(f,g))）,则下面式子的值为( D )；Head(Tail(Head(Tail(Tail(A)))))A．（g） B.(d) C.c D.d26.请指出在顺序表{2、5、7、10、14、15、18、23、35、41、52}中，用二分法查找关键码12需做多少次关键码比较。

（ C）A、2B、3C、4D、527. 下面关于图的存储的叙述中，哪一个是正确的。

（ A）A．用相邻矩阵法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关B．用相邻矩阵法存储图,占用的存储空间数只与图中边数有关,而与结点个数无关C．用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关D．用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关28.给定一个整数集合{3，5，6，9，12}，下列二叉树哪个是该整数集合对应的霍夫曼（Huffman）树。

（ C ）29.对线性表采用折半查找法，该线性表必须(C)。

A.采用顺序存储结构B.采用链式存储结构C.采用顺序存储结构，且元素按值有序D.采用链式存储结构，且元素按值有序30.已知二叉树的前序序列为ABDCEFG，中序序列为DBCAFEG，则后序序列为( B)。

A. DCBAFGEB. DCBFGEAC.DCBFEGA D. DCBGFEA31．下列各式中，按增长率由小至大的顺序正确排列的是( D )A． log n，n！，2n ，n3/2B．n3/2，2n，n logn，2100C．2n，log n，n logn，n3/2D．2100，logn, 2n, n n32．若要在单链表中的结点*p之后插入一个结点*s，则应执行的语句是( A )A．s->next=p->next; p->next=s; B．p->next=s;s->next=p->next;C．p->next=s->next; s->next=p; D．s->next=p;p->next=s->next;33.若要在O（1）的时间复杂度上实现两个循环链表头尾相接，则应对两个循环链表各设置一个指针，分别指向( B )A．各自的头结点B．各自的尾结点C．各自的第一个元素结点D．一个表的头结点，另一个表的尾结点34．二维数组A[20][10]采用列优先的存储方法，若每个元素占2个存储单元，且第1个元素的首地址为200，则元素A[8][9]的存储地址为( 200+(20*9+8)*2=576//首地址应该为200,此时答案为B )A．574B．576C．594D．58035．对广义表L=((a,b),c,d)进行操作tail(head(L))的结果是( D )A．（c,d）B．(d)C．bD．(b)36.已知一棵树的前序序列为ABCDEF，后序序列为CEDFBA，则对该树进行层次遍历得到的序列为( D )A．ABCDEFB．ABCEFDC．ABFCDED．ABCDFE37.在一个长度为n的顺序存储的线性表中，删除第i个元素（1<=I<=n）时，需要从前向后依次前移（A）个元素。

A、n-iB、n-I+1C、n-I-1D、I38.假定一个顺序队列的队首和队尾指针分别为f和r，则判断队空的条件为（ D）A、f+1==rB、r+1==fC、f==0D、f==r39.某带头结点的单链表的头指针为head，判定该链表为非空的条件是( D )A.head==NULLB.head->next==NULLC.head!=NULLD.head->next!=NULL40.导致栈上溢的操作是( B )A.栈满时执行的出栈B.栈满时执行的入栈C.栈空时执行的出栈D.栈空时执行的入栈41.假设一棵完全二叉树按层次遍历的顺序依次存放在数组BT[m]中，其中根结点存放在BT[0]，若BT[i]中的结点有左孩子，则左孩子存放在( D )A. BT[i/2]B. BT[2*i-1]C. BT[2*i]D. BT[2*i+1]42.连通图是指图中任意两个顶点之间( A )A.都连通的无向图B.都不连通的无向图C.都连通的有向图D.都不连通的有向图三、名词解释1．描述线性表中三个概念的区别：头指针、头结点、首元结点（第1个元素结点）。