《数据结构复习题及答案》由会员分享，可在线阅读，更多相关《数据结构复习题及答案（15页珍藏版）》请在金锄头文库上搜索。
1、复习题（一）一填空题（每空 1 分，共 15 分）1. 一个算法的效率可分为_效率和_效率。2. _是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。3. 设 S=“A;/document/Mary.doc”，则 strlen(S)= _， “/”的字符定位的位置为_。4. 设数组 a160, 170的基地址为 2048，每个元素占 2 个存储单元，若以列序为主序顺序存储，则元素 a32,58的存储地址为_。5. 一棵深度为 6 的满二叉树有_个分支结点和_个叶子。6. 用 5 个权值3, 2, 4, 5, 1构造的哈夫曼（Huffman）树的带权路径长度是 。7. 设有
2、一稀疏图 G，则 G 采用 存储较省空间。8. 快速排序算法是对 算法的一种改进。9. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 。10. 大多数排序算法都有两个基本的操作： 和 。11. 设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码按字母序的升序重新排列，则：快速排序一趟扫描的结果是 。二 选择题（每题 2 分，共 30 分）（ ）1数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：（A）存储结构 （B）逻辑结构 （C ）顺序存储结构 （D ）链式存储结构（ ）2. 向一个有 127 个元素的顺序表中插入一个新
3、元素并保持原来顺序不变，平均要移动 个元素（A）8 （B）63.5 （C）63 （D）7（ ）3. 链接存储的存储结构所占存储空间：（A） 分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针（B） 只有一部分，存放结点值（C） 只有一部分，存储表示结点间关系的指针（D） 分两部分，一部分存放结点值，另一部分存放结点所占单元数（ ）4. 设 a1、a 2、a 3 为 3 个结点，整数 P0，3，4 代表地址，则如下的链式存储结构称为P0 3 4P0 a1 3 a2 4 a3 0（）循环链表 （）单链表 （）双向循环链表 （）双向链表（ ）5双向循环链表的每个结点中包括两个指针 next
4、 和 previous，分别指向该结点的后继和前驱结点。现要删除指针 p 所指向的结点，下面的操作序列中哪一个是正确的？（A）p-next-previous = p-previous; p-previous-next = p-next；（B）p-next- previous = p-next; p-previous-next = p-previous；（C）p-previous-next = p-previous; p-next-previous = p-next；（D）p-priou-next-next = p-next; p-next-previous = p-previous；（ ）6.
5、 若已知一个栈的入栈序列是 1，2，3，n，其输出序列为p1，p 2，p 3，p n，若 p1=n，则 pi 为：（）i （）n =i （）n- i+1 （）不确定）7. 数组 Qn用来表示一个循环队列，f 为当前队列头元素的前一位置，r 为队尾元素的位置，假定队列中元素的个数小于 n，计算队列中元素的公式为：（）rf （） （nfr）% n （）nrf （）（nr f）% n（ ）8. 设串 s1=ABCDEFG，s 2=PQRST，函数 con(x,y)返回 x 和 y 串的连接串，subs(s, i, j)返回串 s 的从序号 i 开始的 j 个字符组成的子串， len(s)返回串 s
6、的长度，则con(subs(s1, 2, len(s2), subs(s1, len(s2), 2)的结果串是：（）BCDEF （）BCDEFG （）BCPQRST （）BCDEFEF（ ）9. 设矩阵 A 是一个对称矩阵，为了节省存储，将其下三角部分（如右图所示）按行序存放在一维数组 B1, n(n-1)/2 中，对下三角部分中任一元素 ai,j（ij） ，在一维数组 B 中下标 k 的值是：（）i(i-1)/2+j-1 （）i(i-1)/2+j （）i(i+1)/2+j-1 （）i(i+1)/2+j（ ）10. 具有 n(n0)个结点的完全二叉树的深度为 。nnaaA,2,1,2,1,L（
7、） log2(n) （） log2(n) （） log2(n) +1 （） log2(n)+1（ ）11. 深度优先遍历类似于二叉树的（）先序遍历 （B）中序遍历 （C ）后序遍历 （D ）层次遍历（ ）12. 已知图的邻接矩阵如右图，根据算法，则从顶点 0 出发，按深度优先遍历的结点序列是：（A）0 2 4 3 1 5 6 （B）0 1 3 5 6 4 2 （C）0 4 2 3 1 6 5 （D）0 1 3 4 2 5 6（ ）13. 设哈希表长度为 11，哈希函数为 H（key）=key mod 11。表中已有 4 个元素H（15）=4；H（38）=5 ；H（61）=6；H （84）=7
8、其余地址为空，若用二次探测再散列处理冲突，关键字为 49 的元素的地址是_。（A）3 （B）5 （C ）8 （D）9（ ）14. 任何一个无向连通图的最小生成树（）只有一棵 （B）一棵或多棵 （C）一定有多棵 （D）可能不存在（ ）15. 下述几种排序方法中，要求内存最大的是（）插入排序 （B）快速排序 （C ）归并排序 （D ）选择排序三 判断题（每题 2 分，共 20 分）（ ）1. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。（ ）2. 链表的物理存储结构具有同链表一样的顺序。（ ）3. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。
9、 （ ）4. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。（ ）5. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。（ ）6. 栈和队列是一种非线性数据结构。 （ ）7. 二叉树中每个结点的两棵子树的高度差等于 1。 （ ）8. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。 （ ）9. 二叉树中所有结点个数是 2k-1-1，其中 k 是树的深度。（ ）10. 用二叉链表法（link-rlink）存储包含 n 个结点的二叉树，结点的2n 个指针区域中有 n+1 个为空指针。0110010四 简答题（三题，共 12
10、分）1. 给定如图所示二叉树 T，请画出与其对应的中序线索二叉树。 （5 分）解答：2. 假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：（7 分）(1). 画出描述折半查找过程的判定树；(2). 若查找元素 54，需依次与哪些元素比较？(3). 假定每个元素的查找概率相等，求查找成功时的平均查找长度。解答：五 算法理解题：（共 13 分）1. 设如下图所示的二叉树 B 的存储结构为二叉链表，root 为根指针，结点结构为：(lchild,data,rchild)。其中 lchild，rchild 分别为指向左右孩子的指针，data
11、为字符型，root 为根指针，对下列二叉树 B，执行下列算法 traversal(root)，试指出其输出结果（4 分） ；二叉树 B解答：2. 请对下图的无向带权图，写出它的邻接矩阵，并按普里姆算法求其最小生成树。 （9 分）2825 3340 60 08 54 55AB DC F GEC 的结点类型定义如下：struct nodechar data;struct node *lchild, rchild;C 算法如下：void traversal(struct node *root)if (root)printf(“%c”, root-data);traversal(root-lchild
12、);printf(“%c”, root-data);traversal(root-rchild);六 算法设计题（10 分）编写按层次顺序（同一层自左至右）遍历二叉树的算法。 （10 分）解答：复习题（一）答案一、填空题(每空 1 分，共 15 分)1. 时间；空间2. 队列3. 20；34. 89505. 31；326. 337. 邻接表8. 起泡9. 顺序查找（线性查找）10. 比较；移动11. F H C D P A M Q R S Y X二、 单项选择题(每空 2 分，共 30 分，多选漏选均不得分)1. C 2. B 3. A 4.B 5.A6. C 7. D 8. D 9.B 10
13、.C11. A 12. D 13. A 14.A 15.C三、判断题(每题 2 分，共 20 分)1. 2. 3. 4. 5.6. 7. 8. 9. 10. 四、简答题(共 12 分，意思正确给分)1. 给定如图所示二叉树 T，请画出与其对应的中序线索二叉树。 （5 分）解答：要遵循中序遍历的轨迹来画出每个前驱和后继。中序遍历序列：55 40 25 60 28 08 33 542825 3340 60 08 54553. 假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：（7 分）（1） 画出描述折半查找过程的判定树；（3 分）2826 3340 60 08 54 55282540555560330854NILNIL（2） 若查找元素 54，需依次与哪些元素比较？（2 分）（3） 假定每个
