数据结构复习题23480

1、一、单选题1. 下列四种基本逻辑结构中，数据元素之间关系最弱的是 A，队列属于B 。A. 集合 B. 线性结构 C. 树形结构D. 图形结构2. 线性结构各数据元素之间存在着 B 的关系，图形结构数据元素之间存在 D 的关系。A. 无关 B. 一对一 C. 一对多 D. 多对多3. 在数据结构中，从逻辑上可以把数据结构分成C 。A. 动态结构和静态结构 B. 紧凑结构和非紧凑结构C. 线性结构和非线性结构 D. 内部结构和外部结构4. 算法中的基本操作重复执行的频度称为算法的 A ；除了考虑存储数据结构本身所占用的空间外，实现算法所用辅助空间的多少称为算法的 B 。A. 时间复杂度B.空间复杂

2、度 C.硬件复杂度D.软件复杂度5. 算法分析的目的是 C ，算法分析的两个主要方面是 A 。A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性A. 空间复杂度和时间复杂度 B. 正确性C. 可读性和文档性 D. 数据复杂性和程序复杂性6. 计算机算法指的是 C，它必具备输入、输出和 B等五个特性。 A. 计算方法 B. 排序方法 C. 解决问题的有限运算序列 D. 调度方法 A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性C. 确定性、有穷性和稳定性7. 线性表的逻辑顺序与存储顺序总是一致的，这种说法 B

3、。A正确 B. 不正确8. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址 D。A. 必须是连续的 B. 部分地址必须是连续的C. 一定是不连续的 D. 连续或不连续都可以 D. 易读性、稳定性和安全性二、填空题 (将正确的答案填在相应的空中)1. 数据逻辑结构包括集合、线性结构、树形结构 和 图形四种类型，树形结构和图形结构统称为 非线性结构 。2. 线性结构中，第一个结点 没有 前驱结点，其余每个结点有且仅有 1 个直接前驱结点；最后一个结点 没有 后继结点，其余每个结点有且仅有 1 个直接后继结点。3. 在树形结构中，树根结点没有 前驱 结点，其余每个结点有且只有 1 个前驱结

4、点；叶子结点没有 后继 结点，其余每个结点的后继结点可以 任意多个 。4. 在图形结构中，每个结点的前驱结点数和后继结点数可以 任意多个 。5. 线性结构中元素之间存在 一对一 关系，树形结构中元素之间存在 一对多关系，图形结构中元素之间存在 多对多 关系。6. 算法的五个重要特性是有穷性 、确定性 、可行性 、输入 、输出。7. 下面程序段的时间复杂度是 O（n*m) 。for(i=0;i<n;i+) for(j=0;j<m;j+)aij=0;8. 下面程序段的时间复杂度是 O() 。i=s=0;while(s<n) i+; s+=i; 9. 下面程序段的时间复杂度是O(n

5、2 ) 。s=0;for(i=0;i<n;i+) for(j=0;j<n;j+)s+=bij;sum=s;10. 下面程序段的时间复杂度是 O(log2n) 。i=1;while(i<=n) i=i*3;习 题 二一、填空题1. 在一个长度为n的向量的第i个元素(1in)之前插入一个元素时，需向后移动n-i+1 个元素。2. 在一个长度为n的向量中删除第i个元素(1in)时，需向前移动 n-i 个元素。3. 单链表是线性表 的链接存储表示。4. 在单链表中设置头结点的作用是在插入或删除第一个结点时不必对 表头指针 进行处理。5. 在双链表中，每个结点有两个指针域，一个指向 前

6、驱结点 ，另一个指向 后继结点 。6. 在一个单链表中p所指结点之后插入一个s所指结点时，应执行s->next= p->next 和p->next =s 的操作。7. 非空的循环单链表head的尾结点(由p所指向)满足条件p->next=head二、单选题1. 不带头结点的单链表head为空的判定条件是 A 。A. head=NULL B. head->next=NULL C. head->next=head D. head!=NULL2. 带头结点的单链表head为空的判定条件是 B 。A. head=NULL B. head->next=NULLC

