数据结构习题

第一章 习题

一．填空题

１、数据结构被形式地定义为（D, R），其中D是 的有限集合，R是D上的 有限集合。 ２、数据结构按逻辑结构可分为两大类，它们分别是 和 。 ３、线性结构中元素之间存在 关系，树形结构中元素之间存在 关系，图形结构中元素之间存在 关系。

４、一个算法的效率可分为 效率和 效率。

５、简单地说，一个算法所进行的计算次数的多少称为 ，一个算法所需要辅助存储空间的多少称之为 。 ６、根据数据元素之间关系的不同特性，通常有四类基本结构，它们是集合、 、 、 。 二．选择题

１、算法分析的目的是（ ）

A、找出数据结构的合理性 B、 研究算法中的输入和输出的关系 C、分析算法的效率以求改进 D、分析算法的易懂性和文档性 ２、算法分析的两个主要方面是（ ）

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

C、可读性和文档性 D、 数据复杂性和程序复杂性 ３、计算机算法指的是（ ）

A、计算方法 B、排序方法 C、 解决问题的有限运算序列 D、 调度方法 ４、计算机算法必须具备输入、输出和（ ）等5个特性。

A、可行性、可移植性和可扩充性 B、 可行性、确定性和有穷性 C、 确定性、有穷性和稳定性 D、 易读性、稳定性和安全性 ５、数据元素是数据的基本单位，其内（ ）数据项。

A、只能包含一个 B、不包含 C、可以包含多个 D、必须包含多个 ６、逻辑关系是指数据元素间的（ ） Ａ、类型 Ｂ、存储方式 Ｃ、结构 Ｄ、数据项 ７、数据结构有（ ）种基本逻辑结构。 A、１ B、２ C、３ D、４

８、下列四种基本的逻辑结构中，数据元素之间关系最弱的是（ ）。 A、集合 B、线性结构 C、树形结构 D、图状结构 ９、一个存储结构点存储一个（ ）。

A、 数据项 B、数据元素 C、数据结构 D、数据类型

10、某算法的时间复杂度为O(2n)，表明该算法的（ ）

A、问题规模是2n B、执行时间等于2n C、执行时间与2n成正比 D、问题规模与2n成正比 11、算法执行时间一般与（ ）无关。

