《武汉理工大学数据结构复习题》由会员分享，可在线阅读，更多相关《武汉理工大学数据结构复习题（10页珍藏版）》请在金锄头文库上搜索。
1、1复习题集复习题集一判断题一判断题（）1 线性表在物理存储空间中也一定是连续的。 （）2 顺序存储方式只能用于存储线性结构。（）3 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。（）4 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。（）5 二叉树的度为 2。（）6 若二叉树用二叉链表作存贮结构，则在 n 个结点的二叉树链表中只有 n1 个非空指针域。（）7 二叉树中每个结点的两棵子树的高度差等于 1。 （）8 用二叉链表法存储包含 n 个结点的二叉树，结点的 2n 个指针区域中有 n+1 个为空指针。（
2、 ）9 在冒泡法排序中，关键值较小的元素总是向前移动，关键值较大的元素总是向后移动。（ ）10计算机处理的对象可以分为数据和非数据两大类。（ ）11数据的逻辑结构与各数据元素在计算机中如何存储有关。（ ）12算法必须用程序语言来书写。（ ）13判断某个算法是否容易阅读是算法分析的任务之一。（ ）14顺序表是一种有序的线性表。（ ）15分配给顺序表的内存单元地址必须是连续的。（ ）16栈和队列具有相同的逻辑特性。（ ）18树形结构中每个结点至多有一个前驱。（ ）19在树形结构中，处于同一层上的各结点之间都存在兄弟关系。（ ）20如果表示图的邻接矩阵是对称矩阵，则该图一定是无向图。（ ）21如果表
3、示图的邻接矩阵是对称矩阵，则该图一定是有向图。（ ）22顺序查找方法只能在顺序存储结构上进行。（ ）23折半查找可以在有序的双向链表上进行。（ ）24满二叉树中不存在度为 1 的结点。（ ）25完全二叉树中的每个结点或者没有孩子或者有两个孩子。（ ）26对 n 个元素知心快速排序，在进行第一次分组时，排序码的比较次数总是 n-1 次。（ ）27在有向图中，各顶点的入度之和等于各顶点的出度之和。一、选择题一、选择题（ ）1. 在在 n 个结点的顺序表中，算法的时间复杂度是个结点的顺序表中，算法的时间复杂度是 O(1)的操作是：的操作是：A) 访问第 i 个结点（1in）和求第 i 个结点的直接前
4、驱（2in） C) 删除第 i 个结点 （1in） B) 在第 i 个结点后插入一个新结点（1in） D) 将 n 个结点从小到大排序（C）2. 算法分析的目的是：算法分析的目的是：A) 找出数据结构的合理性 B) 研究算法中的输入和输出的关系 C) 分析算法的效率以求改进 D) 分析算法的易懂性和文档性2（A）3. 算法分析的两个主要方面是：算法分析的两个主要方面是：A) 空间复杂性和时间复杂性 B) 正确性和简明性 C) 可读性和文档性 D) 数据复杂性和程序复杂性（B）4. 计算机算法必须具备输入、输出和计算机算法必须具备输入、输出和 等等 5 个特性。个特性。A) 可行性、可移植性和可
5、扩充性 B) 可行性、确定性和有穷性 C) 确定性、有穷性和稳定性 D) 易读性、稳定性和安全性（B）5.一个向量第一个元素的存储地址是一个向量第一个元素的存储地址是 100，每个元素的长度为，每个元素的长度为 2，则第，则第 5 个元素的地址是个元素的地址是 （A）110 （B）108 （C）100 （D）120（A）5. 链接存储的存储结构所占存储空间：链接存储的存储结构所占存储空间：（A）分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 （B）只有一部分，存放结点值 （C） 只有一部分，存储表示结点间关系的指针 （D） 分两部分，一部分存放结点值，另一部分存放结点所占单元数（
6、 ）6. 一个栈的输入序列为一个栈的输入序列为 1，2，3，n，若输出序列的第一个元素是，若输出序列的第一个元素是 n，输出第，输出第 i（1in）个元素）个元素是。是。A) 不确定 B) ni1 C) i D) ni（ ）7. 最大容量为最大容量为 n 的循环队列，队尾指针是的循环队列，队尾指针是 rear，队头是，队头是 front，则队空的条件是，则队空的条件是 （ ） 。A) (rear1)% n=front B) rear=front C) rear1=front D) (rearl) % n=front（ ）8. 循环队列循环队列 A0.m1存放其元素值，用存放其元素值，用 fro
7、nt 和和 rear 分别表示队头和队尾，则当前队列中的元素数分别表示队头和队尾，则当前队列中的元素数是是 。A) (rearfrontm)%m B) rearfront1 C) rearfront1 D) rearfront（ ）9. 按照二叉树的定义，具有按照二叉树的定义，具有 3 个结点的二叉树有（个结点的二叉树有（ ）种。）种。A) 3 B) 4 C) 5 D) 6（ ）10. 具有具有 n(n0)个结点的完全二叉树的深度为个结点的完全二叉树的深度为 。() log2(n) () log2(n) () log2(n) +1 () log2(n)+1（ ）11在高度为在高度为 h 的完全
8、二叉树中，表述正确的是（的完全二叉树中，表述正确的是（ ）A.度为 0 的结点都在第 h 层上 B.第 i(1inext ; (2) P-next = P; (3) P-next = P-next-next (4) P-next = P-next-next; (5) while(P!=NULL) P = P-next ; (6) while(Q-next != NULL) P = Q; Q=Q-next; (7) while(P-next != Q) P = P-next; (8) while(P-next-next != Q) P = P-next; (9) while(P-next-nex
9、t != NULL) P = P-next; (10) Q = P; (11) Q = P-next; (12) P = L ; (13) L = L-next; (14) free(Q);3. 栈是一种特殊的线性表，允许插入和删除运算的一端称为 。不允许插入和删除运算的一端称为 。4. 用 S 表示入栈操作，X 表示出栈操作，若元素入栈的顺序为 1234，为了得到 1342 出栈顺序，相应的 S 和 X 的操作串为 。5数据的逻辑结构可以分为 和 两大类。6数据的运算用 表示。7逻辑上相邻的结点在存储器中也相邻，这是 存储结构的特点。8在长度为 n 的顺序表上实现定位操作，其算法的时间复杂度
10、为 。9为了实现随机访问，线性结构应该采用 存储。10在长度为 n 的顺序表中插入一个元素，最多要移动 个元素。11栈的存储结构主要有 和 两种。12在编写程序的时候，如果栈的最大长度难以预先估计，则最好使用 栈。13在树形结构中，如果某结点 ，则称该结点为根结点；如果某结点 ，则称该结点为叶子。14在树形结构中，每个结点最多只有一个前驱。15 由 3 个结点所构成的二叉树有 种形态。 16二叉树的前序遍历按如下三个步骤进行： ； ； 。17二叉树的中序遍历按如下三个步骤进行： ； ； 。ACEBFGDH518在 n 个顶点的无向图中，至少有 条边，至多有 条边。19在 n 个顶点的有向图中，
11、至少有 条边，至多有 条边。20如果排序不改变关键字相同的记录之间的相对次序，则称该排序方法是稳定的。21如果排序改变了关键字相同的记录之间的相对次序，则称该排序方法是不稳定的。22在一个图中，所有顶点的度数之和是所有边数的 倍。23无向图中边的数目等于邻接矩阵中非零元素个数的 倍。24在有序表（2，4，6，8，10，12，14，16，18）上用折半查找法查找元素 9，其中第二次被比较的元素是 。25在有序表（2，4，6，8，10，12，14，16，18）上用折半查找法查找元素 9，其中第三次被比较的元素是 。三、简答题三、简答题1. 写出下列程序段的输出结果（队列中的元素类型 QElem T
12、ype 为 char） 。 void main( ) Queue Q; Init Queue (Q); Char x=e; y=c; EnQueue (Q,h); EnQueue (Q,r); EnQueue (Q, y); DeQueue (Q,x); EnQueue (Q,x); DeQueue (Q,x); EnQueue (Q,a); while(!QueueEmpty(Q) DeQueue (Q,y); printf(y); ; Printf(x); 2. 简述以下算法的功能（栈和队列的元素类型均为 int） 。 void algo3(Queue int d; InitStack(S
13、); while(!QueueEmpty(Q) DeQueue (Q,d); Push(S,d); ; while(!StackEmpty(S) Pop(S,d); EnQueue (Q,d); 3. 描述以下三个概念的区别：头指针、头结点、首元结点（第一个元素结点） 。在单链表中设置头结点的 作用是什么？ 答：首元结点是指链表中存储线性表中第一个数据元素 a1的结点。为了操作方便，通常在链表的首元 结点之前附设一个结点，称为头结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表 进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理。头指针是指向链表中第一个结点 （或为头
14、结点或为首元结点）的指针。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空。 否则表示空表的链表的头指针为空。这三个概念对单链表、双向链表和循环链表均适用。是否设置头结点， 是不同的存储结构表示同一逻辑结构的问题。6头结点headdatalink头指针 首元结点 简而言之， 头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针； 头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息（内放头指针？ 那还得另配一个头指针！） 首元素结点是指链表中存储线性表中第一个数据元素 a1的结点。4. 对以下单链表执行下列语句，简述代码的功能，并画出单链表结果示意图。T = L; while(T-next != NULL) T-data = 2 * T-data; T = T-next; 5. 请画出下图的邻接矩阵和邻接表6. 树和二叉树之间有什么样的区别与联系？7. 一棵二叉树中的结点的度或为
