数据结构考试题库及答案.docx
《数据结构考试题库及答案.docx》由会员分享，可在线阅读，更多相关《数据结构考试题库及答案.docx（41页珍藏版）》请在冰点文库上搜索。
数据结构考试题库及答案
数据结构期末考试
题库及答案
2018
目录
第1章绪论
1．选择题
（1）数据结构是指（1.A）。
A.数据元素的组织形式B.数据类型
C.数据存储结构D.数据定义
（2）计算机内部数据处理的基本单位是（10.B）。
A.数据B.数据元素C.数据项D.数据库
（3）数据结构中，与所使用的计算机无关的是数据的C结构.
A）存储B）物理C）逻辑D）物理和存储
【解析】[解析]数据结构概念一般包括数据的逻辑结构、存储结构及数据上的运算集合等。
数据的逻辑结构只抽象地反映数据元素之间的逻辑关系，而不管它在计算机中的存储形式。
（4）算法分析的目的是____C________
A）找出数据结构的合理性B）研究算法中的输入和输出的关系
C）分析算法的效率以求改进D）分析算法的易懂性和文档性
（5）计算机算法必须具备输入、输出和B等5个特性。
A）可行性、可移植性和可扩充性B）可行性、确定性和有穷性
C）确定性、有穷性和稳定性D）易读性、稳定性和安全性
（6）在数据结构中，从逻辑上可以把数据结构分成（）。
A．动态结构和静态结构B．紧凑结构和非紧凑结构
C．线性结构和非线性结构D．内部结构和外部结构
答案：
C
（7）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。
A．存储结构B．存储实现
C．逻辑结构D．运算实现
答案：
C
（8）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。
A．数据具有同一特点
B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致
C．每个数据元素都一样
D．数据元素所包含的数据项的个数要相等
答案：
B
（9）以下说法正确的是（）。
A．数据元素是数据的最小单位
B．数据项是数据的基本单位
C．数据结构是带有结构的各数据项的集合
D．一些表面上很不相同的数据可以有相同的逻辑结构
答案：
D
解释：
数据元素是数据的基本单位，数据项是数据的最小单位，数据结构是带有结构的各数据元素的集合。
（10）算法的时间复杂度取决于（）。
A．问题的规模B．待处理数据的初态
C．计算机的配置D．A和B
答案：
D
解释：
算法的时间复杂度不仅与问题的规模有关，还与问题的其他因素有关。
如某些排序的算法，其执行时间与待排序记录的初始状态有关。
为此，有时会对算法有最好、最坏以及平均时间复杂度的评价。
（11）以下数据结构中，（）是非线性数据结构
A．树B．字符串C．队列D．栈
答案：
A
2．填空题
01、数据结构是一门研究非数值计算的程序设计问题中计算机的（操作对象）以及它们之间的（关系和运算）等的学科。
02、数据结构被形式地定义为（D,R），其中D是（数据元素）的有限集合，R是D上的（关系）有限集合。
03、数据结构包括数据的（逻辑结构）、数据的（存储结构）和数据的（运算）这三个方面的内容。
04、数据结构按逻辑结构可分为两大类，它们分别是（线性结构）和（非线性结构）。
05、线性结构中元素之间存在（一对一）关系，树形结构中元素之间存在（一对多）关系，图形结构中元素之间存在（多对多）关系。
06、在线性结构中，第一个结点（没有）前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点（没有）后续结点，其余每个结点有且只有1个后续结点。
07、在树形结构中，树根结点没有（前驱）结点，其余每个结点有且只有
（1）个前驱结点；叶子结点没有（后续）结点，其余每个结点的后续结点数可以（任意多个）。
08、在图形结构中，每个结点的前驱结点数和后续结点数可以（任意多个）。
09、对于给定的n个元素，可以构造出的逻辑结构有（集合）、（线性结构）、（树形结构）、（图状结构）四种。
10、数据的运算最常用的有5种，它们分别是（插入）、（删除）、（修改）、（查找）、（排序）。
11、一个算法的效率可分为（时间）效率和（空间）效率。
12、数据结构中评价算法的两个重要指标是算法的（时间复杂度）和（空间复杂度）。
13、一个数据结构在计算机中的（映射）称为存储结构。
14、算法的五个重要特性是（有穷性）、（确定性）、（可行性）、输入、输出。
3．判断题
×01、数据元素是数据的最小单位。
×02、数据的逻辑结构是指数据的各数据项之间的逻辑关系。
×03、算法的优劣与算法描述语言无关，但与所用计算机有关。
√04、健壮的算法不会因非法的输入数据而出现莫名其妙的状态。
×05、算法可以用不同的语言描述，则算法实际上就是程序了。
×06、程序一定是算法。
√07、数据的物理结构是指数据在计算机内的实际存储形式。
×08、数据结构的抽象操作的定义与具体实现有关。
×09、在顺序存储结构中，有时也存储数据结构中元素之间的关系。
×10、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
√11、数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。
×12、数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构。
第2章线性表
1．选择题
（1）顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。
A．110B．108C．100D．120
答案：
B
解释：
顺序表中的数据连续存储，所以第5个元素的地址为：
100+2*4=108。
（2）在n个结点的顺序表中，算法的时间复杂度是O
（1）的操作是（）。
A．访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）
B．在第i个结点后插入一个新结点（1≤i≤n）
C．删除第i个结点（1≤i≤n）
D．将n个结点从小到大排序
答案：
A
解释：
在顺序表中插入一个结点的时间复杂度都是O（n2），排序的时间复杂度为O（n2）或O（nlog2n）。
顺序表是一种随机存取结构，访问第i个结点和求第i个结点的直接前驱都可以直接通过数组的下标直接定位，时间复杂度是O
（1）。
（3）向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（）。
A．8B．63.5C．63D．7
答案：
B
解释：
平均要移动的元素个数为：
n/2。
（4）链接存储的存储结构所占存储空间（）。
A．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
B．只有一部分，存放结点值
C．只有一部分，存储表示结点间关系的指针
D．分两部分，一部分存放结点值，另一部分存放结点所占单元数
答案：
A
（5）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。
A．必须是连续的B．部分地址必须是连续的
C．一定是不连续的D．连续或不连续都可以
答案：
D
（6）线性表Ｌ在（）情况下适用于使用链式结构实现。
A．需经常修改Ｌ中的结点值Ｂ．需不断对Ｌ进行删除插入
C．Ｌ中含有大量的结点Ｄ．Ｌ中结点结构复杂
答案：
B
解释：
链表最大的优点在于插入和删除时不需要移动数据，直接修改指针即可。
（7）单链表的存储密度（）。
A．大于1B．等于1C．小于1D．不能确定
答案：
C
解释：
存储密度是指一个结点数据本身所占的存储空间和整个结点所占的存储空间之比，假设单链表一个结点本身所占的空间为D，指针域所占的空间为N，则存储密度为：
D/（D+N），一定小于1。
（8）将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（）。
A．nB．2n-1C．2nD．n-1
答案：
A
解释：
当第一个有序表中所有的元素都小于（或大于）第二个表中的元素，只需要用第二个表中的第一个元素依次与第一个表的元素比较，总计比较n次。
（9）在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时须向后移动（）个元素。
A．n-iB．n-i+1C．n-i-1D．I
答案：
B
（10）线性表L=（a1，a2,……an），下列说法正确的是（）。
A．每个元素都有一个直接前驱和一个直接后继
B．线性表中至少有一个元素
C．表中诸元素的排列必须是由小到大或由大到小
D．除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。
答案：
D
（11）创建一个包括n个结点的有序单链表的时间复杂度是（）。
A．O
（1）B．O（n）C．O（n2）D．O（nlog2n）
答案：
C
解释：
单链表创建的时间复杂度是O（n），而要建立一个有序的单链表，则每生成一个新结点时需要和已有的结点进行比较，确定合适的插入位置，所以时间复杂度是O（n2）。
（12）以下说法错误的是（）。
A．求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低
B．顺序存储的线性表可以随机存取
C．由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活
D．线性表的链式存储结构优于顺序存储结构
答案：
D
解释：
链式存储结构和顺序存储结构各有优缺点，有不同的适用场合。
（13）在单链表中，要将s所指结点插入到p所指结点之后，其语句应为（）。
A．s->next=p+1;p->next=s;
B．（*p）.next=s;（*s）.next=（*p）.next;
C．s->next=p->next;p->next=s->next;
D．s->next=p->next;p->next=s;
答案：
D
（14）在双向链表存储结构中，删除p所指的结点时须修改指针（）。
A．p->next->prior=p->prior;p->prior->next=p->next;
B．p->next=p->next->next;p->next->prior=p;
C．p->prior->next=p;p->prior=p->prior->prior;
D．p->prior=p->next->next;p->next=p->prior->prior;
答案：
A
（15）在双向循环链表中，在p指针所指的结点后插入q所指向的新结点，其修改指针的操作是（）。
A．p->next=q;q->prior=p;p->next->prior=q;q->next=q;
B．p->next=q;p->next->prior=q;q->prior=p;q->next=p->next;
C．q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;
D．q->prior=p;q->next=p->next;p->next=q;p->next->prior=q;
答案：
C
2．填空题
1.线性表是一种典型的_________结构。
1．线性
2.在一个长度为n的顺序表的第i个元素之前插入一个元素，需要后移____个元素。
2．n-i+1
3.顺序表中逻辑上相邻的元素的物理位置________。
3．相邻
4.要从一个顺序表删除一个元素时，被删除元素之后的所有元素均需_______一个位置，移动过程是从_______向_______依次移动每一个元素。
4．前移，前，后
5.在线性表的顺序存储中，元素之间的逻辑关系是通过_______决定的；在线性表的链接存储中，元素之间的逻辑关系是通过_______决定的。
5．物理存储位置，链域的指针值
6.在双向链表中，每个结点含有两个指针域，一个指向_______结点，另一个指向_______结点。
6．前趋，后继
7.当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用_______存储结构为宜。
相反，当经常进行的是插入和删除操作时，则采用_______存储结构为宜。
7．顺序，链接
8.顺序表中逻辑上相邻的元素，物理位置_______相邻，单链表中逻辑上相邻的元素，物理位置_______相邻。
8．一定，不一定
9.在单链表中设置头结点的作用是________。
9．使空表和非空表统一；算法处理一致
3．判断题
（×）1.链表的每个结点中都恰好包含一个指针。
（×）2.链表的物理存储结构具有同链表一样的顺序。
（×）3.链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动将后续各个单元向前移动。
（×）4.线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。
（×）5.顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。
（×）6.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
（×）7.线性表在物理存储空间中也一定是连续的。
（√）8.线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。
（×）9.顺序存储方式只能用于存储线性结构。
（×）10.线性表的逻辑顺序与存储顺序总是一致的。
第3章栈和队列
1．选择题
（1）设有一个栈，元素的进栈次序为A,B,C,D,E,下列是不可能的出栈序列（C）。
A．A,B,C,D,EB．B,C,D,E,A
C．E,A,B,C,DD．E,D,C,B,A
（2）若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（）种情况。
A．5，4，3，2，1B．2，1，5，4，3C．4，3，1，2，5D．2，3，5，4，1
答案：
C
解释：
栈是后进先出的线性表，不难发现C选项中元素1比元素2先出栈，违背了栈的后进先出原则，所以不可能出现C选项所示的情况。
（3）若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（）。
A．iB．n-iC．n-i+1D．不确定
答案：
C
解释：
栈是后进先出的线性表，一个栈的入栈序列是1，2，3，…，n，而输出序列的第一个元素为n，说明1，2，3，…，n一次性全部进栈，再进行输出，所以p1=n，p2=n-1，…，pi=n-i+1。
（4）栈中元素的进出原则是（B）
Ａ．先进先出Ｂ．后进先出Ｃ．栈空则进Ｄ．栈满则出
（5）在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为（C）。
A．top不变B．top=0C．top--D．top++
（6）向一个栈顶指针为hs的链栈中插入一个s结点时，应执行（B）。
A．hs->next=s;
B．s->next=hs;hs=s;
C．s->next=hs->next;hs->next=s;
D．s->next=hs;hs=hs->next;
（7）在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为（D）。
A．rear％n==frontB．（front+l）％n==rear
C．rear％n-1==frontD．（rear+l）％n==front
（8）在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为（C）。
A．rear％n==frontB．front+l=rear
C．rear==frontD．（rear+l）％n=front
（9）在一个链队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操作为（A）。
A．front=front->next B．rear=rear->next
C．rear=front->next D．front=rear->next
（10）数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（）。
A．r-fB．（n+f-r）%nC．n+r-fD．（n+r-f）%n
答案：
D
解释：
对于非循环队列，尾指针和头指针的差值便是队列的长度，而对于循环队列，差值可能为负数，所以需要将差值加上MAXSIZE（本题为n），然后与MAXSIZE（本题为n）求余，即（n+r-f）%n。
（11）链式栈结点为：
（data,link），top指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作（）。
A．x=top->data;top=top->link；B．top=top->link;x=top->link；
C．x=top;top=top->link；D．x=top->link；
答案：
A
解释：
x=top->data将结点的值保存到x中，top=top->link栈顶指针指向栈顶下一结点，即摘除栈顶结点。
（12）栈在 （）中有所应用。
A．递归调用B．函数调用C．表达式求值D．前三个选项都有
答案：
D
解释：
递归调用、函数调用、表达式求值均用到了栈的后进先出性质。
（13）为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。
主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。
该缓冲区的逻辑结构应该是（）。
A．队列B．栈C．线性表D．有序表
答案：
A
解释：
解决缓冲区问题应利用一种先进先出的线性表，而队列正是一种先进先出的线性表。
（14）设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（ ）。
A．2B．3C．4D．6
答案：
B
解释：
元素出队的序列是e2、e4、e3、e6、e5和e1，可知元素入队的序列是e2、e4、e3、e6、e5和e1，即元素出栈的序列也是e2、e4、e3、e6、e5和e1，而元素e1、e2、e3、e4、e5和e6依次进入栈，易知栈S中最多同时存在3个元素，故栈S的容量至少为3。
（15）若一个栈以向量V[1..n]存储，初始栈顶指针top设为n+1，则元素x进栈的正确操作是（）。
A．top++;V[top]=x;B．V[top]=x;top++;
C．top--;V[top]=x;D．V[top]=x;top--;
答案：
C
解释：
初始栈顶指针top为n+1，说明元素从数组向量的高端地址进栈，又因为元素存储在向量空间V[1..n]中，所以进栈时top指针先下移变为n，之后将元素x存储在V[n]。
（16）设计一个判别表达式中左，右括号是否配对出现的算法，采用（ ）数据结构最佳。
A．线性表的顺序存储结构B．队列
C.线性表的链式存储结构D.栈
答案：
D
解释：
利用栈的后进先出原则。
（17）用链接方式存储的队列，在进行删除运算时（ ）。
A.仅修改头指针B.仅修改尾指针
C.头、尾指针都要修改D.头、尾指针可能都要修改
答案：
D
解释：
一般情况下只修改头指针，但是，当删除的是队列中最后一个元素时，队尾指针也丢失了，因此需对队尾指针重新赋值。
（18）循环队列存储在数组A[0..m]中，则入队时的操作为（ ）。
A.rear=rear+1B.rear=（rear+1）%（m-1）
C.rear=（rear+1）%mD.rear=（rear+1）%（m+1）
答案：
D
解释：
数组A[0..m]中共含有m+1个元素，故在求模运算时应除以m+1。
（19）最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（ ）。
A.（rear+1）%n==frontB.rear==front
C．rear+1==frontD.（rear-l）%n==front
答案：
B
解释：
最大容量为n的循环队列，队满条件是（rear+1）%n==front，队空条件是rear==front。
（20）栈和队列的共同点是（ ）。
A.都是先进先出B.都是先进后出
C.只允许在端点处插入和删除元素D.没有共同点
答案：
C
解释：
栈只允许在栈顶处进行插入和删除元素，队列只允许在队尾插入元素和在队头删除元素。
（21）一个递归算法必须包括（ ）。
A.递归部分B.终止条件和递归部分
C.迭代部分D.终止条件和迭代部分
答案：
B
2．填空题
1.线性表、栈和队列都是（线性）结构，可以在线性表的（任何）位置插入和删除元素；对于栈只能在（栈顶）位置插入和删除元素，不允许插入和删除运算的一端称为（栈底）。
；对于队列只能在（队尾）位置插入元素和在（队头）位置删除元素。
2.对于一个栈作进栈运算时，应先判别栈是否为（栈满），作退栈运算时，应先判别栈是否为（栈空），当栈中元素为m时，作进栈运算时发生上溢，则说明栈的可用最大容量为（m）。
为了增加内存空间的利用率和减少发生上溢的可能性，由两个栈共享一片连续的内存空间时，应将两栈的（栈底）分别设在这片内存空间的两端，这样只有当（两个栈的栈顶在栈空间的某一位置相遇）时才产生上溢。
3.设有一空栈，现有输入序列1，2，3，4，5，经过push,push,pop,push,pop,push,push后，输出序列是（2、3）。
4.（队列）是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。
5.在具有n个单元的循环队列中，队满时共有（n-1）个元素。
解析：
因为如果放置n个元素，首尾指针指向同一位置，与空队列无法区别，所以循环队列中认为当尾指针的后一个指针为首指针时，判定队列为满队列，即只能保存n-1个元素
6.带表头结点的空循环双向链表的长度等于（0）。
3．判断题
（×）1.在表结构中最常用的是线性表，栈和队列不太常用。
（√）2.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。
（√）3.对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。
（√）4.栈和链表是两种不同的数据结构。
（×）5.栈和队列是一种非线性数据结构。
（√）6.栈和队列的存储方式既可是顺序方式，也可是链接方式。
（√）7.两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。
（×）8.队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。
（×）9.一个栈的输入序列是12345，则栈的输出序列不可能是12345。
第4章串、数组和广义表
1．选择题
（1）串是一种特殊的线性表，其特殊性体现在（）。
A．可以顺序存储B．数据元素是一个字符
C．可以链式存储D．数据元素可以是多个字符若
答案：
B
（2）串下面关于串的的叙述中，（）是不正确的？
A．串是字符的有限序列B．空串是由空格构成的串
C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储
答案：
B
解释：
空格常常
升级会员 