数据结构2007试卷及答案(共8页).doc
精选优质文档-倾情为你奉上 上 装 订 线 院（系）名： 班级： 姓名： 学号： 考生类别： 考试日期： 下 装 订 线 陕西师范大学20062007学年第二学期期末考试计算机科学学院2005级计算机科学专业数据结构题号一二三四总分分数答卷注意事项： 1、学生必须用蓝色（或黑色）钢笔、圆珠笔或签字笔直接在试题卷上答题。2、答卷前请将密封线内的项目填写清楚。 3、字迹要清楚、工整，不宜过大，以防试卷不够使用。 4、本卷共 4 大题，总分为100分。得分评卷人一、选择题（每题2分 ，共10分）1. 下面程序段的时间复杂度为(C)。 for(int i=0;i<m;i+) for(int j=0;j<n;j+) aij=i*j; A、O(m2) B、O(n2) C、O(m×n) D、O(m+n) 2. 一个栈的输入序列为1，2，3，4，下面哪一个序列不可能是这个栈的输出序列( C ). A、 1，3，2，4 B、2，3，4，1 C、 4，3，1，2 D、3，4，2，13. 假定一个顺序队列的队首和队尾指针分别为1和r，则判断队空的条件为（ D ）A、 f十1= =r B、 r1= =fC、 f= =0 D、 f= =r4. 广义表( (A , B, E, F , G)的表尾是( B )。A、(B, E , F, G) B、( ) C、（A，B， E，F，G） D、不存在5. 设有一个N×N的对称矩阵A，将其下三角部分以行为主序存入一个一维数组B中，A00存入B0中，那么第i行的对角元素Aii存入于B中的（ A ）处。A、（i+3）×i/2 B、(i+1)×i/2 C、(2N-i+1)×i/2 D、(2N-i-1)×i/2 得分评卷人二、填空题（每题2分，共10分）1.一棵深度为6的满二叉树中的结点数为 63 个，一棵深度为4的满四叉树中的结点数为 85 个。2. 设Q0n-1为循环队列，front,rear分别为队列的头，尾，则队列中的元素个数为 (rear-front+n) MOD n 。3. 已知一棵度为5的树中，2度、3度、4度、5度结点的个数依次为1，2，3，4个，则叶子个数为 11 。4. 栈又称为 后进先出 表，队列又称为 先进先出 表。5. 二维数组A的行下标从1到8，列下标从1到10，若每个元素占3个单元，则该数组按“以列序为主序”存放时，A58的起始位置是 180 。得分评卷人三、综合题（题1-10，每题4分，题11-14，每题6分，共10×4+4×6=64分）1.试写出对右边的树进行先根遍历、后根遍历和层次遍历时的访问次序。（4分）答案：先根遍历时顶点的访问次序：A B E F C D G H I J K后根遍历时顶点的访问次序：E F B C I J K H G D A层次遍历时顶点的访问次序：A B C D E F G H I J K2. 给定权值w=(1,3,5,7)，试构造一棵哈夫曼树。（4分）答案：3. 已知一组关键字为 3，1，2，5，4 ，按表中的元素顺序依次插入到一棵初始为空的二叉排序树中，画出该二叉排序树，并求在等概率的情况下查找成功的平均查找长度。（4分）答案：ASL =（1+2+3+2+3）/ 5= 2.24.试将右图中的二叉树进行中序线索化。（4分）答案：5.试分别写出右边有向图的深度优先搜索遍历及广度优先搜索遍历的次序。(假设从顶点A出发进行搜索) （4分）答案：深度优先搜索遍历的次序：A B C F E或 A E C F B广度优先搜索遍历的次序：A B E C F或 A E B C F6.已知一棵二叉树，其先序序列为a b c d e f g，中序序列为c b d a e g f，试画出此棵二叉树。（4分）答案：7. 构造右边网的一棵最小生成树。（4分）答案：8.请写出下面关键字序列的第一趟和第二趟快速排序(排序是从小到大)后的序列。（4分）49 38 65 97 76 13 27 23答案：23 38 27 13 49 76 97 6523 38 27 13 49 76 97 65 13 23 27 38 49 65 76 979.试将右边的森林转化为二叉树。（4分）答案：10.试画出右边有向图的邻接表及逆邻接表。（4分）答案：邻接表: 逆邻接表11.试求AOV-网的关键路径。（要求给出各事件和活动的最早发生时间及最晚发生时间）（6分）答案：12.已知如下12个数据元素的有序表，现用折半查找的方法查找关键字65的数据元素，试画出low指针、high指针和mid指针的指向位置。（假设low指示待查找区间的下界；high 指示待查找区间的上界；mid批示区间的中间位置）（6分）答案：13. 输入关键字序列16,3,7,11,9,26，给出构造一棵平衡二叉树的步骤。（6分）答案：14. 假设哈希表长度m=11，采用除留余数法哈希函数建立如下关键字集合的哈希表： 19, 01, 23, 14, 55, 68, 11, 82, 36 （要求采用线性探测再散列处理冲突），并求在等概率的情况下查找成功的平均查找长度。（6分）答案：ASL =（4×1+2×2+3×1+5×1+6×1）/9= 22/9得分评卷人四、算法实现（每题8分，共16分）1. 试用递归算法写出求二叉树T的深度算法。（8分）答案：int Depth (BiTree T ) / 返回二叉树的深度 if ( !T ) depthval = 0; else depthLeft = Depth( T->lchild ); depthRight= Depth( T->rchild ); depthval = 1 + (depthLeft > depthRight?depthLeft:depthRight); return depthval;2. 设C=a1,b1,a2,b2,an,bn为一线性表,采用带头结点的hc单链表存放，编写一个算法，将其拆分为两个线性表，使得：A=a1,a2,an，B=b1,b2,bn。（8分）答案：解:设拆分后的两个线性表都用带头结点的单链表存放。先建立两个头结点*ha和*hb，它们用于存放拆分后的线性表A和B,ra和rb分别指向这两个单链表的表尾，用p指针扫描单链表hc，将当前结点*p链到ha未尾，p沿next域下移一个结点，若不为空，则当前结点*p链到hb未尾，p沿next域下移一个结点，如此这样，直到p为空。最后将两个尾结点的next域置空。对应算法如下：void fun(LinkList *hc, LinkList *&ha, LinkList *&hb) LinkList *p=hc->next,*ra,*rb; ha=hc; /*ha的头结点利用hc的头结点*/ ra=ha; /*ra始终指向ha的末尾结点*/ hb=(LinkList *)malloc(sizeof(LinkList); /*创建hb头结点*/ rb=hb; /*rb始终指向hb的末尾结点*/while (p!=NULL) ra->next=p;ra=p; /*将*p链到ha单链表未尾*/ p=p->next; if (p!=NULL) rb->next=p; rb=p; /*将*p链到hb单链表未尾*/ p=p->next; ra->next=rb->next=NULL; /*两个尾结点的next域置空*/专心-专注-专业
