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

西交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.后序遍历[正确]B.正确

满分：2

分8.

先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。A.错误[正确]B.正确

满分：2

分9.

若一个叶子结点是某二叉树的中序遍历序列的最后一个结点，则它必是该二叉树的先序遍历序列中的最后一个结点。A.错误[正确]B.正确

满分：2

分10.

不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。A.错误[正确]B.正确

满分：2

分11.

子串“ABC”在主串“AABCABCD”中的位置为2。A.错误[正确]B.正确

满分：2

分12.

设某堆中有n个结点，则在该堆中插入一个新结点的时间复杂度为O(log2n)。A.错误[正确]B.正确

满分：2

分13.

哈夫曼树中没有度数为1的结点。A.错误[正确]B.正确

满分：2

分14.

子串“ABC”在主串“AABCABCD”中的位置为3。[正确]A.错误B.正确

满分：2

分15.

线性表中的所有元素都有一个前驱元素和后继元素。[正确]A.错误B.正确

满分：2

分16.

稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。A.错误[正确]B.正确

满分：2

分17.

希尔排序算法的时间复杂度为O（n）。[正确]A.错误B.正确

满分：2

分18.

为度量一个搜索算法的性能，需要在时间和空间方面进行权衡。A.错误[正确]B.正确

满分：2

分19.

分块查找的基本思想是首先在索引表中进行查找，以便确定给定的关键字可能存在的块号，然后再在相应的块内进行顺序查