数据结构试题A200711答案

陕西科技大学 试题纸（A参考答案及评分标准） 课程 数据结构 班级 信息、数学05 　　　　 学号 姓名 题号 一 二 三 四 五 六 七 八 九 十 总分 得分 阅卷人 选择题（每小题1分，共15分） 请在每小题的四个备选答案中，选出一个正确的答案，并将其号码填在括号内。 设一个栈的输入序列为1，2，3，4，则借助一个栈所得的输出序列不可能是（D）。 A．1，2，3，4 B．4，3，2，1 C．1，3，4，2 D．4，1，2，3 2. 设有80行的二维数组A[80][60]，其元素长度为4字节，按行优先顺序存储，基地址为300，则元素A[18][25]的存储地址为（D）。 A．3800 B．4376 C．3900 D．4720 3. 将一棵有100个节点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根节点的编号为0，则编号为49的结点的左孩子编号为（B）。 A．98 B．99 C．50 D．49 4. 在长度为n的顺序存储的线性表中，删除第i个元素（1≤i ≤n）时，需要从前向后依次前移（A）个元素。 A．n-i B．n-i+1 C．n-i-1 D．i 5. 栈的插入和删除操作在（A）进行。 A．栈顶 B．栈底 C．任意位置 D．指定位置 6. 链表适用于（A）查找。 A．顺序 B．二分法 C．二分法、顺序 D．随机 7. 深度为6(根结点的层次为1)的二叉树至多有（D）个结点。 　　A．64 B．32 C．31 D．63 8. 用邻接表表示图进行广度优先遍历时，通常是采用（B）来实现算法的。 A．栈 B．队列 C．树 D．图 9. 设有两个串ｐ和ｑ，求ｑ在ｐ中首次出现的位置的运算称作（B）。 A．连接 　B．模式匹配 C．求子串 D．求串长 10.若某线性表中最常用的操作是取第i个数据元素，则采用（D）存储方式最节省时间。 A．单链表 B．双链表 C．单向循环 D．顺序表 11.三个结点可构成（D）个不同形态的二叉树。 A．2 B．3 C．4 D．5 12.下列关键字序列中，（D）是堆。 A．16,72,31,23,94,53 B．94,23,31,72,16,53 C．16,53,23,94,31,72 D．16,23,53,31,94,72 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) 。 int i=1, k=0; while(i