数据结构Java版第二章习题汇编
- 格式:doc
- 大小:409.50 KB
- 文档页数:16
数据结构练习题第二章答案一、选择题1. 在数据结构中,线性结构的特点是什么?A. 元素之间存在一对一的关系B. 元素之间存在一对多的关系C. 元素之间存在多对多的关系D. 元素之间存在一对一或一对多的关系答案:D2. 栈(Stack)是一种特殊的线性表,其特点是:A. 允许在表的一端进行插入和删除操作B. 允许在表的两端进行插入和删除操作C. 只能在表的两端进行插入和删除操作D. 只能在表的中间进行插入和删除操作答案:A3. 队列(Queue)与栈的主要区别在于:A. 队列是先进先出(FIFO),栈是先进后出(LIFO)B. 栈是先进先出(FIFO),队列是先进后出(LIFO)C. 队列和栈都是先进先出(FIFO)D. 队列和栈都是先进后出(LIFO)答案:A二、简答题1. 什么是链表?链表有哪些基本操作?答案:链表是一种由一系列节点组成的线性数据结构,每个节点包含数据部分和指向下一个节点的指针。
链表的基本操作包括插入节点、删除节点、查找节点和遍历链表。
2. 线性表的顺序存储结构和链式存储结构有何区别?答案:顺序存储结构使用连续的存储单元来存储数据元素,如数组。
链式存储结构不要求数据元素在存储空间中连续,每个元素包含指向下一个元素的指针,如链表。
三、编程题1. 编写一个函数,实现在单链表中插入一个新节点到指定位置。
```c#include <stdio.h>#include <stdlib.h>typedef struct Node {int data;struct Node *next;} Node;Node* createNode(int data) {Node *newNode = (Node*)malloc(sizeof(Node));newNode->data = data;newNode->next = NULL;return newNode;}void insertNode(Node head, int position, int data) {Node *newNode = createNode(data);if (position == 0) {newNode->next = *head;*head = newNode;} else {Node *current = *head;for (int i = 0; current != NULL && i < position - 1; i++) {current = current->next;}if (current == NULL) return; // Position is greater than the number of nodesnewNode->next = current->next;current->next = newNode;}}int main() {Node *head = NULL;insertNode(&head, 0, 10);insertNode(&head, 1, 20);// Print the list to verify the insertionNode *current = head;while (current != NULL) {printf("%d ", current->data);current = current->next;}return 0;}```四、分析题1. 分析栈的后进先出(LIFO)特性在实际应用中的优势和局限性。
第二章线性表一、选择题1.一个线性表第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是( )(A)110 (B)108(C)100 (D)120参考答案:B2. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变,平均要移动()个元素。
(A)64(B)63 (C)63.5 (D)7参考答案:C3.线性表采用链式存储结构时,其地址()。
(A) 必须是连续的 (B) 部分地址必须是连续的(C) 一定是不连续的 (D) 连续与否均可以参考答案:D4. 在一个单链表中,若p所指结点不是最后结点,在p之后插入s所指结点,则执行()(A)s->next=p;p->next=s; (B) s->next=p->next;p->next=s;(C)s->next=p->next;p=s; (D)p->next=s;s->next=p;参考答案:B5.在一个单链表中,若删除p所指结点的后续结点,则执行()(A)p->next=p->next->next; (B)p=p->next; p->next=p->next->next;(C)p->next=p->next; (D)p =p->next->next;参考答案:A6.下列有关线性表的叙述中,正确的是()(A)线性表中的元素之间隔是线性关系(B)线性表中至少有一个元素(C)线性表中任何一个元素有且仅有一个直接前趋(D)线性表中任何一个元素有且仅有一个直接后继参考答案:A7.线性表是具有n个()的有限序列(n≠0)(A)表元素(B)字符(C)数据元素(D)数据项参考答案:C二、判断题1.线性表的链接存储,表中元素的逻辑顺序与物理顺序一定相同。
()2.如果没有提供指针类型的语言,就无法构造链式结构。
()3.线性结构的特点是只有一个结点没有前驱,只有一个结点没有后继,其余的结点只有一个前驱和后继。
数据结构Java版第二章习题在学习数据结构的过程中,第二章的习题往往是巩固和深化对相关概念理解的重要环节。
这一章可能涵盖了诸如数组、链表、栈、队列等基本数据结构的知识。
先来说说数组,这是一种最简单也最常见的数据结构。
在 Java 中,数组是一组相同类型元素的有序集合。
它的优点很明显,比如可以通过索引快速访问元素,查找操作的时间复杂度为 O(1)。
但缺点也不能忽视,比如数组的长度固定,插入和删除元素可能需要移动大量元素,导致时间复杂度较高。
来看一道关于数组的习题:给定一个整数数组,找出其中出现次数最多的元素。
这就需要我们遍历数组,使用一个辅助的数据结构(比如哈希表)来记录每个元素出现的次数,最后找出出现次数最多的那个元素。
再说说链表,链表是由一系列节点组成的,每个节点包含数据和指向下一个节点的引用。
相比于数组,链表在插入和删除操作上具有优势,时间复杂度为 O(1)。
但查找操作的时间复杂度为 O(n)。
有这样一道链表的习题:实现一个链表的反转。
这就需要我们改变链表节点的指针指向,依次将每个节点的 next 指针指向前一个节点,从而实现链表的反转。
接下来是栈,栈是一种特殊的线性表,遵循后进先出(LIFO)的原则。
在 Java 中,可以使用数组或者链表来实现栈。
比如有这样一道关于栈的习题:判断一个表达式中的括号是否匹配。
我们可以将左括号入栈,遇到右括号时弹出栈顶的左括号进行匹配,如果最后栈为空,则括号匹配成功。
然后是队列,队列遵循先进先出(FIFO)的原则。
在实际应用中,比如排队系统、任务调度等都可以用到队列。
例如,有这样一道队列的习题:实现一个循环队列。
这就需要我们处理好队列的头尾指针,以及队列满和空的判断条件。
在解决这些习题的过程中,我们不仅要熟练掌握各种数据结构的特点和操作方法,还要具备良好的逻辑思维和代码实现能力。
同时,通过不断地练习和思考,我们能够更加深入地理解数据结构的本质,为今后解决更复杂的问题打下坚实的基础。
数据结构第2章习题参考答案2.7习题2.7.1知识点:线性表的逻辑结构一、选择题1①线性表L=(a1, a2,…,an),下列说法正确的是(D)。
A.每个元素都有一个直接前驱和一个直接后继。
B.线性表中至少要有一个元素。
C.表中诸元素的排列顺序必须是由小到大或由大到小。
D.除第一个和最后一个元素外,其余每个元素都有一个且仅有一个直接前驱和直接后继。
2①在线性表的下列运算中,不改变数据元素之间结构关系的运算是(D)。
A.插入B.删除C.排序D.定位3①线性表是具有n个(C)的有限序列(n>0)。
【清华大学1998】A.表元素B.字符C.数据元素D.数据项E.信息项二、判断题(T)1①线性表中的每个结点最多只有一个前驱和一个后继。
(F)2①线性表中的每个结点都至少有一个前驱结点和后继结点。
(F)3①线性表是N个数的有限序列。
(F)4①同一线性表的数据元素可以具有不同的特性。
(T)5①线性表的长度n就是表中数据元素的个数,当n=0时,称为空表。
(T)6①线性表是一个相当灵活的数据结构,它的长度可根据需要增长或缩短。
(F)7①对线性表中的数据元素只能进行访问,不能进行插入和删除操作。
2.7.2知识点:线性表的顺序存储结构一、选择题1①在一个长度为n的顺序表中,在第i个元素(1 <=i <=n+1)之前插入一个新元素时需向后移动(B)个元素.A.n-1B.n-i+1C.n-i-1D.i2①若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素,则采用(D)存储方式最节省时间。
A.单链表B.双链表C.单向循环D.顺序表3②一个数组第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是(B)A.110B.108C.100D.1204①下述哪一条是顺序存储结构的优点(A)。
【北方交通大学2001】A.存储密度大B.插入运算方便C.删除运算方便D.可方便地用于各种逻辑结构的存储表示5③若长度为n的线性表采用顺序存储结构,在其第i个位置插入一个新元素的算法的时间复杂度为(C)(1<=i<=n+1)。
数据结构第2章习题参考答案1. 简答题1.1 什么是数据结构?数据结构是指相互之间存在一种或多种特定关系的数据元素的集合,它包括数据的逻辑结构和物理结构。
1.2 数据结构的分类有哪些?数据结构可以分为线性结构和非线性结构。
线性结构包括线性表、栈、队列和串;非线性结构包括树和图。
1.3 数据结构的逻辑结构有哪些?数据结构的逻辑结构包括线性结构、树形结构和图形结构。
1.4 数据结构的物理结构有哪些?数据结构的物理结构包括顺序存储结构和链式存储结构。
1.5 什么是算法?算法是指求解问题的具体步骤和方法。
1.6 算法的特性有哪些?算法应具有有穷性、确定性、可行性和输入输出性。
2. 选择题2.1 在栈的顺序存储结构中,栈的存储位置是:A. 自顶向下递增B. 自底向上递增C. 自底向上递减D. 自顶向下递减答案:D2.2 下列哪个数据结构不适合表示有父子关系的数据?A. 二叉树B. 图C. 链表D. 堆答案:D2.3 对于一棵完全二叉树,叶子节点的个数为n,则树中节点的总数为:A. 2nB. 2n + 1C. nD. n + 1答案:A2.4 假设有一个长度为10的栈,初始时栈为空,若对该栈连续执行5次入栈操作,然后执行4次出栈操作,最后执行1次入栈操作,则栈中剩余的元素个数为:A. 0B. 1C. 4D. 6答案:D3. 编程题3.1 实现一个栈数据结构的基本操作,包括入栈、出栈、获取栈顶元素和判断栈是否为空。
```Pythonclass Stack:def __init__(self):self.items = []def is_empty(self):return len(self.items) == 0def push(self, item):self.items.append(item)def pop(self):if self.is_empty():return Nonereturn self.items.pop()def peek(self):if self.is_empty():return Nonereturn self.items[-1]```3.2 实现一个队列数据结构的基本操作,包括入队、出队、获取队首元素和判断队列是否为空。
数据结构第二章习题答案数据结构第二章习题答案第一题:给定一个数组arr,其中包含n个元素,要求编写一个函数,将数组中的所有元素按照奇偶性重新排列。
奇数元素排在偶数元素之前。
请给出实现代码。
解答:```pythondef rearrange(arr):n = len(arr)left = 0right = n - 1while left < right:while arr[left] % 2 != 0 and left < right:left += 1while arr[right] % 2 == 0 and left < right:right -= 1if left < right:arr[left], arr[right] = arr[right], arr[left]left += 1right -= 1return arr```第二题:给定一个字符串,判断其是否为回文串。
回文串是指正读和反读都相同的字符串。
要求不考虑大小写和非字母字符,只考虑字母字符。
解答:```pythondef is_palindrome(s):s = ''.join(filter(str.isalpha, s)).lower()return s == s[::-1]```第三题:给定一个链表,判断链表中是否存在环。
如果链表中存在环,则返回True,否则返回False。
解答:```pythonclass ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef has_cycle(head):slow = fast = headwhile fast and fast.next:slow = slow.nextfast = fast.next.nextif slow == fast:return Truereturn False```第四题:给定一个二叉树,判断其是否为平衡二叉树。
(依据自己的状况选作部分习题,不要剽窃)第二章习题次序储存线性表一判断题1.线性表的逻辑次序与储存次序老是一致的。
×2.次序储存的线性表能够按次号随机存取。
√3.次序表的插入和删除操作不需要付出很大的时间代价,由于每次操作均匀只有近一半的元素需要挪动。
×4.线性表中的元素能够是各种各种的,但同一线性表中的数据元素拥有同样的特征,所以是属于同一数据对象。
√5.在线性表的次序储存构造中,逻辑上相邻的两个元素在物理地点上其实不必定紧邻。
×6.在线性表的次序储存构造中,插入和删除时,挪动元素的个数与该元素的地点相关。
√二单项选择题 ( 请从以下 A,B,C,D 选项中选择一项 )1.线性表是 ( A )。
(A)一个有限序列,能够为空;(B)一个有限序列,不可认为空;(C)一个无穷序列,能够为空;(D)一个无序序列,不可认为空。
2.对次序储存的线性表,设其长度为n,在任何地点上插入或删除操作都是等概率的。
插入一个元素时均匀要挪动表中的( A )个元素。
(A) n/2(B) n+1/2(C) n -1/2(D) n三填空题1.在次序表中做插入操作时第一检查___表能否满了 ______________。
四算法设计题1.设线性表寄存在向量A[arrsize]的前elenum个重量中,且递加有序。
试写一算法,将x插入到线性表的适合地点上,以保持线性表的有序性。
而且剖析算法的时间复杂度。
2.已知一次序表A,其元素值非递减有序摆列,编写一个函数删除次序表中剩余的值同样的元素。
3.编写一个函数,从一给定的次序表A 中删除值在 x~y(x<=y) 之间的所有元素,要求以较高的效率来实现。
提示:能够先将序表中所有在 x~y 之的元素置成一个特别的,其实不立刻除它,而后从最后向前挨次描,拥有特别的元素后,移后来面的元素将其除去。
4.性表中有 n 个元素,每个元素是一个字符,存于向量R[n] 中,写一算法,使 R 中的字符按字母字符、数字字符和其余字符的序摆列。
第2章习题答案●习题2-11.79 62 34 57 26 482.26 34 48 57 62 793.48 56 57 62 79 344.56 57 79 345.26 34 39 48 57 62●习题2-31.ElemType delete_min(List &L){ int i,len,min;ElemType e;if(Emptylist(L){printf(‘线性表为空!\n’); exit(1);}len=LenthList(L);min=1;for(i=2;i〈=len;i++)if(GetList(L,min)〉GetList(L,i))min=i;e= GetList(L,min);DeleteList(L,e,min);InsertList(L,GetList(L,LenthList(L)),min);return e;}2。
bool delete_st(ListTyle &L,ElemType s,ElemType t) {int i;ElemType e;if(Emptylist(L){ printf(‘线性表为空!\n’); return false;}i=1;while(i〈=LenthList(L)){If(GetList(L,i)>=s&&GetList(L,i)<=t)DeleteList(L,e,i);elsei++;}return ture;}void MergeList(List La ,List Lb ,List &Lc ) {InitList(Lc);int i=j=1 , k=0, La_len , Lb_len;ElemType a , b;La_len = LenthList (La); Lb_len=LenthList (Lb);While (( i<=La_len)&& (j<=Lb_len )){a=GetList(La ,i );b=GetList( Lb , j );if (a〈=b ){ InsertList (Lc ,a, ++k ) ;++i ; }else { InsertList ( Lc , b ,++k ) ;++j ; }}while (i〈=La_len){ a=GetList( La ,i++ ) ; InsertList ( Lc ,a, ++k ); }while (j〈=Lb_len ){ b=GetList(Lb , j++ ) ;InsertList ( Lc , b,++k );}}//MergeList习题2—42。
第二章习题1.描述以下三个概念的区别:头指针,头结点,首元素结点。
2.填空:(1)在顺序表中插入或删除一个元素,需要平均移动元素,具体移动的元素个数与有关。
(2)在顺序表中,逻辑上相邻的元素,其物理位置相邻。
在单链表中,逻辑上相邻的元素,其物理位置相邻。
(3)在带头结点的非空单链表中,头结点的存储位置由指示,首元素结点的存储位置由指示,除首元素结点外,其它任一元素结点的存储位置由指示。
3.已知L是无表头结点的单链表,且P结点既不是首元素结点,也不是尾元素结点。
按要求从下列语句中选择合适的语句序列。
a. 在P结点后插入S结点的语句序列是:。
b. 在P结点前插入S结点的语句序列是:。
c. 在表首插入S结点的语句序列是:。
d. 在表尾插入S结点的语句序列是:。
供选择的语句有:(1)P->next=S;(2)P->next= P->next->next;(3)P->next= S->next;(4)S->next= P->next;(5)S->next= L;(6)S->next= NULL;(7)Q= P;(8)while(P->next!=Q) P=P->next;(9)while(P->next!=NULL) P=P->next;(10)P= Q;(11)P= L;(12)L= S;(13)L= P;4.设线性表存于a(1:arrsize)的前elenum个分量中且递增有序。
试写一算法,将X插入到线性表的适当位置上,以保持线性表的有序性。
5.写一算法,从顺序表中删除自第i个元素开始的k个元素。
6.已知线性表中的元素(整数)以值递增有序排列,并以单链表作存储结构。
试写一高效算法,删除表中所有大于mink且小于maxk的元素(若表中存在这样的元素),分析你的算法的时间复杂度(注意:mink和maxk是给定的两个参变量,它们的值为任意的整数)。
【关键字】活动、设计、情况、方法、条件、成就、空间、文件、模式、问题、系统、快速、沟通、执行、保持、特点、位置、关键、稳定、网络、需要、工程、方式、增量、结构、速度、关系、优先、解决、实现数据结构作业一、设n为整数,利用大“O”记号,求下列程序段的时间复杂度1、i=0;k=0;Do{ k=k*10*i; i++;} while (i<n);//2、i=1;{else}//3、x=n; //n>14、x=91;while (y>0)else// T(n)=二、选择题1 C )两大类。
A B.顺序结构、链式结构C D.初等结构、构造型结构2、以下数据结构中,哪一个是线性结构( D )?A.广义表 B. 二叉树 C. 稀疏矩阵 D. 串3、在下面的程序段中,对x的赋值语句的频度为( C )for (i=1;i<=n;i++)for (j=1;j<=n;j++)x=x+1;A. O(2n) B.O(n) C.O(n2) D.O(log2n)4、下面关于线性表的叙述中,错误的是哪一个?( B )A.线性表采用顺序存储,必须占用一片连续的存储单元。
B.线性表采用顺序存储,便于进行插入和删除操作。
C.线性表采用链接存储,不必占用一片连续的存储单元。
D.线性表采用链接存储,便于插入和删除操作。
5、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用( D )存储方式最节省运算时间。
A.单链表 B.仅有头指针的单循环链表 C.双链表 D.仅有尾指针的单循环链表6、静态链表中指针表示的是( B ).A.内存地址 B.数组下标 C.下一元素地址 D.左、右孩子地址7、下面的叙述不正确的是( B、C )A.线性表在链式存储时,查找第i个元素的时间同i的值成正比B. 线性表在链式存储时,查找第i个元素的时间同i的值无关C. 线性表在顺序存储时,查找第i个元素的时间同i 的值成正比D. 线性表在顺序存储时,查找第i个元素的时间同i的值无关8、若长度为n的线性表采用顺序存储结构,在其第i个位置插入一个新元素的算法的时间复杂度为( C )(1<=i<=n+1)。
数据结构(Java版)(第2版)习题解答叶核亚编著目录第0章Java程序设计基础 (1)【习0.1】实验0.1 哥德巴赫猜想。
(1)【习0.2】实验0.2 杨辉三角形。
(1)【习0.3】实验0.3 金额的中文大写形式。
(1)【习0.4】实验0.4 下标和相等的数字方阵。
(1)【习0.5】实验0.5 找出一个二维数组的鞍点 (2)【习0.6】实验0.6 复数类。
(2)【习0.7】实验0.8 图形接口与实现图形接口的类 (2)第1章绪论 (3)【习1.1】实验1.1 判断数组元素是否已按升序排序。
(3)【习1.2】实验1.3 用递归算法求两个整数的最大公因数。
(3)第2章线性表 (5)【习2.1】习2-5 图2.19的数据结构声明。
(5)【习2.2】习2-6 如果在遍历单链表时,将p=p.next语句写成p.next=p,结果会怎样? (5)【习2.3】实验2.2 由指定数组中的多个对象构造单链表。
(5)【习2.4】实验2.2 单链表的查找、包含、删除操作详见8.2.1。
(5)【习2.5】实验2.2 单链表的替换操作。
(6)【习2.6】实验2.2 首尾相接地连接两条单链表。
(6)【习2.7】实验2.2 复制单链表。
(6)【习2.8】实验2.2 单链表构造、复制、比较等操作的递归方法。
(7)【习2.9】建立按升序排序的单链表(不带头结点)。
(8)【习2.10】实验2.6 带头结点的循环双链表类,实现线性表接口。
(10)【习2.11】实验2.5 建立按升序排序的循环双链表。
(14)第3章栈和队列 (17)【习3.1】习3-5 栈和队列有何异同? (17)【习3.2】能否将栈声明为继承线性表,入栈方法是add(0,e),出栈方法是remove(0)?为什么? (17)【习3.3】能否用一个线性表作为栈的成员变量,入栈方法是add(0,e),出栈方法是remove(0)?为什么? (17)【习3.4】能否将队列声明为继承线性表,入队方法是add(e),出队方法是remove(0)?为什么? (17)第4章串 (18)【习4.1】实验4.6 找出两个字符串中所有共同的字符。
数据结构第二章习题第2章线性表一、单项选择题1.线性表就是具备n个_________的非常有限序列。
a.表元素b.字符c.数据元素d.数据项2.线性表是_________。
a.一个非常有限序列,可以为空b.一个非常有限序列,不可以为空c.一个无穷序列,可以为空d.一个无穷序列,不可以为空3.线性表使用链表存储时,其地址_________。
a.必须是连续的b.一定是不连续的c.部分地址必须是连续的d.连续与否均可以4.链表不具备的特点是_________。
a.可以随机出访任一结点b.填入删掉不须要移动元素c.不必事先估算存储空间d.所须要空间与其长度成正比5.设立线性表存有n个元素,以下操作方式中,_________在顺序单上同时实现比在链表上同时实现效率更高。
a.输出第i(1≤i≤n)个元素值b.互换第1个元素与第2个元素的值c.顺序输入这n个元素的值d.输出与给定值x相等的元素在线性表中的序号6.设立线性表中存有2n个元素,以下操作方式中,_________在单链单上同时实现Obrero在顺序单上同时实现效率更高。
a.删掉选定的元素b.在最后一个元素的后面插入一个新元素c.顺序输出前k个元素d.互换第i个元素和第2n-i-1个元素的值(i=0,1…,n-1)7.如果最常用的操作是取第i个结点及其前驱,则采用_________存储方式最节省时间。
a.单链表中b.双链表中c.单循环链表d.顺序表8.与单链表相比,双链表的优点之一是_________。
a.填入和删掉操作方式更直观b.可以展开随机出访c.可以省略字段指针或表尾指针d.出访前后相连结点更有效率9.率先垂范结点的单链表中l为觑的认定条件就是_________。
a.l==nullb.l->next==nullc.l->next==ld.l!=null10.在一个具备n个结点的有序单链表填入一个崭新结点并仍然维持有序的时间复杂度就是_________。
第二章线性表2.1描述以下三个概念的区别:头指针,头结点,首元结点(第一个元素结点)。
并说明头指针和头结点的作用。
答:头指针是一个指针变量,里面存放的是链表中首结点的地址,并以此来标识一个链表。
如链表H,链表L等,表示链表中第一个结点的地址存放在H、L中。
头结点是附加在第一个元素结点之前的一个结点,头指针指向头结点。
当该链表表示一个非空的线性表时,头结点的指针域指向第一个元素结点,为空表时,该指针域为空。
开始结点指第一个元素结点。
头指针的作用是用来惟一标识一个单链表。
头结点的作用有两个:一是使得对空表和非空表的处理得以统一。
二是使得在链表的第一个位置上的操作和在其他位置上的操作一致,无需特殊处理。
2.2填空题1、在顺序表中插入或删除一个元素,需要平均移动(表中一半)元素,具体移动的元素个数与(表长和该元素在表中的位置)有关。
2、顺序表中逻辑上相邻的元素的物理位置(必定)相邻。
单链表中逻辑上相邻的元素的物理位置(不一定)相邻。
3、在单链表中,除了首元结点外,任一结点的存储位置由(其直接前驱结点的链域的值)指示。
4、在单链表中设置头结点的作用是(插入和删除元素不必进行特殊处理)。
2.3何时选用顺序表、何时选用链表作为线性表的存储结构为宜?答:在实际应用中,应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构,通常有以下几方面的考虑:1.基于空间的考虑。
当要求存储的线性表长度变化不大,易于事先确定其大小时,为了节约存储空间,宜采用顺序表;反之,当线性表长度变化大,难以估计其存储规模时,采用动态链表作为存储结构为好。
2.基于时间的考虑。
若线性表的操作主要是进行查找,很少做插入和删除操作时,采用顺序表做存储结构为宜;反之,若需要对线性表进行频繁地插入或删除等的操作时,宜采用链表做存储结构。
并且,若链表的插入和删除主要发生在表的首尾两端,则采用尾指针表示的单循环链表为宜。
2.10 Status DeleteK(SqList &a,int i,int k)//删除线性表a中第i个元素起的k个元素{if(i<1||k<0||i+k-1>a.length) return INFEASIBLE;for(count=1;i+count-1<=a.length-k;count++) //注意循环结束的条件a.elem[i+count-1]=a.elem[i+count+k-1];a.length-=k;return OK;}//DeleteK2.11设顺序表中的数据元素递增有序,试写一算法,将X插入到顺序表的适当位置上,以保持该表的有序性。
《数据结构》第二章线性表习题一、单项选择题1. 线性表是________。
A.一个有限序列,可以为空B.一个有限序列,不可以为空C.一个无限序列,可以为空D.一个无限序列,不可以为空2. 在一个长度为n的顺序表中删除第i个元素(0<=i<=n)时,需向前移动个元素。
A.n-i B.n-i+l C.n-i-1 D.i3. 线性表采用链式存储时,其地址________。
A.必须是连续的B.一定是不连续的C.部分地址必须是连续的D.连续与否均可以4. 从一个具有n个结点的单链表中查找其值等于x的结点时,在查找成功的情况下,需平均比较________个元素结点。
A.n/2 B.n C.(n+1)/2 D.(n-1)/25. 在双向循环链表中,在p所指的结点之后插入s指针所指的结点,其操作是____。
A. p->next=s; s->prior=p;p->next->prior=s; s->next=p->next;B. s->prior=p; s->next=p->next;p->next=s; p->next->prior=s;C. p->next=s; p->next->prior=s;s->prior=p; s->next=p->next;D. s->prior=p; s->next=p->next;p->next->prior=s; p->next=s;6. 设单链表中指针p指向结点m,若要删除m之后的结点(若存在),则需修改指针的操作为________。
A.p->next=p->next->next; B.p=p->next; C.p=p->next->next; D.p->next=p;7. 在一个长度为n的顺序表中向第i个元素(0< i<n+l )之前插入一个新元素时,需向后移动______个元素。