线性表练习题
线性表练习题
一、填空题（每题2分，共16分）
1. 向一个长度为n的顺序表的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动 _____个元素。
2. 在一个长度为n的顺序表中删除第i个元素(1≤i≤n)时，需向前移动 _____个元素。
3. 在顺序表中访问任意一结点的时间复杂度均为 ____，因此，顺序表也称为____存取的数据结构。
4. 在单链表中，除了头结点外，任一结点的存储位置由指示。
5．在n个结点的单链表中要删除已知结点*p，需找到它的的地址。
6. 线性表、栈和队列都是结构，对于栈只能在插入和删除元素；对于队列只能在插入和删除元素。
7. 栈是一种特殊的线性表，允许插入和删除运算的一端称为。不允许插入和删除运算的一端称为。
8. 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。
二、判断题（每题2分，共32分）
（）1. 链表的每个结点中都恰好包含一个指针。
（）2. 链表的物理存储结构具有同链表一样的顺序。
（）3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。
（）4. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。
（）5. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。
（）6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
（）7. 线性表在物理存储空间中也一定是连续的。
（）8. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。
（）9. 顺序存储方式只能用于存储线性结构。
（）10. 线性表的逻辑顺序与存储顺序总是一致的。
（）11. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。（）12. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。
（）13. 栈和队列是一种非线性数据结构。
（）14. 栈和队列的存储方式既可是顺序方式，也可是链接方式。
（）15. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。
（） 16. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。
三、单项选择题（每题2分，共24分）
（）1．数据在计算机存储器内表示时，物理地址连续，数据间的逻辑关系依靠其物理地址间的连续性来表达，称之为：
（A）存储结构（B）逻辑结构（C）顺序存储结构（D）链式存储结构（）2.一个顺序表第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（A）110 （B）108 （C）100 （D）120
（）3. 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是：
（A）访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）
（B）在第i个结点后插入一个新结点（1≤i≤n）
（C）删除第i个结点（1≤i≤n）
（D）将n个结点从小到大排序
（）4. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动个元素（A）8 （B）63.5 （C）63 （D）7
（）5. 链接存储的存储结构所占存储空间：
（A）分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
（B）只有一部分，存放结点值
（C）只有一部分，存储表示结点间关系的指针
（D）分两部分，一部分存放结点值，另一部分存放结点所占单元数
（）6. 链表是一种采用存储结构存储的线性表；
（A）顺序（B）链式（C）星式（D）网状
（）7. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址:
（A）必须是连续的（B）部分地址必须是连续的
（C）一定是不连续的（D）连续或不连续都可以
（）8．线性表Ｌ在情况下适用于使用链式结构实现。
（Ａ）需经常修改Ｌ中的结点值（Ｂ）需不断对Ｌ进行删除插入
（Ｃ）Ｌ中含有大量的结点（Ｄ）Ｌ中结点结构复杂
（）9．单链表的存储密度
（Ａ）大于1；（Ｂ）等于1；（Ｃ）小于1；（Ｄ）不能确定
（）10. 向一个栈顶指针为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;
（）11. 从一个栈顶指针为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;
（）12. 一个队列的数据入队序列是1，2，3，4，则队列出队时的输出序列是___ 。
（A） 4，3，2，1 （B） 1，2，3，4
（C） 1，4，3，2 （D） 3，2，4，1
四、简答题（每题5分，共10分）
1.试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？
2 .描述以下三个概念的区别：头指针、头结点、首元结点（第一个元素结点）。在单链表中设置头结点的作用是什么？
五、读程序（每题6分，共18分）
1.写出下列程序段的输出结果（栈的元素类型SElem Type为char）。
void main( ){
Stack S;
Char x,y;
InitStack(S);
x=’c’;y=’k’;
Push(S,x); Push(S,’a’); Push(S,y);
Pop(S,x); Push(S,’t’); Push(S,x);
Pop(S,x); Push(S,’s’);
while(!StackEmpty(S)){ Pop(S,y);printf(y); };
Printf(x);
}
2.写出下列程序段的输出结果（队列中的元素类型QElem Type为char）。void main( ){
Queue Q; Init Queue (Q);
Char x=’e’; y=’c’;
EnQ ueue (Q,’h’); En Q ueue (Q,’r’); En Queue (Q, y); DeQueue (Q,x); EnQueue (Q,x);
DeQueue (Q,x); EnQ ueue (Q,’a’);
while(!QueueEmpty(Q)){ DeQueue (Q,y);printf(y); };
Printf(x);
}
3.简述以下算法的功能（栈和队列的元素类型均为int）。
void algo3(Queue &Q){
Stack S; int d;
InitStack(S);
while(!QueueEmpty(Q)){
DeQueue (Q,d); Push(S,d);
};
while(!StackEmpty(S)){
Pop(S,d); EnQueue (Q,d);
}
}
第二章 考研试题精选
第二章线性表作业 一、选择题 1．下述哪一条是顺序存储结构的优点？（） A．存储密度大B．插入运算方便 C．删除运算方便D．可方便地用于各种逻辑结构的存储表示 2．下面关于线性表的叙述中，错误的是哪一个？（） A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 3．线性表是具有n个（）的有限序列（n>0）。 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. 静态链表中指针表示的是（）. A．内存地址B．数组下标C．下一元素地址D．左、右孩子地址 9. 链表不具有的特点是（） A．插入、删除不需要移动元素B．可随机访问任一元素 C．不必事先估计存储空间D．所需空间与线性长度成正比 10. 下面的叙述不正确的是（）
数据结构试题及答案
数据结构试题 一、单选题 1、在数据结构的讨论中把数据结构从逻辑上分为（C ） A 内部结构与外部结构 B 静态结构与动态结构 C 线性结构与非线性结构 D 紧凑结构与非紧凑结构。 2、采用线性链表表示一个向量时，要求占用的存储空间地址（D ） A 必须是连续的 B 部分地址必须是连续的 C 一定是不连续的 D 可连续可不连续 3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（ D ）。 A n B n/2 C (n-1)/2 D (n+1)/2 4、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（ D ）。 A s→link = p→link;p→link = s; B p→link = s; s→link = q; C p→link = s→link;s→link = p; D q→link = s;s→link = p; 5、如果想在4092个数据中只需要选择其中最小的5个，采用（ C ）方法最好。 A 起泡排序 B 堆排序 C 锦标赛排序 D 快速排序 6、设有两个串t和p，求p在t中首次出现的位置的运算叫做（ B ）。 A 求子串 B 模式匹配 C 串替换 D 串连接 7、在数组A中，每一个数组元素A[i][j]占用3个存储字，行下标i从1到8，列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中，则存放
该数组至少需要的存储字数是（ C ）。 A 80 B 100 C 240 D 270 8、将一个递归算法改为对应的非递归算法时，通常需要使用（ A ）。 A 栈 B 队列 C 循环队列 D 优先队列 9、一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为（ C ）。 10、在循环队列中用数组A[0..m-1] 存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（ D ）。 A ( front - rear + 1) % m B ( rear - front + 1) % m C ( front - rear + m) % m D ( rear - front + m) % m 11、一个数组元素a[i]与（ A ）的表示等价。 A *（a+i） B a+i C *a+i D &a+i 12、若需要利用形参直接访问实参，则应把形参变量说明为（ B ）参数。 A 指针 B 引用 C 值 D 变量 13、下面程序段的时间复杂度为（ C ） for (int i=0;i 第2章线性表 一选择题 下列程序段的时间复杂度为（ C ）。 for( int i=1;i<=n;i++) for( int j=1;j<= m; j++) A[i][j] = i*j ; A. O(m2) B. O(n2) C. O(m*n) D. (m+n) 下面关于线性表的叙述中，错误的是哪一个？（B ） A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 线性表是具有n个（ C ）的有限序列（n>0）。 A．表元素B．字符C．数据元素D．数据项 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。 A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。 A．单链表B．仅有头指针的单循环链表 C．双链表D．仅有尾指针的单循环链表 设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( D )最节省时间。A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（ D ）存储方式最节省运算时间。 A．单链表B．双链表C．单循环链表D．带头结点的双循环链表 链表不具有的特点是（ B ） A．插入、删除不需要移动元素B．可随机访问任一元素 C．不必事先估计存储空间D．所需空间与线性长度成正比 下面的叙述不正确的是（B,C ） A．线性表在链式存储时，查找第i个元素的时间同i的值成正比 B. 线性表在链式存储时，查找第i个元素的时间同i的值无关 C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比 D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ C ）(1<=i<=n+1)。 A. O(0) B. O(1) C. O(n) D. O(n2) 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（C ）。 A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1) 线性表（a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（ C ）A．O（i）B．O（1）C．O（n）D．O（i-1） 循环链表H的尾结点P的特点是（A ）。 A．P->next=H B．P->next= H->next C．P=H D．P=H->next 完成在双循环链表结点p之后插入s的操作是（D ）； 第2章线性表 班级学号__________-姓名 一、判断正误 （×）1. 链表的每个结点中都恰好包含一个指针。 链表中的结点可含多个指针域，分别存放多个指针。例如，双向链表中的结点可以含有两个指针域，分别存放指向其直接前趋和直接后继结点的指针。 （×）2. 链表的物理存储结构具有同链表一样的顺序。 链表的存储结构特点是无序，而链表的示意图有序。 （×）3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。 链表的结点不会移动，只是指针内容改变。 （×）4. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 混淆了逻辑结构与物理结构，链表也是线性表！且即使是顺序表，也能存放记录型数据。 （×）5. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 正好说反了。顺序表才适合随机存取，链表恰恰适于“顺藤摸瓜” （×）6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 前一半正确，但后一半说法错误，那是链式存储的优点。顺序存储方式插入、删除运算效率较低，在表长为n的顺序表中，插入和删除一个数据元素，平均需移动表长一半个数的数据元素。 （×）7. 线性表在物理存储空间中也一定是连续的。 线性表有两种存储方式，顺序存储和链式存储。后者不要求连续存放。 （×）8. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。 线性表有两种存储方式，在顺序存储时，逻辑上相邻的元素在存储的物理位置次序上也相邻。 （×）9. 顺序存储方式只能用于存储线性结构。 顺序存储方式不仅能用于存储线性结构，还可以用来存放非线性结构，例如 完全二叉树是属于非线性结构，但其最佳存储方式是顺序存储方式。（后一节介绍） （×）10. 线性表的逻辑顺序与存储顺序总是一致的。 理由同7。链式存储就无需一致。 二、单项选择题 （C ）1．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：（A）存储结构（B）逻辑结构（C）顺序存储结构（D）链式存储结构（ B ）2. 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（A）110 （B）108 （C）100 （D）120 （ A ）3. 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是： （A）访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） （B）在第i个结点后插入一个新结点（1≤i≤n） （C）删除第i个结点（1≤i≤n） （D）将n个结点从小到大排序 （ B ）4. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动个元素（A）8 （B）63.5 （C）63 （D）7 （ A ）5. 链式存储的存储结构所占存储空间： 习题二 一、选择题 1．在一个长度为n的顺序表中删除第i个元素（0＜i 一、判断题 1．线性表的逻辑顺序与存储顺序总是一致的。(FALSE) 2．顺序存储的线性表可以按序号随机存取。(TRUE) 3．顺序表的插入和删除一个数据元素，每次操作平均只有近一半的元素需要移动。（TRUE） 4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。（TRUE） 5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。（FALSE） 6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。（TRUE）7．线性表的链式存储结构优于顺序存储结构。（FALSE） 8．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。（TRUE） 9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。（TRUE）10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。（FALSE） 二、单选题、(请从下列A，B，C，D选项中选择一项) 11．线性表是( ) 。 (A) 一个有限序列，可以为空；(B) 一个有限序列，不能为空； (C) 一个无限序列，可以为空；(D) 一个无序序列，不能为空。 答：A 12．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等 概率的。插入一个元素时平均要移动表中的（）个元素。 (A) n/2 (B) (n+1)/2 (C) (n –1)/2 (D) n 答：A 13．线性表采用链式存储时，其地址( D ) 。 (A) 必须是连续的；(B) 部分地址必须是连续的； (C) 一定是不连续的；(D) 连续与否均可以。 答：D 14．用链表表示线性表的优点是（）。 (A)便于随机存取 (B)花费的存储空间较顺序存储少 (C)便于插入和删除 (D)数据元素的物理顺序与逻辑顺序相同 答：C 15. 某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用( )存储方式最节省运算时间。 (A)单链表 (B)双链表 (C)单循环链表 序号 数据结构实验报告 班级姓名同组者/ 成绩 日期 3.9指导教师 实验名称实验一线性表及其应用 一、实验目的 1、深刻理解线性表的逻辑特性及其顺序、链式存储方式的特点。 2、熟练掌握线性表的常用操作（建立、插入、删除、遍历等）在顺序、链式存储上的实现。 3、加深对C/C++等编程语言的相关知识点的理解（如结构体、指针、函数、引用参数等）。 二、实验内容 1、根据给定的整型数组，以尾插法建立一个单链表，并实现以下操作： ①查找：输入一个欲查找的整数，找到则显示第一个相匹配的整数在单链表中所处的位置，若不存在，则显示提示信息。 ②删除：输入一个欲删除的整数e ，若存在则在单链表中删除第一个值为 e 的元素。 ③插入：输入一个欲插入位置i 和欲插入元素e，将e 插入到第i 个整数之前（注意i 的合法性）。 A、算法思想 ①创建 head 为头结点指针，初始时head->next 为NULL ；tail 始终指向当前链表的最后一个元素，其初始时指向头结点；p 始终指向每次申请的新结点，修改p->data 为当前读入的整数；修改tail->next 为p ，修改tail 为p ；最后修改tail->next 为NULL ，。 ②插入 找到插入点的前驱（即第i-1 个结点）的指针p ；s 指向新申请的结点；修改s->data 为参数e，修改s->next 为p->next ，修改p->next 为s 。 ③查找 ……利用p进行遍历，直到节点的数据和所给的数据相同，输出节点的位置 ④删除 ……利用p进行遍历，并总是将p的前一节点的指针赋给pre，一旦找到，则删除节点并 退出循环，没有到话，反馈相关信息 B、算法源码 /* *线性表及其应用 */ #include 第2章线性表 一选择题 1．下述哪一条是顺序存储结构的优点？（ A ） A．存储密度大 B．插入运算方便 C．删除运算方 便 D．可方便地用于各种逻辑结构的存储表示 2．下面关于线性表的叙述中，错误的是哪一个？（ B ）A．线性表采用顺序存储，必须占用一片连续的存储单元。B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。D．线性表采用链接存储，便于插入和删除操作。 3．线性表是具有n个（ C ）的有限序列（n>0）。 A．表元素 B．字符 C．数据元 素 D．数据项 E．信息项 4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。 AHA12GAGGAGAGGAFFFFAFAF A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表 5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。 A．单链表 B．仅有头指针的单循环链 表 C．双链表D．仅有尾指针的单循环链表 6．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( D )最节省时间。 A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表 7．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（ D ）存储方式最节省运算时间。 AHA12GAGGAGAGGAFFFFAFAF A．单链表 B．双链表 C．单循环链 表 D．带头结点的双循环链表 8. 静态链表中指针表示的是（ BC ）. A．内存地址 B．数组下标 C．下一元素地址D．左、右孩子地址 9. 链表不具有的特点是（ C ） A．插入、删除不需要移动元素 B．可随机访问任一元素C．不必事先估计存储空间 D．所需空间与线性长度成正比 10. 下面的叙述不正确的是（ BC ） A．线性表在链式存储时，查找第i个元素的时间同i的值成正比 AHA12GAGGAGAGGAFFFFAFAF 填空题（10 * 1’ = 10’） 一、概念题 .当对一个线性表经常进行的是插入和删除操作时，采用链式存储结构为宜。 .当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，最好采用顺序存储结构。 .带头结点的单链表L中只有一个元素结点的条件是L->Next->Next==Null。 .循环队列的引入，目的是为了克服假溢出。 .长度为0的字符串称为空串。 .组成串的数据元素只能是字符。 .设T和P是两个给定的串，在T中寻找等于P的子串的过程称为模式匹配，又称P为模式。 .为了实现图的广度优先搜索，除一个标志数组标志已访问的图的结点外，还需要队列存放被访问的结点实现遍历。 .广义表的深度是广义表中括号的重数 .有向图G可拓扑排序的判别条件是有无回路。 .若要求一个稠密图的最小生成树，最好用Prim算法求解。 . 直接定址法法构造的哈希函数肯定不会发生冲突。 .排序算法所花费的时间，通常用在数据的比较和交换两大操作。 .通常从正确性﹑可读性﹑健壮性﹑时空效率等几个方面评价算法的（包括程序）的质量。 .对于给定的n元素，可以构造出的逻辑结构有集合关系﹑线性关系树形关系﹑图状关系四种。 .存储结构主要有顺序存储﹑链式存储﹑索引存储﹑散列存储四种。 .抽象数据类型的定义仅取决于它的一组逻辑特性，而与存储结构无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部使用。 .一个算法具有五大特性：有穷性﹑确定性﹑可行性，有零个或多个输入﹑有一个或多个输入。 .在双向链表结构中，若要求在p指针所指的结点之前插入指针为s所指的结点，则需执行下列语句：s->prior= p->prior; s->next= p; p->prior- next= s; p->prior= s;。 .在单链表中设置头结点的作用是不管单链表是否为空表，头结点的指针均不空，并使得对单链表的操作（如插入和删除）在各种情况下统一。 .队列是限制在表的一端进行插入和在另一端进行删除的线性表，其运算遵循先进先出原则。 .栈是限定尽在表位进行插入或删除操作的线性表。 .在链式队列中，判定只有一个结点的条件是(Q->rear==Q->front)&&(Q->rear!=NULL)。 .已知链队列的头尾指针分别是f和r，则将x入队的操作序列是node *p=(node *)malloc(node); p->next=x; p->next=NULL; if(r) {r->next=p; r=p;} else {r=p; f=p;}。 .循环队列的满与空的条件是(rear+1)%MAXSIZE==fornt和(front=-1&&rear+1==MAXSIZE)。 .串是一种特殊的线性表，其特殊性表现在数据元素都是由字符组成。 .字符串存储密度是串值所占存储位和实际分配位的比值，在字符串的链式存储结构中其结点大小是可变的。 .所谓稀疏矩阵指的是矩阵中非零元素远远小于元素总数，则称该矩阵为矩阵中非零元素远远小于元素总数，则称该矩阵为稀疏矩阵。 .一维数组的逻辑结构是线性结构，存储结构是顺序存储结构；对二维或多维数组，分别按行优先和列优先两种不同的存储方式。 .在有向图的邻接矩阵表示中，计算第i个顶点入度的方法是求邻接矩阵中第i列非0元素的个数。 网中，结点表示活动，边表示活动之间的优先关系，AOE网中，结点表示事件，边表示活动。 .按排序过程中依据不同原则对内部排序方法进行分类，主要有选择排序﹑交换排序﹑插入排序归并排序等4类。 .在堆排序、快速排序和归并排序中若只从排序结果的稳定性考虑，则应选择归并排序方法；若只从平均情况下排序最快考虑，则应选择快速排序方法；若只从最坏情况下排序最快且要节省类存考虑，则应选择堆排序方法。 .直接插入排序用监视哨的作用是存当前要的插入记录，可又省去查找插入位置时对是否出界的判断。 .设表中元素的初始状态是按键值递增的，则直接插入排序最省时间，快速排序最费时间。 .下列程序判断字符串s是否对称，对称则返回1，否则返回0；如?(“abba”)返回1，?（”abab”）返回0. Int f (char*s) { Int i=0,j=0; 求串长*/ 第2章线性表习题参考答案 习题二 一、选择题 1. 链式存储结构的最大优点是（ D ）。 A.便于随机存取 B.存储密度高 C.无需预分配空间 D.便于进行插入和删除操作 2. 假设在顺序表{a0,a1,……,an－1}中，每一个数据元素所占的存储单元的数目为4，且第0 个数据元素的存储地址为100，则第7个数据元素的存储地址是（ D ）。 A. 106 B. 107 C.124 D.128 3. 在线性表中若经常要存取第i个数据元素及其前趋，则宜采用（ A ）存储方式。 A.顺序表 B. 带头结点的单链表 C.不带头结点的单链表 D. 循环单链表 4. 在链表中若经常要删除表中最后一个结点或在最后一个结点之后插入一个新结点，则宜 采用（ C ）存储方式。 A. 顺序表 B. 用头指针标识的循环单链表 C. 用尾指针标识的循环单链表 D. 双向链表 5. 在一个单链表中的p和q两个结点之间插入一个新结点， 假设新结点为S,则修改链的 java语句序列是（ D ）。 A. s.setNext(p); q.setNext(s); B. p.setNext(s.getNext()); s.setNext(p); C. q.setNext(s.getNext()); s.setNext(p); D. p.setNext(s); s.setNext(q); 6. 在一个含有n个结点的有序单链表中插入一个 新结点，使单链表仍然保持有序的算法的 时间复杂度是（ C ）。 A. O(1) B. O(log2n) C. O(n) D. O(n2) 7. 要将一个顺序表{a0,a1,……,an-1}中第i个数据元素 ai(0≤i≤n-1)删除，需要移动（ B ） 个数据元素。 A. i B. n-i-1 C. n-i D. n-i+1 8. 在带头结点的双向循环链表中的p结点之后插入一个新结 点s，其修改链的java语句序 列是（ D ）。 A. p.setNext(s); s.setPrior(p); p.getNext().setPrior(s); s.setNext(p.getPrior()); B. p.setNext(s); p.getNext().setPrior(s); s.setPrior(p); s.setNext(p.getNext()); C. s.setPrior(p); s.setNext(p.getNext()); p.setNext(s); p.getNext().setPrior(s); 实验1 线性表的基本操作 一、需求分析 目的： 掌握线性表运算与存储概念，并对线性表进行基本操作。 1.初始化线性表； 2.向链表中特定位置插入数据； 3.删除链表中特定的数据； 4.查找链表中的容； 5.销毁单链表释放空间； 二、概要设计 ●基础题 主要函数： 初始化线性表InitList（List* L，int ms） 向顺序表指定位置插入元素InsertList（List* L，int item，int rc）删除指定元素值的顺序表记录DeleteList1(List* L,int item) 删除指定位置的顺序表记录 DeleteList2（List* L,int rc） 查找顺序表中的元素 FindList（List L，int item） 输出顺序表元素OutputList（List L） 实验步骤： 1，初始化顺序表 2，调用插入函数 3，在顺序表中查找指定的元素 4，在顺序表中删除指定的元素 5，在顺序表中删除指定位置的元素 6，遍历并输出顺序表 ●提高题 要求以较高的效率实现删除线性表中元素值在x到y（x和y自定义）之间的所有元素 方法： 按顺序取出元素并与x、y比较，若小于x且大于y，则存进新表中。 编程实现将两个有序的线性表进行合并，要求同样的数据元素只出现一次。 方法： 分别按顺序取出L1，L2的元素并进行比较，若相等则将L1元素放进L中，否则将L 1，L2元素按顺序放进L。 本程序主要包含7个函数 主函数main() 初始化线性表InitList（List* L，int ms） 向顺序表指定位置插入元素InsertList（List* L，int item，int rc）删除指定元素值的顺序表记录DeleteList1(List* L,int item) 删除指定位置的顺序表记录 DeleteList2（List* L,int rc） 查找顺序表中的元素 FindList（List L，int item） 输出顺序表元素OutputList（List L） 提高题的程序 void Combine(List* L1,List* L2,List* L) void DeleteList3(List* L,int x,int y) 二、详细设计 初始化线性表InitList（List* L，int ms） void InitList(List* L,int ms) { L->list=(int*)malloc(LIST_INIT_SIZE*sizeof(int)); L->size=0; L->MAXSIZE=LIST_INIT_SIZE; 第2章线性表 1．下面关于线性表的叙述中，错误的是哪一个？（）A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 2．线性表是具有n个（）的有限序列（n>0）。 A．表元素 B．字符 C．数据元素 D．数据项 E．信息项 3.线性表（ a1,a2,…,an）以链接方式存储时，访问第i位置 元素的时间复杂性为（） A．O（i） B．O（1） C．O（n） D．O（i-1） 4.若长度为n的线性表采用顺序存储结构，在其第i个位置插 入一个新元素的算法的时间复杂度为（）(1<=i<=n+1)。 A. O(0) B. O(1) C. O(n) D. O(n2) 5. 对于顺序存储的线性表，访问结点和增加、删除结点的时间 复杂度为（）。 A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1) 6．对于一个头指针为head的带头结点的单链表，判定该表为空 表的条件是（） A．head==NULL B．head→next==NULL C．head→next==head D．head!=NULL 7.链表不具有的特点是（） A．可随机访问任一元素 B．插入、删除不需要移动元素 C．不必事先估计存储空间 D．所需空间与线性长度成正比 8.在双向链表指针p的结点前插入一个指针q的结点操作是（）。 >Llink=q;q->Rlink=p;p->Llink->Rlink=q;q->Llink=q； >Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink ; C. q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q; >Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q ; 9.在单链表指针为p的结点之后插入指针为s的结点，正确的 操作是：（）。 A． s->next=p->next;p->next=s; B． p->next=s;s->next=p->next; C．p->next=s;p->next=s->next; D． p->next=s->next;p->next=s; 10．对于一个头指针为head的带头结点的单链表，判定该表为 第一章概论 一、选择题 1、研究数据结构就是研究（D ）。 A. 数据的逻辑结构 B. 数据的存储结构 C. 数据的逻辑结构和存储结构 D. 数据的逻辑结构、存储结构及其基本操作（研究非数值计算的程序设计问题中，计算机操作对象以及他们之间的关系和操作） 2、算法分析的两个主要方面是（ A ）。 A. 空间复杂度和时间复杂度 B. 正确性和简单性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。（线性结构就是：在非空有限集合中，存在为一个被称为第一个的数据元素和最后一个元素，有除了第一个元素，集合中每一个元素均只有一个前驱，除了最后一个元素有唯一后继）（链表、栈、队列、数组、串） A. 图 B. 树 C. 广义表（线性表的推广） D. 栈 4、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（B ）等5个特性。 A. 可执行性、可移植性和可扩充性 B. 可执行性、有穷性和确定性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是（ C ）。 for(i=0;i 6、算法是（D ）。为了解决某一问题而规定的一个有限长的操作序列 A. 计算机程序 B. 解决问题的计算方法 C. 排序算法 D. 解决问题的有限运算序列 7、某算法的语句执行频度为（3n+nlog2n+n2+8）,其时间复杂度表示（C ）。 A. O(n) B. O(nlog2n) C. O(n2) D. O(log2n) 8、下面程序段的时间复杂度为（ C ）。 i=1; while(i<=n) i=i*3; A. O(n) B. O(3n) C. O(log3n) D. O(n3) 9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（B ）和运算等的学科。（关系和操作） A. 结构 B. 关系 C. 运算 D. 算法 10、下面程序段的时间复杂度是（ A ）。 i=s=0; while(s 第2章习题 (1) 第2章习题 2.1若将顺序表中记录其长度的分量listlen改为指向最后一个元素的位置last，在实现各基本运算时需要做那些修改？ 【解】 //用线性表最后一个元素的下标last代替listLen实现顺序表 #define MAXLEN 100 typedef int elementType; typedef struct sllLast { elementType data[MAXLEN]; int last; }seqList; //初始化 void initialList(seqList &S) { https://www.wendangku.net/doc/3a11116392.html,st=-1; } //求表长度 int listLength(seqList S) { return https://www.wendangku.net/doc/3a11116392.html,st+1; } //按序号取元素 bool getElement(seqList S,int i,elementType &x) { if(i<1 || i>https://www.wendangku.net/doc/3a11116392.html,st+1) //i为元素编号，有效范围在https://www.wendangku.net/doc/3a11116392.html,st+1之间 return false; else { x=S.data[i-1]; return true; } } //查找元素x，成功：返回元素编号；失败：返回0 int listLocate(seqList S,elementType x) { int i; for(i=0;i<=https://www.wendangku.net/doc/3a11116392.html,st;i++) { if(S.data[i]==x) return i+1; //找到，转换为元素编号输出} return 0; } //插入元素 int listInsert(seqList &S,elementType x, int i) { int k; if(https://www.wendangku.net/doc/3a11116392.html,st>MAXLEN-1) return 0; //表满，返回0 else if(i<1 || i>https://www.wendangku.net/doc/3a11116392.html,st+2) return 1; //插入位置查处范围，返回1 else { for(k=https://www.wendangku.net/doc/3a11116392.html,st;k>=i-1;k--) S.data[k+1]=S.data[k]; S.data[i-1]=x; https://www.wendangku.net/doc/3a11116392.html,st++; return 2; } } //删除元素 int listDelete(seqList &S,int i) { int k; if(https://www.wendangku.net/doc/3a11116392.html,st==-1) return 0; //空表，返回0 else if(i<1 || i>https://www.wendangku.net/doc/3a11116392.html,st+1) return 1; //删除元素编号超出范围，返回1 else 北京邮电大学电信工程学院 数据结构实验报告 实验名称：实验1——线性表 学生姓名： 班级： 班内序号： 学号： 日期： 1．实验要求 1、实验目的：熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法 学习指针、模板类、异常处理的使用 掌握线性表的操作的实现方法 学习使用线性表解决实际问题的能力 2、实验内容： 题目1： 线性表的基本功能： 1、构造：使用头插法、尾插法两种方法 2、插入：要求建立的链表按照关键字从小到大有序 3、删除 4、查找 5、获取链表长度 6、销毁 7、其他：可自行定义 编写测试main()函数测试线性表的正确性。 2. 程序分析 2.1 存储结构 带头结点的单链表 2.2 关键算法分析 1.头插法 a、伪代码实现：在堆中建立新结点 将x写入到新结点的数据域 修改新结点的指针域 修改头结点的指针域,将新结点加入链表中b、代码实现： Linklist::Linklist(int a[],int n)//头插法 {front=new Node; front->next=NULL; for(int i=n-1;i>=0;i--) {Node*s=new Node; s->data=a[i]; s->next=front->next; front->next=s; } } 2、尾插法 a、伪代码实现：a.在堆中建立新结点 b.将a[i]写入到新结点的数据域 c.将新结点加入到链表中 d.修改修改尾指针 b、代码实现: Linklist::Linklist(int a[],int n,int m)//尾插法 {front=new Node; Node*r=front; for(int i=0;i 第 1 章绪论 课后习题讲解 1. 填空 ⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。 【解答】集合，线性结构，树结构，图结构 ⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺在一般情况下，一个算法的时间复杂度是（）的函数。 【解答】问题规模 ⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。 第2章线性表练习题答案 一、填空 1. 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动n-i+1 个元素。 2. 向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动n-i 个元素。 3. 在顺序表中访问任意一结点的时间复杂度均为O(1)，因此，顺序表也称为随机存取的数据结构。 4. 在单链表中，除了首元结点外，任一结点的存储位置由其直接前驱结点的链域的值指示。 5．在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O（n）。 二、判断正误 （×）1. 链表的每个结点中都恰好包含一个指针。 答：错误。链表中的结点可含多个指针域，分别存放多个指针。例如，双向链表中的结点可以含有两个指针 域，分别存放指向其直接前趋和直接后继结点的指针。 （×）2. 链表的物理存储结构具有同链表一样的顺序。错，链表的存储结构特点是无序，而链表的示意图有序。（×）3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。错，链表的结点不会移动，只是指针内容改变。 （×）4. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 错，混淆了逻辑结构与物理结构，链表也是线性表！且即使是顺序表，也能存放记录型数据。 （×）5. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 错，正好说反了。顺序表才适合随机存取，链表恰恰适于“顺藤摸瓜” （×）6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 错，前一半正确，但后一半说法错误，那是链式存储的优点。顺序存储方式插入、删除运算效率较低， 在表长为n的顺序表中，插入和删除一个数据元素，平均需移动表长一半个数的数据元素。 （×）7. 线性表在物理存储空间中也一定是连续的。 错，线性表有两种存储方式，顺序存储和链式存储。后者不要求连续存放。 （×）8. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。 错误。线性表有两种存储方式，在顺序存储时，逻辑上相邻的元素在存储的物理位置次序上也相邻。（×）9. 顺序存储方式只能用于存储线性结构。 错误。顺序存储方式不仅能用于存储线性结构，还可以用来存放非线性结构，例如完全二叉树是属于 非线性结构，但其最佳存储方式是顺序存储方式。 （×）10. 线性表的逻辑顺序与存储顺序总是一致的。 错，理由同7。链式存储就无需一致。 三、单项选择题 （C）1．数据在计算机存储器内表示时，物理地址连续，数据间的逻辑关系依靠其物理地址间的连续性来表达，称之为： （A）存储结构（B）逻辑结构（C）顺序存储结构（D）链式存储结构（ B ）2.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（A）110 （B）108 （C）100 （D）120 （A）3. 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是： （A）访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） （B）在第i个结点后插入一个新结点（1≤i≤n） （C）删除第i个结点（1≤i≤n） （D）将n个结点从小到大排序 （ B ）4. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动个元素（A）8 （B）63.5 （C）63 （D）7线性表练习题(答案)
数据结构第2章作业 线性表(答案)
数据结构线性表2答案
线性表练习题答案
数据结构线性表实验报告
第二章线性表答案
数据结构课后习题及答案
第2章线性表习题参考答案
数据结构_实验1_线性表的基本操作
第2章线性表(课堂作业)
数据结构试题答案
第2章线性表习题解答
数据结构实验一题目一线性表实验报告
数据结构习题与答案
线性表练习题答案