1. 什么是数据结构？有关数据结构的讨论涉及哪三个方面？
答：
（1）数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成.
（2）逻辑结构、存储结构以及运算结构。
2. 什么是算法？算法的特性有哪些？根据这些特性，解释算法与程序的区别？
答：
（1）算法是一组明确指定的简单指令集，即有限的指令序列，用来解决一个问题。
（2）输入：由外部提供的量作为算法的输入。
输出：算法产生至少一个量作为输出。
确定性：组成算法的每条指令是清晰，无歧义的。
有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。
可行性：算法中所有的操作都必须足够基本，使算法的执行者或阅读者明确其含义以及如何执行。
（3）a.算法必须满足有穷性，而程序不一定满足有穷性，比如Windows操作系统在用户没有退出、硬件不出现故障以及有电的条件下理论上可以无限时运行。
b. 算法是解决问题的步骤；程序是算法的代码实现。
c. 算法对于特定的输入有特定的输出，程序提供了确定算法结果的平台。
d. 算法需要考虑设计的可能，程序则具体是实现算法上的设计。
3. 请分析以下程序的时间复杂度。
（1）程序1：
void Matmpy( int n )
{
int i, j, k;
for (i = 0; i <= n-1; i ++ )
for (j = 0; j <= n-1; j ++ ){
C[i][j] = 0;
for (k = 0; k <= n-1; k ++ )
C[i][j] = C[i][j] + A[i][k] * B[k][j];
}
}
时间复杂度为O（n^3）
（2）程序2：
void Mystery( int n )
{
int i, j, k;
for (i = 1; i < n; i ++ )
for (j = i + 1; j <= n; j ++ )
for (k = 1; k <= j; k ++ ){
/ * some statement requiring O(1) time * /
}
}
时间复杂度为O（n^3）
（3）程序3：
void Podd( int n )
{
int i, j, x, y;
for (i = 1; i <= n; j ++ )
if (odd(i)){
for (j = i; j <= n; j ++ )
x = x + 1;
for (j = 1; j <= i; j ++ )
y = y + 1;
}
}
时间复杂度为O（n^2）
4. 请设计与实现一个求最大公因数的算法。附可实现的代码。
#include<stdio.h>
int main()
{
int m,n,r;
scanf("%d",&m);
scanf("%d",&n);
if(n>m)
{
r=n;
n=m;
m=r;
}
r=m%n;
while(r!=0)
{
m=n;
n=r;
r=m%n;
}
printf("最大公因数位：%d",n);
return 0;
}
5、线性表可用顺序存储结构或链式存储结构。那么，（1）两种存储表示各有哪些主要优缺点？（2）如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变，在此情况下，应选用哪种存储表示？为什么？（3）若表的总数基本稳定，并且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时，应采用哪种存储表示？为什么？
答：
（1）
顺序存储结构优点：
a.逻辑结构与存储结构一一对应，无须为表示表中元素之间的逻辑关系而增加额外的存储空间。
b.可以快速地存取表中任一位置的元素。
顺序存储结构缺点：
a.插入或删除元素时不方便，需要移动大量元素。
b.长度需要预先去规定，当线性表长度变化较大时，难以确定存储空间的容量。
c.造成存储空间的碎片。
链式存储结构优点：
a.插入或删除元素时很方便，使用灵活。
b.长度就是精确的长度，需要多少结点就开辟多少空间。
链式存储结构缺点：
a.需要占用额外的空间去存放指针，存储空间利用率不高。
b.不可以随机访问。
（2）选择链式存储结构，因为链表结构使用更加灵活，需要多少长度就新建多少结点。
（3）选择顺序存储结构，因为顺序存储结构的元素逻辑结构和存储结构一一对应，可以随机存取；而链表中元素的逻辑关系是通过指针表示，一个接一个的指向下一个，所以需要从第一个开始，并不是随机存取，效率较低。所以选择顺序存储结构。
6、分别对顺序表和单链表，完成以下操作（函数）：
（1）插入操作（函数）insert；
（2）删除操作（函数）delete；
（3）返回某元素位置操作（函数）locate；
（4）统计给定值x的所有元素操作（函数）number；
答：
顺序表：
#include<stdio.h>
#include<stdlib.h>
#define Maxsize 100
typedef struct{
int data[Maxsize];
int length;
}List;
void initList(List &L)
{
L.length=0;
}
void insertList(List &L,int i,int e)
{
if(L.length>=Maxsize-1)
printf("FULL");
else if(i<1||i>=L.length)
printf("Location does not exist！");
if(i>=1&&i<=L.length-1)
{
for(int j=L.length;j>=i;j--)
{
L.data[j]=L.data[j-1];
}
L.data[i-1]=e;
L.length++;
}
}
void deletList(List &L,int i)
{
if(L.length>=Maxsize-1)
printf("FULL");
else if(i<1||i>=L.length)
printf("Location does not exist！");
if(i>=1&&i<=L.length-1)
{
for(int j=i-1;j<L.length;j++)
{
L.data[j]=L.data[j+1];
}
L.length--;
}
}
int locateList(List &L,int x)
{
int num;
for(int i=0;i<L.length;i++)
{
if(L.data[i]==x)
{
num=i+1;
return num;
}
}
return -1;
}
int numberList(List &L,int x)
{
int num=0;
for(int i=0;i<L.length;i++)
{
if(L.data[i]==x)
num++;
}
return num;
}
void displayList(List L)
{
int i;
for(i=0;i<L.length;i++)
{
printf("%d ",L.data[i]);
}
printf("\n");
}
int main()
{
int s,num;
List L;
initList(L);
for(int i=0;i<=5;i++)
{
L.data[i]=i+1;
L.length++;
}
printf("The original sequence table is:");
displayList(L);
printf("The inserted list is:");
insertList(L,3,5);
displayList(L);
printf("The list after deleting the element at position 4 is:");
deletList(L,4);
displayList(L);
s=locateList(L,1);
printf("The position of element 1 is:%d\n",s);
num=numberList(L,5);
printf("The number of elements with a value of 5 is:%d\n",num);
return 0;
}
单链表：
#include<stdio.h>
#include<stdlib.h>
typedef struct Link{
int elem;
struct Link *next;
}link;
link * initLink()
{
link * p=(link*)malloc(sizeof(link));
link * temp=p;
for (int i=1; i<7; i++)
{
link *a=(link*)malloc(sizeof(link));
a->elem=i;
a->next=NULL;
temp->next=a;
temp=temp->next;
}
return p;
}
link * insertElem(link * p,int elem,int add)
{
link * temp=p;
for (int i=1; i<add; i++)
{
if (temp==NULL) {
printf("error\n");
return p;
}
temp=temp->next;
}
link * c=(link*)malloc(sizeof(link));
c->elem=elem;
c->next=temp->next;
temp->next=c;
return p;
}
link * deletElem(link * p,int add)
{
link * temp=p;
for (int i=1; i<add; i++)
{
if (temp==NULL) {
printf("error\n");
return p;
}
temp=temp->next;
}
temp->next=temp->next->next;
return p;
}
int selectElem(Link* p, int elem)
{
int i = 1;
link* temp=p;
temp = temp->next;
while (temp)
{
if (temp->elem == elem)
{
return i;
}
temp = temp->next;
i++;
}
return -1;
}
int numberElem(Link* p, int elem)
{
int i = 0;
link* temp=p;
temp = temp->next;
while (temp)
{
if (temp->elem == elem)
{
i++;
}
temp = temp->next;
}
return i;
}
void display(link *p)
{
link* temp=p;
while (temp->next)
{
temp=temp->next;
printf("%d ",temp->elem);
}
printf("\n");
}
int main() {
printf("The initialization linked list is:\n");
link *p=initLink();
display(p);
printf("The linked list after the element is inserted at the third position is:\n");
p=insertElem(p, 5, 3);
display(p);
printf("The element list after deleting the fourth position is:\n");
p=deletElem(p, 4);
display(p);
printf("element 4 location of：%d\n",selectElem(p, 4));
printf("The number of element values of 2 is：%d\n",numberElem(p, 5));
return 0;
}
7、 写一个交换单向链表中位置P和Next(P)的元素的算法。
#include<stdio.h>
#include<stdlib.h>
typedef struct Link{
int elem;
struct Link *next;
}link;
link * initLink()
{
link * p=(link*)malloc(sizeof(link));
link * temp=p;
for (int i=1; i<10; i++)
{
link *a=(link*)malloc(sizeof(link));
a->elem=i;
a->next=NULL;
temp->next=a;
temp=temp->next;
}
return p;
}
Link *swapLink(link * p,int x)
{
link *pTemp=(link*)malloc(sizeof(link));
link * temp=p;
for (int i=1; i<x; i=i+1)
{
if (temp==NULL) {
printf("error\n");
return p;
}
temp=temp->next;
}
if(temp==NULL)
{
printf("Error: the exchanged location does not exist. The original linked list is\n");
}
else
{
pTemp = temp->next;
temp->next = pTemp->next;
pTemp->next = pTemp->next->next;
temp->next->next = pTemp;
}
return p;
}
void display(link *p)
{
link* temp=p;
while (temp->next)
{
temp=temp->next;
printf("%d ",temp->elem);
}
printf("\n");
}
int main() {
printf("The initialization linked list is:\n");
link *p=initLink();
display(p);
printf("The linked list after position exchange is:\n");
swapLink(p,3);
display(p);
return 0;
}
8、 铁路进行列车调度时，常把站台设计成栈式结构的站台，如图所示。试问：
(1)设有编号为1,2,3,4,5,6的6辆列车，顺序开入栈式结构的站台，则可能的出栈序列有多少种？
(2)若进站的6辆列车顺序如上述所示，那么是否能够得到435612，325641，154623和135426的出站序列，如果不能，说明为什么不能；如果能，说明如何得到（即写出“进栈”或“出栈”的序列）。
答：
（1）可能的出栈序列有132种。
（2）不能得到435612，154623。对于435612，在4356出栈之后，栈内仅剩12两个元素，其中1先入栈，在栈底，2后入栈，在栈顶，由于后进先出原则应该是2先出栈即435621。对于154623，1546元素出栈后，仅剩23两个元素，2先入栈，在栈底，3后入栈，在栈顶，由于后进先出原则应该是3先出栈即154632。手绘说明图如下
9、写出以下中缀表达式的后缀表达式:
(1) A×B×C
(2) –A+B-C+D
(3) (A+B) ×D+E/(F+A×D)+C
(4) A×B–C/B^2
答：
（1）AB*C*
（2）A-B+C-D+
（3）AB+D*EFAD*+/+C+
（4）AB*CB2^/-
10、（1）实现数据存放循环队列。以front和rear为队列的队首队尾。（2）实现入队和出队元素的操作。（3）基于循坏队列实现约瑟夫环问题。（请附上可执行的代码）
(1)(2)代码
#include<stdio.h>
#define Maxsize 5
typedef struct{
int data[Maxsize];
int front;
int rear;
}Queue;
void initQueue(Queue &Q)
{
Q.front=0;
Q.rear =0;
}
void EnQueue(Queue &Q,int x)
{
if((Q.rear+1)%Maxsize==Q.front)
printf("The queue is full");
else
{
Q.data[Q.rear]=x;
Q.rear=(Q.rear+1)%Maxsize;
}
}
void DeQueue(Queue &Q)
{
if(Q.rear==Q.front)
printf("The queue is empty");
else
Q.front=(Q.front+1)%Maxsize;
}
void displayQueue(Queue Q)
{
int i = Q.front;
while(i != Q.rear)
{
printf("%d ",Q.data[i]);
i = (i+1)%Maxsize;
}
printf("\n");
}
int main()
{
int i,d;
Queue Q;
initQueue(Q);
for(i=0;i<Maxsize-1;i++)
{
printf("Please enter the value of the element you want to join:\n");
scanf("%d",&d);
EnQueue(Q,d);
}
printf("The queue after the element is queued is:\n");
displayQueue(Q);
printf("The queue after the exit is:\n");
DeQueue(Q);
displayQueue(Q);
return 0;
}
(3) 实现约瑟夫环代码
#include<stdio.h>
#define Maxsize 50
typedef struct
{
int data[Maxsize];
int front;
int rear;
}Queue;
void InitQueue(Queue* &Q)
{
Q=new Queue;
Q->front=-1;
Q->rear=-1;
}
int QueueEmpty(Queue *Q)
{
if(Q->front==Q->rear)
return 1;
else
return 0;
}
int enQueue(Queue* &Q,int e)
{
Q->rear=(Q->rear+1)%Maxsize;
if(Q->rear==Q->front)
return 0;
Q->data[Q->rear]=e;
return 1;
}
int deQueue(Queue* &Q,int &e)
{
if(Q->front==Q->rear)
return 0;
else
{
Q->front=(Q->front+1)%Maxsize;
e=Q->data[Q->front];
return 1;
}
}
void yuesefuhuan(Queue* &Q,int a[],int m)
{
int i=0,j=0;
int e;
while(!QueueEmpty(Q))
{
i++;
deQueue(Q,e);
if(i==m)
{
a[j]=e;
i=0,j++;
}
else
{
enQueue(Q,e);
}
}
}
void displayQueue(int a[],int n)
{
int i;
for(i=0;i<n;++i)
{
printf("%d ",a[i]);
}
}
int main()
{
int n,m;
Queue *Q;
InitQueue(Q);
printf("Please enter how many people:\n");
scanf("%d",&n);
printf("Please enter the value of m:\n") ;
scanf("%d",&m);
int a[n];
for(int k=0;k<n;++k)
{
a[k]=k+1;
enQueue(Q,a[k]);
}
printf("Then the order of their leaving the team is:\n");
yuesefuhuan(Q,a,m);
displayQueue(a,n);
}