《李春葆数据结构习题与解析》由会员分享，可在线阅读，更多相关《李春葆数据结构习题与解析（24页珍藏版）》请在金锄头文库上搜索。
1、一、绪论选择题1数据构造是一门研究非数值计算的程序设计问题 计算机的 以及它们之间的 和运算等的学科。 1 A数据元素 B计算措施 C.逻辑存储.数据映像 A.构造 B.关系 C.运算 D.算法2数据构造被形式地定义为 （K,R）,其中K是的有限集,R是上的有限集。 1 .算法 .数据元素 数据操作D逻辑构造2A.操作 B.映像 C存储 D.关系在数据构造中,从逻辑上可以把数据构造提成 。A动态构造和静态构造 B.紧凑构造和非紧凑构造 线性构造和非线性构造 D内部构造和外部构造4线性构造的顺序存储构造是一种 的存储构造，线性表的链式存储构造是一种 的存储构造。A随机存取 B.顺序存取C.索引存
2、取 .散列存取.算法分析的目的是 ,算法分析的两个重要方面是 。 1 A.找出数据构造的合理性 .研究算法中的输入和输出的关系C.分析算法的效率以求改善 .分析算法的易懂性和文档性 A.空间复杂度和时间复杂度 对的性和简朴性 可读性和文档性 D.数据复杂性和程序复杂性.计算机算法指的是,它必须具有输入、输出和 等 5个特性。1 A.计算措施 .排序措施 .解决问题的有限运算序列 D.调度措施 2A.可执行性、可移植性和可扩大性 B可行性、拟定性和有穷性 C拟定性、有穷性和稳定性 D.易读性、稳定性和安全性7线性表的逻辑顺序与存储顺序总是一致的，这种说法。 A.对的 B.不对的线性表若采用链式存
3、储构造时,规定内存中可用存储单元的地址 。 .必须持续的 B部分地址必须持续的 .一定是不续的D持续不持续都可以9.如下的论述中,对的的是 。A.线性表的存储构造优于链式存储构造 .二维数组是其数据元素为线性表的线性表.栈的操作方式是先进先出 .队列的操作方式是先进后出0每种数据构造都具有三个基本运算：插入、删除和查找，这种说法 。 A对的 B不对的填空题.数据逻辑构造涉及三种类型 、 和 ,树形构造和图形构造合称为 。2.在线性构造中,第一种结点 前驱结点，其他每个结点有且只有 个前驱结点；最后一种结点 后续结点，其他每个结点有且只有 个后续结点。3在树形构造中，树根结点没有 结点,其他每个
4、结点有且只有个前驱结点；叶子结点没有 结点，其他每个结点的后续可以 。4.在图形构造中,每个结点的前驱结点数和后续结点数可以 。.线性构造中元素之间存在 关系,树形构造中元素之间存在 关系,图形构造中元素之间存在 关系。.算法的五个重要特性是 、 、 、 、 。7.下面程序段的时间复杂度是 。r（i= 0;i ; i+) fr(j= ； j m;+) Aij = 0;8下面程序段的时间复杂度是 。i s =；hile ( s ） i+; * =i 1 s +=; * s + i/9.下面程序段的时间复杂度是 。 0;r(i = 0;i n; i+) for( j = 0; j n; j+) s
5、+ ij;sum ;0下面程序段的时间复杂度是 。i 1;whle （ i tp!=0 B T-t=0 C.Stp! m .STtop= 6判断一种栈ST(最多元素为m)为满栈的条件是 。 A.ST-tp!0B. ST-to= C. ST-tp！= m-1 . STtp=m-1栈的特点是 1 ,队列的特点是2 。 A.先进先出 B.先进后出.一种队列的入队序列是1、2、,则队列输出序列是 。A.4、2、1 .、2、3、4 C1、4、 .、2、4、1.判断一种队列QU(最多元素为m） 为空的条件是 。A. QUrearQUfront =m B.QU-earQ-fron = m QU-frn =-
6、rar D. rotU-rea + 10判断一种队列U（最多元素为） 为满队列的条件是 。A. QU-reaQ-font = m . QUre-QU-frot1m C. U-font =QU-rer D.QU-rot-QUrr 111判断一种循环队列QU （最多元素为m)为空的条件是 。A. U-front =QU-rear B. QU-rot ! QU-rar C. QUfot = (Q-rear ） %m D. Q-ft !=(Qra+ 1) %12判断一种循环队列QU (最多元素为m) 为满队列的条件是 。.-front = QU-rr . QUfront !=-ear C. QU-rt
7、 =(QU-rear + 1)%m D. -ron != (QU-rer + 1)%m13循环队列用数组A0,m1寄存其元素值,已知其头尾指针分别是frot和ear,则目前队列中的元素个数是。 A.（ra-frn+ m) %m B rearfont+ 1 C.rearfron1 . reafront 14.栈和队列的共同点是 。A.都是先进后出 B都是先进先出 C.只容许在端点处插入、删除元素 没有共同点填空题1.向量、栈和队列都是 构造,可以在向量的 位置插入和删除元素；对于栈只能在 插入和删除元素；对于队列只能在 插入元素和 删除元素。2在一种长度为n的向量中的第i个元素（1)之前插入一种
8、元素时,需向后移动 个元素。3.在一种长度为的向量中的删除第i个元素(1in)时，需要向前移动 个元素。.向栈中压入元素的操作是 。.对栈进行退栈时的操作是 。.在一种循环队列中,队首指针指向队首元素的 。7.从循环队列中删除一种元素时,其操作是 。8.在具有n个单元的循环队列中，队满时共有 个元素的。9.一种栈的输入序列是15,则栈的输出序列4312是 。10一种栈的输入序列是234，则栈的输出序列234是 。三、链表单选题1不带头结点的单链表h为空的鉴定条件是 。 A.ea=NULL Bhad-nxt=ULL C.had-next=hedDhd!=UL2.带头结点的单链表hd为空的鉴定条件
9、是 。 A.hed=NUL.ea-x=NLC.het=hd D.head!=NULL3.非空的循环单链表had的尾结点(由p所指向)满足 。 A.p-ext=NLL B.=NUL C.p-net=hed Dp=head在循环双链表的p所指结点之后插入s所指结点的操作是 。.priht=s；s-le；p-ight-lefts;-ritri;B. piht=s;-rght-efts;s-leftp;srigt=p-rght;.s-left=；s-ightp-ight;p-rgt=s;p-right-efts;D.s-ft=p;s-igh=prht;prght-lef=s；p-rgt=s; 5.在一
10、种单链表中，已知所指结点是p所指结点的前驱结点,若在q和p之间插入结点,则执行 。. st = p-ext; pnext=s; B.p-nex= s-next;s-next = p;C. q-nx= s; s-next = p; D.p-next = s;-nex= q;6在一种单链表中,已知所指结点不是最后结点，在p之后插入s所指结点,则执行。As-net p; p-nex=s; B. s-next = p-next； pnext =s；C -nxt = nxt； p = s； p-nxt=; s-x= p；在一种单链表中,若删除p所指结点的后续结点,则执行 。A. -et= -et-t; B p = p-net; p-extp-nt-nex；C. -net = -xt; D. p =p-et -xt；9.从一种具有n个结点的单链表中查找其值等于x结点时，在查找成功的状况下,需平均比较
