数据结构练习 第二章 线性表资料
数据结构练习第二章线性表
一、选择题
1. 下面关于线性表的叙述错误的是（）。
A.线性表采用顺序存储必须占用一片连续的存储空间
B. 线性表采用链式存储不必占用一片连续的存储空间
C. 线性表采用链式存储便于插入和删除操作的实现
D. 线性表采用顺序存储便于插入和删除操作的实现
2. 设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针
的操作序列为（）。
A.q=p->next；p->data=q->data；p->next=q->next；free(q)；
B. q=p->next；q->data=p->data；p->next=q->next；free(q)；
C. q=p->next；p->next=q->next；free(q)；
D. q=p->next；p->data=q->data；free(q)；
3. 设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为
（）。
n) C. O(1) D. O(n2)
A. O(n)
B. O(nlog
2
4．设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（）。
A. O(log
n) B. O(1) C. O(n2) D. O(n)
2
5．设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（）。
A. head==0
B.head->next==0
C. head->next==head
D.head!=0
6．设带有头结点的单向循环链表的头指针变量为head，则其判空条件是（）。
A. head==0
B. head->next==0
C. head->next==head
D. head!=0
7．建立一个长度为n的有序单链表的时间复杂度为（）
A. O(n)
B. O(1)
C. O(n2)
D. O(log
n)
2
8．设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动（）个元素。
A. n-i
B. n+l -i
C. n-1-i
D. i
9．设指针变量p指向双向链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为（）。
A. p->right=s； s->left=p； p->right->left=s； s->right=p->right；
B. s->left=p；s->right=p->right；p->right=s； p->right->left=s；
C. p->right=s； p->right->left=s； s->left=p； s->right=p->right；
D. s->left=p；s->right=p->right；p->right->left=s； p->right=s；
10．设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用下列（）存储方式最节省运算时间。
A. 单向链表 B .单向循环链表
C. 双向链表
D. 双向循环链表
11．设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B插入结点X的操作序列为（）。
A. s->next=p->next；p->next=-s；
B. q->next=s； s->next=p；
C. p->next=s->next；s->next=p；
D. p->next=s；s->next=q；12．在一个长度为n的顺序存储的线性表中，向第i个元素（1≤i≤n+1）之前插入一个新元素时，需要从后向前依次后移（）个元素。
A．n-i B．n-i+1 C．n-i-1 D．i
13．在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行（）。
A. q->next=p->next;p->next=q;
B. p->next=q->next;q=p;
C. q->next=p->next;p->next=q;
D. p->next=q->next;q->next=p;
14．在单链表中，存储每个结点需要有两个域，一个是数据域，另一个是指针域，指针域指向该结点的（）
A.直接前趋
B.直接后继
C.开始结点
D.终端结点
15．将两个各有n个元素的有序表合并成一个有序表，其最少的比较次数为（）
A.n
B.2n-1
C.2n
D.n2
16．线性表采用链式存储结构时，要求内存中可用存储单元的地址( )
A. 必须是连续的
B. 必须是部分连续的
C. 一定是不连续的
D. 连续和不连续都可以
17．设h是指向非空带表头结点的循环链表的头指针，p是辅助指针。执行程序段
p=h;
while (p->next->next!=h)
p=p->next;
p->next=h;
后（其中，p->next为p指向结点的指针域），则( )
A. p->next指针指向链尾结点
B. h指向链尾结点
C. 删除链尾前面的结点
D. 删除链尾结点
18．设顺序表有19个元素，第一个元素的地址为200，且每个元素占3个字节，则第14个元素的存储地址为( )
A.236
B.239
C.242
D.245
19．设顺序表有9个元素，则在第3个元素前插入一个元素所需移动元素的个数为( )
A.5
B.6
C.7
D.9
20．设p为指向双向循环链表中某个结点的指针，p所指向的结点的两个链域分别用p→llink和p→rlink表示，则同样表示p指针所指向结点的表达式是( )
A.p→llink
B.p→rlink
C.p→llink→llink
D.p→llink→rlink
21．一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元
素的存储地址是( )
A. 110
B. 108
C. 100
D. 120
22．关于存储相同数据元素的说法中正确的是（）
A．顺序存储比链式存储少占空间
B.顺序存储比链式存储多占空间
C.顺序存储和链式存储都要求占用整块存储空间
D.链式存储比顺序存储难于扩充空间
23．已知一个单链表中，指针q指向指针p的前趋结点，若在指针q所指结点和指针p所指结点之间插入指针s所指结点，则需执行（）
A．q→next=s；p→next=s； B.q→next=s；s→next=p；
C.q→next=s；q→next=p；
D.q→next=s；s→next=q；24．在长度为n的线性表中删除一个指针p所指结点的时间复杂度是（）A．O(n) B.O(1)
C.O(log
2
n) D.O(n2)
25．若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算时间的存储方式是（）
A.单链表
B.仅有头指针的单循环链表
C.双链表
D.仅有尾指针的单循环链表
26．从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动的元素的个数是（）
A.n-i
B.n-i+1
C.n-i-1
D.i
27．对于长度为n的顺序表执行删除操作，则其结点的移动次数（）
A.最少为0，最多为n
B.最少为1，最多为n
C.最少为0，最多为n-1
D.最少为1，最多为n-1
28．在一个单链表中，若p所指结点是q所指结点的前驱结点，则删除结点q的正确操作是（）
A. p->next=q
B. p->next=q->next
C. p=q->next
D. p->next=q->next->next
29．在一个具有n个结点的有序单链表中插入一个新结点，并使插入后仍然有序，则该操作的时间复杂性量级为（）
A．O（1） B．O（n）
C．O（nlog
2
n） D．O(n2)
30．顺序存储的线性表（a
1,a
2
,…,a
n
）,在任一结点前插入一个新结点时所需移
动结点的平均次数为（）
A．n B．n/2
C．n+1 D．(n+1)/2
31．设单链表中指针p指向结点A，若删除A后的结点存在，则需要修改指针的操作为（）。
A．p->next=p->next->next B．p=p->next
C．p=p->next->next D．p->next=p
32．线性表的链式存储实现有利于（）运算。
A．插入 B．读表元
C．查找 D．定位
33．从一个长度为n的顺序表中删除第i个元素(1≤i≤n)，需向前移动（）
个元素。
A．n-i B．n-i+1
C．n-i-1 D．i
34．在一个长度为n的顺序存储线性表中，向第i个元素(1≤i≤n+1)之前插入一个新元素时，需向后移动（）个元素。
A．n-i B．n-i+1
C．n-i-1 D．i
35．在一个单链表中，已知*q结点是*p结点的前趋结点，若在*q和*p之间插入*s结点，则需执行（）。
A．s->next=p->next; p->next=s; B．q->next=s; s->next=p;
C．p->next=s->next; s->next=p; D．p->next=s; s->next=q;
36．在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行（）。
A.HL = p; p->next = HL;
B.p->next = HL; HL = p;
C.p->next = HL; p = HL;
D.p->next = HL->next; HL->next = p;
37．在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行（）。
A.p = q->next ; p->next = q->next;
B.p = q->next ; q->next = p;
C.p = q->next ; q->next = p->next;
D.q->next = q->next->next; q->next = q;
38．线性表采用链式存储时，其地址（）。
A．必须是连续的 B．部分地址必须是连续的
C．一定是不连续的 D．连续与否均可以
39．在一个长度为n的线性表中插入第i个元素的操作中，i的取值范围是A．1≤i≤n B．0≤i≤n C．1≤i≤ n+1 D．1≤i≤n-1 40．如果要查找单链表中的第i个元素，应该从（）开始进行查找。
A．第i个结点 B．头结点 C．尾结点 D．任意一个结点41．在一个长度为n的线性表中顺序查找值为x的元素时，查找时的平均查找长度（即x同元素的平均比较次数，假定查找每个元素的概率都相等）为（）。
A.n
B.n/2
C. (n+1)/2
D. (n-1)/2
42．在一个单链表HL中，若要在指针q所指的结点的后面插入一个由指针p所指的结点，则执行（）。
A.q->next = p->next ; p->next = q;
B.p->next = q->next; q = p;
C.q->next = p->next; p->next = q;
D.p->next = q->next ; q->next = p;
43. 在一个单链表中,若q所指结点是p所指结点的前驱结点,若在q与p之间插入一个s所指的结点,则执行( )。
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;
44. 线性链表不具有的特点是（）。
A．随机访问 B．不必事先估计所需存储空间大小
C．插入与删除时不必移动元素 D．所需空间与线性表长度成正比
45. 下述哪一条是顺序存储结构的优点？（）。
A．插入运算方便 B．可方便地用于各种逻辑结构的存储表示C．存储密度大 D．删除运算方便
46. 下面关于线性表的叙述中，错误的是哪一个？（）。
A．线性表采用顺序存储，必须占用一片连续的存储单元。
B．线性表采用顺序存储，便于进行插入和删除操作。
C．线性表采用链接存储，不必占用一片连续的存储单元。
D．线性表采用链接存储，便于插入和删除操作。
47. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。
A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表
48．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。
A. 单链表
B. 仅有头指针的单循环链表
C. 双链表
D. 仅有尾指针的单循环链表
49．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省时间。
A. 带头结点的双循环链表
B.单循环链表
C. 带尾指针的单循环链表
D. 单链表
50．若线性表最常用的操作是存取第I个元素及其前驱和后继元素的值，为节省时间应采用的存储方式( )。
A.单链表
B.双向链表
C.单循环链表
D.顺序表
51．静态链表中指针表示的是( )
A.下一元素的地址
B.内存储器的地址
C.下一元素在数组中的位置
D.左链或右链指向的元素的地址
52．在n个结点的线性表的数组实现中，算法的时间复杂性是O(1)的操作是( )
A. 访问第i个结点(1≤i<=n)和求第i个结点的直接前驱(2≤i<=n)
B. 在第i个结点后插入一个新结点(1≤i<=n)
C. 删除第i个结点(1≤i<=n)
D. 以上都不对
53．(1) 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。
(2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。
(3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。
以上错误的是（）。
A．（1），（2） B．（1） C．（1），（2）,(3) D.（2）54．对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（）。A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1)
55．单链表中，增加一个头结点的目的是为了( ）。
A．使单链表至少有一个结点 B．标识表结点中首结点的位置
C．方便运算的实现 D．说明单链表是线性表的链式存储
56．对于双向循环链表,在p指针所指的结点之后插入s指针所指结点的操作应
为（）。
A．p->right=s ; s->left=p; p->right->left=s ; s->right=p->right;
B．p->right=s ; p->right->left=s ; s->left=p; s->right=p->right;
C．s->left=p; s->right=p->right; p->right=s ; p->right->left=s ; ;
D．s->left=p; s->right=p->right; p->right->left=s ; p->right=s ;
57．对于一个线性表既要求能够进行较快速的插入和删除，又要求存储结构能反
映数据之间的逻辑关系，则应该用( )。
A. 顺序存储方式
B. 链式存储方式
C. 散列存储方式
D. 以上均可以
58．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（）。
A．p->next=s;s->next=p->next; B． s->next=p->next;p->next=s;
C．p->next=s;p->next=s->next; D． p->next=s->next;p->next=s;
59．线性表的顺序存储结构是一种（）。
A. 随机存取的存储结构
B. 顺序存取的存储结构
C. 索引存取的存储结构
D. Hash存取的存储结构
60．顺序表是线性表的（）
A、链式存储结构
B、顺序存储结构
C、索引存储结构
D、散列存储结构
61．带头结点的单链表head为空的条件是（）
A、head=NULL
B、head->next=NULL
C、head->next=head
D、head!=NULL 62．链表不具有的特点是（）
A．插入、删除不需要移动元素 B．可随机访问任一元素
C．不必事先估计存储空间 D．所需空间与线性长度成正比
63．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删
除运算，则利用（）存储方式最节省时间。
A．顺序表 B．双链表
C．带头结点的双循环链表 D．单循环链表
64．下面关于线性表的叙述中，错误的是哪一个？（）
A．线性表采用顺序存储，必须占用一片连续的存储单元。
B．线性表采用顺序存储，便于进行插入和删除操作。
C．线性表采用链接存储，不必占用一片连续的存储单元。
D．线性表采用链接存储，便于插入和删除操作。
二、填空题
1．设顺序线性表中有n个数据元素，则第i个位置上插入一个数据元素需要移
动表中_______个数据元素；删除第i个位置上的数据元素需要移动表中_______
个元素。
2. 设指针变量p指向双向循环链表中的结点X，则删除结点X需要执行的语句
序列为_________________________________________________________（设结
点中的两个指针域分别为llink和rlink）。
3．设指针变量p指向单链表中结点A，则删除结点A的语句序列为：
q=p->next；p->data=q->data；p->next=___________；feee(q)；
4．在带头结点的单链表L中, 第一个元素所对应的结点的指针表达式是_____________。
5．在双向循环链表中，在结点*Ｐ之前插入结点*Ｓ的语句序列是：
S-> prior = P-> prior ; S->next=P; P->prior=S; __________________。
6．在双链表中，存储一个结点有三个域，一个是数据域，另两个是指针域，分别指向_ _和_ 。
7．下面程序段的功能是利用从尾部插入的方法建立单链表的算法，请在下划线处填上正确的内容。
typedef struct node {int data; struct node *next;} lklist;
void lklistcreate(_____________ *head )
{
for (i=1;i<=n;i++)
{
p=(lklist*)malloc(sizeof(lklist));
scanf(“%d”,&(p->data));p->next=0;
if(i==1)head=q=p;else {q->next=p;____________;}
}
}
8．设指针p指向单链表中结点A，指针s指向被插入的结点X，则在结点A的前面插入结点X时的操作序列为：
1) s->next=___________；2) p->next=s；3) t=p->data；
4) p->data=___________；5) s->data=t；
9．设指针变量p指向单链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X需要执行的语句序列：s->next=p->next; _________________;。
10．设指针变量head指向双向链表中的头结点，指针变量p指向双向链表中的第一个结点，则指针变量p和指针变量head之间的关系是p=_________和head=__________（设结点中的两个指针域分别为llink和rlink）。
11．设指针变量p指向双向链表中的结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为_________=p；s->right=p->right；__________=s； p->right->left=s；（设结点中的两个指针域分别为left和right）。
12．设指针变量p指向单链表中结点A，指针变量s指向被插入的新结点X，则进行插入操作的语句序列为__________________________（设结点的指针域为next）。
13．在一个单链表HL 中，若要向表头插入一个由指针p指向的结点，则应执行语句：。
14．在采用独立结点构成的双向链表中，设p和q 分别是具有Dnode * 类型的指针变量。若双向链表中p结点之后插入一个q结点，其操作步骤为：
；
；
；
；
15．对于一个顺序存储的线性表，在表头插入元素的时间复杂度为____________,在表尾插入元素的时间复杂度为________________。
16．在一个长度为n 的顺序表中第i 个元素（1≤i ≤n ）之前插入一个元素时，需向后移动____个元素。
17．设双链表中结点的前趋指针和后继指针的域名分别为t1和r1，指针s 指向双链表中的一个结点（该结点既非头结点，也非尾结点），则删除s 指针所指向结点的操作为“s->tl->r1=s->r1；”和“__ _______”。
18．设有指针head 指向不带表头结点的单链表，用next 表示结点的一个链域，指针p 指向与链表中结点同类型的一个新结点。现要将指针p 指向的结点插入表中，使之成为第一个结点，则所需的操作为“p →next=head ；”和“____”。
19．单链表中逻辑上相邻的两个元素在物理位置上________相邻。
20．在一个长度为n 的数组中删除第i 个元素（1≤i ≤n ）时，需要向前移动的元素的个数是_______。
21．在顺序表上读表元算法的时间复杂度为____。
22．双链表中前驱指针为prior ，后继指针为next ，在指针P 所指结点前插入指针S 所指的结点，需执行下列语句：
S →next=P;S →prior=P →prior;P →prior=S;_______;
23．设某非空双链表，其结点形式为若要删除指针q 所指向的结点，则需执行下述语句段：
q->prior->next ＝q->next; _ ____。
24．双向循环链表的优点是
25．在一个长度为n 的顺序表中删除一个元素，最少需移动 个元素，最多需移动________个元素。
26．将指向单链表中的某个结点的指针p 移动到该结点的后继结点表示为 。
27． 在线性表的单链接存储结构中，每个结点包含有两个域，一个 叫 域，另一个叫 域。
28．在下面数组a 中链接存储着一个线性表，表头指针为a[0].next ，则该线性表为 。
29．在线性表的顺序存储中，若一个元素的下标为i ，则它的前驱元素的下标为 ，后继元素的下标为 。
30．在线性表的单链接存储中，若一个元素所在结点的地址为p ，则其后继结点的地址为 ，若假定p 为一个数组a 中的下标，则其后继结点的下标为 。
31．在循环单链表中，最后一个结点的指针指向 结点。
32．在以HL 为表头指针的带表头附加结点的单链表和循环单链表中，链表为空的条件分别为 和 。
a data next
33．向一个顺序栈插入一个元素时，首先使后移一个位置，然后把待插入元素到这个位置上。
34．从一个栈中删除元素时，首先取出，然后再前移一位。35．设单链表的结点结构为(data,next)，next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点 , 若将结点y插入结点x之后，则需要执行以下语句:_______； ______;【华中理工大学 2000 一.4（2分）】
36．在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动________个元素。【北京工商大学 2001 二.4（4分）】
37．在单链表中设置头结点的作用是________。【哈尔滨工业大学 2000 二.1（1分）】
38．对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为________,在给定值为x的结点后插入一个新结点的时间复杂度为________。【哈尔滨工业大学 2001 一.1（2分）】
39．在双向循环链表中,向p所指的结点之后插入指针f所指的结点，其操作是_______、_______、_______、________。【中国矿业大学 2000 一.1（3分）】40．顺序存储结构是通过________表示元素之间的关系的;链式存储结构是通过________表示元素之间的关系的。【北京理工大学 2001 七.2 （2分）】41．在单链表L中，指针p所指结点有后继结点的条件是：________
【合肥工业大学 2001 三.3 （2分）】
三、判断题
1．（）线性表的顺序存储结构比链式存储结构更好。
2．( )线性表就是顺序存储的表。
3．（）线性表中的所有元素都有一个前驱元素和后继元素。
4．（）非空的双向循环链表中任何结点的前驱指针均不为空。
5．（）不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O(n)。
6．( )对链表进行插入和删除操作时不必移动链表中结点。
7．( )线性表只能用顺序存储结构实现。
8．( )如果某数据结构的每一个元素都最多只有一个直接前驱和一个直接后继，则该数据结构必为线性表。
9．( )采用链式结构存储线性表时，其地址可以是不连续的。
10．( )线性表中的每个元素都有一个前驱元素和后继元素。
11．( )采用顺序结构存储线性表时，其地址可以是不连续的。
12．（）如果某数据结构的每一个元素都最多只有一个直接前驱和一个直接后继，则该数据结构必为线性表。
13．（）线性表的唯一存储形式就是链表。
14．（）线性表不能采用链式存储。
15．（）在单链表中插入结点主要通过移动元素实现。
16．( )所谓静态链表就是一直不发生变化的链表。
17．( )集合与线性表的区别在于是否按关键字排序。
18．（）用头部插入结点的方法建立单链表时，插入元素的顺序和链表中的元素顺序相同。
19．（）线性表中的每个元素都有一个前驱元素和后继元素。
四、简答题
1．比较顺序表与单链表的优缺点。
2．说明以下三个概念的关系：头指针，头结点，首元素结点。
3．写出在双向链表中，在指针p所指结点前插入一个结点*S的语句序列。
4. 画出带头结点的单链表、单循环链表和双向循环链表的示意图，并归纳三者的不同之处。
5．写出下列中缀表达式的后缀表达式：
(1)A*B*C (2)(A+B)*C-D (3)A*B+C/(D-E) (4)(A+B)*D+E/(F+A*D)+C
6．线性表的顺序存储结构具有三个弱点：第一，在作插入或删除操作时，需要移动大量元素；第二，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；第三，表的容量难以扩充。试问，线性表的链式存储结构是否一定能够克服上述三个弱点？请简述之。【北京师范大学2003二.4(6分)】7. 如何通过改链的方法，把一个单向链表变成一个与原来链接方向相反的单向链表？【中国人民大学 2001 二.4 （2分）】
五、应用题
1．在下面的每个程序段中，假定线性表La的类型为List，元素类型ElemType 为int，并假定每个程序段是连续执行的，试写出每个程序段执行后所得到的线性表La。
(1) InitList(La);
int a[]={48,26,57,34,62,79};
for(i=0; i<6; i++) InsertFront(La,a[i]);
TraverseList(La);
(2) InitList(La);
for(i=0; i<6; i++) Insert(La,a[i]);
TraverseList(La);
(3) ClearList(La);
for(i=0; i<6; i++) InsertRear(La,a[i]);
Delete(La, a[5]);
Sort(La);
Insert(La,a[5]/2);
TraverseList(La);
2．写出下面函数被调用执行后，得到的以HL为表头指针的单链表中的数据元素序列。
void AA(LNode * & HL)
{
InitList(HL);
InsertRear(HL,30);
InsertRear(HL,50);
int a[5] = {15,8,9,26,12};
for (int i=0; i<5; i++ )
InsertFront(HL,a[i]);
}
}
六、程序填空题（或算法阅读题）
1．LinkList mynote(LinkList L)
{//L是不带头结点的单链表的头指针
if(L&&L->next){
q=L；L=L－>next；p=L；
S1： while(p－>next) p=p－>next；
S2： p－>next=q；q－>next=NULL；
}
return L；
}
请回答下列问题：
（1）说明语句S1的功能；
（2）说明语句组S2的功能；
（3）设链表表示的线性表为（a
1,a
2
, …,a
n
）,写出算法执行后的返回值
所表示的线性表。
2．int AA(LNode *HL , ElemType x)
{
int n=0;
LNode *p=HL;
while (p!=NULL)
{
if (p->data= =x) n++;
p=p->next;
}
return n;
}
对于结点类型为LNode的单链表，以上算法的功能为：3．void BB(List &L)
{
int i=0;
while (i { int j=i+1; while (j { if(L.list[j] = =L.list[i]) { for (int k=j+1;k L.list[k-1]=L.list[k]; L.size--; } else j++; } i++; } } 以上算法的功能为： 4. 已知一个单链表的表头指针为h，每个结点含元素值data和下一个结点的地址next。链表一共有5个结点，其元素值分别为100,200,300,400,500，经过下列语句后，输出什么结果？。（3分） for (p=h;p->data<300;p=p->next) { p->next = p->next->next; } printf(“%d”,p->data); 5. 指出下面程序段的功能是什么？ void demo1(SeqStack S) {int i，arr[64]，n=0; while(!StackEmpty(S)) arr[n++]=Pop(S); for(i=0;i Push(S，arr[i]); } 实验一线性表的基本操作 一、实验目的与基本要求 1．掌握数据结构中的一些基本概念。数据、数据项、数据元素、数据类型和数据结构，以及它们之间的关系。 2．了解数据的逻辑结构和数据的存储结构之间的区别与联系；数据的运算与数据的逻辑结构的关系。 3．掌握顺序表和链表的基本操作：插入、删除、查找以及表的合并等运算。4．掌握运用C语言上机调试线性表的基本方法。 二、实验条件 1．硬件：一台微机 2．软件：操作系统和C语言系统 三、实验方法 确定存储结构后，上机调试实现线性表的基本运算。 四、实验内容 1．建立顺序表，基本操作包括：初始化，建立一个顺序存储的链表，输出顺序表，判断是否为空，取表中第i个元素，定位函数（返回第一个与x相等的元素位置），插入，删除。 2．建立单链表，基本操作包括：初始化，建立一个链式存储的链表，输出顺序表，判断是否为空，取表中第i个元素，定位函数（返回第一个与x相等的元素位置），插入，删除。 3．假设有两个按数据元素值非递减有序排列的线性表A和B，均以顺序表作为存储结构。编写算法将A表和B表归并成一个按元素值非递增有序（允许值相同）排列的线性表C。（可以利用将B中元素插入A中，或新建C表）4．假设有两个按数据元素值非递减有序排列的线性表A和B，均以单链表作为存储结构。编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许值相同）排列的线性表C。 五、附源程序及算法程序流程图 1.源程序 （1）源程序(实验要求1和3) #include 数据结构试题 一、单选题 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 数据结构练习题1 指导老师：常璐璐 姓名：邢莉彬 学校：滨州学院 院系：信息工程学院软件技术 填空题 1. 对于一个n个结点的单链表，在表头插入元素的时间复杂度为_____O(1)_____，在表尾插入元素的时间复杂度为_____O(n)_____。 2. 删除非空线性链表中由q所指的链结点（其直接前驱结点由r指出）的动作时执行语句___r->link=q->link_______和______free(q)____。 结点结构为 typedef struct Node{ int value; node * link; }node; 3. 非空线性链表中，若要在由p所指的链结点后面插入新结点q，则应执行语句____ q->link=p->link;______和_____ p->link=q;_____。 结点结构为 typedef struct Node{ int value; node* link; }node; 4. 线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_____(n-1)/2_____。 5. 在一个长度为n的顺序表中第i个元素（1≤i≤n）之前插入一个元素时，需向后移动_____ n-i+1_____ 个元素。 6.在具有n个链结点的链表中查找一个链结点的时间复杂度为O(_______n___)。 7. 线性表中的插入、删除操作，在顺序存储方式下平均移动近一半的元素，时间复杂度为_____O（n）_____；而在链式存储方式下，插入和删除操作的时间复杂度都是____O(1)______ 。 8. 若某线性表采用顺序存储结构，每个元素占4个存储单元，首地址为100，则第10个元素的存储地址为____136______。 选择题 1. 对于一个带头结点的单链表，头指针为head，判定该表为空的条件是________B__。 A. head==NULL B. head->next==NULL C. head->next==head D. head!=NULL 2. 将长度为m的线性链表链接在长度为n的线性链表之后的过程的时间复杂度若采用大O形式表示，则应该是______B____。 A．O(m) B．O(n) C．O(m+n) D．O(m-n) 3.在包含1000个数据元素的线性表中，实现如下4个操作所需要的执行时间最长的是______A____ 。 实验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; 习题二 一、选择题 1．在一个长度为n的顺序表中删除第i个元素（0＜i 序号 数据结构实验报告 班级姓名同组者/ 成绩 日期 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 北京邮电大学电信工程学院 数据结构实验报告 实验名称：实验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 填空题（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 分，共20分） 1. 1.对一个算法的评价,不包括如下（B ）方面的内容。 Ａ.健壮性和可读性Ｂ．并行性C。正确性Ｄ．时空复杂度 2.2．在带有头结点的单链表ＨL中,要向表头插入一个由指针p指向 的结点，则执行（A ). Ａ. p－〉ｎｅxt=HL->nexｔ; ＨL-〉nexｔ=p; B． p-〉next=HL；ＨL=p； Ｃ。p-＞ｎext=HＬ； p＝HL；Ｄ. HL=p; ｐ－〉next＝ＨL； 3.3．对线性表,在下列哪种情况下应当采用链表表示？( B ） Ａ.经常需要随机地存取元素 B。经常需要进行插入和删除操作 C。表中元素需要占据一片连续的存储空间D．表中元素的个数不变 4. 4.一个栈的输入序列为１ 2 3，则下列序列中不可能是栈的输出序 列的是( C ） A. 2 3 1 ??? B. ３ 2 1 C。 3 １ 2 ??? D. 1 ２３ 5. 5.AＯV网是一种（D ）。 A．有向图Ｂ．无向图Ｃ．无向无环图D．有向无环图 6.6。采用开放定址法处理散列表的冲突时,其平均查找长度（Ｂ)。 A．低于链接法处理冲突B．高于链接法处理冲突Ｃ.与链接法处理冲突相同 D。高于二分查找 7.7。若需要利用形参直接访问实参时，应将形参变量说明为（D ) 参数. Ａ。值Ｂ。函数 C.指针 D。引用 8.８．在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结 点都具有相同的（ A )。 A。行号 B.列号 C．元素值 D．非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为( D )。 A。O（loｇ 2n) B．Ｏ（nlog 2 n） C。０（n) D.0 （n2） 10.10.从二叉搜索树中查找一个元素时,其时间复杂度大致为( C ). Ａ．O(n） B. Ｏ(1） C。 O（log 2 n） D. O(n2)二、运算题（每题 6 分，共２４分） 《数据结构》实验报告 专业： 学号： 姓名： 实验二线性表 【实验目的】 1.熟悉VC环境，学习如何使用C语言实现线性表的两种存储结构。 2.通过编程、上机调试，进一步理解线性表的基本概念，东运用C语言实现线性表基本操作。 3.熟练掌握线性表的综合应用问题。 【实验内容】 1、一个线性表有n个元素（n-MAXSIZE.MAXSIZE指线性表的最大长度），且递增有。现有一元素x要插入到线性表的适当位置上，并保持线性表原有的顺序不变。设计程序实现。要求：采用顺序存储表示实现；采用链式存储表示方法实现：比较两种方法的优劣。 2.从单链表中删除指定的元素x，若x在单链表中不存在，给出提示信息。 要求： ①指定的值x由键盘输入； ②程序能处理空链表的情况。 3.设有头结点的单链表，编程对表中的任意值只保留一个结点，删除其余值相同的结点。 要求： ①该算法用函数（非主函数)实现； ②在主函数中调用创建链表的函数创建一个单链表，并调用该函数，验证算法的正确性。LinkedList Exchange（LinkedList HEAD,p) //HEAD是单链表头结点的指针，p是链表中的一个结点。本算法将p所指结点与其后 继结点交换。 （q=head->next；//q是工作指针，指向链表中当前待处理结点。 pre=head；//pre是前驱结点指针，指向q的前驱。 while（q'=null &&q1=p)(pre=q；q=q->next；]/未到p结点，后移指针。 if（p->next==null)printf(“p无后继结点\n”）；/p是链表中最后一个结点，无后继。 else/处理p和后继结点交换 （q=p->next；//暂存p的后继。 pre->next=q://p前驱结点的后继指向p的后继。 p->next=q->next；//p的后继指向原p后继的后继。 q->next=p：//原p后继的后继指针指向p。} }//算法结束。 4.已知非空单链表第一个结点由head指出，请写一算法，交换p所指结点与其下一个结点在链表中的位置。 要求： 第一章概论 一、选择题 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 实验一线性表及其应用 一、实验目的 1.熟悉C语言的上机环境，进一步掌握C语言的结构特点。 2.掌握线性表的顺序存储结构的定义及C语言实现。 3.掌握线性表的链式存储结构——单链表的定义及C语言实现。 4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。 5.掌握线性表在链式存储结构——单链表中的各种基本操作。 二、实验内容 1.顺序线性表的建立、插入及删除。 2.链式线性表的建立、插入及删除。 三、实验步骤 1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。 2.利用前面的实验先建立一个顺序表L={21，23，14，5，56，17，31}，然后在第i个位置插入元素68。 3.建立一个带头结点的单链表，结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。 四、实现提示 1.由于C语言的数组类型也有随机存取的特点，一维数组的机内表示就是顺序结构。因此，可用C语言的一维数组实现线性表的顺序存储。 在此，我们利用C语言的结构体类型定义顺序表： #define MAXSIZE 1024 typedef int elemtype; /* 线性表中存放整型元素*/ typedef struct { elemtype vec[MAXSIZE]; int len; /* 顺序表的长度*/ }sequenlist; 将此结构定义放在一个头文件sqlist.h里，可避免在后面的参考程序中代码重复书写，另外在该头文件里给出顺序表的建立及常量的定义。 2. 注意如何取到第i个元素，在插入过程中注意溢出情况以及数组的下标与位序（顺序表中元素的次序）的区别。 3.单链表的结点结构除数据域外，还含有一个指针域。用C语言描述结点结构如下： typedef int elemtype; typedef struct node 第 1 章绪论 课后习题讲解 1. 填空 ⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。 【解答】集合，线性结构，树结构，图结构 ⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺在一般情况下，一个算法的时间复杂度是（）的函数。 【解答】问题规模 ⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。 《数据结构》 第二章线性表习题 一、单项选择题 1. 线性表是________。 A．一个有限序列，可以为空B．一个有限序列，不可以为空 C．一个无限序列，可以为空D．一个无限序列，不可以为空 2. 在一个长度为n的顺序表中删除第i个元素(0<=i<=n)时，需向前移动个元素。 A．n-i B．n-i+l C．n-i-1 D．i 3. 线性表采用链式存储时，其地址________。 A．必须是连续的B．一定是不连续的 C．部分地址必须是连续的D．连续与否均可以 4. 从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较________个元素结点。 A．n/2 B．n C．（n+1）/2 D．（n-1）/2 5. 在双向循环链表中，在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 第一章绪论 一、选择题 1.数据结构是一门研究非数值计算的程序设计问题中计算机的1以及它们之间的2和运算等的学科。1 A.数据元素 B.计算方法 C.逻辑存储 D.数据映像 2 A.结构 B.关系 C.运算 D.算法 2.数据结构被形式地定义为(K, R)，其中K是1的有限集，R是K上的2有限集。 1 A.算法 B.数据元素 C.数据操作 D.逻辑结构 2 A.操作 B.映像 C.存储 D.关系 3.在数据结构中，从逻辑上可以把数据结构分成。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 4.线性结构的顺序存储结构是一种1的存储结构，线性表的链式存储结构是一种2的存储结构。A.随机存取 B.顺序存取 C.索引存取 D.散列存取 5.算法分析的目的是1，算法分析的两个主要方面其一是指2，其二是指正确性和简单性。1 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 2 A.空间复杂度和时间复杂度 B.研究算法中的输入和输出的关系 C.可读性和文档性 D.数据复杂性和程序复杂性k 6.计算机算法指的是1，它必须具备输入、输出和2等5个特性。 1 A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 2 A.可执行性、可移植性和可扩充性 B.可行性、确定性和有穷性 C.确定性、有穷性和稳定性 D.易读性、稳定性和安全性 7.线性表的逻辑顺序与存储顺序总是一致的，这种说法。A.正确 B.不正确 8线性表若采用链式存储结构时，要求内存中可用存储单元的地址。 A.必须连续的 B.部分地址必须连续的 C.一定是不续的D连续不连续都可以 9.以下的叙述中，正确的是。A.线性表的存储结构优于链式存储结构 B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出10.每种数据结构都具备三个基本运算：插入、删除和查找，这种说法。A.正确B.不正确 二、填空题1.数据逻辑结构包括三种类型、和，树形结构和图形结构合称为。2.在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。3.算法的五个重要特性是、、、、。 4.下面程序段的时间复杂度是。 for( i = 0; i < n; i++) for( j = 0; j < m; j++) A[i][j] = 0; 5.下面程序段的时间复杂度是。 i = s = 0; while ( s < n) { i ++; /* i = i +1*/ s += i; /* s = s + i*/ } 6.下面程序段的时间复杂度是。 s = 0; for( i = 0; i < n; i++) for( j = 0; j < n; j++) s += B[i][j]; sum = s; 7.下面程序段的时间复杂度是。 i = 1; while ( i <= n ) i = i * 3; 线性表 一、选择题 1.线性表是（ A ） A．一个有限序列，可以为空B．一个有限序列，不可以为空 C．一个无限序列，可以为空D．一个无限序列，不可以为空 2.一维数组与线性表的特征是（ C ）。 A．前者长度固定，后者长度可变B．两者长度均固定 C．后者长度固定，前者长度可变D．两者长度均可变 3.用单链表方式存储的线性表，存储每个结点需要两个域，一个数据域，另一个是( B ). A．当前结点所在地址域B．指针域 C．空指针域D．空闲域 4.用链表表示线性表的优点是（ B ）。 A．便于随机存取 B．便于进行插入和删除操作 C．占用的存储空间较顺序表少 D．元素的物理顺序与逻辑顺序相同 5.在具有 n 个结点的单链表中，实现__A _的操作，其算法的时间复杂度都是O（n）。 A．遍历链表和求链表的第i个结点 B．在地址为P的结点之后插入一个结点 C．删除开始结点 D．删除地址为P的结点的后继结点 6.下面关于线性表的叙述中，错误的是（ B ）。 A．线性表采用顺序存储必须占用一片连续的存储单元 B．线性表采用顺序存储便于进行插入和删除操作 C．线性表采用链式存储不必占用一片连续的存储单元 D．线性表采用链式存储便于进行插入和删除操作 7.已知单链表的每个结点包括一个指针域next，它指向该结点的后继结点。现要将指针 q 指向的新结点插入到指针 p 指 向的结点之后，下面的操作序列中正确的是（ C ）。 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 ; 数据结构实验报告 实验名称：实验1——线性表 学生姓名： 班级： 班内序号： 学号： 日期： 1．实验要求 1、实验目的：熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法 学习指针、模板类、异常处理的使用 掌握线性表的操作的实现方法 学习使用线性表解决实际问题的能力 2、实验内容： 题目1： 线性表的基本功能： 1、构造：使用头插法、尾插法两种方法 2、插入：要求建立的链表按照关键字从小到大有序 3、删除 4、查找 5、获取链表长度 6、销毁 7、其他：可自行定义 编写测试main()函数测试线性表的正确性。 2. 程序分析 存储结构 带头结点的单链表 关键算法分析 1.头插法 a、伪代码实现：在堆中建立新结点 将x写入到新结点的数据域 修改新结点的指针域 修改头结点的指针域,将新结点加入链表中 b、代码实现： Linklist::Linklist(int a[],int n) 堆中建立新结点 b.将a[i]写入到新结点的数据域 c.将新结点加入到链表中 d.修改修改尾指针 b、代码实现: Linklist::Linklist(int a[],int n,int m)取链表长度函数 a、伪代码实现：判断该链表是否为空链表，如果是，输出长度0 如果不是空链表，新建立一个temp指针，初始化整形数n为0 将temp指针指向头结点 判断temp指针指向的结点的next域是否为空，如果不是，n加一，否 则return n 使temp指针逐个后移，重复d操作，直到temp指针指向的结点的next 域为0，返回n b 、代码实现 void Linklist::Getlength()Linklist(); cout< 第一章线性表 2.1 描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。 解：头指针是指向链表中第一个结点的指针。首元结点是指链表中存储第一个数据元素的结点。头结点是在首元结点之前附设的一个结点，该结点不存储数据元素，其指针域指向首元结点，其作用主要是为了方便对链表的操作。它可以对空表、非空表以及首元结点的操作进行统一处理。 2.2 填空题。 解：(1) 在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与元素在表中的位置有关。 (2) 顺序表中逻辑上相邻的元素的物理位置必定紧邻。单链表中逻辑上相邻的元素的物理位置不一定紧邻。 (3) 在单链表中，除了首元结点外，任一结点的存储位置由其前驱结点的链域的值指示。 (4) 在单链表中设置头结点的作用是插入和删除首元结点时不用进行特殊处理。 2.3 在什么情况下用顺序表比链表好？ 解：当线性表的数据元素在物理位置上是连续存储的时候，用顺序表比用链表好，其特点是可以进行随机存取。 2.4 对以下单链表分别执行下列各程序段，并画出结果示意图。 解： 2.5 画出执行下列各行语句后各指针及链表的示意图。 L=(LinkList)malloc(sizeof(LNode)); P=L; for(i=1;i<=4;i++){ P->next=(LinkList)malloc(sizeof(LNode)); P=P->next; P->data=i*2-1; } P->next=NULL; for(i=4;i>=1;i--) Ins_LinkList(L,i+1,i*2); for(i=1;i<=3;i++) Del_LinkList(L,i); 解： 2.6 已知L是无表头结点的单链表，且P结点既不是C语言数据结构线性表的基本操作实验报告
数据结构试题及答案
数据结构线性表习题1
数据结构_实验1_线性表的基本操作
数据结构线性表2答案
数据结构线性表实验报告
数据结构实验一题目一线性表实验报告
数据结构课后习题及答案
数据结构试题及答案10套
数据结构线性表实验报告
数据结构试题答案
《数据结构》实验一 线性表及其应用
数据结构习题与答案
数据结构 第二章 线性表习题
数据结构作业及答案
数据结构-线性表-习题
数据结构实验一题目一线性表实验报告
数据结构线性表答案
- 数据结构课后习题答案第二章 线性表
- 数据结构第2章 线性表 教案
- 数据结构线性表
- 第二章线性表
- 《数据结构及其应用》笔记含答案 第二章_线性表
- 数据结构第二章课后答案
- 数据结构第2章线性表习题及答案
- 数据结构练习题 第二章 线性表 习题及答案
- 数据结构第二章线性表
- 数据结构习题及答案与实验指导(线性表)2
- 《数据结构》第二章线性表习题与解答
- (完整版)数据结构第二章线性表1答案
- 数据结构第二章课后习题题解
- 《数据结构》 第二章 线性表习题
- 算法与数据结构第2章 线性表
- 数据结构第二章线性表1答案
- 数据结构第二章线性表习题
- 数据结构(C语言)第2章线性表答案
- 数据结构第2章线性表
- 数据结构第二章试题