资源描述：
《数据结构期末复习题答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、《数据结构》复习题（含部分参考答案版）一、单项选择题1.按照数据逻辑结构的不同，可以将数据结构分成C。A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构2.下列关于数据结构的叙述中正确的是A。A.数组是同类型值的集合B.递归算法的程序结构比迭代算法的程序结构更为复杂C.树是一种线性的数据结构D.用一维数组存储二叉树，总是以先序顺序遍历各结点3.在计算机的存储器中表示时，物理地址与逻辑地址相同并且是连续的，称之为BA.逻辑结构B.顺序存储结构C.链式存储结构D.以上都不对4.以下关于算法特性的描述中，B是正确的。（1）算法至少有一
2、个输入和一个输出（2）算法至少有一个输出但是可以没有输入（3）算法可以永远运行下去A.（1）B.（2）C.（3）D.（2）和（3）5.对顺序存储的线性表（a1,a2,…,an）进行插入操作的时间复杂度是C。A.O(n)B.O(n-i)C.(n/2)D.O(n-1)6.链表不具有的特点是A。A.可随机访问任一元素B.插入和删除时不需要移动元素C.不必事先估计存储空间D.所需空间与线性表的长度成正比7.线性链表中各链结点之间的地址C。A.必须连续B.部分地址必须连续C.不一定连续D.连续与否无关8.以下关于链式存储结构的叙述中，C是不正确的。A.结点除自身信息外还包括指针域
3、，因此存储密度小于顺序存储结构B.逻辑上相邻的结点物理上不必邻接C.可以通过计算直接确定第i个结点的存储地址D.插入、删除操作方便，不必移动结点9.设依次进入一个栈的元素序列为d,a,c,b,得不到出栈的元素序列为D。A.dcbaB.acdbC.abcdD.cbda10.将新元素插入到链式队列中时，新元素只能插入到B。A.链头B.链尾C.链中D.第i个位置，i大于等于1，大于等于表长加111.设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2、e4、e3、e6、e5、和e1，则栈S容量
4、至少应该是C。A.6B.4C.3D.212.下面D是‘abcd321ABCD’的子串。A.abcdB.321abC.‘abcABC’D.‘21AB’13.假设8行10列的二维数组A[1…8，1…10]分别以行序为主序和以列序为主序顺序存储时，其首地址相同，那么以行序为主序时元素a[3，5]的地址与以列序为主序时C元素相同。A.a[7，3]B.a[8，3]C.a[1，4]D.ABC都不对14.数组A[0…5，0…6]的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址为A。A.1175B.1180C.1205D.121015
5、.下列广义表中，长度为3的广义表为B。A.（a,b,c,()）B.((g),(a,b,c,d,f),())C.(a,(b,(d)))D.((()))16.以下关于广义表的叙述中，正确的是A。A.广义表是0个或多个单元素或子表组成的有限序列B.广义表至少有一个元素是子表C.广义表不可以是自身的子表D.广义表不能为空表17.若树T有a个度为1的结点，b个度为2的结点，c个度为3的结点，则该树有D个叶结点。A.1+2b+3cB.a+2b+3cC.2b+3cD.1+b+2c18.若一棵二叉树有102片叶子结点，则度二叉树度为2的结点数是B。A.100B.101C.102D.10
6、319.在有n个叶子结点的霍夫曼树中，其结点总数为：。A.nB.2nC.2n+1D.2n-120.具有12个结点的完全二叉树有B。A.5个叶子结点B.5个度为2的结点C.7个分支结点D.2个度为1的结点21.设结点x和y是二叉树中的任意两结点，若在先根序列中x在y之前，而后根序列中x在y之后，则x和y的关系是C。A.x是y的左兄弟B.x是y的右兄弟C.x是y的祖先D.x是y的后代22.先序遍历序列与中序遍历序列相同的二叉树为。A.根结点无左子树的二叉树B.根结点无右子树的二叉树C.只有根结点的二叉树或非叶子结点只有左子树的二叉树D.只有根结点的二叉树或非叶子结点只有右子
7、树的二叉树23.若二叉树T的前序遍历序列和中序遍历序列分别是bdcaef和cdeabf，则其后序遍历序列为A。A.ceadfbB.feacdbC.eacdfbD.以上都不对24.设无向图的顶点个数为n，则该图最多有C条边。A.n-1B.n(n-1)C.n(n-1)/2D.n25.对于一个有n个顶点和e条边的无向图，若采用邻接表表示，邻接表中的结点总数是C。A.e/2B.eC.n+2eD.n+e26.无向图G=（V，E），其中V=｛a,b,c,d,e,f｝,E=｛(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,
