C语言数据结构考试测试题目，题库+答案解析

落日映苍穹つ 2024-03-30 17:59 120阅读 0赞

#### 1 (单选题)数据结构中评价算法的两个重要指标是（ ）。 ####

*  A. 效率、难度

*  B. 可行性、确定性

*  C. 正确性、稳定性

*  D. 时间复杂度、空间复杂度

答案：D

解析：数据结构中评价算法的两个重要指标是[时间复杂度][Link 1]和[空间复杂度][Link 2]。

同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。[算法分析][Link 3]的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。

#### **2 (单选题)设n为正整数。试确定下列各程序段中前置以记号@的语句的频度：** ####

k=0;

for(i=1;i<=n;i++)\{

for(j=i;j<=n;j++)

@ k++;

*  A. n(n-1)/2

*  B. n(n+1)/2

*  C. n+1

*  D. n2

答案：B

解析：i=1时，第二个for语句执行n次；i=2时，第二个for语句执行n-1次；i=3时，第二个for语句执行n-2次...... i=n时，第二个for语句执行1次。

所以语句频度=n+(n-1)+(n-2)+...+1=n(n+1)/2

#### 3 (单选题)线性表若采用顺序存储结构时，要求内存中可用存储单元的地址( )。 ####

*  A. 必须是连续的

*  B. 部分地址必须是连续的

*  C. 一定是不连续的

*  D. 连续不连续都可以

答案：A

解析：[线性表][Link 4]的顺序存储结构，指的是用一段地址连续的[存储单位][Link 5]依次存储线性表的数据元素

#### 4 单链表中，增加一个头结点的目的是为了（ ） ####

*  A. 使单链表至少有一个结点

*  B. 标识表结点中首结点的位置

*  C. 方便运算的实现

*  D. 说明单链表是线性表的链式存储

答案：C

解析：单链表添加头结点主要是方便算法的实现，从而在单链表为空与非空时，保持插入与删除操作的一致。

#### 5 (单选题)向一个栈顶指针为top的链栈中插入一个p所指向的结点时，其操作步骤为（ ）。 ####

*  A.top->next=p;

*  B.p->next=top->next; top->next=p;

*  C.p->next=top; top=p;

*  D. p->next=top;top=top->next;

答案：C

#### 6 (单选题)有两个串p和q，求q在p中首次出现的位置的运算称为（ ）。 ####

*  A. 连接

*  B. 模式匹配

*  C. 求子串

*  D. 求串长

答案：B

解析：模式匹配是数据结构中字符串的一种基本运算，给定一个子串，要求在某个字符串中找出与该子串相同的所有子串。

#### 7 (单选题)广义表（a,(b,c),d,e）的表尾为 \_\_\_\_\_\_\_\_\_\_\_。 ####

*  A. (b,c),d,e

*  B. ((b,c),d,e)

*  C. e

*  D. (e)

答案：B

解析：表尾是由除了表头以外的其余元素组成的广义表，所以，需要在表尾的直接元素外面再加一层括号。

#### 8 (单选题)由3个结点可以构造出（ ）种不同的二叉树。 ####

*  A. 2

*  B. 3

*  C. 4

*  D. 5

答案：D

解析：3个结点可以构成5种形态的二叉树：根左左、根左右、左根右、根右右、根右左。

#### 9 (单选题)利用二叉链表存储树，则根结点的右指针是（ ）。 ####

*  A. 指向最左孩子

*  B. 指向最右孩子

*  C. 空

*  D. 非空

答案：C

解析：利用二叉链表存储树时，右指针指向兄弟结点，因为根节点没有兄弟结点，故根节点的右指针指向空。

#### 10 (单选题)在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶子结点个数是（ ）。 ####

*  A. 41

*  B. 82

*  C. 113

*  D. 122

答案：B

解析：一个森林的所有结点数=（所有结点的度数+n(n棵树，每棵树只有一个根节点)

一个森林的所有叶子结点数=（所有结点的度数+n(n棵树，每棵树只有一个根节点)-m(度数非0的结点个数)

#### 11 (单选题)设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（ ） ####

*  A. 空或只有一个结点

*  B. 任一结点无左孩子

*  C. 任一结点无右孩子

*  D. 任一结点无左孩子或者无右孩子

答案：D

解析：[先序遍历][Link 6]顺序是:M-L-R,[后序遍历][Link 7]顺序是:L-R-M,可以看到,只有中间的结点(M)顺序变化了,左右结点相对位置是不变的; 那可以推断出,要满足题意的话“二叉树的先序序列与后序序列正好相反”,说明整个二叉树左子树或者右子树有一个没有...”

#### 12 (单选题)表达式a\*(b+c/d)的后缀表达式是（ ）。 ####

*  A. abcd/+\*

*  B. abc+\*d/

*  C. abc\*+d/

*  D. /+\*abcd

答案：A

解析：先把每一步运算都加一个括号:(a\*(b+(c/d)))

再把括号内的运算符移到括号外：(a(b(cd)/)+)\*

最后把括号去掉：abcd/+\*

#### 13 (单选题)对于一个包含n个结点的树，用二叉链表存储时，其指针总数为（ ）个。 ####

*  A. n-1

*  B. n

*  C. n+1

*  D. 2n

答案：D

解析：对于一棵具有n个结点的二叉树，用二叉链表存储时，其指针总数为 2n 个

#### 14 (单选题)在有向图中每个顶点的度等于该顶点的（ ）。 ####

*  A. 入度

*  B. 出度

*  C. 入度与出度之和

*  D. 入度与出度之差

答案：C

解析：在有向图中，对于一个顶点，该结点的度等于顶点的入度+顶点的出度， 该结点的弧头数目称为入度，记为ID (v)；结点的弧尾数目称为出度，记为OD (v)，即TD (v)=ID (v)+OD (v)：

#### 15 (单选题)连通分量是（ ）极大连通子图 。 ####

*  A. 图

*  B. 树

*  C. 有向图

*  D. 无向图

答案：D

解析：无向图的极大连通子图称为的连通分量(ConnectedComponent)。任何连通图的连通分量只有一个，即是其自身，非连通的无向图有多个连通分量。

[Link 1]: https://wenwen.sogou.com/s/?w=%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6&ch=ww.xqy.chain
[Link 2]: https://wenwen.sogou.com/s/?w=%E7%A9%BA%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6&ch=ww.xqy.chain
[Link 3]: https://wenwen.sogou.com/s/?w=%E7%AE%97%E6%B3%95%E5%88%86%E6%9E%90&ch=ww.xqy.chain
[Link 4]: https://zhidao.baidu.com/search?word=%CF%DF%D0%D4%B1%ED&fr=iknow_pc_qb_highlight
[Link 5]: https://zhidao.baidu.com/search?word=%B4%E6%B4%A2%B5%A5%CE%BB&fr=iknow_pc_qb_highlight
[Link 6]: https://wenwen.sogou.com/s/?w=%E5%85%88%E5%BA%8F%E9%81%8D%E5%8E%86&ch=ww.xqy.chain
[Link 7]: https://wenwen.sogou.com/s/?w=%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86&ch=ww.xqy.chain