资源描述：
《数据结构半期考试卷》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、工程技术学院数据结构科半期考试题班级学号姓名一、单项选择题：（每题1分，25小题，共25分）1、链表不具有的特点是___________。 A、可随机访问任一元素 B、插入删除不需要移动元素 C、不必事先估计存储空间 D、所需空间与线性表长度成正比2、 一个栈的输入序列是12345，则下列序列中是栈的输出序列的是___________。 A、2,3,4,1,5 B、5,4,1,3,2 C、 3,1,2,4,5 D、 1,4,2,5,33、栈和队列都是_____________。 A、顺序存储的线性
2、结构 B、限制的线性结构 C、链式存储的线性结构 D、限制的非线性结构4、队列操作的原则是_____________。A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删除5、3个结点可构成____________棵不同形态的二叉树。A、2 B、3 C、4 D、56、下面哪一种二叉树的先序序列和后序序列正好相反？____________A、空或者只有两个结点 B、高度大于其结点数C、任一结点无左孩子 D、任一结点既有左孩子又有右孩子7、深度为6（根的层次为1）的二叉
3、树至多有____________结点。A、64 B、32 C、31 D、638、在有n个结点的二叉链表中，值为非空的链域的个数是_____________。A、n-1 B、2n-1 C、n+1 D、2n+19、将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为______________。A、98 B、99 C、50 D、4810、有一个初始为空的栈和下面的输入序列A、B、C、D、E、F、G，现经过如下
4、操作：push，push，pop，push，push，top，push，pop，pop，则______是从栈中删除元素的序列。A、BEDB、BDEC、BEDCD、BDEC11．设语句x++的执行时间时单位时间，以下语句的时间复杂度是________。for(i=1;i<=n;i++)for(j=1;j<=n;j++)x++;A．O(1)B．O(n)C．O(n*n*n)D．O(n*n)12．一高度为h的非空二叉树（假设只含根节点的树的高度为1）最多有________个节点A．2hB．2h-1C．2h-1D．2h13．设双链表的节点类型定义如下，typed
5、efstructnode*link;structnode{ListItemelement;linkleft;linkright;}*p,*q,*r;删除双链表中节点p(由p指向的节点)的操作是______________。A．q=p->left;r=p->right;q->right=r;r->left=q;B．q=p->right;r=p->left;q->right=r;r->left=q;C．q=p->left;r=p->right;q->left=r;r->right=q;D．q=p->left;r=p->right;q->right=r->l
6、eft;14．会引起循环队列队头位置发生变化的操作是____________。A．出队列B．入队列C．取队首元素D．取队尾元素15．用指针实现二叉树，在n个节点的二叉树中含有________个空指针。A．nB．n-1C．n+1D．2n16.具有3个结点的二叉树最多可有________种不同的形态。A、2B、3C、4D、517．已知单链表结构为structnode{intdata;structnode*next;}*p,*q,*r;删除单链表中结点p(由p指向的结点)后面的结点的操作不正确的是_______________A、q=p->next;p->n
7、ext=q->next;B、p->next=p->next->next;C、r=p->next;p->next=q->next;D、q=p->next;r=q->next;p->next=r;18、单链表中有n个结点，在其中查找值为x的结点，在查找成功时需要比较的平均次数是__________________。A、nB、(n-1)/2C、n/2D、(n+1)/219、一棵非空的二叉树中，设根结点在第0层，在第i层上最多有_____________个结点。A、2(i+1)B、2iC、2(i-1)D、2i20、使用一个栈，每次限制进栈和出栈一个元素。假设进
8、栈的元素序列依次是a、b、c、d；指出不可能的出栈序列_______________。A、ab
