数据结构试题

1、数据结构试题一、单项选择题1、设一个栈的输入序列为A,B,C,D,则借助一个栈所得到的输出序列不可能是_。（1）A、B、C、D （2）D、C、B、A （3）A、C、D、B （4）D、A、B、C2、串是_。（1）不少于一个字母的序列 （2）任意个字母的序列（3）不少于一个字符的序列 （4）有限个字符的序列3、在n个叶子结点的哈夫曼树中，其结点总数为_。（1）不确定 （2）2n （3）2n+1 (4)2n-14、将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为_。（1）98 （2）99 （3）50 （4）488、

2、下列序列中，_是执行第一趟快速排序后得到的序列（排序的关键字类型是字符串）。（1）da,ax,eb,de,bbffha,gc (2)cd,eb,ax,daffha,gc,bb（3）gc,ax,eb,ce,bbffda,ha （4）ax,bb,cd,daffeb,gc,ha10、二分查找法要求查找表中各元素的必须是_排列（1）递增或递减 （2）递增 （3）递减 （4）无序11、对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用同_次序的遍历实现编号。（1）先序 （2）中序 （3）后序 （4）从根开始的层次遍历1

3、2、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是_二叉树。（）空或只有一个结点 （）高度等于其结点数（）任一结点无左孩子 （）任一结点无右孩子13、设循环队列中数组的下标范围是1n，其头尾指针分别为f和r，则其元素个数为_。（1）r-f （2）r-f+1 （3）（r-f）mod n+1 （4）(r-f+n) mod n14、数组A1.5，1.6的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A5,5的地址为_。（1）11140 （2）11145 （3）1120 （4）112515、对有18个元素的有序表作二分查法，则查找A3的比较序列的下标依次

4、为_。（1）1，2，3 （2）9，5，2，3 （3）9，5，3 （4）9，4，2，316、一个栈的输入序列为1，2，3，4，5，则下列序中不可能是栈的输出序列的是_。（1）2 3 4 1 5 （2）5 4 1 3 2 （3）2 3 1 4 5 （4）1 5 4 3 217、二判断题1、（ ）串长度是指串中不同字符的个数。2、（ ）数组可以看成是线性结构的一种推广，因此可以对它进行插入、删除等运算。3、（ ）在顺序表中取出第i个元素所花费的时间与i成正比。4、（ ）在栈满情况下不能作进栈运算，否则产生“上溢”。5、（ ）在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该

5、算法是不稳定。6、（ ）串是n个字母的有限序列(n=0)。7、（ ）若一棵二叉树的任一非叶子结点的度为2，则该二叉树为满二叉树。8、（ ）只有在初始数据表为倒序时，冒泡排序所招待的比较次数最多。9、（ ）线性表的长度是线性表所占用的存储空间的大小。10、（ ）如果两个串含有相同的字符，则说它们相等。11、（ ）快速排序算法是排序算法中最快的一种。12、（ ）一棵树中的叶子结点数一定等于与其对应的二叉树中的叶子结点数。三、填空题1、在有序表A1.20中，采用二分查找法查找元素等于A12的元素，所比较过的元素的下标依次为_。2、直接选择排序法所执行的元素交换次数最多为_。3、若某串的长度小于一个常

6、数，则采用_存储方式最节省空间。4、已知完全二叉树的第七层有8个结点，则其叶子结点数是_。5、冒泡排序算法在最好情况下的元素交换次数为_。6、具有100个结点的完全二叉树的深度为_。四、应用题1、已知二叉树的后序和中序序列如下，构造出该二叉树。 后序序列：ABCDEFG 中序序列：ACBGEDF2、对下面给出的数据序列，构造一棵哈夫曼树，并求出其带权路径长度。 4，5，6，7，10，12，15，18，233、分别画出满足下列条件的所有二叉树。 （1）先序序列和中序序列均为ABCDE。 （2）先序序列为ABCDE，并且与其相对应的树的高度为54、有一组关键码序列（38，19，65，13，97，49，41，95，1，73），采用冒泡法排序方法由小到大进行排序，请写出每趟的结果。5、对下面两棵二叉树，分别画出它们的顺序存储结构。6、已知一树的双亲表示法如下，其中各兄弟结点是依次出现的，画出该树及对应的二叉树。7、一项工程P由P1，P2，P3，P4，P5，P6六个子工程组成，这些工程之间有