本科数据结构算法题整理

  |  

参考资料:厦门大学本科计算机历年卷

2012年本科期末B卷

第7题 拆分链表

题目:

有一个带头结点的单链表L={a1, b1, a2, b2, …, an, bn},指针变量L指向头结点。请设计一个函数将其拆分成两个带头结点的单链表A和B,正序链表A={a1, a2, …, an},逆序链表B={bn, bn-1, …, b2, b1}。要求链表A使用链表L的头结点。

注:函数的头部为void split(LinkList &L, LinkList &A, LinkList &B )。

1
2
3
4
5
6
7
8
9
10
11
void split(LinkList &L, LinkList &A, LinkList &B )
{ LinkList * p=L->next, *q;
B = (LinkList ) malloc( sizeof(LinkList) ); //创建B的头结点
B->next = NULL;
while( p!=NULL ) {
q = p->next; assert( q!=NULL);
p->next = q->next; p = p->next;
q->next = B->next; B->next = q->next;
}
A =L; L=NULL;
}

第8题 求子序列和最大

题目:

给出一系列整数,请设计算法求出总和最大的子系列,要求算法的时间复杂性在O(n)之内。

1
2
3
4
5
6
7
8
9
10
11
int maxsubsum(int  a[n])
{
int maxsum=0; thissum=0; int j=0;
for (j=0; j<n;j++)
{
thissum=thissum+a[j];
if (thissum>maxsum) maxsum=thissum;
else if (thissum<0) thissum=0;
}
return maxsum;
}

2012年本科期末A卷

第8题 删除有序单链表重复元素结点

题目:

有一个单链表,其结点的元素值以递增顺序排列,给出数据结构,并编写一个算法删除该单链表中元素值相同的结点。

**算法1:**从头到尾扫描单链表,若当前结点与后继结点的值不相同,则指针后移,若相同则删除该后继结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*链表结构体,必背*/
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
//带头结点

Status Del_Dup(LinkList &L)
{
p=L->next; //p指向第一个元素
if (p ==NULL) return; // 处理空表
while (p->next!=NULL) {
if(p->data!=p ->next->data) //若当前结点与后继结点的值不相同,则指针后移
p=p->next;
else{ //若当前结点与后继结点的值相同,则删除该后继结点
q=p->next;
p->next=q->next;
free(q);
}
}
}

**算法2:**使用两个指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*结构体定义同上*/

Status Del_Dup(LinkList &L)
{
if (L->next ==NULL) return; // 处理空表
f=L->next; p=f->next; //在扫描过程中,f保持为p的前驱
while (p) {
if(f->data!=p ->data){ //若当前结点与后继结点的值不相同,则指针后移
f=p;
p=p->next;
}
else{ //若当前结点与后继结点的值相同,则删除该后继结点
q=p;
f->next=p->next;
free(q);
p=p->next;
}
}
}

第9题 求第k大元素

题目:

在n个元素中,找出第k大的元素,给出数据结构,并设计算法实现上述要求,并给出时间复杂性分析,最好是在O(n)的时间复杂性之内。

1
2
3
4
5
6
7
8
9
10
static ITEM_select(ITEM [] a, int l, int r, int k) //l是下标最小值,r是下标最大值
{
while(r>l) {
int i = partition(a, l ,r); //partition后,比a[i]小的都在i左边,
//比a[i]大的都在 i右边。
if(i==k) return a[k];
if(i<k) r=i-1; //从l到i-1做selection
if(i>k) l=i+1; //从i+1到r做selection
}
}

分析:

对于足够大的随机数组,每次partition会把数组分成大约相等的两半,那么每次问题size缩小一般,比较次数为n+n/2+n/ 4+…+1=2n。因此为O(n)。

注意select和quicksort不同,因为quicksort每次都要比较N,而select的比较次数是指数减少的,因此是O(n)而不是O(nlogn)

2011年本科期末B卷

第1题 部门数据结构表示

请根据下面的描述写出销售部门的数据结构(用C语言):假设一个销售部门有n个职员(最多不超过N个,N为100),其中有一个是销售经理。每个职员都各自有一些客户,客户的个数不固定,不同职员的客户不重叠。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#define N 100
typedef struct CustNode {
Customer cust;
struct CustNode * next;
} CustNode, * CustLink;

typedef struct {
Saleman sm;
CustLink firstcust; //指向第一个销售员
} SalemanNode;

typedef struct SaleDept {
SalemanNode saleman[N];
int n; //销售员的人数
int manager; //销售经理在数组saleman[N]中的序号
} SaleDept;

第6题 两个有序表中共同元素的问题

