数据结构考试习题集

1、第一章：时间复杂度：例如：1.数据元素是数据的基本单位，其中（）数据项A.只能包含一个B.不包括C.可以包含多个D.可以包括也可以不包括2.逻辑关系是指数据元素的（）A.关系 B.存储方式 C.结构 D.数据项3.算法在发生非法操作时可以作出处理的特性称为（）A.正确性 B.易读性C.高效性 D.健壮性4.数据的基本单位是_5.一个算法应具备_、_、_、_、_5个特性6.数据的逻辑结构被分为_、_、_、_四种。7.计算下列算法的时间复杂度x = 1;for(i = 1,i <= n;i+)for(j = 1;j <= n/2;j+)for(k = 1;k <= n;k+)x+

2、; 第二章带头结点的单链表，其头指针为L，则它为空表的条件是？ 在一个单链表中的p所指的结点之前插入一个s所指向的结点，操作如下：s->next = _;p->next = s;t=p->data;p->data=_;s->data=_; 在一个双链表中，在p所指向的结点之后插入q所指向的结点的操作是？ 在一个双链表中，在*p结点之前插入*q结点的操作是？ 在双链表中，删除*p结点的操作是？ 在双链表中，删除*p结点之后的一个结点的操作是？(不释放空间) 若某表最常用的操作是在最后一个结点之后插入一个结点或者删除最后一个结点，在采用_存储方式最节省时间。A单链表

3、B给出表头指针的循环单链表C双链表 D带头结点的循环双链表 某线性表最常用的操作是在最后一个结点之后插入一个结点或删除第一个结点，则采用_存储方式最节省运算时间。A单链表 B仅有头结点的单循环链表C双链表 D仅有尾结点指针的单循环链表 线性表是具有n个（）的有限序列A.表元素 B.字符C.数据元素 D.数据项 线性表采用链表存储时，其地址（）A.必须是连续的 B.一定是不连续的C.部分地址必须是连续的 D.连续与否均可以 线性表的顺序存储中，元素之间的逻辑关系是通过_决定的，而在链式存储中，元素之间的逻辑关系是通过_决定的。 向一个长度为n的顺序表中的第i个元素（1<=i<=n）之

4、前插入一个元素，需向后移动_个元素。 在一个长度为n的顺序表中删除第i个元素时，需要向前移动_个元素。 在一个长度为n的顺序表中删除第i个元素（0<=i<=n-1）时，需向前移动_个元素。 线性表中所有元素的排列顺序必须是由小到大或者由大到小？ 带头结点的循环链表L为空的判定条件是（）A.L= =NULL B.L->next =NULLC.L->next=L D.L!=NULL 在一个长度为n（n>1）的带头结点的单链表h上，另设有尾指针r（指向最后一个结点），执行（ ）操作时其复杂度与链表的长度有关。A.删除单链表的第一个元素B.删除单链表的最后一个元素C.在单

5、链表第一个元素前插入一个新元素D.在单链表最后一个元素后插入一个新元素 在单链表中，要删除某一个指定的结点，必须找到该结点的_结点。 在一个单链表中，指针p所指结点为最后一个结点的条件是_ 在一个单链表（已知每个结点含有数据域data和指针域next）中删除p所指结点时，应执行如下操作：(1)q=p->next;(2)p->next =_;(3)free(q); 线性表是具有n个_的有限序列。 线性表采用链表存储时 ，其元素地址（）A.必须连续B.一定不连续C.部分必须连续D.连续与否都可以 先行表中每个元素都有一个直接前驱和一个直接后继？（） 带头结点的单链表head为空的条件是

6、_。 链表不具备的特点是（） 可随机访问任意结点 插入删除不需要移动元素 不必事先估计存储空间 所需空间与其长度成正比 设线性表有2n个元素，（）在单链表上实现要比顺序表实现效率高？A.删除指定元素B.在最后一个元素后面插入一个新元素C.顺序输出前k个元素D.交换第i个元素和第2n-i-1个元素的值删除顺序表的_元素，需要移动的元素最多。算法设计 已知有某带头结点的单链表，其头指针为head，现在需要寻找表中的元素20，并在其后添加一个元素30，请编写能执行添加的函数，函数的原型如下：NODE* insert(NODE * head ,int x,int y) 其中x 是要寻找的元素,y是要添

7、加的元素，结构体的定义就借鉴以前的内容。第三章请编写程序，让四个字符ABCD按照DCBA的顺序入栈，但是出栈顺序是CDAB，应如何安排他们进栈和出栈 栈是操作受限制的线性表，插入操作和删除操作都必须在表的_进行。 它的元素在栈中的进出遵循_原则。 栈中没有元素，称为_，如果元素个数达到了顺序栈所能容纳的最大值，称为_。 栈中总是设置一个表示栈顶元素下标的变量，叫做_。 有一个栈，元素A，B，C，D只能依次进栈，则出栈序列中以下哪个是不可能得到的（）A. D、C、B、A B. C、B、A、DC. A、B、C、D D. D、C、A、B 有一单向铁路行驶道，（1）如果进站的车厢序列为123，则可能得

