《数据结构与算法期末考试复习试题》由会员分享,可在线阅读,更多相关《数据结构与算法期末考试复习试题(18页珍藏版)》请在金锄头文库上搜索。
1、WORD格式数据构造与算法复习题一、选择题。1在数据构造中,从逻辑上可以把数据构造分为C。A动态构造和静态构造B 紧凑构造和非紧凑构造C线性构造和非线性构造D 内部构造和外部构造2数据构造在计算机内存中的表示是指A。A数据的存储构造B数据构造C数据的逻辑构造D 数据元素之间的关系3在数据构造中,与所使用的计算机无关的是数据的A构造。A逻辑B 存储C逻辑和存储D物理4在存储数据时,通常不仅要存储各数据元素的值,而且还要存储C。A数据的处理方法B 数据元素的类型C数据元素之间的关系D数据的存储方法5在决定选取何种存储构造时,一般不考虑A。A各结点的值如何B结点个数的多少C对数据有哪些运算D所用的编
2、程语言实现这种构造是否方便。6以下说法正确的选项是D。A数据项是数据的根本单位B数据元素是数据的最小单位C数据构造是带构造的数据项的集合D一些外表上很不一样的数据可以有一样的逻辑构造7算法分析的目的是C ,算法分析的两个主要方面是A。( 1 A 找出数据构造的合理性B研究算法中的输入和输出的关系C分析算法的效率以求改进C分析算法的易读性和文档性( 2 A 空间复杂度和时间复杂度B正确性和简明性C可读性和文档性D 数据复杂性和程序复杂性专业资料整理WORD格式1专业资料整理WORD格式8下面程序段的时间复杂度是O(n 2)。s =0;for( I =0; in; i+)for(j=0;jn;j+
3、)s +=Bij; sum = s ;9下面程序段的时间复杂度是O(n*m)。for( i =0; in; i+)for(j=0;jm;j+)Aij 0;10下面程序段的时间复杂度是O(log 3n)。i 0;while inext =NULLC head-next =headD head!=NULL专业资料整理WORD格式2专业资料整理WORD格式15带头结点的单链表head 为空的判定条件是B。A head = NULLB head-next =NULLC head-next =headD head!=NULL16假设某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点,那么
4、采用D 存储方式最节省运算时间。A单链表B给出表头指针的单循环链表C双链表D 带头结点的双循环链表17需要分配较大空间,插入和删除不需要移动元素的线性表,其存储构造是B。A单链表B静态链表C 线性链表D顺序存储构造18非空的循环单链表head 的尾结点由p 所指向满足C。专业资料整理WORD格式A p-next = NULL C p-next =headB p = NULLD p = head专业资料整理WORD格式19在循环双链表的p 所指的结点之前插入s 所指结点的操作是D。A p-prior = s ; s-next = p ; p-prior-next = s ; s-prior =
5、p-priorB p-prior = s ; p-prior-next = s ; s-next = p ; s-prior = p-priorC s-next = p ; s-prior = p-prior ;p-prior = s ; p-prior-next = sD s-next = p ;s-prior = p-prior ;p-prior-next = s ; p-prior = s 20 如果最常用的操作是取第 i 个结点及其前驱,那么采用D 存储方式最节省时间。A单链表B双链表C单循环链表D顺序表21在一个具有n 个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是B
6、 。A O 1BO nCOn2D O nlog2n 22在一个长度为n n1 的单链表上,设有头和尾两个指针,执行B 操作与链表的长度有关。A删除单链表中的第一个元素B删除单链表中的最后一个元素C在单链表第一个元素前插入一个新元素D在单链表最后一个元素后插入一个新元素专业资料整理WORD格式3专业资料整理WORD格式23与单链表相比,双链表的优点之一是D 。A插入、删除操作更简单B可以进展随机访问C可以省略表头指针或表尾指针D顺序访问相邻结点更灵活24如果对线性表的操作只有两种,即删除第一个元素,在最后一个元素的后面插入新元素,那么最好使用B 。A只有表头指针没有表尾指针的循环单链表B 只有表
7、尾指针没有表头指针的循环单链表C非循环双链表D循环双链表25在长度为n 的顺序表的第i 个位置上插入一个元素1 in+1,元素的移动次数为:A 。A n i + 1B n iC iD i 126对于只在表的首、尾两端进展插入操作的线性表,宜采用的存储构造为C。A顺序表B 用头指针表示的循环单链表C用尾指针表示的循环单链表D 单链表27下述哪一条是顺序存储构造的优点?C。A 插入运算方便B 可方便地用于各种逻辑构造的存储表示C 存储密度大D 删除运算方便28下面关于线性表的表达中,错误的选项是哪一个?B。A 线性表采用顺序存储,必须占用一片连续的存储单元B 线性表采用顺序存储,便于进展插入和删除
8、操作。C 线性表采用链式存储,不必占用一片连续的存储单元D 线性表采用链式存储,便于进展插入和删除操作。29线性表是具有n 个B的有限序列。A 字符B数据元素C数据项D 表元素专业资料整理WORD格式4专业资料整理WORD格式30在 n 个结点的线性表的数组实现中,算法的时间复杂度是O 1的操作是A。A 访问第 i 1=i=n 个结点和求第i 个结点的直接前驱1i=n B 在第 i 1=i=n 个结点后插入一个新结点C删除第i 1=inext=s ; s-next=p-nextB s-next=p-next ;p-next=s; C p-next=s;p-next=s-nextD p-next
9、=s-next ; p-next=s36线性表的顺序存储构造是一种A。A 随机存取的存储构造B 顺序存取的存储构造C索引存取的存储构造D Hash 存取的存储构造37栈的特点是B,队列的特点是A。A先进先出B 先进后出专业资料整理WORD格式5专业资料整理WORD格式38栈和队列的共同点是C。A都是先进后出B 都是先进先出C只允许在端点处插入和删除元素D没有共同点39一个栈的进栈序列是a, b,c, d, e,那么栈的不可能的输出序列是C。A edcbaBdecbaC dceabD abcde40设有一个栈,元素依次进栈的顺序为A 、B 、 C、 D、 E。以下C是不可能的出栈序列。A A,B,C,D,EB B,C,D,E,AC E,A,B,C,DD E,D,C,B,A41以下B不是队列的根本运算?A从队尾插入一个新元素B 从队列中删除第i 个元素C判断一个队列是否为空D 读取队头元素的值42假设一个栈的进栈序列是1, 2, 3, n,其输出序列为p1, p2, p3, , ,pn,假设 p1 n,那么 pi 为C 。 A i B n i C n i 1 D不确定43判定一个顺序栈st最多元素为MaxSize 为空的条件是B。A st-top != -1B st-top =