《数据结构》
--------概论测验
1.计算机解决实际问题的基本过程是怎样的?
2.《数据结构》课程研究的内容实质是什么?
3.独立于计算机之外的数据关系称为什么关系?分为几类?
4.在计算机之内的数据关系称为什么关系?有几种?
5.在理解数据结构的概念时,应该把哪三个方面看成一个整体?
6.简略回答为什么要学习数据结构?
7.计算机处理的数据对象集合包含哪些元素?
8.数据运算包含哪些?
9.算法是什么?其特征有哪些?
10.如何评价算法?
--------线性表测验
1.线性表的特征是什么？非线性表的特征呢？
2.画出线性表的顺序存储结构示意图，并用C语言描述其存储结构。
线性表的顺序存储
结构的设计，对你在程序设计中有什么启示？
3.从一个长度为n的顺序表中,在第i个元素之前插入一个元素需要向后移动个元素。
(A) n-i (B) n- i +1 (C ) n- i -1 (D) i
如果删除第i个元素时，需要向前移动个元素。
(A)n-i (B) n- i +1 (C ) n- i -1 (D) i
4.画出线性表的链式存储结构示意图，并用C语言描述其存储结构。
5.在一个单向链表中，若要在指针q所指的结点的后面插入一个由指针p所指的结点，则
需要执行那些语句，请写出这些语句。
6.在一个单向链表中，如果这时需要删除p所指的结点，又需要执行那些语句，请写出这
些语句。
7.在顺序栈中，假定以高端地址作为栈底，以top作为栈顶，则当做入栈处理时，top 的
变化为。
（A）不变(B) top=0 (C ) top=top -1 (D) top=top+1
8.若入栈序列为A、B、C、D、E，入栈过程中可以出栈，则不可以是出栈序列。
（A）ABCDE （B）BCDEA （C）EABCD （D）EDCBA
9.在一个顺序存储的循环队列中，队首指向队首元素的。
(A)前一个位置 (B)后一个位置 (C)队首元素位置
10.在具有n个单元的顺序存储的循环队列中，假定front、rear 分别为队首和队尾指针，
则判断队满的条件是。
（A）(rear%n)== front （B）((front+1%n)==rear
（C）((rear-1) %n)== front （D）((rear+1)%n)==front
11. 输入受限的双端队列是指元素只能从队列的一端输入，但可以从队列的两端输出，如图所示。
若有8、1、4、2依次进入输入受限的双端队列，则得不到输出序列。
输入受限的双端队列
A. 2、8、1、4
B. 1、4、8、2 C . 4、2、1、8 D. 2、1、4、8
11.
--------树测验
1.
树的逻辑特征是怎样的? 2.
二叉树与树在概念上是相同的吗? 为什么？ 3.
深度为h 的二叉树最多有多少结点?第i 层最多有多少结点? 4. 一棵二叉树的中序序列和后序序列分别如下，试画出该二叉树。
（7分）
先序序列：- + a * b c / d e ；
中序序列：a + b * c – d / e ；
后序序列: a b c * + d e / -
------------------------------------------
先序序列：ABCDEFGHIJ ；
中序序列：CBEDAGHFJI ；
后序序列：CEDBHGJIFA
5. 将下图所示的森林转换成对应的二叉树：
6. n 个结点的二叉树，如果采用二叉链表存储，有多少个指针域为空？为什么？
7. n 个结点的二叉树，如果采用二叉链表存储，值非空的链域的个数为 。
a. n-1 b. 2n-1 c. n+1 d. 2n+1
8. 树的存储方式有几种?树的哪两种存储方式结合，可以使寻找双亲和孩子变得容易?并用
C 语言描述其存储结构?
9. 已知用于通讯的电文由7个字母组成，其字母的出现的频度权值W={6,8,2,4,9,15,19},
请构造出这组权值的哈夫曼树，并为这7个字母设计哈夫曼编码。
--------图测验
1. 图的逻辑关系是什么?其特征是什么?
2.图是什么的集合?
3.图分几类?其点和边的关系是什么?
4.图的存储结构有几种? 请用C语言描述出图存储结构?
5.图有几种遍历方法?请写出英文缩写.
6.在图论中，树是怎样定义的?其点和边的数目关系是怎样的?为什么?
--------查找测验
1.查找的方法分几类?它们之间的主要区别是什么?
2.评价查找算法效率的优劣的标准是什么?
3.证明分块查找的平均查找长度ASL是介于顺序查找和二分查找的平均查找长度ASL之
间.
4.列出所学的查找方法,并按第1题的分类进行划分.
5..
6.已知一个有序表为（12，18，24，35，47，50，62，83，90，115，134），当二分查找
值为90的元素时，次比较后查找成功；当二分查找值为47的元素时，次比较后查找成功。
该表的平均查找长度是多少？
7.什么是平衡因子? 它对什么有影响?LL , RR, LR, RL
8.p222 9-12
--------排序测验
1.什么是排序的稳定性和不稳定性?
2.哪些排序算法与数据的初态有关?
3.从未排序的序列中依次取出元素与已排序序列中的元素作比较，将其放入已排序序列中
的正确位置上，此方法称为；从未排序序列中挑选元素，并将其放入已排序序列的另一端，此方法称为；依次将每两个相邻的有序表合并成一个有序表的排序方法叫做；当两个元素比较出现反序（即逆序）时就相互交换位置的排序方法叫做。
4.排序的方法很多,选取排序方法时需要考虑哪些因素?
--------多维数组与广义表测验
1.多维数组(矩阵)一般采用什么方式存储?为什么?
2.广义表一般采用什么方式存储?为什么?
1.算法的设计与实现取决于什么?
3.矩阵数据一般采用存储方法存储数据; 广义表一般采用方式存储。