数据结构复习题总结

填空题1.文件可按其记录的类型不同而分成两类，操作系统文件和数据库文件。2.数据库文件按记录中关键字的多少可分成(单关键字文件)和(多关键字文件)两种文件。3.文件由(记录)组成，记录由(数据项)组成。4.从用户观点看，文件的逻辑结构通常可以区分为两类：一类是如DBASE中数据库文件那样的文件组织结构，称为(数据库)文件；另一种是诸如用各种文字处理软件编辑成的文本文件，称为(文本)文件。

从文件在存储器上的存放方式来看，文件的物理结构往往可区分为三类，即(顺序组织)、(随机组织)、(链组织)。

B+树适用于组织(随机组织)的索引结构，

m阶B+树每个结点至多有(m)

除根结点外每个结点至少有((m/2)向上取整)个儿子，根结点至少有(2)个儿子，有k个儿子的结点必有(k)个关键码。5.物理记录之间的次序由指针相链表示的顺序文件称为(串联文件)6.顺序文件中，要存取第I个记录，必须先存取(第I-1)个记录。7.索引顺序文件既可以顺序存取，也可以(随机)存取。8.建立索引文件的目的的(提高查找速度)。9.索引顺序文件是最常用的文件组织之一，通常用(树)结构来组织索引。10.倒排文件的主在优点在于(检索记录块)。11.检索是为了在文件中满足一定条件的记录而设置的操作。检索可以按(关键字)检索，也可以按(记录号)检索；

按(记录号)检索又可以有(顺序)检索和(直接)检索。12.哈希检索的技术的关键是(构造哈希函数)和(解决冲突的方法)。结构来组织索引。13.VSAM系统是由(索引集)、(顺序集)、(数据集)构成的。14.VSAM(虚拟存储存取方法)文件的优点是：动态地(分配和释放存储空间)，不需要文件进行(重组)，并能较快地(对插入的记录)进行查找。一～五章选择题一学习数据结构的主要目的是(C)。

A．处理数据计算问题B．研究程序设计技巧

C．选取适宜数据结构，写出更有效的算法D．是计算机硬件课程的根底数据结构是一门研究非数值计算的程序设计问题中计算机的逻辑存储以及它们之间的(B)和运算的科学。

A．结构B．关系C．运算D．算法在计算机中存储一个数据元素的位串称为(A)。

A.结点B.数据项C.数据字段D.字符串算法指的是(C)

A.计算机程序B.排序算法

C.解决问题的有限运算序列D.解决问题的计算方法(D)是数据不可分割的最小单位。

A．数据结构B．数据对象C．数据元素D．数据项数据结构有(D)种根本逻辑结构。

A.1B.2C.3在数据结构中，从逻辑上可以把数据结构分成(C)。

A．动态结构和静态结构B．紧凑结构和非紧凑结构

C．线性结构和非线性结构D．内部结构和外部结构通常所说的时间复杂度是指(B)。

A．语句的频度和B．算法的时间消耗C．渐近时间复杂度D．最坏时间复杂度(C)是数据的根本单位。

A．数据结构B．数据项C．数据元素D．数据类型数据元素是数据的根本单位，其内(C)数据项。

A.只能包括一个B.不包含C.可以包含多个D.必须包含多个计算机算法必须具有输入、输出和(A)等五个特性。

A．可执行性、确定性、有穷性B可执行性、可移植性、可扩充性

C．确定性、有穷性和稳定性D．易读性、稳定性和平安性以下时间复杂度中最好的是(A)。

A.O(1)B.O(n)C.O(log2n)D.O(n^2)对于反复屡次使用的程序，应尽是选用(B)算法。

A．节约空间B．节约时间C．简明易懂D．容易调试对于反复屡次使用的程序，应尽是选用(B)算法。

A．节约空间B．节约时间C．简明易懂D．容易调试以下说法不正确的选项是(D)。

A．数据元素是数据的根本单位

B．数据项是数据中不可分割的最小可标识单位

C．数据可由假设干个数据元素构成

D．数据项可由假设干个数据元素构成计算机算法指的是(C)。

