杭州电子科技大学学生数据结构复习卷答案.docx
杭州电子科技大学学生数据结构复习卷答案
一、选择题（每题3分，共30分）
1.数据结构是一门研究非数值计算的程序设计问题中计算机的（）以及它们之间的关系和运算等的学科。
A.操作对象
B.计算方法
C.逻辑存储
D.数据映像
答案：A
详细解答：数据结构主要研究的是操作对象（数据元素）以及它们之间的关系和运算等内容。计算方法侧重于算法的设计和分析来解决具体的数值或非数值问题；逻辑存储是数据存储方式的一种描述；数据映像是数据库中关于数据在不同层面的映射概念。所以本题选A。
2.算法分析的目的是（）。
A.找出数据结构的合理性
B.研究算法中的输入和输出的关系
C.分析算法的效率以求改进
D.分析算法的易读性和文档性
答案：C
详细解答：算法分析主要是对算法的时间复杂度和空间复杂度进行分析，其目的是评估算法的效率，通过分析找到可以改进算法的地方，使算法在时间和空间上更加高效。找出数据结构的合理性是数据结构设计方面的内容；研究算法输入和输出的关系不是算法分析的核心目的；易读性和文档性虽然也是算法的重要方面，但不是算法分析的主要目的。所以选C。
3.线性表采用链式存储时，其地址（）。
A.必须是连续的
B.一定是不连续的
C.部分地址必须是连续的
D.连续与否均可以
答案：D
详细解答：链式存储结构是通过指针来表示元素之间的逻辑关系，每个节点包含数据域和指针域，节点可以存储在内存的任意位置，它们的地址不一定是连续的，连续与否都不影响链表的正常操作。所以线性表采用链式存储时，地址连续与否均可以，选D。
4.栈和队列的共同点是（）。
A.都是先进先出
B.都是先进后出
C.只允许在端点处插入和删除元素
D.没有共同点
答案：C
详细解答：栈是先进后出的数据结构，队列是先进先出的数据结构，所以A和B选项错误。栈只允许在栈顶进行插入和删除操作，队列只允许在队尾插入，队头删除，它们都只允许在端点处进行插入和删除元素，这是它们的共同点。所以选C。
5.若串S1=ABCDEFG，S2=9898，S3=，S4=012345，执行concat(replace(S1,substr(S1,2,3),S3),substr(S4,strlen(S2),2))操作后的结果为（）。
A.ADEFG01
B.AG0123
C.AG01
D.ADEFG0123
答案：C
详细解答：首先，substr(S1,2,3)表示从S1的第2个位置开始取3个字符，结果为BCD。replace(S1,substr(S1,2,3),S3)表示用S3替换S1中的BCD，得到AEFG。strlen(S2)计算S2的长度为4，substr(S4,strlen(S2),2)表示从S4的第4个位置开始取2个字符，结果为01。最后concat函数将两个结果连接起来，得到AG01。所以选C。
6.树最适合用来表示（）。
A.有序数据元素
B.无序数据元素
C.元素之间具有分支层次关系的数据
D.元素之间无联系的数据
答案：C
详细解答：树是一种非线性数据结构，它的特点是元素之间具有明显的分支层次关系，例如家族树、文件系统的目录结构等。有序数据元素通常用线性表来表示；无序数据元素也可以用线性表等结构表示；元素之间无联系的数据不适合用树这种有特定关系的结构表示。所以选C。
7.具有10个叶子节点的二叉树中有（）个度为2的节点。
A.8
B.9
C.10
D.11
答案：B
详细解答：在二叉树中，有一个重要的性质：$n_0=n_2+1$，其中$n_0$表示叶子节点的个数，$n_2$表示度为2的节点个数。已知$n_0=10$，则$n_2=n_01=9$。所以选B。
8.已知一个图的邻接矩阵表示，计算第i个顶点的入度的方法是（）。
A.计算邻接矩阵第i行的非零元素个数
B.计算邻接矩阵第i列的非零元素个数
C.计算邻接矩阵第i行的零元素个数
D.计算邻接矩阵第i列的零元素个数
答案：B
详细解答：在图的邻接矩阵中，矩阵的行表示出边，列表示入边。第i个顶点的入度是指有多少条边指向该顶点，反映在邻接矩阵中就是第i列中非零元素的个数，因为非零元素表示有边指向该顶点。所以选B。
9.对线性表进行二分查找时，要求线性表必须（）。
A.以顺序方式存储
B.以链式方式存储
C.以顺序方式存储，且数据元素有序
D.以链式方式存储，且数据元素有序
答案：C
详细解答：二分查找的基本思想是每次将查找区