A、 问题规模大小 B、计算机的档次 C、程序设计语言的种类或版本D、算法设计者的水平 12、算法分析的主要任务是分析算法（ ） A、 是否具有较好的可读性 B、是否存在语法错误 C、功能是否符合设计要求 D、执行时间和问题规模之间的关系。 13、下列时间复杂度中最坏的是（ ） A、O(1) B、O(n) C、O(log2n) D、O(n2) 14、下列算法的时间复杂度是（ ） D for(i=0;i

A、 O(1) B、O(n) C、O(log2n) D、O(n2) 15、算法的可读性是指（ ）

A、算法所含语句数较少 B、算法较简单，计算机容易编译 C、算法较简单，很容易看出它的执行结果 D、算法结

1

构清晰，容易被算法设计者及其他人看懂 三．简答题

1.数据结构中有哪几类数据结构？哪种关系最简单？哪种关系最复杂？

2.简述顺序存储结构与链式存储结构在表示数据元素之间关系上的主要区别。 3.数据与数据元素有何区别？二者有什么关系？

第二章 习题

一．判断题。

1.存储一个线性表所需的内存空间大小与线性表的元素类型无关。（ ） 2.顺序表的长度等于元素个数与每个元素所占内存单元数之乘积。（ ） 3.分配给顺序表的内在单元地址一定是连续的。（ ）

4.长度是n的顺序表中删除一个元素，所需的时间都是O(n)。（ ） 5.往顺序表中插入一个元素，平均要移动大约一半的元素。（ ） 6.分配给单链表各结点的内存单元地址必须是连续的。（ ） 7.单链表中的结点只有后继，没有前驱。（ ） 8.在链式结构存储的线性表上不能实现随机访问。（ ） 9.空单链表表示的是长度为零的线性表。（ ）

10.在对带头结点的单链表进行插入操作时，永远不会改变头指针的值。（ ） 11. 在描述链表的结点类型时，必须先描述数值字段，再描述指针字段。（ ） 12. 在循环单链表中，任何一个结点的指针字段值都不可能为空（ ） 二．填空题。

1.链表中逻辑上相邻的元素的物理位置（ ）相连。

2.单链表中，除头结点外，任何结点的存储位置都由其（ ）结点的指针指示。

3.已知带表头结点的单链表L，指针p指向L链表中的某个结点，指针q是指向L链表外的一个结点，则：

①在指针p所指结点后插入q所指结点的语句序列是（ ）； ②在指针p所指结点前插入q所指结点的语句序列是( )； ③将q所指结点插入在链表首结点的语句序列是（ ）； ④将q所指结点插入在链表尾结点的语句序列是（ ）； 4.已知带头结点的单链表L，指针p指向L链表中的一个结点（非首结点，非尾结点）则：

①删除指针p所指结点的直接后继结点的语句是（ ）； ②删除指针p所指结点的直接前驱结点的语句序列是（ ）； ③删除指针p所指结点的语句序列是（ ）； ④删除第一个结点的语句序列是（ ）； ⑤删除最后一个结点的语句序列是（ ）；

5.线性表的存储结构有（ ）和（ ）存储两种。

6.线性表的每个元素需4个字节存储，在顺序存储结构下LOC(ai)=1000,则LOC(ai+2)=( )。 7.往长度为n的顺序表中插入一个新元素，最多需要移动（ ）个元素。

8.若用带头结点的单向链表来表示长度为n的线性表，则需要为链表分配（ ）个结点的存储空间。 9.在顺序表的（ ）之后插入新元素，不需要移动任何元素。

10.线性表的元素长度为L，在顺序存储结构下LOC（ai）=LOC(a1)+( ) 11.在单链表中，删除指针q所指结点的直接后继结点，需要执行以下语句序列：p=q->next;( );free(p); 12.在删除每个元素的概率相等的情况下，从长度为n的顺序表中删除一个元素平均要移动（ ）个元素。 13.在长度为n的顺序表中实现定位操作，其算法的时间复杂度为（ ）

14.逻辑上相邻的元素在存储位置上也相邻，这是（ ）结构存储结构的特点。 三．选择题

2

1.一个顺序表所占存储空间的大小与（ ）无关。

A.顺序表长度 B.结点类型 C.结点中各字段的类型 D.结点的存放顺序 2.在程序中，为了设置一个空的顺序表，必须（ ）。

A.给各数组元素赋空值 B.给各顺序表元素赋空值 C.给表示顺序表长度的变量赋初始值 D.给数组变量名赋初始值 3.线性表中有2n个元素，以下算法中，在顺序表上实现比在链表上实现效率高的是（ ）。

A.输出第i个元素的值 B.交换第1个和第二个元素的值 C.顺序输出这2n个元素的值 D.输出与某个给定值x相等的元素在线性表中的序号

4.单链表所占用的内在单元地址一定是（ ）。 A.无序的 B.连续的 C.不连续的 D.部分连续的 5.以下说法正确的是（ ）。

A.线性表的逻辑顺序与存储顺序总是一致的 B.线性表的链式存储结构中，内存中可用的存储单元可以是连续的，也可以不连续 C.线性表的顺序存储结构优于链式存储结构 D.每种数据结构具有插入、删除和查找三种基本运算。 6.L是线性表，已知ListLength(L)的值是5，经过运算DeleteList(L,2)后ListLength(L)的值是（ ）。 A. 5 B. 3 C. 4 D. 6

7.线性表中有一个直接前驱和直接后继的是（ ）。 A. 首元素 B.尾元素 C.中间的元素 D.所有的元素 8.指针p指向循环链表L的首元素的条件是（ ）。 A.p==L B.p->next==L C.L->next==p D.p->next==NULL 9.线性表中各元素的关系是（ ）。 A.序偶关系 B.层次关系 C.网状关系 D.集合

10.单链表中每个结点中有（ ）个指针。 A. １ B. ２ C. ０ D. ３

11.指针p和q分别指向单链表的两个元素，p指针所指向元素是q所指向元素的前驱的条件是（ ）。 A. p->next==q B. q->next==p C. p==q D. p->next==q->next

12.指针p和q分别指向双向链表的两个元素，p指针所指向元素是q所指向元素的后继的条件是（ ）。 A. p==q B. q->next==p C. p->next==q D.q->next==p->next

13.在长度为n的顺序表的第i个(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为（ ）。 A.i-1 B. i C. n-i D.n-i+1

14.对于只在表的首尾两端进行插入操作的线性表，宜采用的存储结构为（ ）。 A.顺序表B.用头指针表示的单循环链表C.用尾指针表示的单循环链表D.单链表 15. 在单链表中，增加头结点的目的是为了（）。

A.使单链表至少有一个结点 B.表示表结点中首结点的位置 C.方便运算的实现D.说明单链表是线性表的链式存储实现 四．简答题

1.什么情况下使用顺序表比使用链表好？

顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。 2.已知带头结点的单链表H，简述下列算法的功能。

Int func(LinkNode *H) {

if(H->next&&H->next->next) {

q=H->next; H=q->next; p =q;

while(p->next) p=p->next; p->next=q; q->next=NULL;

3

}

return OK; }

将第一个结点变成最后一个结点，去掉头结点。 3.已知线性表L＝（A，B，C，D），请画出该线性表存储在顺序表、单链表、循环链表、双向循环链表的示意图。 4.线性表的主要操作有哪些？

5.请给出求单链表H的长度的算法。

6.请给出依次输出单链表H中各结点值的算法。

7.若A和B是两个按结点值升序排列的有序循环链表，试给出将A、B按升序存储合并成循环链表C的算法。 8.线性表的顺序存储和链式存储各有什么特点？

9.若顺序表A中的数据元素按降顺排列，要将x插入到顺序表中的合适位置，以保证表的有序性，试给出其算法。 10.请给出删除单链表H中值为K的结点的算法。

第三章 栈和队列

一． 判断题

1.顺序栈中元素值的大小是有序的。（）

2.栈是一种对删除和插入位置做了限制的线性表。（） 3.进栈越早的元素出栈越晚。（）

4.顺序栈的最大容量是m，则对栈的进栈、出栈操作最多只能进行m次。（） 5.对顺序栈进行进栈、出栈操作，不会涉及元素的前、后移动问题。（） 6.栈顶元素和栈底元素有可能是同一个元素。（） 7.空栈没有栈顶指针。（）

8.对于非空栈来说，栈顶元素和栈底元素都是唯一的。（） 9.栈底元素是不能删除的元素。（）

10.与顺序栈相比，链栈通常不会出现栈满的情况。（）

11.队列是一种先进后出的线性表，栈是一种先进先出的线性表。（） 12.n个元素进队的顺序和出队的顺序总是一致的。（）

13.无论是顺序队还是链队，插入、删除操作的时间复杂度都是O(1)。（）

14.若用不带头结点的非循环单链表来表示链式队列，则可以用“队首指针和队尾指针相等”作为队空的标志。（） 15.队列中的元素个数，可以根据队首指针和队尾指针的值来计算。（） 16.循环队列是顺序结构，不会产生上溢或下溢。（）

17.循环队列队空的条件是头指针和尾指针都指向头结点。（） 18.循环队列满的条件是：q->rear - q->front==maxsize。（） 19.链队列队空的条件是：q->rear==q->front。（） 20.循环队列没有队头元素和队尾元素。（） 二． 填空题

1.栈是一种具有（ ）特性的线性表，队列是一种具有（ ）特性的线性表。 2.如果栈的长度难以估计，最好使用（ ）存储结构。

3.若用带头结点的单链表来表示栈，则栈空的标志是（ ）

4.若用s[0]~s[m-1]作为顺序栈的存储空间，栈空的标志是栈指针top的值等于m,则每进行一次（ ）操作，需将top的值加１，每进行一次（ ）操作，将top的值减一。

5.若用带头结点的单链表来表示链式栈，由创建一个空栈所要执行的操作是（ ）。 6.栈和队列的区别仅在于（ ）。

7.若用q[0]~q[99]作为循环队列的存储空间，q[f]、q[r]分别表示队首元素和下一个插入位置，则当f=80,r=30时，队列中共有（ ）个元素。

4

8.顺序队列在实现的时候，通常将数组看成是一个首尾相连的环，这样做的目的是为了避免产生（ ）现象。

9.栈的存储结构主要有（ ）和（ ）。

10.即使知道队首指针和队尾指针，也无法计算得出元素个数的队列，一定是（ ）存储结构的队列。

11.如果程序处理的数据是逐步产生的，如果要求处理数据元素的顺序和产生的数据元素的顺序正好相反，则通常用（ ）暂存待处理的数据。

12.顺序栈和链栈的区别仅在于（ ）的不同。

13.对栈执行删除操作时，只有在（ ）的情况下，才会将栈底元素删除。

14.若用带头结点的单向链表来表示链接栈，则创建一个空栈所要执行的操作是（ ）。 15.若用q[0]~q[m-1]表示非循环队列的存储空间，则最多只能执行（ ）入队操作。

16.若用q[0]~q[99]表示循环队列的存储空间，q[r]表示队尾元素，q[f]表示队首元素的前一个位置，则当f=60,r=0时，队列中共有（ ）元素。

17. 若用q[0]~q[m-1]表示循环队列的存储空间，q[r]表示队尾元素，q[f]表示队首元素的前一个位置，则可以（ 作为队空的标志，与此相对应，可用（ ）作队满的标志。 18.在队列的顺序存储结构中当插入一个新的元素时，队尾指针（ ），当删除一个队列元素时，队首指针（ 19.已知顺序栈S，入栈操作之前应判断（ ），出栈操作之前需要判断（ ）。 20.s[0]~s[m-1]表示栈的存储空间，栈顶指针为top=0表示栈空，则栈满的条件是（ ）。 三． 选择题

1.栈是限定在 处进行插入或删除操作的线表。 A.端点 B.栈底 C.栈顶 D.中间

2.在栈顶一端可以进行的全部操作是 。 A. 插入 B.删除 C.插入和删除 D.进栈

3.有４个元素按Ａ、B、C、D顺序连续进栈，执行pop(s,x)后，x的值是 。 A. A B. B C. C D. D

4.同一个栈类各元素的类型 。

A.必须一致 B.可以不一致 C.不能一致 D.不必一致 5.顺序栈存储空间的实现使用 。 A.链表 B.数组 C.循环链表 D.变量

6.一个顺序栈一旦说明，其占用空间的大小 。 A.已固定 B.可以改变 C.不能固定 D.动态变化 7.栈是一个 线性表。

A.不加限制的 B.对插入和删除位置加了限制的 C.推广了的 D.非 8.栈与一般线表的区别主要在 方面。

A.元素个数 B.元素类型 C.逻辑结构 D.插入、删除元素的位置 9.队列是限定在 处进行插入操作的线性表。 A. 端点 B.队头 C.队尾 D.中间 10.队列的特点是 。

A.先进先出 B.后进先出 C.先进后出 D.不进不出

11.设有一个栈，元素依次进栈的顺序为abcde。下面是不可能的出栈序列。 A. abcde B.bcdea C.eabcd D.edcba

12.如果以链表作为栈的存储结构，则退栈操作时 。

A.必须判断栈是否为满 B.判断栈元素的类型C.必须判断栈是否为空D.不作任何判断

13.设S[m]为循环队列的存储空间，f为队头指针，r为队尾指针，则执行出队操作的语句是 。 A.f=f+1 B.f=(f+1)%m C.r=(r+1)% m D.r=r+1

14.一个队列的入队顺序是abcd，则离队的顺序是 。 A.adcb B.abcd C.dcba D.cbda

15. 设S[m]为顺序栈的存储空间，则判断栈满的条件是 。

）。 5

）

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构习题在线全文阅读。