《数据结构补考题》由会员分享，可在线阅读，更多相关《数据结构补考题（10页珍藏版）》请在金锄头文库上搜索。
1、判断题，正确在括号内打，错误打X。()1. AOV网的拓扑序列是唯一的。()2.一个有向图的邻接表和逆邻接表中的结点个数一定相等。()3.空串与空格串是相同的。()4.稀疏矩阵压缩存储后，必会失去随机存取的功能。()5.二叉排序树的充要条件是任一结点的值均大于其左孩子的值，小于其右孩子的值。()6.如果某排序算法是不稳定的，则该排序方法没有实际应用价值。()7.由二叉树的中序表示和前序表示可以导出其的后序表示。()8.顺序存储结构只能用来存放线性结构；链式存储结构只能用来存放非线性结构。()9. 在栈满的情况下不能做进栈操作，否则将产生“上溢”。()10.在循环队列(少用一个元素空间)中fro
2、nt指向对头元素位 置，rear指向队尾元素的后一位置，则队满的条件是front二二rear。() 11在单链表中，头结点是必不可少的。()1 2如果一个二叉树中没有度为1的结点，则必为满二叉树。() 13. 循环单链表的结点结构与单链表的结点结构完全相同，只是结点 间的连接方式不同。( ) 14. 顺序存储结构只能用来存放线性结构；链式存储结构只能用来存 放非线性结构。( )1 5. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之 和。( ) 16. 二叉树是树的特殊情形。( ) 17. 从逻辑关系上讲，数据结构主要分为两大类：线性结构和非线性 结构。( ) 18. 连通分量是无向图
3、中的极小连通子图。( ) 19. 拓扑排序是指结点的值是有序排列。()20.在高级语言(如C语言)中，指针类型是原子类型。二、选择题。1. 已知一维数组A采用顺序存储结构，每个元素占用4个存储单元，第九个 元素的地址是144，则第一个元素的地址为( )。A、108B、180C、176 D、1122. 若一个栈的输入序列是1, 2, 3，n输出序列的第一个元素是n则第i个输出元素是()。A、不确定B、n-iC、n-i-D、n-i+13. 在解决计算机主机与打印机之间速度不匹配问题时，通常设置一个打印缓冲区，该缓冲区应该是一个（）结构。A、栈B、队列C、数D、线性表）。4设有两个串p和q,求q在p
4、中首次出现的位置的运算称做（A、连接B、模式匹配C、求子D、求串长5.对特殊矩阵采用压缩存储的目的主要是为了（）。A、表达变得简单B、对矩阵元素的存取变得简单C、去掉矩阵中的多余元素D、减少不必要的存储空间6Ap-next=nullBp=nullCp-next=headDp=head7一个栈的输入序列为123，不可能的输出有（）。A.312B. 321C. 123D . 213设head是带头结点的非空单循环链表的头指针，结点p是其尾结点的条）。件是8A. 250B. 500C. 254D.505E.以上答案都不对一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）。9. 如果结点A有
5、3个兄弟，B是A的双亲，则结点B的度是（ ）。A、1B、2C、3D、410. 线索二叉树中某结点R没有左孩子的充要条件是（）。A、R.l child =1 B、R.ltag=0 C、R.ltag=1D、R.rchild=NULL11. 设森林中有4棵树，树中结点的个数依次为nl、n2、n3、n4，则把森林转换为二叉树后，其根结点的右子树上有（）个结点，其根结点的左子树上有（）个结点。A、n1-1B、n1C、n1+n2+n3D、n2+n3+n412. 由权值为3,8,6,2,5的叶子结点生成一棵哈夫曼树，其带权路径长度为 （ ）。14. 一个有n个顶点的有向图最多有（）条弧。A、24B、48C、
6、53D、7213. 查找算法中一般涉及到三类参数，其中为输出参数。A.查找对象B.查找范围C.查找结果D.平均查找长度A. nB. n(n-1)C. n(n-1)/2D. 2n15. 个具有1025个结点的二叉树的高h%（）。A. 11B. 10 C. 11 至 1025 之间D. 10 至 1024 之间16. 若线性表最常用的操作是存取第i个元素及其前驱的值，则采用）存储方式最节省时间。A.单链表 B.双链表 C.单循环链表D.顺序表17. 采用折半查找法进行查找，数据文件应为（）。A. 采用顺序存储结构的有序表B. 采用链式存储结构的有序表C. 采用顺序存储结构的随机表D. 采用链式存储
7、结构的随机表18. n个顶点的强连通图至少有（）条弧。A、nB、n+1C、n-D、nX（n-1）19. 判定一个有向图是否存在回路，除了可以用拓扑排序的方法外，还可以用（）。A、求关键路径的方法B、求最短路径的方法C、广度优先遍历算法D、深度优先遍历算法）。20. 下面关于工程计划的AOE网的叙述中，不正确的是（A、关键活动不按期完成就会影响整个工程的完成时间B、任何一个关键活动提前完成，那么整个工程将会提前完成C、所有的关键活动都提前完成，那么整个工程将会提前完成D、某些关键活动提前完成，那么整个工程将会提前完成21. 下列命题正确的是（）A、一个图的邻接矩阵表示是唯一的，邻接表表示也唯一B
8、、一个图的邻接矩阵表示是唯一的，邻接表表示不唯一C、一个图的邻接矩阵表示不唯一，邻接表表示是唯一的D、一个图的邻接矩阵表示不唯一，邻接表表示也不唯一22. 执行下面程序段时，执行S语句的次数为（）。for（I=1;I=n;I+）for（j=1;j=n;j+）S;A. n2B. n2/2C. n(n+1)D. n(n+1)/23在线索二叉树中，一个结点是叶子结点的充要条件为( )。A. 左线索标志为0,右线索标志为1B. 左线索标志为1,右线索标志为0C. 左右线索标志均为0D. 左右线索标志均为124树的基本遍历策略分为先根遍历和后根遍历；二叉树的基本遍历策略可 分为先序遍历、中序遍历和后序遍
9、历。下列结论正确的是( )。A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同B. 树的后根遍历序列与其对应的二叉树的先序遍历序列相同C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同D. 以上都不对25下述编码中那一个不是前缀码( )A.(00,01,10,11)B.(0,1,00,11)C.(0,10,110,111)D.(1,01,000,001)题共页第2页26一棵二叉树有67个结点，且无度为1的结点。这棵二叉树中度为2的结点有 （ ）个。A. 33 B. 34 C. 32 D. 3027. 长度为12的有序表采用顺序存储结构，用折半查找方法，在等概率情况 下，查找成功时的平均查找长度是（ ）。A、37/12 B、62/1328. 散列技术中的冲突指的是（A、两个元素具有相同的序号相同C、数据元素过多的存储地址C、38/12D、49/13）。B、两个元素的键值不同，而其他属性D、不同键值的元素对应于相同29. 排序趟数与序列的原始状态有关的排序方法是 （ ）。A、直接插入排序B、简单选择排序C、快速排序D、归并排序30. 用直接插入排序对下面4个序列进行由小到大排序，元素比较次数最少 的是（ ）。