A．计算方法和运算结果B．排序方法C．解决某一问题的有限序列D．调度方法以下时间复杂度中最坏的是(D)。

A.O(1)B.O(n)C.O(log2n)D.O(n^2)根据数据元素之间关系的不同特性，以下四类根本的逻辑结构反映了四类根本的数据组织形式，其中解释错误的选项是(A)。

A．集合中任何两个结点之间都有逻辑关系但组织形式松散

B．线性结构中结点按逻辑关系依次排列形成一条“锁链”

C．树形结构具有分支、层次特性，其形态有点像自然界中的树

D．图状结构中的各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接以下四种根本的逻辑结构中，数据元素之间关系最弱的是(A)。

A.集合B.线性结构C.树形结构D.图状结构某算法的时间消耗为T(n)=100n+10log2n+n2+10，该算法的时间复杂度为(A)：

A．O(n2)B．O(n3)C．O(n)D．O(1)一般而言，最适合描述算法的语言是(C)。

A．自然语言B．计算机程序语言C．介于自然语言和程序设计语言之间的语言D．数学公式研究数据结构就是研究(D)。

A．数据的存储结构

B．数据的存储结构

C．数据的逻辑结构及其数据在运算上的实现

D．数据的逻辑和存储结构及其数据在运算上的实现以下四种根本的逻辑结构中，数据元素之间关系最弱的是(A)。

A.集合B.线性结构C.树形结构D.图状结构评价一个算法时间性能的主要标准是(D)。D．算法的时间复杂度一个算法必须保证执行有限步之后结束，这是算法的(A)特性。

A．有穷性B．确定性C．可行性D．输出逻辑关系是指数据元素间的(C)。

A.类型B.存储方式C.结构D.数据项研究数据结构就是研究(D)。

A．数据的逻辑结构及其数据在运算上的实现

B．数据的存储结构

C．数据的逻辑和存储结构

D．数据的逻辑和存储结构及其数据在运算上的实现算法分析的两个主要方面是(A)。

A．空间复杂性和时间复杂性B．正确性和简明性

C．可读性和文档性D．数据复杂性和程序复杂性用类C语言描写的算法(B)。

A.可以直接在计算机上运行B.可以描述解题思想和根本框架

C.不能改写成C语言程序D.与C语言无关逻辑结构是(A)关系的整体。

A.数据元素之间逻辑B.数据项之间逻辑C.数据类型之间D.存储结构之间要求同一逻辑结构的所有数据元素具有相同特性，这意味着(B)。

A.数据元素具有同一的特点

B.不仅数据元素包含的数据项的个数要相同,而且对应数据项的类型要一致

C.每个数据元素都一样式

D.数据元素所包含的数据项的个数要相等算法分析的目的是(C)。

A.找出数据结构的合理性B.研究算法中的输入与输出的关系

C.分析算法的效率以求改良D.分析算法的易懂性和文档性数据结构被形式化地定义为(K，R)，其中，R是K上(D)的有限集合。

A．操作B．映象C．存储D．关系数据结构被形式化地定义为(K，R)，其中，R是K上(D)的有限集合。

A．操作B．映象C．存储D．关系一个存储结点存放一个(B)。

A.数据项B.数据元素C.数据结构D.数据类型算法能正确地实现预定功能的特性称为(A)。

A.正确性B.易读性C.健壮D.高效率数据结构被形式化地定义为(K，R)，其中K是(B)的有限集合。

A．算法B．数据元素C．数据操作D．逻辑结构数据结构被形式化地定义为(K，R)，其中，R是K上(D)的有限集合。

A．操作B．映象C．存储D．关系数据结构被形式化地定义为(K，R)，其中K是(B)的有限集合。

A．算法B．数据元素C．数据操作D．逻辑结构以下说法不正确的选项是(A)。

A．数据结构就是数据之间的逻辑结构

B．数据类型可看成是程序设计语言中已实现的数据结构

C．数据项是组成数据元素的最小标识单位

D．数据的抽象运算不依赖具体的存储结构算法原那么上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成，这是算法的(C)。

