SCAU数据结构笔试算法设计题汇总_一个线性表中的元素为正整数或负整数

2021

1、设计一个算法deleteMinNode(LinkList &L)，在带头结点的单链表L中删除所有结点值最小的结点（可能有多个结点值最小的结点）。

typedef struct LNode          

{

     ElemType  data;

     struct LNode   *next;

}LNode, *LinkList;

1、参考答案：

用p从头至尾扫描单链表，pre指向*p结点的前驱，用minp保存值最小的结点指针，minpre指向*minp结点的前驱。一面扫描，一面比较，将最小值的结点放到*minp中。删除节点总是要考虑定义一个前驱节点记录位置。算法如下：

void deleteMinNode (LinkList &L)
{
    LinkList pre=L, p=pre->next, minp=p, minpre=pre;
	ElemType mindata=p->data;
	while (p!=NULL && p->data<mindata)
	{	mindata=p->data;
		p=p->next;
	}
p=pre->next;
    while (p!=NULL)	
    {    
		if (p->data==mindata)
		{	pre->next=p->next;
			free(p);
		}
		pre=pre->next;
		p=pre->next;
	}
}

2、二叉树用二叉链表存储表示。

typedef struct BiTNode

{

   TelemType  data;

   Struct BiTNode *lchild, *rchild;

} BiTNode, *BiTree;

编写一个复制一棵二叉树的递归算法。

统一使用如下函数名：BiTree  CopyTree(BiTree  T)

BiTree  CopyTree(BiTree  T) {  
if (!T ) return NULL;
if (!(newT = (BiTNode*)malloc(sizeof(BiTNode))))
  exit(Overflow);
newT-> data = T-> data;
newT-> lchild = CopyTree(T-> lchild);
newT-> rchild = CopyTree(T-> rchild);
return newT;
} 

 2020

1  设计算法判断带头节点的单链表L是否是递增的单链表，单链表的存储结构如下。

typedef struct  LNode

 {

   ElemType  data;

   LNode  *next;

 }LNode,  *LinkList;

