数据结构练习题(1-2)章

精品

数据结构作业（一）

一、填空题

班级 姓名 学号

1. 数据结构按逻辑结构可分为两大类，他们分别是 和 ，其中___________分为____________、___________和___________三种。

2. 数据的存储结构被分为___________、____________、___________和___________四种。常用的两种存储方法为 和 。

3. 数据结构研究内容包括数据的 、数据的 和数据的 这三方面的内容。

4. 数据元素是数据的_____________单位。 是数据不可分割的最小单位。 5. 一个算法的效率可分为 效率和 效率。

6.若一个算法中的语句频度之和为T(n)=3720n+4nlogn，则算法的时间复杂度为 。

7. 按顺序存储方式存储的线性表称为 ，按链式存储方法存储的线性表称为 ；若经常要对线性表进行插入和删除运算，则最好采用 存储结构，若经常要对线性表进行查找运算，则最好采用 存储结构。

8. 在长度为n的顺序存储的线性表中，删除第i（1<=i<=n）个元素时，需向前移动 个

元素；在表的第i（1<=i<=n+1）号位置上插入新结点，需向后移动________个元素。

9. 头指针为H的带头结点的单链表和循环单链表，则空表的判定条件分别是___ __ ___ 和 ；头指针为H的不带头结点的单链表和循环单链表，则空表的判定条件分别是_____ ___ 和 ；在头指针为L的循环链表中，结点的指针为P，P所指的结点为尾结点的条件是 。

10. 链表适合 存取，而顺序表更适合 存取。

二、选择题

1． 已知n为问题规模，则下面程序段的时间复杂度为 。

for (i=0;i<=n-1;i++) for (j=i+1;j<=n-1;j++)

s++;

A. O(1) B. O(n) C. O(n2) D. O(log2n) 2． 下列时间复杂度最好的是 ；最差的是 。

A. O(2n) B. O(log2n) C. O(n) D. O(n2) 3． 一个存储结点存放一个 。

A. 数据项 B. 数据元素 C. 数据结构 D. 数据类型

4． 线性表若采用顺序存储结构时，要求内存中可用存储单元的地址 ；若采用链式存储结构

时，要求内存中可用存储单元的地址 。

A. 必须连续 B. 部分地址必须连续 C. 一定是不连续的 D. 连续或不连续都可以 5． 线性表的长度是 。

A. 顺序存储方式下数组占用的存储空间的大小 B. 表中的数据元素的个数

C. 链式存储方式下所有结点占用的存储空间的大小 D. 所能存储的最大结点的个数

精品

6． 链表中设头结点的目的是为了 。

A. 标识单链表 B. 方便运算的实现 C. 使链表中至少有一个结点 D. 标识起始结点的位置

7． 设H是带表头结点循环单向链表的表头指针。当这种链表成为空链表时， 。

A. 表头结点指针域的值为空 B. H的值为空

C. 表头结点指针域的值与H的值相等 D. 表头结点指针域的值与H的地址相等 8． 在程序中，为了设置一个空的顺序表，必须 。

A. 给各数组元素赋空值 B. 给各顺序表元素赋空值 C. 给表示顺序表长度的变量赋零值 D. 给数组变量名赋初始值

9． 若某线性表最常用的操作是取第i个元素和查找第i个元素的直接前躯，则采用 存储方式最节省时间。

A. 单链表 B. 双链表 C. 循环单链表 D. 顺序表 10． 若某链表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则采用 存储方式最节省运算时间。

A. 单链表 B. 仅有头指针的单循环链表 C. 双链表 D. 仅有尾指针的单循环链表

11． 在一个表头指针为L的单链表中，若要在指针q所指结点个后面插入一个由指针p所指向的结点，

则执行 操作。

A. q->next=p->next;p=q; B. q->next=p->next;p->next=q;

C. p->next=q->next;q=p; D. p->next=q->next;q->next=p;

12． 在一个表头指针为L的单链表中，若要删除由指针q所指向结点的后继结点（若存在的话），则

至少执行 操作。

A. p=q->next;p->next=q->next; B. p=q->next;q->next=p->next;

C. p=q->next;q->next=p; D. q->next=q->next->next;q->next=q;

13． 在一个带头结点的循环双向链表中，若要在指针p所指向的结点之前插入一个q指针所指向的结

点，则需要对p->prior->next赋值为 。

A. q B. p C. p->next D. p->prior

14． 在一个带头结点的循环双向链表中，若要删除指针p所指向的结点，则执行 操作。

A. p->prior->next=p->next;p->next->prior=p->prior; B. p->next->prior=p;p->next=p->next->next; C. p->prior->next=p;p->next=p->next->prior; D. p=p->next;p->prior->next=p->prior; 15． 已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址为Da1 ,则第i

个结点的地址为 。

A. Da1 +（i-1）*m B. Da1 +i*m C. Da1 -i*m D. Da1 +（i+1）*m

三、阅读程序

1、已知head为不带表头结点的单链表的头指针，链表结构如图所示： typedef struct node{ int n; head struct node *next; 1 6 4 5 ^ }Lnode, *LinkList;

精品

算法一：

LinkList ex1(LinkList head) { LinkList u, v, r; if(!head) return head;

u=NULL; v=head; r=v->next; while(v)

{ v->next=u; u=v; v=r; if(r!=NULL) r=r->next; }

return u; }

问，如执行head=ex1(head); 之后，画出head所示的链表结构示意图。

算法二：

LinkList ex2(LinkList head) { LinkList p, q, r;

q=(LinkList)malloc(sizeof(Lnode)); q->next=head; head=q; p=head->next; while(p)

{ if(p->n %3 = = 1)

{ q->next=p->next; r=p; p=p->next; free(r); continue; } q=p; p=p->next;

}

r=head; head=head->next; free(r); return head; }

问，如执行head=ex2(head); 之后，画出head所示的链表结构示意图。

2、设整数3、2、-5、7、-9、4依次存储在循环单链表L中，如图所示：试对L执行下面算法，画出执行算法后L的结构示意图。 L 3 2 - 5 7 -9 4

typedef struct node{ int data;

struct node *next; 结构示意图： }LNode, *LinkList; void ex3(LinkList L) { LinkList p=L;

while (p->next!=L) { q=p->next;

if(p->data>q->data)

{ t=p->data; p->data=q->data; q->data=t; } p=q; } }

精品

四、算法设计题

1、已知一个顺序表L，设计一个将表中元素进行倒置的算法函数void reverse(SeqList *L)，即把原表{a1,a2,...,an}倒置后变成{an,an-1,...,a1}。直接在原表上倒置。 顺序表数据类型定义为： typedef struct{

datatype data[MAX]; int last; /*顺序表长度*/ }Seqlist;

2、已知一个带头结点的单链表头指针为head，数据域的值为整数，数据类型定义如下： typedef struct node{ int data;

struct node *next; }Lnode, *LinkList;

设计一个函数void delete(LinkList head)，将表中所有奇数值的结点删除。