title: 曲师大计院20级的PTA categories: - 数据结构 tags: - PTA toc: true
第一章 绪论
判断题
1-1
数据元素是数据的最小单位。F(数据项)
1-2
数据的逻辑结构是指数据的各数据项之间的逻辑关系。F（数据元素之间）
1-3
数据结构概念包括数据之间的逻辑结构、数据在计算机中的存储方式和数据的运算三个方面。T
1-4
数据结构的抽象操作的定义与具体实现有关。F
1-5
算法和程序没有区别，在数据结构中二者是通用的。F
1-6
数据结构包括数据对象集以及它们的逻辑结构和物理结构，还包括与数据对象相关联的操作集，以及实现这些操作的高效的算法。T
选择题（错题：2-9,2-13）
2-1
在 Data_Structure = (D，R)中，D 是（ ）的有限集合。
A.数据元素
2-2
以下关于数据结构的说法中错误的是（ ）。
A.数据结构相同，对应的存储结构也相同
2-4
算法分析的目的是( )
C.分析算法的效率以求改进
2-5
算法分析的两个主要方面是( )
A.空间复杂度和时间复杂度
2-6
采用链结构存储线性表时，其地址（ ）。
B.连续不连续都可以
2-7
一个正确的算法应该具有 5 个特性，除输入、输出特性外，另外 3 个特性是（ ）。
A.确定性、可行性、有穷性
2-8
算法的时间复杂度取决于（ ）
C.问题的规模和待处理数据的初态
2-9
以下数据结构中，哪一个是线性结构（ ）
D.串
2-10
以下数据结构中，（ ）是非线性数据结构
B.字符串
2-11
算法的时间复杂度与（ ）有关。
A.问题规模
2-12
以下程序段的空间复杂度为
int a = 1, b = 1, i;
for (i=0; i<=10; i++) {
b += a;
a = b - a;
}
B.O(1)
2-13
下列程序段的时间复杂度是（ ）。
count=0; for(k=1;k<=n;k*=2) for(j=1;j<=n;j++) count++;
C.O(nlog2n)
2-14
下面说法中，错误的是（ ）。
ⅰ.算法原地工作的含义是指不需要任何额外的辅助空间
ⅱ.在相同规模n下，复杂度为O(n)的算法在时间上总是优于复杂度为O(2n)的算法
ⅲ.所谓时间复杂度，是指最坏情况下估算算法执行时间的一个上界
ⅳ.同一个算法，实现语言的级别越高，执行效率越低
C.ⅰ,ⅳ
2-15
算法的计算量的大小称为算法的。
B.复杂度
2-16
在下面的程序段中，对x的赋值语句的频度为（ ）
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
x=x+1;
C.O(n2)
2-17
下面程序段的时间复杂度是 ( )
i ＝ 0；
while（i<=n）
i = i * 3；
D.O(log3n)
填空题（错题：4-1, 4-4, 4-6，4-7，4-10）
4-1
算法效率的比较
假设为解决某问题而设计的若干算法的时间复杂度分别为：
A) O(n) B) O(n2) C) O(log2n) D) O(nlog2n) E) O(2n) F) O(n) G) O(n!) H) O(1) I) O(n**n) J) O(n**n)
这些算法按效率由高到低的顺序是 HCFADIBEGJ
4-2
基本术语
数据 是客观事物的符号表示，是所有能输入到计算机中并被计算机程序处理的符号的总称。
4-3
数据结构的数学定义
数据结构的数学定义为一个二元组：
D**S=(D,R)
其中：D 是数据元素的有限集，R 是 D 上的关系 的有限集。
4-4
存储结构存储结构包括数据元素的表示和关系的表示。
4-5
基本术语
抽象数据类型 一般指由用户定义的、表示应用问题的数学模型，以及定义在该模型上的一组操作。
4-6
在数据结构中，数据的逻辑结构分为线性结构和非线性结构 。
4-7
数据结构由数据的逻辑结构、存储结构 和运算|操作三部分组成。
4-8
算法的特性
一个算法必须满足以下五个重要特性：
(1) 有穷性 一个算法必须总是在执行有穷步后结束，且每一步都可以有穷有时间内完成。
(2) 确定性 一个算法中每一条指令必须有确切的含义。
(3) 可行性 算法中的所有操作都可以通过已经实现的基本操作运算执行有限次来实现。
(4) 输入一个算法有零个或多个输入。
(5) 输出一个算法有一个或多个输出，它们是算法进行信息加工后得到的结果。
4-9
基本术语
数据元素是数据的基本单位，数据项是数据的不可分割最小单位。其中：前者在计算机中通常作为一个整体进行考虑和处理，它可以由一个或多个后者组成。
4-10
数据的实例
观察下面的表格：
| 学号 | 姓名 | 性别 | 语文 | 数学 | 物理 | 化学 | 英语 | 总分 |
|---|---|---|---|---|---|---|---|---|
| 15160101 | 王克强 | 男 | 87 | 95 | 93 | 76 | 84 | 435 |
| 15160102 | 刘铭志 | 男 | 77 | 82 | 80 | 97 | 95 | 431 |
| 15160103 | 孙勇 | 男 | 78 | 85 | 87 | 86 | 65 | 401 |
| 15160104 | 李瀚东 | 男 | 93 | 82 | 72 | 75 | 95 | 417 |
| 15160105 | 赵敏 | 女 | 95 | 90 | 88 | 82 | 96 | 451 |
| 15160106 | 张毅 | 男 | 78 | 76 | 65 | 81 | 80 | 380 |
| 15160107 | 柳青 | 女 | 82 | 91 | 82 | 84 | 85 | 424 |
| 15160108 | 蔡文婷 | 女 | 85 | 78 | 80 | 86 | 95 | 424 |
整张表格称为一个 数据对象，其中每一行称为一个 数据元素，任意一行中的每一个栏目称为一个数据项。
4-11
沃斯的名言
瑞士科学家尼古拉斯·沃斯(Niklaus Wirth)有一句在计算机领域里人尽皆知的名言：
算法 + 数据结构 = 程序
编程题
7-1 求最小值和次小值 (25 分)
#include<iostream>
using namespace std;
int main()
{
int n,x;
cin>>n;
cin>>x;
if(n>1){
int mini = x;
int mini2 = x;
int a[n]={x};
for(int i=1;i<n;i++)
{
cin>>a[i];
if(mini>a[i])mini=a[i];
}
for(int i=0;i<n;i++)
{
if(a[i]==mini)continue;
if(mini2==mini)mini2=a[i];
if(mini2>a[i])mini2=a[i];
}
if(mini==mini2)
cout<<"There is no second smallest element"<<endl;
else
cout<<mini<<" "<<mini2;
}
else
{
cout<<"Invalid Input"<<endl;
}
return 0;
}
7-2 求素数个数 (30 分)
#include<iostream>
using namespace std;
int main()
{
int n,num=0;
cin>>n;
int *a=new int[n+1];
for(int i=2;i<=n;i++)
a[i]=1;
a[0]=a[1]=0;
for(int i=2;i*i<=n;i++)
{
if(a[i])
{
for(int j=2*i;j<=n;j+=i)
a[j]=0;
}
}
for(int i=2;i<=n;i++)
{
if(a[i])num++;
}
cout<<num<<endl;
return 0;
}
/*
#include<iostream>
using namespace std;
int main()
{
int n,num=1,flag=1;
cin>>n;
if(n==1)cout<<"0"<<endl;
else if(n==2)cout<<"1"<<endl;
else
{
for(int i=3;i<=n;i+=2)
{
for(int j=3;j*j<=i;j+=2)
{
if(i%j==0)
{
flag=0;
break;
}
}
if(flag)
num++;
flag=1;
}
cout<<num<<endl;
}
return 0;
}
*/
/*
#include<iostream>
using namespace std;
int main()
{
int n,num=0,flag=1;
cin>>n;
for(int i=2;i<=n;i++)
{
for(int j=2;j*j<=i;j++)
{
if(i%j==0)
{
flag=0;
break;
}
}
if(flag)
{
num++;
}
flag=1;
}
cout<<num<<endl;
return 0;
}
*/
第二章 线性表
判断题（错题：1-2,1-4,1-15,1-17）
1-1
顺序存储方式只能用于存储线性结构。F
1-2
在顺序表中取出第i个元素所花费的时间与i成正比。F
1-3
线性表的顺序存储表示优于链式存储表示。F
1-4
带头结点的单循环链表中，任一结点的后继结点的指针域均不空。T
1-5
顺序表 - 存储结构
顺序表中逻辑上相邻的元素，其物理位置也一定相邻。T
1-6
链式存储的优点是插入、删除元素时不会引起后续元素的移动，缺点是只能顺序访问各元素。T
1-7
线性表若采用链式存储结构时，要求内存中可用存储单元的地址一定不连续。F
1-8
链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。T
1-9
若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用顺序表存储最节省时间。T
1-10
对于顺序存储的长度为N的线性表，删除第一个元素和插入最后一个元素的时间复杂度分别对应为O(1)和O(N)。F
1-11
在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。T
1-12
顺序存储方式的优点是存储密度大，且插入、删除运算效率高。F
1-13
在具有N个结点的单链表中，访问结点和增加结点的时间复杂度分别对应为O(1)和O(N)。F
1-14
线性表采用链式存储表示时，所有结点之间的存储单元地址可以连续也可以不连续。T
1-15
在单链表中，要访问某个结点，只要知道该结点的指针即可。因此，单链表是一种随机存取结构。F
1-16
在具有头结点的链式存储结构中，头指针指向链表中的第一个元素结点。F
1-17
在一个设有头指针和尾指针的单链表中，执行删除该单链表中最后一个元素的操作与链表的长度无关。F
1-18
循环链表可以做到从任一结点出发，访问到链表的全部结点。T
1-19
在单链表中，逻辑上相邻的元素，其物理位置必定相邻。F
1-20
在双向链表中，可以从当前结点出发访问到任何一个结点。T
选择题(错题：2-10,2-13,2-16,2-20)
2-1
在一个长度为n的顺序表中，向第i个元素(1≤i≤n+1)位置插入一个新元素时需要从后向前移动多少个元素。
B.n-i+1
2-2
对于线性表，在顺序存储结构和链式存储结构中查找第k个元素，其时间复杂性分别是多少？
D.O(1)和O(k)
2-3
在顺序结构表示的线性表中，删除第i个元素（数组下标为i-1)，需要把后面的所有元素都往前挪一位，相应的语句是：
for (___________ )
PtrL->Data[j-1]=PtrL->Data[j];
其中空缺部分的内容应该是
A.j = i; j< = PtrL->Last; j++
2-4
向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（ ）
B.63.5
2-5
顺序表是线性表的( )
B.顺序存储结构
2-6
以下说法错误的是 ( )。
C.在链表上实现读表元运算的平均时间复杂度为O（1）
2-7
哪个选项不是线性表的链式存储结构（ ）
B.顺序表
2-8
在向表中第i个元素（1≤i≤n+1）位置插入一个新元素时，为保持插入后表中原有元素的相对次序不变，需要从后向前依次后移（ ）个元素。
B.n-i+1
2-9
在删除表中第i个元素时，同样地，为保持删除后表中原有元素的相对次序不变，需要从前向后依次前移（ ）个元素。
A.n-i
2-10
与单链表相比，双链表的优点之一是（）。
D.顺序访问相邻结点更加灵活
2-11
在单链表中，要删除某一指定结点，必须先找到该结点的（）。
A.直接前驱
2-12
循环链表的主要优点是（）。
D.从表中的任意结点出发都能扫描到整个链表
2-13
若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用（）存储方式最节省运算时间。
D.带表头附加结点的双循环链表
2-14
单链表又称为线性链表，在单链表上实施插入和删除操作（ ）。
B.不需移动结点，只需改变结点指针
2-15
链表不具有的特点是( )。
A.可随机访问任一个元素
2-16
下面关于线性表的叙述中，错误的是。
B.线性表采用顺序存储，便于进行插入和删除操作。
2-17
单链表L（带头结点）为空的判断条件是。
B.L->next==NULL
2-18
在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（ ）。
B.s->next=p->next;p->next=s
2-19
对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ ）
B.head→next==NULL
2-20
设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省时间。
D.带头结点的双循环链表
填空题
4-1
顺序表 - 地址计算
假设顺序表第 1 个元素的内存地址是 100，每个元素占用 2 字节内存空间，则第 5 个元素的内存地址是 108
4-2
在有n个元素的顺序表中删除任意一个元素所需移动元素的平均次数为 （n-1)/2
4-3
在有n个元素的顺序表中的任意位置插入一个元素所需移动元素的平均次数为 n/2
4-4
在长度为n的顺序表L中将所有值为x的元素替换成y，该算法的时间复杂度为 O(n)
4-5
在顺序表中，逻辑上相邻的元素，其物理位置 一定 相邻。在单链表中，逻辑上相邻的元素，其物理位置 不一定 相邻。
4-6
对于顺序表的插入算法insert_sqlist来说，若以结点移动为标准操作，则插入算法的在最坏情况下的移动次数为 n ，时间复杂度是 O(n)。在平均情况下的移动次数为 n/2 ，时间复杂度是 O(n)。
4-7
线性表L=(a1, a2, ... , an)用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是 (n-1)/2
程序填空题
5-1 顺序表删除操作。
#include<iostream>
using namespace std;
#define OK 1
#define ERROR 0
#define MAXSIZE 100
typedef int datatype;
typedef struct {
datatype *elem;
int length;
} SqList;
int ListDelete_Sq(SqList &L, int i) {
if ((i < 1) || (i > L.length))
return ERROR;
for (int j = i; j <= L.length; j++)
; (2')
--L.length;
return OK;
}
int main() {
SqList L;
int i = 0, n,a;
datatype e;
L.elem = new datatype[MAXSIZE];
L.length = 0;
cin >> n;
for (i=0;i<n;i++)
cin >> L.elem[i];
L.length = i;
cin >> a;
if (ListDelete_Sq(L, a))
{
for (i = 0; i < L.length; i++)
if(i==0)
cout << L.elem[i];
else
cout << " " << L.elem[i];
}
else
cout << "ERROR";
return 0;
}
5-2单链表删除操作。
#include<iostream>
using namespace std;
#define OK 1
#define ERROR 0
typedef int ElemType;
typedef struct LNode {
ElemType data;
struct LNode *next;
} LNode, *LinkList;
void CreateList(LinkList &L, int n) ;//该函数未显示细节
int ListDelete_L(LinkList &L, int i) {
LinkList p, q;
int j;
p = L;
j = 0;
while((p->next) && (j <i)) (2')
{
p = p->next;
++j;
}
if (!(p->next) || (j > i - 1))
return ERROR;
q = p->next;
p->next=q->next;(2')
delete q;
return OK;
}
void print(LinkList &L)
{
LinkList p;
int flag=1;
p = L->next;
while (p) {
if(flag)
cout << p->data;
else
cout << " "<< p->data;
flag=0;
p = p->next;
}
}
int main() {
LinkList L;
ElemType e;
int length;
int i;
cin >> length;
CreateList(L, length);
cin >> i;
ListDelete_L(L,i);
print(L);
return 0;
}
函数题
6-1 求顺序表最大值 (10 分)
int GetMax(SqList L)
{
int maxi=0;
for(int i=0;i<L.length;i++)
{
if(maxi<L.elem[i])maxi=L.elem[i];
}
return maxi;
}
6-2 单链表逆置* (10 分)
void Reverse(NODE *head)
{
NODE *p,*p1,*p2,*p3;
p = head->next;
p1 = head;
p1->next = NULL;
while(p!=NULL)
{
p2 = p;
p = p->next;
p2->next = p1->next;
p1->next = p2;
}
}
6-3 单链表统计正数个数 (6 分)
int PositiveInt(LinkList L)
{
LNode *p;
int n=0;
p = L->next;
while(p!=NULL)
{
if(p->data>0)n++;
p = p->next;
}
return n;
}
编程题
7-1 学生顺序表的建立 (10 分)
法一：
#include<iostream>
#include<string>
#include<iomanip>
using namespace std;
struct Node
{
int id;
string name;
float s1,s2,s3;
Node *next;
};
int main()
{
int n;
int id;
string name;
float s1,s2,s3;
Node *p,*first,*last=NULL;
last = new Node;
first = last;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>id>>name>>s1>>s2>>s3;
p = new Node;
p->id = id;
p->name = name;
p->s1 = s1;
p->s2 = s2;
p->s3 = s3;
last->next = p;
last = p;
}
last->next = NULL;
p = first->next;
while(p!=NULL)
{
cout<<p->id<<" "<<fixed<<setprecision(1)<<p->name<<" "<<p->s1<<" "<<p->s2<<" "<<p->s3<<endl;
p = p->next;
}
return 0;
}
法二：
#include <iostream>
#include <iomanip>
using namespace std;
struct Students
{
int ID;
string name;
double score1;
double score2;
double score3;
}students[5];
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>students[i].ID>>students[i].name>>students[i].score1>>students[i].score2>>students[i].score3;
}
cout.precision(1);
for(int i=0;i<n;i++)
{
cout<<students[i].ID<<" "<<students[i].name<<" "<<fixed<<students[i].score1<<" "<<fixed<<students[i].score2<<" "<<fixed<<students[i].score3;
if(i!=n-1) cout<<endl;
}
return 0;
}
7-2 求两个一元多项式的和 (20 分)
法一：链表
#include<iostream>
using namespace std;
struct Node
{
int coef,exp;
Node *next;
};
int main()
{
int n,coef,exp;
Node *p,*p1,*q,*q1,*temp;
Node *first1,*first2,*last;
last = new Node;
first1=last;
cin>>n;
for(int i=0; i<n; i++)
{
cin>>coef>>exp;
p=new Node;
p->coef = coef;
p->exp = exp;
last->next=p;
last = p;
}
last->next = NULL;
last = new Node;
first2=last;
cin>>n;
for(int i=0; i<n; i++)
{
cin>>coef>>exp;
p=new Node;
p->coef = coef;
p->exp = exp;
last->next=p;
last = p;
}
last->next = NULL;
p=first1->next;
p1=first1;
q=first2->next;
while(p!=NULL&&q!=NULL)
{
if(p->exp>q->exp)
{
p=p->next;
p1=p1->next;
}
else if(p->exp<q->exp)
{
temp=q->next;
p1->next=q;
q->next=p;
q = temp;
}
else
{
p->coef+=q->coef;
if(p->coef==0)
{
p1->next=p->next;
delete p;
p=p1->next;
}
else
{
p=p->next;
p1=p1->next;
}
q = q->next;
}
}
if(q!=NULL)p1->next=q;
p=first1->next;
if(p!=NULL)
{
while(p->next!=NULL)
{
cout<<p->coef<<" "<<p->exp<<" ";
p=p->next;
}
cout<<p->coef<<" "<<p->exp<<endl;
}
else
cout<<0<<" "<<0<<endl;
return 0;
}
法二：数组
#include<iostream>
using namespace std;
int a[1001]={0};
int main()
{
int n,coef,exp;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>coef>>exp;
a[exp]=coef;
}
cin>>n;
for(int i=0;i<n;i++)
{
cin>>coef>>exp;
a[exp]+=coef;
}
n=0;
for(int i=1000;i>-1;i--)
{
if(n==0&&a[i])
{
cout<<a[i]<<" "<<i;
n=1;
}
else if(a[i])
cout<<" "<<a[i]<<" "<<i;
}
if(n)cout<<endl;
else cout<<0<<" "<<0<<endl;
}
7-3 两个有序链表合并（新表不含重复元素） (20 分)
法一：刘俊兄弟的代码……emm……
#include<iostream>
using namespace std;
int main()
{
int a[1000], b[1000];
int flog = 1;
int lengtha = 0, lengthb = 0;
while (flog)
{
int c;
cin >> c;
if (c == -1)
flog = 0;
else
{
a[lengtha++] = c;
}
}
flog = 1;
while (flog)
{
int c;
cin >> c;
if (c == -1)
flog = 0;
else
{
b[lengthb++] = c;
}
}
int j = 0;
for (int i = lengtha ; i < lengtha + lengthb; i++)
{
a[i] = b[j++];
}
if (lengtha + lengthb == 0)
{
cout << "NULL";
}
int n = lengtha + lengthb;
for (int i = 0; i < n-1; i++) //冒泡循环
{
for (int j = i + 1; j < n; j++)//从i后的一个元素一直往len-1位置寻找
{
if (a[j] == a[i]) //如果发现重复
{
for (int k = j + 1; k < n; k++)//j+1的位置到len-1的位置
{
a[k - 1] = a[k]; //将后面的数依次赋值给前一个位置
}
n--; //数组长度-1
j--; //重复点再次进行查重
}
}
}
for(int i=0;i<n-1;i++)
{
for (int j = 0; j < n - i-1; j++)
{
if (a[j] > a[j + 1])
{
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
for (int i = 0; i < n-1; i++)
{
cout << a[i]<< " ";
}
cout << a[n - 1]<<endl;
return 0;
}
法二：数组
#include<iostream>
using namespace std;
int a1[10000];
int a2[10000];
int main()
{
int x,n=0;
while(1)
{
cin>>x;
if(x == -1)break;
a1[n++] = x;
}
while(1)
{
cin>>x;
if(x == -1)break;
a1[n++] = x;
}
for(int i=0;i<n-1;i++)
{
int mini=i;
for(int j=i+1;j<n;j++)
{
if(a1[mini]>a1[j])mini=j;
}
if(mini!=i)swap(a1[mini],a1[i]);
}
int flag=0;
for(int i=0;i<n;i++)
{
if(a1[i]==flag)a1[i]=0;
else flag = a1[i];//?
}
int n1=0;
for(int i=0;i<n;i++)
{
if(a1[i])
a2[n1++]=a1[i];
}
for (int i = 0; i < n1-1; i++)
{
cout << a2[i]<< " ";
}
cout << a2[n1 - 1]<<endl;
return 0;
}
法三：链表
#include<iostream>
using namespace std;
struct Node
{
int data;
Node *next;
};
int main()
{
int x,flag=-1;
Node *first1,*first2,*first3,*p,*p1,*p2,*last;
last=new Node;
first1 = last;
while(1)
{
cin>>x;
if(x == -1)break;
if(x == flag)continue;
p = new Node;
p->data = x;
flag = x;
last->next = p;
last = p;
}
last->next = NULL;
last=new Node;
first2 = last;
flag = -1;
while(1)
{
cin>>x;
if(x == -1)break;
if(x == flag)continue;
p = new Node;
p->data = x;
flag = x;
last->next = p;
last = p;
}
last->next = NULL;
last = new Node;
first3 = last;
p1 = first1->next;
p2 = first2->next;
while(p1!=NULL||p2!=NULL)
{
if(p1!=NULL&&p2!=NULL)
{
if(p2->data>p1->data)
{
p= new Node;
p->data = p1->data;
last->next = p;
last = p;
p1=p1->next;
}
else if(p2->data<p1->data)
{
p= new Node;
p->data = p2->data;
last->next = p;
last = p;
p2=p2->next;
}
else if(p2->data==p1->data)
{
p= new Node;
p->data = p2->data;
last->next = p;
last = p;
p2=p2->next;
p1=p1->next;
}
}
else if(p2==NULL)
{
p= new Node;
p->data = p1->data;
last->next = p;
last = p;
p1=p1->next;
}
else if(p1==NULL)
{
p= new Node;
p->data = p2->data;
last->next = p;
last = p;
p2=p2->next;
}
}
last->next = NULL;
p= first3->next;
if(p!=NULL)
{
while(p->next!=NULL)
{
cout<<p->data<<" ";
p = p->next;
}
cout<<p->data<<endl;
}
else
cout<<"NULL"<<endl;
return 0;
}
7-4 在有序链表中插入数据 (20 分)
#include<iostream>
using namespace std;
struct Node
{
int data;
Node *next;
};
int main()
{
int n,x;
Node *p,*p2,*p1,*first,*last=new Node;
first=last;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>x;
p = new Node;
p->data = x;
last->next = p;
last = p;
}
last->next = NULL;
cin>>x;
p1 = first->next;
p2 = first;
while(p1!=NULL)
{
if(x == p1->data)break;
if(x<p1->data)
{
p = new Node;
p->data = x;
p->next = p1;
p2->next = p;
break;
}
else if(x>p1->data&&(p1->next==NULL||x<p1->next->data))
{
p = new Node;
p->data = x;
p->next = p1->next;
p1->next = p;
break;
}
p1 = p1->next;
p2 = p2->next;
}
if(first->next == NULL)
{
p = new Node;
p->data = x;
p->next = NULL;
first->next = p;
}
p = first->next;
while(p->next!=NULL)
{
cout<<p->data<<" ";
p = p->next;
}
cout<<p->data<<endl;
return 0;
}
第三章 栈和列表
判断题（错题：1-10）
1-1
若一个栈的输入序列为1，2，3，…，N，输出序列的第一个元素是i，则第j个输出元素是j−i−1。F
1-2
所谓“循环队列”是指用单向循环链表或者循环数组表示的队列。F
1-3
在对不带头结点的链队列作出队操作时，不会改变头指针的值。F
1-4
不论是入队列操作还是入栈操作,在顺序存储结构上都需要考虑"溢出"情况。T
1-5
队列和栈都是运算受限的线性表，只允许在表的两端进行运算。F
1-6
栈和队列的存储方式，既可以是顺序方式，也可以是链式方式。T
1-7
循环队列也存在着空间溢出问题。T
1-8
循环队列执行出队操作时会引起大量元素的移动。F
1-9
栈是插入和删除只能在一端进行的线性表；队列是插入在一端进行，删除在另一端进行的线性表。T
1-10
在n个元素连续进栈以后，它们的出栈顺序和进栈顺序一定正好相反。T
1-11
环形队列中有多少个元素可以根据队首指针和队尾指针的值来计算。T
1-12
栈和队列的插入和删除操作特殊，所以，栈和队列是非线性结构。F
1-13
序列{1,2,3,4,5}依次入栈，则不可能得到{3,4,1,2,5}的出栈序列。 T
1-14
队列中允许插入的一端叫队头，允许删除的一端叫队尾。F
单选题（错题：2-2、2-18）
2-1
若用大小为6的数组来实现循环队列，且当前front和rear的值分别为0和4。当从队列中删除两个元素，再加入两个元素后，front和rear的值分别为多少？
A.2和0
2-2
如果循环队列用大小为m的数组表示，且用队头指针front和队列元素个数size代替一般循环队列中的front和rear指针来表示队列的范围，那么这样的循环队列可以容纳的元素个数最多为：
B.m
2-3
以下数据结构中，（ ）是非线性数据结构。
A.树
2-4
设栈S和队列Q的初始状态均为空，元素{1, 2, 3, 4, 5, 6, 7}依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是{2, 5, 6, 4, 7, 3, 1}，则栈S的容量至少是：
D.4
2-5
线性表、堆栈、队列的主要区别是什么？
B.堆栈和队列都是插入、删除受到约束的线性表
2-6
栈和队列的共同点( )。
C.只允许在端点处插入和删除元素
2-7
下列关于线性表,栈和队列叙述,错误的是( )。
A.线性表是给定的n(n必须大于零)个元素组成的序列
2-8
设用一个数组A[1……N]来存储一个栈，令A[N]为栈底，用整型变量T指示当前栈顶位置，A[T]为栈顶元素。当从栈中弹出一个元素时，变量T的变化为（ ）。
A.T=T+1
2-9
链式栈与顺序栈相比，一个比较明显的优点是（ ）。
B.通常不会出现栈满的情况
2-10
(neuDS)在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的长度是（ ）。
C.(rear-front+maxSize)%maxSize
2-11
(nueDS_C++)设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5、e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是（ ）。提示：对于栈，可以全进再依次出；也可以进一个出一个；也可以进一部分，出一个，再进一部分；但是出栈之后，不能再入栈。
A.3
2-12
关于栈和队列的下列说法正确的是（）
B.栈是后进先出的结构，出栈时除了栈顶元素，其余元素无需移动；
2-13
一个栈的入栈序列是a,b,c,d,e，则栈的出栈序列不可能的是（ ）。
C.dceab
2-14
在一个链表表示的队列中， f和r分别指向队列的头和尾。下列哪个操作能正确地将s结点插入到队列中：
B.r->next=s; r=s;
2-15
栈和队列具有相同的。
B.逻辑结构
2-16
假定利用数组a[n]顺序存储一个栈，用top表示栈顶指针，用top==-1表示栈空，并已知栈未满，当元素x进栈时所执行的操作为（ ）。
C.a[++top]=x
2-17
队列的“先进先出”特性是指（ ）。
Ⅰ.最后插入队列中的元素总是最后被删除 Ⅱ.当同时进行插入、删除操作时，总是插入操作优先 Ⅲ.每当有删除操作时，总要先做一次插入操作 Ⅳ.每次从队列中删除的总是最早插入的元素
B.Ⅰ、Ⅳ
2-18
已知循环队列存储在一维数组A[0...n-1]中，且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列为空，且要求第一个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是（ ）。
B.0,n-1（原因：……）
2-19
执行函数时，其局部变量一般采用（ ）进行存储。
C.栈结构
2-20
对空栈 S 进行 Push 和 Pop 操作，入栈序列为 a, b, c, d, e，经过 Push, Push, Pop, Push, Pop, Push, Push, Pop 操作后，得到的出栈序列是：
D.b, c, e
2-21
用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为( )。
D.SXSSXSXX
填空题（错题：4-3）
4-1
栈的运算遵循 后进先出|先进后出 的原则。
4-2
以下运算实现在链队上的入队列，请在空白处用适当句子予以填充。
void EnQueue(QueptrTp *lq,DataType x){
LqueueTp *p;
p=(LqueueTp *)malloc(sizeof(LqueueTp));
p->data=x;(1')
p->next=NULL;
(lq->rear)->next=p;(1')
lq->rear=p;(1')
}
4-3
以下运算实现在链栈上的初始化，请在空白处用请适当句子予以填充。
typedef struct Node{
DataType data;
struct Node *next;
}StackNode,*LStackTp;
void InitStack(LStackTp &ls){ ls=NULL;}。(1')
函数题
6-3 jmu-ds-舞伴问题 (20 分)
int QueueLen(SqQueue Q)
{
return (Q->rear-Q->front+MAXQSIZE)%MAXQSIZE;
}
int EnQueue(SqQueue &Q, Person e)
{
Q->rear = (Q->rear+1)%MAXQSIZE;
Q->data[Q->rear] = e;
return 0;
}
int QueueEmpty(SqQueue &Q)
{
if(Q->rear==Q->front)return 1;
else return 0;
}
int DeQueue(SqQueue &Q, Person &e)
{
Q->front = (Q->front+1)%MAXQSIZE;
e = Q->data[Q->front];
return 0;
}
void DancePartner(Person dancer[], int num)
{
for(int i=0;i<num;i++)
{
if(dancer[i].sex=='M')
EnQueue(Mdancers,dancer[i]);
else
EnQueue(Fdancers,dancer[i]);
}
while(!QueueEmpty(Mdancers)&&!QueueEmpty(Fdancers))
{
Person x,y;
DeQueue(Mdancers,x);
DeQueue(Fdancers,y);
cout<<y.name<<" "<<x.name<<endl;
}
}
6-4 十进制转二进制（顺序栈设计和应用） (10 分)
bool isEmpty()
{
if(top==-1)return 1;
else return 0;
}
/* 元素x入栈 */
void Push(int x)
{
//if(x==MaxSize)cout<<"上溢"<<endl;
//else
mystack[++top]=x;
}
/* 取栈顶元素 */
int getTop()
{
return mystack[top];
}
/* 删除栈顶元素 */
void Pop()
{
top--;
}
编程题
7-1 银行业务队列简单模拟 (25 分)
#include<iostream>
using namespace std;
int arr[1000];
int main()
{
int n;
int flag1=0,flag2=0;
int top1=0,top2=0,top=0;
cin>>n;
int a1[n+1],a2[n+1],a[n+1];
for(int i=0;i<n;i++)
{
cin>>arr[i];
if(arr[i]%2!=0)a1[top1++]=arr[i];
else a2[top2++]=arr[i];
}
int t1=0,t2=0;
for(int i=0;i<n;i++)
{
if(arr[i]%2==0)flag2++;
else flag1++;
if(flag2%2==0&&flag1%4==0)
{
a[top++]=a1[t1++];
a[top++]=a1[t1++];
a[top++]=a2[t2++];
}else{
if(t1!=top1&&(flag1%2==0||t2==top2))
{
a[top++]=a1[t1++];
a[top++]=a1[t1++];
}
if(t2!=top2&&(flag2%2==0||t1==top1||flag1%2==0))
{
a[top++]=a2[t2++];
}
}
if(top==n)break;
}
for(int i=0;i<n-1;i++)
cout<<a[i]<<" ";
cout<<a[n-1]<<endl;
return 0;
}
7-2 堆栈操作合法性 (20 分)
#include<iostream>
#include<string>
using namespace std;
int main()
{
int N,M;
string str;
int n,x=0;
cin>>N>>M;
for(int i=0; i<N; i++)
{
cin>>str;
n = str.size();
for(int j=0; j<n; j++)
{
if(str[j]=='S')
{
x++;
if(x>M)break;
}
else if(str[j]=='X')
{
x--;
if(x<0)break;
}
}
if(x==0)cout<<"YES"<<endl;
else cout<<"NO"<<endl;
x=0;
}
return 0;
}
第四章 串和数组
判断题
1-1
假设模式串是abababaab，则KMP模式匹配算法中的next[j] = 0 1 1 2 3 4 5 6 2。T
选择题(错题：2-3,2-6,2-9,2-13)
2-1
KMP算法下，长为n的字符串匹配长度为m的字串的时间复杂度为
B.O（M+N）
2-2
串的长度是指
B.串中所含字符的个数
2-3
设主串 T = abaabaabcabaabc，模式串 S = abaabc，采用 KMP 算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是：
B.10（6+4）
2-4
串“ababaaababaa”的next数组为（ ）。
C.011234223456
2-5
已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”。采用KMP算法进行匹配，第一次出现“失配”(s[i]≠t[j])时，i=j=5，则下次开始匹配时，i和j的值分别是()。
C.i=5,j=2
2-6
2 符号串abcde的子串共有：
C.16（1+2+3+4+5+1(空串)）
[长度为n的字符串] 1、有n(n+1)/2 +1个子串；2、非空子串：n（n+1）/2；3、非空真子串：n（n+1）/2– 1
2-7
适用于压缩存储稀疏矩阵的两种存储结构是：
A.三元组表和十字链表
2-8
(neuDS)以下( )是稀疏矩阵的一种存储方法。
A.十字链表
2-9
一个稀疏矩阵采用压缩后，和直接采用二维数组存储相比会失去（ ） 特性。
B.随机存取
2-10
对特殊矩阵采用压缩存储的主要目的是（ ）。
D.减少不必要的存储空间
2-11
对n阶对称矩阵压缩存储时，需要表长为（ ）的顺序表。
C.n(n+1)/2
2-12
顺序查找法适合于存储结构为（ ）的线性表。
B.顺序存储或链式存储
2-13
（SWPU-DS）设有一个 10 阶的对称矩阵 A，采用压缩存储方式，以行序为主存储，a[1, 1] 为第一元素，其存储地址为 1，每个元素占一个地址空间，则 a[8, 5] 的地址为（ ）。
C.33（对称矩阵：(7+1)*7/2+5)）
[n阶对称矩阵的存储单元] n*(n+1)/2
第五章 树和二叉树
选择题
2-1
设一棵非空完全二叉树 T 的所有叶节点均位于同一层，且每个非叶结点都有 2 个子结点。若 T 有 k 个叶结点，则 T 的结点总数是：
A.2k−1
2-2
已知字符集{ a, b, c, d, e, f }，若各字符出现的次数分别为{ 6, 3, 8, 2, 10, 4 }，则对应字符集中各字符的哈夫曼编码可能是：
A.00, 1011, 01, 1010, 11, 100
2-3
已知二叉树的先序遍历序列为ABCDEFGH，中序遍历序列为CBEDFAGH，则该二叉树形态中，父节点的右子节点为（）。
C.G
2-4
若将一棵树 T 转化为对应的二叉树 BT，则下列对 BT 的遍历中，其遍历序列与 T 的后根遍历序列相同的是：
B.中序遍历
对 n 个互不相同的符号进行哈夫曼编码。若生成的哈夫曼树共有 115 个结点，则 n 的值是：
C.58
2-6
设 T 是非空二叉树，若 T 的先序遍历和中序遍历序列相同，则 T 的形态是 __
D.所有结点只有右孩子
2-7
以二叉链表作为二叉树的存储结构，在具有 n 个结点的二叉链表中（n>0），空链域的个数为 __
A.n+1
2-8
已知二叉树的前序遍历序列为 ABDCEFG，中序遍历序列为 DBCAFEG，则后序遍历序列为 __
B.DCBFGEA
2-9
对于任意一棵高度为 5 且有 10 个结点的二叉树，若采用顺序存储结构保存，每个结点占 1 个存储单元（仅存放结点的数据信息），则存放该二叉树需要的存储单元的数量至少是：
A.31
2-10
已知森林 F 及与之对应的二叉树 T，若 F 的先根遍历序列是 a, b, c, d, e, f，后根遍历序列是 b, a, d, f, e, c，则 T 的后序遍历序列是：
C.b, f, e, d, c, a
填空题
4-1
已知一棵完全二叉树的第5层（设根为第1层）有8个叶结点，则该完全二叉树的结点个数最多是：47
4-2
一棵二叉树的前序遍历序列是ABDFECGHK，中序遍历序列是DBEFAGHCK，则它的后序遍历序列是 DEFBHGKCA
4-3
具有n个结点的二叉树中,一共有 2n 个指针域,其中只有 n-1 个用来指向结点的左右孩子，其余的 n+1 个指针域为NULL。
4-4
若以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是 69
程序填空题
5-2
下列代码的功能是将二叉树T中的结点按照层序遍历的顺序输出。
typedef struct TreeNode *Tree;
struct TreeNode
{
int Key;
Tree Left;
Tree Right;
};
void Level_order ( Tree T )
{
Queue Q;
if ( !T ) return;
Q = CreateQueue( MaxElements );
Enqueue( T, Q );
while ( !IsEmpty( Q ) ){
T = Front_Dequeue ( Q ); /* return the front element and delete it from Q */
printf("%d ", T->Key);
if ( T->Left )
Enqueue( T->Left)3分;
if (T->Right 3分 )
Enqueue( T->Right)3分;
}
}
5-3
下列代码的功能是计算给定二叉树T的宽度。二叉树的宽度是指各层结点数的最大值。函数Queue_rear和Queue_front分别返回当前队列Q中队尾和队首元素的位置。
typedef struct TreeNode *BinTree;
struct TreeNode
{
int Key;
BinTree Left;
BinTree Right;
};
int Width( BinTree T )
{
BinTree p;
Queue Q;
int Last, temp_width, max_width;
temp_width = max_width = 0;
Q = CreateQueue(MaxElements);
Last = Queue_rear(Q);
if ( T == NULL) return 0;
else {
Enqueue(T, Q);
while (!IsEmpty(Q)) {
p = Front_Dequeue(Q);
temp_width++3分;
if ( p->Left != NULL ) Enqueue(p->Left, Q);
if ( p->Right != NULL ) Enqueue (p->Right)3分;
if ( Queue_front(Q) > Last ) {
Last = Queue_rear(Q);
if ( temp_width > max_width ) max_width = temp_width;
temp_width=0 3分;
} /* end-if */
} /* end-while */
return max_width;
} /* end-else */
}
函数题
6-1 求二叉树高度 (20 分)
int GetHeight( BinTree BT )
{
int LH,RH;
if(!BT)return 0;
else
{
LH = GetHeight(BT->Left);
RH = GetHeight(BT->Right);
return LH>RH?++LH:++RH;
}
}
6-2 二叉树的遍历 (25 分)
void InorderTraversal( BinTree BT )
{
if(!BT)return;
InorderTraversal(BT->Left);
printf(" %c",BT->Data);
InorderTraversal(BT->Right);
}
void PreorderTraversal( BinTree BT )
{
if(!BT)return;
printf(" %c",BT->Data);
PreorderTraversal(BT->Left);
PreorderTraversal(BT->Right);
}
void PostorderTraversal( BinTree BT )
{
if(!BT)return;
PostorderTraversal(BT->Left);
PostorderTraversal(BT->Right);
printf(" %c",BT->Data);
}
void LevelorderTraversal( BinTree BT )
{
if(!BT)return;
BinTree que[101],t;
int first=0,rear=0;
que[rear++]=BT;
while(first!=rear)
{
t=que[first++];
printf(" %c",t->Data);
if(t->Left)que[rear++]=t->Left;
if(t->Right)que[rear++]=t->Right;
}
}
6-3 先序输出叶结点 (15 分)
void PreorderPrintLeaves( BinTree BT )
{
if(BT)
{
if(!BT->Left&&!BT->Right) printf(" %c",BT->Data);
PreorderPrintLeaves(BT->Left);
PreorderPrintLeaves(BT->Right);
}
}
6-4 二叉树的非递归遍历 (25 分)
void InorderTraversal( BinTree BT )
{
BinTree T=BT;
Stack S = CreateStack();
while(T||!IsEmpty(S))
{
while(T!=NULL)
{
Push(S,T);
T = T->Left;
}
T = Pop(S);
printf(" %c",T->Data);
T=T->Right;
}
}
void PreorderTraversal( BinTree BT )
{
BinTree T=BT;
Stack S = CreateStack();
while(T||!IsEmpty(S))
{
while(T!=NULL)
{
Push(S,T);
printf(" %c",T->Data);
T = T->Left;
}
T = Pop(S);
T = T->Right;
}
}
void PostorderTraversal( BinTree BT )
{
BinTree T=BT;
Stack S = CreateStack();
while(T||!IsEmpty(S))
{
while(T!=NULL)
{
Push(S,T);
T->flag=0;
T = T->Left;
}
T = Peek(S);
if(T->flag==0)
{
T->flag++;
T=T->Right;
}
else{
T = Pop(S);
printf(" %c",T->Data);
T = NULL;
}
}
}
编程题
7-1 根据后序和中序遍历输出先序遍历 (25 分)
#include<iostream>
using namespace std;
struct Node
{
int data;
Node *left,*right;
};
Node* Creat(int *Post,int *In,int n)
{
if(n<=0)return NULL;
int len=0;
Node *p=new Node;
p->data = *(Post+n-1);
while(*(In+len)!=p->data)len++;
p->left=Creat(Post,In,len);
p->right=Creat(Post+len,In+len+1,n-len-1);//右子树……emmm……记住吧……
return p;
}
void Preorder(Node *t)
{
if(!t)return;
cout<<" "<<t->data;
Preorder(t->left);
Preorder(t->right);
}
int main()
{
int n;
cin>>n;
int a[n],b[n];
Node *t;
for(int i=0; i<n; i++)
cin>>a[i];
for(int i=0; i<n; i++)
cin>>b[i];
t=Creat(a,b,n);
cout<<"Preorder:";
Preorder(t);
return 0;
}
7-2 玩转二叉树 (25 分)
#include<iostream>
using namespace std;
struct Node
{
int data;
Node *left,*right;
};
Node* creat(int *In,int *Pre,int n)
{
if(n<=0)return NULL;
int len=0;
while(*(In+len)!=*Pre)len++;
Node *p=new Node;
p->data=*(In+len);
p->left=creat(In,Pre+1,len);
p->right=creat(In+len+1,Pre+len+1,n-len-1);//n-len-1我也不清楚……
return p;
}
void Level(Node *t,int n)
{
if(!t)return;
int first=0,last=0,i;
Node* Q[n],*w;
Q[last++]=t;
while(last!=first)
{
w=Q[first++];
//镜面也可以看做先右子树再左子树
if(w->right)Q[last++]=w->right;
if(w->left)Q[last++]=w->left;
}
for(i=0;i<n-1;i++)
cout<<Q[i]->data<<" ";
cout<<Q[i]->data<<endl;
}
int main()
{
int n;
cin>>n;
int In[n],Pre[n];
for(int i=0;i<n;i++)
cin>>In[i];
for(int i=0;i<n;i++)
cin>>Pre[i];
Node* t=creat(In,Pre,n);
Level(t,n);
return 0;
}
7-3 树的遍历 (25 分)
#include<iostream>
using namespace std;
struct Node
{
int data;
Node *left,*right;
};
Node* creat(int* In,int* Post,int n)
{
if(n<=0)return NULL;
int len=0;
while(*(In+len)!= *(Post+n-1))len++;
Node *p=new Node;
p->data=In[len];
p->left=creat(In,Post,len);
p->right=creat(In+len+1,Post+len,n-len-1);
return p;
}
void Level(Node* t,int n)
{
int last=0,first=0,i;
Node* Q[n],*w;
Q[last++]=t;
while(last!=first)
{
w=Q[first++];
if(w->left)Q[last++]=w->left;
if(w->right)Q[last++]=w->right;
}
for(i=0;i<n-1;i++)
cout<<Q[i]->data<<" ";
cout<<Q[i]->data<<endl;
}
int main()
{
int n;
cin>>n;
int In[n],Post[n];
for(int i=0;i<n;i++)
cin>>Post[i];
for(int i=0;i<n;i++)
cin>>In[i];
Node* t=creat(In,Post,n);
Level(t,n);
return 0;
}
7-4 哈夫曼编码 (30 分)
7-5 二叉搜索树的最近公共祖先 (30 分)
第六章 图
判断题
1-1
无向连通图所有顶点的度之和为偶数。T
1-2
无向连通图至少有一个顶点的度为1。F
1-3
用邻接矩阵法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关。T
1-4
在一个有向图中，所有顶点的入度与出度之和等于所有边之和的2倍。T
1-5
如果无向图G必须进行两次广度优先搜索才能访问其所有顶点，则G中一定有回路。F
1-6
在一个有权无向图中，若b到a的最短路径距离是12，且c到b之间存在一条权为2的边，则c到a的最短路径距离一定不小于10。T
1-7
用一维数组G[]存储有4个顶点的无向图如下：
G[] = { 0, 1, 0, 1, 1, 0, 0, 0, 1, 0 }
则顶点2和顶点0之间是有边的。T
1-8
Kruskal 算法是通过每步添加一条边及其相连的顶点到一棵树，从而逐步生成最小生成树。F
1-9
Prim 算法是通过每步添加一条边及其相连的顶点到一棵树，从而逐步生成最小生成树。T
1-10
若图G有环，则G不存在拓扑排序序列。T
1-11
若图G为连通图且不存在拓扑排序序列，则图G必有环。T
1-12
P 是顶点 S 到 T 的最短路径，如果该图中的所有路径的权值都加 1，P 仍然是 S 到 T 的最短路径。F
1-13
对于带权无向图 G = (V, E)，M 是 G 的最小生成树，则 M 中任意两点 V1 到 V2 的路径一定是它们之间的最短路径。F
1-14
如果从有向图 G 的每一点均能通过深度优先搜索遍历到所有其它顶点，那么该图一定不存在拓扑序列。T
1-15
如果 e 是有权无向图 G 唯一的一条最短边，那么边 e 一定会在该图的最小生成树上。T
选择题
2-1
在拓扑排序算法中用堆栈和用队列产生的结果会不同吗？
(1分)
A.
是的肯定不同
B.
肯定是相同的
C.
有可能会不同
D.
以上全不对
2-2
若要检查有向图中有无回路，除了可以利用拓扑排序算法外，下列哪种算法也可以用？
A.
Dijkstra算法
B.
Prim算法
C.
广度优先搜索
D.
深度优先搜索
2-3
下图为一个AOV网，其可能的拓扑有序序列为：
(2分)
A.
ABCDFEG
B.
ADFCEBG
C.
ACDFBEG
D.
ABDCEFG
2-4
下列选项中，不是下图深度优先搜索序列的是：
(2分)
A.
V1, V5, V4, V3, V2
B.
V1, V3, V2, V5, V4
C.
V1, V2, V5, V4, V3
D.
V1, V2, V3, V4, V5
2-5
若将n个顶点e条弧的有向图采用邻接表存储，则拓扑排序算法的时间复杂度是：
(1分)
A.
O(n)
B.
O(n+e)
C.
O(n2)
D.
O(n×e)
2-6
使用迪杰斯特拉（Dijkstra）算法求下图中从顶点1到其他各顶点的最短路径，依次得到的各最短路径的目标顶点是：
(2分)
A.
5, 2, 3, 4, 6
B.
5, 2, 3, 6, 4
C.
5, 2, 4, 3, 6
D.
5, 2, 6, 3, 4
2-7
使用迪杰斯特拉（Dijkstra）算法求下图中从顶点1到其他各顶点的最短路径，依次得到的各最短路径的目标顶点是：
(2分)
A.
6, 7, 5, 3, 2, 4
B.
6, 2, 5, 7, 3, 4
C.
2, 3, 4, 5, 6, 7
D.
2, 4, 3, 6, 5, 7
2-8
设无向图为 G=(V，E)，其中 V={v1,v2,v3,v4}，E={(v1,v2)，(v3,v4)，(v4,v1)，(v2,v3)，(v1,v3)}。则每个顶点的度依次为：
(2分)
A.
2, 1, 1, 1
B.
1, 1, 2, 1
C.
3, 2, 3, 2
D.
2, 3, 2, 3
2-9
对于给定的有向图如下，其逆邻接表为：
(2分)
A.
B.
C.
D.
2-10
已知一个无向图的顶点集为 {V0,V1,⋯,V7}，其邻接矩阵如下所示：
以下哪项不可能是从 V0 出发的广度优先遍历序？
(2分)
A.
V0,V1,V3,V4,V2,V6,V5,V7
B.
V0,V3,V1,V4,V2,V6,V5,V7
C.
V0,V3,V1,V4,V6,V2,V7,V5
D.
V0,V4,V3,V1,V6,V2,V7,V5
2-11
给定一个图的邻接矩阵如下，则从V1出发的宽度优先遍历序列（BFS，有多种选择时小标号优先）是：
(2分)
A.
V1, V2, V4, V3, V6, V8, V10, V9, V7, V5
B.
V1, V2, V3, V4, V5, V6, V7, V9, V8, V10
C.
V1, V2, V4, V6, V8, V10, V9, V7, V5, V3
D.
V1, V2, V3, V5, V7, V9, V10, V6, V8, V4
2-12
给出如下图所示的具有 7 个结点的网 G，哪个选项对应其正确的邻接矩阵？
A.
B.
C.
D.
2-13
已知无向图 G 如下所示，使用克鲁斯卡尔（Kruskal）算法求图 G 的最小生成树，加入到最小生成树中的边依次是：
A.
(b,f), (b,d), (a,e), (c,e), (b,e)
B.
(b,f), (b,d), (b,e), (a,e), (c,e)
C.
(a,e), (b,e), (c,e), (b,d), (b,f)
D.
(a,e), (c,e), (b,e), (b,f), (b,d)
2-14
若使用 AOE 网估算工程进度，则下列叙述中正确的是：
(2分)
A.
关键路径是从源点到汇点边数最多的一条路径
B.
关键路径是从源点到汇点路径长度最长的路径
C.
增加任一关键活动的时间不会延长工程的工期
D.
缩短任一关键活动的时间将会缩短工程的工期
2-15
下列关于无向连通图特征的叙述中，正确的是：
-
所有顶点的度之和为偶数
-
边数大于顶点个数减1
-
至少有一个顶点的度为1
A.只有1
B.只有2
C.1和2
D.1和3
2-16
若无向图G =（V，E）中含7个顶点，要保证图G在任何情况下都是连通的，则需要的边数最少是：
(3分)
A.6
B.15
D.21
2-17
具有N（N>0）个顶点的无向图至少有多少个连通分量？
A.0
B.1
C.N−1
D.N
2-18
用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是？
A.
无序的
B.
拓扑有序
C.
D.
以上都不对
2-19
若要求在找到从S到其他顶点最短路的同时，还给出不同的最短路的条数，我们可以将Dijkstra算法略作修改，增加一个count[]数组：count[V]记录S到顶点V的最短路径有多少条。则count[V]应该被初始化为：
A.
对所有顶点都有count[V]=1
B.
对所有顶点都有count[V]=0
C.
count[S]=1; `对于其他顶点`V`则令`count[V]=0
D.
count[S]=0; `对于其他顶点`V`则令`count[V]=1
2-20
任何一个带权无向连通图的最小生成树——
A.
是唯一的
B.
是不唯一的
C.
有可能不唯一
D.
有可能不存在
程序填空题
函数题
6-1 邻接矩阵存储图的深度优先遍历 (20 分)
/*void DFS( MGraph Graph, Vertex V, void (*Visit)(Vertex) ){
//cout << vertex[v];
Visit(V);
Visited[V] = true;
for (int j = 0; j < Graph->Nv; j++)
if (Graph->G[V][j] == 1 && Visited[j] == false) DFS(Graph,j,Visit);
}*/
void DFS( MGraph Graph, Vertex V, void (*Visit)(Vertex) )
{
Visit(V);
Visited[V]=true;
for(int j=0;j<Graph->Nv;j++)
{
if(Graph->G[V][j]==1&&Visited[j]==false)DFS(Graph, j, Visit);
}
}
6-2 邻接表存储图的广度优先遍历 (20 分)
void BFS ( LGraph Graph, Vertex S, void (*Visit)(Vertex) )
{
int w,j,Q[MaxVertexNum];
int first=0,late=0;
Visit(S);
Visited[S]=true;
Q[late++]=S;
PtrToAdjVNode tmp;
while(late!=first)
{
w=Q[first++];
tmp=Graph->G[w].FirstEdge;
while(tmp)
{
Vertex pos=tmp->AdjV;
if(!Visited[pos])
{
Visit(pos);
Visited[pos]=true;
Q[late++]=pos;
}
tmp=tmp->Next;
}
}
}
编程题
第七章 查找
判断题（错题：1-1,1-4,1-6）
1-1
在散列中，函数“插入”和“查找”具有同样的时间复杂度。T
1-2
当记录个数小于哈希表长度时，哈希查找平均查找长度必然为0。F
1-3
用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。F
1-4
有n个数存放在一维数组A[1..n]中，在进行顺序查找时，这n个数的排列有序或无序其平均查找长度不同。F
1-5
折半查找法的查找速度一定比顺序查找法快。F
1-6
就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。F
1-7
hash表的平均查找长度与处理冲突的方法无关。F
选择题(错题：2-9,2-10)
2-1
用二分查找从100个有序整数中查找某数，最坏情况下需要比较的次数是：
A.7
2-2
在有n（n>1000）个元素的升序数组A中查找关键字x。查找算法的伪代码如下所示：
k = 0;
while ( k<n 且 A[k]<x ) k = k+3;
if ( k<n 且 A[k]==x ) 查找成功;
else if ( k-1<n 且 A[k-1]==x ) 查找成功;
else if ( k-2<n 且 A[k-2]==x ) 查找成功;
else 查找失败;
本算法与二分查找（折半查找）算法相比，有可能具有更少比较次数的情形是：
B.当x接近数组开头处
2-3
下列二叉树中，可能成为折半查找判定树（不含外部结点）的是：
A.
2-4
在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20，需做的关键码比较次数为( )。
B.4
2-5
顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为( )次。
(2分)
A.n
输入一个正整数序列（53,17,12,66,58,70,87,25,56,60），按次序构造一棵二叉排序树BS为（ ）。
A.
2-7
在下列查找的方法中，平均查找长度与结点个数无关的查找方法是：
C.利用哈希（散列）表
2-8
对哈希(HASH)函数H(k)= k MOD m, 一般来说,m应取
(2分)
A.素数
2-9
将元素序列{18, 23, 4, 26, 31, 33, 17, 39}按顺序插入一个初始为空的、大小为13的散列表中。散列函数为：H(Key)=Key%13，采用线性探测法处理冲突。问：当第一次发现有冲突时，散列表的装填因子大约是多少？
C.0.31
2-10
现有长度为 11 且初始为空的散列表 HT，散列函数是 H(k**ey)=k**ey%7，采用线性探查（线性探测再散列）法解决冲突。将关键字序列 87,40,30,6,11,22,98,20 依次插入到 HT 后，HT 查找失败的平均查找长度是：
C.6
2-11
设有一组关键字 { 29，01， 13，15，56，20，87，27，69，9，10，74 }，散列函数为 H(k**ey)=k**ey%17，采用线性探测方法解决冲突。试在 0 到 18 的散列地址空间中对该关键字序列构造散列表，则成功查找的平均查找长度为 __
D.1.33
2-12
设有一组关键字 { 29，01， 13，15，56，20，87，27，69，9，10，74 }，散列函数为 H(k**ey)=k**ey%17，采用平方探测方法解决冲突。试在 0 到 18 的散列地址空间中对该关键字序列构造散列表，则成功查找的平均查找长度为 __
C.1.25
填空题（错题：4-1）
4-1
执行以下程序，
#include <stdio.h>
int main( ){
int array[10]={2, 12, 24, 36, 48, 49, 2333, 6666, 23333, 99999};
int key=2333, flag=0, low=0, m, h=9, times=0;
while(low <= h){
m = (low + h) / 2;
times++;
if(array[m] == key) {
printf("Found-%d-%d", m, times);
flag = 1;
break;
}
else if(array[m] > key) h = m - 1;
else low = m + 1;
}
if(flag == 0) printf("Not Found!");
return 0;
}
程序运行结果（即：在屏幕上打印的内容）是Found-6-4 。 （注意：要严格按照程序打印的格式填写答案，包括字母的大小写、空格的多少、连字符-和叹号!的格式等，不得随意增加引号、空格等无关字符，否则不得分。例如printf("hello World");打印的内容就是hello World，而不是"hello World"。为防止格式书写错误，建议直接从上面的代码中复制部分相关内容。）
4-2
顺序查找算法的平均查找长度
在下面的线性表中
( 15, 24, 32, 47, 50, 58, 62, 79, 83, 96 )
若采用顺序查找算法，假设各元素的检索概率相同，则平均查找长度为 5.5
4-3
二分查找算法的最大查找长度
在下面的有序表中
( 15, 24, 32, 47, 50, 58, 62, 79, 83, 96 )
若采用二分查找算法，则最大查找长度为 4
函数题
6-1 二分查找 (20 分)
Position BinarySearch( List L, ElementType x )
{
int high=L->Last,low=1,mid;
while(low<=high)
{
mid=(low+high)/2;
if(x<L->Data[mid])high=mid-1;
else if(x>L->Data[mid])low=mid+1;
else return mid;
}
return NotFound;
}
6-2 线性探测法的查找函数 (20 分)
Position Find( HashTable h, ElementType key )
{
int p0,p;
int num=0;
p=p0=Hash(key,h->TableSize);
while(h->Cells[p].Info!=Empty&&h->Cells[p].Data!=key)
{
num++;
if(num==MAXTABLESIZE)
{
return ERROR;
}
p=(p0+num)%h->TableSize;
}
return p;
}
6-3 有序数组的插入 (20 分)
/*bool Insert( List L, ElementType X )
{
if(L -> Last + 1 == MAXSIZE)//满了
return false;
for (int i = 0; i <= L -> Last; i++ )
{
if (L -> Data[i] == X) //已经有了
return false;
else if (L -> Data[i] < X)
{
for (int j = L ->Last; j >= i; j -- )//i之后的后移一位
{
L -> Data[j + 1] = L -> Data[j];
}
L->Data[i] = X;
L->Last ++;
break;
}
else if (i==L->Last && L->Data[i]> X)//插在最后一位
{
L->Data[L->Last+1] = X;
L->Last ++;
break;
}
}
return true;
}*/
bool Insert( List L, ElementType X )
{
if(L->Last==MAXSIZE-1)return false;
int low=0,high=L->Last,mid;
while(low<=high)
{
mid=(low+high)/2;
if(L->Data[mid]>X)low=mid+1;
else if(L->Data[mid]<X)high=mid-1;
else return false;
}
for(int i=L->Last;i>high;i--)
L->Data[i+1]=L->Data[i];
L->Data[high+1]=X;
L->Last++;
return true;
}
6-4 创建哈希表及查找(拉链法) (10 分)
void CreateHash(HashTable HT[],int n)
{
int x,num;
HashNode *p;
for(int i=0;i<n;i++)
{
cin>>x;
num=x%P;
p=new HashNode;
p->key = x;
if(HT[num]==NULL)
{
HT[num]=new HashNode;
p->next=NULL;
HT[num]->next=p;
}
else
{
p->next=HT[num]->next;
HT[num]->next=p;
}
}
}
float ASL(HashTable HT[])
{
HashNode *p;
int sum=0,len=0;
for(int i=0;i<P;i++)
{
if(HT[i]==NULL)continue;
else
{
int cnt=1;
p=HT[i]->next;
while(p!=NULL)
{
sum+=cnt;
cnt++;
len++;
p=p->next;
}
}
}
return sum*1.0/len;
}
编程题
7-1 电话聊天狂人 (25 分)
#include<bits/stdc++.h>
using namespace std;
int main()
{
map<string, int> m;
map<string, int>::iterator it;//迭代器（指针）
int n, cnt = 0, people= 1;
string s;//s存手机号
cin >> n;
for (int i = 0; i < n * 2; i++) {
cin >> s;
m[s]++;
}
for (it = m.begin(); it != m.end(); it++)
{
if (it->second > cnt) {//第一个位置存储的second的大于人数，则
people = 1;
s = it->first;
cnt = it->second;
}
else if (it->second == cnt) {//电话狂人不唯一
people++;//电话狂人有几个
if (it->first < s)//找最小的号码
s = it->first;
}
}
cout << s << " " << cnt;
if (people != 1)
cout << " " << people;
}//map容器
7-2 愤怒的牛 (25 分)
#include <bits/stdc++.h>
using namespace std;
int a[100010];
int l, r;
int n,c;
/*bool juge(int m)//判断距离m是否可以
{
int s = 0, last = 1;//记录上一个
for (int i = 2; i <= n; i++)//依次枚举每个牛栏
{
if (a[i] - a[last]<m)s++;//若此距离不满足当前答案，那么需要的牛栏数+1，即把当前牛放到下一个牛栏
else last = i;//否则就更新上一次的牛栏位置 ，即上一头牛放的位置
if (s>n - c) return false;//若需要牛栏数大于最大牛栏数，此答案不可行
}
return true;
}*/
bool juge(int m)
{
int ans = 1, last = 1; //因为第一个牛一定要占据第一个隔间（这样能使本题的答案最优），所以ans初始化为1
for (int i = 2; i <=n; i++)
{
if (a[i] - a[last] >= m)
{
ans++; //如果比最近距离要大的话，那么该隔间就放牛
last = i;
}
}
if (ans >= c)return true; //如果所选取的隔间数量>=c，则说明枚举的最近距离成立，但是不够大，所以return true,继续枚举更大的距离
return false;
}
int main()
{
cin >> n >> c;
for (int i = 1; i <=n; i++)cin >> a[i];
l = 1; r = a[n] - a[1]; //右边界为n个隔间的总长度，最近距离一定小于等于这个数值
sort(a + 1, a + 1 + n);
while (l <=r)
{
int mid = (l + r)/2;
if (juge(mid))l = mid+1; //如果当前枚举的最近距离符合，那么就让l=mid,看更大的距离是否也符合（因为要求最大的最近距离）
else
r = mid-1;
}
cout << r<< endl; //由于最后l<=r的时候还会运行一次，会让l-1(如果答案正确的话)，所以应该输出的是r
return 0;
}
第八章 排序
判断题
1-1
仅基于比较的算法能得到的最好的“最坏时间复杂度”是O(NlogN)。T
1-2
对N个记录进行简单选择排序，比较次数和移动次数分别为O(N2)和O(N)。T
1-3
对N个记录进行快速排序，在最坏的情况下，其时间复杂度是O(NlogN)。F
1-4
希尔排序是稳定的算法。F
1-5
堆排序是稳定的排序算法。F
1-6
在堆排序中，若要进行升序排序，则需要建立大根堆。T
1-7
排序算法中的比较次数与初始元素序列的排列无关。F
1-8
排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。F
1-9
对于n个记录的集合进行冒泡排序，在最坏情况下需要的时间是O(n2)。T
1-10
直接选择排序的时间复杂度为O(n2)，不受数据初始排列的影响。T
选择题(错题：2-6,2-11,2-12,2-13)
2-1
对N个不同的数据采用冒泡算法进行从大到小的排序，下面哪种情况下肯定交换元素次数最多？
A.从小到大排好的
2-2
在对N个元素进行排序时，基于比较的算法中，其“最坏时间复杂度”中最好的是：
C.O(Nlog**N)
2-3
对N个记录进行归并排序，归并趟数的数量级是：
A.O(log**N)
2-4
有组记录的排序码为{ 46，79，56，38，40，84 }，则利用堆排序的方法建立的初始堆为：
D.84，79，56，38，40，46
2-5
采用递归方式对顺序表进行快速排序，下列关于递归次数的叙述中，正确的是：
C.递归次数与每次划分后得到的分区处理顺序无关
2-6
有组记录的排序码为{46，79，56，38，40，84 }，采用快速排序（以位于最左位置的对象为基准而）得到的第一次划分结果为：
D.{40,38,46,56,79,84}
2-7
对于10个数的简单选择排序，最坏情况下需要交换元素的次数为：
A.9
将序列{ 2, 12, 16, 88, 5, 10, 34 }排序。若前2趟排序的结果如下：
-
第1趟排序后：2, 12, 16, 10, 5, 34, 88
-
第2趟排序后：2, 5, 10, 12, 16, 34, 88
则可能的排序算法是：
C.快速排序
2-9
对初始数据序列{ 8, 3, 9, 11, 2, 1, 4, 7, 5, 10, 6 }进行希尔排序。若第一趟排序结果为（ 1, 3, 7, 5, 2, 6, 4, 9, 11, 10, 8 ），第二趟排序结果为（ 1, 2, 6, 4, 3, 7, 5, 8, 11, 10, 9 ），则两趟排序采用的增量（间隔）依次是：
D.5, 3
2-10
下列排序算法中，占用辅助空间最多的是：( )
A.归并排序
2-11
选择一个排序算法时，除算法的时空效率外，下列因素中，还需要考虑的是：
-
I、数据的规模
-
II、数据的存储方式
-
III、算法的稳定性
-
IV、数据的初始状态
D.I、II、III、IV
2-12
排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一“趟”。下列序列中，不可能是快速排序第二趟结果的是：
D.5, 2, 12, 28, 16, 32, 72, 60
2-13
对大部分元素已有序的数组进行排序时，直接插入排序比简单选择排序效率更高，其原因是：
-
(I). 直接插入排序过程中元素之间的比较次数更少
-
(II). 直接插入排序过程中所需要的辅助空间更少
-
(III). 直接插入排序过程中元素的移动次数更少
A.仅 I
2-14
下述几种排序方法中,( )是稳定的排序方法。
C.归并排序
填空题
4-1
基于比较的排序方法，其最好的时间复杂度为O(nlogn)
4-2
时间复杂度为O(nlogn)的排序算法有归并排序、堆排序和快速排序
4-3
对包含10个记录的表r[1..10]进行简单选择排序，所需进行的关键字间的比较次数为45
函数题
6-1 快速排序 (15 分)
int Partition(SqList &L,int low,int high)
{
int i=low,j=high;
while(i<j)
{
while(i<j&&L.r[i].key<=L.r[j].key)j--;
if(i<j){swap(L.r[i].key,L.r[j].key);i++;}
while(i<j&&L.r[i].key<=L.r[j].key)i++;
if(i<j){swap(L.r[i].key,L.r[j].key);j--;}
}
return i;
}
void QuickSort(SqList &L, int low, int high)
{
if(low>=high)return;
else
{
int pivot=Partition(L,low,high);
QuickSort(L,low,pivot-1);
QuickSort(L,pivot+1,high);
}
}
6-2 冒泡排序 (10 分)
void bubbleSort(int arr[], int n)
{
int i,j;
for(i=0;i<n-1;i++)
{
for(j=0;j<n-i-1;j++)
{
if(arr[j]>arr[j+1])swap(&arr[j],&arr[j+1]);
}
}
}
6-3 简单选择排序 (10 分)
void SelectSort(SqList L)
{
int i,j,mini,temp;
int n = L.Length;
for(i=1;i<n;i++)
{
mini=i;
for(j=i+1;j<n+1;j++)
{
if(L.elem[mini]>L.elem[j])mini=j;
}
if(mini!=i){temp=L.elem[i];L.elem[i]=L.elem[mini];L.elem[mini]=temp;}
}
}
6-4 堆排序 (10 分)
void HeapAdjust( HeapType H, int s, int m)
{
int dad,son,last,temp;
dad=s;son=2*dad,last=m;
while(son<=last)
{
if(son+1<=last&&H.elem[son]<H.elem[son+1])son++;
if(H.elem[dad]>H.elem[son])return;
else
{
temp=H.elem[son];
H.elem[son]=H.elem[dad];
H.elem[dad]=temp;
dad=son;
son=dad*2;
}
}
}
6-5 归并排序 (10 分)
void Merge(SqList L,int low,int m,int high)
{
int Q[high-low+1];
int i=low,j=m+1,k=0;
while(i<=m&&j<=high)
{
if(L.elem[i]>=L.elem[j])
{
Q[k++]=L.elem[j++];
}
else if(L.elem[i]<=L.elem[j])
{
Q[k++]=L.elem[i++];
}
}
while(i<=m)Q[k++]=L.elem[i++];
while(j<=high)Q[k++]=L.elem[j++];
for(int i=low,k=0;i<=high;i++)
{
L.elem[i]=Q[k++];
}
}
编程题
7-1 字符串的冒泡排序 (20 分)
#include<iostream>
#include<string>
using namespace std;
int main()
{
int n,k;
cin>>n>>k;
string arr[n];
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
for(int i=0;i<n-1;i++)
{
for(int j=0;j<n-i-1;j++)
{
if(arr[j]>arr[j+1])swap(arr[j],arr[j+1]);
}
if(i==k-1)break;
}
for(int i=0;i<n;i++)
cout<<arr[i]<<endl;
return 0;
}
7-2 模拟EXCEL排序 (25 分)
/*#include<iostream>
using namespace std;
struct Info
{
string id;
string name;
int score;
};
int main()
{
int n,c,mini;
cin>>n>>c;
Info arr[n];
for(int i=0;i<n;i++)
{
cin>>arr[i].id>>arr[i].name>>arr[i].score;
}
if(c==1)
{
for(int i=0;i<n-1;i++)
{
mini=i;
for(int j=i+1;j<n;j++)
{
if(arr[mini].id>arr[j].id)mini=j;
}
if(mini!=i)swap(arr[mini],arr[i]);
}
}
else if(c==2)
{
int exchange,bound,temp;
exchange=n-1;
while(exchange)
{
bound=exchange;exchange=0;
for(int j=0;j<bound;j++)
{
if(arr[j].id>arr[j+1].id){swap(arr[j],arr[j+1]);exchange=j;}
}
}
exchange=n-1;
while(exchange)
{
bound=exchange;exchange=0;
for(int j=0;j<bound;j++)
{
if(arr[j].name>arr[j+1].name){swap(arr[j],arr[j+1]);exchange=j;}
}
}
}
else if(c==3)
{
int exchange,bound,temp;
exchange=n-1;
while(exchange)
{
bound=exchange;exchange=0;
for(int j=0;j<bound;j++)
{
if(arr[j].id>arr[j+1].id){swap(arr[j],arr[j+1]);exchange=j;}
}
}
exchange=n-1;
while(exchange)
{
bound=exchange;exchange=0;
for(int j=0;j<bound;j++)
{
if(arr[j].score>arr[j+1].score){swap(arr[j],arr[j+1]);exchange=j;}
}
}
}
for(int i=0;i<n;i++)
cout<<arr[i].id<<" "<<arr[i].name<<" "<<arr[i].score<<endl;
return 0;
}*/
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn = 100000 + 7;
int n, c;
struct node {
int id, sc;
char name[22];
}a[maxn];
bool cmp1(node a, node b) {
return a.id < b.id;
}
bool cmp2(node a, node b) {
if(strcmp(a.name, b.name) == 0) return a.id < b.id;
return strcmp(a.name, b.name) < 0;
}
bool cmp3(node a, node b) {
if(a.sc == b.sc) return a.id < b.id;
return a.sc < b.sc;
}
int main() {
//char s[22], t[22];
//scanf("%s %s", s, t);
//printf("%d\n", strcmp(s, t));
scanf("%d %d", &n, &c);
for(int i = 0; i < n; ++i) {
scanf("%d %s %d", &a[i].id, a[i].name, &a[i].sc);
}
if(c == 1) sort(a, a+n, cmp1);
if(c == 2) sort(a, a+n, cmp2);
if(c == 3) sort(a, a+n, cmp3);
for(int i = 0; i < n; ++i)
printf("%.6d %s %d\n", a[i].id, a[i].name, a[i].sc);
return 0;
}
7-3 悄悄关注 (25 分)
/*#include<iostream>
using namespace std;
struct Info
{
string name;
int zan;
};
int main()
{
int n1,n2,avg=0;
cin>>n1;
string guanzhu[n1];
for(int i=0; i<n1; i++)
cin>>guanzhu[i];
cin>>n2;
Info dianzan[n2],temp[n2];
for(int i=0; i<n2; i++)
{
cin>>dianzan[i].name>>dianzan[i].zan;
avg+=dianzan[i].zan;
}
avg /= n2;
int flag=1,k=0;
for(int i=0; i<n2; i++)
{
for(int j=0; j<n1; j++)
{
if(guanzhu[j]==dianzan[i].name)
{
flag=0;
break;
}
}
if(flag&&dianzan[i].zan>avg)
{
temp[k++]=dianzan[i];
}
flag=1;
}
if(k==0)cout<<"Bing Mei You"<<endl;
else
{
for(int i=0; i<k-1; i++)
{
int mini=i;
for(int j=i+1; j<k; j++)
{
if(temp[j].name<temp[mini].name)mini=j;
}
if(mini!=i)swap(temp[mini],temp[i]);
}
for(int i=0; i<k; i++)
cout<<temp[i].name<<endl;
}
return 0;
}
#include<iostream>
#include<set>
#include<map>
using namespace std;
struct Info
{
string name;
int zan;
};
struct List
{
Info dianzan[10000];
};
int Partition(List &l,int first,int last)
{
int i=first,j=last;
while(i<j)
{
while(i<j&&l.dianzan[i].name<=l.dianzan[j].name)j--;
if(i<j)
{
swap(l.dianzan[i],l.dianzan[j]);
i++;
}
while(i<j&&l.dianzan[i].name<l.dianzan[j].name)i++;
if(i<j)
{
swap(l.dianzan[i],l.dianzan[j]);
j--;
}
}
return i;
}
void quicksort(List&l,int first,int last)
{
if(first>=last)return;
else
{
int mid=Partition(l,first,last);
quicksort(l,first,mid-1);
quicksort(l,mid+1,last);
}
}
int main()
{
int n1,n2,zan,sum=0,flag=1,k=0;
string name;
List l;
set<string> guanzhu;
cin>>n1;
for(int i=0;i<n1;i++)
{
cin>>name;
guanzhu.insert(name);
}
cin>>n2;
for(int i=0;i<n2;i++)
{
cin>>name>>zan;
sum+=zan;
if(guanzhu.find(name)==guanzhu.end())
{
l.dianzan[k].name=name;
l.dianzan[k++].zan=zan;
}
}
sum/=n2;
quicksort(l,0,k);
for(int i=0;i<k;i++)
{
if(l.dianzan[i].zan>=sum)
{
cout<<l.dianzan[i].name<<endl;
flag=0;
}
}
if(flag)cout<<"Bing Mei You"<<endl;
return 0;
}
*/
#include<stdio.h>
#include<string>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
using namespace std;
int main()
{
int n,m,i,j,k=0,s=0,f=0,a,fag=0;
string s1,s2;
map<string,int>p;
set<string>p1;
cin>>n;
for(i=0;i<n;i++)
{
cin>>s1;
p[s1]=0;
}
cin>>m;
int c[m];
char b[m][10];
for(i=0;i<m;i++)
{
cin>>s2>>a;
s=s+a;
if(p.find(s2)==p.end())
{
for(j=0;j<sizeof(s2);j++)
{
b[k][j]=s2[j];
}
c[k]=a;
k++;
}
else
{
p[s2]=a;
}
}
s=s/m;
for(i=0;i<k;i++)
{
if(c[i]>s)
{
p1.insert(b[i]);
f++;
fag=1;
}
}
if(fag==0)
{
printf("Bing Mei You");
}
else
{
set<string>::iterator it;
for(it=p1.begin();it!=p1.end();it++)
{
cout<<*it<<endl;
}
}
return 0;
}