《数据结构》练习。
一) 单选题
1. 若不带头结点的单链表的头指针为head，则该链表为空的判定条件是（）。
a) 2. 下列叙述中正确的是（）。
(d) 一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率
3. 数据的基本单位是（）。
a) 数据项
4. 下列程序的时间复杂度为（）。
a) 5. 设广义表，则l的长度和深度分别为（）。
(c) 1和2
6. 算法指的是（）。
d) 解决问题的有限运算序列。
7. 程序段如下：其中n为正整数，则最后一行的语句频度在最坏情况下是（）。
(d) 8. 求循环链表中当前结点的后继和前驱的时间复杂度分别是（）。
(c) 和
9. 程序段forforif其中n为正整数，则最后一行的语句频度在最坏情况下是（ ）
d) 10. 与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。
(b) 逻辑结构
11. 从一个长度为n的顺序表中删除第i个元素时，需向前移动的元素的个数是（）。
a) 12. 设以数组存放循环队列的元素，其头尾指针分别为front和rear，则当前队列中的元素个数为（）。
a) 13. 用链表表示线性表的优点是（）。
(d) 便于插入与删除
14. 若已知一个栈的入栈序列是，其输出序列为，若，则为（）。
c) 15. 栈和队列的共同点是（）。
c) 只允许在端点处插入和删除元素
16. 从逻辑上可以把数据结构分为（）两大类。
c) 线性结构、非线性结构
17. 对于栈操作数据的原则是（）。
(b) 后进先出
18. 一个递归的定义可以用递归过程求解，也可以用非递归过程求解，但单从运行时间来看，通常递归过程比非递归过程（）。
(b) 较慢
19. 对广义表执行操作的结果是（）。
(b) 20. 在下面的程序段中，对x的赋值语句的频度为（）。
(c) 21. 若允许表达式内多种括号混合嵌套，则为检查表达式中括号是否正确配对的算法，通常选用的辅助结构是（）。
a) 栈 22. 对n阶对称矩阵a以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组b中，则在b中确定的位置k的关系为（）。
(b) 23. 下列程序段的渐进时间复杂度为（）。
(c) 24. 非空的单循环链表的头指针为head,尾指针为rear，则下列条件成立的是（）。
a) rear-
25. 若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算时间的存储方式是（）。
(d) 仅有尾指针的单循环链表
26. 下述程序段中语句的频度是（）。
(c) 27. 二维数组采用列优先的存储方法，若每个元素各占3个存储单元，且地址为150，则元素的地址为（）。
a) 429
28. 顺序栈s中top为栈顶指针，指向栈顶元素所在的位置，elem为存放栈的数组，则元素e进栈操作的主要语句为（）。
(d) 29. 一个栈的入栈序列是，则栈的不可能的输出序列是（）。
(c) 30. 线性表采用链式存储时，节点的存储的地址（）。
b) 连续与否均可
二) 多选题
1. 下列数据结构中，（）是线性结构。
a) 线性表 (b) 栈 (c) 队列
2. 下列叙述错误的是（）。
a) 算法的执行效率与数据的存储结构无关
b) 算法的空间复杂度是指算法程序中指令（或语句）的条数
3. 一个栈的入栈序列是，则栈的不可能的输出序列是（）。
c) 45231 (d) 32514
4. 对线性表、栈、队叙述正确的是（）。
a) 它们逻辑结构相同，都是线性的
b) 都可以用顺序存储或链表存储
c) 栈和队列是两种特殊的线性表，即受限的线性表
d) 栈是只允许在一端进行插入和删除运算，因而是后进先出表lifo
e) 队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表fifo
5. 算法描述可以有多种表达方法，下面哪些方法可以描述的算法（）。
a) 自然语言 (b) 流程图 (c) 伪** (d) 程序设计语言
6. 一个链式队列中，假设f和r分别为队首和队尾指针，则插入s所指结点的运算序列是（）。
a) b)
7. 串与线性表叙述正确的是（）。
a) 串的逻辑结构和线性表极为相似
b) 区别仅在于串的数据对象约束为字符集
c) 串的基本操作和线性表有很大差别
d) **性表的基本操作中，大多以作为操作对象
e) 在串的基本操作中，通常以作为操作对象
8. 线性表的两种存储结构叙述正确的是（）。
a) 线性表顺序存储结构可以随机存取表中任一元素
b) 线性表链式存储结构只能顺序存取表中任一元素
c) 线性表顺序存储结构在插入或删除某一元素时，需要移动大量元素
d) 线性表链式存储结构在插入或删除某一元素时，不需要移动大量元素
9. 在链队列中，若删除一个元素，则（）。
(b) 必须修改头指针 (c) 有时需修改尾指针
三) 判断题
1. 链表中的头结点仅起到标识的作用。
(b) 错
2. 在单链表中，指针p指向元素为x的结点，实现的语句是。
(b) 错
3. 在顺序存储结构中，有时也存储数据结构中元素之间的关系。
b) 错 4. 线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。
a) 对 5. 两个栈共用静态存储空间，对头使用也存在空间溢出问题。
a) 对 6. 若输入序列为1，2，3，4，5，6，则通过一个栈可以输出序列1，5，4，6，2，3。
(b) 错
7. 取线性表的第i个元素的时间同i的大小有关。
(b) 错
8. 健壮的算法不会因非法的输入数据而出现莫名其妙的状态。
a) 对 9. 在链队列中，即使不设置尾指针也能进行入队操作。
a) 对 10. 循环链表不是线性表。
(b) 错
11. 在执行简单的串匹配算法时，最坏的情况为每次匹配比较不等的字符出现的位置均为模式串的最末字符。
a) 对 12. 顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。
(b) 错
13. 如果一个串中的所有字符均在另一串**现，则说前者是后者的子串。
(b) 错
14. 为了很方便的插入和删除数据，可以使用双向链表存放数据。
a) 对 15. 数据元素是数据的最小单位。
b) 错 16. 在数据结构中，空串和空格串的概念是一样的。
b) 错 17. 单链表从任何一个结点出发，都能访问到所有结点。
(b) 错
18. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
b) 错 19. 算法可以用不同的语言描述，如果用c语言或pascal语言等高级语言来描述，则算法实际上就是程序了。
b) 错 20. 队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。
(b) 错
21. 数据的逻辑结构是指数据的各数据项之间的逻辑关系。
b) 错 22. 数据的物理结构是指数据在计算机内的实际存储形式。
(b) 错
(一) 单选题
1. 假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除预某个顶点vi相关的所有弧的时间复杂度是（）。
(c) 2. 用邻接表表示图进行广度优先遍历时，通常是采用（）来实现算法的。
b) 队列
3. 在一个非空二叉树的中序遍历序列中，根结点的右边（）。
a) 只有右子树上的所有结点
4. 设森林f对应的二叉树为b，它有m个结点，b的根为p，p的右子树结点个数为n,森林f中第一棵子树的结点个数是（）。
a) 5. 树最适合用来表示（）。
(c) 元素之间具有分支层次关系的数据
6. 已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是（）。
c) 01 3 4 2 5 6
7. 有8个结点的无向连通图最少有（）条边。
(c) 7
8. 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（）。
(b) 9. 在有n个叶子结点的哈夫曼树中，其结点总数为（）。
(d) 10. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。
b) 1 11. 设图的邻接链表如图所示，则该图的边的数目是（）。
(b) 5
12. 无向图，其中：，对该图进行深度优先遍历，得到的顶点序列正确的是（）。
d) a,e,d,f,c,b
13. 关键路径是事件结点网络中（）。
a) 从源点到汇点的最长路径
14. 已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是（）。
a) 03 2 1
15. 某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。
(b) 高度等于其节点数
16. 广度优先遍历类似于二叉树的（）。
d) 层次遍历
17. 在一棵具有n个结点的二叉链表中，所有结点的空域个数等于（）。
c) 18. 用邻接表表示图进行深度优先遍历时，通常是采用（）来实现算法的。
a) 栈 19. 除第一层外，满二叉树中每一层结点个数是上一层结点个数的（）。
(c) 2倍
20. 已知有向图，其中，,,g的拓扑序列是（）。
a) 21. 在一棵度为3的树中，度为3的节点个数为2，度为2的节点个数为1，则度为0的节点个数为（）。
数据结构练习
一 选择题 1 若长度为n的线性表采用顺序存储结构，删除它的第i数据元素之前，需要先依次向前移动 个数据元素。a 2.在单链表中，已知q指的结点是p指的结点的直接前驱结点，若在q和p指的结点之间插入一个由s指的结点，则需执行b a.q next p s next p b.s next p q nex...
数据结构练习
第1章。1.从逻辑上可以把数据结构分为。a 动态结构 静态结构 b 顺序结构 链式结构。c.线性结构 非线性结构 d 初等结构 构造型结构。2.关于算法的描述，不正确的是。a.算法最终必须由计算机程序实现。b 所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界。c.健壮的算法不会因非法的输人数...
数据结构练习
一 选择题。1 广度优先遍历的含义是 从图中某个顶点v出发，在访问了v之后依次访问v的各个未被访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，且 先被访问的顶点的邻接点 先于 后被访问的顶点的邻接点 被访问，直至图中所有已被访问的顶点的邻接点都被访问到是下图的广度优先遍历序列。a.1 ...