数据结构习题及答案.doc

数据结构习题及答案,全国2010年1月自考数据结构试题及答案
全国年月自考数据结构试题及答案表格
全国年月自考数据结构试题及答案
课程代码：

一、单项选择题本大题共小题，每小题分，共分
在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。
若一个算法的时间复杂度用表示，其中的含义是
问题规模语句条数
循环层数函数数量
具有线性结构的数据结构是
树图
栈和队列广义表
线性结构有：顺序表、栈和队列、串
将长度为的单链表连接在长度为的单链表之后，其算法的时间复杂度为


+在带头结点的双向循环链表中插入一个新结点，需要修改的指针域数量是
个个
个个
中
在带头结点的双链表中，将值为的新结点插入结点之前，设≠

①
②
③
④
⑤
⑥

假设以数组存放循环队列的元素，其头指针是，当前队列有个元素，则队列的尾指针值为


辅导书中
对于循环向量中的循环队列，写出通过队头队尾指针表示的队列长度公式。指向实际队头，指向实际队尾的下一元素位置。
当≥时，队列长度；当时，+。这两种情况可统一为+，这里为向量的大小。本题中
若栈采用链式存储结构，则下列说法中正确的是
需要判断栈满且需要判断栈空
不需要判断栈满但需要判断栈豢?br>需要判断栈满但不需要判断栈空
不需要判断栈满也不需要判断栈空
中
因为链栈中的结点是动态分配的，可以不考虑上溢，所以无需定义运算。
若串””，其子串的数目是


中
任意个连续字符组成的子序列称为该串的子串。
设有一个阶的下三角矩阵，采用行优先压缩存储方式，为第一个元素，其存储地址为，每个元素占一个地址单元，则的地址为


中
在阶方阵这个下三角矩阵中，第从开始行≤有+个元素，元素总数为：+，并将元素放在一个向量+中。
若≥，则在左下三角矩阵中，与的对应关系是++。
若，则在右上三角矩阵中，与的对应关系是++。
若为第一个元素，与为第一个元素时的位置一样，+，则的地址+；
若为第一个元素，与为第一个元素时的位置一样，+，则的地址+；
允许结点共享的广义表称为
纯表线性表
递归表再入表
下列数据结构中，不属于二叉树的是树是一种平衡的多叉树
树树树是自平衡二叉查找树
二叉排序树哈夫曼树哈夫曼树是最优二叉树
对下面有向图给出了四种可能的拓扑序列，其中错误的是辅导书中第题

，，，，，，，，，，
，，，，，，，，，，
以为起始结点对下图进行深度优先遍历，正确的遍历序列是

，，，，，，，，，，，，
，，，，，，，，