数据结构试题A200711答案

陕西科技大学试题纸（A参考答案及评分标准）课程 数据结构班级信息、数学05 学号 姓名 题号—一二三四五六七八九十总分得分阅卷人一、选择题（每小题1分，共15分）请在每小题的四个备选答案中，选出一个正确的答案，并将其号码填在括号内。1.设一个栈的输入序列为1,2,3,4,则借助一个栈所得的输出序列不可能是（D）。A．1， 2，3，4 B．4， 3， 2， 1C．1, 3,4,2 D．4, 1, 2, 3设有80行的二维数组A[80][60]，其元素长度为4字节，按行优先顺序存储，基地址为300,则元素A[18][25]的存储地址为（D）。A．3800 B．4376 C．3900 D．4720将一棵有100个节点的完全二叉树从根这一层开始,每一层上从左到右依次对结点进行编号，根节点的编号为0,则编号为49的结点的左孩子编号为（B）。A．98 B．99 C．50 D．49在长度为n的顺序存储的线性表中，删除第i个元素（1WiWn）时，需要从前向后依次前移（A）个元素。A．n-i B．n-i+1 C．n-i-1 D．i栈的插入和删除操作在（A）进行。A.栈顶 B.栈底 C.任意位置 D.指定位置链表适用于（A）查找。A.顺序 B.二分法 C.二分法、顺序D.随机深度为6（根结点的层次为1）的二叉树至多有（D）个结点。A．64 B．32 C．31 D．63用邻接表表示图进行广度优先遍历时，通常是采用（B）来实现算法的。A.栈B.队列 C.树D.图设有两个串P和q,求q在P中首次出现的位置的运算称作（B）。A.连接B.模式匹配 C.求子串D.求串长10•若某线性表中最常用的操作是取第i个数据元素，则采用（D）存储方式最节省时间。A.单链表B.双链表 C.单向循环 D.顺序表11.三个结点可构成（D）个不同形态的二叉树。A．2 B．3 C．4 D．512•下列关键字序列中，（D）是堆。A．16,72,31,23,94,53 B．94,23,31,72,16,53C．16,53,23,94,31,72 D．16,23,53,31,94,72把一棵树转换为二叉树后，这棵二叉树的形态是（A）。A.唯一的 B.有多种，但根结点都没有左孩子C.有多种 D.有多种，但根结点都没有右孩子串是任意有限个（C）。A.符号构成的序列 B.符号构成的集合C.字符构成的序列 D.字符构成的集合在一个链队列中，假定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分）n为整型变量且为正整数，下列算法中加下划线语句的执行次数为n-2，算法的时间复杂度T（n）=0（n）。inti=1,k=0;while（i<n-1）{k=k+10*i;i++;}数据的逻辑结构被分为集合结构、线性结构、树结构和图结构四种。用具有n个元素的一维数组存储一个循环队列，则其队首指针总是指向队首元素的前一个位置，该循环队列的最大长度为n-1。一棵高度为5的二叉树中最少含有2个结点，最多含有31个结点。线性表的顺序存储结构特点是，表中逻辑上相邻的元素在机器内的卫置也是相邻的。当堆栈采用顺序存储结构时，栈顶元素的值可用s—〉stack[s—〉top-1]或s.stack[s.top-1]表示；当堆栈采用链表存储结构时，栈顶元素的值可用Hs—〉data或HL—〉data或Head—〉next—〉data表示。采用冒泡排序对有n个记录的表A按关键字递增排序，若A的初始状态是按关键字递增，则排序过程中记录的比较次数为n-1。若A的初始状态是按关键字递减，则排序过程中记录的交换次数为n（n-1）/2。三、简答题（每小题6分，共30分）什么叫类型？什么叫抽象数据类型？//每问3分答：类型是具有相同特征的数据元素的集合。抽象数据类型是指一个逻辑概念上的类型和这个类型上的操作集合。什么叫运行时栈？什么叫运行时栈中的活动记录？//每问3分答：运行时栈是系统用于保存递归函数调用信息的堆栈。信息包括两个方面：一是调用函数的返回地址；二是调用函数的局部变量值。每一层递归调用所需保存的信息构成运行时栈的一个工作记录，运行时栈的栈顶工作记录称为运行时栈中的活动记录。比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？答：（1）顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。优点：存储密度大，存储空间利用率高。缺点：插入或删除元素时不方便。//2分

