数据结构与算法1

一、选择题

1、数据结构是一门研究非数值计算程序中计算机的     A   以及它们之间的  B  和运算等的学科。

  A. 操作对象  计算方法  逻辑存储  数据映像

    A. 结构  关系   运算   算法

2、线性结构的顺序存储结构是一种      A  的存储结构，线性结构的链式存储结构是一种    B 的存储结构。

  A. 随机存取  顺序存取  索引存取  散列存取

 A. 随机存取  顺序存取  索引存取  散列存取

3、下面程序的时间复杂度为        C     。

 2)  2)  ×n) 

4、下面算法的时间复杂度为            B  。

int f(int n)

{

}

A. O(1)    2) 

5、计算机算法是解决问题的有限运算序列，具备输入、输出、    B       五个特性。

 可执行性、可移植性和可扩充性  可行性、确定性和有穷性

 确定性、有穷性和稳定性   易读性、稳定性和安全性

6、通常所说的时间复杂度是指          Ｃ    .

 语句的频度  算法的时间消耗 

C. 渐进时间复杂度   最坏的时间复杂度

7、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新的元素算法的时间复杂度为         C        。

 2n)      2)

8、以下关于线性表的说法中，不正确的是     C       。

 线性表中的数据元素可以是数字、字符、结构等不同类型

 线性表中包含的数据元素个数不是任意的

 线性表中的每一个结点都有且只有一个直接前驱和直接后继

 存在这样的线性表：表中各结点都没有直接前驱和直接后继

9在有n个结点的顺序表上做插入、删除结点运算的时间复杂度为        B    。

     2)  2n)

10、等概率情况下，在有n个结点的顺序表上做插入结点操作，需平均移动的结点数目为  

      B     。

11、在一个长度为n的顺序存储的线性表中查找值为x的元素时，平均查找长度(及x同元素的平均比较次数，假定查找每个元素的概率都相等)为          C   。

12、在顺序表中，只要知道    A        ，就可以求出任一结点的存储地址。

 基地址  结点大小  向量大小  基地址和结点大小

13、将两个各有n个元素的有序表归并为一个有序表，其最少的比较次数是      A       。

14、线性表采用链表存储时其存储地址要求      D     。

 必须是连续的    部分地址必须是连续的

 必须是不连续的   连续的和不连续的都可以

15、下面关于线性表的描述中，错误的是  Ｂ          。

A. 线性表采用顺序存储，必须占用一片连续的存储单元

B. 线性表采用顺序存储，便于进行插入和删除操作

C. 线性表采用链式存储，不必占用一片连续的存储单元

D. 线性表采用链式存储，便于插入和删除操作

16、向具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是      Ｂ     

     2)  2n)

17、在一个带头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行的语句是      Ｄ        。

18、在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行的语句是 Ｃ  。

二、填空题

1、线性结构中元素的关系是    一对一           ，树形结构中元素的关系是   一对多         ，图形结构中元素的关系是 多对多         。

2、算法的5个重要特性是    输入    、 输出          、       确定性         、               和        有限性  ， 可行性    。

3、评价一个算法优劣的两个主要指标是 时间复杂性          和 空间复杂性           。

4、线性表中结点的集合是有限的，结点之间的关系是   一对一            关系。

5、顺序表中访问任一个结点的时间复杂度为      O（1）           。

6、线性表中第一个结点没有直接前驱，称为      头          结点。

7、在一个长度为n的顺序表中删除第i个元素，要移动   n-i           个元素。

8、在一个长度为n的顺序表中，如果要在第i个元素前插入一个元素，要后移  n-i+1      个元素，在插入操作中，移动元素的均值为   (n+1)/2            。

9、根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成 单向链表         和  双向链表    。

10、链式存储的特点是利用    指针       来表示数据元素之间的逻辑关系。

11、静态链表(线性表的游标实现)是指用   数组下标          表示单链表的指针。

