第一篇：数据结构练习题及答案
数据结构练习题及答案 第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 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； 来实现该操作。 p ∧ a b s 三、选择题 1.在具有n个结点的单向链表中，实现（A）的操作，其算法的时间复杂度都是O(n).A.遍历链表或求链表的第i个结点 B.在地址为P的结点之后插入一个结点 C.删除开始结点 D.删除地址为P的结点的后继结点 2.设a、b、c为3个结点，p、10、20分别代表它们的地址，则如下的存储结构称为（B）。 p a 10 b 20 c ∧ 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.单向链表的示意图如下： L A B C D ∧ P Q R 指向链表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）。 LS H A B C D ∧ 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）。 LQ->front H A B C D ∧ LQ->rear A．A B．B C．C D．D 17.带头结点的链队列LQ示意图如下，指向链队列的队头指针是（C）。 LQ->front H A B C D ∧ LQ->rear A.LQ->front B.LQ->rear C.LQ->front->next D.LQ->rear->next 18.带头结点的链队列LQ示意图如下,在进行进队的运算时指针LQ->frnot(A).LQ->front H A B C D ∧ 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，……an-1），则an-1是其表尾。 （×）9.广义表（（a，b）a，b）的表头和表尾是相等的。 （√）10.一个广义表的表尾总是一个广义表。 （√）二、填空题 1.多维数组的顺序存储方式有按行优先顺序存储和 按优先顺序存储 两种。 2.在多维数组中，数据元素的存放地址可以直接通过地址计算公式算出，所以多维数组是一 种 随机 存取结构。 3.在n维数组中的每一个元素最多可以有 n 个直接前驱。 4.输出二维数组A[n][m]中所有元素值的时间复杂度为 n(n*m)。0 0 0 0 0 0 11 0 0 0 0 0 0 0 6 0 0 0 3 0 0 7 0 0 5 0 0 0 0 0 0 0 0 9 0 图6-19 稀疏矩阵A 5.数组元素a[0…2][0…3]的实际地址是2000，元素长度是4，则LOC[1，2]= 2024。 6.稀疏矩阵的三元组有 3 列。 7.稀疏矩阵的三元组中第1列存储的是数组中非零元素所在的 行数。 8.n阶对称矩，如果只存储下三角元素，只需要 n(n-1)/2 个存储单元。 9.稀疏矩阵A如图6-19所示，其非零元素存三元组表中，三元组（4，1，5）按列优先顺序存储在三元组表的第 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,…,an）,则a1=(a2,…,an)C．若L=（a1,…,an）,则(a1=a2,=…an)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。 A A B C B C E F G 图7-36 二叉树1 E F G 图7-37 二叉树2 HD HD 三、选择题 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）不是完全二叉树。 A． A B.A C.A D.A B C B C B C B C D E HD G D E F D E D 9.如图7-38所示的二叉树，后序遍历的序列是（D）。 A.ABCDEFGHI A B.ABDHIECFG 图7-38二叉树3 C.HDIBEAFCG B C D.HIDEBFGCA D E F G H I 10.对于图7-39所示的二叉树，其中序序序列为（A）。 A． DBEHAFCG B.DBHEAFCG C.ABDEHCFG D.ABCDEFGH A B C D E F G 图7-39二叉树4 H 11.某二叉树的后序遍历序列为：DABEC，中序遍历序列为：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元素的个数为顶点vi的 入度。 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）。 A.n B.e C.2n D.2e v1 1 a a v2 v3 2 3 b c b c e e v4 v5 4 5 d f d f 图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 4.对线性表进行二分查找时，要求线性表必须（D）。 A.以顺序方式存储 B.以链接方式存储，且结点按关键字有序排序 C.以链接方式存储 D.以顺序方式存储，且结点按关键字有序排序 5.衡量查找算法效率的主要标准是（B）。 A.元素个数 B.平均查找长度 C.所需的存储量 D.算法难易难度 6.如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用（A）查找方法。 A.分块 B.顺序 C.二分 D.散列 7.链表适用于（A）查找。 A.顺序 B.二分 C.随机 D.顺序或二分 8.一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值为82的结点时，（C）次比较后查找成功。 A.2 B.3 C.4 D.5 9.二分查找有序表{4，6，10，12，20，30，50，70，88，100}，若查找表中元素58，则它将依次与表中（B）比较大小，查找结果是失败。 A.30，88，70，50 B.20，70，30，50 C.20，50 D.30，88，50 10.对有14个元素的有序A[1‥14]作二分查找，查找元素A[4]时的被比较元素依次为（C）A.A[1]，A[2]，A[3]，A[4] B.A[1]，A[14]，A[7]，A[4] C.A[7]，A[3]，A[5]，A[4] D.A[7]，A[5]，A[3]，A[4] 11.有一个长度为12的有序表，按二分查找法对其进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为（B）。 A.35/12 B.37/12 C.39/12 D.43/12 12.采用分块查找时，若线性表共有625个元素，查找生个元素等概率相等，假设采用顺序查找来确定结点所在的块时，每块分（C）个结点最佳。 A．6 B．10 C．25 D．625 13.下列（C）不是利用查找表中数据元素的关系进行查找的方法。 A．平衡二叉树 B．有序表的查找 C．散列查找 D．二叉排序树的查找 14.设哈希表长m=14，哈希函数H(key)=key%11。表中已有4个结点：addr(15)=4 addr(38)=5 addr(61)=6 addr(84)=7其余地址为空。如用二次探测再散列处理冲突，关键字为49的结点的地址是（D）。 A．8 B．3 C．5 D．9 15.对包含n个元素的散列表进行查找。平均查找长度为（D）。 A．O(n2)B．O(log2n)C．O(n)D．不直接依赖于n 16.冲突指的是（C）。 A．两个元素具有相同序号 B．两个元素的键值不同 C．不同键值对应相同的存储地址 D．两个元素的键值相同 17.在查找过程中，不做增加、删除或修改的查找称为（A）。 A．静态查找 B．内创造 C．动态查找 D．处查找 18.已知8个元素为{34，76，45，18，26，54，92，65}，按照依次插入结点的方法生成一棵二叉排序树，最后两层上结点的总数为（B）。 A．1 B．2 C．3 D．4 19.不可能生成图9-17所示的二叉排序树的关键字的序列是（A）。 A．4 5 3 1 2 B．4 2 5 3 1 C．4 5 2 1 3 D．4 2 3 1 5 4 2 5 1 3 图9-17二叉树 20.动态查找包括（B）查找。 A.顺序表 B.二叉排序树 C.有序表 D.索引顺序表 第10章 排序 一、判断题 1.如果某种排序算法不稳定，则该排序方法就没有实用价值。 （×）2.希尔排序是不稳定的排序。 （√）3.冒泡排序是不稳定的排序。 （×）4.对n个记录的进行快速排序，所需要的平均时间是O（nlog2n）。 （√）5.堆排序所需的时间与待排序的记录个数无关。 （×）6.当待排序的元素个数很多时，为了交换元素的位置占用较多的时间，这是影响时间复杂度的主要因素。 （√）7.快速排序在任何情况下都比其他排序方法速度快。 （×）8.对快速排序来说，初始序列为正序或反序都是最坏情况。 （√）9.采用归并排序可以实现外排序。 （√）10.采用希尔排序时，若原始关键字的排列杂乱无序，则效率最高。 （√）二、填空题 1.大多数排序算法都有两个基本的操作： 比较 和移动。 2.评价排序算法优劣的主要标准是 时间复杂度 和算法所需的附加空间。 3.根据被处理的数据在计算机中使用不同的存储设备，排序可分为 内排序 和外排序。 4.外排序是指在排序过程中，数据的主要部分存在计算机的 外存 中。 5.对n个关键字进行冒泡排序，其可能的最小比较次数为 n-1 次。 6.在最坏情况下，在第i趟直接插入排序中，要进行 i-1 次关键字的比较。 7.对n个关键字进行冒泡排序，时间复杂度为 O（n2）。 8.快速排序在最坏情况下的时间复杂度是 O（n2）。 9.对于n个记录的集合进行归并排序，所需要的平均时间为 O（nlog2n）。 10.对于n个记录的集合进行归并排序，所需要的附加空间为 O(n)。 11.若原始数据接近无序，则选用 快速排序 最好。 12.在排序前，关键字值相等的不同记录，排序后相对位置保持 不变 的排序方法，称为稳定排序方法。 13.在插入排序和选择排序中，若初始数据基本正序，则选用 插入排序较好。 14.当增量为1时，该趟希尔排序与 直接插入 排序基本一致。 15.第一趟排序后，序列中键值最大的记录交换到最后的排序算法是 冒泡 排序。 16.依次将后面文件每个记录插入到一个前面有序的子文件中的排序方法称为直接插入 排序。 17.在插入排序、选择排序和归并排序中，不稳定的排序为： 选择 排序。 18.在对一组记录（54，38，96，23，15，72，60，45，93）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较 3 次。 19.两个序列分别为：L1={25，57，48，37，92，86，12,33} L2 ={25，37，33，12，48，57，86，92} 用冒泡排序法对L1和 L2进行排序，交换次数较少的是序列： L2。 20.对一组记录（54，35，96，21，12，72，60，44，80）进行直接选择排序时，第4次选择和交换后，未排序记录是 54，72，60，96，80。 三、选择题 1.排序是根据（A）的大小重新安排各元素的顺序。 A.关键字 B.数组 C.元素件 D.结点 2.评价排序算法好坏的标准主要是（D）。 A.执行时间 B.辅助空间 C.算法本身的复杂度 D.执行时间和所需的辅助空间 3.直接插入排序的方法是（B）的排序方法。 A.不稳定 B.稳定 C.外部 D.选择 4.直接插入排序的方法要求被排序的数据（B）存储。 A.必须链表 B.必须顺序 C.顺序或链表 D.可以任意 5.排序方法中，从无序序列中选择关键字最小的记录，将其与无序区（初始为空）的第一个记录交换的排序方法，称为（D）。 A.希尔排序 B.归并排序 C.插入排序 D.选择排序 6.每次把待排序的数据划分为左、右两个区间，其中左区间中元素的值不大于基准元素的值，右区间中元素的值不小于基准元素的值，此种排序方法称为（C）。 A.冒泡排序 B.堆排序 C.快速排序 D.归并排序 7.快速排序在（C）情况下最易发挥其长处。 A.待排序的数据中含有多个相同的关键字B.待排序的数据已基本有序 C.待排序的数据完全无序 D.待排序的数据中最大值与最小值相差悬殊。 8.下述几种排序方法中，要求内存量最大的是（D）。 A.插入排序 B.选择排序 C.快速排序 D.归并排序 9.直接插入排序的方法是从第（B）个元素开始，插入前边适当位置的排序方法。 A.1 B.2 C.3 D.n 10.堆的形状是一棵（C）。 A.二叉排序树 B.满二叉树 C.完全二叉树 D.平衡二叉树 11.内排序是指在排序的整个过程中，全部数据都在计算机的（A）中完成的排序。 A.内存 B.外存 C.内存和外存 D.寄存器 12.快速排序的方法是（A）的排序方法。 A.不稳定 B.稳定 C.外部 D.选择 13.下列排序方法中，关键字比较次数与记录的初始排列次序无关的是（A）。 A.选择排序 B.希尔排序 C.插入排序 D.冒泡排序 14.下述几种排序方法中，平均时间复杂度最小的是（A）。 A.希尔排序 B.插入排序 C.冒泡排序 D.选择排序 15.对有n个记录的表作快速排序，在最坏情况下，算法的时间复杂度是（B）。 A.O(n)B.O(n2)C.O(nlog2n)D.O(n3)16.冒泡排序的方法对n个数据进行排序，第一趟排序共需要比较（C）次。 A.1 B.2 C.n-1 D.n 17.对n个不同的排序码进行冒泡（递增）排序，在下列（B）情况比较的次数最多。 A.从小到大排列好的 B.从大到小排列好的C.元素无序 D.元素基本有序 18.用直接插入排序法对下面的4个序列进行由小到大的排序，元素比较次数最少的是（B）。 A.94，32，40，90，80，46，21，69 B.21，32，46，40，80，69，90，94 C.32，40，21，46，69，94，90，80 D.90，69，80，46，21，32，94，40 19.一组记录的排序码为（25，48，16，35，79，82，23，40），其中含有4个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为（A）。 A.16 25 35 48 23 40 79 82 B.16 25 35 48 79 82 23 40 C.16 25 48 35 79 82 23 40 D.16 25 35 48 79 23 40 82 20.一个数据序列的关键字为（46，79，56，38，40，84），采用快速排序，并以第一个数为基准得到第一次划分的结果为（C）。 A.（38，40，46，56，79，84）B.（40，38，46，79，56，84）C.（40，38，46，56，79，84）D.（40，38，46，79，56，84）第十章文件 1．文件：性质相同的记录的集合。放在外存 主关键字项：能唯一标识记录的数据项或数据项的组合（如学号）文件的操作：检索和维护 文件的存贮结构：顺序、索引、散列、链 文件的组织方式：顺序文件、索引文件、散列文件、多关键字文件 2．顺序文件：记录进入文件的先后顺序存放其逻辑顺序与物理顺序一致的文件。 顺序文件的更新方法： 优点： 3．索引文件：在主文件之外另外建立一张表：逻辑记录与物理记录的对应关系表各主文件一起构成的文件叫索引文件。 4．索引顺序文件：索引表按主关键字有序，主文件按关键字可有序 索引非顺序文件索引表按主关键字有序，主文件按关键字无序 ISAM文件：专为磁盘存取设计的文件组织方式，静态索引结构，由多级主索引、柱面索引、磁道索引和主文件组成。 VSAM文件：虚拟存贮存取方法，用B+树用为动态索引结构，文件由三部分组成：索引集、顺序集、数据集 5．散列文件：用散列存贮方式组织的文件，直接存取文件 桶： 6．多关键字文件：包含有多个次关键字索引的文件 多重表文件：索引方法与链接方法相结合的一种组织方式 倒排文件：与多重表不同的是次关键字索引的结构不同 三、应用题(本大题共5小题，每小题6分，共30分)26.已知广义表的图形表示如图所示,(1)写出该广义表L;(2)分别写出该广义表的深度和长度。 L=((e),(),(a,(b,c,d)),(b,c,d))深度3 长度4 27.已知二叉树的先序序列和中序序列分别为ABDEHCFI和DBHEACIF，(1)画出该二叉树的二叉链表存储表示;(2)写出该二叉树的后序序列。DHEBIFCA A B C D E F H I 28.已知有向图的邻接表如图所示,(1)写出从顶点A出发,对该图进行广度优先搜索遍历的顶点序列：ABDCE(2)画出该有向图的逆邻接表。 29.依次读入给定的整数序列{7，16，4，8，20，9，6，18，5}，完成下列操作： 1)构造一棵二叉排序树,计算在等概率情况下该二叉排序树的平均查找长度ASL;2)若变更序列中元素的排列,可构造出平均查找长度达到最小的二叉排序树。写出满足上述要求的序列中的第一个元素。 4 16 6 8 20 5 9 18 ASL=1/9*（1+2*2+3*3+3*4）=26/9 {9，7，5，4，8，18，6，16，20} 9 7 18 5 8 16 20 4 6 ASL=1/9*（1+2*2+4*3+2*4）=25/9 26.由森林转换得到的对应二叉树如图所示，写出原森林中第三棵树 的前序序列和后序序列。 G H I J 前序序列：GHI J 后序序列：HJIG 27.图的邻接表的类型定义如下所示： #define MaxVertexNum 50 typedef struct node { int adjvex;struct node *next;}EdgeNode;typedef struct { VertexType vertex;EdgeNode *firstedge;}VertexNode;typedef VertexNode AdjList[MaxVertexNum];typedef struct { AdjList adjlist;int n, e;}ALGraph;为便于删除和插入图的顶点的操作，可将邻接表的表头向量定义为链式结构，两种定义的存储表示实例如下图所示，请写出重新定义的类型说明。 题27图 typedef struct link { VertexType vertex;EdgeNode *firstedge;link *down;};typedef struct node { struct node *next;struct link *next1;}EdgeNode;struct Link * ALGraph;28.某类物品的编号由一个大写英文字母及2位数字（0..9）组成，形如E32。运用基数排序对下列物品编号序列进行按字典序的排序，写出每一趟（分配和收集）后的结果。 E13，A37，F43，B32，B47，E12，F37，B12 第一趟：B32,E12,B12,E13,F43,A37,B37,F37 第二趟：E12,B12,E13,B32,A37,F37,F43,B47 第三趟：A37,B12,B32,B47,E12,E13,F37,F43 29.（1）画出对表长为13的有序顺序表进行二分查找的判定树； A[6]=28 A[3]= 16 A[10]= 67 A[1]= 12 A[4]= 21 A[8]=43 A[12]=84 A[2]= 14 A[5]= 24 A[7]= 35 A[9]= 52 A[11]= 71 A[13]= 99（2）已知关键字序列为（12，14，16，21，24，28，35，43，52，67，71，84，99），写出在该序列中二分查找37时所需进行的比较次数。5 29．在栈的输入端元素的输入顺序为1，2，3，4，5，6，进栈过程中可以退栈，则退栈时能否排成序列3，2，5，6，4，1和1，5，4，6，2，3，若能，写出进栈、退栈过程，若不能，简述理由。（用push（x）表示x进栈，pop(x)表示x退栈）push（1）push（2）push（3）pop(3)pop(2)push（4）push（5）POP（5）push（6）pop(6)pop(4)pop(1)30．已知一棵二叉树的中根遍历序列为CBEDFAGH，后根遍历序列为CEFDBHGA，画出该二叉树。 A B G C D H E F 31．给定表（15，11，8，20，14，13），试按元素在表中的顺序将它们依次插入一棵初始时为空的二叉排序树，画出插入完成后的二叉排序树，并判断该二叉排序树是否为平衡二叉排序树，若为非平衡二叉排序树，将它调整为平衡二叉排序树。 11 20 8 14 13 调整方法： 根结点不平衡：根左子树高>右子树高+1：根的中序序列8，11，13，14，15，20中根的前一点14上移为根 14 11 15 8 13 20 根左子树高<右子树高+1：根的中序序列中根的后一点上移为根 33．用冒泡排序法（快速排序）对数据序列（49，38，65，97，76，134，27，49）进行排序，写出排序过程。并说明冒泡排序是否为稳定排序。 冒泡排序法稳定 49，38，65，97，76，134，27，49 49，65，97，76，134，38，49，27 65，97，76，134，49，49，38，27 97，76，134，65，49，49，38，27 97，134，76，65，49，49，38，27 134，97，76，65，49，49，38，27 快速排序不稳定 49，38，65，97，76，134，27，49 49，38，27，49，76，134，97，65，27，38，49，49，65，76，97，134 27，38，49，49，65，76，97，134 29.已知3阶B-树如图所示，(1)画出将关键字6插入之后的B-树； (2)画出在(1)所得树中插入关键字2之后的B-树。5 6 2 1 3 2 8 9 2 3 6 2 1 2 1 5 2 8 9 32．如题32图所示无向图，（1）写出其邻接矩阵； （2）写出三种以顶点A为起点的深度优先搜索顶点序列。 a0 1 1 0 0 0 0 1 b1 0 0 1 1 00 0 c0 0 0 0 0 1 0 0 d0 1 0 1 0 0 0 0 e0 1 0 0 0 1 0 0 f 0 0 1 0 0 0 0 0 g0 0 0 1 1 0 0 0 h10 0 0 0 0 0 0 图6-19 稀疏矩阵A ACFBEGDH ABDGEHCF AHBEGDCF 28.假设通信电文使用的字符集为 {a，b，c，d，e，f，g，h} 各字符在电文中出现的频度分别为：7，26，2，28，13，10，3，11，试为这8个字符设计哈夫曼编码。要求： (1)画出你所构造的哈夫曼树(要求树中左孩子结点的权值不大于右孩子结点的权值)； (2)按左分支为0和右分支为1的规则，分别写出与每个字符对应的编码。 46 54 21 25 26b 28d 10f 11h 12 13e 5 7a 2c 3g A:0101 b:10 c:01000 d:00 e:011 f:000 g:01001 h:001 四、算法阅读题(本大题共4小题，每小题5分，共20分)四、算法阅读题（本大题共4小题，每小题5分，共20分）30.假设以带头结点的单链表表示线性表,阅读下列算法f30,并回答问题:(1)设线性表为(a1, a2 , a3, a4 , a 5, a6, a7), 写出执行算法f30后的线性表； (2)简述算法f30的功能。 void f30(LinkList L){ //L为带头结点单链表的头指针 LinkList p,q;P =L;while(p &&p–>next){q = p–>next;//q指向第一个点 p–>next =q–>next;//p的下一个指向第二个点,删除了第一个点 p =q–>next;//p指向第二个点 free(q);//回收q } }(1)(a2 , a3, a4 , a 5, a6, a7),(2)删除了链表第一个点(不是头结点)31.算法f31的功能是借助栈结构实现整数从10进制到8进制的转换，阅读算法并回答问题： (1)画出n为十进制的1348时算法执行过程中栈的动态变化情况;(2)说明算法中while循环完成的操作。 void f31(int n)//n为非负的十进制整数 { int e;SeqStack S;InitStack(& S);do{ Push(& S,n%8);n =n/8;}while(n);while(!StackEmpty(& S)){e =Pop(& S);printf(〞%ld〞,e);} }(1)4，0，5 2(2)当栈不空时出栈输出n化为8进制数的序列2504 32.已知以二叉链表作二叉树的存储结构，阅读算法f32，并回答问题： (1)设二叉树T如图所示,写出执行f32(T)的返回值;(2)简述算法f32的功能。 int f32(BinTree T){ int m, n;if(!T)return 0;else { m= f32(T–>lchild);n = f 32(T–>rchild);if(m>n)return m +1;else return n+1;} }(1)(2)33.设有向图邻接表定义如下； typedef struct{ VertexNode adjlist[Max VertexNum];int n,e;//图的当前顶点数和弧数 } ALGraph;//邻接表类型 vertex firstedge 其中顶点表结点VertexNode结构为： adjvex next 边表结点EdegNode结构为： 阅读下列算法f33，并回答问题： (1)已知有向图G的邻接表如图所示, 写出算法f33的输出结果;(2)简述算法f33的功能。 void dfs(ALGraph *G,int v){ EdgeNode * p;visited[v]=TRUE;printf(〞%c〞,G–>adjlist[v]·vertex);for(p =G–>adjlist[v])·firstedge;p;p=p–>next)if(!visited[p–>adjvex])dfs(G, p–>adjvex);} void f33(ALGraph *G){ int v,w;for(v=0;v typedef int DataType;typedef struct node { DataType data;struct node * next;} LinkNode, * LinkList;阅读下列算法，并回答问题： (1)已知初始链表如图所示，画出执行f30(head)之后的链表； 题30图(2)简述算法f30的功能。 void f30(LinkList head){ LinkList p,r, s;if(head-> next){ r = head-> next;p = r->next;r-> next = NULL;while(p){ s =p;p = p->next;if(s-> data% 2 = = 0){ s-> next = head-> next;head-> next = s;} else { s-> next = r-> next;r->next = s;r =s;} } } }(1)2 8 5 7(2)将原链中偶数置前，奇数置后 31.假设以二叉链表表示二叉树，其类型定义如下： typedef struct node { DataType data;struct node * lchild, * rchild;//左右孩子指针 } * BinTree;阅读下列算法，并回答问题： (1)已知以T为根指针的二叉树如图所示，写出执行f31(T)之后的返回值； (2)简述算法f31的功能。 int f31(BinTree T){ int d;if(!T)return 0;d = f31(T-> lchild)+ f31(T-> rchild);if(T-> lchild && T-> rchild)return d + 1;else return d;(1)(2)32.设有向图邻接表定义如下： typedef struct { VertexNode adjlist[ MaxVertexNum ];int n，e； ／／图的当前顶点数和弧数 }ALGraph； ／／邻接表类型 其中顶点表结点VertexNode 边表结点EdgeNode结构为： 阅读下列算法，并回答问题： (1)已知某有向图存储在如图所示的邻接 表G中，写出执行f32(＆G)的输出； (2)简述算法f32的功能。 int visited[ MaxNum ];void DFS(ALGraph * G, int i){ EdgeNode * p;visited [ i ] = TRUE;if(G-> adjlist[ i].firstedge = = NULL)printf(“% c “, G-> adjlist[ i].vertex)； else { p = G-> adjlist[ i].firstedge;while(p!= NULL){ if(!visited[p-> adjvex])DFS(G, p-> adjvex);p = p->next;} } } void f32(ALGraph * G){ int i;for(i = 0;i < G->n;i ++)visited [ i ] = FALSE;for(i = 0;i < G->n;i++)if(!visited[i])DFS(G, i);}(1)(2)33.下列算法f33的功能是对记录序列进行双向冒泡排序。算法的基本思想为，先从前往后通过交换将关键字最大的记录移动至后端，然后从后往前通过交换将关键字最小的记录移动至前端，如此反复进行，直至整个序列按关键字递增有序为止。请在空缺处填入合适的内容，使其成为完整的算法。 #define MAXLEN 100 typedef int KeyType;typedef struct { KeyType key;InfoType otherinfo;} NodeType;typedef NodeType SqList[ MAXLEN ];void f33(SqList R, int n){ int i,j,k;NodeType t;i =0;j =n-l;while(i < j){ for(k=i;k 数据结构试卷 （二）一、选择题(24分)1．下面关于线性表的叙述错误的是（）。 (A)线性表采用顺序存储必须占用一片连续的存储空间 (B)线性表采用链式存储不必占用一片连续的存储空间(C)线性表采用链式存储便于插入和删除操作的实现(D)线性表采用顺序存储便于插入和删除操作的实现 2．设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（）个空指针域。 (A)2m-1(B)2m(C)2m+1(D)4m 3．设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（）。 (A)R-F(B)F-R(C)(R-F+M)％M(D)(F-R+M)％M 4．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（）。 (A)BADC(B)BCDA(C)CDAB(D)CBDA 5．设某完全无向图中有n个顶点，则该完全无向图中有（）条边。 (A)n(n-1)/2(B)n(n-1)(C)n 2(D)n2-1 6．设某棵二叉树中有2000个结点，则该二叉树的最小高度为（）。 (A)9(B)10(C)11(D)12 7．设某有向图中有n个顶点，则该有向图对应的邻接表中有（）个表头结点。 (A)n-1(B)n(C)n+1(D)2n-1 8．设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为（）。 (A)2，3，5，8，6(B)3，2，5，8，6(C)3，2，5，6，8(D)2，3，6，5，8 二、填空题(24分)1.1.为了能有效地应用HASH查找技术，必须解决的两个问题是____________________和__________________________。 2.2.下面程序段的功能实现数据x进栈，要求在下划线处填上正确的语句。 typedef struct {int s[100];int top;} sqstack;void push(sqstack &stack,int x){ if(stack.top==m-1)printf(“overflow”); else {____________________;_________________;} } 3.3.中序遍历二叉排序树所得到的序列是___________序列（填有序或无序）。4.4.快速排序的最坏时间复杂度为___________，平均时间复杂度为__________。5.5.设某棵二叉树中度数为0的结点数为N0，度数为1的结点数为N1，则该二叉树中度数为2的结点数为_________；若采用二叉链表作为该二叉树的存储结构，则该二叉树中共有_______个空指针域。 6.6.设某无向图中顶点数和边数分别为n和e，所有顶点的度数之和为d，则e=_______。 7.7.设一组初始记录关键字序列为(55，63，44，38，75，80，31，56)，则利用筛选法建立的初始堆为___________________________。 v1324v213v31428.8.设某无向图G的邻接表为v413，则从顶点V1开始的深度优先遍历序列为___________；广度优先遍历序列为____________。 三、应用题(36分)1． 1． 设一组初始记录关键字序列为(45，80，48，40，22，78)，则分别给出第4趟简单选择排序和第4趟直接插入排序后的结果。 2． 2． 设指针变量p指向双向链表中结点A，指针变量q指向被插入结点B，要求给出在结点A的后面插入结点B的操作序列（设双向链表中结点的两个指针域分别为llink和rlink）。 3． 3． 设一组有序的记录关键字序列为(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求计算出查找关键字62时的比较次数并计算出查找成功时的平均查找长度。 4． 4． 设一棵树T中边的集合为{(A，B)，(A，C)，(A，D)，(B，E)，(C，F)，(C，G)}，要求用孩子兄弟表示法（二叉链表）表示出该树的存储结构并将该树转化成对应的二叉树。5． 5． 设有无向图G（如右图所示），要求给出用普里姆算法构造最小生成树所走过的边的集合。 6． 6． 设有一组初始记录关键字为(45，80，48，40，22，78)，要求构造一棵二叉排序树并给出构造过程。 数据结构试卷 （二）参考答案 一、选择题 1.D 2.B 3.C 4.A 5.A 6.C 7.B 8.C 二、填空题 1.1.构造一个好的HASH函数，确定解决冲突的方法 2.2.stack.top++，stack.s[stack.top]=x 3.3.有序 4.4.O(n2)，O(nlog2n)5.5.N0-1，2N0+N1 6.6.d/2 7.7.(31，38，54，56，75，80，55，63)8.8.(1，3，4，2)，(1，3，2，4) 三、应用题 1.1.(22，40，45，48，80，78)，(40，45，48，80，22，78)2.2.q->llink=p;q->rlink=p->rlink;p->rlink->llink=q;p->rlink=q;3.3.2,ASL=91*1+2*2+3*4+4*2)=25/9 4.4.树的链式存储结构略，二叉树略 5.5.E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)} 6.6.略 数据结构试卷 （三）一、选择题(30分)1．设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，则数据结构A是（）。 (A)线性结构(B)树型结构(C)物理结构(D)图型结构 2．下面程序的时间复杂为（） for（i=1，s=0； i<=n； i++）{t=1；for(j=1；j<=i；j++)t=t*j；s=s+t；}(A)O(n)(B)O(n2)(C)O(n3)(D)O(n4)3．设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（）。 (A)q=p->next；p->data=q->data；p->next=q->next；free(q)；(B)q=p->next；q->data=p->data；p->next=q->next；free(q)； (C)q=p->next；p->next=q->next；free(q)； (D)q=p->next；p->data=q->data；free(q)； 4．设有n个待排序的记录关键字，则在堆排序中需要（）个辅助记录单元。 (A)1(B)n(C)nlog2n(D)n2 5．设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为()。(A)10，15，14，18，20，36，40，21(B)10，15，14，18，20，40，36，21(C)10，15，14，20，18，40，36，2l(D)15，10，14，18，20，36，40，21 6．设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（）。(A)O(1)(B)O(log2n)(C)(D)O(n)7．设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（）。 (A)n，e(B)e，n(C)2n，e(D)n，2e 8.设某强连通图中有n个顶点，则该强连通图中至少有（）条边。 (A)n(n-1)(B)n+1(C)n(D)n(n+1)9．设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（）方法可以达到此目的。 (A)快速排序(B)堆排序(C)归并排序(D)插入排序 10.下列四种排序中（）的空间复杂度最大。 (A)插入排序(B)冒泡排序(C)堆排序(D)归并排序 二、填空殖(48分，其中最后两小题各6分)1.1.数据的物理结构主要包括_____________和______________两种情况。 2.2.设一棵完全二叉树中有500个结点，则该二叉树的深度为__________；若用二叉链表作为该完全二叉树的存储结构，则共有___________个空指针域。 3.3.设输入序列为1、2、3，则经过栈的作用后可以得到___________种不同的输出序列。 4.4.设有向图G用邻接矩阵A[n][n]作为存储结构，则该邻接矩阵中第i行上所有元素之和等于顶点i的________，第i列上所有元素之和等于顶点i的________。 5.5.设哈夫曼树中共有n个结点，则该哈夫曼树中有________个度数为1的结点。6.6.设有向图G中有n个顶点e条有向边，所有的顶点入度数之和为d，则e和d的关系为_________。 7.7.__________遍历二叉排序树中的结点可以得到一个递增的关键字序列（填先序、中序或后序）。 8.8.设查找表中有100个元素，如果用二分法查找方法查找数据元素X，则最多需要比较________次就可以断定数据元素X是否在查找表中。 9.9.不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为____________。 10.10.设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号，则第i个结点的双亲结点编号为____________，右孩子结点的编号为___________。11.11.设一组初始记录关键字为(72，73，71，23，94，16，5)，则以记录关键字72为基准的一趟快速排序结果为___________________________。 12.12.设有向图G中有向边的集合E={<1，2>，<2，3>，<1，4>，<4，2>，<4，3>}，则该图的一种拓扑序列为____________________。 13.13.下列算法实现在顺序散列表中查找值为x的关键字，请在下划线处填上正确的语句。 struct record{int key;int others;};int hashsqsearch(struct record hashtable[ ],int k){ int i,j;j=i=k % p;while(hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____)%m;if(i==j)return(-1);} if(_______________________)return(j);else return(-1);} 14.14.下列算法实现在二叉排序树上查找关键值k，请在下划线处填上正确的语句。 typedef struct node{int key;struct node *lchild;struct node *rchild;}bitree;bitree *bstsearch(bitree *t, int k){ if(t==0)return(0);else while(t!=0)if(t->key==k)_____________;else if(t->key>k)t=t->lchild;else_____________;} 数据结构试卷 （三）参考答案 一、选择题 1.B 2.B 3.A 4.A 5.A 6.B 7.D 8.C 9.B 10.D 第3小题分析：首先用指针变量q指向结点A的后继结点B，然后将结点B的值复制到结点A中，最后删除结点B。 第9小题分析：9快速排序、归并排序和插入排序必须等到整个排序结束后才能够求出最小的10个数，而堆排序只需要在初始堆的基础上再进行10次筛选即可，每次筛选的时间复杂度为O(log2n)。 二、填空题 1.1.顺序存储结构、链式存储结构 2.2.9，501 3.3.5 4.4.出度，入度 5.5.0 6.6.e=d 7.7.中序 8.8.7 9.9.O(1)10.10.i/2，2i+1 11.11.(5，16，71，23，72，94，73)12.12.(1，4，3，2)13.13.j+1，hashtable[j].key==k 14.14.return(t)，t=t->rchild 第8小题分析：二分查找的过程可以用一棵二叉树来描述，该二叉树称为二叉判定树。在有序表上进行二分查找时的查找长度不超过二叉判定树的高度1+log2n。 } 数据结构试卷 （四）一、选择题(30分)1．设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（）。(A)O(n)(B)O(nlog2n)(C)O(1)(D)O(n)2．设一棵二叉树的深度为k，则该二叉树中最多有（）个结点。 (A)2k-1(B)2k(C)2k-1(D)2k-1 3．设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为（）。 (A)n(B)e(C)2n(D)2e 4．在二叉排序树中插入一个结点的时间复杂度为（）。 (A)O(1)(B)O(n)(C)O(log2n)(D)O(n2)5．设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（）条有向边。 (A)n(B)n-1(C)m(D)m-1 6．设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行（）趟的分配和回收才能使得初始关键字序列变成有序序列。 (A)3(B)4(C)5(D)8 7．设用链表作为栈的存储结构则退栈操作（）。 (A)必须判别栈是否为满(B)必须判别栈是否为空 (C)判别栈元素的类型(D)对栈不作任何判别 8．下列四种排序中（）的空间复杂度最大。 (A)快速排序(B)冒泡排序(C)希尔排序(D)堆 9．设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（）。 (A)N0=N1+1(B)N0=Nl+N2(C)N0=N2+1(D)N0=2N1+l 10.设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不超过（）。 (A)log2n+1(B)log2n-1(C)log2n(D)log2(n+1) 二、填空题(42分)1． 1． 设有n个无序的记录关键字，则直接插入排序的时间复杂度为________，快速排序的平均时间复杂度为_________。 2． 2． 设指针变量p指向双向循环链表中的结点X，则删除结点X需要执行的语句序列为_________________________________________________________（设结点中的两个指针域分别为llink和rlink）。3． 3． 根据初始关键字序列(19，22，01，38，10)建立的二叉排序树的高度为____________。4． 4． 深度为k的完全二叉树中最少有____________个结点。5． 5． 设初始记录关键字序列为(K1，K2，…，Kn)，则用筛选法思想建堆必须从第______个元素开始进行筛选。 6． 6． 设哈夫曼树中共有99个结点，则该树中有_________个叶子结点；若采用二叉链表作为存储结构，则该树中有_____个空指针域。 7． 7． 设有一个顺序循环队列中有M个存储单元，则该循环队列中最多能够存储________个队列元素；当前实际存储________________个队列元素（设头指针F指向当前队头元素的前一个位置，尾指针指向当前队尾元素的位置）。 8． 8． 设顺序线性表中有n个数据元素，则第i个位置上插入一个数据元素需要移动表中_______个数据元素；删除第i个位置上的数据元素需要移动表中_______个元素。9． 9． 设一组初始记录关键字序列为(20，18，22，16，30，19)，则以20为中轴的一趟快速排序结果为______________________________。 10．10．设一组初始记录关键字序列为(20，18，22，16，30，19)，则根据这些初始关键字序列建成的初始堆为________________________。 11．11．设某无向图G中有n个顶点，用邻接矩阵A作为该图的存储结构，则顶点i和顶点j互为邻接点的条件是______________________。 12．12．设无向图对应的邻接矩阵为A，则A中第i上非0元素的个数_________第i列上非0元素的个数（填等于，大于或小于）。 13．13．设前序遍历某二叉树的序列为ABCD，中序遍历该二叉树的序列为BADC，则后序遍历该二叉树的序列为_____________。 14．14．设散列函数H(k)=k mod p，解决冲突的方法为链地址法。要求在下列算法划线处填上正确的语句完成在散列表hashtalbe中查找关键字值等于k的结点，成功时返回指向关键字的指针，不成功时返回标志0。 typedef struct node {int key;struct node *next;} lklist;void createlkhash(lklist *hashtable[ ]){ int i,k;lklist *s;for(i=0;i 数据结构试卷 （四）参考答案 一、选择题 1．C 2．D 3．D 4．B 5．C 6．A 7．B 8．A 9．C 10．A 二、填空题 1.1.O(n2)，O(nlog2n)2.2.p>llink->rlink=p->rlink;p->rlink->llink=p->rlink 3.3.3 4.4.2k-1 5.5.n/2 6.6.50，51 7.7.m-1，(R-F+M)%M 8.8.n+1-i，n-i 9.9.(19，18，16，20，30，22)10.10.(16，18，19，20，32，22)11.11.A[i][j]=1 12.12.等于 13.13.BDCA 14.14.hashtable[i]=0，hashtable[k]=s 数据结构试卷 （五）一、选择题(30分) 1．数据的最小单位是（）。 (A)数据项(B)数据类型(C)数据元素(D)数据变量 2．设一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量d=4的一趟希尔排序结束后前4条记录关键字为（）。 (A)40，50，20，95(B)15，40，60，20(C)15，20，40，45(D)45，40，15，20 3．设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（）。 (A)15，25，35，50，20，40，80，85，36，70(B)15，25，35，50，80，20，85，40，70，36(C)15，25，35，50，80，85，20，36，40，70(D)15，25，35，50，80，20，36，40，70，85 4．函数substr(“DATASTRUCTURE”，5，9)的返回值为（）。 (A)“STRUCTURE”(B)“DATA” (C)“ASTRUCTUR”(D)“DATASTRUCTURE” 5．设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（）。 (A)O(log2n)(B)O(1)(C)O(n2)(D)O(n)6．设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为Nl，……，度数为m的结点数为Nm，则N0=（）。 (A)Nl+N2+……+Nm (B)l+N2+2N3+3N4+……+(m-1)Nm(C)N2+2N3+3N4+……+(m-1)Nm(D)2Nl+3N2+……+(m+1)Nm 7．设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（）次。 (A)25(B)10(C)7(D)1 8．设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为（）。 (A)abedfc(B)acfebd(C)aebdfc(D)aedfcb 9．设输入序列是1、2、3、……、n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是（）。 (A)n-i(B)n-1-i(C)n+1-i(D)不能确定 设一组初始记录关键字序列为(45，80，55，40，42，85)，则以第一个记录关键字45为基准而得到一趟快速排序的结果是（）。 (A)40，42，45，55，80，83(B)42，40，45，80，85，88(C)42，40，45，55，80，85(D)42，40，45，85，55，80 二、填空题(共30分)1.1.设有一个顺序共享栈S[0：n-1]，其中第一个栈项指针top1的初值为-1，第二个栈顶指针top2的初值为n，则判断共享栈满的条件是____________________。 2.2.在图的邻接表中用顺序存储结构存储表头结点的优点是____________________。 3.3.设有一个n阶的下三角矩阵A，如果按照行的顺序将下三角矩阵中的元素（包括对角线上元素）存放在n(n+1)个连续的存储单元中，则A[i][j]与A[0][0]之间有_______个数据元素。 4.4.栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把栈称为__________表；队列的插入和删除运算分别在队列的两端进行，先进队列的元素必定先出队列，所以又把队列称为_________表。 5.5.设一棵完全二叉树的顺序存储结构中存储数据元素为ABCDEF，则该二叉树的前序遍历序列为___________，中序遍历序列为___________，后序遍历序列为___________。 6.6.设一棵完全二叉树有128个结点，则该完全二叉树的深度为________，有__________个叶子结点。 7.7.设有向图G的存储结构用邻接矩阵A来表示，则A中第i行中所有非零元素个数之和等于顶点i的________，第i列中所有非零元素个数之和等于顶点i的__________。 8.8.设一组初始记录关键字序列(k1，k2，……，kn)是堆，则对i=1，2，…，n/2而言满足的条件为_______________________________。 9.9.下面程序段的功能是实现冒泡排序算法，请在下划线处填上正确的语句。void bubble(int r[n]){ for(i=1;i<=n-1;i++){ for(exchange=0,j=0;j<_____________;j++) if(r[j]>r[j+1]){temp=r[j+1];______________;r[j]=temp;exchange=1;} if(exchange==0)return； } } 10.10.下面程序段的功能是实现二分查找算法，请在下划线处填上正确的语句。struct record{int key;int others;};int bisearch(struct record r[ ], int k){ int low=0,mid,high=n-1; while(low<=high){ ________________________________; if(r[mid].key==k)return(mid+1);else if(____________)high=mid-1;else low=mid+1; } return(0);} 三、应用题(24分) 1.1.设某棵二叉树的中序遍历序列为DBEAC，前序遍历序列为ABDEC，要求给出该二叉树的的后序遍历序列。2.2.设无向图G（如右图所示），给出该图的最小生成树上边的集合并计算最小生成树各边上的权值之和。 3.3.设一组初始记录关键字序列为(15，17，18，22，35，51，60)，要求计算出成功查找时的平均查找长度。 4.4.设散列表的长度为8，散列函数H(k)=k mod 7，初始记录关键字序列为(25，31，8，27，13，68)，要求分别计算出用线性探测法和链地址法作为解决冲突方法的平均查找长度。 数据结构试卷 （五）参考答案 一、选择题 1．A 2．B 3．A 4．A 5．D 6．B 7．B 8．B 9．C 10．C 二、填空题 1.1.top1+1=top2 2.2.可以随机访问到任一个顶点的简单链表 3.3.i(i+1)/2+j-1 4.4.FILO，FIFO 5.5.ABDECF，DBEAFC，DEBFCA 6.6.8，64 7.7.出度，入度 8.8.ki<=k2i && ki<=k2i+1 9.9.n-i，r[j+1]=r[j] 10.10.mid=(low+high)/2，r[mid].key>k 三、应用题 1.1.DEBCA 2.2.E={(1,5),(5,2),(5,3),(3,4)},W=10 3.3.ASL=(1*1+2*2+3*4)/7=17/7 4.4.ASL1=7/6，ASL2=4/3 数据结构试卷 （六）一、选择题(30分)1． 设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权路径长度之和为（）。 (A)20(B)30(C)40(D)45 2．执行一趟快速排序能够得到的序列是（）。 (A)[41，12，34，45，27] 55 [72，63](B)[45，34，12，41] 55 [72，63，27](C)[63，12，34，45，27] 55 [41，72](D)[12，27，45，41] 55 [34，63，72] 3．设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（）。(A)head==0(B)head->next==0(C)head->next==head(D)head!=0 4．时间复杂度不受数据初始状态影响而恒为O(nlog2n)的是（）。 (A)堆排序(B)冒泡排序(C)希尔排序(D)快速排序 5．设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（）。 (A)空或只有一个结点(B)高度等于其结点数 (C)任一结点无左孩子(D)任一结点无右孩子 6．一趟排序结束后不一定能够选出一个元素放在其最终位置上的是（）。 (A)堆排序(B)冒泡排序(C)快速排序(D)希尔排序 7．设某棵三叉树中有40个结点，则该三叉树的最小高度为（）。 (A)3(B)4(C)5(D)6 8．顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为（）。 21/2(A)O(n)(B)O(n)(C)O(n)(D)O(1og2n)9．二路归并排序的时间复杂度为（）。(A)O(n)(B)O(n)(C)O(nlog2n)(D)O(1og2n)10.深度为k的完全二叉树中最少有（）个结点。 (A)2k-1-1(B)2k-1(C)2k-1+1(D)2k-1 11.设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为（）。 (A)front->next=s；front=s；(B)s->next=rear；rear=s； (C)rear->next=s；rear=s；(D)s->next=front；front=s； 12.设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为（）。(A)O(n+e)(B)O(n)(C)O(ne)(D)O(n)13.设某哈夫曼树中有199个结点，则该哈夫曼树中有（）个叶子结点。 (A)99(B)100(C)101(D)102 14.设二叉排序树上有n个结点，则在二叉排序树上查找结点的平均时间复杂度为（）。(A)O(n)(B)O(n)(C)O(nlog2n)(D)O(1og2n)15.设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（）。 (A)第i行非0元素的个数之和(B)第i列非0元素的个数之和 (C)第i行0元素的个数之和(D)第i列0元素的个数之和 二、判断题(20分)1．调用一次深度优先遍历可以访问到图中的所有顶点。（） 2．分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。（）3．冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。（）4．满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。（） 5．设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。（）6．层次遍历初始堆可以得到一个有序的序列。（） 7．设一棵树T可以转化成二叉树BT，则二叉树BT中一定没有右子树。（）8．线性表的顺序存储结构比链式存储结构更好。（） 9．中序遍历二叉排序树可以得到一个有序的序列。（）10.快速排序是排序算法中平均性能最好的一种排序。（） 三、填空题(30分)1．for(i=1，t=1，s=0；i<=n；i++){t=t*i；s=s+t；}的时间复杂度为_________。 2．设指针变量p指向单链表中结点A，指针变量s指向被插入的新结点X，则进行插入操作的语句序列为__________________________（设结点的指针域为next）。3．设有向图G的二元组形式表示为G =（D，R），D={1，2，3，4，5}，R={r}，r={<1,2>，<2,4>，<4,5>，<1,3>，<3,2>，<3,5>}，则给出该图的一种拓扑排序序列__________。4．设无向图G中有n个顶点，则该无向图中每个顶点的度数最多是_________。5．设二叉树中度数为0的结点数为50，度数为1的结点数为30，则该二叉树中总共有_______个结点数。 6．设F和R分别表示顺序循环队列的头指针和尾指针，则判断该循环队列为空的条件为_____________________。 7．设二叉树中结点的两个指针域分别为lchild和rchild，则判断指针变量p所指向的结点为叶子结点的条件是_____________________________________________。8．简单选择排序和直接插入排序算法的平均时间复杂度为___________。 9．快速排序算法的空间复杂度平均情况下为__________，最坏的情况下为__________。10.散列表中解决冲突的两种方法是_____________和_____________。 数据结构试卷 （六）参考答案 一、选择题 1．D 2．A 3．A 4．A 5．D 6．D 7．B 8．A 9．C 10．B 11．C 12．A 13．B 14．D 15．B 二、判断题 1．错 2．对 3．对 4．对 5．错 6．错 7．对 8．错 9．对 10．对 三、填空题 1.1.O(n)2.2.s->next=p->next;p->next=s 3.3.(1，3，2，4，5)4.4.n-1 5.5.129 6.6.F==R 7.7.p->lchild==0&&p->rchild==0 8.8.O(n2)9.9.O(nlog2n)，O(n)10.10.开放定址法，链地址法 数据结构试卷 （七）一、选择题(30分)1．设某无向图有n个顶点，则该无向图的邻接表中有（）个表头结点。 (A)2n(B)n(C)n/2(D)n(n-1)2．设无向图G中有n个顶点，则该无向图的最小生成树上有（）条边。 (A)n(B)n-1(C)2n(D)2n-1 3．设一组初始记录关键字序列为(60，80，55，40，42，85)，则以第一个关键字45为基准而得到的一趟快速排序结果是（）。 (A)40，42，60，55，80，85(B)42，45，55，60，85，80(C)42，40，55，60，80，85(D)42，40，60，85，55，80 4．（）二叉排序树可以得到一个从小到大的有序序列。 (A)先序遍历(B)中序遍历(C)后序遍历(D)层次遍历 5．设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为（）。 (A)2i+1(B)2i(C)i/2(D)2i-1 6．程序段s=i=0；do {i=i+1； s=s+i；}while(i<=n)；的时间复杂度为（）。(A)O(n)(B)O(nlog2n)(C)O(n)(D)O(n/2)7．设带有头结点的单向循环链表的头指针变量为head，则其判空条件是（）。 (A)head==0(B)head->next==0(C)head->next==head(D)head!=0 8．设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（）。 (A)20(B)256(C)512(D)1024 9．设一组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，134),则利用二分法查找关键字90需要比较的关键字个数为（）。 (A)1(B)2(C)3(D)4 10.设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（）。 (A)top=top+1;(B)top=top-1;(C)top->next=top;(D)top=top->next; 三、填空题(30分)1.1.设指针变量p指向双向链表中的结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为_________=p；s->right=p->right；__________=s； p->right->left=s；（设结点中的两个指针域分别为left和right）。2.2.设完全有向图中有n个顶点，则该完全有向图中共有________条有向条；设完全无向图中有n个顶点，则该完全无向图中共有________条无向边。 3.3.设关键字序列为(Kl，K2，…，Kn)，则用筛选法建初始堆必须从第______个元素开始进行筛选。 4.4.解决散列表冲突的两种方法是________________和__________________。 5.5.设一棵三叉树中有50个度数为0的结点，21个度数为2的结点，则该二叉树中度数为3的结点数有______个。 6.6.高度为h的完全二叉树中最少有________个结点，最多有________个结点。7.7.设有一组初始关键字序列为(24，35，12，27，18，26)，则第3趟直接插入排序结束后的结果的是__________________________________。 8.8.设有一组初始关键字序列为(24，35，12，27，18，26)，则第3趟简单选择排序结束后的结果的是__________________________________。 9.9.设一棵二叉树的前序序列为ABC，则有______________种不同的二叉树可以得到这种序列。 10.10.下面程序段的功能是实现一趟快速排序，请在下划线处填上正确的语句。 struct record {int key;datatype others;};void quickpass(struct record r[], int s, int t, int &i){ int j=t;struct record x=r[s];i=s; while(i while(i while(____________________)i=i+1;if(i } _________________;} 数据结构试卷 （七）一、选择题 1．B 2．B 3．C 4．B 6．A 7．C 8．C 9．B 三、填空题 1.1.s->left=p，p->right 2.2.n(n-1)，n(n-1)/2 3.3.n/2 4.4.开放定址法，链地址法 5.5.14 6.6.2h-1，2h-1 7.7.(12，24，35，27，18，26)8.8.(12，18，24，27，35，26)9.9.5 10.10.i 5．B 10．D 数据结构试卷 （八）一、选择题(30分)1.1.字符串的长度是指（）。 (A)串中不同字符的个数(B)串中不同字母的个数 (C)串中所含字符的个数(D)串中不同数字的个数 2.2.建立一个长度为n的有序单链表的时间复杂度为（） (A)O(n)(B)O(1)(C)O(n2)(D)O(log2n)3.3.两个字符串相等的充要条件是（）。 (A)两个字符串的长度相等(B)两个字符串中对应位置上的字符相等 (C)同时具备(A)和(B)两个条件(D)以上答案都不对 4.4.设某散列表的长度为100，散列函数H(k)=k % P，则P通常情况下最好选择（）。 (A)99(B)97(C)91(D)93 5.5.在二叉排序树中插入一个关键字值的平均时间复杂度为（）。(A)O(n)(B)O(1og2n)(C)O(nlog2n)(D)O(n)6.6.设一个顺序有序表A[1:14]中有14个元素，则采用二分法查找元素A[4]的过程中比较元素的顺序为()。 (A)A[1]，A[2]，A[3]，A[4](B)A[1]，A[14]，A[7]，A[4](C)A[7]，A[3]，A[5]，A[4](D)A[7]，A[5]，A[3]，A[4] 7.7.设一棵完全二叉树中有65个结点，则该完全二叉树的深度为（）。 (A)8(B)7(C)6(D)5 8.8.设一棵三叉树中有2个度数为1的结点，2个度数为2的结点，2个度数为3的结点，则该三叉链权中有（）个度数为0的结点。 (A)5(B)6(C)7(D)8 9.9.设无向图G中的边的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为（）。 (A)aedfcb(B)acfebd(C)aebcfd(D)aedfbc 10.10.队列是一种（）的线性表。 (A)先进先出(B)先进后出(C)只能插入(D)只能删除 三、填空题(30分)1． 1． 设一组初始记录关键字序列为(49，38，65，97，76，13，27，50)，则以d=4为增量的一趟希尔排序结束后的结果为_____________________________。 2． 2． 下面程序段的功能是实现在二叉排序树中插入一个新结点，请在下划线处填上正确的内容。 typedef struct node{int data;struct node *lchild;struct node *rchild;}bitree;void bstinsert(bitree *&t,int k){ if(t==0){____________________________;t->data=k;t->lchild=t->rchild=0;} else if(t->data>k)bstinsert(t->lchild,k);else__________________________;} 3． 3． 设指针变量p指向单链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X需要执行的语句序列：s->next=p->next;_________________。4． 4． 设指针变量head指向双向链表中的头结点，指针变量p指向双向链表中的第一个结点，则指针变量p和指针变量head之间的关系是p=_________和head=__________（设结点中的两个指针域分别为llink和rlink）。 5． 5． 设某棵二叉树的中序遍历序列为ABCD，后序遍历序列为BADC，则其前序遍历序列为__________。 6． 6． 完全二叉树中第5层上最少有__________个结点，最多有_________个结点。7． 7． 设有向图中不存在有向边 8． 8． 设一组初始记录关键字序列为(49，38，65，97，76，13，27，50)，则第4趟直接选择排序结束后的结果为_____________________________。 9． 9． 设连通图G中有n个顶点e条边，则对应的最小生成树上有___________条边。10． 10． 设有一组初始记录关键字序列为(50，16，23，68，94，70，73)，则将它们调整成初始堆只需把16与___________相互交换即可。 数据结构试卷 （八）参考答案 一、选择题 1．C 2．C 3．C 4．B 5．B 6．C 7．B 8．C 9．A 10．A 三、填空题 1.1.(49，13，27，50，76，38，65，97)2.2.t=(bitree *)malloc(sizeof(bitree))，bstinsert(t->rchild,k)3.3.p->next=s 4.4.head->rlink，p->llink 5.5.CABD 6.6.1，16 7.7.0 8.8.(13，27，38，50，76，49，65，97)9.9.n-1 10.10.50 图 1.填空题 ⑴ 设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。【解答】0，n(n-1)/2，0，n(n-1)【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。 ⑵ 任何连通图的连通分量只有一个，即是（）。【解答】其自身 ⑶ 图的存储结构主要有两种，分别是（）和（）。【解答】邻接矩阵，邻接表 【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。⑷ 已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。【解答】Ｏ(n+e)【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。 ⑸ 已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。【解答】求第j列的所有元素之和 ⑹ 有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。【解答】出度 ⑺ 图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。【解答】前序，栈，层序，队列 ⑻ 对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal算法求最小生成树的时间复杂度为（）。【解答】Ｏ(n2)，Ｏ(elog2e)【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。 ⑼ 如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。【解答】回路 ⑽ 在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点vi, vj, vk的相对次序为（）。【解答】vi, vj, vk 【分析】对由顶点vi, vj, vk组成的图进行拓扑排序。 2.选择题 ⑴ 在一个无向图中，所有顶点的度数之和等于所有边数的（）倍。A 1/2 B 1 C 2 D 4 【解答】C 【分析】设无向图中含有n个顶点e条边，则。 ⑵ n个顶点的强连通图至少有（）条边，其形状是（）。A n B n+1 C n-1 D n×(n-1)E 无回路 F 有回路 G 环状 H 树状 【解答】A，G ⑶ 含n 个顶点的连通图中的任意一条简单路径，其长度不可能超过（）。A 1 B n/2 C n-1 D n 【解答】C 【分析】若超过n-1，则路径中必存在重复的顶点。 ⑷ 对于一个具有n个顶点的无向图，若采用邻接矩阵存储，则该矩阵的大小是（）。A n B(n-1)2 C n-1 D n2 【解答】D ⑸ 图的生成树（），n个顶点的生成树有（）条边。A 唯一 B 不唯一 C 唯一性不能确定 D n E n +1 F n-1 【解答】C，F ⑹ 设无向图G=(V, E)和G' =(V', E')，如果G' 是G的生成树，则下面的说法中错误的是（A G' 为 G的子图 B G' 为 G的连通分量 C G' 为G的极小连通子图且V = V' D G' 是G的一个无环子图 【解答】B）。 【分析】连通分量是无向图的极大连通子图，其中极大的含义是将依附于连通分量中顶点的所有边都加上，所以，连通分量中可能存在回路。 ⑺ G是一个非连通无向图，共有28条边，则该图至少有（）个顶点。A 6 B 7 C 8 D 9 【解答】D 【分析】n个顶点的无向图中，边数e≤n(n-1)/2，将e=28代入，有n≥8，现已知无向图非连通，则n=9。 ⑻ 最小生成树指的是（）。A 由连通网所得到的边数最少的生成树 B 由连通网所得到的顶点数相对较少的生成树 C 连通网中所有生成树中权值之和为最小的生成树 D 连通网的极小连通子图 【解答】C ⑼ 判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以用（）。A 求关键路径的方法 B 求最短路径的方法 C 广度优先遍历算法 D 深度优先遍历算法 【解答】D 【分析】当有向图中无回路时，从某顶点出发进行深度优先遍历时，出栈的顺序（退出DFSTraverse算法）即为逆向的拓扑序列。 ⑽ 下面关于工程计划的AOE网的叙述中，不正确的是（）?br /> A 关键活动不按期完成就会影响整个工程的完成时间 B 任何一个关键活动提前完成，那么整个工程将会提前完成 C 所有的关键活动都提前完成，那么整个工程将会提前完成 D 某些关键活动若提前完成，那么整个工程将会提前完 【解答】B 【分析】AOE网中的关键路径可能不止一条，如果某一个关键活动提前完成，还不能提前整个工程，而必须同时提高在几条关键路径上的关键活动。 3.判断题 ⑴ 一个有向图的邻接表和逆邻接表中的结点个数一定相等。 【解答】对。邻接表和逆邻接表的区别仅在于出边和入边，边表中的结点个数都等于有向图中边的个数。 ⑵ 用邻接矩阵存储图，所占用的存储空间大小只与图中顶点个数有关，而与图的边数无关。【解答】对。邻接矩阵的空间复杂度为Ｏ(n2)，与边的个数无关。 ⑶ 图G的生成树是该图的一个极小连通子图 【解答】错。必须包含全部顶点。 ⑷ 无向图的邻接矩阵一定是对称的，有向图的邻接矩阵一定是不对称的 【解答】错。有向图的邻接矩阵不一定对称，例如有向完全图的邻接矩阵就是对称的。 ⑸ 对任意一个图，从某顶点出发进行一次深度优先或广度优先遍历，可访问图的所有顶点。【解答】错。只有连通图从某顶点出发进行一次遍历，可访问图的所有顶点。 ⑹ 在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧。【解答】错。只能说明从顶点a到顶点b有一条路径。 ⑺ 若一个有向图的邻接矩阵中对角线以下元素均为零，则该图的拓扑序列必定存在。【解答】对。参见第11题的证明。 ⑻ 在AOE网中一定只有一条关键路径?br />【解答】错。AOE网中可能有不止一条关键路径，他们的路径长度相同 4．n个顶点的无向图，采用邻接表存储，回答下列问题?br />⑴ 图中有多少条边？ ⑵ 任意两个顶点i和j是否有边相连？ ⑶ 任意一个顶点的度是多少?br /> 【解答】 ⑴ 边表中的结点个数之和除以2。⑵ 第i个边表中是否含有结点j。⑶ 该顶点所对应的边表中所含结点个数。 5．n个顶点的无向图，采用邻接矩阵存储，回答下列问题： ⑴ 图中有多少条边？ ⑵ 任意两个顶点i和j是否有边相连？ ⑶ 任意一个顶点的度是多少？ 【解答】 ⑴ 邻接矩阵中非零元素个数的总和除以2。 ⑵ 当邻接矩阵A中A[i][j]=1（或A[j][i]=1）时，表示两顶点之间有边相连。⑶ 计算邻接矩阵上该顶点对应的行上非零元素的个数。 6．证明：生成树中最长路径的起点和终点的度均为１。【解答】用反证法证明。 设v1, v2, …, vk是生成树的一条最长路径，其中，v1为起点，vk为终点。若vk的度为2，取vk的另一个邻接点v，由于生成树中无回路，所以，v在最长路径上，显然 v1, v2, …, vk , v的路径最长，与假设矛盾。所以生成树中最长路径的终点的度为1。同理可证起点v1的度不能大于1，只能为1。 7．已知一个连通图如图6-6所示，试给出图的邻接矩阵和邻接表存储示意图，若从顶点v1出发对该图进行遍历，分别给出一个按深度优先遍历和广度优先遍历的顶点序列。 【解答】邻接矩阵表示如下： 深度优先遍历序列为：v1 v2 v3 v5 v4 v6 广度优先遍历序列为：v1 v2 v4 v6 v3 v5 邻接表表示如下： 8．图6-7所示是一个无向带权图，请分别按Prim算法和Kruskal算法求最小生成树。 【解答】按Prim算法求最小生成树的过程如下： 按Kruskal算法求最小生成树的过程如下： 9．对于图6-8所示的带权有向图，求从源点v1到其他各顶点的最短路径。 【解答】从源点v1到其他各顶点的最短路径如下表所示。 源点 终点 最短路径 最短路径长度 v1 v7 v1 v7 7 v1 v5 v1 v5 11 v1 v4 v1 v7 v4 13 v1 v6 v1 v7 v4 v6 16 v1 v2 v1 v7 v2 22 v1 v3 v1 v7 v4 v6 v3 25 10．如图6-9所示的有向网图，利用Dijkstra算法求从顶点v1到其他各顶点的最短路径。 【解答】从源点v1到其他各顶点的最短路径如下表所示。 源点 终点 最短路径 最短路径长度 v1 v3 v1 v3 15 v1 v5 v1 v5 15 v1 v2 v1 v3 v2 25 v1 v6 v1 v3 v2 v6 40 v1 v4 v1 v3 v2 v4 45 11．证明：只要适当地排列顶点的次序，就能使有向无环图的邻接矩阵中主对角线以下的元素全部为0。【解答】任意n个结点的有向无环图都可以得到一个拓扑序列。设拓扑序列为v0v1v2…vn-1，我们来证明此时的邻接矩阵A为上三角矩阵。证明采用反证法。 假设此时的邻接矩阵不是上三角矩阵，那么，存在下标i和j（i>j），使得A[i][j]不等于零，即图中存在从 vi到vj的一条有向边。由拓扑序 列的定义可知，在任意拓扑序列中，vi的位置一定在vj之前，而在上述拓扑序列v0v1v2…vn-1中，由于i>j，即vi的位置在vj之后，导 致矛盾。因此命题正确。 12.算法设计 ⑴ 设计算法，将一个无向图的邻接矩阵转换为邻接表。 【解答】先设置一个空的邻接表，然后在邻接矩阵上查找值不为零的元素，找到后在邻接表的对应单链表中插入相应的边表结点。 邻接矩阵存储结构定义如下： const int MaxSize=10;template struct AdjMatrix { T vertex[MaxSize];//存放图中顶点的数组 int arc[MaxSize][MaxSize];//存放图中边的数组 int vertexNum, arcNum;//图的顶点数和边数 };邻接表存储结构定义如下： const int MaxSize=10;struct ArcNode //定义边表结点 { int adjvex;//邻接点域 ArcNode *next;};template struct VertexNode //定义顶点表结点 { T vertex;ArcNode *firstedge;};struct AdjList { VertexNode adjlist[MaxSize];int vertexNum, arcNum;//图的顶点数和边数 };具体算法如下： ⑵ 设计算法，将一个无向图的邻接表转换成邻接矩阵。 【解答】在邻接表上顺序地取每个边表中的结点，将邻接矩阵中对应单元的值置为1。邻接矩阵和邻接表的存储结构定义与上题相同。具体算法如下： ⑶ 设计算法，计算图中出度为零的顶点个数。 【解答】在有向图的邻接矩阵中，一行对应一个顶点，每行的非零元素的个数等于对应顶点的出度。因此，当某行非零元素的个数为零时，则对应顶点的出度为零。据此，从第一行开始，查找每行的非零元素个数是否为零，若是则计数器加1。具体算法如下： ⑷ 以邻接表作存储结构，设计按深度优先遍历图的非递归算法。【解答】参见6.2.1。 ⑸ 已知一个有向图的邻接表，编写算法建立其逆邻接表。 【解答】在有向图中，若邻接表中顶点vi有邻接点vj，在逆邻接表中vj一定有邻接点vi，由此得到本题算法思路：首先将逆邻接表的表头结点firstedge域置空，然后逐行将表头结点的邻接点进行转化。 ⑹ 分别基于深度优先搜索和广度优先搜索编写算法，判断以邻接表存储的有向图中是否存在由顶点vi到顶点vj的路径（i≠j）。 【解答】⑴ 基于深度优先遍历： ⑵ 基于广度优先遍历： 学习自测及答案 1．某无向图的邻接矩阵A=，可以看出，该图共有（A 3 B 6 C 9 D 以上答案均不正确 【解答】A 2．无向图的邻接矩阵是一个（），有向图的邻接矩阵是一个（）A 上三角矩阵 B 下三角矩阵 C 对称矩阵 D 无规律 【解答】C，D 3．下列命题正确的是（）。 A 一个图的邻接矩阵表示是唯一的，邻接表表示也唯一）个顶点。 B 一个图的邻接矩阵表示是唯一的，邻接表表示不唯一 C 一个图的邻接矩阵表示不唯一的，邻接表表示是唯一 D 一个图的邻接矩阵表示不唯一的，邻接表表示也不唯一 【解答】B 4．十字链表适合存储（），邻接多重表适合存储（）。【解答】有向图，无向图 5.在一个具有n 个顶点的有向完全图中包含有（）条边： A n(n-1)/2 B n(n-1)C n(n+1)/2 D n2 【解答】B 6．n个顶点的连通图用邻接矩阵表示时，该矩阵至少有（）个非零元素。【解答】2(n-1)7．表示一个有100个顶点，1000条边的有向图的邻接矩阵有（）个非零矩阵元素。【解答】1000 8．一个具有n个顶点k条边的无向图是一个森林（n>k），则该森林中必有（）棵树。 A k B n C n-k D 1 【解答】C 9．用深度优先遍历方法遍历一个有向无环图，并在深度优先遍历算法中按退栈次序打印出相应的顶点，则输出的顶点序列是（）。 A 逆拓扑有序 B 拓扑有序 C 无序 D 深度优先遍历序列 【解答】A 10.关键路径是AOE网中（）。 A 从源点到终点的最长路径 B从源点到终点的最长路径 C 最长的回路 D 最短的回路 【解答】A 11.已知无向图G的邻接表如图6-10所示，分别写出从顶点1出发的深度遍历和广度遍历序列，并画出相应的生成树。 【解答】深度优先遍历序列为：1，2，3，4，5，6 对应的生成树为： 广度优先遍历序列为：1，2，4，3，5，6 对应的生成树为： 12.已知已个AOV网如图6-11所示，写出所有拓扑序列。 【解答】拓扑序列为：v0 v1 v5 v2 v3 v6 v4、v0 v1 v5 v2 v6 v3 v4、v0 v1 v5 v6 v2 v3 v4。 《数据结构》 2n10．散列函数越复杂越好，因为这样随机性好，冲突概率小.× 11．Hash表的平均查找长度与处理冲突的方法无关。× 12．负载因子(装填因子)是散列表的一个重要参数，它反映散列表的装满程度。√ 13.若散列表的负载因子α<1，则可避免碰撞的产生。× 三、填空题 1.顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为__（1）n __次。2.在有序表A[1..20]中，按二分查找方法进行查找，查找长度为5的元素个数是__（2）5 __。 3.在有序表A[1„20]中，按二分查找方法进行查找，查找长度为4的元素的下标从小到大依次是____（3）1,3,6,8,11,13,16,19__。4.有序表(12,18,24,35,47,50,62,83,90,115，134)使用二分法查找90时，需___（4）2_次查找成功，查100时，需___（5）4_次才能确定不成功。 5.在n个记录的有序顺序表中进行折半查找，最大比较次数是___（6）log2n+1__。（取下界） 6.平衡因子的定义是___（7）结点的左子树的高度减去结点的右子树的高度___ 7.高度为8的平衡二叉树的结点数至少有___（8）54__个。（参照教材P238：N0=0,N1=1,N2=2,公式Nh=Nh-1+Nh-2+1） 8.动态查找表和静态查找表的重要区别在于前者包含有___（9）插入 _和__（10）_删除__运算，而后者不包含这两种运算。 四、应用题 1.假定对有序表：(3,4,5,7,24,30,42,54,63,72,87,95)进行折半查找，试回答下列问题： (1).画出描述折半查找过程的判定树； (2).若查找元素54，需依次与那些元素比较?(3).若查找元素90，需依次与那些元素比较?(4).假定每个元素的查找概率相等，求查找成功时的平均查找长度。 2.一棵二叉排序树结构如下,各结点的值从小到大依次为1-9，请标出各结点的值。 3.依次输入表(30,15,28,20,24,10,12,68,35,50,46,55)中的元素，生成一棵二叉排序树【华中理工大学 2000 五（10分）】 (1)试画出生成之后的二叉排序树;(2)对该二叉排序树作中序遍历，试写出遍历序列;(3)假定每个元素的查找概率相等，试计算该二叉排序树的平均查找长度。 4.设哈希函数H（k）=3 K mod 11，散列地址空间为0～10，对关键字序列（32,13,49,24,38,21,4,12）按下述两种解决冲突的方法构造哈希表（1）线性探测再散列（2）链地址法，并分别求出等概率下查找成功时的平均查找长度； 、数据结构复习题及答案 中南大学现代远程教育课程考试（专科）复习题及参考答案 数据结构 一、判断题： 1． 数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。（）2． 链式存储在插人和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序。 （） 3． 在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。（）4． 折半搜索只适用于有序表，包括有序的顺序表和有序的链表。（）5． 如果两个串含有相同的字符，则这两个串相等。 （） 6． 数组可以看成线性结构的一种推广，因此可以对它进行插入、删除等运算。（）7． 在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。（）8． 通常递归的算法简单、易懂、容易编写，而且执行的效率也高。 （）9． 一个广义表的表尾总是一个广义表。 （）10． 当从一个小根堆（最小堆）中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。 （） 11． 对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O（h）。 （） 12． 存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关。 （） 13． 直接选择排序是一种稳定的排序方法。 （）14． 闭散列法通常比开散列法时间效率更高。 （）15． 有n个结点的不同的二叉树有n!棵。（）16． 直接选择排序是一种不稳定的排序方法。（）17． 在2048个互不相同的关键码中选择最小的5个关键码，用堆排序比用锦标赛排序更快。（）18． 当3阶B_树中有255个关键码时,其最大高度(包括失败结点层)不超过8。（）19． 一棵3阶B_树是平衡的3路搜索树,反之,一棵平衡的3路搜索树是3阶非B_树。（）20． 在用散列表存储关键码集合时，可以用双散列法寻找下一个空桶。在设计再散列函数时，要求计算出的值与表的大小m互质。（）21． 在索引顺序表上实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每一块中元素个数有关。（） 22． 在顺序表中取出第i个元素所花费的时间与i成正比。 （）23． 在栈满情况下不能作进栈运算，否则产生“上溢”。 ()24． 二路归并排序的核心操作是将两个有序序列归并为一个有序序列。（）25． 对任意一个图，从它的某个顶点出 发，进行一次深度优先或广度优先搜索，即可访问图的每个顶点.（）26． 二叉排序树或者是一棵空二叉树，或者不是具有下列性质的二叉树：若它的左子树非空，则根结点的值大于其左孩子的值;若它的右子树非空，则根结点的值小于其右孩子的值。（）27． 在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。（） 28． 一个有向图的邻接表和逆邻接表中表结点的个数一定相等。（） 二、选择题： 1． 在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（）。A.O(n) B.O(n／2) C.O(1) D.O(n2)2． 带头结点的单链表first为空的判定条件是：（）A.first==NULL B.first一>1ink＝＝NULL C.first一>link==first D.first!＝NUlL 3． 当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（）。 A.n-2 B.n-l C.n D.n+1 4． 在系统实现递归调用时需利用递归工作记录保存实际参数的值。在传值参数情形，需为对应形式参数分配空间，以存放实际参数的副本；在引用参数情形，需保存实际参数的（），在被调用程序中可直接操纵实际参数。 A.空间 B.副本 C.返回地址 D.地址 5． 在一棵树中，（）没有前驱结点。A.分支结点 D.叶结点 C.树根结点 D.空结点 6． 在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（）。 A.2 B.1 C.0 D.-1 7． 对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为（）的值除以9。A.20 B.18 C.25 D.22 8． 在有向图中每个顶点的度等于该顶点的（）。A.入度 B.出度 C.入度与出度之和 D.入度与出度之差 9． 在基于排序码比较的排序算法中，（）算法的最坏情况下的时间复杂度不高于O(n10g2n)。A.起泡排序 B.希尔排序 C.归并排序 D.快速排序 10． 当α的值较小时，散列存储通常比其他存储方式具有（）的查找速度。A.较慢 B.较快 C.相同 D.不清楚 11． 设有一个含200个表项的散列表，用线性探查法解决冲突，按关键码查询时找到一个表项的平均探查次数不超过1.5，则散列表项应能够至少容纳（）个表项。(设搜索成功的平均搜索长度为Snl＝{1+l／(1一α)}／2，其中α为装填因子) A.400 B.526 C.624 D.676 12． 堆是一个键值序列{k1,k2,.....kn},对I=1,2,....|_n/2_|,满足（）A.ki≤k2i≤k2i+1 B.ki 1(2i+1≤n) 13． 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上() A.操作的有限集合B.映象的有限集合 C.类型的有限集合D.关系的有限集合 14． 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为() A.n-i+1 B.i C.i+1 D.n-i 15． 若不带头结点的单链表的头指针为head，则该链表为空的判定条件是() A.head==NULL B.head->next==NULL C.head!=NULL D.head->next==head 16． 引起循环队列队头位置发生变化的操作是() A.出队 B.入队 C.取队头元素 D.取队尾元素 17． 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是() A.2，4，3，1，5，6 B.3，2，4，1，6，5 C.4，3，2，1，5，6 D.2，3，5，1，6，4 18． 字符串通常采用的两种存储方式是() A.散列存储和索引存储 B.索引存储和链式存储 C.顺序存储和链式存储 D.散列存储和顺序存储 19． 设主串长为n，模式串长为m(m≤n)，则在匹配失败情况下，朴素匹配算法进行的无效位移次数为() A.m B.n-m C.n-m+D.n 20． 二维数组A［12］［18］采用列优先的存储方法，若每个元素各占3个存储单元，且第1个元素的地址为150，则元素A［9］［7］的地址为() A.429 B.432 C.435 D.438 21． 对广义表L=((a,b),(c,d),(e,f))执行操作tail(tail(L))的结果是() A.(e,f) B.((e,f)) C.(f) D.()22． 下列图示的顺序存储结构表示的二叉树是() 23． n个顶点的强连通图中至少含有()A.n-1条有向边 B.n条有向边 C.n(n-1)/2条有向边 D.n(n-1)条有向边 24． 对关键字序列(56，23，78，92，88，67，19，34)进行增量为3的一趟希尔排序的结果为() 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)25． 若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为() A.4 B.5 C.8 D.9 26． 由同一关键字集合构造的各棵二叉排序树() A.其形态不一定相同，但平均查找长度相同 B.其形态不一定相同，平均查找长度也不一定相同 C.其形态均相同，但平均查找长度不一定相同 D.其形态均相同，平均查找长度也都相同 27． ISAM文件和VSAM文件的区别之一是() A.前者是索引顺序文件，后者是索引非顺序文件 B.前者只能进行顺序存取，后者只能进行随机存取 C.前者建立静态索引结构，后者建立动态索引结构 D.前者的存储介质是磁盘，后者的存储介质不是磁盘 28． 下列描述中正确的是（） A． 线性表的逻辑顺序与存储顺序总是一致的 B． 每种数据结构都具备三个基本运算：插入、删除和查找 C． 数据结构实质上包括逻辑结构和存储结构两方面的内容 D． 选择合适的数据结构是解决应用问题的关键步骤 29． 下面程序段的时间复杂度是（） i=s=0 while(s {i++; s+=i; } A．O(1)B.O(n)C.O(log2n)D.O(n2)30． 对于顺序表来说，访问任一节点的时间复杂度是（） A．O(1)B.O(n)C.O(log2n)D.O(n2)31． 在具有n个节点的双链表中做插入、删除运算，平均时间复杂度为（） A．O(1)B.O(n)C.O(log2n)D.O(n2)32． 经过下列运算后，QueueFront(Q)的值是（） InitQueue(Q);EnQueue(Q,a);EnQueue(Q,a);DeQueue(Q,x); A.a B.b C.1 D.2 33． 一个栈的入栈序列是a,b,c，则栈的不可能输出序列是（） A.acb B.abc C.bca D.cab 34． 循环队列是空队列的条件是（） A．Q->rear==Q->front B.(Q->rear+1)%maxsize==Q->front C.Q->rear==0 D.Q->front==0 35． 设s3=“I AM”,s4=“A TERCHER”.则strcmp(s3,s4)=() A.0 B.小于0 C.大于0 D.不确定 36． 一维数组的元素起始地址loc[6]=1000，元素长度为4，则loc[8]为（） A．1000 B.1004 C.1008 D.8 37． 广义表（（a,b）,c,d）的表尾是（） A．a B.b C.(a,b)D.(c,d)38． 对于二叉树来说，第I层上至多有____个节点（） A．2i B.2i-1 C.2i-1 D.2i-1-1 39． 某二叉树的前序遍历序列为ABDGCEFH,中序遍历序列为DGBAECHF，则后序遍历序列为（） A．BDGCEFHA B.GDBECFHA C.BDGAECHF D.GDBEHFCA 40． M叉树中，度为0的节点数称为（） A．根 B.叶 C.祖先 D.子孙 41． 已知一个图如下所示，若从顶点a出发按宽度搜索法进行遍历，则可能得到的一种顶 点序列为（） 42． 堆的形状是一棵（） A．二叉排序树 B.满二叉树 C.完全二义树 D.平衡二叉树 43． 排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为（） A．希尔排序 B.归并排序 C.插入排序 D.选择排序 44． 采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（） A．n B.n/2 C.(n+1)/2 D.（n-1)/2 45． 散列查找是由键值______确定散列表中的位置，进行存储或查找（） A．散列函数值 B.本身 C.平方 D.相反数 46． 顺序文件的缺点是（） A．不利于修改 B.读取速度慢 C.只能写不能读 D.写文件慢 47． 索引文件的检索方式是直接存取或按_____存取（） A．随机存取 B.关键字 C.间接 D.散列 48． 堆是一个键值序列{k1,k2,.....kn},对i=1,2,....|_n/2_|,满足（） A.ki≤k2i≤k2i+1 B.ki C.ki≤k2i且ki≤k2i+1(2i+1≤n)D.ki≤k2i 或ki≤k2i+1(2i+1≤n) 三、计算与算法应用题（本大题每小题9分） 1.给定表（119，14，22，1，66，21，83，27，56，13，10） 请按表中元素的顺序构造一棵平衡二叉树，并求其在等概率情况下查找成功的平均长度。（9分）2.已知一个有向图的顶点集V和边集G分别为： V={a,b,c,d,e,f,g,h} E={ 3.设散列表的长度为13，散列函数为H（h）= k%13，给定的关键码序列为19，14，23，01，68，20，84，27。试画出用线性探查法解决冲突时所构成的散列表。（8分） 0 4.对7个关键字进行快速排序，在最好的情况下仅需进行10次关键字的比较。 (1)假设关键字集合为{1,2,3,4,5,6,7}，试举出能达到上述结果的初始关键字序列； (2)对所举序列进行快速排序，写出排序过程。（９分）5.如图所示二叉树，回答下列问题。（9分） 6.画出在一个初始为空的AVL树中依次插入3,1,4,6,9,8,5,7时每一插入后AVL树的形态。若做了某种旋转，说明旋转的类型。然后，给出在这棵插入后得到的AVL树中删去根结点后的结果。7.已知一组记录的排序码为（46，79，56，38，40，80，95，24），写出对其进行快速排序的每一次划分结果。 8.一个线性表为 B=（12，23，45，57，20，03，78，31，15，36），设散列表为 HT[0..12]，散列函数为 H（key）= key % 13 并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。 9.已知一棵二叉树的前序遍历的结果序列是 ABECKFGHIJ，中序遍历的结果是 EBCDAFHIGJ，试写出这棵二叉树的后序遍历结果。 10.假定对线性表(38，25，74，52，48，65，36)进行散列存储，采用H(K)=K％9作为散列函数，若分别采用线性探查法和链接法处理冲突，则对应的平均查找长度分别为 和 。11．假定一组记录的排序码 为(46，79，56，38，40，80，25，34，57，21)，则对其进行快速排序的第一次划分后又对左、右两个子区间分别进行一次划分，得到的结果为：。 12.下图是带权的有向图G的邻接表表示法。从结点V1出发，深度遍历图G所得结点序列为（A），广度遍历图G所得结点序列为（B）；G的一个拓扑序列是（C）；从结点V1到结点V8的最短路径为（D）；从结点V1到结点V8的关键路径为（E）。其中A、B、C的选择有： V1,V2,V3,V4,V5,V6,V7,V8 V1,V2,V4,V6,V5,V3,V7,V8 V1,V2,V4,V6,V3,V5,V7,V8 V1,V2,V4,V6,V7,V3,V5,V8 V1,V2,V3,V8,V4,V5,V6,V7 V1,V2,V3,V8,V4,V5,V7,V6 V1,V2,V3,V8,V5,V7,V4,V6 D、E的选择有： ① V1,V2,V4,V5,V3,V8 ② V1,V6,V5,V3,V8 ③ V1,V6,V7,V8 ④ V1,V2,V5,V7,V8 13.画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。14.已知如图所示的有向网，试利用Dijkstra算法求顶点1到其余顶点的最短路径，并给出算法执行过程中各步的状态。 15.假定用于通信的电文由８个字母a,b,c,d,e,f,g,h组成，各字母在电文中出现的频率分别为５，２５，３，６，１０，１１，３６，４。试为这８个字母设计不等长Huffman编码，并给出该电文的总码数。 16.已知一棵二叉树的中序和前序序列如下，试画出该二叉树并求该二叉树的后序序列。（9分）中序序列：c，b，d，e，a，g，i，h，j，f 前序序列：a，b，c，d，e，f，g，h，i，j 17.假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。试为这8个字母设计哈夫曼编码。使用0～7的二进制表示形式是另一种编码方案。对于上述实例，比较两种方案的优缺点。 四、算法设计题 1.已知深度为h的二叉树以一维数组BT(1:2h-1)作为其存储结构。请写一算法，求该二叉树中叶结点的个数。 2.编写在以BST为树根指针的二叉搜索树上进行查找值为item的结点的非递归算法，若查找item带回整个结点的值并返回ture，否则返回false。bool Find（BtreeNode*BST，ElemType&item） 3.编写算法，将一个结点类型为 Lnode 的单链表按逆序链接，即若原单链表中存储元素的次序为 a 1，......a n-1，a n，则逆序链接后变为 , a n，a n-1，......a 1。 4.根据下面函数原型，编写一个递归算法，统计并返回以BT为树根指针的二叉树中所有 叶子结点的个数。int Count(BTreeNode * BT)； 5.设A=(a1,...,am)和B=(b1,...,bn)均为顺序表，A'和B'分别为A和B中除去最大共同前缀后的子表。若A'=B'=空表，则A=B；若A'=空表，而B' ≠空表，或者两者均不为空表，且A'的首元小于B'的首元，则A 6.已知单链表a和b的元素按值递增有序排列, 编写算法归并a和b得到新的单链表c，c的元素按值递减有序。 7.编写递归算法，对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。 8.编写算法判别T是否为二叉排序树.9.试写一算法，判断以邻接表方式存储的有向图中是否存在由顶点Vi到顶点Vj的路径（i<>j）。注意：算法中涉及的图的基本操作必须在存储结构上实现。 参考答案 一、判断题 1．√ 2．× 3．√ 4．× 5．√ 6．√ 7．× 8．× 9．× 11 × 12√ 13 × 14 √ 15 × 16 √ 17 × 18 × 19.× 20.× 21.√ 22.× 23.√ 24.√ 25.× 26.× 27.× 28.√ 二、单项选择题 1．A 2．B 3．B 4．D 5．C 6．A 7．C 8．C 9．C 10．B 11．A 12 C 13.B 14.D 15.A 16.A 17.D 18.C 19.C 20.A 21.B 22.A 23.B 24.D 25.C C 28.D 29.B 30.A 31.A 32.B 33.D 34.A 35.C 36.C 37.D 38.C 39.D 40.A 41.B 42.C 43.D 44.C 45.A 46.A 47.B 48.C 三 计算与算法应用题 １．［解答］ 平均长度为4.2、解：画图（略） 深度优先搜索序列：a，b，f，h，c，d，g，e 广度优先搜索序列：a，b，c，f，d，e，h，g 3、解：计算机关键码得到的散列地址 关键码 19 14 23 01 68 20 84 27 散列地址 6 10．× 26.B 1 3 7 6 1 在散列表中散列结果 0 01 68 27 19 20 84 23 4.对n个关键自序列进行一趟快速排序，要进行n-1次比较，也就是基准和其他n-1个关键字比较。 这里要求10次，而71)= 10，这就要求2趟快速排序后，算法结束。所以，列举出来的序列，要求在做partition的时候，正好将序列平分 (1)4 1 3 2 6 5 7 或 4 1 3 7 6 5 2 或 4 5 3 7 6 1 2 或 4 1 3 5 6 2 7.......(2)按自己序列完成 0 1 2 3 4 5 6 7 8 9 10 11 12 13 Apr Aug Dec Feb Jan Mar May June July Sep Oct Nov(1)(2)(1)(1)(1)(1)(2)(4)(5)(2)(5)(6) (2)搜索成功的平均搜索长度为 l／12*(1+2+l+l+l+l+2+4+5+2+5+6)：3l／12 5．答案：(1)djbaechif(2)abdjcefhi(3)jdbeihfca 6.在这个AVL树中删除根结点时有两种方案: 【方案1】在根的左子树中沿右链走到底,用5递补根结点中原来的6,再删除5所在的结点.【方案2】在根的右子树中沿左链走到底,用7递补根结点中原来的6,再删除7所在的结点.7.划分次序 划分结果第二篇：数据结构试题及答案
第三篇：数据结构 第六章 图 练习题及答案详细解析(精华版)
第四篇：数据结构第四教学单元测验练习题(答案)
第五篇：数据结构复习题及答案
点击咨询 