（2）链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放节点值；另一部分存放表示节点间关系的指针。优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小，存储空间利用率低。//2分顺序表适宜于做查找等静态操作；链表适宜于做插入、删除等动态操作。若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；若线性表的长度变化较大，且其主要操作是插入、删除等操作，则采用链表。//2分动态数组和静态数组在使用方法上有什么不同？答：（1）从使用方法上来说，动态数组和静态数组除向系统申请内存空间的方法不同外，数组的使用方法完全相同。//3分（2）从性能上来说，静态数组必须确切指定数组元素个数，这样的指定在程序运行后不能改变；动态数组虽然也要确切指定数组元素个数，但因为这样的指定是在程序运行时通过调用函数实现的，一方面，可以利用malloc（）函数或calloc（）函数根据实际问题的需要申请动态数组的元素个数，另一方面，当所申请的动态数组空间不足时，还可以通过realloc（）函数来重新指定动态数组元素的个数。 〃3分适宜于递归算法求解的问题的充分必要条件是什么？什么叫递归出口？答：充分必要条件是：（1）问题具有某种可借用的类同自身的子问题描述的性质；（2）某一有限步的子问题（也称作本原问题）有直接的解存在。 //3分递归到某一步时的子问题有直接的解存在，这个子问题就是递归出口。或者说递归出口就是递归结束的条件。//3分四、算法思想题（每小题7分，共28分）1.假设用于通信的电文由字符集｛A,B,C,D,E,F,GH｝构成，各字符在电文中出现的概率分别为｛0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10｝。为这8个字母设计哈夫曼编码（要求画出哈夫曼树）。解：哈夫曼树如下：设有数据元素序列｛11，23，设有数据元素序列｛11，23，35，47，51，60，75，88，90，//4分G:00 H:10002.102，113，126｝，用除留余数法构造哈希表，要求：1）设计哈希表的长度取值m；(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<iW18) 〃2分依次对数据元素进行映射，得到的哈希地址分别为： 〃1分h(11)=11 h(23)=4 h(35)=16 h(47)=9 h(51)=13 h(60)=3h(75)=18 h(88)=12 h(90)=14 h(102)=7 h(113)=18(冲突)h1(113)=(18+1)mod19=0 h(126)=12(冲突)h1(126)=(12+1)mod19=13(冲突) h2(126)=(13+1)mod19=14(冲突)h3(126)=(14+1)mod19=15最后得哈希表结构如下：//2分初始关键字475137481219382674350初始关键字475137481219382674350326815506增量为5时475137326219382674350481815506增量为3时219137326350382674475481815506增量为1时1372193263503824754815066748154.设数据元素关键字序列为｛475，137，481，219，382，674，350，326，815，506｝，写出执行希尔排序(增量d=5,3,1)算法时，各趟排序后的关键字序列。解：各趟排序后的关键字序列如下：五、编程题(共12分)编写算法实现顺序表的就地逆置,即要求利用原顺序表的存储单元,请使用抽象数据类型，把数据元素序列(a0,a],...an1)逆置为(an1,_a2,a1)o附：顺序表的抽象数据类型定义如下：//2分//3分//2分1136023102471188519012635750 1 2 3 4 5 6 7 8 9 1011121314 15 1617183.已知一棵二叉树中序遍历序列为DBGEAFHC,后序遍历序列为DGEBHFCA请画出此二叉树。typedefstruct{DataTypelist[MaxSize];intsize;}SeqList;解：typedefstruct