数据结构练习试题和答案解析
第1章绪论
一、判断题
1.数据的逻辑结构与数据元素本身的容和形式无关。（√）
2.一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。（√）
3.数据元素是数据的最小单位。（×）
4.数据的逻辑结构和数据的存储结构是相同的。（×）
5.程序和算法原则上没有区别，所以在讨论数据结构时可以通用。（×）
6.从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。（√）
7.数据的存储结构是数据的逻辑结构的存储映象。（√）
8.数据的物理结构是指数据在计算机实际的存储形式。（√）
9.数据的逻辑结构是依赖于计算机的。（×）
10.算法是对解题方法和步骤的描述。（√）
二、填空题
1.数据有逻辑结构和存储结构两种结构。
2.数据逻辑结构除了集合以外，还包括线性结构、树形结构和图形结构。
3.数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。
4.树形结构和图形结构合称为非线性结构。
5.在树形结构中，除了树根结点以外，其余每个结点只有1个前驱结点。
6.在图形结构中，每个结点的前驱结点数和后继结点数可以任意多个。
7.数据的存储结构又叫物理结构。
8.数据的存储结构形式包括顺序存储、链式存储、索引存储和散列存储。
9.线性结构中的元素之间存在一对一的关系。
10.树形结构中的元素之间存在一对多的关系。
11.图形结构的元素之间存在多对多的关系。
12.数据结构主要研究数据的逻辑结构、存储结构和算法（或运算）3个方面的容。
13.数据结构被定义为（D，R），其中D是数据的有限集合，R是D上的关系有限集合。
14.算法是一个有穷指令的集合。
15.算法效率的度量可以分为事先估算法和事后统计法。
16.一个算法的时间复杂度是算法输入规模的函数。
17.算法的空间复杂度是指该算法所耗费的存储空间，它是该算法求解问题规模的n的函数。
18.若一个算法中的语句频度之和为T(n)=6n+3nlog2n,则算法的时间复杂度为O（nlog2n）。
19.若一个算法的语句频度之和为T(n)=3n+nlog2+n2,则算法的时间复杂度为O（n2）。
20.数据结构是一门研究非数值计算的程序问题中计算机的操作对象，以及它们之间的关系和运算的学
科。
三、选择题
1.数据结构通常是研究数据的（A）及它们之间的相互关系。
A．存储结构和逻辑结构B．存储和抽象C．联系和抽象D．联系与逻辑
2.在逻辑上可以把数据结构分成（C）。
A．动态结构和静态结构B．紧凑结构和非紧凑结构
C．线性结构和非线性结构D．部结构和外部结构。
3.数据在计算机存储表示时，物理地址和逻辑地址相同并且是连续的，称之为（C）。
A．存储结构B．逻辑结构C．顺序存储结构D．链式存储结构
4.非线性结构中的每个结点（D）。
A．无直接前驱结点．B．无直接后继结点．
C．只有一个直接前驱结点和一个直接后继结点D．可能有多个直接前驱结点和多个直接后继结点
5.链式存储结构所占存储空间（A）。
A．分两部分，一部分存放结点的值，另一个部分存放表示结点间关系的指针。
B．只有一部分，存放结点的值。C．只有一部分，存储表示结点间关系的指针。
D．分两部分，一部分存放结点的值，另一部分存放结点所占单元素
6.算法的计算量大小称为算法的（C）。
A．现实性B．难度C．时间复杂性D．效率
7.数据的基本单位（B）。
A．数据结构B．数据元素C．数据项D．文件
8.每个结点只含有一个数据元素，所有存储结点相继存放在一个连续的存储空间里，这种存储结构称为
（A）结构。
A．顺序结构B．链式结构C．索引结构D．散列结构
9.每一个存储结点不仅含有一个数据元素，还包含一组指针，该存储方式是（B）。
A．顺序B．链式C．索引D．散列
10.以下任何两个结点之间都没有逻辑关系的是（D）。
A．图形结构B．线性结构C．树形结构D．集合
11.在数据结构中，与所使用的计算机无关的是（C）。
A．物理结构B．存储结构C．逻辑结构D．逻辑和存储结构
12.下列4种基本逻辑结构中，数据元素之间关系最弱的是（A）。
A．集合B．线性结构C．树形结构D．图形结构
13.与数据元素本身的形式、容、相对位置、个数无关的是数据的（A）。
A．逻辑结构B．存储结构C．逻辑实现D．存储实现
14.每一个存储结点只含有一个数据元素，存储结点存放在连续的存储空间，另外有一组指明结点存储位
置的表，该存储方式是（C）存储方式。
A．顺序B．链式C．索引D．散列
15.算法能正确的实现预定功能的特性称为算法的（A）。
A．正确性B．易读性C．健壮性D．高效性
16.算法在发生非法操作时可以作出相应处理的特性称为算法的（C）。
A．正确性B．易读性C．健壮性D．高效性
17.下列时间复杂度中最坏的是（D）。
A．O（1） B.O（n） C.O( log2n) D.O(n2)
18.下列算法的时间复杂度是（D）。
for(i=0;i for(j=o;i c[i][j]=i+j; A．O（1） B.O（n） C.( log2n) D.O(n2) 19.算法分析的两个主要方面是（A）。 A.空间复杂性和时间复杂性 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 20.计算机算法必须具备输入、输出和（C）。 A.计算方法 B.排序方法 C.解决问题的有限运算步骤 D.程序设计方法 第2章线性表 一、判断题 1.线性表的链式存储结构优于顺序存储。（×） 2.链表的每个结点都恰好包含一个指针域。（×） 3.在线性表的链式存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。（√） 4.顺序存储方式的优点是存储密度大，插入、删除效率高。（×） 5.线性链表的删除算法简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前 移动。（×） 6.顺序表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。（×） 7.线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素。（√） 8.线性表采用顺序存储，必须占用一片连续的存储单元。（√） 9.顺序表结构适宜进行顺序存取，而链表适宜进行随机存取。（×） 10.插入和删除操作是数据结构中是最基本的两种操作，所以这两种操作在数组中也经常使用。（×） 二、填空题 1.顺序表中逻辑上相邻的元素在物理位置上必须相邻。 2.线性表中结点的集合是有限的，结点间的关系是一对一关系。 3.顺序表相对于链表的优点是节省存储和随机存取。 4.链表相对于顺序表的优点是插入、删除方便。 5.当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快速度存取线性表中的 元素时，应采用顺序存储结构。 6.顺序表中访问任意一个结点的时间复杂度均为O（1）。 7.链表相对于顺序表的优点是插入、删除方便；缺点是存储密度小。 8.在双向链表中要删除已知结点*P，其时间复杂度为O（1）。 9.在单向链表中要在已知结点*P之前插入一个新结点，需找到*P的直接前驱结点的地址，其查找的 时间复杂度为O(n)。 10.在单向链表中需知道头指针才能遍历整个链表。 11.线性表中第一个结点没有直接前驱，称为开始结点。 12.在一个长度为n的顺序表中删除第i个元素，要移动n-i 个元素。 13.在一个长度为n的顺序表中，如果要在第i个元素前插入一个元素，要后移n-i+1 个元素。 14.在无头结点的单向链表中，第一个结点的地址存放在头指针中，而其他结点的存储地址存放在 前趋结点的指针域中。 15.线性表的元素总数不确定，且经常需要进行插入和删除操作，应采用链子存储结构。 16.在线性表中的链式存储中，元素之间的逻辑关系是通过指针决定。 17.在双向链表中，每个结点都有两个指针域，它们一个指向其前趋结点，另一个指向其后继结 点。 18.对一个需要经常进行插入和删除操作的线性表，采用链式存储结构为宜。 19.双向链表中，设P是指向其中待删除的结点，则需要执行的操作为p->prior->next=p->next； p->next->prior=p->prior 20.在如图所示的链表中，若在指针P所在的结点之后插入数据域值为a和b的两个结点，则可用语 句S->next->next=p->next和P-> next=S；来实现该操作。 三、选择题 1.在具有n个结点的单向链表中，实现（A）的操作，其算法的时间复杂度都是O(n). A.遍历链表或求链表的第i个结点 B.在地址为P的结点之后插入一个结点 C.删除开始结点 D.删除地址为P的结点的后继结点 2.设a、b、c为3个结点，p、10、20分别代表它们的地址，则如下的存储结构称为（B ）。 p A．循环链表B．单向链表C．双向循环链表D．双向链表 3.单向链表的存储密度（C ）。 A.大于1 B.等于1 C.小于1 D.不能确定 4.已知一个顺序存储的线性表，设每个结点占m个存储单元，若第一个结点的地址为B，则第i个结点 的地址为（A ）。 A.B+(i-1)×m B.B+i×m C.B-i×m D.B+(i+1)×m 5.在有n个结点的顺序表上做插入、删除结点运算的时间复杂度为（ B ）。 A．O（1） B.O（n） C. O(n2) D.O( log2n) 6.设front、rear分别为循环双向链表结点的左指针和右指针，则指针P所指的元素是双循环链表L的尾 元素的条件是（D ）。 A.P= =L B.P->front= =L C.P= =NULL D.P->rear= =L 7.两个指针P和Q，分别指向单向链表的两个元素，P所指元素是Q所指元素前驱的条件是（ B ） A．P->next= =Q->next B.P->next= =Q C.Q->next= =P D.P==Q 8.用链表存储的线性表，其优点是（ C ）。 A．便于随机存取B．花费的存储空间比顺序表少 C．便于插入和删除D．数据元素的物理顺序与逻辑顺序相同 9.在单链表中，增加头结点的目的是（C ）。 A．使单链表至少有一个结点B．标志表中首结点的位置 C．方便运算的实现D．说明该单链表是线性表的链式存储结构 10.下面关于线性表的叙述中，错误的是（D ）关系。 A．顺序表必须占一片地址连续的存储单元B．顺序表可以随机存取任一元素 C．链表不必占用一片地址连续的存储单元D．链表可以随机存取任一元素 11.L是线性表，已知LengthList(L)的值是5，经DelList(L，2)运算后，LengthList(L)的值是（C ）。A．2 B．3 C．4 D．5 12.单向链表的示意图如下： 指向链表Q结点的前驱的指针是（B ）。 A．L B．P C．Q D．R 13.设p为指向单循环链表上某结点的指针，则*p的直接前驱（C ）。 A．找不到B．查找时间复杂度为O（1） C．查找时间复杂度为O（n）D．查找结点的次数约为n 14.等概率情况下，在有n个结点的顺序表上做插入结点运算，需平均移动结点的数目为（8 ）。 A．n B.(n-1)/2 C.n/2 D.(n+1)/2 15.在下列链表中不能从当前结点出发访问到其余各结点的是（C ）。 A.双向链表 B.单循环链表 C.单向链表 D.双向循环链表 16.在顺序表中，只要知道（D ），就可以求出任一结点的存储地址。 A.基地址 B.结点大小 C.向量大小 D.基地址和结点大小 17.在双向链表中做插入运算的时间复杂度为（A ）。 A．O（1） B.O（n） C. O(n2) D.O( log2n) 18.链表不具备的特点是（A ）。 A．随机访问 B.不必事先估计存储空间C. 插入删除时不需要移动元素D.所需空间与线性表成正比 19.以下关于线性表的论述，不正确的为（C ）。 A.线性表中的元素可以是数字、字符、记录等不同类型 B.线性顺序表中包含的元素个数不是任意的 C.线性表中的每个结点都有且仅有一个直接前驱和一个直接后继 D.存在这样的线性表，即表中没有任何结点 20.在（B ）的运算中，使用顺序表比链表好。 A.插入 B.根据序号查找 C.删除 D.根据元素查找 第3章栈 一、判断题 1.栈是运算受限制的线性表。（√） 2.在栈空的情况下，不能作出栈操作，否则产生下溢。（√） 3.栈一定是顺序存储的线性结构。（×） 4.栈的特点是“后进先出”。（√） 5.空栈就是所有元素都为0的栈。（×） 6.在C（或C++）语言中设顺序栈的长度为MAXLEN，则top=MAXLEN时表示栈满。（×） 7.链栈与顺序栈相比，其特点之一是通常不会出现栈满的情况。（√） 8.一个栈的输入序列为：A，B，C，D，可以得到输出序列：C，A，B，D。（×） 9.递归定义就是循环定义。（×） 10.将十进制数转换为二进制数是栈的典型应用之一。（√） 二、填空题 1.在栈结构中，允许插入、删除的一端称为栈顶。 2.在顺序栈中，当栈顶指针top=-1时，表示栈空。 3.在有n个元素的栈中，进栈操作时间复杂度为O（1）。 4.在栈中，出栈操作时间复杂度为O（1）。 5.已知表达式，求它的后缀表达式是栈的典型应用。 6.在一个链栈中，若栈顶指针等于NULL，则表示栈空。 7.向一个栈顶指针为top的链栈插入一个新结点*p时，应执行p->next=top;top=p；操作。 8.顺序栈S存储在数组S->data[0…MAXLEN-1]中，进栈操作时要执行的语句有：S->top++。(或 S->top+1) S->data[S->top]=x 9.链栈LS，指向栈顶元素的指针是LS->next。 10.从一个栈删除元素时，首先取出栈顶元素，然后再移动栈顶指针。 11.由于链栈的操作只在链表的头部进行，所以没有必要设置头结点。 12.已知顺序栈S，在对S进栈操作之前首先要判断栈是否满。 13.已知顺序栈S，在对S出栈操作之前首先要判断栈是否空。 14.若在空间充足，链栈可以不定义栈满运算。 15.链栈LS为空的条件是LS->next=NULL 。 16.链栈LS的栈顶元素是链表的首元素。 17.同一栈的各元素的类型相同。 18.若进栈的次序是A、B、C、D、E，执行3次出栈操作以后，栈顶元素为 B 。 19.A+B/C-D*E的后缀表达式是ABC/+DE*- 。 20.4个元素A、B、C、D顺序进S栈，执行两次Pop(S,x)运算后，x的值是 C 。 三、选择题 1.插入和删除操作只能在一端进行的线性表，称为（C ）。 A．队列B．循环队列C．栈D．循环栈 2.设有编号为1，2。3，4的4辆列车，顺序进入一个栈结构的站台，下列不可能的出站顺序为（D）。 A．1234 B．1243 C．1324 D．1423 3.如果以链表作为栈的存储结构，则出栈操作时（B ）。 A．必须判别栈是否满B．必须判别栈是否为空C．必须判别栈元素类型D．栈可不做任何判别4.元素A、B、C、D依次进栈以后，栈顶元素是（D ） A．A B．B C．C D．D 5.顺序栈存储空间的实现使用（B ）存储元素。 A．链表B．数组C．循环链表D．变量 6.在C（或C++）语言中，一个顺序栈一旦被声明，其占用空间的大小（A ）。 A．已固定B．不固定C．可以改变D．动态变化 7.带头结点的链栈LS的示意图如下，栈顶元素是（ A ）。 A．A B．B C．C D．D 8.链栈与顺序栈相比，有一个比较明显的优点是（ B ）。 A.插入操作更加方便 B.通常不会出现栈满的情况 C.不会出现栈空的情况 D.删除操作更加方便 9.从一个栈顶指针为top的链栈中删除一个结点时，用x保存被删除的结点，应执行下列（d ）命令。 A．x=top;top->next; B.top=top->next;x=top->data C.x=top->data; D.x=top->data;top=top->next 10.在一个栈顶指针为HS的链栈中，将一个S指针所指的结点入栈，应执行下列（ B ）命令。 A.HS->next=S B.S->next=HS->next;HS->next=S; C.S->next=HS->next;HS=S; D.S->next=HS=HS->next 11.4元素按A、B、C、D顺序进S栈，执行两次Pop(S，x)运算后，栈顶元素的值是（ B ）。 A．A B．B C．C D．D 12.元素A、B、C、D依次进栈以后，栈底元素是（A ）。 A．A B．B C．C D．D 13.经过下列栈的运算后，再执行ReadTop(s)的值是（ A ）。 InitStack(s);Push(s，a); Push(s，b);Pob(s); A. a B.b C.1 D.0 14.经过下列栈的运算后，x的值是（B ）。 InitStack(s)（初始化栈）; Push(s，a); Push(s，b); ReadTop(s) ；Pob(s，x); A. a B.b C.1 D.0 15.经过下列栈的运算后，x的值是（ B ）。 InitStack(s)（初始化栈）; Push(s,a); Pob(s，x); Push(s,b); Pob(s，x); A.a B.b C.1 D.0 16.经过下列栈的运算后,SEmpty(s)的值是（ C ）。 InitStack(s)（初始化栈）; Push(s,a); Push(s,b); Pob(s，x); Pob(s，x); A.a B.b C.1 D.0 17.向顺序栈中输入元素时（B ）。 A．先存入元素，后移动栈顶指针B．先移动栈顶指针，后存入元素 C．谁先谁后无关紧要D．同时进行 18.初始化一个空间大小为5的顺序栈S后，S->top的值是（B ）。 A．0 B．-1 C．不再改变D．动态变化 19.设有一个入栈的次序A、B、C、D、E，则栈不可能的输出序列是（ C ）。 A．EDCBA B．DECBA C．DCEAB D．ABCDE 20.设有一个顺序栈S，元素A、B、C、D、E、F依次进栈，如果6个元素出栈的顺序是B、D、C、F、E、 A，则栈的容量至少应是（A ）。 A．3 B．4 C．5 D．6 第4章队列 一、判断题 1.队列是限制在两端进行操作的线性表。（√） 2.判断顺序队列为空的标准是头指针和尾指针都指向同一个结点。（√） 3.在链队列上做出队操作时，会改变front指针的值。（×） 4.在循环队列中，若尾指针rear大于头指针front，其元素个数为rear-front。（√） 5.在单向循环链表中，若头指针为h，那么p所指结点为尾结点的条件是p=h。（×） 6.链队列在一定围不会出现队满的情况。（√） 7.在循环链队列中无溢出现象。（×） 8.栈和队列都是顺序存储的线性结构。（×） 9.在队列中允许删除的一端称为队尾。（×） 10.顺序队和循环队关于队满和队空的判断条件是一样的。（×） 二、填空题 1.在队列中存取数据应遵循的原则是先进先出。 2.队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算线性表。 3.在队列中，允许插入的一端称为队尾。 4.在队列中，允许删除的一端称为队首（或队头）。 5.队列在进行出队操作时，首先要判断队列是否为空。 6.顺序队列在进行入队操作时，首先在判断队列是否为满。 7.顺序队列初始化后，初始化后，front=rear= -1 。 8.解决顺序队列“假溢出”的方法是采用循环队列。 9.循环队列的队指针为front，队尾指针为rear，则队空的条件为front= =rear 。 10.链队列LQ为空时，LQ->front->next= NULL 。 11.设长度为n的链队列用单循环表表示，若只设头指针，则入队操作的时间复杂度为O(n) 。 12.设长度为n的链队列用单循环表表示，若只设尾指针，则入队操作的时间复杂度为O(1) 。 13.在一个链队列中，若队首指针与队尾指针的值相同，则表示该队列为空。 14.设循环队列的头指针front指向队首元素，尾指针rear指向队尾元素后的一个空闲元素，队列的最大 空间为MAXLEN，则队满标志为front= =(rear+1)%MAXLEN 。 15.在一个链队列中，若队首指针为front，队尾指针为rear，则判断队列只有一个结点的条件为front= =rear或front!。 16.向一个循环队列中插入元素时，首先要判断队尾指针，然后再向指针所指的位置写入新的数据。 17.读队首元素的操作不改变或不影响队列元素的个数。 18.设循环队列的容量为40（序号0～39），现经过一系列的入队和出队的运算后，front=11，rear=19， 则循环队列中还有8 个元素。 19.队列Q，经过下列运算：InitQueue(Q)(初始化队列)；InQueue(Q,a)；InQueue(Q,b)；OutQueue(Q,x)； ReadFront(Q,x)；QEmpty(Q)；后的值是8 。 20.队列Q经过InitQueue(Q)(初始化队列)；InQueue(Q,a)；InQueue(Q,b)；ReadFront(Q,x)后，x的值是 a 。 三、选择题 1.队列是限定在（D）进行操作的线性表。 A．中间者 B.队首 C.队尾 D.端点 2.队列中的元素个数是（B）。 A．不变的 B.可变的 C.任意的 D.0 3.同一队列的各元素的类型（A）。 A.必须一致 B.不能一致 C.可以不一致 D.不限制 4.队列是一个（C）线性表结构。 A.不加限制的 B.推广了的 C.加了限制的 D.非 5.当利用大小为n的数组顺序存储一个队列时，该队列的最后一个元素的下标为（B）。 A.n-2 B.n-1 C.n D.n+1 6.一个循环队列一旦说明，其占用空间的大小（A）。 A.已固定 B.可以变动 C.不能固定 D.动态变化 7.循环队列占用的空间（A）。 A.必须连续 B.不必连续 C.不能连续 D.可以不连续 8.存放循环队列元素的数组data有10个元素，则data数组的下标围是（B）。 A.0～10 B.0～9 C.1～9 D.1～10 9.若进队的序列为A、B、C、D，则出队的序列是（C）。 A.B、C、D、A B.A、C、B、D C.A、B、C、D D.C、B、D、A 10.4个元素按A、B、C、D顺序连续进队Q，则队尾元素是（D） A．A B．B C．C D．D 11.4个元素按A、B、C、D顺序连续进队Q，执行一次QutQueue(Q)操作后，队头元素是（B）。 A.A B.B C.C D.D 12.4个元素按A、B、C、D顺序连续进队Q，执行4次QutQueue(Q)操作后，再执行QEmpty(Q)；后的 值是（B）。 A.0 B.1 C.2 D.3 13.队列Q，经过下列运算后，x的值是（B）。InitQueue(Q)(初始化队列)；InQueue(Q,a)；InQueue(Q,b)； OutQueue(Q,x)；ReadFront(Q,x)； A.a B.b C.0 D.1 14.循环队列SQ队满的条件是（B）。 A.SQ->rear= =SQ->front B.(SQ->rear+1)%MAXLEN= =SQ->front C.SQ->rear= =0 D.SQ->front= =0 15.设链栈中结点的结构：data为数据域，next为指针域，且top是栈顶指针，若想在链栈的栈顶插入一 个由指针s所指的结点，则应执行下列（A）操作。 A.s->next=top->next;top->next=s; B.top->next=s; C.s->next=top;top->next; D.s->next=top;top=s; 16.带头结点的链队LQ示意图如下，链队列的队头元素是（A）。 A．A B．B C．C D．D 17.带头结点的链队列LQ示意图如下，指向链队列的队头指针是（C）。 LQ->rear A.LQ->front B.LQ->rear C.LQ->front->next D.LQ->rear->next 18.带头结点的链队列LQ示意图如下,在进行进队的运算时指针LQ->frnot(A). LQ->rear A.始终不改变 B.有时改变 C.进队时改变 D.出队时改变 19.队列Q，经过下列运算后，再执行QEmpty(Q)的值是（C）。 InitQueue(Q)(初始化队列)；InQueue(Q,a)；InQueue(Q,b)；OutQueue(Q,x)；ReadQueue(Q,x)； A.a B.b C.0 D.1 20.若用一个大小为6数组来实现循环队列，且当前front和rear的值分别为3和0，当从队列中删除一个元素，再加入两个元素后，front和rear的值分别为（B）。 A.5和1 B.4和2 C.2和4 D.1和5 第5章串 一、判断题 1.串是n个字母的有限序列。（×） 2.串的数据元素是一个字符。（√） 3.串的长度是指串中不同字符的个数。（×） 4.如果两个串含有相同的字符，则说明它们相等。（×） 5.如果一个串中所有的字母均在另一个串中出现，则说明前者是后者的子串。（×） 6.串的堆分配存储是一种动态存储结构。（√） 7.“DT”是“DATA”的子串。（×） 8.串中任意个字符组成的子序列称为该串的子串。（×） 9.子串的定位运算称为模式匹配。（√） 10.在链串中为了提高存储密度，应该增大结点的大小。（√） 二、填空题 1.由零个或多个字符组成的有限序列称为字符串（或串）。 2.字符串按存储方式可以分为顺序存储、存储和堆分配存储。 3.串的顺序存储结构简称为顺序串。 4.串顺序存储非紧凑格式的缺点是空间利用率低。 5.串顺序存储紧凑格式的缺点是对串的字符处理效率低。 6.串存储的优点是插入、删除方便，缺点是空间利用率。 7.在C或C++语言中，以字符\0 表示串值的终结。 8.空格串的长度等于空格的个数。 9.在空串和空格串中，长度不为0的是空格串。 10.两个串相等是指两个串长度相等，且对应位置的字符都相同。 11.设“S=My Music”，则LenStr(s)= 8 。 12.两个字符串分别为；S1=”Today is”、S2=”30 July，2005”，ConcatStr(S1，S2)的结果是Today is 30 July,2005 。 13.求子串函数SubStr(“Today is 30 July，2005”，13，4)的结果是July 。 14.在串的运算中，EqualStr(aaa,aab)的返回值<0 。 15.在串的运算中，EqualStr(aaa,aaa)的返回值0 。 16.在子串的定位运算中，被匹配的主串称为目标串，子串称为模式。 17.模式匹配成功的起始位置称为有效位移。 18.设S=”abccdcdccbaa”，T=”cdcc”，则第 6 次匹配成功。 19.设S=”c:/mydocument/text1.doc”，T=”mydont”，则字符定位的位置为0 。 20.若n为主串长度，m为子串长度，n>>m，则模式匹配算法最坏情况下的时间复杂度为(n-m+1)*m 。 三、选择题 1.串是和种特殊的线性表，其特殊体现在（B）。 A．可能顺序存储B．数据元素是一个字符C．可以存储D．数据元素可以是多个字符 2.某串的长度小于一常数，则采用（B）存储方式最节省空间。 A．链式B．顺序C．堆结构D．无法确定 3.以下论述正确的是（C）。 A．空串与空格串是相同的B．”tel”是”Teleptone”的子串 C．空串是零个字符的串D．空串的长度等于1 4.以下论述正确的是（B）。 A．空串与空格串是相同的B．”ton”是”Teleptone”的子串 C．空格串是有空格的串D．空串的长度等于1 5.以下论断正确的是（A）。 A．全部由空格组成的串是空格串B．”BEUIJING”是”BEI JING”的子串 C．”something”<”Something”D．”BIT”=”BITE” 6.设有两个串S1和S2，则EqualStr（S1，S2）运算称作（D）。 A．串连接B．模式匹配C．求子串D．串比较 7.串的模式匹配是指（D）。 A．判断两个串是否相等B．对两个串比较大小 C．找某字符在主串中第一次出现的位置D．找某子串在主串中第一次出现的第一个字符位置 8.若字符串”ABCDEFG”采用链式存储，假设每个字符占用1个字节，每个指针占用2个字节。则该字 符串的存储密度为（D）。 A．20% B．40% C．50% D．33.3% 9.若字符串”ABCDEFG”采用链式存储，假设每个指针占用2个字节，若希望存储密度为50%，则每个 结点应存储（A）个字符。 A.2 B.3 C.4 D.5 10.设串S1=”IAM”，S2=”A SDUDENT”，则ConcatStr(S1，S2)=（B）。 A．”I AM” B.”I AM A SDUDENT” C.”IAMASDUDENT” D.”A SDUDENT” 11.设S=””，则LenStr(S)=（A）。 A.0 B.1 C.2 D.3 12.设目标串T=”AABBCCDDE”，模式P=”ABCDE”，则该模式匹配的有效位移为（A）。 A.0 B.1 C.2 D.3 13.设目标串T=”AABBCCDDEEFF”，模式P=”CCD”，则该模式匹配的有效位移为（D）。 A.2 B.3 C.4 D.5 14.设目标串T=”aabaababaabaa”，模式P=”abab”，模式匹配算法的外层循环进行了（D）次。 A.1 B.9 C.4 D.5 15.模式匹配算法在最坏情况下的时间复杂是（D）。 A.O(m) B.O(n) C.O(m+n) D.O(m×n) 16.S=”morning”,执行求子串函数SubSur(S,2,2)后结果为（B）。 A. ”mo” B. ”or” C. ”in” D. ”ng” 17.S1=”good”，S2”morning”，执行串连接函数ConcatStr(S1，S2)后结果为（A）。 A. ”goodmorning” B. ”good morning” C. ”GOODMORNING” D. ”GOODMORNING” 18.S1=”good”, S2=”morning”执行函数SubSur(S2,4,LenStr(S1))后的结果为（B）。 A.”good” B.”ning” C.”go” D.”morn” 19.设串S1=”ABCDEFG”，S2=”PQRST”，则ConcatStr（SubStr(S1，2，LenStr（S2）），SubStr(S1，LenStr （S2），2））的结果串为（D）。 A.BCDEF B.BCDEFG C.BCPQRST D.BCDEFEF 20.若串S=”SOFTWARE”，其子串的数目最多是（C）。 A．35 B.36 C.37 D.38 第6章多维数组和广义表 一、判断题 1.n维多维数可以视为n-1维数组元素组成的线性结构。（√） 2.稀疏矩阵中非零元素的个数远小于矩阵元素的总数。（√） 3.上三角矩阵主对角线以上（不包括主对角线的元素），均为常数C。（×） 4.数组元素可以由若干数据项组成。（√） 5.数组的三元组表存储是对稀疏矩阵的压缩存储。（√） 6.任何矩阵都可以进行压缩存储。（×） 7.广义表是线性表的推广，所以广义表也是线性表。（×） 8.广义表LS=（a0，a1，……a n-1），则a n-1是其表尾。（×） 9.广义表（（a，b）a，b）的表头和表尾是相等的。（√） 10.一个广义表的表尾总是一个广义表。（√） 二、填空题 1.多维数组的顺序存储方式有按行优先顺序存储和按优先顺序存储两种。 2.在多维数组中，数据元素的存放地址可以直接通过地址计算公式算出，所以多维数组是一 种随机存取结构。 3.在n维数组中的每一个元素最多可以有n 个直接前驱。 4.输出二维数组A[n][m]中所有元素值的时间复杂度为n(n*m) 。 5.数组元素a[0…2][0…3] 6.稀疏矩阵的三元组有 3 列。 7.稀疏矩阵的三元组中第1 8.n 9.稀疏矩阵A如图6-19 组表的第 4 项。 10. 11. 12.tail(head((a，b)(c，d)= b 。 13.设广义表（（a，b，c））则将c分离出来的运算是head(tail(tail(head(L)))) 。 14.广义表现出（（a，b）c，d），表尾是(c,d) 。 15.n阶下三角矩阵，因为对角线的上方是同一个常数，需要n(n-1)/2+1 个存储单元。 16.稀疏矩阵中有n个非零元素，则三元组有n 行。 17.广义表LS=（a,（b）,（（c,（d））））的长度是3 。 18.广义表LS=（a,（b）,（（c,（d））））的深度是 4 。 19.广义表LS=（（），L）,则L的深度是∞。 20.广义表LS=（a,（b）,（（c,（d））））的表尾是((b),((c,(d)))) 。 三、选择题 1.在一个m维数组中，（D）恰好有m个直接前驱和m个直接界后继。 A.开始结点 B.总终端结点 C.边界结点 D.部结点 2.对下述矩阵进行压缩存储后，失去随机存取功能的是（D）。 A.对称矩阵 B.三角矩阵 C.三对角矩阵 D.稀疏矩阵 3.在按行优先顺序存储的三元组表中，下述述错误的是（D）。 A.同一行的非零元素，是按列号递增次序存储的 B. 同一列的非零元素，是按行号递增次序存储的 C.三元组表中三元组行号是递增的 D. 三元组表中三元组列号是递增的 4.对稀疏矩阵进行压缩存储是为了（B）。 A.降低运算时间 B.节约存储空间 C.便于矩阵运算 D.便于输入和输出 5.若数组A[0‥m] [0‥n]按列优先顺序存储，则aij的地址为（A）。 A.LOC(a00)+[j×m+i] B. LOC(a00)+[j×n+i] C. LOC(a00)+[(j-1)×n+i-1] D. LOC(a00)+[(j-1)×m+i-1] 6.下列矩阵是一个（B）。 A．对称矩阵B．三角矩阵C．稀疏矩阵D．带状矩阵 1 0 0 0 2 3 0 0 4 5 6 0 7 8 9 10 7.在稀疏矩阵的三元组表示法中，每个三元组表示（D）。 A．矩阵非零元素的值B．矩阵中数据元素的行号和列号 C．矩阵中数据元素的行号、列号和值D．矩阵中非零数据元素的行号、列号和值 8.已知二维数组A[6][10]，每个数组元素占4个存储单元，若按行优先顺序存储存放数组元素a[3][5]的 存储地址是1000，则a[0][0]的存储地址是（B）。 A．872 B．860 C．868 D．864 9.广义表是线性表的推广，它们之间的区别于（A）。 A．能否使用子表B．肥否使用原子项C．是否能为空D．表的长度 10.下列广义表属于线性表的是（B）。 A.E=(a,E) B.E=(a,b,c) C.E=(a,(b,c)) D.E=(a,L);L=() 11.广义表（（a,b）,c,d）的表尾是（D）。 A．a B．d C．(a,b) D．(c,d) 12.广义表A=((x,(a,b)),(x,(a,b),y)),则运算head(head(tail(A)))为（A）。 A．x B．(a,b) C．(x,(a,b)) D．A 13.tail(head((a,b),c,(c,d)))的结果是（B）。 A．b B．(b) C．(a,b) D．(d) 14.若广义表满足head(L)=tail(L),则L的形式是（B）。 A．空表B．若L=（a1,…,a n）,则a1=(a2,…,a n) C．若L=（a1,…,a n）,则(a1=a2,=…a n) D．((a1)( a1)) 15.数组是一个（B）线性表结构。 A.非 B.推广了的 C.加了限制的 D.不加限制的 16.数组A[0：1，0：1，0：1]共有（D）元素。 A.4 B.5 C.6 D.8 17.广义表（（a,b）,c,d）的表头是（C）。 A. a B.d C.(a,b) D.(c,d) 18.广义表A=(a),则表尾为（C）。 A. a B.(()) C.空表 D.(a) 19.以下（C）是稀疏矩阵的压缩存储方法。 A.一维数组 B.二维数组 C.三元数组 D.广义表 20.设广义表D=(a,b,c,d),其深度为（D）。 A.2 B.3 C.4 D.∞ 第7章树和二叉树 一、判断题 1.树结构中每个结点最多只有一个直接前驱。（√） 2.完全二叉树一定是满二叉树。（×） 3.在中序线索二叉树中，右线索若不为空，则一定指向其双亲。（×） 4.一棵二叉树中序遍历序列的最后一个结点，必定是该二叉树前序遍历的最后一个结点。（√） 5.二叉树的前序遍历中，任意一个结点均处于其子女结点的前面。（√） 6.由二叉树的前序遍历序列和中序遍历序列，可以推导出后序遍历的序列。（√） 7.在完全二叉树中，若一个结点没有左孩子，则它必然是叶子结点。（√） 8.在哈夫曼编码中，当两个字符出现的频率相同，其编码也相同，对于这种情况应该做特殊处理。（×） 9.含多于两棵树的森林转换的二叉树，其根结点一定无右孩子。（×） 10.具有n个叶子结点的哈夫曼树共有2n-1个结点。（√） 二、填空题 1.在树中，一个结点所拥有的子树数称为该结点的度。 2.度为零的结点称为叶（或叶子，或终端）结点。 3.树中结点的最大层次称为树的深度（或高度）。 4.对于二叉树来说，第i层上至多有2i-1个结点。 5.深度为h的二叉树至多有2h-1 个结点。 6.由一棵二叉树的前序序列和中序序列可唯一确定这棵二叉树。 7.有20个结点的完全二叉树，编号为10的结点的父结点的编号是 5 。 8.哈夫曼树是带权路径长度的最小的二叉树。 9.由二叉树的后序和中序遍历序列，可以唯一确定一棵二叉树。 10.某二叉树的中序遍历序列为：DEBAC，后序遍历序列为：EBCAD。则前序遍历序列为DABEC 。 11.设一棵二叉树结点的先序遍历序历为：ABDECFGH，中序遍历序历为：DEBAFCHG，则二叉树中叶结 点是：E、F、H 。 12.已知完全二叉树的第8层有8个结点，则其叶结点数是68 。 13.由树转换二叉树时，其根结点无右子树。 14.采用二叉链表存储的n个结点的二叉树，一共有2n 个指针域。 15.采用二叉链表存储的n个结点的二叉树，共有空指针n+1 个。 16.前序为A，B，C且后序C，B，A的二叉树共有 4 种。 17.三个结点可以组成 2 种不同形态的树。 18.将一棵完全二叉树按层次编号，对于任意一个编号为i的结点，其左孩子结点的编号为：2*i 。 19.给定如图7-36所示的二叉树，其前序遍历序列为：ABEFHCG 。 20.给定如图7-37所示的二叉树，其层次遍历序列为：ABCEFGH 。 图7-36 二叉树1 图7-37 二叉树2 1.树最适合用来表示（D）。 A.有序数据元素 B.无序数据元素 C.元素之间无联系的数据 D.元素之间有分支的层次关系 2.前序为A，B，C的二叉树共有（D）种。 A.2 B.3 C.4 D.5 3.根据二叉树的定义，具有3个结点的二叉树有（C）种树型。 A.3 B.4 C.5 D.6 4.在一棵具有五层的满二叉树中，结点的点数为（B）。 A.16 B.31 C.32 D.33 5.具有64个结点的完全二叉树的深度为（C）。 A.5 B.6 C.7 D.8 6.任何一棵二叉树的叶结点在前序、中序、后序遍历序列中的相对次序（A）。 A.不发生改变 B.发生改变 C.不能确定 D.以上都不对 7.A，B为一棵二叉树上的两个结点，在中序遍历时，A在B前的条件是（C）。 A.A和B右方 B.A是B祖先 C.A和B左方 D.A是B子 8.下列4棵树中，（B）不是完全二叉树。 9.如图7-38所示的二叉树，后序遍历的序列是（D）。 A.ABCDEFGHI B.ABDHIECFG 图7-38 C.HDIBEAFCG D.HIDEBFGCA 10.对于图7-39所示的二叉树，其中序序序列为（A）。 A．D C.ABDEHCFG D.ABCDEFGH 图7-39二叉树4 11.DEBAC，则前序遍历序列为（D）。 A.ACBED B.DECAB C.DEABC D.CEDBA 12.具有n(n>1)个结点的完全二叉树中，结点i(2i>n)的左孩子结点是（D）。 A.2i B.2i+1 C.2i-1 D.不存在 13.把一棵树转换为二叉树后，这棵二叉树的形态是（A）。 A.唯一的 B.有多种 C.有多种，但根结点都没有左孩子 D.有多种，但根结点都没有右孩子 14.将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点编号，根结点的编号为1，则编号 为45的结点的左孩子编号为（B）。 A.46 B.47 C.90 D.91 15.将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点编号，根结点的编号为1，则编号 为49的结点的右孩子编号为（B）。 A.98 B.99 C.50 D.100 16.二叉树按某种顺序线索化后，任一结点均有指向其前驱和后继的线索，这种说法（B）。 A.正确 B.错误 C.不确定 D.都有可能 17.下列述正确的是（D）。 A.二叉树是度为为2的有序树 B.二叉树中结点只有一个孩子时无左右之分 C.二叉树必有度为2的结点 D.二叉树中最多只有两棵子树，且有左右子树之分 18.用5个权值{3，2，4，5，1}构造的哈夫曼树的带权路径长度是（B）。 A.32 B.33 C.34 D.15 19.在树结构中，若结点B有4个兄弟，A是B的父亲结点，则A的度为（C）。 A.3 B.4 C.5 D.6 20.二叉树的叶结点个数比度为2的结点的个数（C）。 A.无关 B.相等 C.多一个 D.少一个 第8章图 一、判断题 1.图可以没有边，但不能没有顶点。（√） 2.在无向图中，(v1，v2)与（v2，v1）是两条不同的边。（×） 3.邻接表只能用于有向图的存储。（×） 4.一个图的邻接矩阵表示是唯一的。（√） 5.用邻接矩阵法存储一个图时，所占用的存储空间大小与图中顶点个数无关，而只与图的边数有关。（×） 6.有向图不能进行广度优先遍历。（×） 7.若一个无向图以顶点v1为起点进行深度优先遍历，所得的遍历序列唯一，则可以唯一确定该图。（√） 8.存储无向图的邻接矩阵是对称的，因此只要存储邻接矩阵的上三角（或下三角）部分就可以了。（√） 9.用邻接表法存储图时，占用的存储空间大小只与图中的边数有关，而与结点的个数无关。（×） 10.若从一个无向图中任一顶占出发，进行了一次深度优先遍历，就可以访问图中所有的顶点，则该图一 定是连通的。（√） 二、填空题 1.图常用的存储方式有邻接矩阵和邻接表等。 2.图的遍历有：深度优先搜和广度优先搜等方法。 3.有n条边的无向图邻接矩阵中，1的个数是2n 。 4.有向图的边也称为弧。 5.图的邻接矩阵表示法是表示顶点之间相邻关系的矩阵。 6.有向图G用邻接矩阵存储，其第i行的所有元素之和等于顶点i的出度。 7.n个顶占e条边的图若采用邻接矩阵存储，则空间复杂度为：On2。 8.n个顶占e条边的图若采用邻接表存储，则空间复杂度为：O(n+e) 。 9.设有一稀疏图G，则G采用邻接表存储比较节省空间。 10.设有一稠密图G，则G采用邻接矩阵存储比较节省空间。 11.图的逆邻接表存储结构只适用于有向图。 12.n个顶点的完全无向图有n(n-1)/2 条边。 13.有向图的邻接矩阵表表示适于求顶点的出度。 14.有向图的邻接矩阵表示中，第i列上非0元素的个数为顶点v i的入度。 15.对于具有n个顶点的图，其生成树有且仅有n-1 条边。 16.对有n个顶点，e条弧的有向图，其邻接表表示中，需要n+e 个结点。 17.从图中某一顶点出发，访遍历图中其余顶点，且使每一顶点仅被访问一次，称这一过程为图的遍历。 18.无向图的邻接矩阵一定是对称矩阵。 19.一个连通网的最小生成树是该图所有生成树中权最小的生成树。 20.若要求一个稠密图G的最小生成树，最好用Prim 算法来求解。 三、选择题 1.在一个图中，所有顶点的度数之和等于图的边数的（C）倍。 A.1/2 B.1 C.2 D.4 2.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（B）倍。 A.1/2 B.1 C.2 D.4 3.对于一个具有n个顶点的有向图的边数最多有（B）。 A.n B.n(n-1) C.n(n-1)/2 D.2n 4.在一个具有n个顶点的无向图中，要连通全部顶点至少需要（C）条边。 A.n B.n+1 C.n-1 D.n/2 5.有8个结点的有向完全图有（C）条边。 A.14 B.28 C.56 D.112 6.深度优先遍历类似于二叉树的（A）。 A.先序遍历 B.中序遍历 C.后序遍历 D.层次遍历 7.广度优先遍历类似于二叉树的（D）。 A.先序遍历 B.中序遍历 C.后序遍历 D.层次遍历 8.任何一个无向连通图的最小生成树（A）。 A.只有一棵 B.一棵或多棵 C.一定有多棵 D.可以不存在 9.无向图顶点v的度是关联于该顶点B）的数目。 A.顶点 B.边 C.序号 D.下标 10.有n个顶点的无向图的邻接矩阵是用（B）数组存储。 A.一维 B.n行n列 C.任意行n列 D.n行任意列 11.对于一个具有n个顶点和e条边的无向图，采用邻接表表示，则表头向量大小为（C）。 A.n-1 B.n+1 C.n D.n+e 12.在图的表示法中，表示形式唯一的是（A）。 A.邻接矩阵表示法 B.邻接表表示法 C.逆邻接表表示法 D.邻接表和逆邻接表表示法 13.在一个具有n个顶点e条边的图中，所有顶点的度数之和等于（C）。 C.2n D.2e 图8-23度为3的结点图8-24（15）题图8-25从顶点a出发图8-26优先遍历 14.图8-23中，度为3的结点是（B）。 A.V1 B.V2 C.V3 D.V4 15.图8-24是（A）。 A.连通图 B.强连通图 C.生成树 D.无环图 16.如图8-25所示，从顶点a出发，按深度优先进行遍历，则可能得到的一种顶点序列为（D）。 A.a,b,e,c,d,f B.a,c,f,e,b,d C.a,e,b,c,f,d D.a,e,d,f,c,b 17.如图8-26所示，从顶点a出发，按广度优先进行遍历，则可能得到的一种顶点序列为（A）。 A.a,b,e,c,d,f B.a,b,e,c,f,d C.a,e,b,c,f,d D.a,e,d,f,c,b 18.最小生成树的构造可使用（A）算法。 A.Prim算法 B.卡尔算法 C.哈夫曼算法 D.迪杰斯特拉算法 19.下面关于图的存储结构的叙述中正确的是（A）。 A.用邻接矩阵存储图，占用空间大小只与图中顶点数有关，而与边数无关 B.用邻接矩阵存储图，占用空间大小只与图中边数有关，而与顶点数无关 C.用邻接存储图，占用空间大小只与图中顶点数有关，而与边数无关 D.用邻接存储图，占用空间大小只与图中边数有关，而与顶点数无关 20.连通分量是（C）的极通子图。 A.树 B.图 C.无向图 D.有向图 第9章查找 一、判断题 1.二分查找法要求待查表的关键字值必须有序。（√） 2.对有序表而言采用二分查找总比采用顺序查找法速度快。（×） 3.在二叉排序树中，根结点的值都小于孩子的结点的值。（×） 4.散列存储法的基本思想是由关键字的值的决定数据的存储地址。（√） 5.哈希表是一种将关键字转换为存储地址的存储方法。（√） 6.选择好的哈希函数就可以避免冲突的发生。（×） 7.在有序的顺序表和有序的链表上，均可以采用二分查找来提高查找速度。（×） 8.采用分块查找，既有实现线性表所希望的查找速度，又能适应动态变化的需要。（√） 9.哈希查找的效率主要取决于哈希表构造时选取的哈希函数和处理冲突的方法。（√） 10.在二叉排序树上删除一个结点时，不必移动其他结点，只要将该结点的父结点的相应指针域置空即可。 （×） 二、填空题 1.顺序查找法，表中元素可以任意存放。 2.在分块查找方法中，首先查找索引，然后再查找相应的块。 3.顺序查找、二分查找、分块查找都属于静态查找。 4.静态查找表所含元素个数在查找阶段是固定不变的。 5.对于长度为n的线性表，若进行顺序查找，则时间复杂度为O(n) 。 6.对于长度为n的线性表，若采用二分查找，则时间复杂度为O(log2n) 。 7.理想情况下，在散列表中查找一个元素的时间复杂度为：O(1) 。 8.在关键字序列（7，10，12，18，28，36，45，92）中，用二分查找法查找关键字92，要比较 4 次 才找到。 9.设有100个元素，用二分查找法查找时，最大的比较次数是7 次。 10.对二叉排序树进行查找的方法是用待查的值与根结点的键值进行比较，若比根结点值小，则继续在 左子树中查找。 11.二叉排序树是一种动态查找表。 12.哈希表是按散列存储方式构造的存储结构。 13.哈希法既是一种存储方法，又是一种查找方法。 14.散列表的查找效率主要取决于散列表造表时选取的散列函数和处理冲突的方法。 15.设散列函数H和键值k1，k2，若k1≠k2，而H（k2）H（k2），则称这种现象为冲突。 16.处理冲突的两类主要方法是开放定地址法和拉链法（或链地址法）。 17.散列表（或散列）查找法的平均查找长度与元素个数n无关。 18.在哈希函数H（key）= key%P中，P一般应取质数。 19.在查找过程中有插入元素或删除元素操作的，称为动态查找。 20.各结点左、右子树深度之差的绝对值至多为 1 的二叉树称为平衡二叉树。 三、选择题 1.查找表以（A）为查找结构。 A.集合 B.图 C.树 D.文件 2.顺序查找法适合于存储结构为（B）的线性表。 A.散列存储 B.顺序存储或存储 C.压缩存储 D.索引存储 3.在表长为n的链表中进行线性查找，它的平均查找长度为（B ）。 A.ASL=n B.ASL=(n+1)/2 C.ASL=+1 D.ASL≈log2n 数据结构试题及答案 一、单项选择题 (1)一个算法应该就是（)。 A)程序???B）问题求解步骤得描述 C）要满足五个基本属性??D) A与C (2)算法指得就是（)。 A）计算机程序???B）解决问题得计算方法 C)排序算法???D）解决问题得有限运算序列。 (3)与数据元素本身得形式、内容、相对位置、个数无关得就是数据得(）。 A) 存储结构B) 逻辑结构C）算法D)操作 (4)从逻辑上可以把数据结构分为( ）两大类。 A）动态结构、静态结构??B) 顺序结构、链式结构 C）线性结构、非线性结构???D）初等结构、构造型结构 (5)下列叙述中正确得就是(）。 A)一个逻辑数据结构只能有一种存储结构 B）数据得逻辑结构属于线性结构,存储结构属于非线性结构 C）一个逻辑数据结构可以有多种存储结构,且各种存储结构不影响数据处理得效率 D）一个逻辑数据结构可以有多种存储结构,且各种存储结构影响数据处理得效率 (6)数据得基本单位就是（） ?A) 数据项??B) 数据类型C)数据元素??D)数据变量 (7)下列程序得时间复杂度为（) i=０；s＝０; wｈｉlｅ(s 一、单选题（每题 2 分，共20分） 1. 1.对一个算法的评价，不包括如下（B ）方面的内容。 A．健壮性和可读性B．并行性C．正确性D．时空复杂度 2. 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结 点，则执行( )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3. 3.对线性表，在下列哪种情况下应当采用链表表示？( ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4. 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是 ( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5. 5.AOV网是一种（）。 A．有向图B．无向图C．无向无环图D．有向无环图 6. 6.采用开放定址法处理散列表的冲突时，其平均查找长度（）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同D．高于二分查找 7.7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。 A．值B．函数C．指针D．引用 8.8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具 有相同的（）。 A．行号B．列号C．元素值D．非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为（）。 A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2) 10.10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、二、运算题（每题 6 分，共24分） 1. 1.数据结构是指数据及其相互之间的______________。当结点之间存在M 对N（M：N）的联系时，称这种结构为_____________________。 2. 2.队列的插入操作是在队列的___尾______进行，删除操作是在队列的 ____首______进行。 3. 3.当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则 表示栈满的条件是___top==0___(要超出才为满)_______________。 4. 4.对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度 为_________，在表尾插入元素的时间复杂度为____________。 《数据结构》题库及答案 一、选择题 1．线性表的顺序存储结构是一种 的存储结构，线性表的链式存储结构是一种 的存储结构。 a. 随机存储； b.顺序存储； c. 索引存取； d. HASH 存取 2．一个栈的入栈序列是a,b,c,d,e ，则栈的不可能的输出序列是 。 a. edcba; b. decba; c. dceab; d.abcde 3．一个队列的入队序列是1，2，3，4，则队列的输出序列是 。 a. 4,3,2,1; b. 1,2,3,4; c. 1,4,3,2; d.3,2,4,1 4．在一个单链表中，已知p 结点是q 结点的直接前驱结点，若在p 和q 之间插入结点s ，则执行的操作是 。 a. s->nxet=p->next; p->next=s; b. p->next=s->next; s->next=p; c. q->next=s; s->next=p; d. p->next=s; s->next=q; 5．设有两个串p,q ，求q 在p 中首次出现的位置的运算称作 。 a.联接 b.模式匹配 c.求子串 d.求串长 6．二维数组M 的成员是6个字符（每个字符占一个存储单元）组成的串，行下标i 的范围从0到8，列下标j 的范围从1到10，则存放M 至少需要 个字节。 a. 90 b.180 c.240 d.540 7．在线索二叉树中，结点p 没有左子树的充要条件是 。 a. p->lch==NULL b. p->ltag==1 c. p->ltag==1且p->lch=NULL d. 以上都不对 8．在栈操作中，输入序列为（A ，B ，C ，D ），不可能得到的输出序列为：______ A 、（A ， B ， C ， D ） B 、（D ，C ，B ，A ） C 、（A ，C ，D ，B ） D 、（C ，A ，B ，D ） 9．已知某二叉树的后序序列是dabec ，中序序列是debac ，则它的先序序列是 。 A 、acbed B 、decab C 、deabc D 、cedba 10．设矩阵A 是一个对称矩阵，为了节省存储空间，将其下三角部分（见下图）按行序存放在一维数组B[1..n(n-1)/2]中，对任一上三角部分元素)(j i a ij ，在一维数组B 的存放位置是 。 一．是非题 （正确的打“√”，错误的打“×”。） 1. 数据结构可用三元式表示（D，S，P）。其中：D是数据对象，S是D上的关系， P是对D的基本操作集。× 2. 线性表的链式存储结构具有可直接存取表中任一元素的优点。× 3. 字符串是数据对象特定的线性表。 4. 二叉树是一棵结点的度最大为二的树。× 5．邻接多重表可以用以表示无向图，也可用以表示有向图。× 6．可从任意有向图中得到关于所有顶点的拓扑次序。× 7．一棵无向连通图的生成树是其极大的连通子图。× 8．二叉排序树的查找长度至多为log2ｎ。× 9．对于一棵m阶的B-树.树中每个结点至多有m 个关键字。除根之外的所有非终端结点至少有┌m/2┐个关键字。× 10．对于目前所知的排序方法，快速排序具有最好的平均性能。 11. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。× 12. 二维数组是其数据元素为线性表的线性表。 13. 连通图G的生成树是一个包含G的所有n个顶点和n-1条边的子图。× 14. 折半查找不适用于有序链表的查找。 15. 完全二叉树必定是平衡二叉树。 16. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。 17. 队列是与线性表完全不同的一种数据结构。× 18. 平均查找长度与记录的查找概率有关。 19. 二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所以，二叉树是树的特殊情形。× 20. 算法的时间复杂性越好，可读性就越差；反之，算法的可读性越好，则时间复杂性就越差。× 二．选择题 1. 若对编号为1，2，3的列车车厢依次通过扳道栈进行调度，不能得到 ( e ) 的序列。 a:1,2,3 b:1,3,2 c:2,1,3 d:2,3,1 e:3,1,2 f:3,2,1 2. 递归程序可借助于( b )转化为非递归程序。 a:线性表 b: 栈 c:队列 d:数组 3. 在下列数据结构中( c )具有先进先出（FIFO）特性， ( b )具有先进后出(FILO）特性。 a:线性表 b:栈 c:队列 d:广义表 4. 对字符串s=’data-structure’ 执行操作replace(s,substring(s,6,8),’bas’) 单选题(每题2分，共20分) 1. 1. 对一个算法的评价，不包括如下(B )方面的内容。 A .健壮性和可读性 B .并行性 C .正确性 D .时空复杂度 2.2. 在带有头结点的单链表HL 中，要向表头插入一个由指针 p 指向 的结点，则执行(A )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; 都具有相同的(A )。 A.行号 B .列号 C .元素值 D .非零元素个数 9. 快速排序在最坏情况下的时间复杂度为(D )。 A. O(log 2n) B . O(nlog 2n) C . 0(n) D 10.10. 从二叉搜索树中查找一个元素时，其时间复杂度大致 为 A. O(n) B. O(1) C. O(log 2 n) D. O(n 二、 运算题(每题6分，共24分) 1. 1. 数据结构是指数据及其相互之间的 _________________ 。当结点之 间存在M 对N (M N)的联系时，称这种结构为 __________________________ 。 2. 2. 队列的插入操作是在队列的_ _尾 ________ 行，删除操作是在队 列的 ____ 首 _____ 行。 3. 3. 当用长度为N 的数组顺序存储一个栈时，假定用top==N 表示栈 C. p->next=HL; p=HL; 3. 3. A. C. D. HL=p; p-> next=HL; 对线性表，在下列哪种情况下应当采用链表表示? 经常需要随机地存取元素 B. 表中元素需要占据一片连续的存储空间 一个栈的输入序列为1 2 3， 4. 4. 列的是(C ) A. 2 3 1 C. 3 1 2 AOV 网 是一种(D ) 有向 图 B .无向图 (B ) 经常需要进行插入和删除操作 D.表中元素的个数不变 则下列序列中不可能是栈的输出序 B. 3 2 1 5. 5. 6. .无向无环图 D .有向无环图 采用 开放定址法处理散列表的冲突时，其平均查找长度( B. 高于链接法处理冲突 D .高于二分查找 7. 8. 6. A.低于链接法处理冲突 .与链接法处理冲突相同 7. 参数。 A.值 8. B)。 若需要利用形参直接访问实参时，应将形参变量说明为( B .函数 C .指针 D .引用 在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点 9. .0(n 2) (C )。 2 ) 数据结构习题集含答案 目录 选择题 第一章绪论 1.数据结构这门学科是针对什么问题而产生的（A ） A、针对非数值计算的程序设计问题 B、针对数值计算的程序设计问题 C、数值计算与非数值计算的问题都针对 D、两者都不针对 2.数据结构这门学科的研究内容下面选项最准确的是（D ） A、研究数据对象和数据之间的关系 B、研究数据对象 C、研究数据对象和数据的操作 D、研究数据对象、数据之间的关系和操作 3.某班级的学生成绩表中查得张三同学的各科成绩记录，其中数据结构考了90分，那 么下面关于数据对象、数据元素、数据项描述正确的是（C ） A、某班级的学生成绩表是数据元素，90分是数据项 B、某班级的学生成绩表是数据对象，90分是数据元素 C、某班级的学生成绩表是数据对象，90分是数据项 D、某班级的学生成绩表是数据元素，90分是数据元素 4.*数据结构是指（A ）。 A、数据元素的组织形式 B、数据类型 C、数据存储结构 D、数据定义 5.数据在计算机存储器内表示时，物理地址与逻辑地址不相同，称之为（C ）。 A、存储结构 B、逻辑结构 C、链式存储结构 D、顺序存储结构 6.算法分析的目的是（C ） A、找出数据的合理性 B、研究算法中的输入和输出关系 C、分析算法效率以求改进 D、分析算法的易懂性和文档型性 7.算法分析的主要方法（A ）。 A、空间复杂度和时间复杂度 B、正确性和简明性 C、可读性和文档性 D、数据复杂性和程序复杂性 8.计算机内部处理的基本单元是（B ） A、数据 B、数据元素 C、数据项 D、数据库 9.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储 比顺序存储要（B ）。 A、低 B、高 C、相同 D、不好说 10.算法的时间复杂度取决于（ C ） A 、问题的规模B、待处理数据的初始状态 C、问题的规模和待处理数据的初始状态 D、不好说 11.数据结构既研究数据的逻辑结构，又研究物理结构，这种观点（B ）。 A、正确 B、错误 C、前半句对，后半句错 D、前半句错，后半句对 12.在数据结构中，从逻辑上可以把数据结构分成（ C ） A、动态结构和静态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 13.线性表的顺序存储结构是一种( )的存储结构，线性表的链式存储结构是一种（ A ） 存储结构。 A、随机存取 B、顺序存取 C、索引存取 D、散列存取 14.*下列程序的时间复杂度是（A ） for (i=1; i<=n; ++i){ for (j=1; j<=n; ++j){ c [i][j]=0; 第 1 章绪论 课后习题讲解 1. 填空 ⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。 【解答】集合，线性结构，树结构，图结构 ⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺在一般情况下，一个算法的时间复杂度是（）的函数。 【解答】问题规模 ⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。 数据结构试题? 一、?单选题（每题 2 分，共20分） 1.1.???? 对一个算法的评价，不包括如下（ B ）方面的内容。 A．健壮性和可读性B．并行性 C．正确性 D．时空复杂度 2.2.???? 在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点， 则执行( A )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3.3.???? 对线性表，在下列哪种情况下应当采用链表表示？( B ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4.4.???? 一个栈的输入序列为 1 2 3，则下列序列中不可能是栈的输出序列的是 ( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5.5.???? AOV网是一种（ D ）。 A．有向图 B．无向图 C．无向无环图D．有向无环图 6.6.???? 采用开放定址法处理散列表的冲突时，其平均查找长度（ B ）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同 D．高于二分查找 7.7.???? 若需要利用形参直接访问实参时，应将形参变量说明为（ D ）参数。 A．值 B．函数 C．指针 D．引用 8.8.???? 在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有 相同的（ A ）。 A．行号B．列号 C．元素值 D．非零元素个数 9.9.???? 快速排序在最坏情况下的时间复杂度为（ D ）。 A．O(log 2n) B．O(nlog 2 n) C．O(n) D．O(n2) 10.10. 从二叉搜索树中查找一个元素时，其时间复杂度大致为( C )。 A. O(n) B. O(1) C. O(log 2 n) D. O(n2) 二、运算题（每题 6 分，共24分） 1. 1.?数据结构是指数据及其相互之间的_对应关系(联系)。当结点之间存在M对N（M： N）的联系时，称这种结构为图（或图结构）。 2. 2.队列的插入操作是在队列的__队尾___进行，删除操作是在队列的_对头_进行。 3. 3.??当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈 满的条件是_top==0__。 4. 4.???对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为 一、单项选择题 1 某算法的时间复杂度是O(n 2 ) ，表明该算法（）。 A 问题规模是n2 B 问题规模与n2成正比 C 执行时间等于n2 D 执行时间与n2成正比 2、关于数据结构的描述，不正确的是（）。 A数据结构相同，对应的存储结构也相同。 B数据结构涉及数据的逻辑结构、存储结构和施加其上的操作等三个方面。 C数据结构操作的实现与存储结构有关。 D定义逻辑结构时可不考虑存储结构。 3、按排序策略分来，起泡排序属于（）。 A插入排序B选择排序C交换排序D归并排序 4、利用双向链表作线性表的存储结构的优点是（）。 A便于进行插入和删除的操作 B 提高按关系查找数据元素的速度 C节省空间D便于销毁结构释放空间 5、一个队列的进队顺序为1,2,3,4，则该队列可能的输出序列是（）。 A 1,2,3,4 B 1,3,2,4 C 1,4,2,3 D 4,3,2,1 6、 Dijkstra算法是按（）方法求出图中从某顶点到其余顶点最短路径的。 A按长度递减的顺序求出图的某顶点到其余顶点的最短路径 B按长度递增的顺序求出图的某顶点到其余顶点的最短路径 C通过深度优先遍历求出图中从某顶点到其余顶点的所有路径 D通过广度优先遍历求出图的某顶点到其余顶点的最短路径 7、字符串可定义为n（ n≥ 0）个字符的有限（）。其中，n是字符串的长度，表明字符串中字符的个数。 A集合B数列C序列D聚合 8、在二维数组A[9][10]中，每个数组元素占用 3 个存储单元，从首地址SA 开始按行连续存放。在这种情况下，元素A[8][5]的起始地址为（）。 A SA+141 B SA+144 C SA+222 D SA+255 9、已知广义表为L(A(u,v,(x,y),z),C(m,(),(k,l,n),(())),((())),(e,(f,g),h))，则它的长度是（）。 A2B3C4D5 10.对于具有n(n>1)个顶点的强连通图，其有向边条数至少有_____。 A. n+1 B. n C. n-1 D. n-2 11.一个递归算法必须包括 __________ 。 A. 递归部分 B . 结束条件和递归部分 C. 迭代部分 D. 结束条件和迭代部分 12.从逻辑上看可以把数据结构分为__________两大类。 A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 13、若在长度为n 的顺序表的表尾插入一个新元素的渐进时间复杂度为（）。 A O(n) B O(1) C O(n 2) D O(log 2n) 14.采用顺序搜素方式搜索长度为 n 的线性表时，在等概率情况下，搜索成功时的平均搜索 长度为 __________。 A. n B. n/2 C . (n+1)/2 D. (n-1)/2 15、非空的循环单链表first的链尾结点（由p 所指向）满足（）。 A p->link==NULL; B P==NULL; 第一章概论 一、选择题 1、研究数据结构就是研究（Ｄ）。 Ａ. 数据的逻辑结构?B。数据的存储结构 C。数据的逻辑结构和存储结构?D．数据的逻辑结构、存储结构及其基本操作(研究非数值计算的程序设计问题中，计算机操作对象以及他们之间的关系和操作) 2、算法分析的两个主要方面是（Ａ）。 A．空间复杂度和时间复杂度???B。正确性和简单性 C。可读性和文档性D．数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。(线性结构就是：在非空有限集合中，存在为一个被称为第一个的数据元素和最后一个元素,有除了第一个元素，集合中每一个元素均只有一个前驱，除了最后一个元素有唯一后继)（链表、栈、队列、数组、串） A. 图Ｂ. 树??C．广义表(线性表的推广) D．栈 4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、（ B ）等5个特性。 Ａ．可执行性、可移植性和可扩充性? B. 可执行性、有穷性和确定性 C。确定性、有穷性和稳定性??? D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是( C ）。 for(i=0；i 数据结构试题库及答案 第一章 概论 一、选择题 1 、研究数据结构就是研究（ D ）。 A. 数据的逻辑结构 B. 数据的存储结构 C. 数据的逻辑结构和存储结构 D. 数据的逻辑结构、存储结构及其基本操作 2 、算法分析的两个主要方面是（ A ）。 A. 空间复杂度和时间复杂度 B. 正确性和简单性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 3 、具有线性结构的数据结构是（ D ）。 A. 图 B. 树 C. 广义表 D. 栈 4 、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、 （ B ）等 5 个 特性。 A. 可执行性、可移植性和可扩充性 B. 可执行性、有穷性和确定性 C. 确定性、有穷性和稳定性 D.易读性、稳定性和确定性 5 、下面程序段的时间复杂度是（ C ）。 for(i=0;i 一、判断题： 1、线性表的逻辑顺序与物理顺序总是一致的。( ) 2、线性表的顺序存储表示优于链式存储表示。( ) 3、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。( ) 4、二维数组是其数组元素为线性表的线性表。( ) 5、每种数据结构都应具备三种基本运算：插入、删除和搜索。( ) 6、数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个 方面。( ) 7、线性表中的每个结点最多只有一个前驱和一个后继。（） 8、线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。（） 9、栈和队列逻辑上都是线性表。（） 10、单链表从任何一个结点出发，都能访问到所有结点（） 11、删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。（） 12、快速排序是排序算法中最快的一种。（） 13、多维数组是向量的推广。（） 14、一般树和二叉树的结点数目都可以为0。（） 15、直接选择排序是一种不稳定的排序方法。（） 16、98、对一个堆按层次遍历，不一定能得到一个有序序列。（） 17、在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。（） 18、折半搜索只适用与有序表，包括有序的顺序表和有序的链表。（） 19、堆栈在数据中的存储原则是先进先出。（） 20、队列在数据中的存储原则是后进先出。（） 21、用相邻矩阵表示图所用的存储空间大小与图的边数成正比。（） 22、哈夫曼树一定是满二叉树。（） 23、程序是用计算机语言表述的算法。（） 24、线性表的顺序存储结构是通过数据元素的存储地址直接反映数据元素的逻辑关系。（） 25、用一组地址连续的存储单元存放的元素一定构成线性表。（） 26、堆栈、队列和数组的逻辑结构都是线性表结构。（） 27、给定一组权值，可以唯一构造出一棵哈夫曼树。（） 28、只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。（） 数据结构习题集含答案 目录 目录 (1) 选择题 (2) 第一章绪论 (2) 第二章线性表 (4) 第三章栈和队列 (6) 第四章串 (7) 第五章数组和广义表 (8) 第六章树和二叉树 (8) 第七章图 (11) 第八章查找 (13) 第九章排序 (14) 简答题 (19) 第一章绪论 (19) 第二章线性表 (24) 第三章栈和队列 (26) 第四章串 (28) 第五章数组和广义表 (29) 第六章树和二叉树 (31) 第七章图 (36) 第八章查找 (38) 第九章排序 (39) 编程题 (41) 第一章绪论 (41) 第二章线性表 (41) 第三章栈和队列 (52) 第四章串 (52) 第五章数组和广义表 (52) 第六章树和二叉树 (52) 第七章图 (52) 第八章查找 (52) 第九章排序 (57) 选择题 第一章绪论 1.数据结构这门学科是针对什么问题而产生的？（A ） A、针对非数值计算的程序设计问题 B、针对数值计算的程序设计问题 C、数值计算与非数值计算的问题都针对 D、两者都不针对 2.数据结构这门学科的研究内容下面选项最准确的是（D ） A、研究数据对象和数据之间的关系 B、研究数据对象 C、研究数据对象和数据的操作 D、研究数据对象、数据之间的关系和操作 3.某班级的学生成绩表中查得张三同学的各科成绩记录，其中数据结构考了90 分，那么下面关于数据对象、数据元素、数据项描述正确的是（C ） A、某班级的学生成绩表是数据元素，90分是数据项 B、某班级的学生成绩表是数据对象，90分是数据元素 C、某班级的学生成绩表是数据对象，90分是数据项 D、某班级的学生成绩表是数据元素，90分是数据元素 4.*数据结构是指（A ）。 A、数据元素的组织形式 B、数据类型 C、数据存储结构 D、数据定义 5.数据在计算机存储器内表示时，物理地址与逻辑地址不相同，称之为（C ）。 A、存储结构 B、逻辑结构 C、链式存储结构 D、顺序存储结构 6.算法分析的目的是（C ） A、找出数据的合理性 B、研究算法中的输入和输出关系 好风光好感动1、线性表的逻辑顺序与物理顺序总是一致的。( x ) 2、线性表的顺序存储表示优于链式存储表示。( X ) 3、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。( v ) 4、二维数组是其数组元素为线性表的线性表。( v ) 5、每种数据结构都应具备三种基本运算：插入、删除和搜索。( x ) 6、数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个 方面。( v ) 7、线性表中的每个结点最多只有一个前驱和一个后继。（x ） 8、线性的数据结构可以顺序存储，也可以存储。非线性的数据结构只能存储。（x ） 9、栈和队列逻辑上都是线性表。（v ） 10、单链表从任何一个结点出发，都能访问到所有结点（v ） 11、删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。（x ） 12、快速排序是排序算法中最快的一种。（x ） 13、多维数组是向量的推广。（x） 14、一般树和二叉树的结点数目都可以为0。（v） 15、直接选择排序是一种不稳定的排序方法。（x ） 16、98、对一个堆按层次遍历，不一定能得到一个有序序列。（v ） 17、在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。（x ） 18、折半搜索只适用与有序表，包括有序的顺序表和有序的链表。（x ） 19、堆栈在数据中的存储原则是先进先出。（x ） 20、队列在数据中的存储原则是后进先出。（x ） 21、用相邻矩阵表示图所用的存储空间大小与图的边数成正比。（x ） 22、哈夫曼树一定是满二叉树。（x ） 23、程序是用计算机语言表述的算法。（v） 24、线性表的顺序存储结构是通过数据元素的存储地址直接反映数据元素的逻辑关系。（v ） 25、用一组地址连续的存储单元存放的元素一定构成线性表。（v ） 26、堆栈、队列和数组的逻辑结构都是线性表结构。（v ） 27、给定一组权值，可以唯一构造出一棵哈夫曼树。（x ） 28、只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。（v ） 29、希尔排序在较率上较直接接入排序有较大的改进。但是不稳定的。（v ） 数据结构试题及答案 一、选择题（每小题2分，共20分），每个题的备选答案中，只有一个是正确的，请将答案填写在试题的括号中。 1、对顺序存储的线性表，设其长度为20，在任何位置上插入或删除操作都是 等概率的。插入一个元素时平均要移动表中的（ A ）个元素。 A．10 B．9 C．11 D．12 2、若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。 A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表 3、当利用大小为n的数组顺序存储一个栈时，假定用top==n表示栈空，则向这个栈插入一个元素时，首先应执行（ B ）语句修改top指针。 A．top++ B．top-- C．top = 0 D．top 4、设入栈顺序为A，B，C，D，E，则出栈序列不可能是（ C ）。A．EDCBA B．ABCDE C．ADEBC D．ABDEC 5、已知关键字序列（46, 79, 56, 38, 40, 84），采用快速排序（以位于最左位 置的关键字为基准）得到的第一次划分结果为：（ A ） A．{ 40, 38, 46, 56, 79, 84 } B．{ 38, 46, 79, 56, 40, 84 } C．{ 38, 46, 56, 79, 40, 84 } D．{ 40, 38, 46, 79, 56, 84 } 6、一个有n个顶点和n条边的无向图一定是（ C ）。 A．不连通的 B．连通的 C．有环的 D．无环的 7、在一棵具有n个结点的二叉树的第i层上，最多具有（ B ）个结点。 A．2i B．2i-1 C．2i+1 D．2n 8、对线性表采用折半查找法，该线性表必须（ B ）。 A．采用顺序存储结构B．采用顺序存储结构，且元素按值有序 C．采用链式存储结构 D．采用链式存储结构，且元素按值有序 9、在一棵具有n个结点的完全二叉树中，分支结点的最大编号为（ C ）。A．?(n-1)/2? B．?n/2? C．?n/2? D．?n/2? -1 10、在一个无向图中，所有顶点的度数之和等于所有边数的 ( D ) 倍。 A．3 B．1/2 C．1 D．2 二、填空题（每小题2分，共20分），请将正确的结果，填写在试题的横线上。 1、带头结点的循环链表L为空的条件是。 2、序列A={12, 70, 33, 65, 24, 56}给出对应于序列A的大顶堆HA（以线性数 组表示）。 3、每次使两个相邻的有序表合并成一个有序表，这种排序方法叫做________ 排序。 4、设循环队列Q的队头和队尾指针分别为front和rear，队列的最大容量为MaxSize，且规定判断队空的条件为Q.front = = Q.rear，则队列的长度 为。 5、已知数组A[0..11][0..8]按行优先存储，每个元素占有5个存储单元，且 A[0][0]的地址为1000（十进制），则A[6][7]的地址为________________。 6、已知广义表A=(a，()，(b，(c)))，则其深度为。 7、在一棵二叉树中，假定度为2的结点个数为5个，度为1的结点个数为6 个，则叶子结点数为__ ____个。 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 （一） （二） （三） （四） （五） （六） （七 ）（八 ） （九 ） （十 ） 9 12 15 17 19 21 24 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 （一） （二） （三 ） （四 ） （五 ） （六） （七） （八） （九） （十 ） 27 28 29 31 33 35 37 38 39 40 数据结构试卷(一) 、单选题(每题 栈和队列的共同特点是(A ) 。 A. 只允许在端点处插入和删除元素 B. 都是先进后出 C. 都是先进先出 D. 没有共同点 用链接方式存储的队列，在进行插入运算时 (C ). 头、尾指针都要修改 头、尾指针可能都要修改 (D ) 线性表 2分，共20分) 1. 2. A. C. 3. A. 4. 仅修改头指针 B. 仅修改尾指针 D. 以下数据结构中哪一个是非线性结构? 队列 B.栈 C. 设有一个二维数组 A[m][ n]，假设 个空间，问 676(10)，每个元素占 制表示。 .688 D. 二叉树 A[2][2]存放位置在 (10)存放在什么位置？脚注(10)表示用10进 A[0][0] 存放位置在644(10), A[3][3] .678 C C ） 。 B. A 5.树最适合用来表示( A.有序数据元素 C.元素之间具有分支层次关系的数据 二叉树的第k 层的结点数最多为(D ). k .2 -1 B.2K+1 C.2K-1 若有18个元素的有序表存放在一维数组 6. A 7. 692 D . 696 D. 无序数据元素 乙间无联系的数 据 元素之 f k-1 D. 2 A[19]中，第一个元素放 A[1]中，现进行二 分查找，则查找 A : 3 ]的比较序列的下标依次为 (C ) A. 1 , 2, 3 B. 9 , 5, 2, 3 C. 9 , 5, 3 D. 9 , 4, 2, 3 对n 个记录的文件进行快速排序，所需要的辅助存储空间大致为 D. O 8. A. O (1) B. O (n ) C. O (1og 2n ) D. O (n2) 9. 对于线性表(7, 34, 55, 25, 64, 46, 20, 10)进行散列存储时，若选用 H (K ) =K %9作为散列函数，则散列地址为 1的元素有(D )个， A . 1 B . 2 C . 3 10. 设有6个结点的无向图，该图至少应有 ( A.5 B.6 C.7 D.8 二、填空题(每空 1分，共26分) 1.通常从四个方面评价算法的质量： _ 高效率 _______ 和―强壮性 _______ 。 1. 一个算法的时间复杂度为(n 3 +nlog 2n+14n)/ n 2 ,其数量级表示为 —o(n) ____________________ 。 2. 假定一棵树的广义表表示为 A (C, D (E , F , G , H( I , J )),则树中所含的结点数为 __________ 个，树的深度为 ____________ ，树的度为 ___________ 。 .4 条边才能确保是一个连通图。 正确性 易读性 第一章 1．在数据结构中，从逻辑上可以把数据结构分为（C ） A．动态结构和静态结构 B. 紧凑结构和非紧凑结构 C．线性结构和非线性结构 D. 内部结构和外部结构 ● 2.在数据结构中,与所使用的计算机无关的是( A ) A. 逻辑结构 B. 存储结构 C. 逻辑和存储结构 D. 物理结构 3.下面程序的时间复杂度为____O（mn）_______。 for (int i=1; i<=m; i++) for (int j=1; j<=n; j++ ) S+=i 第二章线性表 ●链表不具备的特点是（A） A 可以随机访问任一结点（顺序） B 插入删除不需要移动元素 C 不必事先估计空间 D 所需空间与其长度成正比 2. 不带头结点的单链表head为空的判定条件为（A ），带头结点的单链表head为空的判定条件为（B ） A head==null B head->next==null C head->next==head D head!=null ●3.在线性表的下列存储结构中，读取元素花费时间最少的是（D） A 单链表 B 双链表 C 循环链表 D 顺序表 ● 4.对于只在表的首、尾两端进行手稿操作的线性表，宜采用的存储结构为(C) A 顺序表 B 用头指针表示的单循环链表 C 用尾指针表示的单循环链表 D 单链表 ● 5.在一个具有n 个结点的有序单链表中插入一个新的结点，并保持链表元素仍然有序， 则操作的时间复杂度为( D ) A O(1) B O(log2n) C O(n2) D O(n) ● 6.在一个长度为n (n>1)的单链表上，设有头和尾两个指针，执行(B)操作与链表的长 度有关 A 删除单链表中第一个元素 B 删除单链表中最后一个元素 C 在第一个元素之前插入一个新元素 D 在最后一个元素之后插入一个新元素 ●7.与单链表相比，双向链表的优点之一是(D) A 插入删除操作更简单 B 可以进行随机访问 C 可以省略表头指针或表尾指针 D 顺序访问相邻结点更容易 ●8.若list是某带头结点的循环链表的头结点指针，则该链表最后那个链结点的指针域 (头结点的地址)中存放的是( B ) A list的地址 B list的内容 C list指的链结点的值 D 链表第一个链结点的地址 ●9.若list1和list2分别为一个单链表与一个双向链表的第一个结点的指针，则( B ) A list2比list1占用更多的存储单元 B list1与list2占用相同的存储单元 C list1和list2应该是相同类型的指针变量 D 双向链表比单链表占用更多的存储单元 10.链表中的每个链结点占用的存储空间不必连续，这句话正确吗？ (不正确) 11. 某线性表采用顺序存储结构，元素长度为4，首地址为100，则下标为12的（第13个）元素的存储地址为148。V 100+4*12=148 11.在顺序表的（最后一个结点之后）插入一个新的数据元素不必移动任何元素。 12.若对线性表进行的操作主要不是插入删除，则该线性表宜采用（顺序）存储结构，若频繁地对线性表进行插入和删除操作，则该线性表宜采用( 链 )存储结构。 数据结构期末考试试题及答案 期末样卷参考答案 一．是非题（每题1分共10分） 1. 线性表的链式存储结构优于顺序存储结构。F 2. 栈和队列也是线性表。如果需要，可对它们中的任一元素进行操作。F 3．字符串是数据对象特定的线性表。T 4．在单链表P指针所指结点之后插入S结点的操作是：P->next= S ; S-> next = P->next; F 5．一个无向图的连通分量是其极大的连通子图。T 6．邻接表可以表示有向图，也可以表示无向图。T 7．假设B是一棵树，B′是对应的二叉树。则B的后根遍历相当于B′的中序遍历。T 8．通常，二叉树的第i层上有2i-1个结点。F 9．对于一棵m阶的B-树,树中每个结点至多有m 个关键字。除根之外的所有非终端结点至少有ém/2ù个关键字。F 10．对于任何待排序序列来说，快速排序均快于起泡排序。F 二．选择题（每题2分共28分） 1．在下列排序方法中，（c ）方法平均时间复杂度为0(nlogn)，最坏情况下时间复杂度为0(n2)；（d ）方法所有情况下时间复杂度均为0(nlogn)。 a. 插入排序 b. 希尔排序 c. 快速排序 d. 堆排序 2. 在有n个结点的二叉树的二叉链表表示中，空指针数为（ b ）。 a.不定 b.n+1 c.n d.n-1 3. 下列二叉树中，（a ）可用于实现符号不等长高效编码。 a.最优二叉树 b.次优查找树 c.二叉平衡树 d.二叉排序树 4. 下列查找方法中，（a ）适用于查找有序单链表。 a.顺序查找 b.二分查找 c.分块查找 d.哈希查找 5. 在顺序表查找中，为避免查找过程中每一步都检测整个表是否查找完毕，可采用（ a ）方法。 a.设置监视哨 b.链表存贮 c.二分查找 d.快速查找 6. 在下列数据结构中，（c ）具有先进先出特性，（b ）具有先进后出特性。 a．线性表b．栈c．队列d．广义表 7．具有m个结点的二叉排序树，其最大深度为（f ），最小深度为（ b ）。 a. log 2 m b. └log2 m ┘+1 c. m/2 d .┌m/2 ┐-1 e. ┌m/2 ┐ f. m 8．已知一组待排序的记录关键字初始排列如下：56,34,58,26,79,52,64,37,28,84,57。 下列选择中（ c ）是快速排序一趟排序的结果。 （ b ）是希尔排序（初始步长为4）一趟排序的结果。（ d ）是基数排序一趟排序的结果。 （ a ）是初始堆（大堆顶）。 a. 84，79，64，37，57，52，58，26，28，34，56。 b. 28，34，57，26，56，52，58，37，79，84，64。 c. 28，34，37，26，52，56，64，79，58，84，57。 d. 52，34，64，84，56，26，37，57，58，28，79。 e. 34，56，26，58，52，64，37，28，79，57，84。 f. 34，56，26，58，52，79，37，64，28，84，57。三．填空题（每题2分共20分） 1．有向图的存储结构有（邻接矩阵）、（邻接表）、（十字链表）等方法。 2．已知某二叉树的先序遍历次序为afbcdeg，中序遍历次序为cedbgfa。 其后序遍历次序为（edcgbfa）。层次遍历次序为（afbcgde）。 3．设有二维数组A 5 x 7 ,每一元素用相邻的4个字节存储，存储器按字节编址。已知A00的存储地址为100。则按行存储时，元素A14的第一个字节的地址是（144）；按列存储时，元素A14的第一个字节的地址是（184）。 4．请在下划线上填入适当的语句，完成以下法算。Status Preordertraverse(Bitree T,Status(*Visit)(Telemtype e)){ //先序非递归遍历二叉树。 Initstack ( S ); Push ( S,T ); While ( !stackempty( S ) ) { While ( gettop( S, p )&& p ) { visit (p->data ) ; push(S, p->lchild ;} Pop ( S , p ); If ( !stackempty(s) ) { pop(S, p) ; push( S, p->rchild ); } } return ok; 四．简答题（每题5分共25分） 1．将图示森林转换为二叉树，并对该二叉树中序全序线索化。 2．已知Hash函数为H（K）=K mod 13 ，散列地址为0 --14， 用二次探测再散列处理冲突，给出关键字（23，34，56，24，75，12，49, 52，36，92，06，55）在散列 地址的分布。 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14数据结构试题库答案
数据结构试题及答案(免费)
《数据结构》题库及答案
数据结构试题(含答案)
数据结构试题及答案(10套最新)
数据结构考试题库含答案
数据结构习题与答案
数据结构试题及答案
算法与数据结构题库与答案
数据结构试题及答案
数据结构试题库与答案
数据结构试题及答案
数据结构考试试题库含答案解析
数据结构试题及答案
数据结构试题及答案.docx
十套数据结构试题与答案
数据结构习题及答案
(完整版)数据结构期末考试试题及答案