int   isriselk(LinkList  &L)
{
LNode  *p = L->next, *q; 
if(p != NULL)
  {
           while(p->next != NULL)
     {
           q = p->next; //q是p的后继
           if (q->data > p->data) //只要是递增的，就继续考察其后继
            p = q; 
else return false; //只要有一个不是后继大于前驱，便不是递增
      }
 

      2  用按层次顺序遍历二叉树的方法，统计树中具有度为1的结点数目，可以调用教材上实现的队列和栈等数据结构的相关算法，二叉树采用二叉链表存储，存储结构如下。

typedef struct BiTNode {

  TElemType data;

  struct BiTNode  * lchild,* rchild;

} BiTNode,*BiTree;

int Level(BiTree bt) //层次遍历二叉树，并统计度为1的结点的个数
{
    SqQueue Q;
    int num=0; //num统计度为1的结点的个数
     if(bt)
    { 
        InitQueue (Q); 
        EnQueue (Q,bt);//Q是以二叉树结点指针为元素的队列
        while(!QueueEmpty(Q))
        {
            p=DeQueue(Q);
             cout<<p->data;     //出队,访问结点
            if(p->lchild && !p->rchild ||!p->lchild && p->rchild) 
                num++;
                    //度为1的结点
            if(p->lchild) 
                 EnQueue(Q,p->lchild); //非空左子女入队
            if(p->rchild)  
                EnQueueIn(Q,p->rchild); //非空右子女入队
          } // while(!QueueEmpty(Q))
    }//if(bt)         
return(num); 
}//返回度为1的结点的个数 

 2019

二叉树有先序、中序、后序、按层遍历等遍历序列，给定中序和其它一种遍历序列可以用递归的方式确定一棵二叉树的结构。假定一棵二叉树的每个结点都用一个小写字母表示，现在给出二叉树的先序和中序遍历序列，编写算法输出其后序遍历序列。

输入共两行，第一行一个字符串，表示树的先序遍历，第二行一个字符串，表示树的中序遍历。输出一行，表示树的后序遍历序列。

【输入样例】

abdec

dbeac

【输出样例】

debca

#include <iostream>
#include <cstring>
 
using namespace std;
 
char x[35],z[35];
typedef struct Binode
{
    char data;
    struct Binode *lchild,*rchild;
}Binode,*Bitree;
 
void creat(Bitree &T,int xl,int xr,int zl,int zr)
{
    if(xl>xr||zl>zr)
    {
        T=NULL;
        return;
    }
    int pos;
    T=new Binode;
    T->data=x[xl];
    for(int i=zl;i<=zr;i++)
    {
        if(z[i]==x[xl])
        {
            pos=i;
            break;
        }
    }
    int len=pos-zl;
    creat(T->lchild,xl+1,xl+len,zl,pos-1);
    creat(T->rchild,xl+1+len,xr,pos+1,zr);
}
 
void show(Bitree T)
{
    if(T)
    {
        show(T->lchild);
        show(T->rchild);
        cout<<T->data;
    }
}
int main()
{
    cin>>x>>z;
    Bitree T;
    int n=strlen(x);
    creat(T,0,n-1,0,n-1);
    show(T);
}

从键盘读入一个后缀表达式（字符串），只含有0-9组成的运算数及加（+）、减（—）、乘（*）、除（/）四种运算符。每个运算数之间用一个空格隔开，不需要判断给你的表达式是否合法。以@作为结束标志。输出表达式的结果。

比如，16–9*(4+3)转换成后缀表达式为：16□9□4□3□+*–，（□代表空格）在字符数组A中的形式为（下图）：

 算法思想：读取数据，数值型入栈，运算符出栈两个元素计算后后结果入栈。
#include <iostream>
#include <stack>
using namespace std;
string  s;
stack <long long> st;
long long  getnum(int p)
{
    long long i=p,sum=0;
    while(isdigit(s[i]))
    {
        sum=sum*10+s[i]-'0';
        i++;
    }
    return sum;
}
int main()
{
    long long i,j,x1,x2;
    getline(cin,s);
    i=0;
    while(s[i]!='@')
    {
        if(isdigit(s[i]))
        {
            st.push(getnum(i));
            while(isdigit(s[i]))
                i++;
        }
        else if(s[i]=='+'||s[i]=='-'||s[i]=='*'||s[i]=='/')
        {
            switch(s[i])
            {
                case '+':x2=st.top();st.pop();x1=st.top();st.pop();st.push(x1+x2);break;
                case '-':x2=st.top();st.pop();x1=st.top();st.pop();st.push(x1-x2);break;
                case '*':x2=st.top();st.pop();x1=st.top();st.pop();st.push(x1*x2);break;
                case '/':x2=st.top();st.pop();x1=st.top();st.pop();st.push(x1/x2);break;
            }
            i++;
        }
        else
        {
            i++;
        }
    }
    cout<<st.top();
    return 0;
}

2018

1、一个线性表中的元素为正整数或负整数。设计一个算法，将正整数和负整数分开，使得线性表前半部分均为负整数，后半部分均为正整数。不要求对这些元素排序，但要求尽量减少元素交换次数。线性表使用顺序存储结构，其定义如下：

typedef  struct{

  int  *elem；

  int  listsize；

  int  length；

}SqList

统一使用函数名：void exchange(SqList L)

算法思想：设置好上下界，从两端查找正整数和负整数，然后交换，直到上下界相遇。
void exchange(SqList L)
{
    int i = 0;
    int j = L.length-1;
    while(i<j)
    {
        while(i<j&&L.elem[i]<0) i++;
        while(i<j&&L.elem[j]>0) j++;
        if(i<j)
        {
            int temp=L.elem[i];
            L.elem[i]=L.elem[j];
            L.elem[j]=temp;
            i++;
            j--;
        }
    
    }
}

以二叉链表为存储结构，编写求二叉树中叶子节点个数的算法。

二叉树的二叉链表存储结构定义如下：

typedef struct BiTNode{

int     data;

struct BiTNode  * lchild, * rchild;

} BiTNode, * BiTree;

    统一使用函数名：int countLeaf(BiTree T)

算法思想：递归实现二叉树叶子节点数=左子树叶子节点数+右子树叶子节点数
int countLeaf(BiTree T)
{
    if(T==NULL)
        return 0;
    else if(T->lchile==NULL&&T->rchile=NULL)
        return 1;
    else
        return countLeaf(T->lchild)+countLeaf(T->rchild)
}

2017

 1、设有一线性表A=（a0,a1,..., ai,...an-1），其逆线性表定义为A'=( an-1,..., ai,...,a1, a0)，设计一个算法，将线性表逆置，要求线性表仍占用原线性表的空间，线性表采用顺序存储结构。

 Typedef  struct 
 {
   ElemType *elem; // 存储空间基址
   int length; // 当前长度
   int listsize; // 当前分配的存储容量(以sizeof(ElemType)为单位)
 }SqList ;
 void  ListInvert(SqList  &L) 
{ 
       ElemType  x; 
     int i; 
     for(i=0; i<L.length/2; i++) 
     { 
         x=L.elem[i]
        L.elem[i]=L.elem[L.length-i-1]; 
         L->data[L.elem-i-1]=x; 
     } 
}
 
 

已知一棵结点数据类型为整数的满二叉树顺序存储在数组B[1…n]中，设计一个算法，产生二叉树的二叉链表。

叉树的二叉链存储结构如下：

typedef struct BiTNode{

int     data;

struct BiTNode  * lchild, * rchild;

} BiTNode, * BiTree;

Void  CreateTree(BiTree T , int  index){ 
if（index>n）
T=NULL;
else{
T=(BiTNode *)malloc(sizeof(BiTree ));
     T->data=B[index];
CreateTree(T->lchild,  index * 2 );
     CreateTree(T->rchild,  index * 2 + 1);
}
}

2016

1、编写算法，将两个非递减有序顺序表LA和LB合并成一个新的非递减有序顺序表LC：

typedef struct

{

    int *elem;

    int length;

    int listsize;

}SqList;

Status InitList_Sq(SqList &L)

{

  // 构造一个空的线性表L。

  L.elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));

  if (!L.elem) return OK;        // 存储分配失败

  L.length = 0;                  // 空表长度为0

  L.listsize = LIST_INIT_SIZE;   // 初始存储容量

  return OK;

}

