数据结构 ( 第2次 )

《数据结构 ( 第2次 )》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第2次作业一、单项选择题（本大题共60分，共20小题，每小题3分）1.按克鲁斯卡尔算法建的最小生成树（）。A.只有一种B.有多种C.不确定2.以下关于单链表的叙述中，错误的是（）。A.在单链表中插入一个结点必须先找到其前驱结点B.在单链表中删除一个结点必须先找到其前驱结点C.在单链表中只能通过结点的next指针向后查找结点D.在单链表中查找第i个结点的时间复杂度是O(1)3.输入序列为ABC，可以变为CBA时，经过的栈操作为（）。A.push,pop,push,pop,push,popB.push,push,push,pop,pop,popC

2、.push,push,pop,pop,push,popD.push,pop,push,push,pop,pop4.如图所示，可得到一个拓扑排序序列（ ）。A.v1,v6,v4,v3,v2,v5B.v1,v2,v6,v4,v3,v5C.v1,v2,v6,v3,v4,v5D.v1,v4,v6,v3,v2,v55.下列排序方法中，哪一个是稳定的排序方法？（　）A.简单选择排序B.堆排序C.希尔排序D.快速排序6.一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有（）结点。A.2hB.2h-1C.2h+1D.h+17.平衡二叉树的平衡

3、因子的取值可能是（）。A.1B.2C.3D.48.一个有n个顶点的无向图最多有（）条边。A.n　B.n(n-1)C.n(n-1)/2　D.2n9.在迷宫求解问题中，用（）作为转换过程中的数据存储结构。A.线性表B.栈C.队列D.单链表10.计算机算法指的是（）。A.计算方法B.排序方法C.解决问题的步骤序列D.调度方法11.基数排序是（）。A.稳定的B.不稳定的C.看具体情况D.未知12.对（70.83.100.65.10.32.7.9）进行简单选择排序，排序后第一趟结果为（）。A.7.83.100.65.10.32.70.9B.7.9.10

4、0.65.10.32.70.83C.7.9.10.65.100.32.70.83D.7.9.10.32.100.65.70.8313.对于一个有向图的逆邻接链表表示，第i个链表中有x个结点，则顶点i的出度为（）。A.xB.x+1C.x+iD.无法确定14.1348转化为8进制结果是（）。A.2504B.2405C.4052D.205415.二维数组A［10］［20］采用按行为主序的存储方式，每个元素占4个存储单元，若A［0］［0］的存储地址为300，则A［10］［10］的地址为（）。A.700B.1120C.1180D.114016.已知He

5、ad(Tail([Head(S),Head(Tail(Tail(S)))]))=[a]，广义表S满足上式，则S为（）(其中，方括号表示广义表，圆括号表示函数，如[a,b]表示由a,b构成的广义表，而Head()表示取广义表的头部）。A.[[a,b],b,a]B.[[b,a],[a],[b]]C.[[a],[a,b],[b]]D.[[b],[b,a],[a]]17.若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为（）。A.X的双亲B.X的右子树中最左的结点C.X的左子树中最右结点D.X的左子树中最右叶结点18.在对应于序列(1

6、2，5，8，15，25，10，30，7)的二叉排序树中查找30需要进行多少次比较。（）A.1B.2C.3D.419.对长度为155的顺序表在等概率情况下进行顺序查找的平均查找长度为（）。A.78B.77.5C.155D.15620.对于三个结点的二叉树有多少种形态？（）A.3B.4C.5D.6二、判断题（本大题共40分，共20小题，每小题2分）1.判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用求最短路径的Dijkstra方法。2.在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每

7、块中元素个数有关。3.散列法的平均检索长度不随表中结点数目的增加而增加，而是随负载因子的增大而增大。4.两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。5.一个树的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。6.广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。7.Hash表的平均查找长度与处理冲突的方法无关。8.完全二叉树中，若一个结点没有左孩子，则它必是树叶。9.一个稀疏矩阵Am*n采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把m和n的值

8、互换，则就完成了Am*n的转置运算。10.图的遍历要求从图的某一顶点出发，访遍图中的其余顶点，且每个顶点仅被访问一次。11.迷宫求解问题中经常用到顺序表来存储数据。