1.试述CPU与外设交换数据的方式及其特点分为三种方式: (1)程序传送方式:包括无条件传送和程序查询传送。无条件传送不查询外设状态,认为外设已经准备就绪,直接与外设传送数据。程序查询传送在执行输入输出前,要先查询接口中状态寄存器的状态

第一章 绪论 1、什么是数据结构 2、抽象数据类型及面向对象概念 3、数据结构的抽象层次 4、用C++描述面向对象程序 5、算法定义 6、模板 7、性能分析与度量

第三章链表 1.单链表(Singly Linked List 2.循环链表(Circular List 3.多项式及其相加 4.双向链表(Doubly Linked List 5.稀疏矩阵

第五章 递归 1、递归(Recurve)的概念 2、迷宫Maze问题 3、递归过程与递归工作栈 4、广义表(General Lists)

集合及其表示 等价类与并查集 静态搜索表 二叉搜索树 最优二叉搜索树 AVL树 小结

第九章 排序 1、概述 2、插入排序 3、交换排序 4、选择排序 5、归并排序 6、基数排序 7、外排序 8、小结

第一章概述 研究对象:信息的表示方法、数据的组织方法、操作算法设计 意义地位:数据结构+算法=程序 程序设计的基础 系统软件的核心

1-4.什么是抽象数据类型?试用C++的类声明定义“复数”的抽象数据类型。要求 (1)在复数内部用浮点数定义它的实部和虚部。 (2)实现3个构造函数:缺省的构造函数没有参数;第二个构造函数将双精度浮点数 赋给复数的实部,虚部置为0;第三个构造函数将两个双精度浮点数分别赋给复数的实部 和虚部

2-1设n个人围坐在一个圆桌周围,现在从第s个人开始报数,数到第m个人,让他出局;然后从出 局的下一个人重新开始报数,数到第m个人,再让他出局,…,如此反复直到所有的人全部出局为 止。下面要解决的 Josephus问题是:对于任意给定的n,s和m,求出这n个人的出局序列。请以n= 9,s=1,m=5为例,人工模拟 Josephus的求解过程以求得问题的解。 【解答】 出局人的顺序为5,1,7,4,3,6,9,2,8。 2-2试编写一个求解 Josephus问题的函数。用整数序列1,2,3,…,n表示顺序围坐在圆桌周围的 人,并采用数组表示作为求解过程中使用的数据结构。然后使用n=9,s=1,m=5,以及n=9,s=1, m=0,或者n=9,s=1,m=10作为输入数据,检查你的程序的正确性和健壮性。最后分析所完成算

4-2改写顺序栈的进栈成员函数push(x),要求当栈满时执行一个 stackFull()操作进行栈满处理。其功能 是:动态创建一个比原来的栈数组大二倍的新数组,代替原来的栈数组,原来栈数组中的元素占据新数组 的前 MaxSize位置。 【解答】 templatepush( const Type&item) if isFull ( stackFull();