《【考研计算机专业课】武汉大学期末试题数据结构2007》由会员分享，可在线阅读，更多相关《【考研计算机专业课】武汉大学期末试题数据结构2007（6页珍藏版）》请在金锄头文库上搜索。
1、武汉大学计算机学院2006 年2007 学年第二学期“数据结构”考试试题（A）姓名 学号(序号)_ 班号 要求： 所有的题目的解答均写在答题纸上 （每张答题纸上要写清楚姓名、 班号和学号） ， 需写清楚题目的序号。每张答题纸都要写上姓名和序号。一、单项选择题（每小题 2 分，共 20 分）1. 在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 。 A. 数据的处理方法 B. 数据元素的类型 C. 数据元素之间的关系 D. 数据的存储方法 2. 下述函数中对应的渐进时间复杂度（n 为问题规模）最小是 。 A.T1(n)=nlog2n+5000n B.T2(n)=n2-8000n C.T3
2、(n)= nn2log-6000n D.T4(n)=1000nlog2n+7000log2n 3. 设线性表有 n 个元素，以下操作中， 在顺序表上实现比在链表上实现效率更 高。 A.输出第 i(1in)个元素值 B.交换第 1 个元素与第 2 个元素的值 C.顺序输出这 n 个元素的值 D.输出与给定值 x 相等的元素在线性表中的序号 4. 设 n 个元素进栈序列是 p1，p2，p3，pn，其输出序列是 1，2，3，n，若 p3=3， 则 p1的值 。 A.可能是 2B.一定是 2 C.不可能是 1D.一定是 1 5. 以下各种存储结构中，最适合用作链队的链表是 。 A.带队首指针和队尾指针
3、的循环单链表B.带队首指针和队尾指针的非循环单链表 C.只带队首指针的非循环单链表D.只带队首指针的循环单链表 6. 对于链串 s（长度为 n，每个结点存储一个字符） ，查找元素值为 ch 的算法的时间复 杂度为 。 A.O(1)B.O(n) C.O(n2)D.以上都不对 7. 设二维数组 A610，每个数组元素占用 4 个存储单元，若按行优先顺序存放的数 组元素 a35的存储地址为 1000，则 a00的存储地址是 。 A.872B.860 C.868D.864 8. 一个具有 1025 个结点的二叉树的高 h 为 。 A.11B.10 C.111025D.1210242数据结构期末考试试题
4、（共 3 页）9. 一棵二叉树的后序遍历序列为 DABEC， 中序遍历序列为 DEBAC， 则先序遍历序列 为 。 A.ACBEDB.DECAB C.DEABCD.CEDBA 10. 对图 1 所示的无向图， 从顶点 1 开始进行深度优先遍历； 可得到顶点访问序列 。 A.1 2 4 3 5 7 6B.1 2 4 3 5 6 7 C.1 2 4 5 6 3 7D.1 2 3 4 5 7 61 2 3 4 5 6 7 图 1 一个无向图二、填空题（每题 2 分，共 10 分）1. 顺序队和链队的区别仅在于 的不同。 2. 在有 n 个顶点的有向图中，每个顶点的度最大可达 。 3. 对有 18 个
5、元素的有序表 R1.18进行二分查找，则查找 R3的比较序列的下标 为 。 4. 对含有 n 元素的关键字序列进行直接选择排序时，所需进行的关键字之间的比较次 数为 。 5. 已知关键字序列为2,7,4,3,1,9,10,5,6,8，采用堆排序法对该序列作升序排序时，构 造的初始堆（大根堆）是 。 （不用画出堆，只需写出初始堆的序列）三、问答题（共 40 分）1. 一棵完全二叉树上有 1001 个结点，其中叶结点的个数是多少？（需写出推导过程， 8 分） 2. 给出如下各种情况下求任意一个顶点的度的过程（只需文字描述） ： （8 分） （1）含 n 个顶点的无向图采用邻接矩阵存储； （2）含
6、n 个顶点的无向图采用邻接表存储； （3）含 n 个顶点的有向图采用邻接矩阵存储； （4）含 n 个顶点的有向图采用邻接表存储。 3. 将整数序列4,5,7,2,1,3,6中的数依次插入到一棵空的平衡二叉树中，试构造相应的 平衡二叉树。 （要求画出每个元素插入过程，若需调整，还需给出调整后的结果，并指出是 什么类型的调整，12 分） 4. 当实现插入直接排序过程中，假设 R0.i-1为有序区，Ri.n-1为无序区，现要将 Ri插入到有序区中，可以用二分查找来确定 Ri在有序区中的可能插入位置，这样做能否 改善直接插入排序算法的时间复杂度?为什么?（8 分） 5. 简述外排序的两个阶段。 （4
7、分）数据结构期末考试试题（共 3 页）3四、算法设计题（共 30 分）1. 设计一个算法 delminnode(LinkList *ElemType mindata=p-data;while (p!=NULL p=p-next;p=pre-next;while (p!=NULL) if (p-data=mindata)pre-next=p-next;free(p);pre=pre-next;p=pre-next; 评分标准：根据算法的正确性评分，不考虑算法的时间复杂度。 2解：递归算法如下：void copy(BTNode *b,BTNode *if (b=NULL) t=NULL;elset=(BTNode *)malloc(sizeof(BTNode);copy(b-lchild,l);copy(b-rchild,r);t-lchild=l;t-rchild=r;评分标准：根据算法的正确性评分，不考虑算法的时间复杂度。