A．有穷性B．确定性C．可行性D．输出二线性表L=(a1,a2,…ai,…,an),以下说法正确的选项是(D)。

A.每个元素都有一个直接前驱和直接后继

B.线性表中至少要有一个元素

C.表中诸元素的排列顺序必须是由小到大或由大到小的

D.除第一个元素和最后一个元素外其余每个元素都有一个且仅有一个直接前驱和直接后继对线性表进行二分法查找，其前提条件是(A)。

A．线性表以顺序方式存储，并且按关键码值排好序

B．线性表以顺序方式存储，并且按关键码值的检索频率排好序

C．线性表以链接方式存储，并且按关键码值排好序

D．线性表以链接方式存储，并且按关键码值的检索频率排好序对于只在表的首尾两端进行插入操作的线性表，宜采用的存储结构为(C)。

A.顺序表B.用头指针表示的单循环链表

C.用尾指针表示的单循环链表D.单链表线性表的顺序存储结构是一种(A)的存储结构。

A．随机存取B．顺序存取C．索引存取D．散列存取用数组表示线性表的优点是(B)。

A.便于插入和删除操作B.便于随机存取

C.可以动态地分配存储空间D.不需要占用一片相邻的存储空间在线性表的以下存储结构中,读取元素花费时间最少的是(D)。

A.单链表B.双链表C.循环链表D.顺序表线性结构中的一个结点代表一个(A)。

A.数据元素B.数据项C.数据D.数据结构对于顺序表,以下说法错误的选项是(A)。

A.顺序表是用一维数组实现的线性表,数组的下标可以看成是元素的绝对地址

B.顺序表的所有存储结点按相应数据元素元素间的逻辑关系决定的次序依次排列

C.顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻

D.顺序表的特点是:逻辑上相邻的元素,存储在物理位置也相邻的单元中假设某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，那么采用(A)存储方式最节省时间。

A．单链表B．双链表C．单向循环D．顺序表线性表是(A)。

A.一个有限序列，可以为空B.一个有限序列，不可以为空

C.一个无限序列，可以为空D.一个无限序列，不可以为空在(C)运算中，使用顺序表比链表好。

A．插入B．删除C．根据序号查找D．根据元素值查找在循环双向链表的p所指的结点之后插入s所指结点的操作是(D)。

A．p->next=s;s->prior=p;p->next->prior=s;s->next=p->next;

B．p->next=s;p->next->prior=s;s->prior=p;s->next=p->next;

C．s->prior=p;s->next=p->next;p->next=s;p->next->prior=s;

D.s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;(D)适合作为经常在首尾两端操作线性表的存储结构。

A.顺序表B.单链表C.循环链表D.双向链表对于顺序表的优缺点,以下说法错误的选项是(C)。

A.无需为表示结点间的逻辑关系而增加额外的存储空间

B.可以方便地随机存取表中的任何一结点

C.插入和删除操作较方便

D.由于顺序表要求占用连续的空间,存储分配只能预先进行(静态分配)设非空单链表的数据字段为data，指针字段为next，指针p指向单链表中第i个结点，s指向已生成的新结点，现将s结点插入到单链表中，使其成为第i+1个结点，以下算法段能正确完成上述要求的是(C)。

A.s->next=p->next=s；

B.p->next=s；s->next=p->next；

C.s->next=p->next；p->next=s；交换p->data和s->data；

D.p=s；s->next=p线性表中各元素之间的关系是(C)关系。

A.层次B.网状C.有序D.集合在长度为n的顺序表的第i〔1≤i≤n+1〕各位置上插入一个元素，元素的移动次数为(D)。

A.n-(i-1)B.n-iC.iD.i-1在一个单链表HL中,假设要在指针q所指结点的后面插入一个由指针p所指向的结点，那么执行(D)。

A．q->next=p->next;p->next=q;

B．p->next=q->next;q=p;

C．q->next=p->next;p->next=p;

D．p->next=q->next;q->next=p;不带头结点的单链表head为空的判定条件是(A)

