复习课1(0705)数据结构

线性表 栈 队列 线性表基础知识算法设计栈与队列栈与队列的结构特性 两种存储结构上 栈与队列的基本操作 栈与队列在程序设计中的应用 基础知识题 1 2 4 对以下单链表分别执行下列各程序段 画出结果示意图 1 Q P next 2 L P next 3 R data P data 4 R data P next data 5 P next next next data P data 6 T P while T NULL T data T data 2 T T next 7 T P while T next NULL T data T data 2 T T next 2 2 6 已知L是无头结点的单链表 且P结点既不是首结点 也不是尾结点 1 在P结点后插入S结点 2 在P结点前插入S结点 3 在表首插入S结点 4 在表尾插入S结点 3 2 9 简述以下算法的功能 voidBB LNode s LNode q P s While p next q p p next P next s BBvoidAA LNode pa LNode pb pa和pb分别指向单循环链表中的两个结点BB pa pb BB pb pa AA 算法设计题 顺序表 defineLIST INIT SIZE100 defineLISTINCREMENT10typedefstruct ElemType elem intlength intlistsize SqList 单链表typedefstructLnode ElemTypedata StructLnode next Lnode LinkList 线性表类型定义 4 2 19 已知线性单链表中的元素以值递增有序排列 试写一个高效的算法 删除表中所有介于 mink maxk 的元素 mink maxk h o 查找第一个大于mink的结点P next P while P next datanext StatusLL DEL LinkList LL DEL 8 2 22 试写一算法 对单链表实现就地逆置StatusLinkConvert LinkList LinkConvert 2 38设有一个双向循环链表 每个结点中除了有prior data和next域外 还增设了一个访问频度域freq 在链表被起用之前 频度域都初始化为0 而当对链表进行一次LOCATE L x 操作后 被访问的结点中的频度域freq的值便增1 同时调整链表中结点的顺序 使其按访问频度非递增的顺序排列 试编写符合上述要求的LOCATE操作算法 分析 定义数据结构typedefstructDuLNode ElemTypedata intfreq structDuLNode prior structDuLNode next DuLNode DuLinkList 访问值为x的结点 并使freq 调整顺序 找到第一个频度域比x结点大的结点 StatusLocate 基础知识题 1 栈与线性表的差别2 队列与栈两种数据类型的相同点和差异3 3 4 分析以下算法的功能 SElemType为int Statusalgo1 StackS intI n A 255 n 0 while StackEmpty S n Pop S A n for i 1 i n i Push S A i 栈与队列 2 Statusalgo2 StackS inte StackT intd InitStack T while StackEmpty S Pop S d if d e Push T d while StackEmpty T Pop T d Push S d 4 简述下列算法的功能voidalgo3 Queue 类型定义 顺序栈 defineSTACK INIT SIZE100 defineSTACKINCREMENT10 typedefstruct SElemType base SElemType top intstacksize SqStack 算法设计题 顺序循环队列 defineMAXQSIZE100 typedefstruct QElemType base intfront intrear SqQueue 5 3 17 试写一个算法 识别依次读入的一个以 为结束符的字符序列是否形如 序列1 序列2 模式的字符序列 其中序列1和序列2中都不含字符 且序列2是序列1的逆序列 如 a b b a 分析 算法中采用何种数据类型 线性表 栈 队列 a 初始化一个栈S b 依次读入字符 并压栈c 当字符为 时 依次读下面的字符 并与出栈元素比较 有一个不相等 则ERRORd 字符结束时 栈空 则OK 否则ERROR intsymmetry 使用栈 对读入的字符在 symmetry 6 3 28 假设以带头结点的循环链表表示队列 并且只设一个指针指向队尾元素结点 不设头指针 编写相应的队列初始化 入队和出队的算法 初始化 Q rear next Q rear 入队 创建一个新的结点pp next Q rear nextQ rear next p 出队操作 P Q rear nextR P nextP next R nextFree R 出队算法 StatusDeQu LinkQueuefree R 课堂练习 写出入队算法 8 3 33 在顺序存储结构上实现输出受限的双端循环队列的入列和出列 只允许队头出列 算法 设每个元素表示一个待处理的作业 元素值表示作业的预算时间 入队列采取简化的短作业优先原则 若一个新提交的作业的预计执行时间小于队头和队尾作业的平均时间 则插入在队头 否则插入在队尾 分析 用顺序队列实现 出队列与普通队列没有区别 入队 元素值 平均值 队尾入队 StatusEnQueue SqQueue EnQueue StatusDeQueue SqQueue 3 15假设以顺序存储结构实现一个双向栈 即在一个一维数组的存储空间中存在着两个栈 它们的栈底分别设在数组的两个端点 试编写实现这个双向栈tws的三个操作 初始化inistack tws 入栈push tws i x 和出栈pop tws i 的算法 其中i为0或1 用以分别指示设在数组两端的两个栈 定义双向栈 defineSTACK INIT SIZE 100 typedefstruct SElemType base SElemType top0 top1 ints