西安电子科技大学数据结构期末复习题

西安电子科技大学 《数据结构》复习题 (含部分参考答案版) 一、 单项选择题 A.动态结构和静态结构B. 紧凑结构和非紧凑结构 C. 线性结构和非线性结构D. 内部结构和外部结构 1. 按照数据逻辑结构的不同，可以将数据结构分成C。 ２. 下列关于数据结构的叙述中正确的是A。 A. 数组是同类型值的集合 B．递归算法的程序结构比迭代算法的程序结构更为复杂 C. 树是一种线性的数据结构 Ｄ. 用一维数组存储二叉树,总是以先序顺序遍历各结点 3． 在计算机的存储器中表示时，物理地址与逻辑地址相同并且是连续的，称之为 B A.逻辑结构B.顺序存储结构 C.链式存储结构D.以上都不对 4. 以下关于算法特性的描述中，Ｂ是正确的。 (１）算法至少有一个输入和一个输出 （2）算法至少有一个输出但是可以没有输入 (3）算法可以永远运行下去 A. (１)B. （２)C. （３）Ｄ. （2)和 （3) ５. 对顺序存储的线性表（a １,a２,…,aｎ）进行插入操作的时间复杂度是 Ｃ。 Ａ.O(n)B．O（ｎ-ｉ)C．(ｎ/２) D. Ｏ（n-1） 6. 链表不具有的特点是 Ａ。 A.可随机访问任一元素Ｂ.插入和删除时不需要移 动元素 C.不必事先估计存储空间D． 所需空间与线性表的长度成正比 7.线性链表中各链结点之间的地址Ｃ。 A．必须连续B.部分地址必须连续 C.不一定连续D.连续与否无关 ８.以下关于链式存储结构的叙述中,C是不正确的。 A.结点除自身信息外还包括指针域,因此存储密度小于顺序存储结构 B.逻辑上相邻的结点物理上不必邻接 C.可以通过计算直接确定第ｉ个结点的存储地址 D．插入、删除操作方便，不必移动结点 9.设依次进入一个栈的元素序列为ｄ, a, c, ｂ,得不到出栈的元素序列为 D。 A. dcbaB. ａcdbＣ.abcdD. cbｄａ 10． 将新元素插入到链式队列中时,新元素只能插入到B。 A． 链头Ｂ. 链尾C. 链中 D. 第 i 个位置,ｉ大于等于１，大于等于表长加１ １１． 设栈Ｓ和队列Ｑ的初始状态为空,元素ｅ1、e２、e3、ｅ4、ｅ5 和 e6 依次通过栈 Ｓ,一个元素出栈后即进入队列 Q,若 6 个元素出队的顺序是 e2、e４、ｅ３、e6、e5、和 e1,则栈Ｓ容量至少应该是C。 A.6B. 4C． 3D. 2 1２.下面D是‘ａｂｃd３21ABCD’的子串。 A． abcｄB. 3２1aｂC. ‘ａ bcABＣ’ Ｄ． ‘21AB’ 13.假设 8 行 10 列的二维数组 A［1…8，1…1０]分别以行序为主序和以列序为主序顺序 存储时,其首地址相同，那么以行序为主序时元素 a[3,5］的地址与以列序为主序时 C 元素相同。 A. a[7， 3]B. a[8， 3］Ｃ. ａ ［1,4]D. ABC 都不对 14． 数组 A[０…5,0…6］的每个元素占5 个字节,将其按列优先次序存储在起始地址为１ 000 的内存单元中,则元素 A[5，5]的地址为A。 A. 1175B. 1180C． １20５D. １21０ 15.下列广义表中，长度为 3 的广义表为B。 A.（a，b,ｃ， （ )）B. （ （g),(a，b,c，ｄ，ｆ） ，( ）)C. (a，(b,（d))） D. (（( ))） 16. 以下关于广义表的叙述中，正确的是A。 A.广义表是０个或多个单元素或子表组成的有限序列 Ｂ． 广义表至少有一个元素是子表 C. 广义表不可以是自身的子表 D. 广义表不能为空表 1７.若树T有a个度为1的结点， b个度为２的结点， c个度为３的结点,则该树有Ｄ个 叶结点。 Ａ.1+2b+3ｃB.ａ＋ 2b+3ｃＣ.２ｂ +3ｃ D. 1+ｂ+2c 1８.若一棵二叉树有 102 片叶子结点，则度二叉树度为２的结点数是B。 A． 1０0B． 101C. 102 Ｄ． 103 1９． 在有 n 个叶子结点的霍夫曼树中，其结点总数为:。 A. ｎB. 2nC. ２n+1D. 2n － 1 20.具有 12 个结点的完全二叉树有B。 A.5 个叶子结点B.5 个度为２的结点 Ｃ. 7 个分支结点Ｄ.2 个度为１的结点 21．设结点ｘ和ｙ是二叉树中的任意两结点，若在先根序列中 x 在 y 之前，而后根序列中 ｘ在ｙ之后,则ｘ和ｙ的关系是C。 Ａ.ｘ是 y 的左兄弟B. x 是 y 的右兄弟 Ｃ． x 是ｙ的祖先D. x 是 y 的后代 22.先序遍历序列与中序遍历序列相同的二叉树为。 A.根结点无左子树的二叉树B.根结点无右子树的二叉树 C. 只有根结点的二叉树或非叶子结点只有左子树的二叉树 D.只有根结点的二叉树或非叶子结点只有右子树的二叉树 ２3.若二叉树 T 的前序遍历序列和中序遍历序列分别是 bｄcaeｆ和 cdeabf，则其后序遍历 序列为A。 Ａ.ｃeａdfbB. feacdbＣ.ｅacdfｂＤ. 以上都不对 24．设无向图的顶点个数为ｎ，则该图最多有C条边。 Ａ.n－1B.n（n-１）C． n(n－1)/2 D. n ２5.对于一个有 n 个顶点和 e 条边的无向图，若采用邻接表表示，邻接表中的结点总数是 Ｃ。 A. e／2Ｂ．eＣ. n+2e Ｄ． ｎ＋ｅ 26.无向图 G=(V,E),其中 V=｛a,b,c,d,e,f},E=｛(a,b),(a,e),(a,c）,(ｂ,e） ，(ｃ，f),（ｆ，d）, （e,d)｝ 。 对该图进行深度优先遍历，下面不能得到的序列是D。 A. ａcfｄeｂB. ａebdfｃC． aｅdfcb D.aｂecｄf 2７．在下述排序方法中,不属于内排序方法的是Ｃ。 A． 插入排序法B.选择排序法C． 拓扑排序法D. 归 并排序法 ２8．直接插入排序在最好情况下的时间复杂度为B。 A. Ｏ(lｏｇ2n)Ｂ. Ｏ(ｎ)Ｃ． Ｏ(nlｏg2n）D. O(n2） 29.对有 n 个记录的表作快速排序，在最坏情况,算法的时间复杂度是Ｄ。 Ａ. O(n3)B. O（ｎ)C． O(nlｏg２n）D. Ｏ (n2) 30.下面的排序算法中，稳定是Ａ。 Ａ．直接插入排序法B. 快速排序法 C． 直接选择排序法D． 堆排序法 二、二、填空题填空题 １．一个算法具有 5 个特性:、、、有零个或多个 输入，一个或多个输出。 2. .设数组 a[1…5０,1…80]的基地址为２000,每个元素占２个存储单元,若以行序为主序顺 序存储，则元素ａ[45,68]的存储地址为9174；若以列序为主序顺序存储,则元 素 a[45,6８]的存储地址为8788。 3. 当线性表的元素总数基本稳定， 且很少进行插入和删除操作， 但要求以最快的速度存取 线性表中的元素时,应采用存储结构。 4.两个字符串相等的充分必要条件是长度相等且对应位置上的字符相等。。 5. 字符串“abcd”中共有个长度大于 0 的字串。 6. 广义表 liｓt=（5， （3，2,(１４,９，３),（),4)，2,(6,３,１0))的长度及深度分别 为和。 ７.若二叉树的先序序列和后序序列相反， 则该二叉树一定满足只有一个叶子结点。 8．若无向图满足有 n－1 条边的连通图,则该图是树。 9．若无向图中有n 个顶