南京市南京大学《数据结构》试卷(含答案).pdf

考试科目名称 数据结构 （A1 卷） 得分 1、填空题。（每小题2 分，本题满分20 分） (1) C++语言中，数组是按行优先顺序存储的，假设定义了一个二维数组A[20][30] ，每个元 素占两个字节，其起始地址为2140 ，则二维数组A 的最后一个数据元素的地址为 2140+2*(30*20-1) = 3338(3338,3339) 。 (2) 若A ，B 是两个单链表，链表长度分别为n 和m，其元素值递增有序，将A 和B 归并成 一个按元素值递增有序的单链表，并要求辅助空间为O(1)，则实现该功能的算法的时间 复杂度为 O(m+n) 。 (3) 快速排序的平均时间复杂度是____n*lg n___________ 。 (4) 假设有一个包含 9 个元素的最小堆，存放在数组 A 中，则一定比 A[3]大的元素有_ _2 (A[7],A[8]) ____个；一定比A[3]小的元素有__2 (A[0],A[1])____个。（元素从第0 个位 置开始存放） (5) 广义表(((A)),(B,C), D, ((A), ((E,F)))) 的长度是 4 ，深度是 4 。 (6) 有10 个元素的有序表，采用折半查找，需要比较4 次才可找到的元素个数为____3_____ 。 (7 ）当两个栈共享一存储区时，栈利用一维数组A[n]表示，两栈顶指针为top[0]与top[ 1]， 则栈满时的判断条件为___top[0]+1=top[1]_ 或者 top[0] = top[1]+ 1 ___ 。 (8) 假设计算斐波那契数的函数Fib(long n)定义如下： long Fib(long n){ if(n<=1) return n; else return Fib(n- 1)+Fib(n-2) } 计算Fib(5) 时的递归调用树（即指明函数调用关系的树）的高度是___4 _____ 。假设叶 子结点所在的高度为0 。 (9) 完全二叉树按照层次次序，自顶向下，同层从左到右顺序从0 开始编号时，编号为i 的 结点的左子结点的编号为___2*i+1______ 。 (10) 假设用子女—兄弟链表方式表示森林，对应的二叉树的根结点是p ，那么森林的第三棵 树的根结点在二叉树中对应的结点是： ___p->rightchild->rightchild____________ 。假 设二叉树的结点结构为： leftchild data rightchild 得分 2、选择题。（每小题2 分，本题满分20 分） (1) 如果能够在只知道指针p 指向链表中任一结点，不知道头指针的情况下，将结点*p 从链 表中删除，则这个链表结构应该是： ( B,C ) （多选题） A. 单链表 B. 循环链表 C. 双向链表 D. 带头结点的单链表 (2) 以下哪种矩阵压缩存储后会失去随机存取的功能?( A ) A. 稀疏矩阵 B. 对称矩阵 C. 对角矩阵 D. 上三角矩阵 (3) 下面哪一方法可以判断出一个有向图是否有环（回路）：( B ) (选A ，B 也对) A. 广度优先遍历 B. 拓扑排序 C. 求最短路径 D.求关键路径 (4) n 个结点的线索二叉树(没有头结点)上含有的线索数为（ B ） 第 1 页 共 12 页 A. 2n B. n －l C. n＋l D. n (5) 循环队列存储在数组A[0..m]中，则入队时队尾指针rear 的操作为（ D ） A. rear=rear+1 B. rear=(rear+1) mod (m-1) C. rear=(rear+1) mod m D.