1. 算法指的是....................................( ) A.计算机程序 B.解决问题的计算方法
C.排序算法 D.解决问题的有限运算序列
2. 线性表采用链式存储时，结点的存储地址..........( ) A.必须是不连续的 B.连续与否均可
C.必须是连续的 D.和头结点的存储地址相连续 3. 如下描述正确的是..............................( ) A.串是一种特殊的线性表 B.串的长度必须大于零 C.串中元素只能是字母 D.空串就是空白串
4. 一个非空广义表的表头..........................( ) A.不可能是子表 B.只能是子表
C.只能是原子 D.可以是子表或原子
5. 在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为....( )
A.4 B.5 C.6 D.7
6. 用某种排序方法对关键字序列（25,84,21,47,15,27,68,35,20）进行排序时，序列的变化情况如下：
25, 84, 21, 47, 15, 27, 68, 35, 20 20, 84, 21, 47, 15, 27, 68, 35, 25 20, 25, 21, 47, 15, 27, 68, 35, 84 20, 15, 21, 47, 25, 27, 68, 35, 84 20, 15, 21, 25, 47, 27, 68, 35, 84 [20, 15, 21],25,[47, 27, 68, 35, 84] 15, 20, 21, 25,[35, 27, 68, 47, 84] 15, 20, 21, 25,[35, 27, 47, 68, 84] 15, 20, 21, 25,[35, 27,]47,[68, 84]
15, 20, 21, 25, 27, 35, 47, 68, 84 则采用的排序方法是..........................( ) A.选择排序 B.希尔排序 C.冒泡排序 D.快速排序
7. 适用于对动态查找表进行高效率查找的组织结构是......................................( ) A.有序表 B.分块有序表 C.二叉排序树 D.线性链表
8. 数据结构中，与所使用的计算机无关的是数据的______结构 A.存储 B.物理 C.逻辑 D.逻辑和存储
9. 若某线性表最常用的操作是取第i个元素和找第i个元素的直接前驱元素，则采用________存储方式最节省运算时间
A.顺序表 B.单链表 C.双链表 D.单循环链表
10. 若编号为1,2,3,4,5,6的六节车厢依次通过一段栈形轨道，则在出口处不可能得到
____的次序。
A.143562 B.456321 C.145326 D.426531
11. 在计算递归函数时，若不用递归则应借助数据结构......................................( ) A.数组 B.队列 C.链表 D.栈
12. 二维数组A[0..9, 0..10] 采用行优先的存储方法，若每个元素各占3个存储单元且A[0,0] 的地址为200，则A[6,9] 的地址为( )
A.422 B.425 C.428 D.431
13. 线性表是..........................................................................( ) A.一个有限序列，可以为空 B.一个有限序列，不能为空
C.一个无限序列，可以为空 D.一个无序序列，不能为空
14. 稀疏矩阵一般的压缩存储方法有两种，即..............................................( ) A.二维数组和三维数组 B.三元组和散列
C.三元组表和十字链表 D.散列和十字链表
14. 用链表表示线性表的优点是..........................................................( ) A.便于随机存取 B.花费的存储空间较顺序存储少
C.便于插入和删除 D.数据元素的物理顺序与逻辑顺序相同
15. 利用双向链表作线性表的存储结构的优点是............................................( ) A.便于进行插入和删除的操作 B.提高按关系查找数据元素的速度 C.节省空间 D.便于销毁结构释放空间
二、填空题 30% 共15题，每题2分
1. 数据的逻辑结构是从逻辑关系上描述数据，它与数据的 存储（或存储结构） 无关，是独立于计算机的。
2. 在一个带头结点的单向循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head= p->next->next 。 3. 栈顶的位置是随着 进栈和退栈 操作而变化的。
4. 在串S=\" Structure\"中，以t为首字符的子串有 12 个。
5. 已知一棵完全二叉树中共有768个结点，则该树中共有 384 个叶子结点。 6. 已知一个图的广度优先生成树如下图所示，则与此相应的广度优先遍历序列为 abefcdg 。
7. 在有序表(12, 24, 36, 48, 60, 72, 84)中二分查找关键字72时所需进行的关键字比较次数为 2 。
8. 线性表、栈和队列都是 线性 结构，可以线性表的 任意 位置插入和删除元素，对于栈只能在 栈顶 位置插入和删除元素，对于队列只能在 队尾 位置插入和 队头 位置删除元素。
9. 设字符串S='abbbabbc'，T='bb'，R='b'，则转换操作 REPLACE(S,T,R)的执行结果是S= 'abbabc' 。
10. 如下图所示，请写出前序遍历 abcdfg ，中序遍历 cbdagf ，后序遍历 cdbgfa 。 11. 顺序表是一种 随机存取 结构。
12. 二叉搜索树又称二叉排序树或称二叉查找树。它或者是一棵空树，或者是一棵具有下列特性的非空二叉树：若它的左子树非空，则子左树上所有结点的值均小于 根结点 的值。若它的右子树非空，则右子树上所有结点的值均 大于 根结点的值。
13. 哈夫曼树 又称最优二叉树。是n个带权叶子结点构成的所有二叉树中 带权路径长度最小 的二叉树。
14. 顺序检索方法适用于线性表的 顺序存储结构，也适用于线性表的链式存储结构。效率较高的检索方法是 折半检索或(二分检索)。分块检索又称索引顺序检索，是一种介于顺序检索与折半检索之间的检索方法。
15. 哈希(Hash)检索技术中的哈希函数采用方法有：直接定址法、除留余数法、数字分析法、折叠法、平方取中法等五种。 三、简答题 25% 共3题，每题5分
现有如下的稀疏矩阵A(如下所示)，要求画出三元组表示法 5% 15 0 0 22 0 -15 0 13 3 0 0 0
0 0 0 -6 0 0 0 0 0 0 0 0 91 0 0 0 0 0 0 0 28 0 0 0
2. 带权有向图(下图)，根据从顶点A到其它各顶点的最短路径，给出网的带权邻接矩阵，并给出每个顶点的入度和出度。 10%
3. 对关键字序列{5，4，2，8，6}建立一棵平衡二叉检索树（画出过程） 10%
四、算法阅读题 15% 共1题
1. 以下给出的算法：在一个链表中插入一个结点，请以空白处填入适当的内容
insert(p，x) /*将值为x的新结点插入*p之后*/ linklist *p； elemtp x； {linklist *s；
s=_________； malloc(sizeof(linklist))； ___________； s->data=x； ___________； s->next=p->next； p->next=s；} 简答题答案： 1. 答： I j v 0 0 15 0 3 22
0 5 -15 1 1 13 1 2 3 2 3 -6 4 0 91 5 2 28
答：
0 ∞ 2 10 ∞ 40 ∞ A顶点入度1 出度3 9 0 ∞ ∞ ∞ ∞ ∞ B顶点入度1 出度1 ∞ 1 0 6 20 ∞ ∞ C顶点入度1 出度3 A= ∞ ∞ ∞ 0 5 8 ∞ D顶点入度3 出度2 ∞ ∞ ∞ ∞ 0 ∞ ∞ E顶点入度2 出度0 ` ∞ ∞ ∞ ∞ ∞ 0 ∞ F顶点入度2 出度0 ∞ ∞ ∞ 17 ∞ ∞ 0 G顶点入度0 出度1 4 5 2 2 4 5
3. a. b. 右旋转一次 c. 4 5
2 8 5 8 2 6 4 6
d. 左旋转一次得结果
因篇幅问题不能全部显示，请点此查看更多更全内容