济南铁道职业技术学院 专升本辅导教材 数据结构
语句)
A．q->llink=p B．q->rlink->llink=p
C．p->fiink->llink=p D．p->llink->llink=p
(22)在非空双向循环链表中由q所指的那个链结点前面插入一个p所指的链结点的动作对 应的语句依次为：p->rlink=Q；p->llink=q->llink；q->[1ink=p；——。(空白 处为一条赋值语句)
A．q->rlink=p； B．q->llink->rlink=p；
C．p->rlink->rlink=p； D．p->llink->rlink=p；
(23)在包含有1000个数据元素的线性表中实现如下四个操作，所需要的执行时间最长的是 一O
A．线性表采用顺序存储结构，在第10个元素后面插入一个新的元素 B．线性表采用链式存储结构，在第10个元素后面插入一个新的元素 C．线性表采用顺序存储结构，删除第990个元素 D．线性表采用链式存储结构，删除p所指的链结点 2．3填空题。
(1)顺序表是一种——线性表。
(2)在程序设计中，描述线性表的顺序存储结构一般都用——。
(3)在——情况下，删除线性表中一个数据元素平均要移动表中近一半的元素。 (4)在顺序表的——插入一个新的数据元素不必移动任何元素。
(5)若长度为n的线性表采用顺序存储结构，在其第i个位置(1≤i≤n+1)插入一个新的数据 元素，当不溢出时，首先——，然后——，最后——。
(6)若长度为n的线性表采用顺序存储结构，删除其第i个元素(1≤i≤n)，首先——，然 后——。
(7)若长度为n的线性表采用顺序存储结构，插入或删除一个元素的时间复杂度为——。
(8)若某线性表采用顺序存储结构，每个元素占4个存储单元，首地址为100，则第12个元素 的存储地址为——。
(9)线性表的链式存储结构主要包括——、——和——三种形式。
(10)线性表的顺序存储结构是通过——来直接反映数据元素之间的逻辑关系，而链式存 储结构则是通过——间接反映数据元素之间的逻辑关系。
(11)根据——的多少，可以将链表分为线性链表(单链表)与双向链表。
(12)若对线性表进行的操作主要不是插入和删除，则该线性表宜采用——存储结构，若 频繁地对线性表进行插入和删除操作，则该线性表宜采用——存储结构。 (13)删除由list所指的线性链表的第一个链结点是执行操作——。
(14)删除非空线性链表中由q所指的链结点(其直接前驱结点由r指出)的动作是执行语句 ——和——。
(15)在线性链表中由q所指的链结点后面插入一个地址为p的新结点的过程是依次执行操 作——和——。
(16)若p为指向循环链表中某链结点的指针变量，判断循环链表是否只有一个链结点的标志 是——。
(17)删除非空双向链表中由q所指的链结点的过程是执行语句——和——。 (18)在具有n个链结点的链表的已知位置插入一个链结点的时间复杂度为——。 (19)在具有n个链结点的链表中查找一个链结点的时间复杂度为——。 (20)一元多项式f(x)二9x1’—4x8+3x—5的线性链表表示为——。
2．4 已知长度为n的线性表A采用顺序存储结构，请写一算法，找出该线性表中值最小的数据元素。
第 11 页 共 63 页
济南铁道职业技术学院 专升本辅导教材 数据结构
2．5 已知长度为n的线性表A采用顺序存储结构，请写出逆转该线性表的算法，即由A二(al，a2，?，An-l，An)产生A'：(An-1，An，?，A1，A2)，要求在逆转过程中用最少的附加空间(即用尽可能少的辅助变量)。
2．6 已知线性表A的长度为n，并且采用顺序存储结构，请写一算法，删除该线性表中所有值为d的数据元素，并讨论算法的时间复杂度。
2．7 已知长度为n的线性表A采用顺序存储结构，并且每个数据元素均为一个无符号整数，请写一算法，删除线性表中的所有奇数。
2．8 已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为O(n)的算法，该算法删除线性表中原来序号为奇数的那些数据元素。 2．9 已知长度为n的线性表A采用顺序存储结构，写一算法，删除表中重复出现的所有数据元素 要求：剩余元素的相对位置保持不变。
2．10 已知长度为n的线性表A采用顺序存储结构，并且元素按值的大小非递减排列，请写一算法，在线性表中插入一个新的数据元素让em，要求插入以后线性表中元素仍然保持按值的大小非递减排列。 2．11 已知长度为n的线性表A采用顺序存储结构，写一算法，删除所有值大于x且小于y的数据元素。
2．12 请写一算法，通过键盘输入一系列数据元素，建立一个长度为n、且不包含重复元素的线性表A。这里，设线性表A采用的存储结构为顺序存储结构，并且假设空间足够。
2。13 已知线性表A与线性表B的长度分别为n与m，并且都采用顺序存储结构，写一算法，在线性表A的第i个位置插入线性表B。约定：不考虑存储空间溢出问题。
2．14 已知非空线性链表的第一个链结点的存储地址为list，写出删除该链表第i个链结点的算法。 2．15 已知非空线性链表第一个链结点的存储地址为1ist，试写出删除链表中从第i个链结点开始的(包括第i个链结点本身)连续k个链结点的算法。
2．16 已知线性链表第一个链结点的存储地址为1ist，写一算法，把该链表中数据域值为d的所有链结点的数据域值修改为p。
2．17 已知线性链表第一个链结点指针为list，写一算法，删除链表中数据域值最大的那个链结点。 2．18 已知线性链表第一个链结点指针为list，写一算法》，j断该链表是否是有序链表(即链结点是否按照数据域大小链接)，若是，算法返回1，否则返回—1。
2．19 已知线性链表第一个链结点指针为1ist，写一算法，交换p所指链结点与其下一个链结点的位置(设p指向的不是链表最后那个链结点)。
2．20 已知非空线性链表第一个链结点由list指出，请写一算法，将链表中数据域值最小的链结点移到链表最前面。
2．21 已知非空线性链表第一个结点的指针为list，试编写一算法按递减次序打印各链结点数据域的内容(提示：在链表中打出最大值结点，打印之后将其删除。反复执行，直到链表为空时为止)。
2．22 已知一个不带头结点也无头指针变量，并且长度大于1的循环链表，试写一算法，删除p所指链结点的直接前驱结点。
2．23 已知带有头结点的循环链表中头结点的指针为list，试写出删除并释放数据域内容为x的所有结点的算法。
2．24 已知线性链表第一个链结点的指针为list，试写一算法，删除数据域值相同的多余结点，即： 若链表中有多个结点具有相同的数据域值，只保留其中一个结点，其余结点均从链表中的最后删去，使得到的链表中所有结点的数据域值都不相同。
2．25 设线性表X=(x1，x2，?，Xn)与Y=(yl，y2，?，ym)都采用链式存储结构(两个链表第一个结点的指针不妨用X与Y分9U表示)。试写一个算法归并这两个线性链表为一个线性链表，使 ((x1，Y1，x2，y2，?，xm,Ym，Xm+1，?，Xn) 当m≤n时 ((x1，Y1，x2，y2，?，xn，yn，yn+1，?，ym) 当m>n时
第 12 页 共 63 页
济南铁道职业技术学院 专升本辅导教材 数据结构
2．27 试写出将一个线性链表(第一个结点的存储地址为list)分解为两个循环链表，并将两个循环链表的长度存放在各自的头结点的数据域中的算法。
分解规则：若线性链表中某一链结点属于第一个循环链表，则下一个链结点就属于第二
个循环链表；反之，若线性链表中某一个链结点属于第二个循环链表，则下一个链结点就属于第一个循环链表。 2．28 设A与B分别为两个带有头结点的有序循环链表(所谓有序是指链结点按数据域值大小链接，这里，不妨按数据域值从小到大链接)，lista和listb分别为两个链表的头结点指针。请写出将这两个链表合并为一个带头结点的有序循环链表的算法。
2．29 已知循环链表头结点指针list，请编写一个能逆转链表方向的算法。
2．30 写一算法，先从键盘输人n个整型数，建立一个带有头结点的双向循环链表，然后按照与输入相反的次序依次输出这n个整型数。
2．31 在非空双向循环链表中由q所指的结点后面插入一个数据信息为item的新结点的算法如下： voidINSERTD(DLinkListq，datatypeitem) {
DLinkList p；
p：(DLinkList)malloc(sizeof(DNode))； ／*申请一个新的链结点*／ p->data=item； p->llink=q；
p->rlink=q->rlink； q->rlink=p；
请在算法的方框中填上必要的动作(一条语句)。
2．32 有人说线性表的顺序存储结构比链式存储结构的存储空间开销要小，也有人说线性表的链式存储结构比顺序存储结构的存储空间开销要小，你是如何看待这两种说法的?请说明你的看法。
第二章 历年试题
1．在线性表的下列存储结构中，读取元素花费时间最少的是（ ）
A．单链表 B．双链表 C．循环链表 D．顺序表 2．顺序存储的线性表（a1,a2,?,an）,在任一结点前插入一个新结点时所需移动结点的平均次数为（ ）
A．n B．n/2 C．n+1 D．(n+1)/2
3.在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为( ) A.n-i+1 B.n- i C.i D.i-1
4．在顺序存储的线性表（a1,a2?，an）中的第i (1≤i≤n)个元素之前插入一个元素，则需向后移动_________个元素。 一、选择题
1．在线性表的下列存储结构中，读取元素花费时间最少的是（ ）
A．单链表 B．双链表 C．循环链表 D．顺序表
2．顺序存储的线性表（a1,a2,?,an）,在任一结点前插入一个新结点时所需移动结点的平均次数为（ ）
A．n B．n/2 C．n+1 D．(n+1)/2
3.在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为( ) A.n-i+1 B.n- i C.i D.i-1
4．在顺序存储的线性表（a1,a2?，an）中的第i (1≤i≤n)个元素之前插入一个元素，则需向后移动
第 13 页 共 63 页
济南铁道职业技术学院 专升本辅导教材 数据结构
_________个元素。
5．在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用（ ）
A．数据元素的相邻地址表示 C．指向后继元素的指针表示
B．数据元素在表中的序号表示 D．数据元素的值表示
6．设p指向单链表中的一个结点，s指向待插入的结点，则下述程序段的功能是（ ） s -> next = p -> next; p -> next = s;
t = p -> data; p -> data = s -> data; s ->data = t;
A．结点*p与结点*s的数据域互换 B．在p所指结点的元素之前插入元素 C．在p所指结点的元素之后插入元素 D．在结点*p之前插入结点*s
7．在线性表的下列存储结构中，读取元素花费时间最少的是（ ）
A．单链表 C．循环链表
B．双链表
D．顺序表
8．将一个头指针为p的单链表中的元素按与原单链表相反的次序存放，则下列算法段中的空白处应为:
q=NULL;
while (p!=NULL) {
（ ）
} p=q;
A. r =q; q=p; p=p -> next; q -> next=r; B．q=p; r=q; p=p -> next; q -> next=r; C．r=q; p=p -> next; q=p; q -> next=r;
D．q=p; p=p -> next; r=q; q -> next=r;
9.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( ) A.顺序表 B.用头指针表示的单循环链表 C.用尾指针表示的单循环链表 D.单链表 10.设单链表中结点的结构为
typedef struct node { //链表结点定义 ElemType data; //数据
struct node * Link; //结点后继指针 } ListNode;
(1) 已知指针p所指结点不是尾结点，若在*p之后插入结点*s，则应执行下列哪一个操作？ A. s->link = p; p->link = s;
B. s->link = p->link; p->link = s; C. s->link = p->link; p = s; D. p->link = s; s->link = p;
(2) 非空的循环单链表first的尾结点（由p所指向）满足： A. p->link == NULL; B. p == NULL;
C. p->link == first; D. p == first;
第 14 页 共 63 页
济南铁道职业技术学院 专升本辅导教材 数据结构
二、判断题。
(1) 线性表的逻辑顺序与物理顺序总是一致的。 (2) 线性表的顺序存储表示优于链式存储表示。
(3) 线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。 (4) 二维数组是其数组元素为线性表的线性表。
(5) 每种数据结构都应具备三种基本运算：插入、删除和搜索。 三、填空题。
1．已知指针p指向单链表中某个结点，则语句p -> next =p -> next -> next的作用是________。 2．若链串结点中的指针占4个字节，每个字符占1个字节，则结点大小为2的链串的存储密度为________。
3．设某非空双链表，其结点形式为若要删除指针prior data next 所指向的结点，则需执行下述语句段：
q->prior->next＝q->next; __ _____________。
4．在如图所示的链表中，若在指针p所指的结点之后插入数据域值相继为a和b的两个结点，则可用下列两个语句实现该操作，它们依次是________和________。
5.函数中，h是带头结点的双向循环链表的头指针。
(1) 说明程序的功能；
(2) )当链表中结点数分别为1和6(不包括头结点)时，请写出程序中while循环体的执行次数。
int f(DListNode *h) {
DListNode *p,*q; int j=1; p=h->next; q=h->prior;
while(p!=q && p->prior!=q) if(p->data==q->data) {
p=p->next; q=q->prior; }
else j=0; return j;
第 15 页 共 63 页
q