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
#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;
5-5
本题目要求实现压入链栈操作和弹出链栈操作。
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
已知先序遍历序列和中序遍历序列建立二叉树。 例如
输入先序遍历序列： 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行，每行输出哈夫曼节点的权值、父节点编号、左右孩子节点编号。
1 6 0 0 5 7 0 0 2 6 0 0 7 8 0 0 10 9 0 0 3 7 1 3 8 8 6 2 15 9 4 7 25 0 5 8
作者
王东
单位
贵州师范学院
时间限制
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##
输出：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分
}
注：请使用西文半角逗号。
