程序填空题

5-1链栈入栈出栈操作。#include<iostream>using namespace std;typedef char SElemType;typedef struct StackNode {SElemType data;struct StackNode *next;} StackNode, *LinkStack;int Push(LinkStack &S, SElemT

真题OK撒

6043人浏览 · 2021-12-26 19:52:39

真题OK撒 · 2021-12-26 19:52:39 发布

5-1

链栈入栈出栈操作。

#include<iostream>
using namespace std;

typedef char SElemType;

typedef struct StackNode {
    SElemType data;
    struct StackNode *next;
} StackNode, *LinkStack;


int Push(LinkStack &S, SElemType e) {
    LinkStack p;
    p = new StackNode; 
    p->data = e;

delete p;
    return 1;
}

int main() {
    LinkStack s=NULL;
    int n, i;
    char c;
    cin >> n;
    for(i=0;i<n;i++){
        cin >> c;
        Push(s,c);        
    }
    for(i=0;i<n;i++){
         Pop(s,c);
        cout << c << " ";
    }
    return 0;
}

作者

王东

单位

贵州师范学院

时间限制

400 ms

内存限制

64 MB

5-2

本题目要求入顺序栈。

#define MAXSIZE  1024 
#include <stdio.h>
#include <malloc.h>  
typedef  int datatype;
typedef  struct
{
    datatype  data[MAXSIZE];
    int  top;
}SeqStack;

int Push_SeqStack (SeqStack *s, datatype  x)
{    if (s->top==MAXSIZE-1)  return 0; 
     else 
      {

         return 1;
     }
 }

作者

朱晓龙

单位

西安邮电大学

时间限制

400 ms

内存限制

64 MB

5-3

本题目要求出顺序栈。

#define MAXSIZE  1024 
#include <stdio.h>
#include <malloc.h>  
typedef  int datatype;
typedef  struct
{
    datatype  data[MAXSIZE];
    int  top;
}SeqStack;



int Pop_SeqStack(SeqStack *s, datatype *x)
{  
    if  (Empty_SeqStack ( s ) )  return 0;  
    else 
    {

3分

=s->data[s->top];

3分

; return 1; } }

作者

朱晓龙

单位

西安邮电大学

时间限制

400 ms

内存限制

64 MB

5-4

本题目要求函数LinkStack Init_LinkStack () 初始化栈，并使用函数Empty_LinkStack (LinkStack top )判断链栈是否为空。链栈为空,函数返回1,否则返回0。

#include <stdio.h>
#include <malloc.h>  
typedef  int datatype;
typedef struct node
{    datatype data;
     struct node *next;
}StackNode, * LinkStack;

LinkStack  Init_LinkStack ()
{   
    return  NULL;  
}

int  Empty_LinkStack (LinkStack top )  
{ 
    if (

3分

) return 1; else return 0; }

作者

朱晓龙

单位

西安邮电大学

时间限制

400 ms

内存限制

64 MB

5-5

本题目要求实现压入链栈操作和弹出链栈操作。

#include <stdio.h>
#include <malloc.h>  
typedef  int datatype;
typedef struct node
{    datatype data;
     struct node *next;
}StackNode, * LinkStack;

LinkStack Push_LinkStack (LinkStack top, datatype x)         
{ 
    StackNode *s;
    s=(StackNode *)malloc (sizeof (StackNode));
    s->data=x;

3分

;

3分

; return top; } LinkStack Pop_LinkStack (LinkStack top, datatype *x) { StackNode *p; if (top==NULL) return NULL; else {

3分

; p = top;

3分

; free (p); return top; } }

作者

朱晓龙

单位

西安邮电大学

时间限制

400 ms

内存限制

64 MB

5-6

本题目要求Init_SeQueue()函数初始化循环队列，返回指向队列的指针，Empty_SeQueue(c_SeQueue *q)函数判空队列，空队列返回1。否则返回0。

