徐州工程学院试卷一、选择题（共15小题，每题2分，共计30分）1．排序时扫描待排序记录序列，顺次比较相邻的两个元素的大小，逆序时就交换位置。这是的基本思想。A.堆排序B.直接插入排序C.快速排序D.冒泡排序2．已知一个有向图的邻接矩阵表示，要删除所有从第i个结点发出的边，应该。A.将邻接矩阵的第i行删除B.将邻接矩阵的第i行元素全部置为0C.将邻接矩阵的第i列删除D.将邻接矩阵的第i列元素全部置为03．有一个含头结点的双向循环链表，头指针为head,则其为空的条件是。A.head->prior==NULLB.head->next==NULLC.head->next==headD.head->next->prior==NULL4.在顺序表(3,6,8,10,12,15,16,18,21,25,30)中，用折半法查找关键码值11，所需的关键码比较次数为。A.2B.3C.4D.55.以下不是队列的基本运算？A.在队尾插入一个新元素B.从队列中删除第i个元素C.判断一个队列是否为空D.读取队头元素的值6.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644，A[2][2]存放位置在676，每个元素占一个空间，则A[3][3]存放在。A.688B.678C.692D.6967.设有6个结点的无向图，该图至少应有条边才能确保是一个连通图。A.5B.6C.7D.88.设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为。A.2，3，5，8，6B.3，2，5，8，6C.3，2，5，6，8D.2，3，6，5，89.在长度为n的顺序表的第i个位置上插入一个元素（1≤i≤n+1），元素的移动次数为。A.n–i+1B.n–iC.iD.i–110.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。A．1/2B.1C.2D.411.下面程序的时间复杂为。for（i=1，s=0；i<=n；i++）{t=1；for(j=1；j<=i；j++)t=t*j；s=s+t；}A.O(n)B.O(n2)C.O(n3)D.O(n4)12．对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为。A.顺序表B.用头指针表示的循环单链表C.用尾指针表示的循环单链表D.单链表13．算法分析的两个主要方面是。A．数据复杂性和程序复杂性B．可读性和文档性C．时间复杂度和空间复杂度D．正确性和简单性14．将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号最大的非叶结点的编号为。A.48B.49C.50D.5115．某二叉树结点的中序序列为：A、B、C、D、E、F、G，后序序列为：B、D、C、A、F、G、E，则其左子树中结点数目为。A.3B.2C.4D.5二、判断题（共10小题，每题1分，共计10分）1.数据结构中，与所使用的计算机无关的是数据的物理结构。（）2.空串就是空白串。（）3.有8个结点的无向连通图最少有7条边。（）4.一棵度为2的树与一棵二叉树是一样的。（）5.顺序表中逻辑上相邻的元素的物理位置必定相邻。（）6.头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。（）7.快速排序在被排序的数据完全无序的情况下最易发挥其长处。（）8.一棵二叉排序树，用先序遍历，可以得到各结点键值的递增序列。（）9.完全二叉树的某结点若无左孩子，则它必是叶子结点。（）10.平衡二叉排序树上任何一个结点的左、右子树的高度之差不大于1。（）三、填空题（共10空，每空2分，共计20分）1.数据的四种存储结构是顺序存储、①、②和散列存储。2.广义表A＝[C，（E，F，G），（H，（I，J））]，则其深度为③。3.设某棵二叉树中度数为0的结点数为N0，度数为1的结点数为N1，则该二叉树中度数为2的结点数N2为④。4.递归实现或函数调用时，处理参数及返回地址，应采用的数据结构是⑤。5.在各种查找方法中，平均查找长度与结点个数n无关的查找方法是⑥_____________。6.判定一个栈ST（最多元素为m0）为空的条件是⑦。7.高度为h的完全二叉树最少有⑧个结点。8.已知一有向图的邻接表存储结构如下：从顶点1出发，DFS遍历的输出序列是⑨，BFS遍历的输出序列是⑩。四、应