数据结构试题A200711答案

第１页共5页陕西科技大学试题纸（A参考答案及评分标准）课程数据结构班级信息、数学05学号姓名题号一二三四五六七八九十总分得分阅卷人一、选择题（每小题1分，共15分）请在每小题的四个备选答案中，选出一个正确的答案，并将其号码填在括号内。1.设一个栈的输入序列为1，2，3，4，则借助一个栈所得的输出序列不可能是（D）。A．1，2，3，4B．4，3，2，1C．1，3，4，2D．4，1，2，32.设有80行的二维数组A[80][60]，其元素长度为4字节，按行优先顺序存储，基地址为300，则元素A[18][25]的存储地址为（D）。A．3800B．4376C．3900D．47203.将一棵有100个节点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根节点的编号为0，则编号为49的结点的左孩子编号为（B）。A．98B．99C．50D．494.在长度为n的顺序存储的线性表中，删除第i个元素（1≤i≤n）时，需要从前向后依次前移（A）个元素。A．n-iB．n-i+1C．n-i-1D．i5.栈的插入和删除操作在（A）进行。A．栈顶B．栈底C．任意位置D．指定位置6.链表适用于（A）查找。A．顺序B．二分法C．二分法、顺序D．随机7.深度为6(根结点的层次为1)的二叉树至多有（D）个结点。A．64B．32C．31D．638.用邻接表表示图进行广度优先遍历时，通常是采用（B）来实现算法的。A．栈B．队列C．树D．图9.设有两个串ｐ和ｑ，求ｑ在ｐ中首次出现的位置的运算称作（B）。A．连接B．模式匹配C．求子串D．求串长10.若某线性表中最常用的操作是取第i个数据元素，则采用（D）存储方式最节省时间。A．单链表B．双链表C．单向循环D．顺序表11.三个结点可构成（D）个不同形态的二叉树。A．2B．3C．4D．512.下列关键字序列中，（D）是堆。A．16,72,31,23,94,53B．94,23,31,72,16,53C．16,53,23,94,31,72D．16,23,53,31,94,72第２页共5页13.把一棵树转换为二叉树后，这棵二叉树的形态是（A）。A．唯一的B．有多种，但根结点都没有左孩子C．有多种D．有多种，但根结点都没有右孩子14.串是任意有限个（C）。A．符号构成的序列B．符号构成的集合C．字符构成的序列D．字符构成的集合15.在一个链队列中，假定front和rear分别为队首和队尾指针，则进行插入s结点的操作时应执行（C）操作。A．front—〉next=s;front=s;B．s—〉next=rear;rear=s;C．rear—〉next=s;rear=s;D．s—〉next=front;front=s;二、填空题（每空1分，共15分）1.n为整型变量且为正整数，下列算法中加下划线语句的执行次数为n-2，算法的时间复杂度T（n）=O(n)。inti=1,k=0;while(in-1){k=k+10*i;i++;}2.数据的逻辑结构被分为集合结构、线性结构、树结构和图结构四种。3.用具有n个元素的一维数组存储一个循环队列，则其队首指针总是指向队首元素的前一个位置，该循环队列的最大长度为n-1。4.一棵高度为5的二叉树中最少含有5个结点，最多含有31个结点。5.线性表的顺序存储结构特点是，表中逻辑上相邻的元素在机器内的位置也是相邻的。6.当堆栈采用顺序存储结构时，栈顶元素的值可用s—〉stack[s—〉top-1]或s.stack[s.top-1]表示；当堆栈采用链表存储结构时，栈顶元素的值可用Hs—〉data或HL—〉data或Head—〉next—〉data表示。7.采用冒泡排序对有n个记录的表A按关键字递增排序，若A的初始状态是按关键字递增，则排序过程中记录的比较次数为n-1。若A的初始状态是按关键字递减，则排序过程中记录的交换次数为n(n-1)/2。三、简答题（每小题6分，共30分）1.什么叫类型？什么叫抽象数据类型？//每问3分答：类型是具有相同特征的数据元素的集合。抽象数据类型是指一个逻辑概念上的类型和这个类型上的操作集合。2.什么叫运行时栈？什么叫运行时栈中的活动记录？//每问3分答：运行时栈是系统用于保存递归函数调用信息的堆栈。信息包括两个方面：一是调用函数的返回地址；二是调用函数的局部变量值。每一层递归调用所需保存的信息构成运行时栈的一个工作记录，运行时栈的栈顶工作记录称为运行时栈中的活动记录。3.比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？答：（1）顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。优点：存储密度大，存储空间利用率高。缺点：插入或删除元素时不方便。//2分第３页共5页（2）链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放节点值；另一部分存放表示节点间关系的指针。优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小，存储空间利用率低。//2分顺序表适宜于做查找等静态操作；链表适宜于做插入、删除等动态操作。若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；若线性表的长度变化较大，且其主要操作是插入、删除等操作，则采用链表。//2分4.动态数组和静态数组在使用方法上有什么不同？答：（1）从使用方法上来说，动态数组和静态数组除向系统申请内存空间的方法不同外，数组的使用方法完全相同。//3分（2）从性能上来说，静态数组必须确切指定数组元素个数，这样的指定在程序运行后不能改变；动态数组虽然也要确切指定数组元素个数，但因为这样的指定是在程序运行时通过调用函数实现的，一方面，可以利用malloc()函数或calloc()函数根据实际问题的需要申请动态数组的元素个数，另一方面，当所申请的动态数组空间不足时，还可以通过realloc()函数来重新指定动态数组元素的个数。//3分5.适宜于递归算法求解的问题的充分必要条件是什么？什么叫递归出口？答：充分必要条件是：（1）问题具有某种可借用的类同自身的子问题描述的性质；（2）某一有限步的子问题（也称作本原问题）有直接的解存在。//3分递归到某一步时的子问题有直接的解存在，这个子问题就是递归出口。或者说递归出口就是递归结束的条件。//3分四、算法思想题（每小题7分，共28分）1.假设用于通信的电文由字符集{A,B,C,D,E,F,G,H}构成，各字符在电文中出现的概率分别为{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}。为这8个字母设计哈夫曼编码（要求画出哈夫曼树）。解：哈夫曼树如下：//4分根据上图可得编码表：//3分A:1001B:01C:10111D:1010E:11F:10110G:00H:10002.设有数据元素序列{11，23，35，47，51，60，75，88，90，102，113，126}，用除留余数法构造哈希表，要求：（1）设计哈希表的长度取值m；1.0000.400.210.190.280.320.110.170.100.070.060.030.050.020.600000001111111第４页共5页（2）画出用开放地址法的线性探查法解决哈希冲突的哈希表结构；解：（1）要存放的数据元素个数为n=12，m最好取1.1n~1.7n之间的一个素数，所以设计哈希表的长度m≈1.5n=19。（也可取17）//2分（若取其它大于12的值最多得1分）（2）用哈希函数h(k)=kmodm=kmod19，哈希冲突函数d0=h(k)di=(di+1)mod19,(1≤i≤18)//2分依次对数据元素进行映射，得到的哈希地址分别为：//1分h(11)=11h(23)=4h(35)=16h(47)=9h(51)=13h(60)=3h(75)=18h(88)=12h(90)=14h(102)=7h(113)=18(冲突)h1(113)=（18+1）mod19=0h(126)=12(冲突)h1(126)=（12+1）mod19=13(冲突)h2(126)=（13+1）mod19=14(冲突)h3(126)=（14+1）mod19=15最后得哈希表结构如下：//2分11360231024711885190126357501234567891011121314151617183.已知一棵二叉树中序遍历序列为DBGEAFHC，后序遍历序列为DGEBHFCA请画出此二叉树。解：此二叉树如下：//错一个扣1分4.设数据元素关键字序列为{475，137，481，219，382，674，350，326，815，506}，写出执行希尔排序（增量d=5，3，1）算法时，各趟排序后的关键字序列。解：各趟排序后的关键字序列如下：初始关键字475137481219382674350326815506增量为5时475137326219382674350481815506//2分增量为3时219137326350382674475481815506//3分增量为1时137219326350382475481506674815//2分五、编程题（共12分）编写算法实现顺序表的就地逆置，即要求利用原顺序表的存储单元，请使用抽象数据类型，把数据元素序列（a0,a1,…an-1）逆置为（an-1,…a2,a1）。附：顺序表的抽象数据类型定义如下：typedefstruct{DataTypelist[MaxSize];intsize;CABDGEFH第５页共5页}SeqList;解：typedefstruct{DataTypelist[MaxSize];intsize;}SeqList;//3分voidConverse(SeqList*L){intmid,i;DataTypex;mid=L-size/2;for(i=0;imid;i++){x=L-list[i];L-list[i]=L-list[L-size-1-i];L-list[L-size-1-i]=x;}}//9分