带答案的数据结构补充习题.doc

【精品文档】如有侵权，请联系网站删除，仅供学习与交流带答案的数据结构补充习题.精品文档.补充习题第一章第五章一、 单选或填空题1. 下列程序段中S语句的执行频度为 。for(i0；in；i+ ）for(j0；ji；j+ ） S；2. 下列算法的时间复杂度是（）。for(i0；in；i+ ）cii；3. 算法的时间复杂度可表示为 O(1)、线性阶 、平方阶O(n2)、对数阶O(logn)和指数阶O(2n)等。4 以下关于数据结构的基本概念中，叙述正确的是 A) 数据元素是数据不可分割的最小单位。B) 数据是数据对象的子集。C) 数据元素之间的关系在计算机中可用顺序映像和非顺序映像两种不同的方法表示。D) 数据结构在计算机中的表示又称为逻辑结构。5. 在数据结构中，数据的逻辑结构包括（）。 A) 线性结构和非线性结构 B) 逻辑结构和物理结构 C) 顺序结构和链式结构 D) 虚拟结构和抽象结构 6. 在数据结构中，数据的存储结构包括 。§ A) 线性结构和非线性结构 B) 逻辑结构和物理结构§ C) 顺序结构和链式结构 D) 虚拟结构和抽象结构 7. 线性结构的数据元素之间存在一种( )。A一对多关系B多对多关系C多对一关系D一对一关系8. 在长度为n的顺序表中插入一个元素，需要平均移动 个元素。A) n/2 B)nC) n(n-1) D) n(n+1)9. 在有n个元素的顺序表中做插入、删除运算，平均时间复杂度为 。10. 顺序表中逻辑上相邻的元素物理位置 相邻，单链表中逻辑上相邻的元素的物理位置 相邻。A)必然、必然 B)必然、不一定C)不一定、必然 D)不一定、不一定11相对于顺序存储而言，链式存储的优点是（）。A随机存取B节约空间C增、删操作方便D节点间关系简单12 以下关于头结点的描述中，叙述错误的是 A) 头结点是对链表首元结点的别称B) 若链表中附设头结点，则头指针一定不为空C) 头结点中不存储链表的数据元素，而是一些诸如表长之类的辅助信息D) 在单链表中附设头结点，插入或删除首元素时不必进行特殊处理13已知L是无表头结点的单链表，且P所指结点既不是首元结点，也不是尾元结点，则在P之后插入S所指结点，则执行（）。A) S->next=P->next； P->next=S；B) P->next=S->next； S->next=P；C) S->next=P； P->nextS；D) P->next=S； S->next=P；14. 已知L是带表头结点的非空单链表，且P结点是S结点的直接前驱。则删除S结点的语句序列为 。I. P->next = S ;free(P)II. P->next = P->next->next; free(S)III. P->next = S->next; free(S) IV. P = P->next ;free(S)A) I和II正确 B) II和 III正确C) III和IV正确 D) 全部正确15. 已知L是带表头结点的单链表，则删除首元结点的语句序列是（ ）。A) L->next =L->next->next; free(L)B) P = L ;L= P->next ;free(P)C) P = L->next ; L->next= P->next ;free(P)D) P = L ;L= P->next ;free(P)16. 已知L是一带有头结点的单链表的头指针，则该单链表为空的条件是 。17. 已知P结点是某双向链表的中间结点，则删除P结点的语句序列是 ， ，free(P);18. 设将整数1，2，3，4，5依次进栈，最后都出栈，出栈可以在任何时刻(只要栈不空)进行，则出栈序列不可能的是（ ）。A) 32415 B) 45231 C) 32145 D) 4532119. 在栈中由顶向下已存放元素c, b, a 在第4个元素d入栈前，栈中元素可以出栈，则不可能的出栈序列是A) dcba B) cbda C) cdba D) cadb21. 设有栈S和队列Q，其初始状态为空，元素a1,a2,a3,a4,a5,a6依次入栈，出栈的元素进入队列Q。若元素出队列的顺序是a2,a4,a3,a6,a5,a1，则栈的容量至少是 。22. 某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，则abcde顺序入队，不可能的到的顺序是（）。AbacdeBdbaceCdbcaeDecbad23. 设用一维数组An存储一个栈，令An为栈底，用整型变量T指示当前栈顶位置，AT为栈顶元素。当从栈中弹出一个元素时，变量T的变化为（ ）。A) T=T+1 B) T=T-1 C) T不变 D) T=n-124. 循环队列是满队列的条件是 。A）Q.rearQ.front B）(Q.rear+1) % maxsizeQ.frontC）Q.rear0 D）Q.front025. 在具有m个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队满的条件是（ ）A. front= (rear1) % m B. front1= rearC. front= rear D. rear= m26. 在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队空的条件是（ ）A)front= (rear1) % n B)front1=rearC)front=rear D)front=027. 循环队列用数组A0m-1存放其数据元素。设front指向其实际的队头，rear指向其实际队尾的下一个位置，则当前队列中的数据元素有 个。28 在串的运算中，StrLength(Concat (aa，bb)的返回值为 A) 0B) 8C) 6D) 429设s1”I have_”，s2”a dream”，则strcat(s1, s2)的值是 I have_ a dream ，SubString(s1,4,3)的值是 ave 。30. 设s1”I am a student”，s2”a student”，则Index(s1,s2)的值是 。31. 假设有二维数组A5×6，每个元素用相邻的4个字节存储，存储器按字节编址。已知A的基地址为1000，则数组A的最后一个元素a45的第一个字节的地址是 ；按行存储时，元素a14的第一个字节的地址是 。32. 已知二维数组A1.7，1.7按列存放，其起始存储位置为100，每个元素占用4个字节，则元素A4,6的第一个字节的地址为 。A）204 B）252 C）208 D）25633. 一个非空广义表的表头（）。A一定是子表 B一定是原子C不能是子表 D可以是原子，也可以是子表34. 设广义表L（(a,b),c,()），则head(L) ，tail(L) 。二、 算法题1. 写出下列程序段的功能。Status A(LinkedList L) /L是无表头结点的单链表If(L &&L->next) Q=L; L=L->next; P=L; While (P->next) P=P->next; P->next=Q; Q->next=NULL; Return OK; 2. 写出下列程序段的输出结果。void main() Stack S; char x,y; InitStack(S); x=i; y=s; Push(S,x);Push(S,r);Push(S,y); Pop(S,x); Push(S,h);Push(S,x); Pop(S,x); Push(S,c); while (!StackEmpty(S) Pop(S,y);printf(y); printf(x);3. 写出下列程序段的输出结果。void main() Queue Q; InitQueue(Q); char x=e, y=c; EnQueue(Q, a);EnQueue(Q, d);EnQueue(Q, y); DeQueue(Q, x); EnQueue(Q, x); DeQueue(Q, x); EnQueue(Q, r); while (!QueueEmpty(Q) DeQueue(Q, y); printf(y); printf(x);4. 已知L是带头结点的单链表。试写一算法求该单链表的长度。5. 已知L是带头结点的单链表。试写一算法在该链表上查找值为x的元素。6. 将带头结点的L中的第i个数据元素删除。7. 在带头结点的L中第i个元素之前插入数据元素e 。8. 正位序输入n个元素的值，建立带头结点的单链表L。9. 已知线性表中的元素以值递增有序排列，并以带有头结点的单链表作存储结构。试写一算法删除表中所有值大于mink且小于maxk的元素，同时释放被删除的结点空间。10. LA和LB是两个数据元素按升序排列的单链表，将LA和LB合并为有序单链表LC。写出这两个有序链表合并的算法。第六章一、 单选或填空题1. 已知完全二叉树的第7层上有10个叶子结点，则整个二叉树的结点数最多是 A) 73 B) 63 C) 235 D) 2452. 300个结点的完全二叉树的叶结点有 个。3一个具有1025个结点的二叉树的高h为_。A）11 B）10 C）11至1025之间 D）10至1024之间4. m叉树的第i层至多有 个结点5. 将一棵有100个节点的完全二叉树从上到下，从左到右依次对节点进行编号，根节点的编号为1，则编号为49的节点的右孩子编号为（）。ABCDEFA99B98C50D486把如右图所示的树转换成二叉树时，C是（ ） A. A的左子女 B. A的右子女 C. B的左子女 D. B的右子女7. 设森林F中有3棵树，其结点个数分别是n1、n2和n3，则与森林对应的二叉树根结点的右子树上的结点个数是 。 A) n1-1 B)n1+n2 C) 0 D) n2+n38.在一颗度为4的树T中，若有20个度为4的结点，10个度为3的结点，5个度为2的结点，10个度为1的结点，则树T的叶结点个数有 个。9. 一棵二叉树中序遍历结果为DCBAEFG，后序遍历结果为DCBGFEA。则此二叉树先序遍历的结果应为A) ABCDEFG B)ABECFDG C)AEBFCGD D)不能确定10. 将一棵树t 转换为孩子兄弟链表表示的二叉树h，则t 的后根遍历是h 的A）先序遍历 B）中序遍历 C）后序遍历 C）层序遍历11.现有一段电文共100个字符，其中A出现50次，B出现20次，C出现5次，D出现10次，E出现15次。现对这5个字符进行哈夫曼编码，则其平均码长为 。二、 解答题1. 某二叉树的中序遍历结果为DEFABCG；后序遍历结果为FEDCBAG。（1）画出此二叉树，并给出其先序遍历的结果。（2）画出与这棵二叉树对应的树（森林）。2. 已知一个二叉树的先序遍历序列为：ABDGIECFH；中序遍历序列为：DIGBEAFHC。（1）画出该二叉树（2）画出下图所示森林对应的二叉树。AACABADAEAHAIAFAGAJAKLA3. 某二叉树层序序列为abcdefghij，中序序列为bgdhjaecif。（1）画出该二叉树；（2）画出该二叉树的后序后继线索树；（3）画出该二叉树对应的树或森林。4. 已知某通讯用电文仅有A、B、C、D、E、F六个字符构成，其出现的频率分别为26，8，17，11，28，10，请首先建立哈夫曼树，然后给出六个字符的哈夫曼编码（注：建立哈夫曼树时权值小的为左子树，权值大的为右子树）。三、算法题1. 以二叉链表作为二叉树的存储结构，编写以下算法：（1）求先序序列为k的结点的值（2）求二叉树中叶子结点的数目（3）交换所有结点的左右子树（4）求二叉树的深度第七章一 单选或填空题1. 若某有向图的邻接矩阵A只有0和1两种元素，其中aij1表示有向图中存在弧<i,j>，则编号为i顶点的入度可用 表示。A) 邻接矩阵中第i行元素之和 B) 邻接矩阵中第i列元素之和 C) 邻接矩阵中对角线元素之和 D) 以上均不正确2. 使用邻接表作为某无向图的存储结构，若无向完全图中有n个顶点，则邻接表中必存在 个表结点。A)n2 B)2n C)n(n-1) D) 2n-13. 一个含有n个顶点和e条边的无向图，在其邻接矩阵存储结构中共有（）零元素。AeB2eCn2-eDn2-2e4在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。A1/2B1C2D45下列关于图的叙述中，正确的是（ ）、 回路是简单路径 、存储稀疏图，用邻接矩阵比邻接表更省空间 、若有向图中存在拓扑序列，则该图不存在回路 A仅 B仅、 C仅 D仅、 6. 有n个顶点的无向图至少有 条边才能确保是一个连通图。7在有n个结点的无向图中，其边数最多为 。8. 对于具有n个结点的连通图，它的最小生成树中有 条边。A)n2 B)n-1 C)n(n-1) D) n(n-1)/29. 关键路径是AOE网中A）从源点到汇点的最长路径 B）从源点到汇点的最短路径C）最长回路D）最短回路10. 以下关于图的描述中，正确的是A) n个顶点的无向完全图有条边。B) 对任何用顶点表示活动的网络（AOV网）进行拓扑排序的结果是唯一的。C) 若图G的邻接矩阵是对称的，则G一定是无向图cabedD) 有向图的邻接矩阵一定是非对称矩阵11. 对下图进行拓扑排序，可以得到不同的拓扑序列的个数是（）A5B3C2D112下图为用边表示活动的AOE-网。则V8的最早发生时间是 。二、解答题1. 已知某无向图的邻接表存储结构如下图所示，求解下列问题：（1）画出它的无向图；（2）画出它的的邻接矩阵存储结构；（3）从顶点A出发，画出其广度优先生成树。0 A 1 41 B 0 2 52 C 1 3 43 D 2 54 E 0 2 55 F 1 3 42. 已知无向带权图G的邻接矩阵如下所示。（1）从顶点a出发，求其深度优先生成树； （2）从顶点a出发，根据普里姆算法构造最小生成树，过程在下面的图(1)至(5)中画出。（3）给出邻接表存储结构；3. 对于如下图所示的带权有向图，求解关键路径, 计算各事件（顶点）的最早发生时间和最迟发生时间，各活动（弧）的最早开始时间和最迟开始时间。请填写在答题纸的表格中。bbdg64521187244acdefhk表1 计算各事件（顶点）的最早发生时间和最迟发生时间，请填写在表1的空白处。顶点abcdefghkve06457151418vl0810161418表2 计算各活动（弧）的最早开始时间和最迟开始时间，请填写在表2的空白处。弧abacadbecedfegehfhgkhke00064571514l38101614 4.对于右图，求解下列问题：（1）写出该图的邻接矩阵；（2）写出全部拓扑排序序列；（3）从顶点V1出发，给出深度优先遍历生成树；（4）按照迪杰斯特拉算法，求V1结点到各点的最短路径，填写表1的空白处。终点从V1到各终点的距离和最短路径的求解过程i=1i=2i=3i=4i=5i=6i=7V22-V333-V4-V51313-V6-V7-V8161616vjv2v3第九章一单选或填空题1已知一个长度为11的有序表，使用折半查找的方法，查找第8个元素时所需进行的关键字比较次数为 。2. 已知一个长度为16的有序表，使用折半查找的方法，查找一个不存在的元素，则所需进行的关键字比较次数最多是 。A4B5C6D73. 在二叉排序树中，关键字值最大的结点A）左指针一定为空 B）右指针一定为空C）左右指针均为空 D）左右指针均不为空4 对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是（ ） A95,22,91,24,94,71 B92,20,91,34,88,35 C21,89,77,29,36,38 D12,25,71,68,33,34 5AVL树是一种平衡的二叉排序树，树中任一结点的A左、右子树的高度均相同 B. 左、右子树高度差的绝对值不超过1C. 左子树的高度均大于右子树的高度 D. 左子树的高度均小于右子树的高度6. 以下关于查找方法的描述中，错误的是 A) 平衡二叉树一定也是二叉排序树。B) 有序表的折半查找判定树是二叉排序树。C) 中序遍历一棵二叉排序树，可以得到其数据元素的升序排列。D) 后序遍历一棵二叉排序树，可以得到其数据元素的降序排列。7.下列二叉排序树中，满足平衡二叉树定义的是（ ）8、在下列所示的平衡二叉树中插入关键字48后得到一棵新平衡二叉树，在新平衡二叉树中，关键字37所在结点的左、右子结点中保存的关键字分别是（ ）A、13，48 B、24，48 C、24，53 D、24，909. 从理论上讲，将数据以何（）结构存放，则查找一个数据所用时间不依赖于数据个数n.A）二叉查找数 B）链表 C）二叉树D）哈希表10 为提高散列（Hash）表的查找效率，可以采取的正确措施是（ ）、增大装填（载）因子 、设计冲突（碰撞）少的散列函数、处理冲突（碰撞）时避免产生聚集（堆积）现象A仅 B仅 C仅、 D仅、二、解答题1. 设记录关键字集合key=33,20,53,55,23,38,40,65，选取哈希函数为H(x)=key mod 11；解决冲突的方法为“线性探测法”。（1）请按上述条件将key中各值依次填入下表中：（2）求该哈希表查找成功和查找不成功情况下的平均查找长度。2. 设记录关键字集合key=32,13,49,55,22,39,20，选取哈希函数为H(x)=key mod 7；解决冲突的方法为“链地址法”。（1）画出所构造的哈希表；（2）求该哈希表查找成功和查找不成功情况下的平均查找长度。3. 设记录关键字集合key=32,13,49,55,22,39,20，解决冲突的方法为“线性探测法”，要求装填因子为：0.7，哈希函数的形式为H(x)=key mod P，散列表的地址从0开始。（1）构造哈希函数；（2）画出所构造的哈希表；（2）求该哈希表查找成功和查找不成功情况下的平均查找长度。4. 选取哈希函数H(key)=(3*key) mod 11。用开放定址法处理冲突，di=i(7*key) % 10+1)(i=1,2,3)。试在010的散列地址空间对关键字序列（22，41，53，46，30，13，01，67）：1） 构造该序列对应的哈希表；2） 求等概率情况下查找成功的平均查找长度。哈希表如下图所示：5. 从空树开始，依次插入13，34，51，24，62，43，75，18，画出建立2-3树后的状态，并分别画出删除43、24后的2-3树状态。6. 画出对长度为12的有序表进行折半查找的判定树，并求其等概率查找成功时的平均查找长度。第十章一、 单选或填空题1. 数组中原有数据如下：15，13，20，18，12，60。下面是一组用不同排序方法进行一趟排序后的结果。则ABCD四个选项中，说法正确的是 I 12，13，15，18，20，60 II 13，15，18，12，20，60III 13，15，20，18，12，60 IV 12，13，20，18，15，60V 13，15，18，20，12，60A) I快速排序；II简单选择排序；III直接插入排序；IV冒泡排序；V归并排序B) I冒泡排序；II快速排序；III归并排序；IV简单选择排序；V直接插入排序C) I快速排序；II冒泡排序；III直接插入排序；IV简单选择排序；V归并排序D) I直接插入排序；II归并排序；III快速排序；IV简单选择排序；V冒泡排序 2. 对一组数据(2，12，16，88，5，10)进行排序，若前三趟排序结果如下：第一趟：2，12，16，5，10，88第二趟：2，12，5，10，16，88第三趟：2，5，10，12，16，88则采用的排序方法可能是( )A.冒泡排序法 B.希尔排序法 C.归并排序法 D.基数排序法3. 若一组记录的排序码为(45，78，56，36，40，87)，则初始小根堆的结果为A36，45，56，78，40，87B87，78，56，36，40，45C40，36，45，56，78，87D36，40，56，78，45，874已知序列25,13,10,12,9是大根堆，在序列尾部插入新元素18，将其再调整为大根堆，调整过程中元素之间进行的比较次数是（ ） A1 B2 C4 D55. 已知关键序列 5，8，12，19，28，20，15，22 是小根堆（最小堆），插入关键字 3，调整后得到的小根堆是A3，5，12，8，28，20，15，22，19B. 3，5，12，19，20，15，22，8，28C3，8，12，5，20，15，22，28，19D. 3，12，5，8，28，20，15，22，197. 下列排序算法中属于不稳定的排序方法是 A)直接插入排序 B)冒泡排序 C)简单选择排序 D)归并排序8下列排序方法的时间复杂度不为线性对数阶的是 。A）快速排序 B）2-路归并排序 C）希尔排序D）堆排序9最好和最坏时间复杂度均为O(nlogn)且稳定的排序方法是 。A）快速排序 B）2-路归并排序 C）希尔排序D）堆排序10. 对于快速排序，若初始关键字有序排列，则时间复杂度为 。11分别采用堆排、快序速排序、直接插入排序和归并排序算法对初始状态为递增序列的表按递增顺序排序，最省时间的是 算法。三、 解答题1. 已知待排序的序列为37，65，56，8，76，3，89，34，21，46，试完成下列各题（本题排序均指非递减有序排列）：(1) 写出希尔排序每一趟排序的结果；（d1=5,d2 = 3,d3 = 1） (2) 写出第一趟快速排序过程及结果。（3）画出初始堆，以及第一次交换后，经过堆调整重新形成的堆。2. 已知待排序的序列为37，65，56，8，76，3，89，34，21，46，试完成下列各题（本题排序均指非递减有序排列）：(1) 写出直接插入排序每一趟排序的结果； (2) 写出2路归并排序每一趟排序的结果。参考答案：第一章-第五章一单选与填空1. n(n-1)/2 2.O(n) 3.常数阶 O(n) 4.C 5.A 6.C 7.D 8.A 9. O(n) 10.B 11.C 12.A 13.A 14.B 15.C 16.L->next=NULL 17. P->prior->next=P->next P-> next -> prior =P->prior18.B 19.D 21.3 22.C 23.A 24.B 25.A 26.C 27. (rear-front+m)%m 28.D29. I have a dream ， ave 30. 6 31. 1116,1040 32.B 33.D 34.(a,b) (c,( )二、算法题1. 程序的功能： 对长度大于等于2的单链表，将首元结点插入到表尾。2. 程序的运行结果：chris3. 程序的运行结果：card4.-10 题答案：.#define OK 1#define ERROR 0typedef int Status;typedef struct LNode int data; struct LNode *next;LNode,*LinkList;4. 题答案int Length(LinkList L)/求链表的长度 k=0; p=L;   while (p->next) p=p->next; k+;   return k;/Length 5. 题答案LNode* Locate(LinkList L, Elemtype x)/链表上的元素查找,返回指针  p=L->next;while (p&&p->data!=x) p=p->next;   return p;/Locate 6. 题答案Status ListDelete_L(LinkList &L,int i,ElemType &e)/将线性表L中第i个数据元素删除 p=L;j=0; while(p->next &&j<i-1)/寻找第i个结点，并令p指向其前驱 p=p->next; +j; if(!(p->next)|j>i-1) return ERROR; /删除位置不合理 q=p->next; /临时保存被删结点的地址以备释放 p->next=q->next; /改变删除结点前驱结点的指针域 e=q->data; /保存删除结点的数据域 free(q); /释放删除结点的空间 return OK; /ListDelete_L 7. 题答案Status ListInsert_L(LinkList &L,int i,ElemType e) /在第i个元素之前插入数据元素e p=L;j=0; while(p&&j<i1)p=p->next;+j;/寻找第i1个结点 if(!p|j>i1)return ERROR;/i大于表长 + 1或者小于1 s= (LinkList) malloc ( sizeof (LNode); /生成新结点s s->data=e; /将结点s的数据域置为e s->next=p->next; /将结点s插入L中 p->next=s; return OK; /ListInsert_L 8. 题答案void CreateList_L(LinkList &L,int n) /正位序输入n个元素的值，建立带表头结点的单链表L L=(LinkList) malloc (sizeof (LNode); L->next=NULL; r=L; /尾指针r指向头结点 for(i=0;i<n;+i) p = (LinkList) malloc (sizeof (LNode); /生成新结点 scanf(&p->data); /输入元素值 p->next=NULL; r->next=p; /插入到表尾 r=p; /r指向新的尾结点 /CreateList_L 9. 题答案Status Delete_Between(Linklist &L,int mink,int maxk)/删除元素递增排列的链表L中值大于mink且小于maxk的所有元素  q=L; p =L->next; while(p && p->data <= mink ) q=p;p = p->next; /q是最后一个不大于mink的元素, /p是第一个大于mink的元素  if(!p) return ERROR;  /如果没有比mink更大的元素  while(p && p->data < maxk) q->next = p->next; free(p); p =q->next;return OK;/Delete_Between10. 题答案void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc) pa=La->next; pb=Lb->next; pc=Lc=La; /用La的头结点作为Lc的头结点 while(pa && pb) if(pa->data<=pb->data) pc->next=pa;pc=pa;pa=pa->next; elsepc->next=pb; pc=pb; pb=pb->next; pc->next=pa?pa:pb; /插入剩余段 free(Lb); /释放Lb的头结点第六章一单选与填空1.C 2. 150 3.C 4.mi-1 5.A 6.D 7.D 8. 86 9.A 10.B 11. 1.95二解答题1. （1）先序遍历：GADEFBC；二叉树的形态见下左图； （2）对应的树见下右图2.（1）画出