复试专业课问题

• 1、数据结构：详细描述归并排序的过程

归并排序是用分治思想，分治模式在每一层递归上有三个步骤：

• 分解（Divide）：将n个元素分成个含n/2个元素的子序列。
• 解决（Conquer）：用合并排序法对两个子序列递归的排序。
• 合并（Combine）：合并两个已排序的子序列已得到排序结果。

1. 2、操作系统：什么是动态重定位，
2. 在程序运行过程中要访问数据时再进行逻辑地址与物理地址的变换（即在逐条指令执行时完成地址映射）

3、计算机网络：什么是子网掩码，请简述其原理及其应用。

子网掩码 (subnet mask) 又叫网络掩码、地址掩码、子网络遮罩，是一个应用于 TCP/IP 网络的 32 位二进制值。它可以屏蔽掉 IP 地址中的一部分，从而分离出 IP 地址中的网络部分与主机部分，基于子网掩码，管理员可以将网络进一步划分为若干子网。它必须结合 IP 地址一起使用。

在使用 TCP/IP 协议的两台计算机之间进行通信时，我们通过将本机的子网掩码与接受方主机的 IP 地址进行 ' 与 '运算，即可得到目标主机所在的网络号，又由于每台主机在配置 TCP/IP 协议时都设置了一个本机 IP 地址与子网掩码，所以可以知道本机所在的网络号。

通过比较这两个网络号，就可以知道接受方主机是否在本网络上。如果网络号相同，表明接受方在本网络上，那么可以通过相关的协议把数据包直接发送到目标主机；如果网络号不同，表明目标主机在远程网络上，那么数据包将会发送给本网络上的路由器，由路由器将数据包发送到其他网络，直至到达目的地。

4、

 ①从键盘上输入数字1-7，输出对应的日期。

#include <stdio.h>int main()
{int a;printf("Please input a single numeral(1-7): ");scanf("%d",&a);if (a==1)printf("Sunday\n");else if (a==2)printf("Monday\n");else if (a==3)printf("Tuesday\n");else if (a==4)printf("Wednesday\n");else if (a==5)printf("Thursday\n");else if (a==6)printf("Friday\n");else if (a==7)printf("Saturday\n");elseprintf("Invalid - please input a single numeral(1-7).\n");return 0;
}

②计算从100-500的所有素数个数以及其中所有素数之和。

#include<stdio.h>
int prime(int n) //定义函数判断素数
{
int i,flag=1;
for(i=2;i<n/2;i++)
if(n%i==0)flag=0;
if(flag==0)return 0;
else return 1;
}
void main() //主函数
{
int i,sum=0;
for(i=100;i<=500;i++)
if(prime(i)==1)sum+=i;
printf(">> sum=%d\n",sum);
}

 ③输出5*5矩阵中的最大值和最小值，以及其下标。

#include <stdio.h>void fun(int *p,int n)
{int *pmax,*pmin,*m;int t;pmax = pmin = m = p;	//四个指针均指向一维空间的起始单元//找最大数和最小数for(m=m+1;m<p+n;m++){if(*m > *pmax){pmax = m;}if(*m <	*pmin){pmin = m;}}//把最大数放到中心位置		t = *(p+2*5+2);*(p+12) = *pmax;*pmax = t;//把最小值放到左上角t = *p;*p = *pmin;*pmin = t;//找次小数pmin = p+1;m = p + 2;for(; m<p+n;m++){if(*m < *pmin){pmin = m;}}//把次小数置换到右上角t = *(p+4);*(p+4) = *pmin;*pmin = t;//找次次小数pmin = p+1;m = p+2;for(; m<p+n;m++){if( (*m<*pmin)&&(m!=(p+4)) ){pmin = m;}}//把次次小数置换到左下角	[4][0]——>4*5+0t = *(p+20);*(p+20) = *pmin;*pmin = t;//找出此次次次小数pmin = p+1;m = p+2;for(; m<p+n;m++){if( (*m<*pmin)&&(m!=(p+4))&&(m!=(p+20)) ){pmin = m;}}//把次次次小数置换到右下角	[4][4]——>24t = *(p+24);*(p+24) = *pmin;*pmin = t;
}	int main()
{int a[5][5],i,j;for(i=0;i<5;i++){for(j=0;j<5;j++){scanf("%d",&a[i][j]);}}fun(*a,25);for(i=0;i<5;i++){for(j=0;j<4;j++){printf("%d ",a[i][j]);}printf("%d",a[i][j]);printf("\n");}				return 0;
}						

 ④从输入的字符串中找出数字，并将其删除后输出。

