2016年长沙理工大学初试算法题

2016年长沙理工大学初试算法题

用C或C++语言实现如下算法。说明：必须写清楚算法所涉及到的数据结构,对程序要加以适当的注释，程序应有良好的结构.
1.若一个字符串与其自身的逆序串相等，则称该字符串为回文字符串。例如"CSUSTSUSC"就是一个回文字符串。设计实现顺序栈（包括栈的初始化、进栈、出栈、判栈空等操作）和链队列（包括队列的初始化、进队、出队、判队空等操作）；并基于栈和队列，编写主程序main()实现判断一个字符串是否是回文字符串，是则打印yes,否则打印no。

#include<bits/stdc++.h>
using namespace std;
const int MaxSize = 100; //栈的大小
typedef struct { // 顺序栈char data[MaxSize];int top;
}Stack;
void InitStack(Stack &S) { // 栈的初始化S.top = -1;
}
bool Push(Stack &S, char x) { // 进栈p == MaxSize - 1) return false; // 栈满，报错S.data[+&#p] = x;return true;
}
bool Pop(Stack &S, char &x) {p == -1) return false; // 栈空，报错x = S.p--];return true;
}
bool Empty(Stack S) { // 判栈空p == -1) return true;else return false;
}
//链队列
typedef struct LinkNode{char data;struct LinkNode *next;
} LinkNode;
typedef struct{LinkNode *front, *rear;
}LinkQueue;
void InitQueue(LinkQueue &Q) { // 初始化链队Q.front = Q.rear = (LinkNode *) malloc (sizeof(LinkNode));Q.front -> next = NULL;
}
void EnQueue(LinkQueue &Q, char x) { // 入队LinkNode *s;s = (LinkNode *) malloc (sizeof(LinkNode));s -> data = x;s -> next = ar -> next = ar = s;
}
bool DeQueue(LinkQueue &Q, char &x) { // 出队if(Q.front == Q.rear) return false; // 队列为空，报错LinkNode *p = Q.front -> next;x = p -> data;Q.front -> next = p -> next;ar == p) { // 若原队列中只有一个结点，删除后变为空Q.rear = Q.front;}free(p);return true;
}
bool Empty(LinkQueue Q) { // 判队空if(Q.front == Q.rear) return true;else return false;
}
int main() {char str[100];scanf("%s", str);Stack S;LinkQueue Q;InitStack(S);InitQueue(Q);char a, b;int len = strlen(str); // strlen函数获取输入字符串长度for(int i = 0; i < len; i++) {Push(S, str[i]);EnQueue(Q, str[i]);}bool flag = true;while(!Empty(S) && !Empty(Q)) {Pop(S, a);DeQueue(Q, b);if(a != b) { // a 不等于 b 则不是回文flag = false;break;}}if(flag) puts("yes");else puts("no");return 0;
}
/*
测试样例一：
CSUSTSUSC
测试样例二：
SHUSIISHKSJHS
*/

2.二叉树用二叉链表来存储表示，实现二叉树的建树（通过键盘输入）、先序遍历、中序遍历、后序遍历、销毁5个操作。编制主程序main()调用这些函数，并输出各遍历结果。

#include<bits/stdc++.h>
using namespace std;
typedef struct BitNode{char data;struct BitNode *lchild, *rchild;
}BitNode, *BiTree;
void build_tree(BiTree &bt) { // 建树,用先序遍历的思想建立二叉树char ch;scanf("%c", &ch);if(ch == '#') {bt = NULL;} else {bt = (BitNode *) malloc (sizeof(BitNode));bt -> data = ch;build_tree(bt -> lchild);build_tree(bt -> rchild);}
}
void preorder(BiTree bt) { // 先序遍历if(bt == NULL) return;printf("%c", bt->data);preorder(bt->lchild);preorder(bt->rchild);
}
void inorder(BiTree bt) { // 中序遍历if(bt == NULL) return;inorder(bt->lchild);printf("%c", bt->data);inorder(bt->rchild);
}
void postorder(BiTree bt) { // 后序遍历if(bt == NULL) return;postorder(bt->lchild);postorder(bt->rchild);printf("%c", bt->data);
}
void freeTree(BiTree bt) { // 销毁二叉树if(bt == NULL) return;freeTree(bt->lchild);freeTree(bt->rchild);free(bt);
}
int main() {BiTree T;build_tree(T);preorder(T);cout << endl;inorder(T);cout << endl;postorder(T);cout << endl;freeTree(T);return 0;
}
/*
测试样例一：
ABD###CE##F##A/ B   C/   / D   E   F
测试样例二：
ABDG##H###CE#I##F##A/ B   C/   / D   E   F/      G   H   I
*/

3.从键盘读入大小无序的80000个整数并已建立顺序表。请用时间复杂度最低的算法从中挑选出最大的前10个整数并打印。（提示：模仿堆排序的思想）

