下载文档原格式
第二章线性表习题1 ．填空题(1) 链表中逻辑上相邻的元素的物理位置( ) 相连。
(2) 在单链表中除首结点外，任意结点的存储位置都由( ) 结点中的指针指示。
(3) 在单链表中，设置头结点的作用是在插入或删除首结点时不必对( ) 进行处理。
(4) 已带头结点的单链表L ，指针p 指向L 链表中的一个结点，指针q 是指向L 链表外的一个结点，则：在指针p 所指结点后插入q 所指结点的语句序列是( ) ；在指针p 所指结点前插入q 所指结点的语句序列是( ) ；将q 所指结点插入在链表首结点的语句序列是( ) ；将q 所指结点插入在链表尾结点的语句序列是( ) 。
(5) 已知带表头结点的单链表L ，指针p 指向L 链表中的一个结点（非首结点，非尾结点），则：删除指针p 所指结点的直接后继结点的语句是( ) 。
删除指针p 所指结点的直接前驱结点的语句序列是( ) 。
删除指针p 所指结点的语句序列是( ) 。
删除首结点的语句序列是( ) 。
⑤删除尾结点的语句序列是( ) 。
(6) 已知指针p 指向双向链表中的一个结点（非首结点，非尾结点），则：将结点s 插入在指针p 所指结点的直接后继位置的语句是( ) 。
将结点s 插入在指针p 所指结点的直接前驱位置的语句是( ) 。
删除指针p 所指结点的直接后继结点的语句序列是( ) 。
删除指针p 所指结点的直接前驱结点的语句序列是( ) 。
⑤删除指针p 所指结点的语句序列是( ) 。
(7) 线性表的存储结构有顺序存储和( ) 存储两种。
(8) 线性表的元素长度为4 ，在顺序存储结构下Loc(ai)=2000 ，则Loc(ai ＋1)=( ) 。
(9) 线性表a 的元素长度为L ，在顺序存储结构下Loc(ai)=Loc(a1)+( ) 。
(10) 在线性表的链式存储结构中，某结点的指针字段指向该结点的( ) 两种存储。
(11) 线性表的元素长度为4 ，Loc(ai ＋1)=1000 ，则Loc(a3)=( ) 。
数据结构练习题线性表习题及答案精品文档第二章线性表一．名词解释1.线性结构2.数据结构的顺序实现3.顺序表4.链表5.数据结构的链接实现6. 建表7.字符串8.串9.顺序串 10.链串二、填空题1.为了便于讨论，有时将含n(n>=0)个结点的线性结构表示成(a，a,……a)，其中每n12个a代表一个______。
a称为______结点，a称为______结点，i称为a在线性表中的________ii1n或______。
对任意一对相邻结点a、a(1<=i<n),a称为a的直接______a称为a的直iii┼1i┼1┼i1i接______。
< bdsfid="75" p=""></n),a称为a的直接______a称为a的直iii┼1i┼1┼i1i接______。
<>2.为了满足运算的封闭性，通常允许一种逻辑结构出现不含任何结点的情况。
不含任何结点的线性结构记为______或______。
3.线性结构的基本特征是:若至少含有一个结点，则除起始结点没有直接______外，其他结点有且仅有一个直接______;除终端结点没有直接______外，其它结点有且仅有一个直接______.4.所有结点按1对1的邻接关系构成的整体就是______结构。
5.线性表的逻辑结构是______结构。
其所含结点的个数称为线性表的______，简称______.6.表长为O的线性表称为______7.线性表典型的基本运算包括:______、______、______、______、______、______等六种。
8.顺序表的特点是______。
9.顺序表的类型定义可经编译转换为机器级。
假定每个datatype 类型的变量占用k(k>=1)个内存单元，其中，b是顺序表的第一个存储结点的第一个单元的内存地址，那么，第i个结点a的存储地址为______。
数据结构(线性表)习题与答案数据结构(线性表)习题与答案1. 线性表的定义线性表是一种常用的数据结构，它由一系列元素组成，并且每个元素具有前驱和后继关系。
线性表可以通过顺序存储或链式存储来实现。
2. 线性表的实现方式2.1 顺序存储顺序存储是利用数组来实现线性表的一种方式。
数组的每个元素可以存储一个数据项，通过下标可以快速访问和操作其中的元素。
2.2 链式存储链式存储是通过节点之间的指针关联来实现线性表的一种方式。
每个节点包含数据域和指针域，指针域指向下一个节点。
3. 线性表的基本操作3.1 初始化线性表初始化线性表需要给表头节点分配内存空间，并将头节点的指针域置为空。
3.2 插入元素在线性表的某个位置插入元素，需要先找到插入位置的前一个节点，然后将新节点插入到该位置。
调整节点之间的指针关联即可完成插入操作。
3.3 删除元素删除线性表中的某个元素，需要找到待删除元素的前一个节点，然后将该节点的指针指向待删除节点的下一个节点，释放待删除节点的内存空间即可。
3.4 查找元素查找线性表中某个元素的位置，可以从表头节点开始逐个比较节点的数据域，直到找到目标元素或者遍历结束。
4. 线性表的习题与答案4.1 习题1已知线性表L中的元素按非递减顺序排列，设计一个算法，将元素x插入到L中，保持L的有序性。
解答：1) 从表头节点开始，顺序遍历节点的数据域，找到第一个大于等于x的节点的前一个节点，记为p。
2) 创建新的节点node，将x赋值给node的数据域。
3) 将node的指针域指向p的下一个节点。
4) 将p的指针域指向node。
5) 插入完成。
4.2 习题2已知线性表L中的元素按递减顺序排列，设计一个算法，删除L中所有大于x的元素。
解答：1) 从表头节点开始，顺序遍历节点的数据域，找到第一个小于等于x的节点的前一个节点，记为p。
2) 将p的指针域指向p的下一个节点，删除p的后继节点。
3) 重复执行步骤2，直到遍历结束。
第二章线性表习题一判断题1．线性表的逻辑顺序与存储顺序总是一致的。
2．顺序存储的线性表可以按序号随机存取。
3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。
4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。
5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。
6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。
7．线性表的链式存储结构优于顺序存储结构。
8．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。
9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。
10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。
二单选题 (请从下列A，B，C，D选项中选择一项)1．线性表是( ) 。
(A) 一个有限序列，可以为空；(B) 一个有限序列，不能为空；(C) 一个无限序列，可以为空；(D) 一个无序序列，不能为空。
2．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。
插入一个元素时平均要移动表中的（）个元素。
(A) n/2 (B) n+1/2 (C) n -1/2 (D) n3．线性表采用链式存储时，其地址( ) 。
(A) 必须是连续的；(B) 部分地址必须是连续的；(C) 一定是不连续的；(D) 连续与否均可以。
4．用链表表示线性表的优点是（）。
(A)便于随机存取 (B)花费的存储空间较顺序存储少(C)便于插入和删除 (D)数据元素的物理顺序与逻辑顺序相同5．某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用( )存储方式最节省运算时间。
(A)单链表 (B)双链表 (C)单循环链表 (D)带头结点的双循环链表6．循环链表的主要优点是( )。
数据结构--线性表习题及答案第⼆章线性表⼀、选择题1、若长度为n的线性表采⽤顺序存储结构，在其第i个位置插⼊⼀个新元素算法的时间复杂度（）。
A. O(log2n)B.O(1)C. O(n)D.O(n2)2、若⼀个线性表中最常⽤的操作是取第i个元素和找第i个元素的前趋元素，则采⽤（）存储⽅式最节省时间。
A. 顺序表B. 单链表C. 双链表D. 单循环链表3、具有线性结构的数据结构是（）。
A. 图B. 树C. ⼴义表D.栈4、在⼀个长度为n的顺序表中，在第i个元素之前插⼊⼀个新元素时，需向后移动（）个元素。
A. n-iB. n-i+1C. n-i-1D. i5、⾮空的循环单链表head的尾结点p满⾜（）。
A. p->next==headB. p->next==NULLC. p==NULLD. p==head6、链表不具有的特点是（）。
A. 可随机访问任⼀元素B. 插⼊删除不需要移动元素C. 不必事先估计存储空间D. 所需空间与线性表长度成正⽐7、在双向循环链表中，在p指针所指的结点后插⼊⼀个指针q所指向的新结点，修改指针的操作是（）。
A. p->next=q;q->prior=p;p->next->prior=q;q->next=q;B. p->next=q;p->next->prior=q;q->prior=p;q->next=p->next;C. q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;D. q->next=p->next;q->prior=p;p->next=q;p->next=q;8、线性表采⽤链式存储时，结点的存储地址（）。
A. 必须是连续的B. 必须是不连续的C. 连续与否均可D. 和头结点的存储地址相连续9、在⼀个长度为n的顺序表中删除第i个元素，需要向前移动（）个元素。
线性表部分复习题一、单项选择题1.线性表中______称为线性表的长度。
A、元素的长度B、数据项的数目C、数据的长度D、元素的个数2.线性表是具有n个______的有限序列（n>0）。
A、表元素B、字符C、数据元素D、数据项3.不属于线性表基本运算的是：______。
A、删除运算B、指针运算C、取结点运算D、插入运算4.在下列关于线性表的叙述中，错误的是：______。
A、采用顺序存储的线性表，必须占用一片连续的存储单元B、采用顺序存储的线性表，便于进行插入和删除操作C、采用链式存储的线性表，不必占用一片连续的存储单元D、采用链式存储的线性表，便于进行插入和删除操作5.链表不具有的特点是______。
A、可随机访问任一元素B、插入和删除时不需要移动元素C、不必事先估计存储空间D、所需空间与线性表的长度成正比6.线性表采用链式存储时，结点的存储地址______。
A、必须是不连续的B、连续与否均可C、必须是连续的D、和头结点的存储地址相连续7.算法指的是______。
A、计算机程序B、解决问题的计算方法C、排序算法D、解决问题的有限运算序列8.算法具有“确定性”等5个特性，下面对另外4个特性的描述中错误的是______。
A、可行性B、有零个或多个输入C、有穷性D、有零个或多个输出9.衡量一个算法的质量除了正确性之外，最重要的是要考查______。
A、可行性B、有穷性C、时间复杂度和空间复杂度D、输入和输出10.线性链表(动态)是通过______方式表示元素之间的关系的。
A、保存后继元素地址B、元素的存储顺序C、保存左、右孩子地址D、保存后继元素的数组下标11.设顺序表的每个元素占8个存储单元。
第1个单元的存储地址是100，则第6个元素占用的最后一个存储单元的地址为______。
A、139B、140C、147D、14812.设顺序表的长度为n，并设从表中删除元素的概率相等。
则在平均情况下，从表中删除一个元素需移动的元素个数是______。
第二章线性表一、选择题1.线性表是（）A．一个有限序列，可以为空B．一个有限序列，不可以为空C．一个无限序列，可以为空D．一个无限序列，不可以为空2.一维数组与线性表的特征是（）。
A．前者长度固定，后者长度可变B．两者长度均固定C．后者长度固定，前者长度可变D．两者长度均可变3.用单链表方式存储的线性表，存储每个结点需要两个域，一个数据域，另一个是( ).A．当前结点所在地址域B．指针域C．空指针域D．空闲域4.用链表表示线性表的优点是（）。
A．便于随机存取B．便于进行插入和删除操作C．占用的存储空间较顺序表少D．元素的物理顺序与逻辑顺序相同5.在具有 n 个结点的单链表中，实现___的操作，其算法的时间复杂度都是O（n）。
A．遍历链表和求链表的第i个结点D．删除地址为P的结点的后继结点B．在地址为P的结点之后插入一个结点 C．删除开始结点6.下面关于线性表的叙述中，错误的是（）。
A．线性表采用顺序存储必须占用一片连续的存储单元B．线性表采用顺序存储便于进行插入和删除操作C．线性表采用链式存储不必占用一片连续的存储单元D．线性表采用链式存储便于进行插入和删除操作7.已知单链表的每个结点包括一个指针域next，它指向该结点的后继结点。
现要将指针 q 指向的新结点插入到指针 p 指向的结点之后，下面的操作序列中正确的是（）。
A . q = p->next; p->next = q->next ;B . p->next = q->next; q = p->next ;C . q->next = p->next; p->next = q ;D . p->next = q; q->next = p->next ;8.设 a l，a2， a3为三个结点； p , 10 , 20 代表地址，则如下的链表存储结构称为（）。
A．链表B．单链表C．双向循环链表D．双向链表9.单链表的存储密度（）。
第2章线性表参考答案一、填空1. 【严题集2.2①】在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与表长和该元素在表中的位置有关。
2. 线性表中结点的集合是有限的，结点间的关系是一对一的。
3. 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动n-i+1 个元素。
4. 向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动n-i 个元素。
5. 在顺序表中访问任意一结点的时间复杂度均为 O(1)，因此，顺序表也称为随机存取的数据结构。
6. 【严题集2.2①】顺序表中逻辑上相邻的元素的物理位置必定相邻。
单链表中逻辑上相邻的元素的物理位置不一定相邻。
7. 【严题集2.2①】在单链表中，除了首元结点外，任一结点的存储位置由其直接前驱结点的链域的值指示。
8．在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O（n）。
二、判断正误（在正确的说法后面打勾，反之打叉）（ × ）1. 链表的每个结点中都恰好包含一个指针。
答：错误。
链表中的结点可含多个指针域，分别存放多个指针。
例如，双向链表中的结点可以含有两个指针域，分别存放指向其直接前趋和直接后继结点的指针。
（ × ）2. 链表的物理存储结构具有同链表一样的顺序。
错，链表的存储结构特点是无序，而链表的示意图有序。
（ × ）3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。
错，链表的结点不会移动，只是指针内容改变。
（ × ）4. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。
错，混淆了逻辑结构与物理结构，链表也是线性表！且即使是顺序表，也能存放记录型数据。
（ × ）5. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。
错，正好说反了。
顺序表才适合随机存取，链表恰恰适于“顺藤摸瓜”（ × ）6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
1、线性表是具有n 个______ 的有限序列。
A.数据项B.字符C.数据元素D.表元素正确答案：C2、线性表是_______。
A.一个无限序列，可以为空B.一个有限序列不可以为空C.一个无限序列，不可以为空D.一个有限序列，可以为空正确答案：D3、关于线性表的正确说法是_______。
A.每一个元素都有一个前驱和一个后继元素B.除第一个元素和最后一个元素外，其余元素有且仅有一个前驱和一个后继元素C.表中元素的排序顺序必须是由小到大或者由大到小D.线性表中至少有一个元素正确答案：B4、线性表采用链表存储时，其存放各个元素的单元地址是_______。
A.连续与否均可以B.部份地址必须是连续的C.一定是不连续的D.必须是连续的5、链表不具备的特点是_______。
A.插入删除不需要挪移元素B.所需空间与其长度成正比C.不必事先估计存储空间D.可随机访问任一节点正确答案：D6、线性表的静态链表存储结构与顺序存储结构相比，优点是_______。
A.所有的操作算法实现简单B.便于利用零散的存储器空间C.便于随机存取D.便于插入和删除正确答案：D7、线性表的顺序存储结构和链式存储结构相比，优点是_______。
A.便于随机存取B.便于插入和删除C.所有的操作算法实现简单D.节省存储空间正确答案：A 8、设线性表有n 个元素，以下操作中，_______在顺序表上实现比在链表上实现效率高。
A.交换第1 个元素第2 个元素的值B.输出与给定值x 相等的元素在线性表中的符号C.输入第i ( 1<=i<=n )个元素值D.顺序输出这n 个元素的值正确答案：C9、对于一个线性表，既要求能够较快地进行插入和删除操作，又要求存储结构能够反映数据元素之间的逻辑关系，则应采用_______ 存储结构。
A.顺序B.链式C.散列D.索引正确答案：B10、设线性表中有n 个元素，以下操作，_______ 在单链表上实现要比在顺序表上实现效率高。