7、. head->next=head D. head!=NULL3. 非空的循环单链表head的尾结点(由p所指向)满足 C 。A. p->next=NULLB. p=NULLC. p->next=headD. p=head4. 在循环双链表的p所指结点之后插入s所指结点的操作是 D 。A. p->next=s; s->prior=p;p->next->prio=s; s->next=p->next;B. p->next=s; p->next->prior=s; s->prior=p; s->next=p->

8、;next;C. s->prior=p; s->next=p->next; p->next=s; p->next->prior=s;D. s->prior=p; s->next=p->next; p->next->prior=s; p->next=s;5. 在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行 C。A. s->next=p->next; p->next=s;B. p->next=s->next; s->next=p;C. q->ne

9、xt=s; s->next=p;D. p->next=s; s->next=q; 6. 一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行 B 。A. s->next=p; p->next=s;B. s->next=p->next; p->next=;C. s->next=p->next; p=s;D. p->next=s; s->next=p;7. 在一个单链表中，若删除p所指结点的后继结点，则执行 A 。A. p->next=p->next->next;B. p=p->nex

10、t; p->next=p->next->next;C. p->next=p->nextD. p=p->next->next习 题 三一、填空题1. 栈是限定仅在表尾进行 插入和删除 操作的线性表，表头端称为 栈底 ，表尾端称为 栈顶 ，栈的操作特性是 后进先出 。2. 队列是限定仅在表尾进行 插入 和在表头端进行 删除 的线性表，队列的操作特性是 先进先出 。3. 以下定义了一个顺序栈： #define MAXSTACK 500 typedef struct char dataMAXSTACK; int top; sqstack; sqstack ss

11、;栈空的条件是：ss.top<0 ，栈满的条件是：ss.top=MAXSTACK-1 ；栈顶元素的表达式是：ss.datass.top ，栈底元素的表达式是：ss.data0 。二、简答题1. 设将整数1，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序插入在入栈操作之间，请回答下述问题：(1) 若入、出栈次序为Push(1), Pop(), Push(2), Push(3), Pop(), Pop( ), Push(4), Pop( )，则出栈的数字序列是什么(这里Push(i)表示i进栈，Pop( )表示出栈)?1324(2) 能否得到出栈序列1423和1432?并说

12、明为什么不能得到或者如何得到。不能得到1423序列，因为要得到14的出栈序列，则应做到push(1),pop(),push(2),push(3),push(4),pop()这样，3在栈顶，2在栈底，所以不能得到23的出栈序列。 能得到1432的出栈序列，具体操作为：push(1),pop(),push(2),push(3),push(4),pop(),pop(),pop()(3) 请分析1，2，3，4的24种排列中，哪些序列可以通过相应的入、出栈操作得到。在1234的24种排列中，可以通过相应入出栈的操作得到的序列是：1234，1243，1324，1342，1432，2134，2143，231

