判断题
1-1
算法分析的两个主要方面是时间复杂度和空间复杂度的分析。（T）
1-2
算法可以没有输入，但是必须有输出。（T）
1-3
（T）
1-4
（F）
1-5
序列{1,2,3,4,5}依次入栈，则不可能得到{3,4,1,2,5}的出栈序列。（T）
1-6
栈结构不会出现溢出现象。（F）
1-7
队列的特性
队列是后进先出的线性表。（F）
1-8
两个栈共享一片连续空间，可以将两个栈的栈底分别设在这片空间的两端。（T）
1-9
线性表L如果需要频繁地进行不同下标元素的插入、删除操作，此时选择顺序存储结构更好。（F）
1-10
栈的特性
栈是后进先出的线性表。（T）
1-11
循环队列也存在空间溢出的问题。（T）
1-12
将N个数据按照从小到大顺序组织存放在一个单向链表中。如果采用二分查找，那么查找的平均时间复杂度是O(logN)。（F）
1-13
若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用顺序表存储最节省时间。（T）
1-14
链表 - 存储结构
链表中逻辑上相邻的元素，其物理位置也一定相邻。（F）
1-15
链表 - 存储结构
链表是一种随机存取的存储结构。（F）
1-16
若一个栈的输入序列为1，2，3，…，N，输出序列的第一个元素是i，则第j个输出元素是j−i−1。（F）
1-17
所谓“循环队列”是指用单向循环链表或者循环数组表示的队列。（F）
1-18
在用数组表示的循环队列中，front值一定小于等于rear值。（F）
1-19
对于顺序存储的长度为N的线性表，删除第一个元素和插入最后一个元素的时间复杂度分别对应为O(1)和O(N)。（F）
1-20
若一个栈的输入序列为{1, 2, 3, 4, 5}，则不可能得到{3, 4, 1, 2, 5}这样的出栈序列。（T）
单选题
2-1
在数据结构中，从逻辑上可以把数据结构分成（C ）。
A.动态结构和静态结构
B.紧凑结构和非紧凑结构
C.线性结构和非线性结构
D.内部结构和外部结构
2-2
以下说法正确的是（D ）。
A.数据元素是数据的最小单位
B.数据项是数据的基本单位
C.数据结构是带有结构的各数据项的集合
D.一些表面上很不相同的数据可以有相同的逻辑结构
2-3
算法的时间复杂度取决于（D ）。
A.问题的规模
B.待处理数据的初态
C.计算机的配置
D.A和B
2-4
下面的程序段违反了算法的（A）原则。
void sam()
{ int n=2;
while (n%2==0) n+=2;
printf(“%d”,n);
}A.有穷性 B.确定性 C.可行性 D.健壮性
2-5
下列程序段的时间复杂度为（B）。
x = n; /*n > 1*/
y = 0;
while(x >= (y + 1) * (y + 1))
y = y + 1;
A.Θ(n) B.Θ(n½) C.Θ(1) D.Θ(n2)
2-6
下列程序段的时间复杂度是（）
int sum = 0;
for(int i=1;i<n;i*=2)
for(int j=0;j<i;j++)
sum++;
A.O(logn) B.O(n) C.O(nlogn) D.O(n2)
2-7
假设某个带头结点的单链表的头指针为head，则判定该表为空表的条件是（B）
A.head==NULL
B.head->next==NULL
C.head!=NULL
D.head->next==head
2-8
线性表L在什么情况下适用于使用链式结构实现？（A）
A.需不断对L进行删除插入
B.需经常修改L中的结点值
C.L中含有大量的结点
D.L中结点结构复杂
2-10
执行下面程序段时，执行S语句的频度为（D）。
for(int i=0;i<n;i++)
for(int j=1;j<=i;j++)
S;
A.n2 B.n2/2 C.n(n+1) D.n(n+1)/2
2-11
下列函数中，哪个函数具有最慢的增长速度：（B）
2-12
用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为(D )。
A.SXSSSXXX
B.SXSXSXSX
C.SSSSXXXX
D.SXSSXSXX
2-14
有六个元素以6、5、4、3、2、1的顺序进栈，问哪个不是合法的出栈序列？（B）
A.2 3 4 1 5 6
B.3 4 6 5 2 1
C.5 4 3 6 1 2
D.4 5 3 1 2 6
2-15
若top为指向栈顶元素的指针，判定栈S（最多容纳m个元素）为空的条件是：（B）
A.S->top == 0
B.S->top == -1
C.S->top != m-1
D.S->top == m-1
2-16
若用大小为6的数组来实现循环队列，且当前front和rear的值分别为0和4。当从队列中删除两个元素，再加入两个元素后，front和rear的值分别为多少？
A.2和0
B.2和2
C.2和4
D.2和6
2-17
顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ C）。
A.100
B.105
C.108
D.110
2-18
线性表、堆栈、队列的主要区别是什么？（B）
A.线性表用指针，堆栈和队列用数组
B.堆栈和队列都是插入、删除受到约束的线性表
C.线性表和队列都可以用循环链表实现，但堆栈不能
D.堆栈和队列都不是线性结构，而线性表是
2-19
循环队列的引入，目的是为了克服( A)。
A.假溢出问题
B.真溢出问题
C.空间不够用
D.操作不方便
2-20
栈和队列的共同点是（C）。
A.都是先进先出
B.都是先进后出
C.只允许在端点处插入和删除元素
D.没有共同点
2-21
设栈S和队列Q的初始状态均为空，元素{1, 2, 3, 4, 5, 6, 7}依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是{2, 5, 6, 4, 7, 3, 1}，则栈S的容量至少是：（D）
A.1 B.2 C.3 D.4
2-22
下列关于栈的叙述中，错误的是：（C）
- 采用非递归方式重写递归程序时必须使用栈
- 函数调用时，系统要用栈保存必要的信息
- 只要确定了入栈次序，即可确定出栈次序
- 栈是一种受限的线性表，允许在其两端进行操作
A.仅 1
B.仅 1、2、3
C.仅 1、3、4
D.仅 2、3、4
2-23
链表 - 存储密度
链表的存储密度 ▁▁▁C▁▁ 。
A.大于 1
B.等于 1
C.小于 1
D.不能确定
2-24
现有队列 Q 与栈 S，初始时 Q 中的元素依次是{ 1, 2, 3, 4, 5, 6 }（1在队头），S 为空。若允许下列3种操作：（1）出队并输出出队元素；（2）出队并将出队元素入栈；（3）出栈并输出出栈元素，则不能得到的输出序列是：（C）
A.1, 2, 5, 6, 4, 3
B.2, 3, 4, 5, 6, 1
C.3, 4, 5, 6, 1, 2
D.6, 5, 4, 3, 2, 1
2-25
元素A,B,C,D依次入栈，出栈无限制，则以下（B）是可能的出栈序列。
A.C, A, B, D
B.B, A, D, C
C.B, D, A, C
D.A, D, B, C
2-26
已知初始为空的队列 Q 的一端仅能进行入队操作，另外一端既能进行入队操作又能进行出队操作。若 Q 的入队序列是 1、2、3、4、5，则不能得到的出队序列是：（D）
A.5、4、3、1、2
B.5、3、1、2、4
C.4、2、1、3、5
D.4、1、3、2、5
2-27
已知二维数组 A 按行优先方式存储，每个元素占用 1 个存储单元。若元素 A[0][0] 的存储地址是 100，A[3][3] 的存储地址是 220，则元素 A[5][5] 的存储地址是：（B）
A.295
B.300
C.301
D.306
函数题
6-1 十进制转二进制（顺序栈设计和应用） (15 分)
设计一个顺序栈，并利用该顺序栈将给定的十进制整整数转换为二进制并输出。
函数接口定义：
#define MaxSize 100 /* 栈最大容量 */
int top; /* 栈顶指针 */
int mystack[MaxSize]; /* 顺序栈 */
/*判栈是否为空，空返回true，非空返回false */
bool isEmpty();
/* 元素x入栈 */
void Push(int x);
/* 取栈顶元素 */
int getTop();
/* 删除栈顶元素 */
void Pop();
其中 MaxSize 和 top 分别为栈的最大容量和栈顶指针。数组mystack 用来模拟顺序栈。请实现给出的isEmpty、Push、getTop和Pop这四个函数。
裁判测试程序样例：
#include <bits/stdc++.h>
using namespace std;
#define MaxSize 100 /* 栈最大容量 */
int top; /* 栈顶指针 */
int mystack[MaxSize]; /* 顺序栈 */
/*判栈是否为空，空返回true，非空返回false */
bool isEmpty();
/* 元素x入栈 */
void Push(int x);
/* 取栈顶元素 */
int getTop();
/* 删除栈顶元素 */
void Pop();
/* 十进制正整数转换为二进制 */
void dec2bin(int x) {
top = -1; /* 初始化栈顶指针 */
while (x) {
Push(x % 2);
x >>= 1;
}
while (!isEmpty()) {
int t = getTop();
Pop();
printf("%d", t);
}
printf("\n");
}
int main(int argc, char const *argv[])
{
int n;
while (scanf("%d", &n) != EOF) {
dec2bin(n);
}
return 0;
}
/* 请在这里填写答案 */
输入样例：
10输出样例：
1010我的代码（C++）
bool isEmpty()
{//判断栈是否为空
if(top==-1)
return 1;
else
return 0;
}
void Push(int x)
{//入栈
mystack[++top]=x;
}
int getTop()
{//取栈顶元素
return mystack[top];
}
void Pop()
{//出栈
top--;
}
编程题
7-1 两个有序序列的中位数 (15 分)
已知有两个等长的非降序序列S1, S2, 设计函数求S1与S2并集的中位数。有序序列A0,A1,⋯,AN−1的中位数指A(N−1)/2的值,即第⌊(N+1)/2⌋个数（A0为第1个数）。
输入格式:
输入分三行。第一行给出序列的公共长度N（0<N≤100000），随后每行输入一个序列的信息，即N个非降序排列的整数。数字用空格间隔。
输出格式:
在一行中输出两个输入序列的并集序列的中位数。
输入样例1:
5
1 3 5 7 9
2 3 4 5 6
输出样例1:
4输入样例2:
6
-100 -10 1 1 1 1
-50 0 2 3 4 5
输出样例2:
1我的代码（C++）
#include<iostream>
#include<queue>
#include<stdlib.h>
using namespace std;
int main(void)
{
priority_queue <int,vector<int>,greater<int> > q;
int n;
cin>>n;
int *a,*b;
a=(int*)malloc(n*sizeof(int));
b=(int*)malloc(n*sizeof(int));
for(int i=0; i<n; i++)
{
cin>>a[i];
q.push(a[i]);
}
for(int i=0; i<n; i++)
{
cin>>b[i];
q.push(b[i]);
}
for(int i=0; i<n-1; i++)
{
q.pop();
}
cout<<q.top()<<endl;
}