发布时间 : 星期五 文章山东专升本计算机专业数据结构练习题 - 图文更新完毕开始阅读f123d207de80d4d8d15a4f7d
济南铁道职业技术学院 专升本辅导教材 数据结构
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
济南铁道职业技术学院 专升本辅导教材 数据结构
}
6．下列函数的功能是，对以带头结点的单链表作为存储结构的两个递增有序表（表中不存在值相同的数据元素）进行如下操作：将所有在Lb表中存在而La表中不存在的结点插入到La中，其中La和Lb分别为两个链表的头指针。请在空缺处填入合适内容，使其成为一个完整的算法。 void union (LinkList La, LinkList Lb) {
{ } if (pb) }
四、程序设计
1、设某头指针为head的单链表的结点结构说明如下：（6分） typedef struct node1 {
int data; struct node1*next
(3) ; if (pa -> data
{q = pb; pb = pb -> next; free (q); }
pre = pb; pb = pb -> next; (2) ;
//本算法的功能是将所有Lb表中存在而La表中不存在的结点插入到La表中 LinkList pre = La, q; LinkList pa = La -> next; LinkList pb = Lb -> next; free (Lb); while (pa && pd)
}node;
试设计一个算法void change (node*head),将该单链表中的元素按原单链表相反的次序重新存放，即第一个结点变成最后一个结点，第二个结点变为倒数第二个结点，如此等等。 2．设某带头结头的单链表的结点结构说明如下： typedef struct nodel {
int data;
struct nodel*next;
第 16 页 共 63 页