复习题

一、简述题

1. 说明在带头结点单链表L中以下三个概念的关系：头指针，头结点，首元素结点。

头指针：指向链表的第一个结点的指针。

首元结点：链表存放数据的第一个结点。

头结点：链表的第一个结点，但是其数据域不含有数据，指针域内指针指向首元结点。

2. 简述在图的遍历中，设置访问标志数组的作用。

保证图中的各顶点在遍历过程中仅访问一次

3. 说明具有n个结点的二叉树Bt，若采用二叉链表存储表示法，其空链域的数目，并写出求解过程。

2n-(n-1)=n+1

1. 简述线性表的链式存储结构的优缺点

优点：插入、删除运算方便
缺点：占用额外的存储空间存储元素之间的关系，存储密度降低
不能随机存取元素

2. 简述在一般的顺序队列中的“ 假溢出 ” 问题及解决方法。

随着队头出队慢慢地就会空出一个个存储单元，但是队尾一直再进，最后就是存储空间根本没用满，队列就满了

一种是另设一个布尔变量来判断；

第二种是少用一个元素空间，入队时先测试（(rear+1)%m = front）? 满：空；

第三种就是用一个计数器记录队列中的元素的总数。

3. 设有1000个无序元素，仅要求找出前10个最小元素，在下列排序方法中（归并排序、基数排序、快速排序、堆排序、插入排序）哪一种方法最好，为什么？

用堆排序或锦标赛排序最合适，因为不必等全部元素排完就能得到所需结果，时间效率为O(nlog2n)

1. 请写出数据结构的形式化定义，分别说明两个构成要素的含义。

数据结构是一个二元组Data_Structures=(D, S)，其中，D是数据元素的有限集，S是D上关系的有限集。

2. 使用折半查找的两个前提条件是什么？

1)采用物理线性结构存储；

2)数据必须有序。

3. 排序算法的稳定性。 举例说明某个排序算法是不稳定的。

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变。

---

线性表

1.顺序表L删除所有值为x的元素，时间复杂度O(n),空间复杂度O(1)

void delx(SqlList* L,ElemType x){
   
    
    i=0,j=0;
    while(i<L->last){
   
    
        if(L->elem[i]!=x){
   
    
            L->elem[j]=L->elem[i];
            i++,j++;
        }else{
   
    
            i++;
        }
    }
    L->last=j-1;
}

2.带头结点单链表就地逆置

void ReserveList(LinkList L){
   
    
    p=L->next;
    L->next=NULL;
    while(p){
   
    
        q=p->next;	//保留当前处理节点的下一个节点
        p->next=L->next;
        L-next=p;
        p=q;
    }
}

3.带头结点单链表L，以表中第一个元素值为标准，将表中所有值小于第一个元素放在第一个元素之前，大于放在之后

void changeList(LinkList L){
   
    
    if(L->next==NULL){
   
    
        return;
    }
    p1=L->next;
    pre=p1;	//pre始终指向正在处理元素的前一个位置
    p=p1->next;		//p为当前处理节点
    while(p){
   
    
        q=p->next;	//保存当前处理节点的下一个节点
        if(p->data>=p1->data){
   
    
            pre=p;
            p=q;
        }else{
   
    
            pre->next=p->next;
            p->next=L->next;
            L->next=p;
            p=q;
        }
    }
}

栈与队列

1.括号匹配算法

void BracketMatch(char* str){
   
    	//str为输入字符
    Stack S;
    int i;char ch;
    InitStack(&S);
    for(i=0;str[i]!='\0';i++){
   
    
        switch(str[i]){
   
    
            case '(':
            case '[':
            case '{':
            	Push($S,str[i]);
                break;
            case ')':
            case ']':
            case '}':
            	if(isEmpty(S)){
   
    
                    printf("右括号多余");
                }else{
   
    
                    GetTop(S,&ch);
                    if(Match(ch,str[i])){
   
    
                        Pop(&S,&ch);
                    }else{
   
    
                        printf("左右括号不同类");
                    }
                }
                break;
        }
    }
    if(IsEmpty(S)){
   
    
        printf("括号匹配");
    }else{
   
    
        printf("左括号多余");
    }
}

2.无括号算术表达式处理

//读入一个简单表达式计算值，OPTR为运算符栈，OVS为运算数栈
int ExpEvaluation(){
   
    
    InitStack($OPTR);
    InitStack(&OVS);
    Push($OPTR,'#');
    ch=getchar();
    while(ch!='#'||GetTop(OPTR)!='#'){
   
    
        if(!In(ch,OPSet)){
   
    	//不是操作符 是操作数
            n=GetNumber(ch);
            Push(&OVS,n);
            ch=getchar();
        }else{
   
    
            switch(Compare(ch,GetTop(&OPTR))){
   
    
                case '>':Push(&OPTR,ch);ch=getchar();break;
                case '=':
                case '<':Pop(&OPTR,&op);Pop(&OVS,&b);
                    	 Pop(&OVS,&a);v=Excute(a,op,b);
                    	 Push(&OVS,v);break;
            }
        }
    }
    v=GetTop(&OVS);
    return v;
}

