数据结构  设计 
课程代码：7399
一、单项选择题（在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。每小题2分，共40分）
1、串的长度是（ ）。
  A、串中不同字母的个数
  B、串中不同字符的个数
  C、串中所含字符的个数，且大于0
  D、串中所含字符的个数
2、若用数组]作为两个栈S1和S2的共同存储结构，对任何一个栈，只有当S全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是（）。
  A、S1的栈底位置为0，S2的栈底位置为n+1
  B、S1的栈底位置为0，S2的栈底位置为n/2
  C、S1的栈底位置为1，S2的栈底位置为n
  D、S1的栈底位置为1，S2的栈底位置为n/2
3、队列操作的原则是（）。
  A、先进先出
  B、后进先出
  C、只能进行插入
  D、只能进行删除
4、有64个结点的完全二叉树的深度为（）（根的层次为1）。
  A、8      B、7      C、6      D、5
5、在有n个结点的二叉链表中，值为非空的链域的个数为（）。
  A、n-1
  B、2n-1
  C、n+1
  D、2n+1
6、带权有向图G用邻接矩阵A存储，则顶点i的人度等于A中（）。
  A、第i行非∞的元素之和
  B、第i列非∞的元素之和
  C、第i行非∞且非0的元素个数
  D、第i列非∞且非0的元素个数
7、在有n个结点且为完全二叉树的二叉排序树中查一个键值，其平均比较次数的数量级为（）。
  A、0(n)
  B、0(log2n)
  C、0(nolg2n)
  D、0(n2)
8、若表R在排序前已按键值递增顺序排列，则（）算法的比较次数最少。
  A、直接插入排序
  B、快速排序
  C、归并排序
  D、选择排序
9、下列排序算法中，（）排序在某趟结束后不一定选出一个元素放到其最终的位置上。
  A、选择
  B、冒泡
  C、归并
  D、堆
10、若线性表最常用的操作是存取第i个元素及其前趋的值，则采用（）存储方式节省时间。
  A、单链表
  B、双链表
  C、单循环链表
  D、顺序表
11、对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用（）遍历实现编号。
  A、无序
  B、中序
  C、后序
  D、从根开始的层次遍历
12、某二叉树的中序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。
  A、空或只有一个结点
  B、高度等于其结点数
  C、任一结点无左孩子
  D、任一结点无右孩子
13、下列排序算法中，时间复杂度不受数据初始状态影响，恒为0（nlog2n）的是（）
  A、堆排序
  B、冒泡排序
  C、直接选择排序
  D、快速排序
14、下列排序算法中，（）算法可能会出现下面情况：初始数据有序时，花费的时间反而最多。
  A、堆排序
  B、冒泡排序
  C、快速排序
  D、SHELL排序
15、一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（）。
  A、2 3 4 1 5
  B、5 4 1 3 2
  C、2 3 1 4 5
  D、1 5 4 3 2
16、设循环队列中数组的下标范围是1-n先序中序后序遍历二叉树，其头尾指针分别为f和r，则其元素个数为（）。
  A、r-f
  B、r-f+1
  C、(r-f) mod n+1
  D、(r-f+n) mod n
17、若某链表最常用的操作是在最后一个结点之后插入一个结点删除最后一个结点，则采用（）存储方式最节省时间。
  A、单链表
  B、双链表
  C、带头结点的双循环链表
  D、单循环链表
18、一棵非空的二叉树的先序序列和后序序列正好相同，则该二叉树一定满足（）。
  A、其中任意一结点均无左孩子
  B、其中任意一结点均无右孩子
  C、其中只有一个结点
  D、是任意一棵二叉树
19、一棵左右子树均不空的二叉树在先序线索化后，其空指针域数为（）。
  A、0      B、1      C、2      D、不确定
20、数组A[1..5,1..6]每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[5,5]的地址为（）。
  A、1140      B、1145      C、1120      D、1125
二、判断题（对的打“√”，错的打“×”。每小题1分，共10分）
1、线性表的唯一存储形式是链表。（）
2、已知指针P指向链表L中的某结点，执行语句P：=P∧.next不会删除该链表中的结点。（）
3、在链队列中，即使不设置尾指针也能进行入队操作。（）
4、如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串。（）
5、设与一棵树T所对应的二叉树为BT，则与T中的叶子结点所对应的BT中的结点也一定是叶子结点。（）
6、9阶B树中，除根以外的任何一个非叶子结点中的关键字数目均在5-9之间。（）
7、任一AOE网中至少有一条关键路径，且是从源点到汇点的路径中最长的一条。（）
8、若图G的最小生成树不唯一，则G的边数一定多于n-1，并且权值最小的边有多条（其中n为G的顶点数）。（）
9、给出不同的输入序列建造二叉排序树，一定得到不同的二叉排序树。（）
10、由于希尔排序的最后一趟与直接插入排序过程相同，因此前者一定比后者花费的时间多。（）
三、填空题（每空2分，共20分）
1、已知二叉树中叶子数为50，仅一个孩子的结点数为30，则总结点数___。
2、直接选择排序算法在最好情况下所作的交换元素的次数为___。
3、有n个顶点的连通图至少有 ___条边。
4、取出广义表A=(x,(a,b,c,d))中原子a的函数是____。
5、在双循环链表中，删除指针P所指结点的语句序列是____。
6、队列的特性是____。
7、若某串的长度小于一个常数，则采用____存储方式最节省空间。
8、在有n个叶子结点的哈夫曼树中，总结点数是___。
9、在有序表A[1..18]中，采用二分查算法查元素值等于A[7]的元素，所比较过的元素的下标依次为____。
10、求最短路径的FLOYD算法的时间复杂度为____。
四、简答题（每小题5分，共15分）
1、对下面数据表，写出采用冒泡算法排序的前三趟的结果。
  (25  10  20  31  5  44  16  61  100  3)
2、已知下面二叉排序树的各结点的值依次为1-9，写出该二叉树的层次遍历结果。






3、对下面的递归算法，写出调用P(4)的执行结果。
  procedure p (w:Integer);
    begin
      if w>0 then
      begin write(W);
              P(w-1);
            P(w-1)
          end
    end;
五、综合应用题（共15分）
1、采用直接插入排序算法，对关键字序列（46,32,55,81,65,11,25,43）按从小到大的次序进行排序，写出每趟排序的结果。（满分6分）
2、已知带头结点的单循环链表L中至少有一个元素，设计算法判断L中各元素的值是否均是其序号的两倍，若满足，返回true。否则返回false，同时返回该链表中的结点序号。（满分9分）

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。