考研真题 常州大学858数据结构历年考研真题.docx
考研真题常州大学858数据结构历年考研真题
```c
//常州大学858数据结构历年考研真题示例
//2019年真题
//一、选择题（每题2分，共20分）
1.在单链表中，要删除指针P所指的结点，执行的操作是（）
A.pnext=pnextnext;
B.pnext=pnextnextnext;
C.p=pnext;
D.pnext=NULL;
2.下面关于栈的叙述中，正确的是（）
A.栈是一种先进先出的线性表
B.栈是一种先进后出的线性表
C.栈是一种可以随机访问的线性表
D.栈是一种有序的线性表
//二、填空题（每题3分，共30分）
3.在顺序存储结构中，数据元素之间的逻辑关系由______表示。
4.在双向链表中，每个结点包含两个指针，分别指向前一个结点和______。
5.设栈S的初始状态为空，元素a,b,c,d,e,f依次进栈，则栈的输出序列可能是______（至少给出两个可能的序列）。
//三、简答题（每题10分，共30分）
6.简述线性表、栈和队列之间的区别和联系。
7.请简要描述快速排序的基本思想和步骤。
8.请举例说明什么是二叉树的遍历，并写出前序遍历的算法实现。
//四、应用题（每题20分，共40分）
9.已知一个整数序列：{3,1,4,1,5,9,2,6,5,3,5}，请编写一个C语言程序，使用顺序栈实现该序列的逆序输出。
10.请编写一个C语言程序，实现一个带头结点的单链表的基本操作，包括创建链表、插入结点、删除结点、查找结点、输出链表。
//以下为单链表操作的部分代码实现：
includestdio.h
includestdlib.h
typedefstructNode{
intdata;
structNodenext;
}Node;
//创建链表
NodecreateList(intarr,intn){
Nodehead=(Node)malloc(sizeof(Node));
headnext=NULL;
Nodecurrent=head;
for(inti=0;in;i++){
NodenewNode=(Node)malloc(sizeof(Node));
newNodedata=arr[i];
newNodenext=NULL;
currentnext=newNode;
current=newNode;
}
returnhead;
}
//插入结点
voidinsertNode(Nodehead,intdata,intposition){
NodenewNode=(Node)malloc(sizeof(Node));
newNodedata=data;
newNodenext=NULL;
Nodecurrent=head;
for(inti=0;ipositioncurrentnext!=NULL;i++){
current=currentnext;
}
newNodenext=currentnext;
currentnext=newNode;
}
//删除结点
voiddeleteNode(Nodehead,intposition){
Nodecurrent=head;
Nodetemp=NULL;
for(inti=0;iposition1currentnext!=NULL;i++){
current=currentnext;
}
if(currentnext!=NULL){
temp=currentnext;
currentnext=tempnext;
free(temp);
}
}
//查找结点
NodesearchNode(Nodehead,intdata){
Nodecurrent=headnext;
while(current!=NULL){
if(currentdata==data){