数据结构试题a200711答案

《数据结构试题a200711答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、陕西科技大学试题纸（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

2、个节点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根节点的编号为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.用邻接表表示图进行广度优先遍历时，通常是采

3、用（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,53第５页共5页C．16,53,23,94,31,72D．16,23,53,31,94,7213.把一棵树转换为二叉树后，这棵二叉树的形

4、态是（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，

5、算法的时间复杂度T（n）=O(n)。inti=1,k=0;while(i

6、的值可用Hs—〉data或HL—〉data或Head—〉next—〉data表示。7.采用冒泡排序对有n个记录的表A按关键字递增排序，若A的初始状态是按关键字递增，则排序过程中记录的比较次数为n-1。若A的初始状态是按关键字递减，则排序过程中记录的交换次数为n(n-1)/2。三、简答题（每小题6分，共30分）1.什么叫类型？什么叫抽象数据类型？//每问3分答：类型是具有相同特征的数据元素的集合。抽象数据类型是指一个逻辑概念上的类型和这个类型上的操作集合。1.什么叫运行时栈？什么叫运行时栈中的活动记录？//每问3分答：运行时栈是系统用于保存递归函数调用信息的堆栈。信息包括两个方面：一是调

7、用函数的返回地址；二是调用函数的局部变量值。每一层递归调用所需保存的信息构成运行时栈的一个工作记录，运行时栈的栈顶工作记录称为运行时栈中的活动记录。2.比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？答：（1）顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。第５页共5页优点：存储密度大，存储空间利用率高。缺点：插入或删除元素时不方便。//2分（2）链式存储时，相邻数据元