《数据结构14章复 习题 答案资料》由会员分享，可在线阅读，更多相关《数据结构14章复 习题 答案资料（6页珍藏版）》请在金锄头文库上搜索。
1、一、选择题。1. 算法的计算量的大小称为计算的（ b ）。A效率 B. 复杂性 C. 现实性 D. 难度2.计算机算法指的是（1c），它必须具备（2b） 这三个特性。(1) A计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法(2) A可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 3. 下面关于算法说法错误的是（ d ）A算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的4. 下面说法错误的是（ c ） (1）
2、算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A(1) B.(1),(2) C.(1),(4) D.(3)5从逻辑上可以把数据结构分为（ c ）两大类。A动态结构、静态结构 B顺序结构、链式结构 C线性结构、非线性结构 D初等结构、构造型结构6程序段 For(i=n-1;i0;i-) For(j=1;jaj+1)ajaj+1其中 n为正整数，则最后一行的语句时间复杂度在最坏情况下是（ d ）A
3、. O（n） B. O(nlogn) C. O(n3) D. O(n2) 7下述哪一条是顺序存储结构的优点？（ a ）A存储密度大 B插入运算方便 C删除运算方便 D可方便地用于各种逻辑结构的存储表示8下面关于线性表的叙述中，错误的是哪一个？（ b ）A线性表采用顺序存储，必须占用一片连续的存储单元。B线性表采用顺序存储，便于进行插入和删除操作。C线性表采用链接存储，不必占用一片连续的存储单元。D线性表采用链接存储，便于插入和删除操作。9若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ a ）存储方式最节省时间。A顺序表 B双链表 C带头结点的双循环链表 D单
4、循环链表11. 链表不具有的特点是（ b ） A插入、删除不需要移动元素 B可随机访问任一元素 C不必事先估计存储空间 D所需空间与线性长度成正比12.单链表的一个存储结点包含（d） A数据域或指针域 B指针域或链域 C指针域和链域 D数据域和链域14. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ c ）。AO(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1)15.设REAR是指向非空带头结点的循环单链表的尾指针,则删除表首结点的操作可表示为( d )A.p=rear; B.rear=rear-next;rear=rear-nex
5、t; free(rear);free(p)C.rear=rear-next-next; D. p=rear-next-next;free(rear); rear-next-next=p-next; free(p); 16带头结点的单链表Head为空的判定条件是 bA.Head=Null B.Head-next=NULL C.Head-next=HeadDHead-data=NULL17.非空的单循环链表L的尾结点*P,满足 cA.P-next=NULL B.P=NULL C. P-next=L D.P=L.18.双向链表结点结构如下： LLink dataRLink其中：LLink是指向前驱结
6、点的指针域：data是存放数据元素的数据域；Rlink是指向后继结点的指针域。下面给出的算法段是要把一个新结点*Q作为非空双向链表中的结点*p的前驱，插入到此双向链表中。不能正确完成要求的算法段是 cA.Q-LLink=P-LLink; B.P-LLink=Q;Q-Rlink=P; Q-Rlink=P;P-LLink=Q; P-LLink-Rlink=Q;P-LLink-Rlink=Q; Q-LLink=P-LLink;C.Q-LLink=P-LLink;Q-Rlink=P;P-LLink-Rlink=Q;P-LLink=Q;D.Q-LLink=P.-LLink; Q-Rlink=P;P-Ll
7、ink=Q;Q-Llink-Rlink=Q;19.线性结构中的一个结点代表一个数据元素，通常要求同一线性结构的所有结点所代表的数据元素具有相同的特性，这意味着 cA.每个结点所代表的数据元素都一样。B.每个结点所代表的数据元素包含的数据项的个数要相等C.不仅数据元素包含的数据项的个数要相同，而且对应数据项的类型要一致D.结点所代表的数据元素有同一特点1. 对于栈操作数据的原则是（ b ）。A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序2. 在作进栈运算时,应先判别栈是否( b ),在作退栈运算时应先判别栈是否( a )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容
8、量为( 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. 两个栈的栈顶在栈空间的某一位置相遇. D. 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底.3. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法
9、的出栈序列？（ 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 4. 输入序列为ABC，可以变为CBA时，经过的栈操作为（ b ）A. push,pop,push,pop,push,pop B. push,push,push,pop,pop,pop C. push,push,pop,pop,push,pop D. push,pop,push,push,pop,pop5. 设计一个判别表达式中左，右括号是否配对出现的算法，采用（ d ）数据结构最佳。A线性表的顺序存储结构 B. 队列 C. 线性表的链式存储结构 D.
10、栈6. 用链接方式存储的队列，在进行删除运算时（ d ）。A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改7. 循环队列存储在数组A0.m中，则入队时的操作为（ d ）。A. rear=rear+1 B. rear=(rear+1) mod (m-1) C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1) 8. 最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是 （ b ）。 A. (rear+1) MOD n=front B. rear=front Crear+1=front D
11、. (rear-l) MOD n=front9. 栈和队列的共同点是（ c ）。A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点10. 栈的特点是（ b ）,队列的特点是（ a ）,栈和队列都是（ c ）。若进栈序列为1,2,3,4 则（ c ）不可能是一个出栈序列（不一定全部进栈后再出栈）；若进队列的序列为1,2,3,4 则（ f ）是一个出队列序列。, : A. 先进先出 B. 后进先出 C. 进优于出 D. 出优于进: A.顺序存储的线性结构 B.链式存储的线性结构 C.限制存取点的线性结构 D.限制存取点的非线性结构, : A. 3,2,1,
12、4 B. 3,2,4,1 C. 4,2,3,1 D. 4,3,2,1 F. 1,2,3,4 G. 1,3,2,411. 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是( c )。A 6 B. 4 C. 3 D. 2二、判断题。1. 数据元素是数据的最小单位。( f )2算法的优劣与算法描述语言无关，但与所用计算机有关。( f )3健壮的算法不会因非法的输入数据而出现莫名其妙的状态。( t )4. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( f )5. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构. ( f )6. 链表中的头结点仅起到标识的作用。( f ) 7线性表采用链表存储时，结点和结点内部的存储
