数据结构与算法习题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有关,计算过程如下表所示:

j

1

2

3

4

p

b

a

b

a

b

next[j]

-1

1

2

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;
    }
}

相关推荐