#include <stdio.h>
#include <malloc.h>
#define MAXSIZE 1024
typedef int datatype;
typedef  struct     { 
    datatype data[MAXSIZE];          /*数据的存储区*/
    int front,rear;                  /*队头队尾指针*/
    int num;                         /*队中元素的个数*/
 }c_SeQueue;                         /*循环队*/


c_SeQueue*  Init_SeQueue()
{     
    c_SeQueue *q;
    q=(c_SeQueue*)malloc(sizeof(c_SeQueue));

3分

; q->num=0; return q; } int Empty_SeQueue(c_SeQueue *q) { if (

3分

) return 1; else return 0; }

作者

朱晓龙

单位

西安邮电大学

时间限制

400 ms

内存限制

64 MB

5-7

本题目要求Out_SeQueue (c_SeQueue *q , datatype *x)函数将出循环队列的值送给变量x。出队成功返回1，否则返回-1。

#include <stdio.h>
#include <malloc.h>
#define MAXSIZE 1024
typedef int datatype;
typedef  struct     { 
    datatype data[MAXSIZE];          /*数据的存储区*/
    int front,rear;                  /*队头队尾指针*/
    int num;                         /*队中元素的个数*/
 }c_SeQueue;                         /*循环队*/


int   Out_SeQueue (c_SeQueue *q , datatype  *x)
{  
    if  (q->num==0)
    {  
        printf("The c+SeQueue is empty");
        return -1;
    }
    else 
    {  
        q->front=

3分

; *x=q->data[q->front];

3分

; return 1; } }

作者

朱晓龙

单位

西安邮电大学

时间限制

400 ms

内存限制

64 MB

5-8

本题目要求Init_LQueue()函数初始化带头结点的链队列,并用Empty_LQueue( LQueue *q)函数判断队列是否为空，队列为空返回1，否则返回0。

#include <stdio.h>
#include <malloc.h>
typedef int datatype;
typedef struct node
{
    datatype data;
    struct node *next;
}QNode;

typedef struct
{
    QNode *front, *rear;
}LQueue;

LQueue  *Init_LQueue()
{      
    LQueue *q;
    QNode *p;
    q=(LQueue * )malloc(sizeof(LQueue));   
    p=(QNode * )malloc(sizeof(QNode));    
    p->next=NULL;

3分

; return q; } int Empty_LQueue( LQueue *q) { if (

3分

) return 1; else return 0; }

作者

朱晓龙

单位

西安邮电大学

时间限制

400 ms

内存限制

64 MB

5-9

本题目要求使用函数In_LQueue(LQueue *q , datatype x)将数据x入链队列q中。

#include <stdio.h>
#include <malloc.h>
typedef int datatype;
typedef struct node
{
    datatype data;
    struct node *next;
}QNode;

typedef struct
{
    QNode *front, *rear;
}LQueue;

void In_LQueue(LQueue *q , datatype  x)
{    
    QNode *p;
    p=(QNode * )malloc(sizeof(QNode));  
    p->data=x;   
    p->next=NULL;

3分

;

3分

; }

作者

朱晓龙

单位

西安邮电大学

时间限制

400 ms

内存限制

64 MB

5-10

本题目要求使用函数Out_LQueue(LQueue *q , datatype *x)从链队列q中弹出数据。

#include <stdio.h>
#include <malloc.h>
typedef int datatype;
typedef struct node
{
    datatype data;
    struct node *next;
}QNode;

typedef struct
{
    QNode *front, *rear;
}LQueue;

int Out_LQueue(LQueue *q , datatype  *x)
{   
      QNode *p;
     if (Empty_LQueue(q) ) 
     { 
         printf ("The LQueue is empty");
         return 0; 
     }   
     else 
     { 
         p=q->front->next;

3分

; *x=p->data; free(p); if (q->front->next==NULL)

3分

; return 1; } }

作者

朱晓龙

单位

西安邮电大学

时间限制

400 ms

内存限制

64 MB

5-11

下列代码的功能是将二叉树T中的结点按照层序遍历的顺序输出。

