数据结构与算法习题1

Problem 1.

数组Q[n]用来表示一个循环队列，front为队头元素的前一个位置，rear为队尾元素的位置，计算队列中元素个数的公式为   (rear-front+n)%n   。

循环队列中，rear-front的结果可能是负整数，而对一个负整数求模，其结果在不同的编译器环境中可能会有所不同。

Problem 2.

栈和队列的共同特点是  只允许在端点插入和删除元素   。

Problem 3. 

一个n×n的对称矩阵，按列优先进行压缩存储，则其存储容量为  n*(n+1)/2  。

对于对称矩阵，行优先和列优先，其存储容量是一样的，1+2+…+n = n (n+1)/2。

Problem 4.

用链表表示线性表的优点是  便于插入和删除 ，用循环链表表示线性表的主要优点是  从表中任何结点出发都能访问整个链表。

Problem 5.

对于由n个元素组成的线性表，建立一个单链表的时间复杂度是 O(n)。

Problem 6.

在一个单链表中，已知q所指结点是p所指结点的直接前驱，若在q和p之间插入s所指结点，则需要执行下列操作：  q->next=s; s->next=p; 。

Problem 7.

已知一个栈的进栈序列是1，2，3，…，n，其输出序列是p1，p2，…，pn，若p1=n，则pi的值是  n-i+1  。

当p1=n时，输出序列是唯一的，即为n、n-1、…、2，1，则p2=n-1，…，pn=1，推断出pi=n-i+1。

Problem 8.

设目标串为s=“abcabababaab”，模式串为p=“babab”，则KMP模式匹配算法的next数组为 {-1,0,0,1,2}  。

next数组只与模式串p有关，计算过程如下表所示：

Problem 9.

在单链表中，增加头结点的目的是   方便运算的实现  。

Problem 10.

算法分析的目的是  分析算法的效率以求改进 。

Problem 11.

给定一个链表，判断链表是否存在环型链表。

如果链表有环，那么在遍历链表时则会陷入死循环，利用这个特征，我们可以设计这样的算法。

1. 使用一个slow指针，一个fast指针。

2. slow指针一次往后遍历以1个节点，fast指针一次往后遍历2个节点，一直做这样的操作。如果有环，肯定fast先于或同时slow进入环，进入后因为一快一慢，又不能跳出循环，所以有环二者一定相遇。没环fast->next=NULL结束。

struct link
{
    int data;
    link *next;
}

bool isLoop(link * head)
{
    //slow，fast用于遍历链表 
    link *slow=head,*fast=head;
    
    //若链表长度<3，则不是环型链表 
    if(head==NULL||head->next==NULL)
    {
        return false;
    }
    
    //否则链表长度>=3，遍历链表
    do{
        //slow一次遍历1个节点 
        slow=slow->next
        //fast一次遍历2个节点 
        fast=fast->next->next;
    //遍历完链表或slow指针和fast指针相遇时退出循环 
    }while(fast&&fast->next&&slow!=fast)
    
    //若slow指针和fast指针相遇，存在环 
    if(slow==fast)
        return true;
    //否则说明走到尾节点，不存在环 
    else 
        return false;
}

12.已知单链表中各结点的元素值为整数且递增有序，设计算法”DeleteBetween”删除链表中所有大于mink且小于maxk的元素，并释放被删结点的存储空间。

因为是在有序单链表上的操作，所以，要充分利用其有序性。

在单链表中查找第一个大于mink的结点和第一个小于maxk的结点，再将二者间的所有结点删除。

DeleteBetween(Node<T> *first,int mink,int maxk)
{
    p=first;
    //遍历到最后一个小于mink的节点 
    while(p->next!=NULL && p->next->data<=mink)
        p=p->next;
    // q指向第一个大于mink的节点 
    if(p->next!=NULL) 
        q=p->next;
    // 如果q->data小于mask，对q进行摘链    
    while(q!=NULL&&q->data<maxk)
    {
        u=q->next;
        p->next=u;
        delete q;
        q=u;
    }
}