北京语言大学22春“计算机科学与技术”《数据结构》离线作业（一）辅导答案16

书山有路勤为径，学海无涯苦作舟！ 住在富人区的她北京语言大学22春“计算机科学与技术”数据结构离线作业（一）辅导答案一.综合考核(共50题)1.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为_。A.O(n2)B.O(n)C.O(1)D.O(0)参考答案：B2.一个加权的无向连通图的最小生成树()。A.有一颗或多颗B.只有一颗C.一定有多颗D.可能不存在参考答案：A3.组成数据的基本单位是_。A.数据项B.数据类型C.数据变量D.数据元素参考答案：D4.稀疏矩阵压缩后，必会失去()功能。A.顺序存储B.随机存储C.输入输出D.以上都不对参考答案：B5.允许对队列进行的操作有()。A.对队列中的元素排序B.取出最近进队的元素C.在队头元素之前插入元素D.删除队头元素参考答案：D6.栈的插入和删除操作在_进行。A.栈顶B.栈底C.指定位置D.任意位置参考答案：A7.设有以下四种排序方法，则()的空间复杂度最大。A.冒泡排序B.快速排序C.堆排序D.希尔排序参考答案：B8.若已知一个栈序列是1，2，3，.，n，其输出序列为p1，p2，p3，.，pn，若p1=n，则pi为_。A.不确定B.n-i+1C.n-iD.i参考答案：B9.数组的逻辑结构不同于下列_的逻辑结构。A.队列B.线性表C.树D.栈参考答案：C10.设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列_方法可以达到此目的。A.插入排序B.快速排序C.归并排序D.堆排序参考答案：D11.下列四种排序中()的空间复杂度最大。A.插入排序B.冒泡排序C.堆排序D.归并排序参考答案：D12.线性表采用链式存储时，结点的存储地址_。A.连续与否均可B.必须是连续的C.必须是不连续的D.和头结点的存储地址相连续参考答案：A13.栈和队列的共同点是()。A.都是先进后出B.都是先进先出C.只允许在端点处插入和删除元素D.没有共同点参考答案：C14.线性表是具有n个()的有限序列。A.字符B.数据元素C.数据项D.表元素参考答案：B15.线性表的顺序存储结构是一种()存储结构。A.散列存取B.顺序存取C.随机存取D.索引存取参考答案：C16.若已知一个栈序列是1，2，3，.，n，其输出序列为p1，p2，p3，.，pn，若p1=n，则pi为()。A.iB.n-iC.n-i+1D.不确定参考答案：C17.指针p所指的元素是双向循环链表L的尾元素的条件是()。A.p=LB.p=NULLC.p-prior=LD.p-next=L参考答案：D18.串是一种特殊的线性表，其特殊性体现在()。A.可以顺序存储B.数据元素是一个字符C.可以链式存储D.数据元素可以是多个字符参考答案：B19.在长度为n的顺表表的第i个位置上插入一个元素(1in+1)，元素的移动次数为_。A.n-i+1B.n-iC.i-1D.i参考答案：A20.设某棵二叉树中有2000个结点，则该二叉树的最小高度为_。A.9B.12C.11D.10参考答案：C21.设二维数组A610，每个数组元素占用4个存储单元，若按行优先顺序存放数组元素，a00的存储地址为860，则a35的存储地址是_。A.860B.1200C.1140D.1000参考答案：D22.设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有_个空指针域。A.4mB.2m-1C.2m+1D.2m参考答案：D23.设Hash的地址空间为0到m-1，哈希函数为h(k)=k%p，为了减少发生冲突的可能性，一般取p为()。A.小于m的最大素数B.小于m的最大奇数C.小于m的最大合数D.小于m的最大偶数参考答案：A24.设计一个判别表达式中左、右括号是否配对出现的算法，采用()数据结构最佳。A.线性表的顺序存储结构B.队列C.线性表的链式存储结构D.栈参考答案：D25.在长度为n的顺表表的第i个位置上插入一个元素(1in+1)，元素的移动次数为()。A.n-i+1B.n-iC.iD.i-1参考答案：C26.下列说法中，不正确的是()。A.数据元素是数据的基本单位B.数据项是数据中不可分割的最小可标识单位C.数据可由若干个数据元素构成D.数据项可由若干个数据元素构成参考答案：D27.按层次次序将一颗有n个结点的完全二叉树的所有结点从1到n编号，当iA.2i-1B.2iC.2i+1D.不确定参考答案：B28.需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是()。A.单链表B.静态链表C.线性链表D.顺序存储结构参考答案：C29.下列关于数据结构基本概念的叙述中，正确的是_。A.结点是有独立含义的数据最小单位B.数据的逻辑结构分为表结构和树结构C.数据的存储结构分为线性结构和非线性结构D.数据元素是数据的基本单位参考答案：D30.在一个无向图中，所有顶点的度数之和等于所有边数的()倍。A.1/2B.1C.2D.4参考答案：C31.设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有()条有向边。A.nB.n-1C.mD.m-1参考答案：C32.以下()不是队列的基本运算。A.从队尾插入一个新元素B.从队列中删除第i个元素C.判断一个队列是否为空D.读取队头元素的值参考答案：B33.内部排序是根据关键词的大小重新安排各()的顺序。A.关键词B.数据项C.文件D.数据元素参考答案：B34.设某棵二叉树中有2000个结点，则该二叉树的最小高度为()。A.9B.10C.11D.12参考答案：C35.有一个有序表1，3，9，12，32，41，45，62，75，77，82，95，100，当折半查找值为82的结点时，_次比较后查找成功。A.8B.5C.4D.11参考答案：C36.在一个长度为n(n1)的单链表上，设有头和尾两个指针，执行_操作与链表的长度有关。A.在单链表第一个元素前插入一个新元素B.在单链表最后一个元素后插入一个新元素C.删除单链表中的第一个元素D.删除单链表中的最后一个元素参考答案：D37.若有18个元素的有序表存放在一堆数组A19中，第一个元素放A1中，现进行二分查找，则查找A3的比较序列的下标依次为_。A.9,5,3B.9,5,2,3C.9,4,2,3D.1,2,3参考答案：C38.以下_不是队列的基本运算。A.读取队头元素的值B.判断一个队列是否为空C.从队尾插入一个新元素D.从队列中删除第i个元素参考答案：D39.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的()倍。A.1/2B.1C.2D.4参考答案：C40.在一个有向图中所有顶点的入度之和等于所有顶点的出度之和的()倍。A.1/2B.1C.2D.4参考答案：B41.设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有()个空指针域。A.2m-1B.2mC.2m+1D.4m参考答案：B42.与单链表相比，双链表的优点之一是()。A.插入、删除操作更简单B.可以进行随机访问C.可以省略表头指针或表尾指针D.顺序访问相邻结点更灵活参考答案：C43.排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为_。A.选择排序B.插入排序C.希尔排序D.冒泡排序参考答案：B44.广义表(a)，a)的表头是_。A.aB.(a)C.()D.(a)参考答案：B45.由带权为9，2，5，7的四个叶子结点构造一颗哈夫曼树，该树的带权路径长度为()。A.23B.37C.46D.44参考答案：D46.设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数为_。A.5B.4C.3D.1参考答案：B47.栈的插入和删除操作在()进行。A.栈顶B.栈底C.任意位置D.指定位置参考答案：A48.在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是()。A.O(1)B.O(n)C.O(n2)D.O(nlog2n)参考答案：B49.由权值分别为11,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为_。A.71B.53C.48D.24参考答案：A50.具有n个结点的连通图至少有()条边。A.n-1B.nC.n(n-1)/2D.2n参考答案：A