《数据结构》模拟卷
一、选择题
1. 在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（ ）。
A. O(n) B. O(n/2) C. O(1) D. O(n2)
2. 带头结点的单链表first为空的判定条件是：（ ）。
A. first == NULL; B. first->link == NULL;
C. first->link == first; D. first != NULL;
3. 从逻辑上可以把数据结构分为（ ）两大类。
A．动态结构、静态结构 B．顺序结构、链式结构
C．线性结构、非线性结构 D．初等结构、构造型结构
4. 在系统实现递归调用时需利用递归工作记录保存实际参数的值。在传值参数情形，需为对应形式参数分配空间，以存放实际参数的副本；在引用参数情形，需保存实际参数的（ ），在被调用程序中可直接操纵实际参数。
A. 空间 B. 副本 C. 返回地址 D. 地址
5. 以下数据结构中，哪一个是线性结构（ ）。
A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串
6. 以下属于逻辑结构的是（ ）。
A．顺序表 B. 哈希表 C.有序表 D. 单链表
7. 对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为（ ）的值除以9。
A. 20 B. 18 C. 25 D. 22
8. 在有向图中每个顶点的度等于该顶点的（ ）。
A. 入度 B. 出度
C. 入度与出度之和 D. 入度与出度之差
9. 在基于排序码比较的排序算法中，（ ）算法的最坏情况下的时间复杂度不高于O(nlog2n)。
A. 起泡排序 B. 希尔排序 C. 归并排序 D. 快速排序
10. 当α的值较小时，散列存储通常比其他存储方式具有（ ）的查找速度。
A. 较慢 B. 较快 C. 相同 D.不同
二、填空题
1. 二维数组是一种非线性结构，其中的每一个数组元素最多有_________个直接前驱（或直接后继）。
2. 将一个n阶三对角矩阵A的三条对角线上的元素按行压缩存放于一个一维数组B中，A[0][0]存放于B[0]中。对于任意给定数组元素B[K]，它应是A中第_________行的元素。
3. 链表对于数据元素的插入和删除不需移动结点，只需改变相关结点的________域的值。
4. 在一个链式栈中，若栈顶指针等于NULL则为________。
5. 主程序第一次调用递归函数被称为外部调用，递归函数自己调用自己被称为内部调用，它们都需要利用栈保存调用后的_________地址。
6. 在一棵树中，______结点没有后继结点。
7. 一棵树的广义表表示为a (b (c, d (e, f), g (h) ), i (j, k (x, y) ) )，结点f的层数为______。假定根结点的层数为0。
8. 在一棵AVL树（高度平衡的二叉搜索树）中，每个结点的左子树高度与右子树高度之差的绝对值不超过________。
9. n (n﹥0) 个顶点的无向图最多有________条边，最少有________条边。
10. 在索引存储中，若一个索引项对应数据对象表中的一个表项（记录），则称此索引为________索引，若对应数据对象表中的若干个表项，则称此索引为________索引。
三、判断题
1. 数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的( )
2. 链式存储在插入和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序( )
3. 在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针( )
4. 通常递归的算法简单、易懂、容易编写，而且执行的效率也高( )
5. 一个广义表的表尾总是一个广义表( )
6. 当从一个小根堆（最小堆）中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止( )
7. 对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O(h)( )
8. 存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关( )
9. 直接选择排序是一种稳定的排序方法( )
10. 闭散列法通常比开散列法时间效率更高( )
四、运算题
1. 设有一个1010的对称矩阵A，将其下三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么A[8][5]存放于B中什么位置。
2. 这是一个统计单链表中结点的值等于给定值x的结点数的算法，其中while循环有错，请重新编写出正确的while循环。
int count ( ListNode * Ha, ElemType x )
{ // Ha为不带头结点的单链表的头指针
int n = 0;
while ( Ha->link != NULL ) {
Ha = Ha->link;
if ( Ha->data == x ) n++;
}
return n;
}
3. 已知一棵二叉树的前序和中序序列，求该二叉树的后序序列。
前序序列：A, B, C, D, E, F, G, H, I, J
中序序列：C, B, A, E, F, D, I, H, J, G
后序序列：
4. 已知一个有序表 ( 15, 26, 34, 39, 45, 56, 58, 63, 74, 76, 83, 94 ) 顺序存储于一维数组a[12]中，根据折半搜索过程填写成功搜索下表中所给元素34, 56, 58, 63, 94时的比较次数。
元素值
比较次数
5. 设散列表为HT[17], 待插入关键码序列为 { Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec }，散列函数为H (key) = i 2，其中，i是关键码第一个字母在字母表中的序号。现采用线性探查法解决冲突。
字母 A B C D E F G H I J K L M
序号 1 2 3 4 5 6 7 8 9 10 11 12 13
字母 N O P Q R S T U V W X Y Z
序号 14 15 16 17 18 19 20 21 22 23 24 25 26
(1) 试画出相应的散列表；
(2) 计算等概率下搜索成功的平均搜索长度；
参考答案：
1. 根据题意，矩阵A中当元素下标I与J满足I≥J时，任意元素A[I][J]在一维数组B中的存放位置为I * (I + 1) / 2 + J，因此，A[8][5]在数组B中位置为
8 * (8 + 1) / 2 + 5 = 41。
2.
while ( Ha != NULL ) {
if ( Ha->data == x ) n++;
Ha = Ha->link;
}
3. 后序序列：C, B, F, E, I, J, H, G, D, A
4. 判断结果
元素值
比较次数 //对1个给1分，全对给8分
5.
H(Jan) = 102 = 5，成功. H(Feb) = 62 = 3，成功.
H(Mar) = 132 = 6，成功. H(Apr) = 12 = 0，成功.
H(May) = 132 = 6，= 7，成功， H(June) = 102 = 5，= 6，= 7，=8，成功.
H(July) = 102 = 5，= 6，= 7，= 8，= 9，成功.
H(Aug) = 12 = 0，= 1，成功. H(Sep) = 192 = 9，= 10，成功.
H(Oct) = 152 = 7，= 8，= 9，= 10，= 11，成功.
H(Nov) = 142 = 7，= 8，= 9，= 10，= 11，= 12，成功.
H(Dec) = 42 = 2，成功.
(1) 相应的散列表(6分)，错一个存储位置扣1分，最多扣6分。
0 1 2 3 4 5 6 7 8 9 10 11 12 13
Apr Aug Dec Feb Jan Mar May June July Sep Oct Nov
(1) (2) (1) (1) (1) (1) (2) (4) (5) (2) (5) (6)
(2) 搜索成功的平均搜索长度为
1/12 * (1 + 2 + 1 + 1 + 1 + 1 + 2 + 4 + 5 + 2 + 5 + 6) = 31 / 12 （2分）
五、算法设计题
已知二叉树中的结点类型用BinTreeNode表示，被定义为:
struct BTreeNode { char data; BinTreeNode *leftChild, *rightChild; };其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域，根据下面函数声明编写出求一棵二叉树中结点总数的算法，该总数值由函数返回。假定参数BT初始指向这棵二叉树的根结点。
int BTreeCount ( BinTreeNode* BT );
一、选择题
1. 在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（ ）。
A. O(n) B. O(n/2) C. O(1) D. O(n2)
2. 带头结点的单链表first为空的判定条件是：（ ）。
A. first == NULL; B. first->link == NULL;
C. first->link == first; D. first != NULL;
3. 从逻辑上可以把数据结构分为（ ）两大类。
A．动态结构、静态结构 B．顺序结构、链式结构
C．线性结构、非线性结构 D．初等结构、构造型结构
4. 在系统实现递归调用时需利用递归工作记录保存实际参数的值。在传值参数情形，需为对应形式参数分配空间，以存放实际参数的副本；在引用参数情形，需保存实际参数的（ ），在被调用程序中可直接操纵实际参数。
A. 空间 B. 副本 C. 返回地址 D. 地址
5. 以下数据结构中，哪一个是线性结构（ ）。
A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串
6. 以下属于逻辑结构的是（ ）。
A．顺序表 B. 哈希表 C.有序表 D. 单链表
7. 对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为（ ）的值除以9。
A. 20 B. 18 C. 25 D. 22
8. 在有向图中每个顶点的度等于该顶点的（ ）。
A. 入度 B. 出度
C. 入度与出度之和 D. 入度与出度之差
9. 在基于排序码比较的排序算法中，（ ）算法的最坏情况下的时间复杂度不高于O(nlog2n)。
A. 起泡排序 B. 希尔排序 C. 归并排序 D. 快速排序
10. 当α的值较小时，散列存储通常比其他存储方式具有（ ）的查找速度。
A. 较慢 B. 较快 C. 相同 D.不同
二、填空题
1. 二维数组是一种非线性结构，其中的每一个数组元素最多有_________个直接前驱（或直接后继）。
2. 将一个n阶三对角矩阵A的三条对角线上的元素按行压缩存放于一个一维数组B中，A[0][0]存放于B[0]中。对于任意给定数组元素B[K]，它应是A中第_________行的元素。
3. 链表对于数据元素的插入和删除不需移动结点，只需改变相关结点的________域的值。
4. 在一个链式栈中，若栈顶指针等于NULL则为________。
5. 主程序第一次调用递归函数被称为外部调用，递归函数自己调用自己被称为内部调用，它们都需要利用栈保存调用后的_________地址。
6. 在一棵树中，______结点没有后继结点。
7. 一棵树的广义表表示为a (b (c, d (e, f), g (h) ), i (j, k (x, y) ) )，结点f的层数为______。假定根结点的层数为0。
8. 在一棵AVL树（高度平衡的二叉搜索树）中，每个结点的左子树高度与右子树高度之差的绝对值不超过________。
9. n (n﹥0) 个顶点的无向图最多有________条边，最少有________条边。
10. 在索引存储中，若一个索引项对应数据对象表中的一个表项（记录），则称此索引为________索引，若对应数据对象表中的若干个表项，则称此索引为________索引。
三、判断题
1. 数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的( )
2. 链式存储在插入和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序( )
3. 在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针( )
4. 通常递归的算法简单、易懂、容易编写，而且执行的效率也高( )
5. 一个广义表的表尾总是一个广义表( )
6. 当从一个小根堆（最小堆）中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止( )
7. 对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O(h)( )
8. 存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关( )
9. 直接选择排序是一种稳定的排序方法( )
10. 闭散列法通常比开散列法时间效率更高( )
四、运算题
1. 设有一个1010的对称矩阵A，将其下三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么A[8][5]存放于B中什么位置。
2. 这是一个统计单链表中结点的值等于给定值x的结点数的算法，其中while循环有错，请重新编写出正确的while循环。
int count ( ListNode * Ha, ElemType x )
{ // Ha为不带头结点的单链表的头指针
int n = 0;
while ( Ha->link != NULL ) {
Ha = Ha->link;
if ( Ha->data == x ) n++;
}
return n;
}
3. 已知一棵二叉树的前序和中序序列，求该二叉树的后序序列。
前序序列：A, B, C, D, E, F, G, H, I, J
中序序列：C, B, A, E, F, D, I, H, J, G
后序序列：
4. 已知一个有序表 ( 15, 26, 34, 39, 45, 56, 58, 63, 74, 76, 83, 94 ) 顺序存储于一维数组a[12]中，根据折半搜索过程填写成功搜索下表中所给元素34, 56, 58, 63, 94时的比较次数。
元素值
比较次数
5. 设散列表为HT[17], 待插入关键码序列为 { Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec }，散列函数为H (key) = i 2，其中，i是关键码第一个字母在字母表中的序号。现采用线性探查法解决冲突。
字母 A B C D E F G H I J K L M
序号 1 2 3 4 5 6 7 8 9 10 11 12 13
字母 N O P Q R S T U V W X Y Z
序号 14 15 16 17 18 19 20 21 22 23 24 25 26
(1) 试画出相应的散列表；
(2) 计算等概率下搜索成功的平均搜索长度；
参考答案：
1. 根据题意，矩阵A中当元素下标I与J满足I≥J时，任意元素A[I][J]在一维数组B中的存放位置为I * (I + 1) / 2 + J，因此，A[8][5]在数组B中位置为
8 * (8 + 1) / 2 + 5 = 41。
2.
while ( Ha != NULL ) {
if ( Ha->data == x ) n++;
Ha = Ha->link;
}
3. 后序序列：C, B, F, E, I, J, H, G, D, A
4. 判断结果
元素值
比较次数 //对1个给1分，全对给8分
5.
H(Jan) = 102 = 5，成功. H(Feb) = 62 = 3，成功.
H(Mar) = 132 = 6，成功. H(Apr) = 12 = 0，成功.
H(May) = 132 = 6，= 7，成功， H(June) = 102 = 5，= 6，= 7，=8，成功.
H(July) = 102 = 5，= 6，= 7，= 8，= 9，成功.
H(Aug) = 12 = 0，= 1，成功. H(Sep) = 192 = 9，= 10，成功.
H(Oct) = 152 = 7，= 8，= 9，= 10，= 11，成功.
H(Nov) = 142 = 7，= 8，= 9，= 10，= 11，= 12，成功.
H(Dec) = 42 = 2，成功.
(1) 相应的散列表(6分)，错一个存储位置扣1分，最多扣6分。
0 1 2 3 4 5 6 7 8 9 10 11 12 13
Apr Aug Dec Feb Jan Mar May June July Sep Oct Nov
(1) (2) (1) (1) (1) (1) (2) (4) (5) (2) (5) (6)
(2) 搜索成功的平均搜索长度为
1/12 * (1 + 2 + 1 + 1 + 1 + 1 + 2 + 4 + 5 + 2 + 5 + 6) = 31 / 12 （2分）
五、算法设计题
已知二叉树中的结点类型用BinTreeNode表示，被定义为:
struct BTreeNode { char data; BinTreeNode *leftChild, *rightChild; };其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域，根据下面函数声明编写出求一棵二叉树中结点总数的算法，该总数值由函数返回。假定参数BT初始指向这棵二叉树的根结点。
int BTreeCount ( BinTreeNode* BT );
版权声明
声明：有的资源均来自网络转载，版权归原作者所有，如有侵犯到您的权益
请联系本站我们将配合处理！
上一篇 : 山东大学20年春季《招聘与筛选》（C）辅导