3.汉诺塔递归算法

//将X上从上到下编号1至n，直径由小到大叠放的n个圆盘，按规则借助Y移动到Z上
void hannoi(int n,char X,char Y,cahr Z){
   
    
    if(n==1){
   
    
        move(X,1,Z);
    }else{
   
    
        hannoi(n-1,X,Z,Y);
        move(X,n,Z);
        honnoi(n-1,Y,X,Z);
    }
}

---

4.打印杨辉三角形前n行元素

void YangHuiTriangle(){
   
    
    SeqQueue Q;
    InitQueue(&Q);
    EnterQueue(&Q,1);		//第1行元素入队
    for(n=2;n<=N;n++){
   
    
        EnterQueue(&Q,1);	//第n行第一个元素入队
        for(i=1;i<=n-2;i++){
   
    //利用n-1行元素产生第n行中间n-2个元素
            DeleteQueue(&Q,&tmp);
            printf(tmp);
            GetHead(Q,&x);
            tmp+=x;
            EnterQueue(&Q,tmp);
        }
        DeleteQueue(&Q,&x);
        printf(x);
        EnterQueue(&Q,1);	//第n行最后一个元素入队
    }
    while(!IsEmpty(Q)){
   
    
        DeleteQueue(&Q,&x);
        printf(x);
    }
}

树与二叉树

一、二叉树的遍历与线索化

1.输出二叉树中的节点

void PreOrder(BiTree root){
   
    
    if(root!=NULL){
   
    
        printf(root->data);
        PreOrder(root->LChild);
        PreOrder(root->RChild);
    }
}

2.输出二叉树中的叶子节点

void PreOrder(BiTree root){
   
    
    if(root!=NULL){
   
    
        if(root->LChild==NULL&&root->RChild==NULL){
   
    
            printf(root->data);
        }
        PreOrder(root->LChild);
        PreOrder(root->RChild);
    }
}

3.统计叶子节点的数目

方法一：后序遍历实现

//leafCount为保存叶子节点数目的全局变量 初始值为0
void leaf(BiTree root){
   
    
    if(root!=NULL){
   
    
        leaf(root->LChild);
        leaf(root->RChild);
        if(root->LChild==NULL&&root->RChild==NULL){
   
    
            leafCount++;
        }
    }
}

方法二：分治算法

void leaf(BiTree root){
   
    
    int leafCount;
    if(root==NULL){
   
    
        leafCount=0;
    }else if(root->LChild==NULL&&root->RChild==NULL){
   
    
        leafCount=1;
    }else{
   
    
        leafCount=leaf(root->LChild)+leaf(root->RChild);
    }
    return leafCount;
}

4.拓展先序序列创建二叉树

void CreateBiTree(BiTree* bt){
   
    
    char ch;
    ch=getchar();
    if(ch=='.'){
   
    
        *bt=NULL;
    }else{
   
    
        *bt=(BiTree)malloc(sizeof(BiTNode));
        (*bt)->data=ch;
        CreateBiTree(&((*bt)->LChild));
        CreateBiTree(&((*bt)->RChild));
    }
}

5.求二叉树高度

分治法

int PostTreeDepth(BiTree bt){
   
    
    int hr,hl,max;
    if(bt!=NULL){
   
    
        hl=PostTreeDepth(bt->LChild);	//求左子树的深度
        hr=PostTreeDepth(bt->RChild);	//求右子树的深度
        max=hr>hl?hr:hl;
        return max+1;	//加树根的高度
    }else{
   
    
        return 0;
    }
}

先序遍历实现

//depth为全局变量 为当前求得的最大层次
void PreTreeDepth(BiTree bt,int h){
   
    
    if(bt!=NULL){
   
    
        if(h>depth){
   
    
            depth=h;
        }
        PreTreeDepth(bt->LChild,h+1);
        PreTreeDepth(bt->RChild,h+1);
    }
}

6.按横向树形显示二叉树

//二叉树的横向显示是竖向显示的逆时针90度旋转，分析可知输出的节点序列正好为逆中序顺序
void PrintTree(BiTree bt,int nLayer){
   
    
    if(bt==NULL){
   
    
        return;
    }
    PrintTree(bt->RChild,nLayer+1);
    for(i=0;i<nLayer;i++){
   
    
        printf(" ");
    }
    printf(bt->data);
    PrintTree(bt->LChild,nLayer+1);
}

二、基于栈的递归消除

1.中序遍历二叉树的非递归算法

void InOrder(BiTree root){
   
    
    InitStack(&S);
    p=root;
    while(p!=NULL||!IsEmpty(S)){
   
    
        if(p!=NULL){
   
    
            Push(&S,p);
            p=p->LChild;
        }else