《练习题1-6章(含答案)》由会员分享，可在线阅读，更多相关《练习题1-6章(含答案)（14页珍藏版）》请在金锄头文库上搜索。
1、习题练习第一章1. 算法的计算量的大小称为计算的（ B ）。A效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于（ c）A问题的规模 B. 待处理数据的初态 C. A和B3.计算机算法指的是（1c），它必须具备（2b） 这三个特性。(1) A计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法(2) A可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 4一个算法应该是（ b ）。 A程序 B问题求解步骤的描述 C要满足五个基本特性 DA和C. 5、下面属于逻辑结构的是（ c ）A 顺序表
2、B哈希表 C 有序表 D 单链表6、某算法的时间复杂度为O(n2)，表明该算法的（c）A 问题规模是n2 B执行时间等于n2C 执行时间与n2成正比 D问题规模与n2成正比7、下面关于算法说法错误的是（ c ）A算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的8从逻辑上可以把数据结构分为（ c ）两大类。A动态结构、静态结构 B顺序结构、链式结构 C线性结构、非线性结构 D初等结构、构造型结构9以下与数据的存储结构无关的术语是（ d ）。A循环队列 B. 链表 C. 哈希表 D. 栈10以下数据结
3、构中，哪一个是线性结构（ d ）？ A广义表 B. 二叉树 C. 稀疏矩阵 D. 串11以下那一个术语与数据的存储结构无关？（ a ）A栈 B. 哈希表 C. 线索树 D. 双向链表12在下面的程序段中，对x的赋值语句的频度为（ c ）FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1;A O(2n) BO(n) CO(n2) DO(log2n) 14以下数据结构中，（ a ）是非线性数据结构A树 B字符串 C队 D栈15. 下列数据中，（ c ）是非线性数据结构。A栈 B. 队列 C. 完全二叉树 D. 堆16连续存储设计时，存储单元的地址（ a ）。A一定连续
4、 B一定不连续 C不一定连续 D部分连续，部分不连续17以下属于逻辑结构的是（ c ）。A顺序表 B. 哈希表 C.有序表 D. 单链表 二、问答：1. 数据结构是一门研究什么内容的学科？ 2. 数据元素之间的关系在计算机中有几种表示方法？各有什么特点？ 3. 数据类型和抽象数据类型是如何定义的。二者有何相同和不同之处，抽象数据类型的主要特点是什么？使用抽象数据类型的主要好处是什么？ 4. 回答问题（1）在数据结构课程中，数据的逻辑结构，数据的存储结构及数据的运算之间存在着怎样的关系？（2）若逻辑结构相同但存储结构不同，则为不同的数据结构。这样的说法对吗？举例说明之。（3）在给定的逻辑结构及其
5、存储表示上可以定义不同的运算集合，从而得到不同的数据结构。这样说法对吗？举例说明之。5评价一个好的算法，您是从哪几方面来考虑的？第二章1下述哪一条是顺序存储结构的优点？（ a ）A存储密度大 B插入运算方便 C删除运算方便 D可方便地用于各种逻辑结构的存储表示2下面关于线性表的叙述中，错误的是哪一个？（ b ）A线性表采用顺序存储，必须占用一片连续的存储单元。B线性表采用顺序存储，便于进行插入和删除操作。C线性表采用链接存储，不必占用一片连续的存储单元。D线性表采用链接存储，便于插入和删除操作。3线性表是具有n个（ c ）的有限序列（n0）。A表元素 B字符 C数据元素 D数据项 E信息项4若
6、某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ a ）存储方式最节省时间。A顺序表 B双链表 C带头结点的双循环链表 D单循环链表5某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ d ）存储方式最节省运算时间。A单链表 B仅有头指针的单循环链表 C双链表 D仅有尾指针的单循环链表6若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（ d ）存储方式最节省运算时间。A单链表 B双链表 C单循环链表 D带头结点的双循环链表7. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复
7、杂度为（ c ）(1=iLlink=q;q-Rlink=p;p-Llink-Rlink=q;q-Llink=q；B. p-Llink=q;p-Llink-Rlink=q;q-Rlink=p;q-Llink=p-Llink;C. q-Rlink=p;q-Llink=p-Llink;p-Llink-Rlink=q;p-Llink=q;D. q-Llink=p-Llink;q-Rlink=q;p-Llink=q;p-Llink=q;20在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（ b）。Ap-next=s;s-next=p-next; B s-next=p-next;p-next=
8、s;Cp-next=s;p-next=s-next; D p-next=s-next;p-next=s;25对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ b ）Ahead=NULL Bheadnext=NULL Cheadnext=head Dhead!=NULL二、算法设计：1. 插入算法，在带有头结点的单链表La中第i个元素之前插入e。2. 删除算法，删除带有头结点的单链表La中第i个元素3. 将两个有序的带有头结点单链表和进行合并成一个有序的单链表算法4. 将链表进行逆置等操作。5. 已知非空线性链表由list指出，链结点的构造为（data,link）.请写一算法
9、，将链表中数据域值最小的那个链结点移到链表的最前面。要求：不得额外申请新的链结点。6. (6) 有一个单链表L（至少有1个结点），其头结点指针为head，编写一个过程将L逆置，即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。7. 在一个递增有序的线性表中，有数值相同的元素存在。若存储方式为单链表，设计算法去掉数值相同的元素，使表中不再有重复的元素。例如：（7，10，10，21，30，42，42，42，51，70）将变作（7，10，21，30，42，51，70），分析算法的时间复杂度。第三章1. 对于栈操作数据的原则是（b ）。A. 先进先出 B. 后进先出 C. 后进
10、后出 D. 不分顺序2. 在作进栈运算时,应先判别栈是否( b ),在作退栈运算时应先判别栈是否( a )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( b )。为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的 ( d )分别设在这片内存空间的两端,这样,当( c )时，才产生上溢。 , : A. 空 B. 满 C. 上溢 D. 下溢 : A. n-1 B. n C. n+1 D. n/2 : A. 长度 B. 深度 C. 栈顶 D. 栈底 : A. 两个栈的栈顶同时到达栈空间的中心点.B. 其中一个栈的栈顶到达栈空间的中心点. C.
11、 两个栈的栈顶在栈空间的某一位置相遇. D. 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底.3. 一个栈的输入序列为123n，若输出序列的第一个元素是n，输出第i（1=i=n）个元素是（ b ）。A. 不确定 B. n-i+1 C. i D. n-i4. 若一个栈的输入序列为1,2,3,n，输出序列的第一个元素是i，则第j个输出元素是（ d ）。i-j+1 A. i-j-1 B. i-j C. j-i+1 D. 不确定的5. 若已知一个栈的入栈序列是1,2,3,n，其输出序列为p1,p2,p3，pN,若pN是n，则pi是( d )。 A. i B. n-i C. n-i+1 D. 不确定6. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ c ）A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 8. 一
