杭州电子科技大学大二计算机专业数据结构试卷及答案.docx
杭州电子科技大学大二计算机专业数据结构试卷及答案
一、选择题（每题2分，共30分）
1.数据结构是一门研究非数值计算的程序设计问题中计算机的（）以及它们之间的关系和运算等的学科。
A.数据元素
B.计算方法
C.逻辑存储
D.数据映像
答案：A
解析：数据结构研究的是数据元素、数据元素之间的关系以及相关运算。计算方法主要侧重于数值计算的算法；逻辑存储表述不准确；数据映像是数据在存储介质上的表示方式，不是数据结构研究的核心内容，所以选A。
2.以下说法正确的是（）。
A.数据项是数据的基本单位
B.数据元素是数据的最小单位
C.数据结构是带有结构的数据元素的集合
D.数据的逻辑结构反映了数据在计算机中的存储方式
答案：C
解析：数据元素是数据的基本单位，数据项是数据元素的组成部分，是数据的最小单位，所以A、B错误；数据的逻辑结构是指数据元素之间的逻辑关系，与数据在计算机中的存储方式无关，存储方式是物理结构，D错误；数据结构是带有结构的数据元素的集合，C正确。
3.线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。
A.必须是连续的
B.部分地址必须是连续的
C.一定是不连续的
D.连续或不连续都可以
答案：D
解析：链式存储结构通过指针来表示元素之间的逻辑关系，不要求内存中可用存储单元的地址是连续的，连续或不连续都可以，所以选D。
4.栈和队列的共同点是（）。
A.都是先进先出
B.都是先进后出
C.只允许在端点处插入和删除元素
D.没有共同点
答案：C
解析：栈是先进后出，队列是先进先出，A、B错误；栈只允许在栈顶进行插入和删除操作，队列只允许在队尾插入，队头删除，它们都只允许在端点处插入和删除元素，C正确，D错误。
5.若串S=“software”，其子串的数目是（）。
A.8
B.37
C.36
D.9
答案：B
解析：对于长度为n的串，其子串数目为\(n(n+1)/2+1\)（包含空串）。这里\(n=8\)，则子串数目为\(8\times(8+1)/2+1=36+1=37\)，所以选B。
6.一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为（）。
A.219
B.221
C.229
D.231
答案：A
解析：根据二叉树的性质，\(n_0=n_2+1\)（\(n_0\)为叶子结点数，\(n_2\)为度为2的结点数），已知\(n_0=70\)，则\(n_2=n_01=69\)。总结点数\(n=n_0+n_1+n_2=70+80+69=219\)，所以选A。
7.已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（）。
A.acbed
B.decab
C.deabc
D.cedba
答案：D
解析：后序遍历的最后一个元素是根节点，所以根节点是c；在中序遍历中找到c，c左边的是左子树的中序遍历序列（deba），右边为空；根据左子树的中序遍历序列和后序遍历序列（dabe）可确定左子树的根节点是e，以此类推构建出二叉树，其前序遍历序列是cedba，所以选D。
8.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A[3]的比较序列的下标依次为（）。
A.1，2，3
B.9，5，2，3
C.9，5，3
D.9，4，2，3
答案：D
解析：二分查找的基本思想是每次将待查找区间缩小一半。初始区间是\([1,18]\)，中间元素下标为\((1+18)/2=9\)；因为\(A[3]A[9]\)，所以新的区间是\([1,8]\)，中间元素下标为\((1+8)/2=4\)；因为\(A[3]A[4]\)，新的区间是\([1,3]\)，中间元素下标为\((1+3)/2=2\)；因为\(A[3]A[2]\)，新的区间是\([3,3]\)，找到元素，所以比较序列的下标依次为9，4，2，3，选D。
9.对线性表进行折半查找时，要求线性表必须（）。
A.以顺序方式存储
B.以链式方式存储
C.以顺序方式存储，且结点按关键字有序排序
D.以链式方式存储，且结点按关键字有序排序
答案：C
解析：折半查找要求线性表以顺序方式存储，这样才能方便地计算中间元素的位置，同时结点要按关键字有序排序，才能根据中间元素的值来缩小查找范围，所以选C。
10.有n个记录的线性表，采用冒泡排序，比较次数最多为（）。
A.n1
B.n
C.n(n1)/2
D.n(n+