既然五一假期出不去，那就好好准备各科的期中考试吧～
期中考试要加油鸭！
本试卷为2020级数据结构与程序设计期中考试试卷真题。
选择填空题共10道，每道0.5分。 第一道编程题15分，第二道编程题10分。 共30分。
注意：填空题答案中不得有空格，选择题答案只填大写或小写字母，不得有括号等其它字符！
选择题 （总分：4.50）
若线性表最常用的运算是存取第i个元素及其前驱的值，则采用__________存储方式节省时间。
A．单链表 B．双链表 C．顺序表 D．循环单链表
正确答案: c
设p指针指向单链表（单链表长度为n）中的某个结点（p≠NULL）,若只知道指向该单链表第一个结点的指针和p指针，则在p指针所指结点之前和p指针所指结点之后插入一个结点的时间复杂度分别是__________。
A. O(1)和O(n) B. O(1)和O(1) C. O(n)和O(n) D. O(n)和O(1)
正确答案: d
下列语句中，能正确进行字符串赋值的是__________。
A. char s[10]; s=“BUAA”; B. char* sp; *sp=“BUAA” ;
C. char *sp=“BUAA”; D. char s[10]; *s=“BUAA”;
正确答案: C
设有以下说明语句：
struct strutype
{
int a;
float b;
}var;
则下面叙述中错误的是__________
(A) struct是结构类型的关键字
(B) struct strutype是用户定义的结构类型
? var是用户定义的结构类型名
(D) a和b都是结构成员名
正确答案: c
若有以下说明和语句:
struct student
{
int age;
int num;
}std, *p;
p = &std;
则以下对结构变量 std 中成员 age 的引用方式不正确的是__________
A. std.age
B. p->age
C. (*p).age
D. *p.age
正确答案: d
若有语句 int *point,a=4; 和 point=&a; 下面均代表地址的一组选项是__________
A. a , point , *&a ；
B. &(*a) , &a , *point ；
C. *(&point) , *point , &a ；
D. &a , &(*point) , point ；
正确答案: D
设某一非空的单循环链表的头指针（指向第一个结点的指针）为Head，尾指针（指向最后一个结点的指针）为Rear，则下列条件判断结果一定为真的是__________。
A. Head== Rear->link B. Head== Rear->link->link
C. Rear== Head->link D. Rear== Head->link->link
正确答案: A
若要删除非空线性链表中由p所指的链结点的直接后继链结点（由p->link指向），则需依次执行__________。
A．r=p->link; p->link=r; free?;
B．r=p->link; p->link=r->link; free?;
C．r=p->link; p->link=r->link; free§;
D．p->link=p->link->link; free§;
正确答案: b
顺序存储表示中数据元素之间的逻辑关系是由__________表示的，链式存储表示中数据元素之间的逻辑关系是由__________表示的。
A．指针 B．逻辑顺序 C．存储位置 D．问题上下文
正确答案: c | a
填空题 （总分：0.50）
若有函数定义为：
int func(int n)
{
if(n<=1)
return 1;
else
return (2+n*func(n-1));
}
假设m为int类型，则执行语句：m=func(5);后，m的值为：__________
正确答案: 292
编程题（总分：25.00）
- 标 识 符 的 识 别 （分值：15.00）
【问题描述】
从控制台读入一行符合C语言语法要求的语句，该语句以分号结束。编写程序抽取出语句中的标识符，重复的标识符只保留一个，然后按照字典序由大到小的顺序输出这些标识符。
规定：
1）读入的语句中字符个数不超过200，每个标识符的字符个数不超过32，语句中标识符的个数不超过50个，且至少有一个标识符。
2）读入的语句中不会出现字符常量、字符串常量，也没有注释。
3）读入的语句中不会出现带后缀的常量类型：例如：2.5f、15l、18L、106ll、5u等情况。
【输入形式】
从控制台输入一行符合C语言语法要求的语句，语句以英文分号结束，末尾有回车符。
【输出形式】
按照字典序由大到小的顺序输出抽取出的标识符，各标识符间以一个空格分隔，最后一个标识符后有无空格均可。
【样例输入】
array_sum[i] = array_a[i] +array_a[j]+ _next2[ j ]getArea( x, y , z) - 100i;
【样例输出】
z y x j i getArea array_sum array_a _next2
【样例说明】
从控制台读入的语句中有5个普通的变量：i、j、x、y和z，三个数组名：array_sum、array_a和_next2，一个函数调用，其函数名为getArea，将这9个标识符按照字典序由大到小排序输出。
【评分标准】
该题要求输入语句中标识符的识别和排序输出，提交程序名为：identifier.c。
解答1:
#include <stdio.h>
#include <string.h>
#include <ctype.h>
int main()
{
char line[201], str[50][16], temp[16];
int i, j, k, m, n;
gets(line);
m = 0;
for (i = 0; line[i] != '\0'; i++)
{
if (line[i] != '_' && !isalpha(line[i]))
continue;
j = 0;
temp[j++] = line[i++];
while (line[i] != '\0' && (isalnum(line[i]) || line[i] == '_'))
temp[j++] = line[i++];
temp[j] = '\0';
for (k = 0; k < m; k++)
if (strcmp(str[k], temp) == 0)
break;
if (k == m)
strcpy(str[m++], temp);
if (line[i] == '\0')
break;
}
for (i = 0; i < m; i++)
{
n = i;
for (j = i + 1; j < m; j++)
if (strcmp(str[n], str[j]) < 0)
n = j;
if (n != i)
{
strcpy(temp, str[n]);
strcpy(str[n], str[i]);
strcpy(str[i], temp);
}
}
for (i = 0; i < m; i++)
printf("%s ", str[i]);
}
解答2:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
typedef struct sign
{
char *data;
int cnt;
struct sign *lch, *rch;
} Node, *Nodeptr;
char buf[BUFSIZ] = {0};
int isfirst(int c)
{
return (c == '_' || isalpha(c));
}
int isuse(int c)
{
return (c == '_' || isalpha(c) || isdigit(c));
}
Nodeptr findItem(Nodeptr p, char *item)
{
if (p == NULL)
return NULL;
else if (strcmp(item, p->data) < 0)
return findItem(p->lch, item);
else if (strcmp(item, p->data) > 0)
return findItem(p->rch, item);
else
return p;
}
Nodeptr insert(Nodeptr p, char *item)
{
if (p == NULL)
{
p = (Nodeptr)malloc(sizeof(Node));
p->data = item;
p->cnt = 1;
p->lch = NULL;
p->rch = NULL;
}
else if (strcmp(item, p->data) < 0)
p->lch = insert(p->lch, item);
else if (strcmp(item, p->data) > 0)
p->rch = insert(p->rch, item);
else
p->cnt++;
return p;
}
Nodeptr getSign(Nodeptr root)
{
char *l = buf, *r = buf, *substr;
while (*r != ';')
{
while (!isfirst(*l))
l++;
r = l; //_ or alpha
while (isuse(*r))
r++;
r--; // last size
{
substr = (char *)malloc(sizeof(char) * (r - l + 2));
strncpy(substr, l, r - l + 1);
substr[r - l + 1] = 0;
root = insert(root, substr);
}
r++; // not useful size
while (!isfirst(*r) && *r != ';')
r++;
l = r;
}
return root;
}
void Visit(Nodeptr p)
{
printf("%s ", p->data);
}
void printNode(Nodeptr root)
{
if (root != NULL)
{
printNode(root->rch);
Visit(root);
printNode(root->lch);
}
}
int main()
{
Nodeptr root = NULL;
fgets(buf, BUFSIZ, stdin);
root = getSign(root);
printNode(root);
return 0;
}
解答3:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int isit(char a)
{
if ((a >= '0' && a <= '9') || (a >= 'a' && a <= 'z') || (a >= 'A' && a <= 'Z') || a == '_')
return 1;
else
return 0;
}
int isnotnum(char a)
{
if (a >= '0' && a <= '9')
return 0;
else
return 1;
}
int main()
{
char s[300], word[100][40], temp[40];
int i, l, j = 0, k = 0, flag;
gets(s);
l = strlen(s);
for (i = 0; i < l;)
{
if (isit(s[i]))
{
k = 0;
word[j][k] = s[i];
while (isit(s[++i]))
{
word[j][++k] = s[i];
}
word[j][++k] = '\0';
j++;
i++;
}
else
i++;
}
for (i = 0; i < j; i++)
{
l = strlen(word[i]);
flag = 0;
for (k = 0; k < l; k++)
{
if (isnotnum(word[i][k]))
{
flag = 1;
break;
}
}
if (flag == 0)
word[i][0] = '*';
}
for (i = 0; i < j - 1; i++)
{
for (k = 0; k < j - 1; k++)
{
if (strcmp(word[k], word[k + 1]) < 0)
{
strcpy(temp, word[k]);
strcpy(word[k], word[k + 1]);
strcpy(word[k + 1], temp);
}
}
}
for (i = 0; i < j - 1; i++)
{
if (strcmp(word[i], word[i + 1]) == 0)
word[i][0] = '*';
}
for (i = 0; i < j; i++)
{
if (word[i][0] != '*')
printf("%s ", word[i]);
}
return 0;
}
- 空 闲 空 间 申 请 模 拟（ 首 次 适 应 ） （分值：10.00）
【问题描述】
在操作系统中，空闲存储空间通常以空闲块链表方式组织，每个块包含块起始位置、块长度及一个指向下一块的指针。空闲块按照存储位置升序组织，最后一块指向第一块（构成循环链表）。当有空间申请请求时，按照如下原则在空闲块循环链表中寻找并分配合适的空间：
1）从当前位置开始遍历空闲块链表（初始时从地址最小的第一个空闲块开始），寻找第一个大于等于请求空间的空闲块（即首次适应原则）；
2）如果选择的空闲块恰好与请求的大小相符合，则将它从链表中移除并返回给用户；这时当前位置变为被移除的空闲块指向的下一空闲块；
3）如果选择的空闲块大于所申请的空间大小，则将大小合适的空闲块返回给用户，剩下的部分留在空闲块链表中；这时当前位置仍然为该空闲块；
4）如果找不到足够大的空闲块，则申请失败；这时当前位置不变。
例如：下图示例给出了空闲块链表的初始状态，每个结点表示一个空闲块，结点中上面的数字指空闲块的起始位置，下面的数字指空闲块的长度，位置和长度都用正整数表示，大小不超过int表示范围。当前位置为最小地址为1024的空闲块。
若有4个申请空间请求，申请的空间大小依次为：1024、2560、10240和512。则从当前位置开始遍历上图的链表，按照上述原则寻找到满足条件的空闲块为地址是16384的空闲块，其长度正好为1024，所以将其从链表中删除，这时链表状态如下图所示，当前位置变成地址为32768的空闲块。
从当前位置开始为第二个空间请求（大小为2560）遍历链表，按照上述原则寻找到满足条件的空闲块为当前位置的空闲块，其长度为3072，大于请求的空间大小，于是申请空间后该空闲块剩余的长度为512，当前位置不变，链表状态如下图所示：
从当前位置开始为第三个空间请求（大小为10240）遍历链表，遍历一圈后发现找不到足够大的空闲块，则忽略该请求，当前位置不变。下面继续为第四个空间请求（大小为512）遍历链表，按照上述原则寻找到满足条件的空闲块仍然为当前位置的空闲块，其长度等于请求的空间大小，于是将该空闲块删除后，链表状态变为下图所示：
编写程序，模拟上述空闲空间申请。
【输入形式】
先从控制台读入一正整数，表示当前空闲块的个数（大于0且小于等于100）。
然后按照起始位置由小到大的顺序分行输入每个空闲块的起始位置和长度，位置和长度都用正整数表示，大小不超过int表示范围，两整数间以一个空格分隔。
最后在新的一行上依次输入申请空间的大小，以-1表示结束，各整数间以一个空格分隔，申请请求的个数不超过100个。
【输出形式】
按照上述原则模拟完空闲空间申请后，输出当前空闲空间链表状态，即从当前位置开始，遍历链表，分行输出剩余空闲块的长度和起始位置，长度和起始位置间以一个空格分隔。若申请完后，链表中没有空闲块，则什么都不输出。
【样例输入】
12
1024 512
8192 512
16384 1024
32768 3072
65536 8192
77824 1024
80896 8192
96016 1024
101136 5120
119328 512
134448 1024
142640 3072
1024 2560 10240 512 2048 6400 2560 5600 2000 -1
【样例输出】
560 101136
512 119328
1024 134448
3072 142640
512 1024
512 8192
544 65536
1024 77824
1792 80896
1024 96016
【样例说明】
样例输入了12个空闲块的信息，形成了如上述第一个图所示的空闲块链表；然后读取了9个空间申请请求，为前4个申请请求分配空间后，空闲块链表状态为上述最后一张图所示。满足第五个请求后，地址为65536的空闲块剩余长度为6144；满足第六个请求后，地址为80896的空闲块剩余长度为1792；满足第七个请求后，地址为101136的空闲块剩余长度为2560；满足第八个请求后，地址为65536的空闲块剩余长度为544；满足第九个请求后，地址为101136的空闲块剩余长度为560，这时链表中剩余10个空闲块，当前位置为地址是101136的空闲块，从该空闲块开始依次遍历输出所有剩余空闲块的长度和起始位置。
【评分标准】
该题要求编程模拟实现空闲空间的申请，提交程序名为memory.c。
解答1：
#include <stdio.h>
#include <stdlib.h>
struct node
{
int ad, l;
struct node *next;
};
int main()
{
int i, k, n;
struct node *cur, *pre, *old, *temp;
scanf("%d", &n);
cur = temp = (struct node *)malloc(sizeof(struct node));
scanf("%d%d", &cur->ad, &cur->l);
for (i = 1; i < n; i++)
{
temp->next = (struct node *)malloc(sizeof(struct node));
temp = temp->next;
scanf("%d%d", &temp->ad, &temp->l);
}
temp->next = cur;
pre = temp;
while (1)
{
scanf("%d", &k);
if (k == -1)
break;
if (cur == NULL)
continue;
old = cur;
do
{
if (cur->l == k)
{
if (pre == cur)
{
cur = NULL;
free(pre);
}
else
{
pre->next = cur->next;
temp = cur;
cur = cur->next;
free(temp);
}
break;
}
else if (cur->l > k)
{
cur->l -= k;
break;
}
pre = cur;
cur = cur->next;
} while (cur != old);
}
if (cur == NULL)
return 0;
old = cur;
do
{
printf("%d %d\n", cur->l, cur->ad);
cur = cur->next;
} while (cur != old);
return 0;
}
解答2:
#include <stdio.h>
#include <stdlib.h>
typedef struct space
{
int pos;
int length;
struct space *link;
} S, *SP;
int main()
{
int n, i, num1, num2;
SP p, q = NULL, temp = NULL;
scanf("%d", &n);
scanf("%d%d", &num1, &num2);
p = (SP)malloc(sizeof(S));
p->pos = num1;
p->length = num2;
q = p;
temp = p;
for (i = 1; i < n; i++)
{
scanf("%d%d", &num1, &num2);
p = (SP)malloc(sizeof(S));
p->pos = num1;
p->length = num2;
q->link = p;
q = p;
}
p->link = temp;
p = p->link;
while (1)
{
scanf("%d", &num1);
if (num1 != -1)
{
temp = p;
while (1)
{
if (p->length == num1)
{
q->link = p->link;
p = p->link;
break;
}
else if (p->length > num1)
{
p->length = p->length - num1;
break;
}
else
{
p = p->link;
q = q->link;
}
if (p->pos == temp->pos)
break;
}
}
else
break;
}
temp = p;
while (1)
{
printf("%d %d\n", p->length, p->pos);
p = p->link;
if (p->pos == temp->pos)
break;
}
return 0;
}
解答3:
#include <stdio.h>
#include <math.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#define ll long long
#define N 210
typedef struct Qwe *link;
typedef struct Qwe
{
int index, val;
link nxt;
} qwe;
link head, p;
int main()
{
int i, n, index, val, x;
head = malloc(sizeof(qwe));
p = head;
scanf("%d", &n);
scanf("%d%d", &index, &val);
p->index = index;
p->val = val;
for (i = 1; i < n; ++i)
{
scanf("%d%d", &index, &val);
p->nxt = malloc(sizeof(qwe));
p->nxt->index = index;
p->nxt->val = val;
p = p->nxt;
}
p->nxt = head;
while (1)
{
scanf("%d", &x);
if (x == -1)
break;
p = head;
while (p->val < x && p->nxt != head)
p = p->nxt;
if (p->val > x)
{
p->val -= x;
head = p;
}
else if (p->val == x)
{
while (head->nxt != p)
head = head->nxt;
head->nxt = p->nxt;
free(p);
head = head->nxt;
}
}
p = head;
do
{
printf("%d %d\n", p->val, p->index);
p = p->nxt;
} while (p != head);
return 0;
}
期中加油！
