上海对外经贸大学《数据结构》试卷（A卷）
专业班级?????????????姓名?????????????????学号
题号
一
二
三
四
五
六
七
八
九
十
成绩
复核签字
得分
登分签字
说明：本试卷共大题，共100分；答题要求：按要求答题
考生须知:
1.姓名、学号、系、专业、年级、班级必须写在密封线内指定位置。
2.答案必须用蓝、黑色钢笔或圆珠笔写在试卷上，字迹要清晰，卷面要整洁，写在草稿纸上的一律无效。
一、单项选择题（每题2分，共30分）
数据结构中，与所使用的计算机无关的是数据的（）结构。
A.存储
B.物理
C.逻辑
D.物理和存储
线性表采用链式存储时，其地址（）。
A.必须是连续的
B.部分地址必须是连续的
C.一定是不连续的
D.连续与否均可以
若进栈序列为1，2，3，4，进栈过程中可以出栈，则下列不可能的一个出栈序列是（）。
A.1，4，3，2
B.2，3，4，1
C.3，1，4，2
D.3，4，2，1
队列的“先进先出”特性是指（）。
A.最早插入队列中的元素总是最后被删除
B.当同时进行插入、删除操作时，总是插入操作优先
C.每当有删除操作时，总是要先做一次插入操作
D.每次从队列中删除的总是最早插入的元素
一个栈的入栈序列是a，b，c，d，e，则栈的不可能的输出序列是（）。
A.edcba
B.decba
C.dceab
D.abcde
循环队列存储在数组A[0..m]中，则入队时的操作为（）。
A.rear=rear+1
B.rear=(rear+1)mod(m-1)
C.rear=(rear+1)modm
D.rear=(rear+1)mod(m+1)
对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（）。
A.O(n)O(n)
B.O(n)O(1)
C.O(1)O(n)
D.O(1)O(1)
设某棵二叉树中只有度为0和度为2的结点且度为0的结点数为n，则这棵二叉中共有（）个结点。
A.2n
B.n+1
C.2n-1
D.2n+1
深度为5的二叉树至多有（）个结点。
A.16
B.32
C.31
D.10
具有10个叶结点的二叉树中有（）个度为2的结点。
A.8
B.9
C.10
D.11
二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法（）。
A.正确
B.错误
C.不一定
D.以上都不对
对n个记录的文件进行快速排序，所需要的辅助存储空间大致为（）。
A.O(1)
B.O(n)
C.O(logn)
D.O(n^2)
已知一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100}，当用折半查找值为82的元素时，（）次比较后查找成功。
A.1
B.2
C.4
D.8
哈希表的平均查找长度与处理冲突的方法有关，这种说法（）。
A.正确
B.错误
C.不一定
D.以上都不对
对线性表进行二分查找时，要求线性表必须（）。
A.以顺序方式存储
B.以链式方式存储
C.以顺序方式存储，且数据元素有序
D.以链式方式存储，且数据元素有序
二、多项选择题（每题3分，共15分）
数据结构的存储结构包括（）。
A.顺序存储
B.链式存储
C.索引存储
D.散列存储
以下关于栈和队列的说法正确的是（）。
A.栈是一种后进先出的线性表
B.队列是一种先进先出的线性表
C.栈和队列都是线性结构
D.栈和队列都可以用顺序存储结构和链式存储结构实现
二叉树的遍历方式有（）。
A.前序遍历
B.中序遍历
C.后序遍历
D.层次遍历
排序算法的稳定性是指（）。
A.经过排序之后，能使值相同的数据保持原顺序中的相对位置不变
B.经过排序之后，能使值相同的数据保持原顺序中的绝对位置不变
C.算法的排序性能与被排序元素的数量关系不大
D.算法的排序性能与被排序元素的数量关系密切
下列属于查找算法的有（）。
A.顺序查找
B.二分查找
C.哈希查找
D.插入排序
三、判断题（每题1分，共10分）
数据元素是数据的最小单位。（）
线性表的顺序存储结构优于链式存储结构。（）
栈和队列都是限制存取点的线性结构。（）
完全二叉树一定是满二叉树。（）
二叉树的中序遍历序列中，根结点一定在其左子树结点之后，右子树结点之前。（）
快速排序在任何情况下的时间复杂度都是O(nlogn)。（）
堆排序是一种稳定的排序算法。（）
哈希表是一种基于关键字直接访问的数据结构。（）
对链表进行插入和删除操作时，不需要移动元