北京语言大学23春“计算机科学与技术”《数据结构》考试高频考点参考题库答案

长风破浪会有时，直挂云帆济沧海。北京语言大学23春“计算机科学与技术”《数据结构》考试高频考点参考题库带答案（图片大小可自由调整）第I卷一.综合考核(共15题)1.下面关于线性表的叙述错误的是()。A.线性表采用顺序存储必须占用一片连续的存储空间B.线性表采用链式存储不必占用一片连续的存储空间C.线性表采用链式存储便于插入和删除操作的实现D.线性表采用顺序存储便于插入和删除操作的实现2.若已知一个栈序列是1，2，3，...，n，其输出序列为p1，p2，p3，...，pn，若p1=n，则pi为()。A.iB.n-iC.n-i+1D.不确定3.线性表的链式存储结构是一种___。A.顺序存取的存储结构B.随机存取的存储结构C.索引存取的存储结构D.Hash存取的存储结构4.在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度(即x与元素的平均比较次数，假定查找每个元素的概率都相等)为()。A.nB.n/2C.(n+1)/2D.(n-1)/25.线性表的顺序存储结构是一种()存储结构。A.散列存取B.顺序存取C.随机存取D.索引存取6.具有n个结点的连通图至少有()条边。A.n-1B.nC.n(n-1)/2D.2n7.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点的个数是()。A.9B.11C.15D.不能确定8.以下____不是队列的基本运算。A.读取队头元素的值B.判断一个队列是否为空C.从队尾插入一个新元素D.从队列中删除第i个元素9.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的()倍。A.1/2B.1C.2D.410.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为___。A.O(n)O(n)B.O(n)O(1)C.O(1)O(n)D.O(1)O(1)11.不定长文件是指___。A.记录的长度不固定B.文件的长度不固定C.字段的长度不固定D.关键字项的长度不固定12.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为___。A.O(n2)B.O(n)C.O(1)D.O(0)13.线性表(a1，a2，...，an)以链式方式存储，访问第i位置元素的时间复杂度为()。A.O(0)B.O(1)C.O(n)D.O(n2)14.设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列___方法可以达到此目的。A.插入排序B.快速排序C.归并排序D.堆排序15.数组的逻辑结构不同于下列___的逻辑结构。A.队列B.线性表C.树D.栈第II卷一.综合考核(共15题)1.在一个长度为n(n>1)的单链表上，设有头和尾两个指针，执行___操作与链表的长度有关。A.在单链表第一个元素前插入一个新元素B.在单链表最后一个元素后插入一个新元素C.删除单链表中的第一个元素D.删除单链表中的最后一个元素2.设Hash的地址空间为0到m-1，哈希函数为h(k)=k%p，为了减少发生冲突的可能性，一般取p为()。A.小于m的最大素数B.小于m的最大奇数C.小于m的最大合数D.小于m的最大偶数3.若已知一个栈序列是1，2，3，...，n，其输出序列为p1，p2，p3，...，pn，若p1=n，则pi为___。A.不确定B.n-i+1C.n-iD.i4.需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是()。A.单链表B.静态链表C.线性链表D.顺序存储结构5.在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是___。A.O(nlog2n)B.O(n2)C.O(n)D.O(1)6.串是一种特殊的线性表，其特殊性体现在()。A.可以顺序存储B.数据元素是一个字符C.可以链式存储D.数据元素可以是多个字符7.设一组初始记录关键字序列(5,2,6,3,8)，以第一个记录关键字5为基准进行一趟快速排序的结果为___。A.3,2,5,8,6B.3,2,5,6,8C.2,3,6,5,8D.2,3,5,8,68.在长度为n的顺表表的第i个位置上插入一个元素(1≤i≤n+1)，元素的移动次数为()。A.n-i+1B.n-iC.iD.i-19.下列四种基本的逻辑结构中，数据元素之间关系最弱的是()。A.集合B.线性结构C.树形结构D.图状结构10.由权值分别为11,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为___。A.71B.53C.48D.2411.有一个有序表{1，3，9，12，32，41，45，62，75，77，82，95，100}，当折半查找值为82的结点时，___次比较后查找成功。A.8B.5C.4D.1112.下列四种排序中()的空间复杂度最大。A.插入排序B.冒泡排序C.堆排序D.归并排序13.由带权为9，2，5，7的四个叶子结点构造一颗哈夫曼树，该树的带权路径长度为()。A.23B.37C.46D.4414.稀疏矩阵压缩后，必会失去()功能。A.顺序存储B.随机存储C.输入输出D.以上都不对15.串的长度是指___。A.串中所含非空格字符的个数B.串中所含字符的个数C.串中所含不同字符的个数D.串中所含不同字母的个数第I卷参考答案一.综合考核1.参考答案：D2.参考答案：C3.参考答案：B4.参考答案：C5.参考答案：C6.参考答案：A7.参考答案：C8.参考答案：D9.参考答案：C10.参考答案：D11.参考答案：A12.参考答案：B13.参考答案：C14.参考答案：D15.参考答案：C第II卷参考答案一.