统一使用如下函数名：int  MergeList (SqList  La,  SqList  Lb,  SqList  &Lc)

int MergeList_Sq(SqList La,SqList Lb,SqList &Lc){
  ElemType *pa,*pa_last,*pb,*pb_last,*pc;
   pa=La.elem;
   pb=Lb.elem;
   Lc.listsize=Lc.length=La.length+Lb.length;
   pc=Lc.elem=(ElemType *)malloc(Lc.listsize*sizeof(ElemType));
   if(!Lc.elem) 
    return ERROR;
   pa_last=La.elem+La.length-1;
   pb_last=Lb.elem+Lb.length-1;
   while(pa<=pa_last&&pb<=pb_last) 
   { // 归并
     if(*pa<=*pb)
       *pc++=*pa++;
     else
       *pc++=*pb++;
   }
   while(pa<=pa_last) 
     *pc++=*pa++;
   while(pb<=pb_last) 
     *pc++=*pb++; 
     return OK;
}
 

2、编写算法，设计判断一棵二叉树是否是完全二叉树的算法。

二叉树的存储结构定义如下：

typedef struct BTNode

 {

   int data;

   struct BTNode *lchild,*rchild;

 }BTNode,*BTree;

其中队列数据结构的基本操作如下:

InitQueue(Queue &Q);构造一个空队Q

QueueEmpty(Queue Q) ;//若队列为空返回TRUE，否则返回FALSE

EnQueue(Queue &Q,e);入队

DeQueue(Queue &Q,e);出队，并用e返回

假定上述操作已经实现，直接调用即可。

统一使用如下函数名：int  IsCompleteTree(BTree  T)

int  IsCompleteTree( BTree T ) //是完全二叉树，则返回1；否则返回0
{
BTree p = T;
if (p==0) return 1;
 
Queue Q;
InitQueue(Q);
EnQueue(Q, p);
 
int flag = 0;
while (!QueueEmpty(Q)) {
DeQueue(Q, p);
if (p->lchild && !flag) 
EnQueue(Q, p->lchild);
else {
if (p->lchild) return 0;
else flag = 1;
}
if (p->rchild && !flag) 
EnQueue(Q, p->rchild);
else {
if (p->rchild) return 0;
else flag = 1;
} // while
 
return 1;
}

2015

1、将头指针为a的单链表A分解成两个单链表A和B，表A头指针为a，表B的头指针为b，表A含有原单链表A序号为奇数的元素，而表B含有原单链表A序号为偶数的元素，且均保持原来的相对次序。

     单链表存储结构定义如下：

struct LNode

 {

   int data;

   struct LNode *next;

 };

 typedef struct LNode *LinkList;

统一使用函数名：void  Split(LinkList & A，LinkList & B) 

void Split(LinkList & A，LinkList & B) 
{
    LNode  *p,*q,*r;
    B= (LNode*)malloc(sizeof(LNode));
    B->next = NULL;
    r = B;
    p = A->next;
    while(p!=NULL && p->next!=NULL)
    {
           q = p->next;
           if(q!=NULL)
           {
             p->next = q->next;
             r->next = q;
             r = q;
             p = p->next;
           }
         }
    r->next = NULL;
 }

2、一个具有n个结点的完全二叉树采用顺序存储方式，其数据存放在整型一维数组a中，编写非递归算法对其进行先序遍历。

算法可以直接调用栈的基本操作：

初始化：InitStack(SqStack &S)

  入栈：Push(SqStack &S,int e)

出栈：Pop(SqStack &S,int &e)

判断栈空： Empty（SqStack S）

统一使用函数名：void  preorder(int a[], int n)

void preorder（int a[], int n）
{
   SqStack S;
   InitStack(S);
   Push(S,0);
   int i = 1;
   int j = 2*i;
   visit(a[i]);
   Push(S,i);
   while(Empty(S))
   {
      while(j<=n)
      {
         Push(S,j);
         i=j;  j=2*i;
         visit(a[i]);
       }
       Pop(S,i);
       j = 2*i+1;
    }
}