A．head==NULLB．head->next==NULLC．head->next==headD．head!=NULL非空的循环单链表head的尾结点(由p所指向)满足(C)。

A．p->next=NULLB．p=NULLC．p->next=headD．p=head顺序表是线性表的(B)。

A.链式存储结构B.顺序存储结构C.索引存储结构D.散列存储结构线性表中哪些元素只有一个直接前驱和一个直接后继(C)。

A.首元素B.尾元素C.中间元素D.所有的元素在长度为n的顺序存储的线性表中，删除第i个元素(1≤i≤n)时，需要从前向后依次前移(A)个元素。

A．n-IB．n-i+1C．n-i-1D．i在一个单链表中，假设p所指结点不是最后结点，在p之后插入s所指结点，那么执行(D)。

A．s->next=p;p->next=s;B．s->next=p->next;p->next=s;

C．s->next=p->next;p=s;D．p->next=s;s->next=p;从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比拟(B)个结点。

A．nB．n/2C．(n-1)/2D．(n+1)/2假设left和right为双向链表中指向直接前趋结点和直接后继结点的指针字段，现要把一个指针s所指的新结点作为非空双链表中q所指结点〔中间结点〕的直接后继结点插入到该双向链表中，那么以下算法段能正确完成上述要求的是(C)。

A.q->right=s；s->left=q；q->right->left=s；s->right=q->right；

B.s->left=q；q->right=s；q->right->left=s；s->right=q->right；

C.s->left=q;s-right=q->right;q->right-left=s;q->right=s;

D.以上都不对下面给出的算法段是把一个q所指新结点作为非空双向链表中的p所指结点的前驱结点插入到该双链表中，能正确完成要求的算法段是(A)。

A．q->rlink=p;q->llink=p->llink;p->llink=q;p->llink->rlink=q;

B．p->llink=q;q->rlink=p;p->llink->rlink=q;q->llink=p->llink;

C．q->llink=p->llink;q->rlink=p;p->llink->rlink=q;p->llink=q;

D．以上都不对循环链表的主要优点是(D)。

A.不再需要头指针了

B.某个结点的位置后,容易找到它的直接前驱

C.在进行插入、删除操作时,能更好地保证链表不断开

D.从表中任一结点出发都能扫描到整个链表在单链表的一个结点中有(A)个指针。

A.1B.2C.0在一个单链表中，删除p所指的直接后继的操作是(A)。

A．p->next=p->next->next;B．p=p->next->next;

C．p=p->next;D．p->next->next=p->next;带有头结点的单链表head为空的判定条件是(B)。

A．head==NULLB．head->next==NULL

C．head->next==headD．head!=NULL将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为(C)。

A．O(1)B．O(n)C．O(m)D．O(m+n)下面关于线性表的表达中，错误的选项是(B)。

A.线性表采用顺序存储，必须占用一片连续的存储单元

B.线性表采用顺序存储，便于进行插入和删除操作

C.线性表采用链接存储，不必占用一片连续的存储单元

D.线性表采用链接存储，便于插入和删除操作一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是(B)。

A.O(1)B.O(n)C.O(n^2)D.O(log2n)在单循环链表中，用尾指针取代头指针的作用是(D)。

A．方便查找中间结点B．方便查找终端结点

C．方便查找开始结点D．查找开始结点和终端结点同样方便在一个单链表中，q所指结点是p所指结点的前趋结点，假设在p和q之间插入s结点，那么执行的操作序列是。(C)。

A.s->next=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;带有头结点的单循环链表head为空的判定条件是(C)。

A．head==NULLB．head->next==NULLC．head->next==headD．head!=NULL链式存储的存储结构所占存储空间(A)。

A.分两局部，一局部存放结点值，另一局部存放表示结点关系的指针

B.只有一局部，存放结点值

C.只有一局部，存放表示结点关系的指针

D.分两局部，一局部存放结点值，另一局部存放结点所占单元数线性表〔L〕经运算InitList〔L〕后，函数IEmpty〔L〕的值是(C)。

A.0B.falseC.1D.Null以下关于链式存储结构的表达中，(C)是不正确的。

