1、解释：算法 抽象数据类型 数据结构
2、算法的5个重要特性是 、 、 输入和输出。
3、一个算法性能的分析主要考虑 和 两个方面。
4、数据逻辑结构可分为 、 、 和 四种。
5、数据物理结构可分为 和 两种。
6、抽象数据类型可用三元组（D，S，P）表示，其中D是 ， S是 ，P是 。
7、数据结构在计算机内存中的表示是指（ ）。 A．数据的存储结构 B.数据结构
C．数据的逻辑结构 D.数据元素之间的关系 8、以下程序段的时间复杂度为( )。 S=0;
for ( i = 1 ; i <= n; i ++;) for ( j = 1;j <= i; j ++;)
for ( k = 1 ; k <= n; k ++;)
S++;
A． O(n3) B． O(n2) C． O(n) D． O(1) 第二章
1. 对链表设置头结点的作用是什么？简述顺序表和链表存储方式的特
点。
2. 画出单链表在进行插入和删除数据元素前后结点的指针变化情况并用
C语言描述指针的变化。
3. 用C语言描述单链表中的结点定义。
1. 线性表的链式存储结构主要包括 链表、 链表和
链表三种形式。
2. 线性表的存储结构分成___ ___和______。
3. 线性表的顺序存储结构是通过 来直接反映数据元素
之间的逻辑关系，而链式存储结构是通过 间接反映数据元素之间的逻辑关系。
4. 若对线性表进行的操作主要不是插入和删除，则该线性表宜采用
存储结构；若频繁地对线性表进行插入和删除操作，则该线性表宜采用 存储结构。
5. 线性表的逻辑结构：在线性表中，除第一个元素和最后一个元素外，
第 页 （ 共 8 页 ） 1
其他元素都有且仅有 个直接前趋，有且仅有 个直接后继。 6. 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求
以最快的速度存取线性表中的元素时，应采用_______存储结构。 7. 线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概
率相同，则删除一个元素平均需要移动元素的个数是________。 8. 顺序表的插入、删除操作平均要移动表长的 。 9. 在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素
时，需向后移动________个元素。 10. 对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点
的时间复杂度为________,在给定值为x的结点后插入一个新结点的时间复杂度为________。
11. 对于双向链表,在两个结点之间插入一个新结点需修改的指针共
______个，对单链表，则需修改_______个指针。
12. 在单链表L中，指针p所指结点有后继结点的判断条件是：if
（__ ）。
13. 列举四种线性结构：______、______、_______和_______。 14. 在单链表中设置头结点的作用是__ ______。 15. 顺序表存储特点： 16. 顺序表操作特点： 17. 线性链表存储特点 18. 线性链表操作特点
19. 循环单链表的最大优点是：________。 20. 线性表的顺序存储结构具有三个弱点： 21. 设单链表结点指针域为next，试写出删除链表中指针p所指结点的直
接后继的C语言语句 。 22. a、b为单链表中的两个相邻结点（如图），已知p为指向结点a的指
针，s为指向结点x的指针。试写出在a、b之间插入一个结点x的语句： p a b
s x 23. 设计一个算法，求一个单链表中的结点个数。 设有一线性表e=(e1 , e2 , … , en-1 , en)，其逆线性表定义为e'=( en , en-1 , … , e2 , e1)，请设计一个算法，将线性表置逆，要求逆线性表仍占用原线性表的空间，并且用顺序表和单链表两种方法来表示，写出不同的处理函数。 第三章
第 页 （ 共 8 页 ） 2
1. 对栈操作数据的原则是（ ）。
A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序
2. 设abcdef以所给的次序进栈，若在进栈操作时，允许退栈操作,则下
面得不到的序列为（ ）。
A．fedcba B. bcafed C. dcefba D. cabdef
3. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第
i（1<=i<=n）个元素是（ ）。
A. 不确定 B. n-i+1 C. i D. n-i 4. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（ ）
的数据结构。
A．队列 B．多维数组 C．栈 D. 线性表
5. 用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾
指针指向队尾结点，则在进行删除操作时( )。 A．仅修改队头指针 B. 仅修改队尾指针
C. 队头、队尾指针都要修改 D. 队头,队尾指针都可能要修改
6. 假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和
rear，则当前队列中的元素个数为（ ）。 A.(rear-front+m)%m B.rear-front+1 C.(front-rear+m)%m D．(rear-front)%m 7. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值
分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( )
A. 1和 5 B. 2和4 C. 4和2 D. 5和1 8. 栈和队列的共同点是（ ）。
A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点
9. 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次
通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是( )。 A． 6 B. 4 C. 3 D. 2 10.请写出循环队列和顺序队列队空和队满的条件。 第四章
1. 下面关于串的的叙述中，哪一个是不正确的？（ ）
A．串是字符的有限序列 B．空串是由空格构成的串
第 页 （ 共 8 页 ） 3
C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储
2. 串的长度是指（ ）
A．串中所含不同字母的个数 B．串中所含字符的个数
C．串中所含不同字符的个数 D．串中所含非空格字符的个数 3. 串是一种特殊的线性表，其特殊性表现在__ __；两个串相等的充分
必要条件是__ _ _。 第五章
1. 设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，
a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）。 A. 13 B. 33 C. 18 D. 40
2. 若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对
角线上所有元素)依次存放于一维数组B［1..(n(n+1))/2］中，则在B中确定aij（i 3. 对稀疏矩阵进行压缩存储目的是（ ）。 A．便于进行矩阵运算B．便于输入和输出C．节省存储空间D.降低运算的时间复杂度 4. 广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为（ ） Head(Tail(Head(Tail(Tail(A))))) A. (g) B. (d) C. c D. d 5. 下面说法不正确的是( )。 A. 广义表的表头总是一个广义表 B. 广义表的表尾总是一个广义表 C. 广义表难以用顺序存储结构 D. 广义表可以是一个多层次的结构 6．广义表(a,(a,b),d,e,((i,j),k))的长度是 _，深度是 _。 第六章 树 1．设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ ） A．5 B．6 C．7 D．8 2．在下述结论中，正确的是（ ） ①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树 第 页 （ 共 8 页 ） 4 的左右子树可任意交换;④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A．①②③ B．②③④ C．②④ D．①④ 3．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ） A．9 B．11 C．15 D．不确定 4．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1， M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（ ）。 A．M1 B．M1+M2 C．M3 D．M2+M3 5．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ） A． 250 B． 500 C．254 D．505 E．以上答案都不对 6. 有n个叶子的哈夫曼树的结点总数为（ ） A．不确定 B．2n C．2n+1 D．2n-1 7．一棵具有 n个结点的完全二叉树的树高度（深度）是（ ） A．nlog2n B．log2n C．log2n+1 D．不确定 8．利用二叉链表存储树，则根结点的右指针是（ ） A．指向最左孩子 B．指向右兄弟 C．空 D．非空 9．在下列存储形式中，哪一个不是树的存储形式？（ ） A．双亲表示法 B．孩子链表表示法 C．孩子兄弟表示法 D．顺序存储表示法 10．n个结点的线索二叉树上含有的线索数为（ ） A．2n B．n－l C．n＋l D．n 11．二叉树由_(1)__，__(2)_，_(3)__三个基本单元组成 12．深度为k的完全二叉树至少有___(1)____个结点，至多有___(2)____个结点。 13．假设根结点的层数为１，具有ｎ个结点的二叉树的最大高度是______。 14．已知一棵二叉树的前序序列为abdecfhg,中序序列为dbeahfcg，画出该树。 15．度为2的树和二叉树之间有什么样的区别与联系？ 16．列出树的四种表示方法。 17．给定叶结点（a，b，c，d，e，f，g），分别带权（23，12，15，7，17，2，8），画出对应的哈夫曼树并确定各点的哈夫曼编码。 18、有森林如下： g a e b 第 页 （ 共 8 页 ） 5 c f h i j d k L （1）将森林转换成对应的二叉树。 （2）写出按先序、中序、后序和层序对二叉树遍历所得到的结点序列。 （3）请用C语言描述二叉链表存储结构。 第七章 图 1、对N个顶点的连通图来说，它的生成树一定有 条边。 2、在一个有向图中，所有顶点的入度与出度之和等于顶点总数的 倍。 3、在一棵平衡二叉树中，每个结点的平衡因子的取值范围是 。 4、Dijkstra最短路径算法从源点到其余各顶点的最短路径的路径长度按 ___ ___次序依次产生，Dijkstra算法的时间复杂度为 。 5、Prim（普里姆）算法适用于求______的网的最小生成树，算法的时间复 杂度为______。kruskal（克鲁斯卡尔）算法适用于求______的网的最小生成树，算法的时间复杂度为______。 6、为了实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点 外，还需______数据结构存放被访问的结点以实现遍历。如果采用飞递归算法求图的深度优先搜索，需______数据结构存放被访问的结点 以实现遍历。如果一个人去旅游，为了使换车中转次数最少，可采用 遍历实现。 7、AOV网中,结点表示______,边表示______。AOE网中,结点表示______, 边表示______。 8、当一个AOV网用邻接表表示时，可按下列方法进行拓扑排序。 （1）．查邻接表中入度为______的顶点，并进栈； （2）．若栈不空，则①输出栈顶元素Vj，并退栈；②查Vj的直接后继 Vk，对Vk入度处理，处理方法是______； （3）．若栈空时，输出顶点数小于图的顶点数，说明有______，否则拓 扑排序完成。 9、设有向图有n个顶点和e条边，进行拓扑排序时，总的计算时间为______。 10、已知一个图的顶点集（G）和边集（V）分别为： G={0，1，2，3，4，5，6，7，8} V={<0，1>，<0，2>，<1，3>，<1，4>，<2，4>，<2，5>， <3，6>，<3，7>，<4，7>，<4，8>，<5，7>，<6，7>，<7，8>} （1） 画出该图。 （2） 请画出此图邻接表、逆邻接表和邻接矩阵的图示。 （3） 从结点2出发得到的DFS序列及BFS序列。 第 页 （ 共 8 页 ） 6 （4） 从结点2出发得到的DFS生成树（或者生成森林）及BFS生成树（或 者生成森林）。 （5）此图能否进行拓扑排序？若能，请你写出一种拓扑排序序列。 （6）找出图中所有的强连通分量。 11、请简述单源点最短路径中迪杰斯特拉（Dijstra）算法的思想。 18 12、求下图的一棵最小生成树。 5 2 1 23 6 12 4 8 7 5 15 3 25 7 10 4 6 20 第九章 1、与其他查找方法相比，散列查找方法的特点是（ ）。 A）通过关键字的比较进行查找 B）通过关键字计算元素的存储地址进行查找 C）通过关键字计算元素的存储地址并进行一定的比较进行查找 D）以上都不是 3、二分法查找如果成功时的平均查找长度ASLbs是多少（ ）。 A）log2（n＋1）－1 B）log2（n＋1） C）（n＋1）/2 D）nlogn 4、 选取哈希函数H（k）＝（3k）MOD11。用开放定址法处理冲突， di＝i（（7k）MOD10＋1）（i＝1，2，3，…）。试在0～10的散列地址空间中对关键字序列（22，41，53，46，30，13，01，67）造哈希表，并求等概率情况下查找成功时的平均查找长度。 5、 一个线性表中的关键字序列为（12，23，45，57，20，03，78，31， 15，36），哈希函数为H（key）= key % 13，并用链地址法解决冲突，请画出依次插入线性表中各关键值后的链表，并计算等概率情况下查找成功的平均查找长度。 6、 将关键字（53，78，65，17，87，09，81，45，23）依次入到一棵初 始为空的二叉排序树中，画出对应的二叉排序树，并计算此二叉树在查找成功和不成功时的平均查找长度。 7．解释：哈希冲突 第十章 在插入排序、堆排序、快速排序、选择排序和归并排序中，平均比较次数最少的是 。 每次从无序子表中选出一个最大或最小元素，把它交换到有序子表的一端，此种排序方法叫做 排序。 每次使两个相邻的有序表合并成一个有序表的排序方法叫 第 页 （ 共 8 页 ） 7 排序。 选择题： 1、归并排序的时间复杂度为（ ）。 A）O（nlog2n） B）O（n2） C）O（n） D）O（2n） 2、对于12个记录的序列，采用冒泡排序最少的比较次数是（ ）。 A）1 B）144 C）11 D）66 3、下列4种排序方法中，要求内存容量最大的是（ ）。 A）插入排序 B）选择排序 C）快速排序 D）归并排序 应用题 1、 已知序列{503，87，512，61，908，170，897，275，653，462}，请 给出采用堆排序对该序列作升序排序时的每一趟结果。 2、 已知序列{503,87,512,61,908,170,897,275,653,462},请给出采用快 速排序法对该序列作升序排序时的每一趟结果及排序的最终结果。 程序设计题 1、编写算法，对n个关键字取整数值的记录进行整理，以使所有关键字为负的记录排在关键字为非负值的记录之前。要求： （1）、采用顺序存储结构，至多使用一个记录的辅助存储空间； （2）、算法的时间复杂度为O（n）； （3）、讨论算法中记录的最大移动次数。 第 页 （ 共 8 页 ） 8 因篇幅问题不能全部显示，请点此查看更多更全内容