苏州大学数据结构期中复习.doc

《苏州大学数据结构期中复习.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一、题型（填空2*15应用题5*10算法设计题2*10）算法设计题，包括书上定义的各类的方法，以及自己添加的类方法或调用类的外部函数。有30分左右的英文题目，答题可全部用中文。二、复习素材a)课件b)书后习题及补充习题，特别是做过的习题，课件和做过的习题答案已全部放在实验平台上可供下载192.168.131.161。c)实验题中的一些算法实现d)本复习提纲需下载的同学请至实验平台下载第7章“作业”。第一章1、计算某一条语句执行次数2、时间复杂度计算。3、hedge第二章栈1、栈的抽象数据类型定义和基本操作，ADT定义的两个部分。2、

2、线性表和数组区别3、栈的特点、性质（LIFO,overflow,underflow,push,pop后栈的状态）、双栈共享空间、利用栈的方法实现栈的其他操作的算法，如：copy_stack等。4、栈类定义及顺序实现（包括各个方法的具体实现）5、逆波兰式计算器、括号匹配等应用第三章队列1、掌握队列的抽象数据类型定义和基本操作、扩展的队列操作。2、队列的特点、性质（FIFO,入队、出队后不改变原序列）3、队列的类定义及顺序实现，顺序队列产生的问题！如何解决？4、利用循环队列产生的问题（队空队满条件相同的问题）？有哪些解决方案？5、循环队

3、列实现算法。（包括各个方法的具体实现）第四章链栈和链队列1、链表结点类定义p1232、不使用safeguards的链栈（链队列，链表），可能会产生的一些问题剖析！如垃圾的累积，破坏封装特性等问题！举例说明？P131-136，分析算法中的错误。3、链栈类定义、具体实现（包括各个方法的具体实现）4、链队列定义、具体实现（包括各个方法的具体实现）第五章递归1、什么是递归，递归的种类，栈与函数调用，什么是调用记录2、汉诺塔算法实现过程3、递归算法递归树的画法第六章线性表和串1、线性表的概念和基本操作2、顺序线性表的类定义和实现。3、两种单链

4、表的方法实现。改进版中current,current_postion的作用，mutable的含义等。4、双向链表的实现算法。1、顺序存储和链式结构的优缺点比较和适用场合，如何在多种结构中选择？2、掌握串的概念、串的类定义和基本操作。P236-240,各构造函数的实现和调用时机，利用c串实现strcat，strncpy,strstr等操作。第七章查找1、各种查找算法（顺序查找，带sentinel的顺序查找，2种二分查找）的递归算法和非递归算法实现2、画比较树，利用查找树分析成功以及不成功时的平均比较次数（平均查找长度，AverageS

5、earchLength,ASL），时间复杂度分析和比较。3、以关键字比较为基础的查找算法的最好性能O(lgn)LowerBoundsp300第6章算法例题分析1、假设用带头结点、不带current指针的单链表作为线性表list的存储结构，为list添加一个成员函数，删除线性表中所有值为x的元素。请按以下函数原型进行设计，其中count返回被删除的元素的个数。templateintList::remove_all_x(constList_entry&x){Node

6、ntry>*p,*q;intcount=0;p=head;while(p->next){if(p->next->entry==x){q=p->next;p->next=q->next;deleteq;count++;}elsep=p->next;returncount;}2、假设用普通单链表作为线性表的存储结构，编写一线性表的方法，以判断该线性表的元素是否按值非递减有序排列。