A.结点除自身信息外还包括指针域，因此存储密度小于顺序存储结构

B.逻辑上相邻的结点物理上不必邻接

C.可以通过计算直接确定第i个结点的存储地址

D.插入、删除运算操作方便，不必移动结点在等概率情况下，顺序表的插入操作要移动(B)结点。

A．全部B．一半C．三分之一D．四分之一在一个具有n个结点的有序单链表中插入一个新的结点并仍然有序的时间复杂度是(B)。

A．O(1)B．O(n)C．O(n^2)D．O(log2n)单链表中，增加头结点的作用是(A)。

A.方便运算的实现B.用于标志单链表

C.使单链表中至少有一个结点D.用于标志起始结点两指针p和q，分别指向单链表的两个元素，p所指元素是q所指元素的前驱的条件是(A)。

A.p->next==qB.q->next==pC.p==qD.p->next==null线性表采用链式存储时，其地址(D)。

A.必须是连续的B.一定是不连续的

C.局部地址必须是连续的D.连续与否均可以以下关于线性表的说法不正确的选项是(C)。

A.线性表中的数据元素可以是数字、字符、记录等不同类型

B.线性表中包含的数据元素个数不是任意的

C.线性表中的每个结点都有且只有一个直接前驱和直接后继

D.存在这样的线性表：表中各结点都没有直接前驱和直接后继在具有n个结点的单链表中，实现(A)的操作，其算法的时间复杂度都是O(n)。

A．遍历链表和求链表的第I个结点B．在地址为p的结点之后插入一个结点C．删除开始结点D．删除地址为p的结点的后继结点指针P所指的元素是双向循环链表L的尾元素的条件是(D)。

A.P==LB.p==nullC.p->prior==LD.p->next==L对顺序表上的插入、删除算法的时间复杂度分析来说，通常以(B)为标准操作。

A．条件判断B.结点移动C.算术表达式D.赋值语句两个指针p和q分别指向双向循环链表L两个元素，p所指元素是q所指元素的后继的条件是(B)。

A.p==qB.q->next==pC.p->next==qD.q->next==p->next线性表的链接实现有利于(A)运算。

A.插入B.读表元C.查找D.定位用单链表的方式存储的线性表，存储每一个结点需要两个域，一个是数据域，另一个是(B)。

A.当前结点所在地址域B.指针域C.空指针域D.空闲域在双向链表的一个结点中有(B)个指针。

A.1B.2C.0指针p指向线性链表L首元素的条件是(A)。

A.p=LB.L->next=pC.p->next=LD.p->next=null对线性表，在(B)情况下应当采用链表表示。

A．经常需要随机在存取元素B．经常需要进行插入和删除

C．表中元素需要占据一片连续的存储空间D．表中元素的个数不变假设某线性表中，最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，那么采用(C)存储方式最省时。

A.单链表B.仅有头指针的单循环链表

C.双链表D.仅有尾指针的单循环链表线性表的链式存储结构是一种(B)的存储结构。

A．随机存取B．顺序存取C．索引存取D．散列存取用链接方式存储的队列，在进行删除运算时(D)。

A．仅修改头指针B．仅修改尾指针

C．头、尾指针都要修改D．头、尾指针可能都要修改在顺序表中，只要知道(D)，就可在相同时间内求出任一结点的存储地址。

A．基地址B．结点大小C．向量大小D．基地址和结点大小三4个元素进S栈的顺序是A、B、C、D，进行两次Pop〔S，x〕操作后，栈顶元素的值是(B)。

A．AB．BC．CD．D表达式a*(b+c)-d的后缀表达式是(B)。

A.abcdd+-B.abc+*d-C.abc*+d-D.-+*abcd从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，那么执行(D)。

A.x=HS;HS=HS->next;B.x=HS->data;

C.HS=HS->next;x=HS->data;D.x=HS->data;HS=HS->next;当循环队列Sq是满队列时，存放队列元素的数组data有n个元素，那么data中存放个队列元素(A)。

A．nB．n-1C．n-2D队列操作的原那么是(B)。

A．先进先出B．先进后出C．只能进行插入D．只能进行删除队列的特点是(A)。