typedef struct TreeNode *Tree;
struct TreeNode
{
   int Key;
   Tree  Left;
   Tree  Right;
};

void Level_order ( Tree T )
{
   Queue Q;

   if ( !T ) return; 
   Q = CreateQueue( MaxElements ); 
   Enqueue( T, Q ); 
   while ( !IsEmpty( Q ) ){
      T = Front_Dequeue ( Q ); /* return the front element and delete it from Q */
      printf("%d ", T->Key);
      if ( T->Left )

3分

; if (

3分

)

3分

; } }

作者

陈越

单位

浙江大学

时间限制

400 ms

内存限制

64 MB

5-12

下列代码的功能是计算给定二叉树T的宽度。二叉树的宽度是指各层结点数的最大值。函数Queue_rear和Queue_front分别返回当前队列Q中队尾和队首元素的位置。

typedef struct TreeNode *BinTree;
struct TreeNode
{
   int Key;
   BinTree  Left;
   BinTree  Right;
};

int Width( BinTree T )
{
   BinTree  p;
   Queue Q;
   int Last, temp_width, max_width;

   temp_width = max_width = 0;
   Q = CreateQueue(MaxElements);
   Last = Queue_rear(Q);
   if ( T == NULL) return 0;
   else {
      Enqueue(T, Q);
      while (!IsEmpty(Q)) {
         p = Front_Dequeue(Q);

3分

; if ( p->Left != NULL ) Enqueue(p->Left, Q);

3分

; if ( Queue_front(Q) > Last ) { Last = Queue_rear(Q); if ( temp_width > max_width ) max_width = temp_width;

3分

; } /* end-if */ } /* end-while */ return max_width; } /* end-else */ }

作者

陈越

单位

浙江大学

时间限制

400 ms

内存限制

64 MB

5-13

二叉树的层序遍历: 下面代码的功能是将二叉树中的结点按层次序遍历的顺序输出。请填空。

#include <stdio.h>
#include <stdlib.h>
#include <queue>
#include <stack>
using namespace std;

struct TreeNode
{
    char data;
    TreeNode* left;
    TreeNode* right;
};

void levelOrder(struct TreeNode* root)
{
    queue<struct TreeNode*> que;
    if (root == NULL)return;
    que.push(root);
    while (!que.empty()) {
        struct TreeNode* tmp = que.front();
        que.pop();
        printf(" %c", tmp->data);
        if (tmp->left)

5分

; if (

5分

)

5分

; } }

作者

李廷元

单位

中国民用航空飞行学院

时间限制

400 ms

内存限制

64 MB

5-14

已知先序遍历序列和中序遍历序列建立二叉树。例如

二叉树.png

输入先序遍历序列： ABDFGC，再输入中序遍历序列： BFDGAC，则输出该二叉树的后序遍历序列： FGDBCA。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef char ElementType;
typedef struct BiTNode{
    ElementType data;
    struct BiTNode *lchild;
    struct BiTNode *rchild;
}BiTNode,*BiTree;

BiTree CreatBinTree(char *pre,char*in,int n );
void postorder( BiTree T );

int main()
{
    BiTree T;
    char prelist[100];
    char inlist[100];
    int length;
    scanf("%s",prelist);
    scanf("%s",inlist);
    length=strlen(prelist);
    T=CreatBinTree(prelist,inlist, length);
    postorder(  T );
    return 0;
}
void  postorder( BiTree T )
{
    if(T)
    {

        postorder(T->lchild);
        postorder(T->rchild);
        printf("%c",T->data);
    }
}
BiTree CreatBinTree(char *pre,char*in,int n)
{
    BiTree T;
    int i;
    if(n<=0) return NULL;
    T=(BiTree)malloc(sizeof(BiTNode));
    T->data=pre[0];
    for(i=0;in[i]!=pre[0];i++);
    T->lchild=

3分

; T->rchild=

3分

; return T; }

作者

DS课程组

单位

