2007级算法与数据结构试题A

第1页共11页山西财经大学2008—2009学年第2学期期末算法与数据结构课程试卷（A卷）题号一二三四五总分分数评卷人复核人1、本卷考试形式为闭卷，考试时间为两小时。2、考生不得将装订成册的试卷拆散，不得将试卷或答题卡带出考场。3、考生只允许在密封线以外答题，答在密封线以内的将不予评分。4、考生答题时一律使用蓝色、黑色钢笔或圆珠笔（制图、制表等除外）。5、考生禁止携带手机、耳麦等通讯器材。否则，视为作弊。一、单项选择题（共10小题，每题1分，共计10分）二、判断题（共10小题，每题1分，共计10分）三、简答题（共4小题，每题5分，共计20分）四、应用题（共8小题，1-6小题必做，7、8任选一，1-2每小题5分，3-8每小题6分，共计40分）五、算法设计题（1、2小题任选一，3、4小题任选一，每题10分，共计20分）第2页共11页一、单项选择题（共10小题，每题1分，共计10分）答题要求：（请将正确的选项填在题后的括号中）1．若某线性表最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则下列的存储方式中最节省时间的是()。A．单链表B．仅有头指针的单循环链表C．双向链表D．仅有尾指针的单循环链表2.下面给出的算法段是要把一个p所指新结点，插入到非空双向链表中，作为该双链中q所指结点的前驱结点，能正确完成要求的算法段是（）。A．p-llink=q-llink;B．q-llink=p;p-rlink=q;p-rlink=q;q-llink-rlink=p;q-llink-rlink=p;q-llink=p;p-llink=q-llink;C．p-rlink=q;D．p-rlink=q;p-llink=q-llink;p-llink=q-llink;q-llink=p;q-rlink=p;q-llink-rlink=p;q-llink-rlink=p;3．下列选项中，（）是非线性数据结构。A．栈B.队列C.完全二叉树D.堆4．判定一个循环队列Q(最多元素为m0)为满队列的条件是()。A．Q.front!=Q.rearB．Q.front==Q.rearC．Q.front!=(Q.rear+1)%m0D．Q.front==(Q.rear+1)%m05．串的长度是()。A．串中不同字母的个数B．串中不同字符的个数C．串中所含字符的个数，且大于0D．串中所含字符的个数6．数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[7][5]本题得分第3页共11页的起始地址为（）。A．SA+192B．SA+195C．SA+222D．SA+2257．设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（）A．m-nB．m-n-1C．n+1D．条件不足，无法确定8．有向网G用邻接矩阵A存储，则顶点i的入度等于A中()。A．第i行非∞元素之和B．第i列非∞的元素之和C．第i行非∞且非0的元素个数D．第i列非∞且非0的元素个数9．对线性表进行二分查找时，要求线性表必须（）。A．以顺序方式存储B．以链接方式存储C．以顺序方式存储，且结点按关键字有序排列D．以链接方式存储，且结点按关键字有序排列10．下列排序算法中，在某趟结束后不一定能选出一个元素放到其最终的位置上的是()。A．堆B．归并C．起泡D．选择二、判断题（共10小题，每题1分，共计10分）答题要求：（正确的请在题后的括号内打“√”，错误的请打“x”）1．顺序存储方式的优点是存储密度大，且插入、删除运算效率高。()2．在链表中，逻辑上相邻的两个元素在物理上不一定相邻。()3．栈和队列的存储方式，可以采用顺序方式，也可以采用链式方式。()4．数组可以看成是线性结构的一种推广，因此可以对它进行插入、删除。（）5．一棵树中的叶子数一定等于与其对应的二叉树的叶子数。()本题得分第4页共11页6．删除二叉排序树中的一个结点，再重新插入进去，一定能得到原来的二叉排序树。()7．采用散列法存储，负载因子越大，发生碰撞的可能性也越大。()8．若一棵树中某结点的度为1，则该结点仅有一棵子树。()9．如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串。()10．对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可访问到该图的每个顶点。()三、简答题（共4小题，每题5分，共计20分）答题要求：（第2、3题请写出中间过程，只写结果不得分）1.请简述栈和队列的相同和不同之处。2.已知完全二叉树的第8层有10个结点，则整个二叉树的结点数最多为？3.什么是二叉排序树？如何在二叉排序树上实施查找操作？本题得分第5页共11页4.直接插入排序和快速排序两种算法的稳定性如何?请写出原因。三、应用题（1-6小题必做，7、8任选一，1-2每小题5分，3-8每小题6分，共计40分）四、答题要求：（请尽量写出中间过程）1.设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分按行序存放在一维数组B[1，n(n-1)/2]中，对上三角部分的任一元素ai,j(ij)，求它在一组数组B中的下标位置k的值？2.如右图所示的一棵二叉树，(1)请画出它的顺序存储表示(2)写出它的中序遍历序列(3)画出它的后序线索二叉树。本题得分bacfdehg第6页共11页3.某二叉树的前序遍历结点访问顺序是abdcefgh，中序遍历的结点访问顺序是cbdagfeh，请画出该二叉树。4.以数据集｛3,5,9,14,16,25,33｝为结点权值(1)请构造的哈夫曼树。(2)并求出它的带权路径长度。5.哈希表长为11，请给出对序列{7，18，40，35，9，33，28，37，90}进行散列，按照哈希函数H(key)＝keyMOD11，及线性线性探测再散列处理冲突，请给出处理的过程及结果。第7页共11页6．已知序列{30，8，25，15，78，97，65，43，72}，采用堆排序法对该序列作升序排序。(1)建立的初始堆应是大顶堆还是小顶堆？(2)建初始堆时应从哪一个位置开始筛选？(3)请画出建成的初始堆。7．求出下面AOE网中的关键路径。要求标明每个顶点的最早和最迟发生时间，并画出关键路径。104997a1bcdegf651326第8页共11页8．求出下图的一棵最小生成树，要求给出过程和所依据的是哪一种算法。8106596142538763437512第9页共11页五、算法设计题（1、2小题任选一，3、4小题任选一，每题10分，共计20分）答题要求：（在写出算法之前先简要写出算法思想；在算法中尽可能写一些注释信息。不按要求只写算法不得分。）单链表存储结构如下：typedefstructLnode{Elemtypedata;StructLnode*next;}Lnode,*Linklist;1．试编写在带头结点的单链表中删除最小值结点的算法。voiddelete（Linklist&L）2．请编写对不带头结点的单链表进行就地逆置的算法，要求算法用L返回逆置后的链表的头指针。二叉链表存储表示定义如下：typedefstructBiTNode{TelemTypedata;StructBiTNode*lchild,*rchild;本题得分第10页共11页}BiTNode,*BiTree;3．假设二叉树采用二叉链表作为存储结构，请编写算法求二叉树中度为2的结点数。4．设一棵二叉树以二叉链表为存贮结构，设计一个算法将二叉树中所有结点的左，右子树相互交换。第11页共11页薃肀莂蒃袂肀肂虿袈聿芄薂螄肈莇螇蚀肇葿薀罿肆腿莃袅肅芁薈螁膄莃莁蚇膄肃薇薃膃芅荿羁膂莈蚅袇膁蒀蒈螃膀膀蚃虿腿节蒆羈芈莄蚁袄芈蒆蒄螀芇膆蚀蚆袃莈蒃蚂袂蒁螈羀袁膀薁袆袁芃螆螂袀莅蕿蚈衿蒇莂羇羈膇薇袃羇艿莀蝿羆蒂薆螅羅膁蒈蚁羅芄蚄罿羄莆蒇袅羃蒈蚂螁羂膈蒅蚇肁芀蚁薃肀莂蒃袂肀肂虿袈聿芄薂螄肈莇螇蚀肇葿薀罿肆腿莃袅肅芁薈螁膄莃莁蚇膄肃薇薃膃芅荿羁膂莈蚅袇膁蒀蒈螃膀膀蚃虿腿节蒆羈芈莄蚁袄芈蒆蒄螀芇膆蚀蚆袃莈蒃蚂袂蒁螈羀袁膀薁袆袁芃螆螂袀莅蕿蚈衿蒇莂羇羈膇薇袃羇艿莀蝿羆蒂薆螅羅膁蒈蚁羅芄蚄罿羄莆蒇袅羃蒈蚂螁羂膈蒅蚇肁芀蚁薃肀莂蒃袂肀肂虿袈聿芄薂螄肈莇螇蚀肇葿薀罿肆腿莃袅肅芁薈螁膄莃莁蚇膄肃薇薃膃芅荿螀羀膆蒃蚆肀芈芆薂聿羈蒂蒈肈肀芅袆肇芃薀螂肆莅莃蚈肅肅薈薄蚂膇莁蒀蚁艿薇蝿螀罿荿蚅蝿肁薅薁螈膄莈薇螈莆膀袆螇肆蒆螁螆膈艿蚇螅芀蒄薃螄羀芇葿袃肂蒃螈袂膄芅蚄袂芇蒁蚀袁肆芄薆袀腿蕿蒂衿芁莂螁袈羁薇蚇袇肃莀薃羆膅薆葿羆芈荿螇羅羇膁螃羄膀莇虿羃节芀薅羂羂蒅蒁羁肄芈螀羀膆蒃蚆肀芈芆薂聿羈蒂蒈肈肀芅袆肇芃薀螂肆莅莃蚈肅肅薈薄蚂膇莁蒀蚁艿薇蝿螀罿荿蚅蝿肁薅薁螈膄莈薇螈莆膀袆螇肆蒆螁螆膈艿蚇螅芀蒄薃螄羀芇葿袃肂蒃螈袂膄芅蚄袂芇蒁蚀袁肆芄薆袀腿蕿蒂衿芁莂螁袈羁薇蚇袇肃莀薃羆膅薆葿羆芈荿螇羅羇膁螃羄膀莇虿羃节芀薅羂羂蒅蒁羁肄芈螀羀膆蒃蚆肀芈芆薂聿羈蒂蒈肈肀芅袆肇芃薀螂肆莅莃蚈肅肅薈薄蚂膇莁蒀蚁艿薇蝿螀罿荿蚅蝿肁薅薁螈膄莈薇螈莆膀袆螇肆蒆螁螆膈艿蚇螅芀蒄薃螄羀芇葿袃肂蒃螈袂膄芅蚄袂芇蒁蚀袁肆芄薆袀腿蕿蒂衿芁莂螁袈羁薇蚇袇肃莀薃羆膅薆葿羆芈荿螇羅羇膁螃羄膀莇虿羃节芀薅羂羂蒅蒁羁肄芈螀羀膆蒃蚆肀芈芆薂聿羈蒂蒈肈肀芅袆肇芃薀螂肆莅莃蚈肅肅薈薄蚂膇莁蒀蚁艿薇蝿螀罿荿蚅蝿肁薅薁螈膄莈薇螈莆膀袆螇肆蒆螁螆膈艿蚇螅芀蒄薃螄羀芇葿袃肂蒃螈袂膄芅蚄袂芇蒁蚀袁肆芄薆袀腿蕿蒂衿芁莂螁袈羁薇蚇袇肃莀薃羆膅薆葿羆芈荿螇羅羇膁螃羄膀莇虿羃节芀薅羂羂蒅蒁羁肄芈螀羀膆蒃蚆肀芈芆薂聿羈蒂蒈肈肀芅袆肇芃薀螂肆莅莃蚈肅肅薈薄蚂膇莁蒀蚁艿薇蝿螀罿荿蚅蝿肁薅薁螈膄莈薇螈莆膀袆螇肆蒆螁螆膈艿蚇螅芀蒄薃螄羀芇葿袃肂蒃螈袂膄芅蚄袂芇蒁蚀袁肆芄薆袀腿蕿蒂衿芁莂螁袈羁薇蚇袇肃莀薃羆膅薆葿羆芈荿螇羅羇膁螃羄膀莇虿羃节芀薅羂羂蒅蒁羁肄芈螀羀膆蒃蚆肀芈芆薂聿羈蒂蒈肈肀芅袆肇芃薀螂肆莅莃蚈肅肅薈薄蚂膇莁蒀蚁艿薇蝿螀罿荿蚅蝿肁薅薁螈膄莈薇螈莆膀袆螇肆蒆螁螆膈艿蚇螅芀蒄薃螄羀芇葿袃肂蒃螈袂膄芅蚄袂芇蒁蚀袁肆芄薆袀腿蕿蒂衿芁莂螁袈羁薇蚇袇肃莀薃羆膅薆葿羆芈荿螇羅羇膁螃羄膀莇虿羃节芀薅羂羂蒅蒁羁肄芈螀羀膆蒃蚆肀芈芆薂聿羈蒂蒈肈肀芅袆肇芃薀螂肆莅莃蚈肅肅薈薄蚂膇莁蒀蚁艿薇蝿螀罿荿蚅蝿肁薅薁螈膄莈薇螈莆膀袆螇肆蒆螁螆膈艿蚇螅芀蒄薃螄羀芇葿袃肂蒃螈袂膄芅蚄袂芇蒁蚀袁肆芄薆袀腿蕿蒂衿芁莂螁袈羁薇蚇袇肃莀薃羆膅薆葿羆芈荿螇羅羇膁螃羄膀莇虿羃节芀薅羂羂蒅蒁羁肄芈螀羀膆蒃蚆肀芈芆薂聿羈蒂蒈肈肀芅袆肇芃薀螂肆莅莃蚈肅肅薈薄蚂膇莁蒀蚁艿薇蝿螀罿荿蚅蝿肁薅薁螈膄莈薇螈莆膀袆螇肆蒆螁螆膈艿蚇螅芀蒄薃螄羀芇葿袃肂蒃螈袂膄芅蚄袂芇蒁蚀袁肆芄薆袀腿蕿蒂衿芁莂螁袈羁薇蚇袇肃莀薃羆膅薆葿羆芈荿螇羅羇膁螃羄膀莇虿羃节芀薅羂羂蒅蒁羁肄芈螀羀膆蒃蚆肀芈芆薂聿羈蒂蒈肈肀芅袆肇芃薀螂肆莅莃蚈肅肅薈薄蚂膇莁蒀蚁艿薇蝿螀罿荿蚅蝿肁薅薁螈膄莈薇螈莆膀袆螇肆蒆螁螆膈艿蚇螅芀蒄薃螄羀芇葿袃肂蒃螈袂膄芅蚄袂芇蒁蚀袁肆芄薆袀腿蕿蒂衿芁莂螁袈羁薇蚇袇肃莀薃羆膅薆葿羆芈荿螇羅羇膁螃羄膀莇虿羃节芀薅羂羂蒅蒁羁肄芈螀羀膆蒃蚆肀芈芆薂聿羈蒂蒈肈肀芅袆肇芃薀螂肆莅莃蚈肅肅薈薄蚂膇莁蒀蚁艿薇蝿螀罿荿蚅蝿肁薅薁螈膄莈薇螈莆膀袆螇肆蒆螁螆膈艿蚇螅芀蒄薃螄羀芇葿袃肂蒃螈袂膄芅蚄袂芇蒁蚀袁肆芄薆袀腿蕿蒂衿芁莂螁袈羁薇蚇袇肃莀薃羆膅薆葿羆芈荿螇羅羇膁螃羄膀莇虿羃节芀薅羂羂蒅蒁羁肄芈螀羀膆蒃蚆肀芈芆薂聿羈蒂蒈肈肀芅袆肇芃薀螂肆莅莃蚈肅肅薈薄蚂膇莁蒀蚁艿薇蝿螀罿荿蚅蝿肁薅薁螈膄莈薇螈莆膀袆螇肆蒆螁螆膈艿蚇螅芀蒄薃螄羀芇葿袃肂蒃螈袂膄芅蚄袂芇蒁蚀袁肆芄薆袀腿蕿蒂衿芁莂螁袈羁薇蚇袇肃莀薃羆膅薆葿羆芈荿螇羅羇膁螃羄膀莇虿羃节芀薅羂羂蒅蒁羁肄芈螀羀膆蒃蚆肀芈芆薂聿羈蒂蒈肈肀芅袆肇芃薀螂肆莅莃蚈肅肅薈薄蚂膇莁蒀蚁艿薇蝿螀罿荿蚅蝿肁薅薁螈膄莈薇螈莆膀袆螇肆蒆螁螆膈艿蚇螅芀蒄薃螄羀芇葿袃肂蒃螈袂膄芅蚄袂芇蒁蚀袁肆芄薆袀腿蕿蒂衿芁莂螁袈羁薇蚇袇肃莀薃羆膅薆葿羆芈荿螇羅羇膁螃羄膀莇虿羃节芀薅羂羂蒅蒁羁肄芈