13、4，2341，2431，3214，3241，3421，4321不能得到的序列为：1423，2413，3124，3142，3412，4123，4132，4213，4231，43122. 循环队列的优点是什么? 如何判别它的空和满?优点：克服”假上溢“,能是空间得到充分的利用。判断空和满的方法：1。设置布尔变量来区分空和满 2.少用一个元素的空间变量， 3.设置一个计数器习 题 四一、填空题1. 已知二维数组Amn采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是Loc(A00)，则Aij的地址是 Loc(A(0)(0) +(n*i+j)*k 。2. 二维数组A1020采用列

14、序为主方式存储，每个元素占一个存储单元，并且A00的存储地址是200，则A612的地址是 326 。二、单选题1. 常对数组进行的两种基本操作是 C 。A. 建立与删除 B. 索引和修改C. 查找和修改 D. 查找与索引2. 数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，存放该数组至少需要的单元数是 C 。A. 80 B.100 C. 240 D. 2703. 数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A85的起始地址为 C 。A. SA +141 B. SA +144 C.

15、SA + 222 D. SA + 2254. 稀疏矩阵一般的压缩存储方法有两种，即 C 。A. 二维数组和三维数组 B. 三元组表和散列C. 三元组表和十字链表 D. 散列和十字链表习 题 五一、简答题1. 设S="I AM A STUDENT"，T="GOOD"，Q="WORKER"。求：STRLEN(s)=14，STRLEN(t)=4，SUBSTR(s，8，7)="STUDENT"，SUBSTR(t，2，1)="O"，INDEX(s，"A")=3，INDEX(s，t)=0

16、，REPLACT(s，"STUDENT"，q)="I AM A WORKER"。2. 已知下列字串：A="THIS"，f="S A MPLE"，c="GOOD"，d="NE"，b="V"，g="IS"S= CONCAT(a，CONCAT(CONCAT (b，SUBSTR(a，3，2)，SUBSTR(f，2，6)T=REPLACE(f，SUBSTR(f，3，5)，c)U= CONCAT (SUBSTR(c，3，1)，d)V= CONCAT

17、(s，CONCAT(b，CONCAT(t，CONCAT(b，u)问s="THIS IS SMPLE"，t="A GOOD"，v="THIS IS SMPLE A GOOD ONE"，STRLEN(s)=13，INDEX(v,g)=3，INDEX(u,g)各是什么=0？3. 简述下列每对术语的区别：空串和空格串 空串是不包含任何字符的串，长度为0，空格串指包含一个或者多个空格的串，空格也是字符串变量和串常量 串常量是指在程序中只可引用但不可改变其值的串，串变量时可以再运行中改变其值的。主串和子串是相对的，一个串中任意个连续的字符组成的串

18、就是这个串的子串，而包含子串的串就称为主串4. 两个字符串相等的充要条件是什么？串长度相等，并且各对应位置上的字符也相等5. 设已知两个串为：S1=“bc cad cabcadf”；S2=“abc”。试求两个串长度，并判断S2串是否是S1的子串。如果S2是S1的子串，指出S2在S1中的起始位置。S1的长度是14，S2的长度是3，S2是S1的子串，S2在S1的起始位置为9习 题 六一、判断题1. 二叉树是树的特殊情形。( 错 )2. 二叉树的先序遍历序列中，任意结点均处在其孩子结点之前。( 对 )3. 二叉链表是一种逻辑结构。( 错 )4. 由二叉树的先序序列和后序序列可以唯一确定一棵二叉树。(

19、 错 )5. n个结点的完全二叉树不唯一。( 错 )6. 树的后序遍历序列与其对应的二叉树的后序遍历序列相同。( 错 )7. 完全二叉树的某结点若无左孩子，则它必是叶子结点。( 对 )二、选择题 1. 将一棵树t转换为孩子兄弟链表表示的二叉树h，则t的后序遍历是h的( B )A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历2. 对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用( C)次序的遍历实现编号。A. 先序 B. 中序 C. 后序 D. 从根开始的层次遍历3. 已知一棵完全二叉树中共有76

20、8个结点，则该树中共有( B )个叶子结点。A. 383 B. 384 C. 385 D. 3864. 先序遍历和中序遍历相同的二叉树为( D )。A 只有根结点的二叉树 B. 根结点无左孩子的二叉树C 一般二叉树 D. 只有根结点的二叉树和所有结点只有右子树的二叉树三、简答题1. 一棵树的边集为(a,b)，(b,e)，(a,c)，(c,g)，(a,d)，(d,i)，(c,f)，(c,h)，(d,j)，(i,k),请画出此棵树的形态，并回答下列问题：(1) 树的根是哪个结点？A 哪些是叶子结点？ efghjk 哪些是分支结点？ abcdi(2) 各结点的度分别是多少？树的度是多少？4 结点 a

21、 b c d e f g h i j k 度 3 1 3 2 0 0 0 0 1 0 0 层次 1 2 2 2 3 3 3 3 3 3 4(3) 各结点的层次分别是多少？树的深度是多少？3以d为根的子树深度是多少？3(4) 结点i的双亲是哪个结点？d 祖先是哪个结点？A 孩子是哪些结点？K 兄弟是哪些结点？j2. 树和二叉树有哪些区别？树是无序树，而二叉树是有序树，二叉树的度不能大于2，它的两个分支是有先后顺序的。3. 已知二叉树的后序和中序序列如下，构造出该二叉树，写出它的前序遍历序列。 后序序列：ABCDEFG 中序序列：ACBGDFE GCABFDE4. 假设用于通信的电文由字符集a,b

22、,c,d,e,f,g中的字母构成，它们在电文中出现的频度分别为0.31, 0.16, 0.10, 0.08, 0.11, 0.20, 0.04(1) 为这7个字母设计哈夫曼编码。 a,b,c,d,e,f,g的编码分别为：11，102，010，1001，011，00，1000，(2) 对这7个字母进行等长编码，至少需要几位二进制数？哈夫曼编码与等长编码相比，能使电文总长压缩多少？WPL=2.61等长编码需要3bit，则压缩了（3-2.61）、3=13%习 题 七一、单项选择题1. 一个有n个顶点的无向图最多有_C_条边。A. n B. n(n-1) C. n(n-1)/2 D. 2n2. 一个有

23、4个顶点的无向完全图有_A_条边。A. 6 B. 12 C. 16 D. 203. 一个有5个顶点的连通图至少有_B_条边。A. 3 B. 4 C. 5 D. 64. _B_的邻接矩阵是对称矩阵。A. 有向图 B. 无向图 C. AOV网5. 邻接表是图的一种_B_。A. 顺序存储结构 B. 链接存储结构C. 索引存储结构 D. 散列存储结构6. 采用邻接表存储的图的深度优先遍历算法类似于二叉树的_A_。A. 前序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历7. 采用邻接表存储的图的广度优先遍历算法类似于二叉树的_D_。A. 前序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历8.

24、 任何一个无向连通图_B_最小生成树。 .只有一棵 B. 有一棵或多棵 C. 一定有多棵 D. 可能不存在9. 一个图的_B_表示法是唯一的，而_C_表示法是不唯一的。A. 三元组 B. 邻接矩阵 C. 邻接表 D. 索引二、简答题1. 对图7.23所示有向图，回答下列问题：(1) 该图是强连通图吗？若不是，则给出其强连通分量。(2) 请给出从顶点1到顶点3的所有的简单路径。(3) 请给出顶点1的度、入度和出度。(4) 请给出其邻接矩阵、邻接表及逆邻接表。习 题 八一、单选题1. 对线性表进行二分查找时,要求线性表必须 C 。A. 以顺序方式存储 B. 以链接方式存储C. 以顺序方式存储且结点

25、按关键字有序排列D. 以链接方式存储且结点按关键字有序排列2. 采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为 C 。A. n B. n/2C. (n+1)/2 D. (n-1)/23采用二分查找长度为n的线性时，每个元素的平均查找长度为 D 。A. O(n2) B.O(nlog2n)C. O(n) D. O(log2n)4. 有一个有序表为(5，7，8，22，32，40，45，62，70，77，82，97，100)，当二分查找值为82的结点时， C 次比较后查找成功。A. 1 B. 3 C. 4 D. 85. 从一个具有n个结点的单链表中查找其值等于x结点时，查找成功的情况

26、下，需平均比较 D 个结点。A. n B. n/2 C. (n1)/ 2 D. (n+1)/2二、填空题1. 假设在有序线性表A1，A20上进行二分查找，则比较一次查找成功的结点数为 1 ，则比较二次查找成功的结点数为 2 ，则比较三次查找成功的结点数为 4 ，则比较四次查找成功的结点数为 8 ，则比较五次查找成功的结点数为 5 ，平均查找长度为 3.7 。2. 在散列存储中，装填因子的值越大，存取数据元素时发生冲突的可能性 越大 ；的值越小，则发生冲突的可能性 越小 。三、简答题设有一组关键字(19，01，23，14，55，20，84，27，68，11，10，77)，采用哈希函数H(key)

27、 = key % 13采用开放地址法的线性探测再散列方法解决冲突，试在012的散列地址空间中对该关键字序列构造哈希表。0 1 2 3 4 5 6 7 8 9 10 11 1277 1 14 55 27 68 19 20 84 23 11 102. 对上题中的关键字序列，采用链地址法，画出相应的哈希表。3. 对有序表(5，8，27，36，45，48，57，72，89，95)，采用二分查找，画出二分查找过程的二叉判定树，并计算其平均查找长度。习 题 九一、单选题1. 在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是 D 。A. 希尔排序 B. 冒泡排序 C. 直接插入排序 D. 直接选择排序2. 设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用 B 排序