自学数据结构也有一段时日了，虽然推的比较慢但我一直是坚持把一块内容完全搞明白才去推下一块内容。正好有同学马上面临数据结构的期末考，我找他要了他们数据结构的期中考试上机模拟题，自己试做了一下。只做出来前四题，第五题实在是结构体太多太绕，我没有什么好的思路，暂时先搁置一会儿吧。
题目后面是我的个人题解
第一题（5分）
| （1）编写一个将数组元素逆序打印的递归函数。 （2）编写main函数，输入N个整数，将其存入到一个数组中，并调用（1）中的函数，将元素逆序输出。 Example: 从键盘读入：5，7，1，4，6 输出为：6，4，1，7，5 #include #include void InversePrint(int a[], int n) { } int main() { int i; int a[5]; for(i=0;i<5;i++){ scanf("%d", &a[i]);
} InversePrint(a,5);
} |
第二题（5+5+10=20分）
| #include "stdio.h" #include "stdlib.h" #define OK 1 #define ERROR 0 #define MAXSIZE 20 typedef int Status; typedef int ElemType; typedef struct Node { ElemType data; struct Node *next; }Node; typedef struct Node *LinkList; //========================== //打印单链表 //========================== void ListTraverse(LinkList L) { LinkList p=L->next; while(p) { printf("%d ", p->data); p=p->next; } printf("n"); } //======================================= //初始化单链表 //======================================= Status InitList(LinkList *L) { } int ListLength(LinkList L) { int i=0; LinkList p=L->next; while(p) { i++; p=p->next; } return i; } Status GetElem(LinkList L, int i, ElemType *e) { } Status ListInsert(LinkList *L, int i, ElemType e) { int j; LinkList p,s; p = *L; j = 1; while (p && j < i) { p = p->next; j=j+1; } if (!p || j > i) return ERROR; s = (LinkList)malloc(sizeof(Node)); if(!(s)) return ERROR; s->data = e; s->next = p->next; p->next = s; return OK; } //========================================================= //求单链表所有元素的累加和，并将该累加和作为一个新的结点插在单链表的尾部 //========================================================= Status AddSumForChecking(LinkList *L) { } int main() { LinkList L; ElemType e; Status i; int j,k,l; i=InitList(&L); if(i==ERROR) { return 0; } printf("Please input the length of frame:n"); scanf("%d", &k); if (k > 0) printf("Please input the element of frame one by one:n"); for(j=1;j<=k;j++) { scanf("%d", &l); i=ListInsert(&L,1,l); } printf("The frame is: "); ListTraverse(L); printf("The length of the frame is: %d n",ListLength(L)); if(OK==AddSumForChecking(&L)) { GetElem(L, ListLength(L), &e); printf("The checksum added is: %dn", e); printf("The length of the frame added checksum is: %d n",ListLength(L)); printf("The frame added checksum is: "); ListTraverse(L); } return 0; } |
第三题（5+10=15分）
| #include "stdio.h" #include "stdlib.h" #define OK 1 #define ERROR 0 #define MAXSIZE 20 typedef int Status; typedef int ElemType; typedef struct { ElemType data[MAXSIZE]; int length; }SqList; void ListTraverse(SqList L) { int i; for(i=0;i printf("%d ",L.data[i]); printf("n"); } int ListLength(SqList L) { return L.length; } Status GetElem(SqList L,int i,ElemType *e) { } Status ListInsert(SqList *L,int i,ElemType e) { int k; if (L->length>=MAXSIZE || i<0 || i>L->length) return ERROR; for(k=L->length-1;k>=i;k--) L->data[k+1]=L->data[k]; L->data[i]=e; L->length++; return OK; } void InterLeaving(SqList *L3, SqList L1, SqList L2) { } int main() { SqList L1, L2, L3; Status i; int j,k,l; printf("Please input the length of SqList1:n"); scanf("%d", &k); L1.length = 0; if (k > 0) printf("Please input the element of SqList1 one by one:n"); for(j=1;j<=k;j++) { scanf("%d", &l); i=ListInsert(&L1,0,l); } printf("The SqList1 is: "); ListTraverse(L1); printf("The length of SqList1 is: %d n",ListLength(L1)); printf("Please input the length of SqList2:n"); scanf("%d", &k); L2.length = 0; if (k > 0) printf("Please input the element of SqList2 one by one:n"); for(j=1;j<=k;j++) { scanf("%d", &l); i=ListInsert(&L2,0,l); } printf("The SqList2 is: "); ListTraverse(L2); printf("The length of SqList1 is: %d n",ListLength(L2)); L3.length = 0; InterLeaving(&L3, L1, L2); printf("The SqList3 of interleaving L1&2 is: "); ListTraverse(L3); printf("The length of SqList1 is: %d n",ListLength(L3)); return 0; } |
第四题（5+10=15分）
| #include #include #include #include struct Stack { int top; unsigned capacity; char* array; }; struct Stack* createStack(unsigned capacity) { struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack)); stack->capacity = capacity; stack->top = -1; stack->array = (char*) malloc(stack->capacity * sizeof(char)); return stack; } int isFull(struct Stack* stack) { int full = 0; full = (stack->top == (int)stack->capacity - 1)?1:0; return full; } int isEmpty(struct Stack* stack) { return stack->top == -1; } void push(struct Stack* stack, char item) {
} char pop(struct Stack* stack) { if (isEmpty(stack)) return CHAR_MIN; return stack->array[stack->top--]; } void reverseStr(char str[]) {
} int main() { char str[] = "ILoveChina, ILoveBJTU, ILoveGJCXSJXL"; printf("The given string %s has %d characters.n", str, strlen(str)); reverse(str); printf("Reversed string is %sn", str); return 0; } |
第五题（5+5+5=15分）
| 利用队列编写程序模拟计算机操作系统的分时任务调度。 结构体QElemType定义了队列中任务的各个数据元素，其中成员id为任务编号，cycle为任务需要消耗的CPU计算资源，rescycle记录任务完成还需要的CPU计算资源，wait统计任务完成总共等待的调度周期。 函数create_task（int id, QElemType *t）用于生成随机任务，参数id为任务id，t为新生成的任务。新生成任务的cycle及rescycle为[1,CYCLEMAX]之间的随机数，wait初始化为0。 已知计算机的CPU核数为N，则被调度任务（即出队列任务）的rescycle值将减少N，如果该任务的rescycle值仍大于0，则需要将该任务重新入队列等待下次调度，如果小于等于0，则该任务完成并将recycle赋值0。如图所示，假设CPU核数为4，程序初始化后开始。队列头成员a0出队列后，判断（recycle-4=3）仍大于0，a0重新入队列。每个调度周期需要更新队列中所有成员的wait值，即wait值加1变为1。 补全函数说明如下： （1）int EnQueue(LinkQueue *Q, QElemType t) 入队列基本操作。 （2）int ProcQueue(LinkQueue *Q, QElemType *t, int N) 取出队列元素将rescycle减 N，判断rescycle值是否大于0，如果大于0则将任务重新入队列，否则将recycle赋值为0。 （3）int QueueTraverse(LinkQueue *Q) 遍历队列中所有成员并将其wait值加1。 #include #include #define TASKMAX 10 #define CYCLEMAX 10 #define TASKINIT 5 #define OK 1 #define ERROR 0 typedef struct{ int id; // task id int cycle; // task complexity: cpu cycles int rescycle; // count residual cpu cycles int wait; // count the wait times to finish task }QElemType; typedef struct QNode { QElemType data; struct QNode *next; } QNode, *QueuePtr; typedef struct{ QueuePtr front; QueuePtr rear; int len; } LinkQueue; int create_task(int id, QElemType *t){ t->id=id; t->cycle=rand()%CYCLEMAX+1; t->rescycle=t->cycle; t->wait=0; return OK; } int InitQueue (LinkQueue *Q){ Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode)); if(!Q->front) return ERROR; Q->front->next=NULL; Q->len=0; return OK; } //InitQueue int EnQueue(LinkQueue *Q, QElemType t){ } int DeQueue(LinkQueue *Q, QElemType *t){ QueuePtr p; if(Q->front==Q->rear) return ERROR; p=Q->front->next; *t=p->data; Q->front->next=p->next; Q->len--; if(Q->rear==p) Q->rear=Q->front; free(p); return OK; } int ProcQueue(LinkQueue *Q, QElemType *t, int N){
} int QueueTraverse(LinkQueue *Q){
} int main(){ int i; int N; int taskid; QElemType t; LinkQueue Q; InitQueue(&Q); for(i=1; i<=TASKINIT; i++){ create_task(i, &t); EnQueue(&Q, t); } taskid=TASKINIT+1; printf("Please input the number of CPU cores of your computer: "); scanf("%d", &N); while(Q.front!=Q.rear){ ProcQueue(&Q,&t,N); if(t.rescycle==0) printf("task %4d with %4d cycles has finished and wait %4d schedule times.n", t.id, t.cycle, t.wait); QueueTraverse(&Q); if (taskid<=TASKMAX){ create_task(taskid, &t); EnQueue(&Q,t); taskid++; } } return 0; } |
#include第二题：链表的实际应用#include void InversePrint(int a[], int n) { if(n==0) return; printf("%d",a[n-1]); InversePrint(a,--n); } int main() { int i; int a[5]; for(i=0;i<5;i++){ scanf("%d", &a[i]); } InversePrint(a,5); }
其实链表一直是我个人认为的数据结构的一个难点，因为它要涉及到很多指针的运用，而且还是后面很多常用数据结构类型（栈、队列、树、图）存储结构的基础，因此把链表牢牢掌握非常重要。而掌握链表一定是要把指针完全掌握的，指针则又是C语言的一大难点，经常会发生野指针的情况，又难发现错误又容易犯这种错误。
#include "stdio.h"
#include "stdlib.h"
#define OK 1
#define ERROR 0
#define MAXSIZE 20
typedef int Status;
typedef int ElemType;
typedef struct Node
{
ElemType data;
struct Node *next;
}Node;
typedef struct Node *LinkList;
//==========================
//打印单链表
//==========================
void ListTraverse(LinkList L)
{
LinkList p=L->next;
while(p)
{
printf("%d ", p->data);
p=p->next;
}
printf("n");
}
//=======================================
//初始化单链表
//=======================================
Status InitList(LinkList *L)
{
*L = malloc(sizeof(Node));
(*L)->data = 0;
(*L)->next = NULL;
return OK;
}
int ListLength(LinkList L)
{
int i=0;
LinkList p=L->next;
while(p)
{
i++;
p=p->next;
}
return i;
}
Status GetElem(LinkList L, int i, ElemType *e)
{
LinkList pCurrent = L->next;
if(pCurrent == NULL)
return ERROR;
while(i>1){
pCurrent = pCurrent->next;
i--;
}
if(i==1)
*e = pCurrent->data;
return OK;
}
Status ListInsert(LinkList *L, int i, ElemType e)
{
int j;
LinkList p,s;
p = *L;
j = 1;
while (p && j < i)
{
p = p->next;
j=j+1;
}
if (!p || j > i)
return ERROR;
s = (LinkList)malloc(sizeof(Node));
if(!(s))
return ERROR;
s->data = e;
s->next = p->next;
p->next = s;
return OK;
}
//=========================================================
//求单链表所有元素的累加和，并将该累加和作为一个新的结点插在单链表的尾部
//=========================================================
Status AddSumForChecking(LinkList *L)
{
if(*L == NULL)
return ERROR;
if((*L)->next == NULL)
return ERROR;
int sum = 0;
LinkList pCurrent = (*L)->next;
LinkList pBefore = *L;
while(pCurrent != NULL){
sum += pCurrent->data;
pBefore = pBefore->next;
pCurrent = pCurrent->next;
}
LinkList newNode = malloc(sizeof(Node));
newNode->data = sum;
newNode->next = NULL;
pBefore->next = newNode;
return OK;
}
int main()
{
LinkList L;
ElemType e;
Status i;
int j,k,l;
i=InitList(&L);
if(i==ERROR)
{
return 0;
}
printf("Please input the length of frame:n");
scanf("%d", &k);
if (k > 0)
printf("Please input the element of frame one by one:n");
for(j=1;j<=k;j++)
{
scanf("%d", &l);
i=ListInsert(&L,1,l);
}
printf("The frame is: ");
ListTraverse(L);
printf("The length of the frame is: %d n",ListLength(L));
if(OK==AddSumForChecking(&L))
{
GetElem(L, ListLength(L), &e);
printf("The checksum added is: %dn", e);
printf("The length of the frame added checksum is: %d n",ListLength(L));
printf("The frame added checksum is: ");
ListTraverse(L);
}
return 0;
}
第三题：顺序表的交叉合并
这题比较好做，无非就是两个if判断的问题
#include "stdio.h"
#include "stdlib.h"
#define OK 1
#define ERROR 0
#define MAXSIZE 20
typedef int Status;
typedef int ElemType;
typedef struct
{
ElemType data[MAXSIZE];
int length;
}SqList;
void ListTraverse(SqList L)
{
int i;
for(i=0;i=L.length-1&&i<0)
return ERROR;
*e = L.data[i];
return OK;
}
Status ListInsert(SqList *L,int i,ElemType e)
{
int k;
if (L->length>=MAXSIZE || i<0 || i>L->length)
return ERROR;
for(k=L->length-1;k>=i;k--)
L->data[k+1]=L->data[k];
L->data[i]=e;
L->length++;
return OK;
}
void InterLeaving(SqList *L3, SqList L1, SqList L2)
{
int i = 0;
int n1 = 0;
int n2 = 0;
int add = L1.length + L2.length;
if(add == 0)
return;
while(add>0){
if(L1.length>0){
L3->data[i++] = L1.data[n1++];
L1.length --;
L3->length++;
}
if(L2.length>0){
L3->data[i++] = L2.data[n2++];
L2.length--;
L3->length++;
}
add = L1.length + L2.length;
}
return;
}
int main()
{
SqList L1, L2, L3;
Status i;
int j,k,l;
printf("Please input the length of SqList1:n");
scanf("%d", &k);
L1.length = 0;
if (k > 0)
printf("Please input the element of SqList1 one by one:n");
for(j=1;j<=k;j++)
{
scanf("%d", &l);
i=ListInsert(&L1,0,l);
}
printf("The SqList1 is: ");
ListTraverse(L1);
printf("The length of SqList1 is: %d n",ListLength(L1));
printf("Please input the length of SqList2:n");
scanf("%d", &k);
L2.length = 0;
if (k > 0)
printf("Please input the element of SqList2 one by one:n");
for(j=1;j<=k;j++)
{
scanf("%d", &l);
i=ListInsert(&L2,0,l);
}
printf("The SqList2 is: ");
ListTraverse(L2);
printf("The length of SqList1 is: %d n",ListLength(L2));
L3.length = 0;
InterLeaving(&L3, L1, L2);
printf("The SqList3 of interleaving L1&2 is: ");
ListTraverse(L3);
printf("The length of SqList1 is: %d n",ListLength(L3));
return 0;
}
第四题：利用栈对字符逆序输出
这一题和我都是老朋友了，早在PAT乙级题目里面就碰到过，当时用C++自带的vector容器很容易地实现了这一要求。这一题要求自己写出来一个栈并实现操作，也比较简单。
#include#include #include #include struct Stack { int top; unsigned capacity; char* array; }; struct Stack* createStack(unsigned capacity) { struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack)); stack->capacity = capacity; stack->top = -1; stack->array = (char*) malloc(stack->capacity * sizeof(char)); return stack; } int isFull(struct Stack* stack) { int full = 0; full = (stack->top == (int)stack->capacity - 1)?1:0; return full; } int isEmpty(struct Stack* stack) { return stack->top == -1; } void push(struct Stack* stack, char item) { if(!(item)) return; if(stack == NULL) return; stack->array[++stack->top] = item; return; } char pop(struct Stack* stack) { if (isEmpty(stack)) return CHAR_MIN; return stack->array[stack->top--]; } void reverseStr(char str[]) { int i = 0; struct Stack *myStack = createStack(strlen(str)); while(isFull(myStack)!=1){ push(myStack,str[i++]); } i = 0; while(isEmpty(myStack)!=1){ str[i++] = pop(myStack); } return; } int main() { char str[] = "ILoveChina, ILoveBJTU, ILoveGJCXSJXL"; printf("The given string %s has %d characters.n", str, strlen(str)); reverseStr(str); printf("Reversed string is %sn", str); return 0; }