12、在静态链表中，一般都有一个变量available表示的结点链，其中的结点为 空闲节点        。

三、写一个算法合并两个已排序的线性表。（用两种方法：数组表示的线性表（顺序表）和指针表示的线性表（链表））

 要求：1、定义线性表节点的结构，并定义节点的型和位置的型。

 、定义线性表的基本操作

 、在1，2的基础上，完成本题。

 、在main函数中进行测试：先构建两个有序的线性表，然后合并这两个线性表。

数组：#include

#define maxlength 100

using namespace std;

typedef int Elementtype;

typedef int position;

struct LIST {

  };

position End(LIST L)

{

}

void Insert(Elementtype x, position p, LIST &L)

{

}

position Locate( Elementtype x, LIST L )

{

}

Elementtype Retrieve( position p, LIST L )

{

}

void Delete( position p, LIST & L)

{

}

position Previous( position p, LIST L )

{

}

position Next( position p, LIST L )

{

}

void MakeNull( LIST &L )

{

}

void Merge( LIST &L, LIST L1, LIST L2 )

{

}

void Print( LIST L )

{

 线性表元素个数为：" << End(L) << endl;

 元素分别为：";

}

int main()

{

 请输入两个有序线性表：" << endl;

 第一个线性表长度为：";

 输入第一个线性表元素：";

 第一个线性表长度为：";

 输入第二个线性表元素：";

}

链表：#include

#define maxlength 100

using namespace std;

typedef int Elementtype;

struct celltype{

  };

typedef celltype *LIST;

typedef celltype *position;

position End( LIST L )

{

}

void Insert( Elementtype x, position p, LIST &L )

{ 

}

position Locate( Elementtype x, LIST L )

{ 

}

Elementtype Retrieve( position p , LIST L )

{

}

void Delete( position p, LIST &L )

{ 

}

position Previous( position p, LIST L )

{ 

} 

position Next( position p, LIST L )

{ 

}

position MakeNull( LIST &L )

{

}

void Merge( LIST &L, LIST L1, LIST L2 )

{

}

void Print( LIST L )

{

 线性表元素个数为：" << End(L) << endl;

 元素分别为：";

}

int main()

{

 请输入两个有序线性表：" << endl;

 第一个线性表长度为：";

 输入第一个线性表元素：";

 第二个线性表长度为：";

 输入第二个线性表元素：";

}

四、已知一个单向链表，试给出复制该链表的算法。

要求：1、定义线性表的节点的结构以及节点的型和位置的型。

 、定义线性表的基本操作

 、在1，2的基础上，完成本题。

 4、在main函数中进行测试：先构建一个线性表，并定义一个空线性表，然后进行复制。

#include

using namespace std;

struct node {  

 int data;  

 struct node* next;  

};  

typedef struct node* pNode;

pNode newNode(int data){  

pNode nd = (pNode)malloc(sizeof(node));  

nd->data = data;

nd->next = NULL;

return nd;  

} 

struct node* copyList(struct node* head) {  

struct node* current = head;  

struct node* newList = NULL; //新链表的头指针  

struct node* tail = NULL; // 新链表的尾部指针  

while (current != NULL) {  

if (newList == NULL) { // 特殊情况，第一个新结点  

newList = newNode(current->data);

tail = newList;  

 } 

 else {  

tail->next = newNode(current->data);

tail = tail->next;

}  

current = current->next;

    }  

    return(newList);  

}

void push(struct node** headRef, int data)  

{  

    pNode nd = newNode(data);  

nd->next = *headRef;

      *headRef = nd;  

}  

struct node* copyListWithRef(struct node* head)  

{  

    struct node* current = head;  

    struct node* newList = NULL;  

    struct node** lastPtr = &newList;    

   while (current != NULL) {  

    push(lastPtr, current->data);  

lastPtr = &((*lastPtr)->next);

current = current->next;

    }  

    return newList;  

} 