#include<stdio.h>int dele(char x[]){int i = 0; int j = 0;while (x[i] != '\0'){                if (x[i] >= '0'&&x[i] <= '9')    //用ASCII判断x[]数组内容是否为数字i++;                        //只加i变量，相当于剔除当字符串某一字符为数字剔除下标else{x[j] = x[i]; i++; j++;}}x[j] = '\0';                        //末尾的下标是没\0的，需要加进去return x[j];
}int main()
{char str[100];            //char型数组存字符；int型数组存整形printf("Please input a sentence\n");//scanf("%s", str);        //遇到空格\t \n停止gets(str);                //遇到回车停止dele(str);printf("The new string is:%s\n", str);return 0;
}

 ⑤定义结构体 typedef struct { int sno; char name [10]; } 从键盘上输入学生信息，并将其写入文件“student.dat”中，输入学号为0时即停止输入。

#include <stdio.h>
#include <string.h>typedef struct {int sno;char name[10];
} Student;int main() {Student student;printf("请输入学生的学号和姓名（学号和姓名之间用空格隔开）：");scanf("%d %9s", &student.sno, student.name); // 使用%9s限制字符串长度为9，避免溢出printf("学号: %d, 姓名: %s\n", student.sno, student.name);return 0;
}

 ⑥递归方法写出直接插入排序。