A．先进先出B．后进先出C.先进后出D．不进不出队列是限定在(C)处进行插入操作的线性表。

A．端点B．队头C．队尾D．中间和顺序栈相比，链栈有一个比拟明显的优势是(A)。

A.通常不会出现栈满的情况B.通常不会出现栈空的情况

C.插入操作更容易实现D.删除操作更容易实现经过以下运算后GetHead〔Q〕的值是(B)。

InitQueue〔Q〕；EnQueue〔Q，a〕；EnQueue(Q,b〕；OutQueue〔Q，x〕；

A．aB．bC．1D．2链栈ls是空栈的条件是(A)。

A．ls==nullB．ls->next==nullC．Ls==0D．ls->next==ls判定一个顺序栈ST〔最多元素为m0〕为空的条件是(B)。

A．ST.top<>ST.baseB．ST.top==ST.base

C．ST.top<>m0D．ST.top==m0判定一个循环队列QU(最多元素为m0)为空的条件是(C)。

A．QU.front==〔QU.rear+1〕%m0B．QU.front！=〔QU.rear+1〕%m0

C．QU.front==QU.rearD．QU.front判定一个循环队列QU(最多元素为m0)为满的条件是(A)。

A．QU.front==〔QU.rear+1〕%m0B．QU.front！=〔QU.rear+1〕%m0

C．QU.front==QU.rearD．QU.front如果以链表作为栈的存储结构,那么出栈操作时(C)

A.必须判别栈是否满B.判别栈元素的类型

C.必须判别栈是否空D.对栈不做任何判别假设一个栈的入栈序列是1,2,3,…,n,其输出序列为p1,p2,p3,…,pn,假设p1=n,那么pi为(C)。

A.IB.n=IC.n-I+1D.不确定设计一个判别表达式中左、右括号是否配对出现的算法,采用()数据结构最正确(B)。

A.线性表的顺序存储结构B.栈

C.队列D.线性表的链式存储结构顺序栈存储空间的实现使用(B)。

A．链表B．数组C．循环链表D．变量顺序栈是空栈的条件是(A)。

A．top==0B．top==1C．top==-1D同一个栈内各元素的类型(A)。

A．必须一致B．可以不一致C．不能一致D．不必不一致向一个栈顶指针为HS的链栈中插入一个s所指结点时，那么执行(C)。

A.HS->next=s;B.s->next=HS->next;HS->next=s;

C.s->next=HS;HS=s;D.s->next=HS;HS=HS->next;循环队列Sq是空队列的条件是(A)。

A．Sq->rear==Sq->frontB．(Sq->rear+1〕％maxsize==Sq->front

C．Sq->rear==0D．Sq->front==0循环队列Sq是满队列的条件是(B)。

A．Sq->rear==Sq->frontB．〔Sq->rear+1〕％maxsize==Sq->front

C．Sq->rear==0D．Sq->front==0一个队列的入对序列是1,2,3,4,那么队列的输出序列是(B)。

A.4,3,2,1B.1,2,3,4C.1,4,3,2D.一个顺序栈一旦说明，其占用空间的大小(A)。

A．已固定B．可以改变C．不能固定D．动态变化一个栈的入栈序列(顺序)是a,b,c,d,e,那么栈不可能的输出序列是(C)。

A.edcbaB.decbaC.dceabD.abcde一个栈的入栈序列是1,2,3,4,那么栈的可能的输出序列是(B)。

A.1,4,2,3B.2,1,4,3C.4,2,1,3D.一个栈的入栈序列是a,b,c,d,e,那么栈的不可能的输出序列是(C)。

A.edcbaB.decbaC.dceabD.abcde以下说法正确的选项是(A)。

A.因链栈本身没有容量限制，故在用户内存空间的范围内不会出现栈满情况

B.因顺序栈本身没有容量限制，故在用户内存空间的范围内不会出现栈满情况

C.对于链栈而言，在栈满状态下，如果再进行入栈操作，那么会发生“上溢”

D.对于顺序栈而言，在栈满状态下，如果再进行入栈操作，那么会发生“下溢”元素A、B、C、D依次进顺序栈后，栈顶元素是(D)。

A．AB．BC．CD．D在计算递归函数时,如不使用递归过程，那么一般情况下必须借助(A)数据结构

A.栈B.树C.双向队列D.顺序表在栈顶一端可进行的全部操作是(C)。

A．插入B．删除C．插入和删除D．进栈栈操作的原那么是(B)。

A．先进先出B．先进后出C．只能进行插入D．只能进行删除栈的特点是(B)。

A．先进先出B．后进先出C．后进后出D．不进不出栈和队列的共同点是(C)。

A.都是先进后出发B.都是先进先出

C.只允许在端点处插入和删除元素D.没有共同点栈是限定在(C)处进行插入或删除操作的线性表。

A．端点B．栈底C．栈顶D．中间栈是一个(B)线性表结构。

A．不加限制的B．加了限制的C．推广了的D．非栈与一般线性表区别主要在方面(D)。

A．元素个数B．元素类型C．逻辑结构D．插入、删除元素的位置四设串s1=’ABCDEFG’,s2=’PQRST’,函数con(x,y)返回x和y串的连接串,subs(s,i,j)返回串s的从序号i的字符开始的j个实际字符组成的子串,len(s)返回串s的长度,那么con(subs(s1,2,len(s2)),subs(s1,len(s2),2)的结果是(D)。

A.BCDEFB.BCDEFGC.BCPQRSTD.BCDEFEF串是任意有限个〔C〕

A符号构成的序列B符号构成的集合C字符构成的序列D字符构成的集合设有两个串p和q,求q在p中首次出现的位置的运算称作(B)

A.连接B.模式匹配C.求子串D.求串长说串是一种特殊的线性表，那么其特殊性表现在(C)。

A.串是可以顺序存储的B.串是可以链接存储的

C.串中的每一个结点由一个字符组成D.串中的结点是多个字符组成的五常对数组进行的两种根本操作是(C)。

A.建立与删除B.索引和修改C.查找和修改D.查找和索引对矩阵压缩存储是为了〔B〕。

A.方便运算B.节省时间C.方便存储D.提高运算速度二维数组M的成员是6个字符〔每个字符占一个存储单元〕组成的串，行下标I的范围从0到8，列下标j的范围从1到10，如M按行优先方式存储，元素M[8][5]的起始位置与当M按列优先方式存储时的(B)元素的起始地址一致。

A.M[8][5]B.M[3][10]C.M[5][8]D.M[0][9]二维数组M的成员是6个字符〔每个字符占一个存储单元〕组成的串，行下标I的范围从0到8，列下标j的范围从1到10，那么M的第8列和第5行共占(A)个字节。

A.108B.114C.54二维数组M的成员是6个字符〔每个字符占一个存储单元〕组成的串，行下标I的范围从0到8，列下标j的范围从1到10，那么存在M至少需要(D)个字节。

A.90B.180C.240二维数组M的元素是4个字符〔每个字符占一个存储单元〕组成的串，行下标I的范围从0到4，列下标j的范围从0到5，M按行存储时元素M[3][5]的起始地址与M按列存储时元素(B)的起始地址相同。

A.M[2][4]B.M[3][4]C.M[3][5]D.M[4][4]假设采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点(B)。

A.正确B.错误设矩阵A是一个对称矩阵，为了节省空间，将其下三角矩阵按行序存放在一维数组B[1，n〔n+1〕/2]中，对下三角局部中任一元素aij〔i≥j〕，在一维数B中下标k的值是(B)。

A．i〔i-1〕/2+j-1B．i〔i-1/2+jC．i〔i+1〕/2+j-1D．i〔i+1〕/2+j数组A中，每个元素A的长度为3个字节，行下标I从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数是(C)。

A.50B.100C.240数组A中，每个元素A的长度为3个字节，行下标I从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A[5][8]的起始地址为__B__。

A.SA+141B.SA+180C.SA+141D.数组A中，每个元素A的长度为3个字节，行下标I从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为(C)。

A.SA+141B.SA+144C.SA+222D.数组的根本操作主要包括(C)。

A．建立与删除B．索引与修改C．访问与修改D．访问与索引稀疏矩阵一般的压缩存储方法有两种，即(C)。

A.二维数组和三维数组B.三元组和散列C.三元组和十字链D.散列和十字链表判断题1．线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。()2．采用线性探测法处理冲突的散列表中，所有同义词〔其冲突的元素〕在表中相邻。 (×)3．调用一次深度优先遍历可以访问到图中的所有顶点。 (×)4．调用一次广度优先遍历可以访问到图中的所有顶点。 (√)5．堆是完全二叉树，完全二叉树不一定是堆。 (×)6．对链表进行插入和删除操作时不必移动链表中结点。 (√)7．分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。 (√)8．快速排序是排序算法中平均性能最好的一种排序。 (√)9．满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树(√)10．冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。 (√)11．任何有向网拓扑排序的结果是唯一的。 (×)12．入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。 (×)13．假设一个叶子结点是某二叉树的中序遍历序列的最后一个结点，那么它必是该二叉树的先序遍历序列中的最后一个结点。 (√)14．设一棵二叉树的先序序列和后序序列，那么能够唯一确定出该二叉树的形状。 ()15．设一棵树T可以转化成二叉树BT，那么二叉树BT中一定没有右子树。 ()16．顺序表查找指的是在顺序存储结构上进行查找。 ()17．算法的效率越高越好。 ()18．外部排序过程主要局部分为两个阶段：生成初始归并段和对归并段进行逐趟归并。 ()19．希尔排序算法的时间复杂度为O(n^2)。 ()20．线性表的顺序存储结构比链式存储结构更好。 ()21．用邻接矩阵法存储图时，所占用的空间大小仅与图中结点个数有关。 ()22．用邻接矩阵作为图的存储结构时，那么其所占用的存储空间与图中顶点数无关而与图中边数有关。 ()23．有向图的邻接表和逆邻接表中表结点的个数不一定相等。()24．栈和队列的存储方式既可是顺序方式，也可是链接方式。()25．中序遍历二叉排序树可以得到一个有序的序列。 ()26．子串“ABC”在主串“AABCABCD”中的位置为2。 ()完成以下操作(二)

15．设无向图G如以下图所示，给出该图的最小生成树上边的集合并计算最小生成树各边上的权值之和。

16．设有无向图G，要求给出用普里姆算法(克鲁斯卡尔算法，两个算法都做)构造最小生成树所走过的边的集合。

三、思考以下算法设计设计一个算法，功能是在带头结点的单链表head中删除数据域值最小的结点。structNode

{

int

Data;

Node*next;

};

void

deleteNode(Node*head,intKeyData)

//KeyData需要删除的结点的值

{

Node*p=head;

while(p->next!=NULL)

{

if(p->next->Data==KeyData)

p->next=p->next->next;

p=p->next;

}}有一种简单的排序算法，叫做计数排序〔countsorting〕。这种排序算法对一个待排序的表〔用数组表示，表中所有待排序的关键字互不相同〕进行排序，并将排序结构存放到另一个新的表中。计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键字比该记录的关键字小。假设对某一个记录，统计出计数值为C，那么，这个记录在新的有序表中的适宜的存放位置即为C。实现计数排序的算法。试以单链表为存储结构实现简单项选择择排序的算法。voidLinkList_Select_Sort(LinkList&L)//单链表上的简单项选择择排序算法{for(p=L;p->next->next;p=p->next)

{

q=p->next;x=q->data;

for(r=q,s=q;r->next;r=r->next)//在q后面寻找元素值最小的结点

if(r->next->data<x)

{

x=r->next->data;

s=r;

}

if(s!=q)//找到了值比q->data更小的最小结点s->next

{p->next=s->next;s->next=q;

t=q->next;q->next=p->next->next;

p->next->next=t;

}//交换q和s->next两个结点

}//for}//LinkList_Select_Sort编写一个双向起泡的排序算法，即相邻两趟向相反方向起泡。voidBubble_Sort2