- 前言
- 顺序表与单链表
- 1.选择题
- 2.函数&&编程题
- （1）顺序表的插入函数
- （2）顺序表的删除函数
- （3）单链表的查询插入删除
- 栈与队列
- 1.选择题
- 2.基本运算题
- （1）进制转换
- （2）循环队列出队入队
- （3）后缀表达式
- 树与二叉树
- 1.选择题
失踪人口回归啦~ 我作为一名普通的大学生，坐牢数天，只为期末。两天速成的大物取得了7*分的好（不挂）成绩.jpg 上午刚考完的高数大概也不会挂，前两天考了通英和英语六级。就是说坐牢结束了，但没完全结束。==【数据结构与算法】==还得考，挑重点的来，那就浅浅复习一下吧~
PS:鉴于时间原因，主要是通过例题来复习。
（1）对于顺序表，以下说法错误的是（ A）
A.顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址
B.顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列
C.顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻
D.顺序表的特点是:逻辑上相邻的元素，存储在物理位置也相邻的单元中
在C语言中，数组的下标是从0开始的，但位置序号是从1开始的，所以要注意区分元素的位置序号和该元素在数组中的下标位置的对应关系。另外，对于线性表，假设每个元素占用l个存储单元，并以所占的第一个单元的存储地址作为数据元素的起始位置，则线性表中第i个数据元素ai的存储位置为：LOC（ai） = LOC (a1)+(i-1)*l
—————————————————————————————————
（2）以下说法错误的是 ( C)。
A.对于线性表来说，定位运算LocateElem在顺序表和单链表上的时间复杂度均为O（n）
B.插入、删除操作在顺序表上的实现，平均时间复杂度为O（n）
C.在链表上实现读表元运算的平均时间复杂度为O（1）
D.插入、删除操作在链表上的实现可在O（1）时间内完成
对于A，定位运算需要遍历对比元素，故对；对于B,顺序表的插入和删除操作需要将按位移动元素，也对；对于C，链表中读元操作需要遍历元素，平均时间复杂度不是O（1），而在顺序表中，因为可以通过下标直接访问元素，所以时间复杂度为常数时间；对于D选项，在链表的头部插入和尾部删除的实现操作是常数时间，故正确。
————————————————————————————————
（3）顺序存储表示中数据元素之间的逻辑关系是由（ C）表示的。
A.指针
B.逻辑顺序
C.存储位置
D.问题上下文
顺序存储的存储位置与逻辑结构中的逻辑前后顺序是对应的。
————————————————————————————————
（4）设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( D)最节省时间。
A.单链表
B.单循环链表
C.带尾指针的单循环链表
D.带头结点的双循环链表
因为在末尾插入或者结点需要找到尾结点以及尾结点的前一个结点，因此采用单链表操作的时间复杂度为O（n),用带尾指针的单循环链表删除尾结点是常数时间，但插入节点仍然是O（n）。用带头结点的双循环链表最节省时间。
int ListInsert(SqList &L,int i,ElemType e){
//插入位置不合法
if(i<=0||(i>L.length+1)){
return 0;
}
//表满
if(L.length>=MAXSIZE){
return 0;
}
int j;
//插入位置后的元素后移一位
for(j=L.length-1;j>=i-1;j--){
L.elem[j+1]=L.elem[j];
}
L.elem[i-1]=e;
//表长加一
L.length ++;
return 1;
}
—————————————————————————————————
（2）顺序表的删除函数int ListDelete(SqList &L,int i){
//删除位置不合法
if((i<1)||(i>L.length)){
return 0;
}
//元素前移
for(int j=i;j<=L.length-1;j++){
L.elem[j-1]=L.elem[j];
}
//表长减1
L.length --;
return 1;
}
————————————————————————————————
（3）单链表的查询插入删除int Get_LinkList(LinkList H, ElemType key){
int i = 0;
while(H->data!=key){
H=H->next;
i ++;
}
return i;
}
Status ListInsert(LinkList &H,int i,ElemType e){
LinkList p = H;
LinkList s = NULL;
if(i<=0){
return OVERFLOW;
}
int j = 0;
while(p!=NULL&&j
p=p->next;
j++;
}
if(j>i-1){
return OVERFLOW;
}
s= new LNode;
s->data = e;
s->next = p->next;
p->next = s;
return OK;
}
Status ListDelete(LinkList &H,int i){
if(i<=0){
return OVERFLOW;
}
LinkList q = H,s=NULL;
if(q==NULL||q->next==NULL){
return FALSE;
}
int flag = 0;
while(q->next&&flag
q=q->next;
flag ++;
}
s = q->next;
q->next = s->next ;
delete(s);
return TRUE;
}
栈与队列
1.选择题
（1）设栈S和队列Q的初始状态均为空，元素a、b、c、d、e、f、g依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是b、d、c、f、e、a、g，则栈S的容量至少是：©
A.1
B.2
C.3
D.4
自己想一想吧哈哈哈，简单题。
————————————————————————————————
（2）用链接方式存储的队列，在进行删除运算时（D ）。
A.仅修改头指针
B.仅修改尾指针
C.头、尾指针都要修改
D.头、尾指针可能都要修改
用一个不带头结点的单链表来表示队列时，队空的条件为rear = NULL或者front = rear =NULL，如果队列中有两个及以上的元素，则在删除时只需要修改front指针，但是在队列中只有一个元素时，删除后即为空，需要修改rear指针。所以选D。
#include#include typedef int Status; typedef int SElemType; #define stack_INIT_SIZE 100 #define stackINCREMENT 10 #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef struct { SElemType *base; //栈底指针 SElemType *top; //栈顶指针 int stacksize; //栈空间 }Sqstack; Sqstack S; Status iniStack(Sqstack &S); Status push(Sqstack &S,SElemType x); Status pop(Sqstack &S,SElemType &e); void conversion(int n,int R); int main() { int N,R; scanf("%d",&N); //输入十进制数 scanf("%d",&R); //输入要转换的进制 if(R<0||R>=10) //判断R是否合法 { printf("illegal input"); return ERROR; } conversion(N,R); //进制转换 return OK; } Status iniStack(Sqstack &S){ S.base = (SElemType*)malloc(sizeof( SElemType)); if(!S.base){ return ERROR; } S.top = S.base; S.stacksize = stack_INIT_SIZE; return OK; } Status push(Sqstack &S,SElemType x){ if(S.top-S.base>=stack_INIT_SIZE){ S.base=(SElemType*)realloc(S.base,(stack_INIT_SIZE+stackINCREMENT)*sizeof(SElemType)); if(!S.base){ return ERROR; } } *S.top = x; S.top ++; return OK; } Status pop(Sqstack &S,SElemType &e){ if(S.top==S.base){ return ERROR; } S.top--; e=*S.top; return OK; } void conversion(int n,int R){ iniStack(S); while(n>0){ push(S,n%R); n=n/R; } while(S.top!=S.base){ pop(S,*S.top); printf("%d",*S.top); } }
————————————————————————————————
（2）循环队列出队入队void InitQ(SqQueue &Q,int N){
Q.base = (int *)malloc(N*sizeof(int));
if(!Q.base){
return ;
}
Q.front = 0;
Q.rear = 0;
}
void AddQ(SqQueue &Q, int x ){
if((Q.rear+1)%N==Q.front){//队列满
printf("Queue Fulln");
return ;
}
Q.base[Q.rear]=x;
Q.rear=(Q.rear+1)%N;
}
Status DeleteQ(SqQueue &Q,int &e){
if(Q.rear==Q.front){//队列空
printf("Queue Emptyn");
return ERROR ;
}
e=Q.base[Q.front];
Q.front=(Q.front+1)%N;
return OK;
}
—————————————————————————————————
（3）后缀表达式#include树与二叉树#include #include using namespace std; const int aMod = 1000000007; int main() { using ll = long long; #define int ll stack Stk; string Str; getline(cin, Str); int num = 0; bool isnum = false; for (char c : Str) { if (c >= '0' && c <= '9') num = (num * 10 + c - '0') % aMod, isnum = true; else if (c == ' ' && isnum) { isnum = false; Stk.push(num); num = 0; } else if (c != ' ') { isnum = false; int a = Stk.top(); Stk.pop(); int b = Stk.top(); Stk.pop(); switch (c) { case '+': Stk.push((a + b) % aMod); break; case '-': Stk.push((b - a) % aMod); break; case '*': Stk.push(a * b % aMod); break; case '/': Stk.push(b / a % aMod); break; } } } printf("%d", int(Stk.top())); return 0; }
树的这一章概念太多啦，就需要花时间记。复习的话，还是来看题吧。
1.选择题（1）以下说法错误的是 (A )
A.
树形结构的特点是一个结点可以有多个直接前趋
B.
线性结构中的一个结点至多只有一个直接后继
C.
树形结构可以表达(组织)更复杂的数据
D.
树(及一切树形结构)是一种"分支层次"结构
E.
任何只含一个结点的集合是一棵树
这道题算是对树形结构的一种阐述吧。
（2)利用二叉链表存储树，则根结点的右指针是（ ）。
A.指向最左孩子
B.指向最右孩子
C.空
D.非空
这道题考查的是二叉树的存储结构，二叉链表存储结构就是指树的孩子兄弟表示法，左指针指向第一个孩子结点，右指针指向下一个兄弟结点。而树的根节点没有兄弟结点，故选C。
————————————————————————————————
（3）已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（ A）。
A.CBEFDA
B.FEDCBA
C.CBEDFA
D.不定
关于二叉树的遍历，推荐一篇文章，传送之门：二叉树的四种遍历方法。