临沂大学

时间限制

400 ms

内存限制

64 MB

5-15

创建哈夫曼树。


#include<cstring>
#include<iostream>
using namespace std; 

typedef struct
{    
    int weight;
    int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode;


void Select(HuffmanTree HT,int len,int &s1,int &s2)
{
    int i,min1=32767,min2=32767;
    for(i=1;i<=len;i++)
    {
        if(HT[i].weight<min1&&HT[i].parent==0)
        {
            s2=s1;
            min2=min1;
            min1=HT[i].weight;
            s1=i;
        }
        else if(HT[i].weight<min2&&HT[i].parent==0)
        {    min2=HT[i].weight;
            s2=i;
        }
    }
}

void CreatHuffmanTree(HuffmanTree &HT,int n)
{
    int m,s1,s2,i;
    if(n<=1) return;
    m=2*n-1;
    HT=new HTNode[m+1];
    for(i=1;i<=m;++i)              
       { HT[i].parent=0;  HT[i].lchild=0;  HT[i].rchild=0; }
    for(i=1;i<=n;++i)        
        cin >> HT[i].weight;
    for(i=n+1;i<=m;++i) 
    {

2分

; HT[s1].parent=

2分

; HT[s2].parent=

2分

; HT[i].lchild=

2分

; HT[i].rchild=

2分

; HT[i].weight=

2分

; } } void print(HuffmanTree HT,int n) { for(int i=1;i<=2*n-1;i++) cout << HT[i].weight << " " << HT[i].parent << " " << HT[i].lchild << " " << HT[i].rchild << endl; } int main() { HuffmanTree HT; int n; cin >> n; CreatHuffmanTree(HT,n); print(HT,n); return 0; }

输入样例：

第一行输入一个数n(1<n<100)，表示叶子节点的个数，接下去输入n个整数(小于1000），表示每个节点表示的字符和权值。

5 1 5 2 7 10

输出样例：

输出2*n-1行，每行输出哈夫曼节点的权值、父节点编号、左右孩子节点编号。

作者

王东

单位

贵州师范学院

时间限制

400 ms

内存限制

64 MB

5-16

#include<iostream>
using namespace std;

typedef struct ElemType{    
    int key;
}ElemType;

typedef struct BSTNode{
    ElemType data;
    BSTNode *lchild,*rchild;
}BSTNode,*BSTree;

int flag=1;

BSTree SearchBST(BSTree T,char key) {
  if(

2分

) return T; else if (key<T->data.key)

2分

; else

2分

; } void InsertBST(BSTree &T,ElemType e )；//实现细节隐藏 void CreateBST(BSTree &T ) { int i=1,n; cin >> n; T=NULL; ElemType e; while(i<=n){ cin>>e.key; InsertBST(T, e); i++; } } int main() { BSTree T; CreateBST(T); int key; cin>>key; BSTree result=SearchBST(T,key); if(result) {cout<<"find!";} else {cout<<"not find!";} return 0; }

作者

王东

单位

贵州师范学院

时间限制

400 ms

内存限制

64 MB

5-17

使用递归方式计算二叉树的深度。提示：二叉树是根据先序遍历顺序建立起来的。

#include<stdio.h>
#include<stdlib.h>
typedef struct BiNode
{
    char data;
    struct BiNode *lchild, *rchild;
}BiTNode, *BiTree;


void CreateBiTree(BiTree * T)
{
    char ch;
    scanf("%c", &ch);
    if (ch == '#')
        *T = NULL;
    else
    {
        *T = (BiTree)malloc(sizeof(BiTNode));
        (*T)->data = ch;
        CreateBiTree(&(*T)->lchild);
        CreateBiTree(&(*T)->rchild);
    }
}

int Depth(BiTree T)
{
    int m, n;
    if (

2分

) return 0; else { m =

2分

; n =

2分

; if (m > n) return(m + 1); else return (n + 1); } } int main() { BiTree tree = NULL; CreateBiTree(&tree); int depth = Depth(tree); printf("%d", depth); return 0; }

测试数据

ab##c##.png

输入：ab##c##
输出：2

作者

余雨萍

单位

中原工学院

时间限制

400 ms

内存限制

64 MB

5-18

给定一组整数：

{ 47, 25, 87, 36, 90, 18, 65, 31, 79, 58 }

采用简单选择排序法，请写出经过一趟排序后的结果：

4分

}

注：请使用西文半角逗号。

作者

李祥

单位

湖北经济学院

时间限制

400 ms

内存限制

64 MB

5-19

给定一组整数：

{ 47, 25, 87, 36, 90, 18, 65, 31, 79, 58 }

采用直接插入排序法，请写出经过一趟排序后的结果：

4分

}

