数据结构习题集和答案(2007-6-11) 下载本文

第1章 绪论

1、填空题

1.常见的数据结构有_线性__结构,__树形___结构,__图形__结构等三种。 2.常见的存储结构有__顺序存储_______结构,__链式存储____结构等两种。

3.数据的基本单位是_数据元素___,它在计算机中是作为一个整体来处理的。

4.数据结构中的结构是指数据间的逻辑关系,常见的结构可分为两大类,__线性结构____和__非线性结构___。

2、应用题

1、给出以下算法的时间复杂度. void fun(int n) {

int i=1,k=100; while(i

时间复杂度为____O(n)_____。 2、给出以下算法的时间复杂度. void fun2(int n) {

int i=1,k=100;

k=k+1; i=i+2;

while(i

时间复杂度为____O(log n)___________。

i=i*10; k=k+1;

第2章 线性表

1、填空题

1. 线性表按照存储结构不同主要有两种实现方式,一种是__顺序_表,另一种是___链___表。

2.顺序表采用__随机___访问机制对数据元素进行访问。 3.若在单链表结点p的后面插入一个新的结点s,则其操作序列为: ①____s->next=p->next_____________; ②____p->next=s___________________;

4.在单向链表中,若要删除某个结点p,一般要找到__p的前趋__结点,才能实现该操作。

2、选择题

1. 将两个各有n个元素的有序表归并成一个有序表,其最少的比较次数

是 A 。

(A)n (B)2n-1 (C)2n (D)n-1

2. 在单链表中,如果在结点p之后插入一个新结点s,其操作为 A 。 (A)s->next=p->next; p->next=s; (B)p->next=s; s->next=p->next;

(C)s->next=p; p->next=s->next; (D)p->next=s; s->next=p;

3.若长度为n的线性表采用顺序存储结构,在其第i个位置删除一个元素的算法的平均时间复杂度为( C )。(1≤i≤n)

A.O(0) B.O(1) C.O(n) D.O(n2)

4. 若长度为n的线性表采用顺序存储结构,在其第i个位置插入一个新元素需要移动的元素个数为( B )。(1≤i≤n+1)

A.n-i B.n-i+1 C. i D.n-i-1

3、判断题

1.线性表中每一个元素都有一个前驱和一个后继。( × )

4、程序设计题

1、单链表的结点结构定义如下: struct LinkNode {

LinkNode *next; int data; };

请根据述函数的功能写程序。

void Insert(LinkNode *h,LinkNode *s)

{//h指向链表的头结点(即使链表中没有元素,头结点也存在。) //链表中元素已经递增有序

//函数功能为将结点s插入到链表h中。插入后链表仍然保持递增的顺序 LinkNode *p,*q;//q指向p的前驱 q=h; p=h->next; while(p) {

if(p->data>s->data)

}

{//寻找到插入点位置,插入s } else { }

q=p; (1分) p=p->next; (1分) q->next=s; s->next=p; return;

//当表中没有比s大的结点时,插入到表尾 s->next=q->next; (2分) q->next=s; (2分) }

2、设顺序表L是一个递增有序表,试写一算法,将x插入L中,并使L仍是一个有序表。顺序表的结构定义如下:

#define ListSize 100 // 假定表空间大小为100 struct SqList {

int elem[ListSize]; // 数组elem用于存放表中的数据 int length; // 当前的表长度 };

//以上为顺序表的结构 //函数头定义如下

void InsertIncreaseList( SqList &L ,int x ) { int i;

if ( L.length>=ListSize) cout<<”OVERFLOW”; //判断是否溢出 for ( i=L.length ; i>0 && L.elem[ i-1 ] > x ; i--)

L.elem[ i ]=L.elem[ i-1 ] ; // 比较并移动元素

L.elem[ i ] =x; //插入x L.length++; //表长增1 }

///////

3、单链表中结点的结构如下所示: typedef struct node { int data;

struct node *next; }node;

请设计满足下述功能的函数。

要求: 建立带头结点的单链表H,要求函数从屏幕上读入m个整数,每读入一个,便生成相应的结点,并且把它插入到链表H的尾部。函数形式为void CreateLinkList(node *H)。

参考程序:

void CreateList(node *H) {//H指向头指针 int m,temp;

cout<<\输入数据的个数:\ cin>>m;// int i=1; node *tail; H->next=NULL; tail=H;

while(i<=m) {

cout<<\ cin>>temp;

node *t=new node ; t->data=temp;

t->next=tail->next; tail->next=t; tail=t; i++;

}