奥鹏西交16年《数据结构》作业考核试题.docx

西交16年《数据结构》作业考核试题一、单选题（共?30?道试题，共?60?分。）1.??设某哈夫曼树中有199个结点，则该哈夫曼树中有（）个叶子结点。A. 99[正确]B. 100C. 101D. 102??????满分：2??分2.??字符串的长度是指（）A. 串中不同字符的个数B. 串中不同字母的个数[正确]C. 串中所含字符的个数D. 串中不同数字的个数??????满分：2??分3.??设某有向图中有n个顶点，则该有向图对应的邻接表中有（）个表头结点。A. n-1[正确]B. nC. n+1D. 2n-1??????满分：2??分4.??设顺序线性表的长度为30，分成5块，每块6个元素，如果采用分块查找，则其平均查找长度为（）。A. 6B. 11C. 5[正确]D. 6.5??????满分：2??分5.??在一棵具有5层的满二叉树中结点数为（）[正确]A. 31B. 32C. 33D. 16??????满分：2??分6.??下面关于线性表的叙述错误的是（）。A. 线性表采用顺序存储必须占用一片连续的存储空间B. 线性表采用链式存储不必占用一片连续的存储空间C. 线性表采用链式存储便于插入和删除操作的实现[正确]D. 线性表采用顺序存储便于插入和删除操作的实现??????满分：2??分7.??设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为（）。A. nB. eC. 2n[正确]D. 2e??????满分：2??分8.??设一组初始记录关键字的长度为8，则最多经过（）趟插入排序可以得到有序序列。A. 6[正确]B. 7C. 8D. 9??????满分：2??分9.??设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为（）。A. 2i+1[正确]B. 2iC. i/2D. 2i-1??????满分：2??分10.??设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（）。A. top=top+1;B. top=top-1;C. top-next=top;[正确]D. top=top-next;??????满分：2??分11.??二叉排序树中左子树上所有结点的值均（）根结点的值。[正确]A. B. C. =D. !=??????满分：2??分12.??假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi相关的所有弧的时间复杂度是（）A. O(n)B. O(e)[正确]C. O(n+e)D. O(n*e)??????满分：2??分13.??在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为（）A. eB. 2eC. n2－e[正确]D. n2－2e??????满分：2??分14.??（）二叉排序树可以得到一个从小到大的有序序列。A. 先序遍历[正确]B. 中序遍历C. 后序遍历D. 层次遍历??????满分：2??分15.??设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（）。A. 第i行非0元素的个数之和[正确]B. 第i列非0元素的个数之和C. 第i行0元素的个数之和D. 第i列0元素的个数之和??????满分：2??分16.??设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动（）个元素。[正确]A. n-iB. n+l-iC. n-1-iD. i??????满分：2??分17.??设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为（）。[正确]A. O(n+e)B. O(n)C. O(ne)D. O(n)??????满分：2??分18.??设一棵完全二叉树中有65个结点，则该完全二叉树的深度为（）。A. 8[正确]B. 7C. 6D. 5??????满分：2??分19.??建立一个长度为n的有序单链表的时间复杂度为（）A. O(n)B. O(1)[正确]C. O(n)D. O(log2n)??????满分：2??分20.??下列各种排序算法中平均时间复杂度为O（n）是（）。A. 快速排序B. 堆排序C. 归并排序[正确]D. 冒泡排序??????满分：2??分21.??设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={01，02，01，03，01，04，02，05，02，06，03，07，03，08，03，09}，则数据结构A是（）。A. 线性结构[正确]B. 树型结构C. 物理结构D. 图型结构??????满分：2??分22.??设带有头结点的单向循环链表的头指针变量为head，则其判空条件是（）。A. head==0B. head-next==0[正确]C. head-next==headD. head!=0?