《第1-3章复习题及参考答案》由会员分享，可在线阅读，更多相关《第1-3章复习题及参考答案（9页珍藏版）》请在金锄头文库上搜索。
1、第1-3章 复习题数据构造与算法复习题一、选择题。在数据构造中，从逻辑上可以把数据构造分为 C 。A.动态构造和静态构造 .紧凑构造和非紧凑构造C.线性构造和非线性构造 D.内部构造和外部构造2数据构造在计算机内存中的表达是指 A 。A.数据的存储构造 B数据构造 数据的逻辑构造 D数据元素之间的关系3在数据构造中，与所使用的计算机无关的是数据的 构造。A逻辑 B存储 C逻辑和存储 物理.在存储数据时，一般不仅要存储各数据元素的值，并且还要存储 C 。A.数据的解决措施 B数据元素的类型 数据元素之间的关系 D.数据的存储措施5.在决定选用何种存储构造时,一般不考虑 A 。A各结点的值如何 B
2、.结点个数的多少C.对数据有哪些运算 D所用的编程语言实现这种构造与否以便。6.如下说法对的的是 D 。A数据项是数据的基本单位B数据元素是数据的最小单位数据构造是带构造的数据项的集合D某些表面上很不相似的数据可以有相似的逻辑构造.算法分析的目的是 ,算法分析的两个重要方面是A 。(1)A.找出数据构造的合理性 B研究算法中的输入和输出的关系C.分析算法的效率以求改善 C分析算法的易读性和文档性（)A空间复杂度和时间复杂度 B对的性和简要性 C可读性和文档性 D.数据复杂性和程序复杂性8.下面程序段的时间复杂度是 O(n2) 。 s 0；or( I 0; i;+) f(j=0;j;+)s =B
3、ij；sm = ;9下面程序段的时间复杂度是 O(n*） 。for( =0; in; i+) for(j=0;jm；+)Aij = 0;0.下面程序段的时间复杂度是 O(log3n) 。i 0；hi(inext =NUL Che-ne =ha D hea！=ULL1.带头结点的单链表had为空的鉴定条件是 。Ahead=NLL B had-next =NULL C.ad-next = D head！=ULL1.若某表最常用的操作是在最后一种结点之后插入一种结点或删除最后一种结点，则采用 D 存储方式最节省运算时间。A.单链表 B.给出表头指针的单循环链表 C双链表 D带头结点的双循环链表7需要
4、分派较大空间,插入和删除不需要移动元素的线性表，其存储构造是 B 。.单链表 .静态链表 .线性链表 D.顺序存储构造8.非空的循环单链表head的尾结点(由p所指向）满足 。pnext = NL = NLC.p-nxt =head Dp = had1.在循环双链表的p所指的结点之前插入s所指结点的操作是 D 。Apprio= s；n =p;ppior-net= s;spio=p-iorBp-prio s；p-pror-nex = s；s-next = ；s-pror = ppriorC.s-nx ；-prio=p-prior;p-prior = ；pi-next = ss-ext = p;-
5、prior=pprir;p-rir-next ；prio =s20.如果最常用的操作是取第i个结点及其前驱,则采用 D 存储方式最节省时间。A单链表 B双链表 C.单循环链表 D 顺序表2在一种具有n个结点的有序单链表中插入一种新结点并仍然保持有序的时间复杂度是 B 。AO（1) B.O(n) .O（n2) DO（nlg2n）2.在一种长度为(n）的单链表上，设有头和尾两个指针,执行 操作与链表的长度有关。.删除单链表中的第一种元素删除单链表中的最后一种元素在单链表第一种元素前插入一种新元素D在单链表最后一种元素后插入一种新元素23与单链表相比，双链表的长处之一是 D 。A插入、删除操作更简朴
6、 B.可以进行随机访问.可以省略表头指针或表尾指针D.顺序访问相邻结点更灵活24如果对线性表的操作只有两种,即删除第一种元素，在最后一种元素的背面插入新元素,则最佳使用 。A只有表头指针没有表尾指针的循环单链表B.只有表尾指针没有表头指针的循环单链表C.非循环双链表D循环双链表2.在长度为n的顺序表的第i个位置上插入一种元素(1 i+1）,元素的移动次数为： 。A. i+ 1 n C D 1 26.对于只在表的首、尾两端进行插入操作的线性表,宜采用的存储构造为 。顺序表 B 用头指针表达的循环单链表C用尾指针表达的循环单链表 D.单链表27下述哪一条是顺序存储构造的长处？ C 。插入运算以便
7、B可以便地用于多种逻辑构造的存储表达C存储密度大 删除运算以便2下面有关线性表的论述中，错误的是哪一种？ B 。A线性表采用顺序存储,必须占用一片持续的存储单元线性表采用顺序存储，便于进行插入和删除操作。C线性表采用链式存储，不必占用一片持续的存储单元D线性表采用链式存储,便于进行插入和删除操作。29线性表是具有n个 B 的有限序列。A字符 数据元素 C数据项 D.表元素30.在个结点的线性表的数组实现中，算法的时间复杂度是（1）的操作是 A 。访问第(1=i=n）个结点和求第i个结点的直接前驱（i)B在第i(1=i=n）个结点后插入一种新结点C删除第i(1nx=s;-next=pex . -
8、nexp-next ;n=s;Cp-nx=s；pex=-net D-nxt=s-；-nex3.线性表的顺序存储构造是一种 A 。A.随机存取的存储构造 .顺序存取的存储构造C.索引存取的存储构造 D.Hah存取的存储构造3.栈的特点是 ，队列的特点是 A 。A先进先出 B.先进后出38栈和队列的共同点是 C 。A.都是先进后出 B都是先进先出C只容许在端点处插入和删除元素 没有共同点39.一种栈的进栈序列是a,，d，,则栈的不也许的输出序列是 。Aedcba Bdecb Cdceab Dabcde0设有一种栈,元素依次进栈的顺序为A、B、E。下列 C 是不也许的出栈序列。 .A,B,D,E B
9、.B,C,D,E,A C.,A，B，C，D D，,B,41如下 B 不是队列的基本运算?A从队尾插入一种新元素 B.从队列中删除第i个元素C.判断一种队列与否为空 .读取队头元素的值4若已知一种栈的进栈序列是1，2,3，其输出序列为p1,p,p3,pn，若p=n,则p为 C 。A.i .n-i n1 D不拟定43鉴定一种顺序栈t（最多元素为aSize）为空的条件是 B 。At-top ！= - Bs-top = 1 C.st-tp != axSz D.s-op = MaSze 4鉴定一种顺序栈t（最多元素为MaxSize）为满的条件是 D 。Astop ！=- B.stp = 1 C.st-to ! MaxSiz Dst-top MaxSize 45.一种队列的入队序列是1，2，3,4,则队列的输出序列是 B
