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

《奥鹏西交16年数据结构作业考核试题.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、西交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.  设顺

2、序线性表的长度为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

3、.  设某无向图中有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指向当前链式栈的栈顶，则删除栈顶元素的操

4、作序列为（）。A.top=top+1;B.top=top-1;C.top->next=top;[正确]D.top=top->next;      满分：2  分11.  二叉排序树中左子树上所有结点的值均（）根结点的值。[正确]A.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条边的无向图的邻接矩阵中,

5、零元素的个数为（）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个元素需要移动（）个元素

6、。[正确]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.  下

7、列各种排序算法中平均时间复杂度为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.  设带有头结点的单向循环链

8、表的头指针变量为head，则其判空条件是（）。A.head==0B.head->next==0[正确]C.head->next==headD.head!=0      满分：2  分23.  如下陈述中正确的是（）[正确]A.串是一种特殊的线性表B.串的长度必须大于零C.串中元素只能是字母