8、到的出站车厢的序列有哪些可能性。（2）如果进站的车厢序列为123456，则能否得到435612和135426的序列，说明为什么不能得到或者如何得到。 设n个元素进栈序列是1,2,3.,n，输出序列是p1,p2,.pn,若p1=3,则p2的值（）A.一定是2 B.一定是1C.不可能是1 D.以上都不对 有5个元素，它们的进栈顺序是A,B,C,D,E,在可能的出栈顺序中，以元素CD最先出栈的次序有哪几个？ 判定一个顺序栈st为空的条件是（）A.st.top=0; B.st.top!=0;C.st.top!=MAX;D.st.top=MAX; 判定一个顺序栈st为栈满的条件是（）；A.st.top=

9、0; B.st.top!=0;C.st.top!=MAX-1;D.st.top=MAX-1; 将f=1+1/2+1/3+.+1/n转化成递归函数，其递归出口（终结条件）是_递归公式是_。 队列也是操作受到限制的线性表，它只能在表的_插入，这一端称为_在表的_删除,这一端称为_。 队列中元素在表中的进出遵循_的原则。 顺序队列在多次出队和入队操作之后，会出现一种元素并没有装满，却无法再次入队的情况，我们称为_现象。 在队列中我们常常设置一个指针front，指向_的位置，我们称为队首指针，又设置一个指针rear,志向_的位置，我们称为_。 循环队列qu，已满的条件是（）A.（qu.rear+1）%

10、MAX=(qu.front+1)%MAXB. （qu.rear+1）%MAX=qu.front+1C.（qu.rear+1）%MAX=qu.frontD.qu.rear=qu.front 循环队列qu，已空的条件是（）A.（qu.rear+1）%MAX=(qu.front+1)%MAXB. （qu.rear+1）%MAX=qu.front+1C.（qu.rear+1）%MAX=qu.frontD.qu.rear=qu.front 某循环队列中数组下标是0n-1，其头指针front和rear值分别为f和r，则元素的个数为_。 带头结点的链队qu，对头和队尾指针分别为front和rear，则判断队

11、空的条件是（）A.qu.front=qu.rearB.qu.front!=NULLC.qu.rear!=NULLD.qu.front=NULL 某链队qu,目前只有一个元素，要将此元素删除，应当怎么做。p=qu->front->next;qu->front->next =_;_ = qu->front;free(p);5.在栈中允许插入和删除的一端称为_，另一端称为_。栈的插入操作通常称为_，而删除操作则称为_。栈中无元素时称为_。6.已知一个栈的进栈序列是1234n，其输出序列的第一个元素是i，则第j个出栈元素是（i-j+1）。A.I B.n-IC.j-i+1

12、D.不确定7.设n个元素进栈序列是123.n，其输出序列是p1p2,.pn,则p33，则p2的值（）。A. 一定是2 B.一定是1C.不可能是2 D.不可能是36.顺序栈中元素值的大小是有序的？7.N个元素进栈后，他们的出栈顺序一定和进栈顺序正好相反。8.栈顶元素和栈底元素可能是同一个元素。9.判定一个顺序栈st为空的条件是（）；A.st.top=0; B.st.top!=0;C.st.top!=MAX;D.st.top=MAX;10.判定一个顺序栈st为栈满的条件是（）；A.st.top=0; B.st.top!=0;C.st.top!=MAX-1;D.st.top=MAX-1;C.f(0)

13、=1 D.f(n)=n第四章第五章有如下矩阵，则用三元组法表示应该如何表示？第六章有某树中序序列为DGBAECF 后序序列为GDBEFCA，请构造出此二叉树。 给定某树的中序遍历序列为BDCAEHGKF，后序遍历为：DCBHKGFEA，请画出树的形态图。 某通信系统中可能出现8个字符a,b,c,d,e,f,g,h，出现的频度分别为(5,29,7,8,14,23,3,11)，为此8个字符设计哈夫曼编码。 按照树的定义，具有3个结点的二叉树有（）种 A.3B.4 C.5D.6 一个满二叉树，有n个结点和m个叶子,深度为h，则 A.n=h+mB.h+m=2n C.m=h-1D.n=2h-1 在一棵完

14、全二叉树中，结点数目为n，从1开始从上到下，从左到右编号，编号最大的分支结点编号是_。 二叉树有50个叶子结点，则二叉树的总结点数目至少有多少个？ 在一非空二叉树的中序编列序列中，根结点的左边（） A.只有右子树上的所有结点 B.只有右子树上的部分结点 C.只有左子树上的所有结点 D.只有左子树上的部分结点 任何一棵二叉树的叶子结点在三种遍历序列中的相对次序（） A.不发生改变B.发生改变 C.不能确定D.以上都不对 一棵二叉树的先序遍历序列为ABCDEFG，它的中序序列可能是（） A.CABDEFGB.ABCDEFG C.DACEFBGD.ADCFEGB 一棵二叉树的先序序列是ABCDEF，中序为CBAEDF，则后序为（） A.CBEFDAB.FEDCBA C.CBEDFAD.不确定 二叉树先序序列和中序序列相同的条件是_。 n个结点的线索二叉树上含有的线索数目为 A.2nB.n-1 C.n+1D.n 线索二叉树中左线索指向_，右线索指向_. 引入线索二叉树的目的是（） A.加快查找结点前驱和后继的速度 B.为了能在树中方