西安科技大学研究生2012数据结构试卷

共9页第1页西安科技大学2012年硕士研究生入学考试试题─────────────────────────────────科目编号：824科目名称：数据结构与算法设计考生须知：1、答案必须写在答题纸上，写在试题或草稿纸上不给分。2、答题须用蓝、黑色钢笔或圆珠笔，用铅笔、红色笔者不给分。3、答题必须写清题号，字迹要清楚，卷面要保持整洁。4、试题要随答题纸一起交回。一、选择题（每题2分，共20分）1.一个栈的入栈序列是abcde，则栈的不可能的输出序列是()。（A）edcba（B）deacb（C）cbade（D）abcde2.判断一个循环队列Q(元素最多为n)为满的条件是()。（A）Q-rear==Q-front（B）Q-rear!=Q-front（C）Q-front==(Q-rear+1)%n（D）Q-front!=(Q-front+1)%n3.下列不属于栈的应用的是（）（A）迷宫问题(B)表达式求值(C)作业调度(D)程序递归4.对于一个非空的广义表来说，()。（A）可能不含任何原子元素（B）至少含一个原子元素（C）其长度不小于其中任何一个子表的长度（D）至少含一个非空的子表元素5.串的逻辑结构与()的逻辑结构不同。（A）线性表（B）栈（C）队列（D）树6.高度为h的二叉树上只有度为0和2的结点，则此类二叉树中所包含的结点数至少为()。（A）2h（B）2h-1（C）2h+1（D）h+17.在散列函数H(n)=nMODp中，p应取()。（A）奇数（B）偶数（C）质数（D）正数8.对任何一棵二叉树T，设n0，n1，n2分别是度数为0，1，2的结点数，则n0=()。（A）n1+1（B）n2+1（C）n1+n2（D）2n1+19.采用分块查找时，若线性表中共有256个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分()个结点最佳。（A）16（B）64（C）128（D）25610.下列排序方法中，()是从未排序序列中依次挑选元素，并将其放入已排序序列（初始为空）的一端。（A）希尔排序（B）归并排序（C）选择排序（D）插入排序共9页第2页二、填空题（每空3分，共30分）1．在长度为n的顺序表中插入一个元素，平均需要移动元素，删除一个元素平均需要移动个元素。2．一个有n个顶点的无向图，其生成树有条边。3．在顺序表中，逻辑上相邻的元素，其物理位置相邻。在单链表中，逻辑上相邻的元素，物理位置相邻。4．按中序遍历二叉树的结果为ABC，有种形态的二叉树可以得到这个结果。5．深度为k的二叉树至少有个结点，至多有个结点。6．设计递归函数时，如不用递归过程（即非递归过程）就应借助于的数据结构是。7．以数据集{2,5,7,9,13}为权值构造一棵哈夫曼树，其带权路径长度为。三、简答题（任选4题，每题10分，共40分）1.你认为应该如何评估一个数据结构或算法的有效性。2．对10阶对称矩阵A[0..9][0..9]，采用压缩存储方式存储其下三角部分，已知每个元素占用2个存储单元，其第一个元素A(0,0)的存储位置为1000，给出a(4,5)的存储位置。3．为何引进循环队列，其优点是什么？如何判别它的空和满？4．内部排序指的是什么？什么是排序方法的稳定性？5.试述顺序查找法、折半查找法和分块查找法对被查找的表中元素的要求，对长度为n的表来说，三种查找法在查找成功时的查找长度各是多少？6.何谓队列的上溢现象和假溢出现象？解决它们有哪些方法？四、综合题（任选3题，每题10分，共30分)1.已知二叉树T的前序（先根）遍历序列和中序（中根）遍历序列分别为EDCHABFGI和DHCEFBGIA，试画出二叉树T，并写出其后序遍历序列。2.已知一组关键字｛19，27，36，30，16，46，71，42，24，49，64｝，哈希表长为13，哈希函数为：H(key)=key%13，解决冲突用拉链法。构造哈希表，求等概率下查找成功的平均查找长度。3.关键码集合如下：{10，2，13，15，12，14}，用堆排序方法从小到大排序，画出堆排序的初态、建堆和重建堆的过程。4.输入一组关键字｛60，33，92，71，8，45，39，50，3，15，82｝，画出由此而生成的二叉排序树。如果对每一个关键字的查找概率相等，求其平均查找长度ASL。试问对此二叉排序树进行何种操作可得到有序序列？画出删除二叉排序树中“33”之后的二叉排序树。五、算法与程序设计题(任选3题，每题10分，共30分)1.设计算法将一个带头结点的单链表A分解成两个具有相同结构的链表B,C。其中B表的结点是A表中值小于零的结点，而C表的结点为A表中值大于零的结点(链表A的元素类型为整型，要求B，C表利用A表的结点)。2.设计一个算法，求出指定结点在给定的二叉树中所在的层次。3.已知表（K1，K2，…，Kn），其中Ki为正整数，设计一个算法，能在O(n)的时间内将线性表划分成两部分，其左半部分的每个关键字均小于K1，右半部分的关键字均大于等于共9页第3页K1。4.仔细阅读下面的函数，并回答有关问题。voidUnknownname(inta[500]；intn){inti，j，x；{b=true；i=1；while(in)&&b{b=false;for(j=1；___①______；j++)if___②_____{x=a[j];a[j]=a[j+1];a[j+1]=x;____③_______；}i=i+1}}}(1)在______中填上正确的语句，使该函数能完成预期的功能；(2)该函数使用的是什么排序方法？(3)当数组a的元素初始时已按值递增排序，该函数执行中会进行多少次比较？多少次交换？(4)当数组a的元素初始时已按值递减排序，该函数执行中会进行多少次比较？多少次交换？共9页第4页西安科技大学2012年硕士研究生入学考试参考答案─────────────────────────────────科目编号：824科目名称：数据结构与算法设计考生须知：5、答案必须写在答题纸上，写在试题或草稿纸上不给分。6、答题须用蓝、黑色钢笔或圆珠笔，用铅笔、红色笔者不给分。7、答题必须写清题号，字迹要清楚，卷面要保持整洁。8、试题要随答题纸一起交回。一、选择题（每题2分，共20分）1.B2.C3.C4.A5.D6.B7.C8.B9.A10.C二、填空题（每空3分，共30分）（1）n/2，（n-1）/2（2）n-1（3）也/肯定,不一定(4)5（5）k，2k-1（6）栈（7）79三、简答题（任选3题，每题10分，共40分）1.你认为应该如何评估一个数据结构或算法的有效性。答：前提之一是算法的正确性，其二还必须考虑执行算法所耗费的时间和执行算法所耗费的空间（主要是指辅助空间），以及算法的易读、易编码以及易于调试等。2．.答：假设对称矩阵以行序存放在压缩数组中。a(4,5)元素前面有4行，元素个数为1+2+3+4=10个，在第5行中，前面有5个元素，则压缩存储时，其序号为19+5=15LOC(a(4,5))=LOC(a(0,0))+15×2=10303．答：循环队列的优点是：它可以克服顺序队列的“假上溢”现象，能够使存储队列的空间得到充分的利用。判别循环队列的“空”或“满”不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是少用一个元素的空间，每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满；二是设置一计数器记录队列中元素总数，不仅可判别空和满，还可以得到队列中元素的个数。三是另设一布尔变量来区别队列的空和满。4.答：假定给定含有n个记录的文件(r1，r2，…，rn)，其相应的关键字为(k1，k2，…，kn)则排序就是确定文件的一个序列r1′，r2′，…，rn′，使得k1′≤k2′≤…≤kn′，从而使得文件中n个记录按其对应关键字有序排列。如果整个排序过程在内存中进行，则排序叫内部排序。假设在待排序的文件中存在两个或两个以上的记录具有相同的关键字，若采用某种排序方法后，使得这些具有相同关键字的记录在排序前后相对次序依然保持不变，则认为该排序方法是稳定的，否则就认为排序方法是不稳定的。共9页第5页5.答：顺序查找法：表中元素可以任意存放。折半查找法：表中元素必须以关键字的大小递增或递减的次序存放且以顺序存储。分块查找法：表中元素每块内的元素可任意存放，但块与块之间必须以关键字的大小递增（或递减）存放，即前一块内所有元素的关键字都不能大（或小）于后一块内任何元素的关键字。三种方法的平均查找长度分别如下：顺序查找法：查找成功的平均查找长度为(n+1)/2。折半查找法：查找成功的平均查找长度为log2(n+1)-1。分块查找法：若用顺序查找确定所在的块，平均查找长度为(n/s+s)/2+1；若用折半查找确定所在的块，平均查找长度为log2(n/s+1)+s/2。其中s为每块含有的元素个数。6.何谓队列的上溢现象和假溢出现象？解决它们有哪些方法？答：在队列的顺序存储结构中，设头指针为front，队尾指针为rear，队列的容量（存储空间的大小）为m。当有元素加入到队列时，若rear=m（初始时rear=0）,则发生队列的上溢出现象，该元素不能加入到队列中，。这里需要特别注意的是队列的假溢出现象，队列中还有空余的空间，但元素不能进队列。造成这种现象的原因是由于队列的操作方式所致。解决队列的上溢的方法有以下几种：1）建立一个足够大的存储空间，但这样做往往造成空间使用效率低。2）当出现假溢出时，可采用以下办法：a采用平移元素的方法，每当队列中加入一个元素时，队列中已有的元素向队头移动一个位置（当然要有空余的空间可移）。b每当删除一个队头元素时，则依次移动队中的元素，始终使front指针指向队列中的第一个位置。c采用循环队列方式。把队列看成一个首尾相邻的循环队列，虽然物理上队尾在队首之前，但逻辑上队首仍然在前，作插入和删除运算时仍按”先进先出”的原则。四、综合题（任选3题，每题10分，共30分)1.已知二叉树T的前序（先根）遍历序列和中序（中根）遍历序列分别为EDCHABFGI和DHCEFBGIA，试画出二叉树T。解答：该二叉树如图所示EIGFHBCAD共9页第6页2.解答：（哈希表为（６分）:ASLSUCC=111(1×9+2×2)=1113≈1.18（４分）3.关键码集合如下：{10，2，13，15，12，14}，用堆排序方法从小到大排序，画出堆排序的初态、建堆和重建堆的过程。解答：其堆排序过程如图所示：10141215132(a)初态21412151310(b)建初始堆(c)输出21412151310(d)调整为堆1014151312(f)调整为堆12151314(g)输出12151314(h)调整为堆131514(i)输出131514(j)调整为堆1415(k)输出1415(l)输出15(e)输出1014151312共9页第7页4.答：（1）二叉排序树为：（2）ASL=1/10*（1+2*2+4*3+1*4+2*5）=3.1（3）中序遍历可得有序序列（4）删除33之后的二叉树为：五、算法与程序设计题(任选3题，每题10分，共30分)1.解答：voidsplit(slink*A,slink*&B,slink*&C){slink*pa=A-next,*pb,*pc;B=(structslink*)malloc(sizeof(structslink));C=(structslink*)malloc(sizeof(structslink));pb=B;pc=C;while(pa!=NULL){if(pa-data0){pb-next=pa;pb=pa;}else{pc-next=pa;pc=pa;}pa=pa-next;}pb-next=pc-next=NULL;}33A92815453713950608239A9281545371508260共9页第8页2.解答：intlevel(bitree*t,*p){intcount;count=0;if(t==Null)retu