算法思路：这个题的初衷并不是想让你直接写个堆排序，然后输出最大那10个数。其实我们可以根据小根堆的特点，模仿堆排序的思想，无需直接进行堆排序。
由于小根堆的根节点是这个堆里面最小的数，因此我们可以从无序的顺序表中先将前十个数取出来建立一个小根堆，然后再依次遍历顺序表中剩下的79990个数，每次遍历的时候与小根堆的根节点进行比较，如果小于该小根堆的根节点，则不可能是最大的10个数，如果大于根节点的值，则将该数替换掉小根堆的根节点，并向下调整堆，等到80000个数全部遍历完的时候，小根堆里面的十个数就是最大的十个数。大约O(n)的时间复杂度。

void HeapAdjust(int a[], int k, int len) { // 将元素k为根的子树进行调整a[0] = a[k]; // a[0] 暂存子树根节点for(int i = k*2; i <= len; i *= 2) {if(i < len && a[i] > a[i+1]) i++; // 沿着key较小的子结点向下筛选if(a[0] <= a[i]) break;else {a[k] = a[i]; // 将a[i] 调整到双亲上k = i; // 修改k值，以便继续向下筛选}}a[k] = a[0]; // 被筛选的结点的值放入最终位置
}
void build_Min_Heap(int a[], int len) { // 建立小根堆for(int i = len / 2; i >= 1; i--) {HeapAdjust(a, i, len);}
}
void solve(int test[], int a[]) {// 假设test为已建立的顺序表, a为小根堆for(int i = 1; i <= 10; i++) a[i] = test[i];build_Min_Heap(a, 10); // 建立小根堆for(int i = 11; i <= 80000; i++) {if(test[i] > a[1]) { // 如果大于堆的根节点，则替换根节点，并调整堆a[1] = test[i];HeapAdjust(a, 1, 10); }}// 遍历完所有结点之后，小根堆里面的十个数即最大的十个数for(int i = 1; i <= 10; i++) printf("%d ", a[i]);
}

当然，我也专门写了一份用来测试我算法思路的代码，我也给出来，供大家参考，如果有啥不对的地方，欢迎大家指出来，我会尽快改正的。
test.cpp

#include<bits/stdc++.h>
using namespace std;
const int maxn = 80000;
const int mod = 80000;
void HeapAdjust(int a[], int k, int len) { // 将元素k为根的子树进行调整a[0] = a[k]; // a[0] 暂存子树根节点for(int i = k*2; i <= len; i *= 2) {if(i < len && a[i] > a[i+1]) i++; // 沿着key较小的子结点向下筛选if(a[0] <= a[i]) break;else {a[k] = a[i]; // 将a[i] 调整到双亲上k = i; // 修改k值，以便继续向下筛选}}a[k] = a[0]; // 被筛选的结点的值放入最终位置
}
void build_Min_Heap(int a[], int len) { // 建立小根堆for(int i = len / 2; i >= 1; i--) {HeapAdjust(a, i, len);}
}
/*
void solve(int test[], int a[]) {// 假设test为已建立的顺序表, a为小根堆for(int i = 1; i <= 10; i++) a[i] = test[i];build_Min_Heap(a, 10); // 建立小根堆for(int i = 11; i <= 80000; i++) {if(test[i] > a[1]) { // 如果大于堆的根节点，则替换根节点，并调整堆a[1] = test[i];HeapAdjust(a, 1, 10); }}// 遍历完所有结点之后，小根堆里面的十个数即最大的十个数for(int i = 1; i <= 10; i++) printf("%d ", a[i]);
}
*/
bool judge(int test[], int a[]) { // judge函数用于判断此时a数组里面的数是否是80000个整数里面最大的10个整数sort(test + 1, test + maxn + 1, greater<int>()); // 将 test数组从大到小排序sort(a + 1, a + 10 + 1, greater<int>()); // 将a数组从小到大排序for(int i = 1; i <= 10; i++) cout << a[i] << " ";cout << endl;for(int i = 1; i <= 10; i++) cout << test[i] << " ";cout << endl;for(int i = 1; i <= 10; i++) { // 判断堆里面的十个数是不是80000个数里面最大的10个数if(a[i] != test[i]) return false;}return true;
}
int a[11]; // 小根堆
int test[maxn+10]; // test数组用于记录输入的80000个数
int main() {srand((unsigned)time(NULL));int n;for(int i = 1; i <= 10; i++) { n = rand() % mod;//n= i;a[i] = n;test[i] = a[i];}build_Min_Heap(a, 10); // 先将前面输入的前十个数建立好小根堆for(int i = 11; i <= maxn; i++) {n = rand() % mod;//n=i;test[i] = n;if(n > a[1]) { // 如果大于堆的根节点，则替换根节点，并调整堆a[1] = n;HeapAdjust(a, 1, 10);}}for(int i = 1; i <= 10; i++) cout << a[i] << " ";cout << endl;// sort(test+1, test+maxn+1);// for(int i =1; i <= maxn; i++) cout << test[i] << " ";//cout << endl;if(judge(test, a)) cout << "yes";else cout << "no";return 0;
}