数据结构(C语言)试卷（2）.docVIP

PAGE PAGE 7 成都东软信息技术学院 200 ~200 学年第 学期期末试题——数据结构(C语言) 题号 一 二 三 四 五 六 总分 分数 本课程为闭卷考试，试卷共六道大题，试卷满分100分，考试时间120分钟。 一．选择题（10×2分）：共10小题，请将答案填入题中的括号中，每小题只有一个正确答案，错选或不选均不给分。 1．如果树的结点有4个兄弟，而且B为A的双亲，则B的度为（ ） Ａ．3 Ｂ．4 C．5 D．1 2．设有一个栈，元素的进栈次序为A,B,C,D,E，则下列（ ）是不可能的出栈序列。 A．A,B,C,D,E B．B,C,D,E,A C．E,A,B,C,D D．E,D,C,B,A 3．在所有排序方法中，关键字的比较次数与记录的初始排列无关的是（ ）。 A．快速排序 B．冒泡排序 C．直接插入排序 D．简单选择排序 4．设一棵二叉树共有20个度为2的结点，则叶子结点共有（ ）个。 A．40 B．19 C．20 D．21 5．在具有N个单元的顺序存储循环队列中，假定front和rear分别为对头指针和对尾指针，则判断对满的条件为（ ）。 A．front== rear B．(rear+1)%MAXSIZE==front C．front-rear==1 D．rear%MAXSIZE==front 6．设有1000个元素，用二分法查找时，最小比较次数为（ ） Ａ．0 Ｂ．1 C．10 D．500 7．一个元素进入队列的时间复杂度是（ ）。 A．O(1) B．O(n) C．O(n2) D．O(log2n) 8．一棵完全二叉树中根结点的编号为1，而且23号结点有左孩子但没有右孩子，则完全二叉树共有（ ）个结点。 A．24 B．45 C．46 D．47 9．如某数据结构的数据元素的集合为S={A,B,C,D,E,F,G}，数据元素间的关系为R={A,D,A,G,D,B,D,C,G,E,G,F}，则该数据结构是一种（ ）。 A．线性结构 B．树结构 C．链表结构 D．队列结构 10．从一个长度为n的顺序表中删除第i个元素(1≤i≤n)，需向前移动（ ）个元素。 A．n-i B．n-i+1 C．n-i-1 D．i 二．填空题（20分）：每空2分， １．后序序列和中序序列相同的二叉树为 、后序序列和前序序列相同的二叉树为 。 2．已知某算法的执行时间为n+n2,n代表问题规模，则该算法的时间复杂度是 。 3．数据结构有线性结构、树结构、 、 等几种逻辑结构。 4．采用快速排序法进行排序时，如果 时，排序效率会大大降低。 5．在一个长度为n的顺序表中插入一个元素，最少需要移动 元素，最多需要移动 元素， 6．如果指针p指向一棵二叉树的一个结点，则判断p没有左孩子的逻辑表达式为 。 7．栈的原则是 。 三．简答题（4×5分） 写出线性表(26,45,12,20,30)采用快速排序算法排序后，第一趟排序过程及结果。（5分） 线性表采用插入排序算法排序几趟后，有序部分是(16,20,40)，无序部分是(18,25)，则下一趟的排序需要移动几个元素？写出下一趟结束的结果。（5分） 给出下图所示的二叉树的中序遍历结果。（5分） A A F B C D G E 试说明单链表采用头结点的优点。（5分） 四．判断题（5×2分） １．如果某数据结构的每一个元素最多只有一个直接前驱，则其必为线性表。( ) 2．快速排序算法