数据结构 ( 第1次 )

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

1、第1次作业一、单项选择题（本大题共60分，共20小题，每小题3分）1.将线性表的数据元素进行扩充，允许是带结构的线性表是()。A.串B.树C.广义表D.栈2.一棵树中，（）没有前驱结点。A.分支结点B.叶结点C.树根结点D.空结点3.孩子兄弟表示法中，若要访问结点x的第i个孩子，则要先从firstchild域找到第1个孩子结点，然后沿着孩子结点的nextsibling域连续走（）步，便可找到x的第i个孩子。A.1B.2C.i-1D.i4.建堆是将所有元素按照初始顺序填充到一个（）中。A.二叉树B.平衡二叉树C.红黑树D.完全二叉树5.若n个顶点的无向图采用邻接矩阵存储方法，该

2、邻接矩阵为一个什么矩阵？（）A.对称矩阵B.一般矩阵C.稀疏矩阵D.对角矩阵6.由3个结点所构成的二叉树有（）种形态。A.3B.4C.5D.67.排序算法的作用是（）。A.让元素以递增的顺序排列B.让元素以递减的顺序排列C.让无序的数据组合变成有序的数据组合D.以上都不对8.下面关于折半查找的叙述正确的是()。A.表必须有序，表可以顺序方式存储，也可以链表方式存储B.表必须有序且表中数据必须是整型，实型或字符型C.表必须有序，而且只能从小到大排列D.表必须有序，且表只能以顺序方式存储9.图中有关路径的定义是（）。A.由顶点和相邻顶点序偶构成的边所形成的序列B.由不同顶点所形成

3、的序列C.由不同边所形成的序列D.上述定义都不是10.采用邻接表存储的图的深度优先遍历算法类似于二叉树的（）。A.先序遍历　B.中序遍历　C.后序遍历D.按层遍历11.设有50行60列的二维数组A[50][60]，其元素长度为4字节，按行优先顺序存储，基地址为200，则元素A[18][25]的存储地址为（）。A.3700B.4376C.3900D.462012.迪杰斯特拉(Dijkstra)算法用于求解图上的单源点最短路径。本质上说，该算法是一种基于（）策略的算法。A.分治B.动态规划C.贪心D.回溯13.简单选择排序是一种（）。A.稳定的排序算法B.不稳定的排序算法C.无法

4、确定其是否稳定D.以上都不对14.分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是(）。A.（100，80，90，60，120，110，130）B.（100，120，110，130，80，60，90）C.（100，60，80，90，120，110，130）D.(100，80，60，90，120，130，110)15.任何一个带权的无向连通图的最小生成树（）。A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在16.弗罗伊德(Floyd)算法时间复杂度是（）。A.B.C.D.17.设F是一个森林，B是由F转换得到的二叉树，F中有n个非叶结点，则B中右指针域

5、为空的结点有（）个。A.n-1B.nC.n+1D.n+218.设一个广义表中结点的个数为n，则求广义表深度算法的时间复杂度为（）。A.O(1)B.O(n)C.O(n2)D.O(log2n)19.设要将序列（q,h,c,y,p,a,m,s,r,d,f,x）中的关键码按字母升序重新排序，第一次交换位置的是（）。A.a和xB.p和fC.p和dD.y和r20.对于长度为n的顺序存储的线性表，访问结点和插入、删除结点的平均时间复杂度为（）。A.O(0)B.O(1)C.O(n)D.O(n2)二、判断题（本大题共40分，共20小题，每小题2分）1.任一查找树(二叉分类树)的平均查找时间都小

6、于用顺序查找法查找同样结点的线性表的平均查找时间。2.对无序表用折半查找比顺序查找快。3.对于无向图来说，若深度优先遍历过程中遇到回边（即指向已访问过的顶点的边），则必定存在环。4.对一棵二叉排序树按前序方法遍历得出的结点序列是从小到大的序列。5.线性结构中，每一个结点都至少有一个直接前驱和一个直接后继。6.排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。7.n个顶点的连通图至少n-1条边。8.Dijkstra最短路径算法从源点到其余各顶点的最短路径的路径长度按递增次序依次产生。9.二叉排序树删除一个结点后，仍是二叉排序树。10.二叉树中每个结点的两棵子树的高度

7、差等于1。11.树中的每个结点有不唯一的一个双亲结点。12.克鲁斯卡尔算法适应范围为稀疏图。13.在稀疏矩阵的顺序存储中，利用一个数组来存储非零元素，该数组的长度应等于对应三元组线性表的长度。14.在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要n条弧。15.图的遍历算法有深度优先搜索算法和广度优先搜索算法。16.已知单链表中某一结点由p指向，求此后继结点存储地址的操作为p=p->next。17.在散列检索中，“比较”操作一般也是不可避免的。18.在广义表的存储结构中，每个结点均包含有3