《数据结构习题集(总)》由会员分享,可在线阅读,更多相关《数据结构习题集(总)(18页珍藏版)》请在金锄头文库上搜索。
1、1数据结构习题集数据结构习题集第一章第一章 绪论绪论1.1 数据结构是一门研究非数值计算的程序设计问题中计算机的_ 以及它们之间的_ 和运算 等的学科。 A.数据元素 B.计算方法 C.逻辑存储 D.数据映像 A.结构 B.关系 C.运算 D.算法 1.2 算法分析的目的是_ ,算法分析的两个主要方面是_ 。 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系 C.分析算法的效率 以求该进 D.分析算法的易懂性和文档性 A.空间复杂度和时间复杂度 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 1.3 计算机算法指的是_ ,它必须具备输入、输出和_ 等 5 个重要特
2、性。 A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 A.可读性、可移植性和可扩展性 B. 可读性、可移植性和有穷性 C. 确定性、有穷性和稳定性 D.易读性、稳定性 和安全性 1.4 数据结构是研究数据的_和_,并对这种结构定义相适应的运算,设计出相应的算 法,分析算法的效率。 1.5 数据逻辑结构包括集合、 、 和 四种类型,其中树形结构和图状结构 合称为_。 1.6 线性结构中元素之间存在_ 关系,树形结构中元素之间存在_ 关系,图状结构中元素之间存 在_ 关系。 1.7 数据物理结构主要有两种,分别是_和_。1.8 一个算法的时间复杂度为(3n3+2n7)(5n)
3、,其数量级表示为 。1.9 存储结构可根据数据元素在机器中的位置是否连续分为,。1.10 顺序存储结构是通过_表示元素之间的逻辑关系的;链式存储结构是通过_表示元素之间的逻辑关系的。1.11 算法设计的目标: 、 、 、 和 。1.12 数据的基本单位是_ ,数据的最小单位是_ 。1.13 数据结构在计算机中的表示称为数据的 ,它分为_、_、 _ 、_四种存储类型。1.14 算法性能的分析和度量,可以从算法的 和 来评价算法的优劣。1.15 某程序的时间复杂度为(3n+nlog2n+n2+8), 其数量级表示为 。第二章第二章 线性表线性表2.1 链表不具备的特点是 _ 。A.可随机访问任一结
4、点 B.插入删除不需移动元素 C.不必事先估计存储空间 D.所需空间与其长 度成正比22.2 不带头结点的单链表 head 为空的判定条件是_。A. head=null B. head-next=null C. head-next=head D. head !=null 2.3 带头结点的单链表 head 为空的判定条件是_。A. head=null B. head-next=null C. head-next=head D. head!=null 2.4 非空的循环单链表 head 的尾节结点(由 p 所指向)满足_。A. p-next=null B. p=null C. p-next=he
5、ad D. p=head 2.5 在一个具有 n 个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是_。A. O(1) B. O(n) C. O(n2) D. O(nlog2n) 2.6 在单链表中设置头结点的作用是_。 2.7 在一个单链表中的 p 所指结点之后插入一个 S 所指结点时,可执行如下操作: (1) s-next=_ (2) p-next=s; (3) t=p-data; (4)p-data=_ (5)s-data=_ 2.8 在一个单链表中删除 p 所指结点时,应执行以下操作:(1)q=p-next; (2) p-data=p-next-data; (3)p-nex
6、t=_; (4) free(q); 2.9 在一个单链表中 p 所指结点之后插入一个 s 所指结点时,应执行 s-next=_和 p-next=_ 的 操作。2.10 线性表的逻辑顺序与物理顺序总是 的。2.11 已知具有n个元素的一维数组采用顺序存储结构,每个元素占k个存储单元,第一个元素的地址为LOC(a1),那么,LOC(ai)=_。2.12 线性表中数据元素之间具有_,除第一个和最后一个元素外,其他数据元素有且只有_后继和前趋。2.13 线性链表中各个结点之间的地址 连续。2.14 若频繁地对线性表进行插入和删除操作,该线性表采用 存储结构比较合适。 2.15 若线性表采用顺序存储结构
7、,每个数据元素占用3个存储单元,第11个数据元素的存储地址为130,则第1个数据元素的存储地址是 。2.16 符号p-next 出现在表达式中表示p所指的那个结点的 。2.17 要将指针p移到它所指的结点的下一个结点应执行语句 。2.18 在非空线性链表中由p所指的结点后面插入一个由s所指的结点的过程是依次执行语句:_;_。2.19 在以head为头结点的循环单链表中,尾指针p应满足p-next= 。2.20.以 head 为头结点循环双链表为空时,应满足 head-llink= , head-rlink= 。2.21 若线性表采用顺序存储结构,线性表的最大长度为 1000,每个数据元素占 3
8、 个存储单元,则要分配给该线性表_存储单元,若第一个数据元素的存储地址是 2000,则第 11 个元素的存储地址是_。32.22 在单链表中,指针p指向元素为x的结点,实现“删除x的后继”的语句是 。A.p=p-next; B.p-next=p-next-next; C.p-next=p; D.p=p-next-next; 2.23 在单链表中,已知q指的结点是p指的结点的直接前驱结点,若在q和p指的结点之间插入一个由s指的结点,则需执行_。A. s-next=p-next;p-next=s B. q-next=s;s-next=pC. p-next=s-next;s-next=p D.p-n
9、ext=s;s-next=q2.24 带头结点 head 的循环单链表的尾结点(由 p 所指向)满足_。A. p-next=NULL B. p=NULL C. p-next=head D. p=head 2.25 若长度为n的线性表采用顺序存储结构,删除它的第i个数据元素,需要先依次向前移动_个数据元素。A.n-i B.n+i C.n-i-1 D.n-i+12. 28 下面的程序段可以将第 i 个元素以后的所有元素前移,程序的空白处应填入的语句为 。x=v i ; for (j=i+1 ; jnext=s; s-next=p B. (*s).next=(*p).next; (*p).next=
10、s; C. p=p-next; s-next=p; p-next=s D. p-next=s; s-next=p-next2.40 若已建立以下链表结构,指针 p 和 s 分别指向如图所示的结点,以下语句组中,能够将 s 所指结点 从链表中删除并释放该结点的是() A. free(s);p-next=s-next; B. s=s-next; p-next=s; free(s); C. p-next=s-next; free(s); D. s=s-next; pnext=s; p=p-next; free(p);2.41 设有结点定义: Struct node Int data; Struct
11、node *node; : 且已建立如图所示的带有头结点的单向链表:函数 sum 的功能是:计算链表中各结点数据域之和,作为函数值返回。请填空。int sum(struct node*head) int s=0 struct node*p; p=head-next; dos=s+_ ;p=p-next; 5while(p!= _); return s;2.42 以下算法用以统计链表中元素的个数,其中 first 指向链表中的第一个结点,count 用 来统计结点的个数。请填空 struct link char data; struct link*next; ; structlink *p,*f
12、irst; int count=0; p=first;while(_) _P=_; 第三章第三章 栈与队列栈与队列3.1 栈的特点是_ ,队列的特点是_ 。 A.先进先出 B.先进后出 3.2 栈和队列的共同点时_。 A.都是先进后出 B.都是先进先出 C.只允许在端点处插入和删除元素 D.没有共同点 3.3 一个栈的进栈序列是 a,b,c,d,e,则栈的不可能的输出序列是_ 。A. edcba B. decba C. dceab D. abcde 3.4 判定一个栈 ST(最多元素 MaxSize)为空的条件是_ 。A.ST-top!=-1 B. ST-top=-1 C.ST-top!= M
13、axSize D. ST-top=MaxSize-1 3.5 判定一个栈 ST(最多元素 MaxSize)为栈满的条件是_ 。A.ST-top!=-1 B. ST-top=-1 C.ST-top!= MaxSize D. ST-top=MaxSize-1 3.6 向一个栈顶指针为 HS 的链栈中插入一个 S 所指结点时,则执行_ 。A.HS-next =s; B. s-next =HS-next; HS-next =s; C. s-next =HS; HS=s; D. s-next=HS; HS=HS-next; 3.7 向一个栈顶指针为 HS 的链栈中删除一个结点时,用 x 保存被删结点的值,则执行_ 。A. x=HS;HS=HS-next; B. x=HS-data; C. HS=HS-next;x=HS-data; D. x=HS-data;HS=HS-next; 3.8 一个队