注：请使用西文半角逗号。

作者

李祥

单位

湖北经济学院

时间限制

400 ms

内存限制

64 MB

5-20

本题要求实现快速排序操作，待排序列的长度1<=n<=1000。使排序后的数据从小到大排列。 ###类型定义：

typedef  int  KeyType;
typedef  struct {                      
  KeyType *elem; /*elem[0]一般作哨兵或缓冲区*/                       
  int Length;      
}SqList;

程序：

#include<stdio.h>
#include<stdlib.h>
typedef  int  KeyType;
typedef  struct {                      
  KeyType *elem; /*elem[0]一般作哨兵或缓冲区*/                       
  int Length;      
}SqList;
void  CreatSqList(SqList *L);/*待排序列建立，由裁判实现，细节不表*/ 
int Partition ( SqList  L,int low,  int  high );
void Qsort ( SqList  L,int low,  int  high );
int main()
{
  SqList L;
  int i;
  CreatSqList(&L);
  Qsort(L,1,L.Length);
  for(i=1;i<=L.Length;i++)
   {        
     printf("%d ",L.elem[i]);
    }
  return 0;
}
int Partition ( SqList  L,int low,  int  high ) 
{ /*一趟划分*/
  KeyType  pivotkey;
  L.elem[0] = L.elem[low];   
  pivotkey = L.elem[low];
  while(low<high) 
    {
         while ( low < high && L.elem[high] >= pivotkey ) 
                --high;
         L.elem[low] = L.elem[high];
         while ( low < high && L.elem[low] <= pivotkey )
                 ++low;
         L.elem[high] = L.elem[low];
     }
   L.elem[low]=L.elem[0]; 
   return low;
}
void Qsort ( SqList  L,int low,  int  high ) 
{ 
  int  pivotloc;
  if  (

2分

) { pivotloc = Partition(L, low, high ) ; Qsort (

1分

) ;

1分

; } }

输入样例：

第一行整数表示参与排序的关键字个数。第二行是关键字值例如：

10
5 2 4 1 8 9 10 12 3 6

输出样例：

输出由小到大的有序序列，每一个关键字之间由空格隔开，最后一个关键字后有一个空格。

1 2 3 4 5 6 8 9 10 12

作者

DS课程组

单位

临沂大学

时间限制

400 ms

内存限制

64 MB

5-21

冒泡排序

给定一组整数：

{ 47, 25, 87, 36, 90, 18, 65, 31, 79, 58 }

采用冒泡排序法，请写出经过一趟排序后的结果：

4分

}

注：请使用西文半角逗号。

2048 AI社区

有“AI”的1024 = 2048，欢迎大家加入2048 AI社区

更多推荐

AI编程革命：不会用就落后了？

AI辅助编程不是一道选择题，而是一场正在发生的变革。确实还有人尚未登船，原因复杂多样。然而，理解这些障碍，积极寻求解决方案，并认识到拥抱AI是提升个人和团队未来竞争力的关键一步。与其问“还有人不会用吗？”，不如思考“我/我们该如何更好地利用它？” 掌握驾驭AI的能力，将是未来程序员不可或缺的“新基础技能”。这场人机协作的编程新时代，才刚刚拉开序幕。