在两个有序线性表中,寻找是否存在共同元素。如果存在共同元素,返回第一个共同元素在第一个有序表中的位置。请设计数据结构,并在其上设计算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
可以参考有序表的归并算法。
数据结构可以使用一维数组,并且第0个元素放空。
int SearchCommonItem(int a[n], int b[m])//第0位放空,返回值为0代表找不到
{
int i=1,j=1;
while (i<=n && j<=n)
{
if (a[i]==b[j]) return i;
else (a[i]<b[j]) i++;
else j++;
}
return 0;
}

分析:自己设计的时候容易忘记考虑没找到的情况结果该如何表示


第7题 遍历二叉查找树

编写一个遍历二叉查找树T的算法,要求遍历过程恰好按结点键值从大到小的次序进行。二叉树T数据结构采用二叉链表。

1
2
3
4
5
6
7
void travel(bitree bt)
{
if(bt){
travel(bt.rchild);
visit(bt.data);
travel(bt.lchild);
}

第8题 链表重组,奇前偶后

一个正整数序列存放在带头结点的链表L中,每个结点存放一个正整数。请编写算法将该链表调整为所有奇数在链表的前部分,所有偶数在链表的后部分,并且调整后的奇数序列和偶数序列都与它们在原来序列中的次序一致(例如:原序列1 2 3 4 5 6,调整后 1 3 5 2 4 6)。要求:除算法外,还要给出数据结构、算法思想和代码注释。

数据结构:

1
2
3
4
5
//链表数据结构
typedef struct Node {
int data;
struct Node * next;
}*List;

**法一:**链表r保存倒序的奇数序列,然后逆序插入链表L的头部。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void OddEven( List &L)
{ struct Node *p, *q, *r;
p = L; r = NULL; //r是不带头结点的链表
while( p->next!=NULL )
if( p->next->data%2==0 ) p = p->next;//如果是偶数,不管
else {
q = p->next; //把结点从链表L中移走
p->next = q->next; //把结点从链表L中移走
q->next = r; //加入到链表r中
r = q; //加入到链表r中
}
while( r!=NULL ) { //链表r逆序插入链表L的头部
q = r;r = r->next;
q->next = L->next;L->next = q;
}
}

**法二:**顺序扫描链表直到表尾,每找到一个奇数时将其从原来位置删除,然后插入到奇数部分的表尾辅助指针ot(初始指向虚设的头结点)之后,并更新ot指针令其指向该新插入结点

1
2
3
4
5
6
7
8
9
10
11
12
13
void OddEven( List &L)
{ struct Node *p, *q, *ot;
p = L; ot = L;
while( p->next!=NULL )
if( p->next->data%2==0 ) p = p->next;//如果是偶数,不管
else if (p!=ot)
{ q = p->next; //把结点从链表L中移走
p->next = q->next; //把结点从链表L中移走
q->next = ot->nextr; //到链表ot之后
ot->next=q; //到链表ot之后
ot = q;
}
}

2011年本科期末A卷

第8题 树的双亲表示下求公共祖先结点

假设一棵树的存储结构采用双亲表示法,双亲数组为int parent[MaxSize],其中MaxSize为最大结点个数。树中各结点按先根遍历的次序存放,根结点存于parent[0]。试编写一个函数,计算下标p所指结点和下标q所指结点的最近公共祖先结点。

1
2
3
4
5
6
int CommonAncestry(int parent[], int MaxSize, int p, int q){
int i,j;
for (i=p; i!=-1;i=parent[i])
for (j=q; j!=-1; j=parent[j])
if (i==j) return I;
}

第9题 n个正整数在n容量数组中的排序

1,2,……,n这n个数,无序地保存在数组c[1…n]中。请编写一个时间复杂度为O(n)的排序算法,将数组c[1…n]按小到大排序。

1
2
3
4
5
6
7
8
9
10
void C_sort(int c[], int n)
{
int i, x;
for (i=1;i<=n;i++)
while (c[i]!=i){
x=c[i];
c[i]=c[x];
c[x]=x;
}
}

2010年本科期末B卷

第7题 链表最小值移动到链头

在带头结点的非空线性链表中,试设计一算法,将链表中数据域值最小的那个结点移到链表的最前面,其余各结点的顺序保持不变。要求:不得额外申请新的链结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
typedef struct node {
int data;
struct node * next;
}Node,*LinkList;
void MinFirst(LinkList L){
Node *p,*q,*ptrmin;
if(L->next == NULL) return; //空表
ptrmin = L; //ptrmin指向当前最小结点的前一个结点
p = L->next;//p指向当前结点的前一个结点
while(p->next!=NULL) {
if( p->next->data < ptrmin->next->data ) ptrmin = p;
p = p->next;
}
//q指向最小结点,并从链表中删除
q = ptrmin->next; ptrmin->next = q->next;
q->next = L->next; L->next = q; //q指向的最小结点插入到链表头
}

第8题 用两个队列模拟一个栈

请利用两个队列Q1和Q2来模拟一个栈。已知队列的三个运算定义如下:bool EnQueue(Queue &Q,int e):插入一个元素e入队列; bool DeQueue(Queue &Q,int &e):删除一个元素e出队列;bool QueueEmpty(Queue Q):判队列为空。假设数据结构Queue已定义,栈Stack的数据结构定义如下。请利用队列的运算来实现该栈的三个运算:Push(Stack ST,int x):元素x入ST栈;Pop(Stack ST, int x):ST栈顶元素出栈,赋给变量x;StackEmpty(Stack ST):判ST栈是否为空。

typedef struct {

Queue Q1;

Queue Q2;

} Stack;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/*队列Q1或Q2中的某一个保存所有的栈元素。*/
//判断栈是否为空
bool StackEmpty(Stack S)
{
return QueueEmpty(S.Q1) && QueueEmpty(S.Q2);//两队列都为空,即栈为空
}

//x入栈
bool Push(Stack &S, int e)
{
if( QueueEmpty(S.Q2)==false )
return EnQueue(S.Q2, e);
return EnQueue(S.Q1, e);
}

//出栈并赋值给x
bool Pop( Stack &S, int &e) {
Queue *from,*to;
int x;
if( QueueEmpty(S.Q1)==true && QueueEmpty(S.Q2)==true ) return false;
if( QueueEmpty(S.Q1)==false ) {
from = &S.Q1; to = &S.Q2;
}
else {
from = &S.Q2; to = &S.Q1;
}

/*假设Q1非空,把Q1的元素依次出队,再赋给Q2,直到Q1为空,把最后出队的x赋给e*/
DeQueue(*from,x);
while( QueueEmpty(*from)==false ) {
EnQueue(*to,x);
DeQueue(*from,x);
}
e = x;
return true;
}

2010年本科期末A卷

第7题 有序单链表插入元素

设L是一个带头结点的非递减有序单链表的表头指针,试设计一个算法,将元素e插入到链表L中的合适地方,使得该链表仍是非递减有序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef struct Node {
ElemType e;
struct Node * next;
} Node, *LinkList;

void Insert( LinkList &L, ElemType e){
Node * p, *q, *s;
p = L->next; q = L;
while ( p!=NULL && p->data <= e ) {
q = p; p = p->next;
}
s = (Node *) malloc( sizeof(Node) );
s->data = e;
s->next = p;
q->next = s;
}

我的答案(算法部分):

1
2
3
4
5
6
7
8
9
10
11
12
13
void Insert( LinkList &L, ElemType e){
Node * p, *q;
p=L;
if(L->next==NULL) return;
while ( p!=NULL) {
if(p->data < e && p->next->data >= e){
q=(Node*)malloc(sizeof(Node));
q->data=e;
q->next=p->next;
p=>next=q;
}
else p=p->next;
}

2009年本科期末B卷

第7题 孩子兄弟链表求树深度

用孩子兄弟链表作为树的存储结构,设计算法求出树的深度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
typedef struct CSNode{
ElemType data;
struct CSNode *firstchild, * nextsibling;
} CSNode, *CSTree;

int depth(CSNode * t)
{
CSNode *p; int m, d;
if (t==NULL) return 0;
p=tfirstchild; m=0;
while (p) {
d=depth(p);
if (d>m) m=d;
p=pnextsibling;
}
return m+1;
}

算法思路:一棵树的深度可以递归定义为:若树为空,则深度为0,否则树的深度为根结点的所有子树深度的最大值加1。

文章目录
  1. 2012年本科期末B卷
    1. 第7题 拆分链表
    2. 第8题 求子序列和最大
  2. 2012年本科期末A卷
    1. 第8题 删除有序单链表重复元素结点
    2. 第9题 求第k大元素
  3. 2011年本科期末B卷
    1. 第1题 部门数据结构表示
    2. 第6题 两个有序表中共同元素的问题
    3. 第7题 遍历二叉查找树
    4. 第8题 链表重组,奇前偶后
  4. 2011年本科期末A卷
    1. 第8题 树的双亲表示下求公共祖先结点
    2. 第9题 n个正整数在n容量数组中的排序
  5. 2010年本科期末B卷
    1. 第7题 链表最小值移动到链头
    2. 第8题 用两个队列模拟一个栈
  6. 2010年本科期末A卷
    1. 第7题 有序单链表插入元素
  7. 2009年本科期末B卷
    1. 第7题 孩子兄弟链表求树深度
本站总访问量 | 本页面被访问 | 本站访客数
载入天数...载入时分秒...