大工《数据结构》课程考试模拟试卷a

《大工《数据结构》课程考试模拟试卷a》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《数据结构》一、单项选择题（本大题共10小题，每小题3分，共30分）1、若进栈的序列为1，2，3，4，则不可能得到的出栈序列是（）。A.3,2,1,4B.3,2,4,1C.4,2,3,1D.2,3,4,12、深度为k的完全二叉树所含叶结点的个数最多为（），设根结点在第1层上。A.2kB.2k-1C.kD.2k-13、衡量查找算法效率的主要标准是（）。A.元素个数B.所需的存储量C.平均查找长度D.算法难易程度4、与线性表的顺序存储不相符的特性是（）。A.插入和删除操作灵活B.需要连续的存储空间C.便于随机访问D.存储密度大5、若进队序列为1，2，3，则出队序

2、列是（）。A.3,2,1B.1,2,3C.1,3,2D.3,1,26、不带头结点的单链表L为空的判定条件是（）。A.L==NULLB.L->next==NULLC.L->next==LD.L!=NULL7、union(A,B,C)表示求集合A和B的并集C。若A={a,b,c},B={c,d},则union(A,B,C)运算后C=（）。A．{a,b,c,d}B．{a,b,c}C．{a,b}D．{c,d}8、数组A中，每个元素的长度为3个存储单元，行下标i从1到5，列下标j从1到6，从首地址SA开始连续存放在存储器内，存放该数组至少需要的存储单元数是（）。A.9

3、0B.70C.50D.309、遍历一棵具有n个结点的二叉树，在先序序列、中序序列和后序序列中所有叶子结点的相对次序（）。A.都不相同B.完全相同C.先序和中序相同D.中序和后序相同10、用给定的哈夫曼编码来压缩数据文件，其压缩效率主要取决于（）。A.文件长度B.平均码长C.被压缩文件的特征D.以上都不是1、设有如下遗产继承规则：丈夫和妻子可以互相继承遗产，子女可以继承父亲或母亲的遗产，子女间不能相互继承，则表示该遗产继承关系的最合适的数据结构应该是（）。A.树B.图C.数组D.二叉树2、下列排序中，占用辅助空间最多的是（）。A.堆排序B.冒泡排序C.直接选择

4、排序D.二路归并3、排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（）。A.选择排序B.冒泡排序C.希尔排序D.插入排序4、在待排序序列局部有序的情况下，最好的内部排序应该是（）。A.直接选择排序B.堆排序C.直接插入排序D.快速排序5、下列排序算法中不稳定的是（）。A.直接选择排序B.直接插入排序C.起泡排序D.归并排序6、当利用大小为N的数组顺序存储一个栈时，假定用top==N表示栈空，则向这个栈插入一个元素时，首先应执行（）语句修改top指针。A.top++B.top--C.

5、top=0D.top=N-17、在一个带头结点的双向循环链表中，若要在p所指向的结点之前插入一个新结点，则需要相继修改（）个指针域的值。A.2B.3C.4D.58、利用3,6,8,12,5,7这六个值作为叶子结点的权，生成一棵哈夫曼树，该树的深度为（）。A.3B.4C.5D.69、在一个具有n个顶点和e条边的有向图的邻接表中，保存顶点单链表的表头指针向量的大小至少为（）。A.nB.2nC.eD.2e10、index(s,t)表示子串定位运算。若串t是串s的子串，则函数返回值是串t在串s中第一次出现的开始位置，否则返回值是0。若s="ababa",t="ba"

6、,则index(s,t)=（）。A.0B.1C.2D.3二、判断题（本大题共15小题，每小题2分，共30分）1、栈和队列逻辑上都是线性结构。（A.正确）2、算法的优劣与算法描述语言无关，但与所用计算机有关。（B.错误）3、在n个结点的无向图中，若边数大于n-1,则该图必是连通图。（B.错误）4、空串是任意串的子串。（A.正确）5、快速排序并非在任何情况下都比其他排序方法速度快。（A.正确）6、通常把串s称为主串，串t称为模式串，从主串s中查找与模式串t完全相同的子串的过程叫做模式匹配。（A.正确）7、堆排序是一种选择排序。（A.正确）8、排序的稳定性是指排序

7、算法中的比较次数保持不变，且算法能够终止。（B.错误）9、文件是性质相同的记录的集合，文件通常存储在外存上。（A.正确）10、散列文件的优点是存取速度通常比索引文件更快，插入删除方便，不需要索引区。（A.正确）11、用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。（B.错误）12、无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。（B.错误）13、散列函数越复杂越好，因为这样随机性好，冲突概率小。（B.错误）14、负载因子(装填因子)是散列表的一个重要参数，它反映散列表的装满程度。（A.正确）15、交换排序的基本思想是两两比较待排序记

8、录的排序码，并交换不满足顺序要求的那些偶对，直到全部