public static void sort(int []arr,int k) {if(k==0) {					//递归的出口return;								//第一个元素不用去排序}sort(arr,k-1);					//对从0到倒数第二个元素排序int x=arr[k];					int index=k-1;						//设置指针while(index>-1&& x<arr[index]) {			//对最后一个元素进行插入arr[index+1]=arr[index];					//交换index--;}arr[index+1]=x;											//指针的边界}

5、

（1）关于链表的大题

①初始化带头结点的链表A

void initList(LinkList &L) {// 1、要给头指针分配一个存储空间，注意：一个单链表哪怕他是空的，他都必须有个头指针L = (LNode *)malloc(sizeof(LNode));// 2、此处是初始化带头结点的单链表，所以头指针L是指向头结点，而L->next的意思是头指针指向头结点的指针域，而头结点的指针域存储着下一节点的地址，所以给L->next赋值为null就表示头结点后面没有结点，单链表是空的L->next=NULL;
}

 ②构造有N个节点的非递减链表

//有序单链表
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct Node
{int data;struct Node *next;
};
//顺序插入
void Insert(Node *p,int n)
{//利用两个指针Node *p1=p;//指向头 ，因为这是有序单链表 所以每次插入前都得先从头来 Node *p2=p->next; //指向头节点之后 之后也用它来判断是否位只含有头节点的空链表 Node *s=(Node *)malloc(sizeof(Node));s->data=n;//写入数据while(p2&&p2->data>n){p1=p2;p2=p2->next;//这样同时往后移的话 插入的时候好插入	}s->next=p2;p1->next=s;//插入节点 
} //遍历列表void traversal(Node *p){Node *p3=p->next;//不能从p开始遍历因为p是头节点没存东西while(p3){printf("%d\n",p3->data);p3=p3->next;}} 
int main()
{Node *p;int i,j,k;p=(Node *)malloc(sizeof(Node));p->next=NULL;//创建头节点 for(i=0;i<3;i++){printf("Please input the number you want to insert");scanf("%d",&k);Insert(p,k);}traversal(p);return 0; 
}

③将链表A中不重复的数字复制到链表B中

#include <stdio.h>
#include <stdlib.h>typedef struct Node {int data;struct Node* next;
} Node, *LinkedList;// 创建一个新节点
Node* createNode(int data) {Node* newNode = (Node*)malloc(sizeof(Node));if (newNode == NULL) {printf("内存分配失败\n");exit(0);}newNode->data = data;newNode->next = NULL;return newNode;
}// 向链表中插入数据
void insertData(LinkedList* head, int data) {Node* newNode = createNode(data);if (*head == NULL) {*head = newNode;} else {Node* temp = *head;while (temp->next != NULL) {temp = temp->next;}temp->next = newNode;}
}// 打印链表
void printList(LinkedList head) {while (head != NULL) {printf("%d ", head->data);head = head->next;}printf("\n");
}// 将链表a中的不重复元素复制到链表b中
void copyUniqueToLinkedList(LinkedList a, LinkedList* b) {Node* currentA = a;Node* currentB = *b;while (currentA != NULL) {int isUnique = 1; // 假设是唯一的Node* tempA = a;while (tempA != currentA) {if (tempA->data == currentA->data) {isUnique = 0; // 发现重复break;}tempA = tempA->next;}if (isUnique) {Node* newNode = createNode(currentA->data);if (*b == NULL) {*b = newNode;} else {currentB->next = newNode;}currentB = newNode;}currentA = currentA->next;}
}int main() {LinkedList headA = NULL;LinkedList headB = NULL;// 示例数据insertData(&headA, 1);insertData(&headA, 2);insertData(&headA, 3);insertData(&headA, 2);insertData(&headA, 4);insertData(&headA, 1);printf("链表A: ");printList(headA);copyUniqueToLinkedList(headA, &headB);printf("链表B(不重复元素): ");printList(headB);return 0;
}

（2）关于双端队列的大题

 ①初始化队列

void Init(QUEUE *Q)
{(*Q).front = (struct celltype *)malloc(sizeof(struct celltype));(*Q).front->next=NULL; //创建一个空节点，并将其作为队列的头(*Q).rear = (*Q).front; //将尾指针指向头指针
}

②关于从队头队尾插入元素的问题

typedef struct Node {int data;struct Node* next;
} Node;
typedef struct LinkedList {Node* head;Node* tail;
} LinkedList;
void insert_to_head(LinkedList* list, int value) {Node* new_node = (Node*)malloc(sizeof(Node));new_node->data = value;new_node->next = list->head;list->head = new_node;if (list->tail == NULL) {list->tail = new_node;}
}void insert_to_tail(LinkedList* list, int value) {Node* new_node = (Node*)malloc(sizeof(Node));new_node->data = value;new_node->next = NULL;if (list->tail == NULL) {list->head = list->tail = new_node;} else {list->tail->next = new_node;list->tail = new_node;}
}
void print_list(LinkedList* list) {Node* current = list->head;while (current != NULL) {printf("%d ", current->data);current = current->next;}printf("\n");
}
int main() {LinkedList list;list.head = list.tail = NULL;insert_to_head(&list, 1);insert_to_tail(&list, 2);insert_to_head(&list, 3);insert_to_tail(&list, 4);print_list(&list); // 输出: 3 1 2 4return 0;
}

 ③关于从队头队尾删除元素的问题

#include <stdio.h>
#include <stdlib.h>typedef struct Node {int data;struct Node *next;
} Node;typedef struct Queue {Node *front;Node *rear;
} Queue;// 初始化队列
void init(Queue *q) {q->front = NULL;q->rear = NULL;
}// 在队尾插入元素
void enqueue(Queue *q, int data) {Node *newNode = (Node *)malloc(sizeof(Node));newNode->data = data;newNode->next = NULL;if (q->rear == NULL) {q->front = q->rear = newNode;} else {q->rear->next = newNode;q->rear = newNode;}
}// 从队头删除元素
void dequeueFromFront(Queue *q) {if (q->front == NULL) {printf("Queue is empty\n");return;}Node *temp = q->front;q->front = q->front->next;free(temp);if (q->front == NULL) {q->rear = NULL;}
}// 从队尾删除元素
void dequeueFromRear(Queue *q) {if (q->front == NULL) {printf("Queue is empty\n");return;}Node *current = q->front;if (current->next == NULL) {free(current);q->front = q->rear = NULL;} else {while (current->next != q->rear) {current = current->next;}free(q->rear);q->rear = current;q->rear->next = NULL;}
}int main() {Queue q;init(&q);// 添加元素enqueue(&q, 10);enqueue(&q, 20);enqueue(&q, 30);// 从队头删除元素dequeueFromFront(&q);// 从队尾删除元素dequeueFromRear(&q);return 0;
}