五、写出从一个带表头的单链表中删除其值等于给定值x的结点的算法函数：

 如果x在该链表中，则删除对应结点，并返回其在链表中的位置（逻辑位置，第一个结点的逻辑位置为1），否则返回-1。

要求：1、定义线性表的节点的结构以及节点的型和位置的型。

2、定义线性表的基本操作

3、在1，2的基础上，完成本题。

4、在main函数中进行测试：先构建一个线性表，然后调用函数删除值等于给定值的节点。

#include

uaing namespace std;

#define maxlength 100

typedef int elementtype;

typedef int position;

struct LIST {

    elementtype elements[maxlength];

    int last;

};

int delete(LIST &L, int x)

{ 

    position q ;

if ( ( p > L.last ) || ( p < 1 ) )

        error ("指定位置不存在！");

    else

    { 

        L.last = L.last-1;

     for ( q = p ; q <= L.last ; q ++ )

            L.elements[ q ] = L.elements[ q + 1 ];

    }

} 

六、写出一个将两个静态链表（属于同一个存储池）合并的算法函数：

 合并的方法是将N链表中的所有结点添加到M链表的后面，并将N链表的表头结点添加到空闲结点链表中。

要求：1、定义静态链表的结点的结构以及结点的型SPACE以及位置（position）和游标（cursor）的型。

 、定义静态链表的基本操作：void Initialize(); 初始化，将所有存储池中的结点设置为空闲；cursor GetNode(); 从空闲链中获取一个结点；void FreeNode(cursor q); 将结点q加入到空闲链； void Insert ( elementtype x, position p, cursor M ); 在链表M中的位置为p的元素后面添加一个值为x的结点；void Delete (cursor M,  position p ); 在链表M中删除位置为p的元素的后一个元素。

 、在1、2的基础上完成本题。

4、在main函数中进行测试：先构建一个存储池，然后在该存储池中创建两个静态表，最后将这两个静态表合并。

#include

uaing namespace std;

#define maxsize 100

typedef int elementtype;

typedef struct {

    elementtype element ;

    int next ;

} spacestr; /*结点类型*/

spacestr SPACE[ maxsize ] ;/*存储池*/

typedef int position, cursor;

cursor available;

void Initialize()

{

    int j;

    /* 依次链接池中结点*/

for (j=0; j        SPACE[j].next=j+1;

    SPACE[j].next=-1;      /* 最后一个接点指针域为空*/

    available=0;        /* 标识线性表*/

}

// 可用空间的分配操作

cursor GetNode() // q=new spacestr ;

{ 

    cursor p;

    if (SPACE[available].next ==-1)

        p=-1;

    else

    { 

        p= SPACE[available].next ;

        SPACE[available].next =    SPACE[ p ].next ;

    }

    return p;

}/* 从池中删除*/

void FreeNode(cursor q) //delete q;

{ 

    SPACE [ q ].next =SPACE[available].next ;

    SPACE[available].next = q ;

}/* 放回池中*/

void Insert ( elementtype x, position p, spacestr *SPACE )

{ 

    position q ;

    q = GetNode( ) ;

    SPACE[ q ].element = x ;

    SPACE[ q ].next = SPACE[ p ].next ;

    SPACE[ p ].next = q ;

}

void Delete ( position p, spacestr *SPACE )

{ 

    position q ;

    if ( SPACE[ p ].next != -1 )

    { 

        q = SPACE[ p ].next ;

        SPACE[ p ].next = SPACE[ q ].next ;

        FreeNode( q ) ;

    }

}

void main()

{

    Initialize();

    position p=GetNode();

    Insert(2, p, SPACE);

    p=GetNode();

    Insert(4, p, SPACE);

}

要求：

1、上述作业要求在单独完成；

2、完成后，于规定期限内提交到教学辅助系统中，注意，在提交时将所编写的程序统一拷贝到一个Word文件中，文件名为学号的最后三位数＋姓名，比如501XXX