数据结构习题集_答案.doc

《数据结构习题集_答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、郑州航空工业管理学院《数据结构》习题集第1章绪论1、填空题(1)常见的数据结构有集合、_线性__结构，__树___结构，__图__结构等三种。(2)常见的存储结构有__顺序存储___结构，__链式存储___结构等两种。(3)数据的基本单位是_数据元素__，它在计算机中是作为一个整体来处理的。(4)数据结构中的结构是指数据间的逻辑关系，常见的逻辑结构可分为两大类：__线性结构____和__非线性结构___。2、选择题(1)数据结构是一门研究非数值计算的程序设计中计算机的A以及它们之间的C和运算等的学科。（A）数据元素（B）计算方法（C）关系（D）数据映像(2)在数据

2、结构中，与所使用的计算机无关的是数据的A结构。（A）逻辑（B）存储（C）物理（D）逻辑与存储3、应用题(1)、给出以下算法的时间复杂度.voidfun(intn){inti=1,k=100;while(i

3、__顺序_表，另一种是___链___表。(2)顺序表采用__随机___访问机制对数据元素进行访问。(3)若在单链表结点p的后面插入一个新的结点s，则其操作序列为:①____s->next=p->next_____________；②___p->next=s___________________；(4)在单向链表中，若要删除某个结点p，一般要找到__p的直接前驱__结点，才能实现该操作。2、选择题(1)将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是A。(A)n(B)2n－1(C)2n(D)n-1(2)在单链表中，如果在结点p之后插入一个新结点s，其操

4、作为A。（A）s->next=p->next;p->next=s;（B）p->next=s;s->next=p->next;（C）s->next=p;p->next=s->next;（D）p->next=s;s->next=p;(3)若长度为n的线性表采用顺序存储结构，在其第i个位置删除一个元素的算法的平均时间复杂度为(C)。(1≤i≤n)(A)．O(0)(B)．O(1)(C).O(n)(D)．O(n2)(4)若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素需要移动的元素个数为(B)。(1≤i≤n+1)(A)．n-i(B)．n-i+1(C).I(D

5、)．n-i-13、判断题(1).线性表中每一个元素都有一个前驱和一个后继。（错）第3章栈和队列1、填空题(1).栈和队列在本质上都是操作受限的_线性表__________。(2).栈的操作特点是__后进先出_。队列的操作特点是_先进先出__。2、选择题(1).消除递归不一定需要使用栈，此说法__A____。(A).正确(B).错误(2).一个栈的进展序列为（1，2，3，4），则不可能得到的输出序列是__D____。(A)（1，2，3，4）(B)（4，3，2，1）(C)（1，3，4，2）(D)（3，1，2，4）(3).用单循环链表表示队列，正确的说法是B。(A)可设

6、一个头指针使入队、出队都方便；(B)可设一个尾指针使入队、出队都方便；(C)必须设头尾指针才能使入队、出队都方便；(D)无论如何,只可能使入队方便。3、判断题(1).栈的特点是先进先出。（错）(2).可以在队列的任意位置插入元素。（错）(3).递归程序化非递归程序必须用到栈。（错）(4).如果进栈的序列为（1，2，3，4），则（4，2，3，1）不可能是出栈序列。（对）(5).在用顺序表表示的循环队列中，可以设一个变量L作为标志位来区分队空或队满的条件，当L==0时表示队列为空，等L的值为空间的大小时表示队列为满。（对）(6).当用数组做为栈的存储结构时，应把栈顶设

7、在高地址哪一端，这样入栈、出栈不需要移动其他元素。（对）(7).当用单链表作为栈的存储结构时，应把栈顶设置链表的头部，这样入栈、出栈不需要移动其他元素。（对）第4章串1、选择题(1).串是任意有限个（D）(A).符号构成的序列(B).符号构成的集合(C).字符构成的集合(D).字符构成的序列(2).串是一种特殊的线性表，其特殊性体现在（B）(A).可以顺序存储(B).数据元素是一个字符(C).可以连接存储(D).数据元素可以是多个字符(3).以下（D）是“abcd321ABCD”的子串。(A).abcd(B).321AB(C).“abcABC”(D).“21AB”

8、(4).两