《专升本《数据结构》_试卷_答案.pdf》由会员分享，可在线阅读，更多相关《专升本《数据结构》_试卷_答案.pdf（4页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、专升本数据结构专升本数据结构一、一、(共共 7575题，共题，共 150150 分）分）1。数据的基本单位是（）.（2 分）A。数据元素 B.记录 C.数据对象 D.数据项.标准答案：A2。（）是数据的不可分割的最小单位。（2 分）A。数据对象 B.数据元素 C.数据类型 D。数据项。标准答案：D3.算法的空间复杂度是对算法（）的度量.(2分)A。时间效率 B.空间效率 C.可读性 D.健壮性。标准答案：B4.（）是限制了数据元素的内部结构仅为一个字符的线性表。（2 分)A。栈 B.队列 C.串 D.数组。标准答案：B5.串的长度是指串中所含（）的个数。(2分)A.不同字符 B.不同字母 C.
2、相同字符 D.所有字符.标准答案：D6。采用带头结点双向链表存储的线性表，在删除一个元素时，需要修改指针（）次。（2 分）A。1 B。2 C.3 D.4.标准答案：B7。线性表的顺序存储结构是一种（）的存储结构。（2 分)A.顺序存取 B.随机存取 C。索引存取 D。Hash存取。标准答案:B8.数组 a1。.m采用顺序存储，a1和 am地址分别为 1024 和 1150，每个元素占 2 字节，则 m 是(）。(2分）A.64 B。32 C.16 D。8。标准答案：A9。深度为 h 的二叉树，第 h 层最多有（）个结点。(2分）A。h B。2h-1C.2h-1 D。2h.标准答案:C10.m
3、个结点的二叉树，其对应的二叉链表共有(）个非空链域。(2 分）A.m B。m+1 C。2m D.m-1。标准答案:B11.下面叙述错误的是（）。（2 分）A.顺序表是借助物理单元相邻表示数据元素之间的逻辑关系B。对于空队列进行出队操作过程中发生下溢现象C.有向图的邻接矩阵一定是对称的D。具有相同的叶子个数和具有相同的叶子权值的赫夫曼树不是唯一的.标准答案：C12.以下与数据的存储结构无关的术语是（）。(2分）1第1页共4页A。循环队列 B.双向链表 C。哈希表 D.数组。标准答案:D13。在一个长度为 n 的链式栈中出栈实现算法的时间复杂度为(）。（2分）A.O（1）B.O（log n)C。O
4、（n）D。O(n2）。标准答案：A14.在具有 k 个度数为 2的二叉树中，必有（)个叶子结点。（2分)A。k B。k1 C.2k D.k+1。标准答案：D15.在关键字序列（10，20，30，40，50）中，采用折半法查找 20，关键字之间比较需要（）次。（2分）A。1 B。2 C.3 D.4.标准答案：C16。16 某二叉树的后序遍历序列和和中序遍历序列均为 abcd，该二叉树的前序遍历序列是（）。（2分）A。abcd B。dcba C。acbd D.dbca.标准答案:B17.n 个顶点的无向连通图的生成树，至少有（）个边.（2分）A.n（n1)B。n(n-1)/2 C。2n D.n1。
5、标准答案:D18.可以采用(）这种数据结构，实现二叉树的层次遍历运算.（2分）A.队列 B。树 C。栈 D.集合。标准答案:A19。假设以数组 A0.n1存放循环队列的元素，其头指针 front 指向队头元素、尾指针 rear指向队尾元素一个，则在少用一个元素空间的前提下，队列空的判定条件为（）。(2分）A.rear=front B。（front+1)n=rearC.rear+1=front D。(rear+1）%n=front.标准答案：A20.序列（21,19,37,5，2）经冒泡排序法由小到大排序，第一趟后所得结果为（）。（2 分）A.（19，21,37，5，2）B。(19，21,5，2
6、，37）C.(19，21，5，37，2)D。(19,21,2,5，37）.标准答案：B21.二叉链表适合作为（）的存储结构。(2分）A.队列 B.二叉树 C。树 D.森林。标准答案:B，C,D22.设哈希(Hash）函数为 H(k）=k%17，其中 k 为关键字，关键字(）是同义词。（2 分）A。44,5，15 B。28,45，62 C。6，57,125 D。201,31,48。标准答案:B,C,D23。下列各项键值（）序列不是堆的。（2 分)A。94，68,23，16，5 B。94，23，68，5，16C。94，23，16，68，5 D.94，16，68,23，5。标准答案：C,D24.在下
7、列排序方法中,(）的空间复杂度为 O(n）。其中，n 为参加排序的元素个数.（2 分）A.选择排序 B。快速排序 C.归并排序 D.冒泡排序。标准答案:B，C25.十字链表适合于（）选作存储结构。（2 分）A.队列 B。稀疏矩阵C.边或弧数较少的图 D.二叉树。标准答案：B，C26。基于数据的逻辑关系,数据的逻辑结构划分为(）基本结构.（2 分）A.6类 B。5 类 C。4 类 D.3类.标准答案：C27。（）不是算法具有的 5 个特性之一。（2分）A。有穷性 B.确定性 C.可行性 D.正确性.标准答案：D28。算法的时间复杂度是对算法（）的度量。（2 分）A.时间效率 B。空间效率 C.可
8、读性 D。健壮性。标准答案：A29。线性表若采用链式存储结构时，要求结点的存储单元地址（）。（2分）A。必须是连续的 B。部分地址必须是连续的C。必须是不连续的 D。连续或不连续都可以.标准答案：D30。二维数组通常采用顺序存储，其优点是(）。（2 分）A.便于增加存储空间 B.防止下标溢出C.避免数据元素的移动 D.便于依据下标进行随机存取。标准答案:D31.采用顺序存储的线性表，若表长为 n，在第 i 号元素之后插入一个元素时，需要移动（)个元素。（2 分）A.i+1 B.i C.ni D.n-i+1.标准答案：C32.若已知一个栈的入栈序列是 1、2、3、4,其出栈序列不可能为_。（2分
9、）A.1、4、3、2 B。3、4、1、2 C.4、3、2、1 D。2、3、4、1.标准答案：B33。数组 a1。.256采用顺序存储，a的首地址为 10，每个元素占 2 字节，则 a21的地址是（）。（2 分)A.10 B。30 C.50 D.70。标准答案：C34.深度为 h 的完全二叉树至少有（）个叶子结点。(2分)A。2(h1)+1 B。2(h-2)+12第2页共4页C.2h1 D。2h2.标准答案:D35.若二叉树对应的二叉链表共有 m 个非空链域,则该二叉树有()个结点的二叉树。（2 分)A。m B。m-1 C。m+1 D。2m。标准答案：B36。下面叙述错误的是（）。（2 分）A。
10、单链表是借助指针表示数据元素之间的逻辑关系B.在顺序栈的入栈操作过程中可能发生上溢现象C。具有相同的叶子个数和具有相同的叶子权值的赫夫曼树是唯一的D.无向图的邻接矩阵一定是对称的.标准答案：C37。以下（）术语与数据的存储结构无关（2 分）A.栈 B.哈希表 C.线索树 D.双向链表.标准答案：A38。在一个长度为 n 的链式队列中入队实现算法的时间复杂度为（）。(2分)A.O（1）B.O(log n）C.O(n）D.O(n2）。标准答案：A39。队列的出队操作是指（）操作.（2 分）A。队尾删除 B.队头删除 C.队尾插入 D.队头插入.标准答案：B40。在关键字序列（10，15,20,25
11、，30)中采用折半法查找 25，依次与()关键字进行了比较。（2 分）A。30,25 B.20,25 C。20，30，25 D.25.标准答案：B41。16 某二叉树的前序遍历序列和和中序遍历序列分别为 abcd和 bcad,该二叉树的后序遍历序列是（）。（2 分）A.cbda B.dcba C.abcd D.dcba。标准答案：A42。所占用的存储空间大小仅与图的顶点个数相关的存储结构是（)。（2分)A。邻接表 B.逆邻接表C.十字链表 D.邻接矩阵.标准答案：D43。可以采用（）这种数据结构，实现图的深度优先遍历运算.（2分）A。队列 B。树 C。栈 D。集合.标准答案:C44。线性表采用
12、带头结点单链表实现，head 为头指针，则判断表空的条件为(）。（2 分)A。head=NULL B.head！=NULLC.headnext=NULL D.head-next！=NULL.标准答案：C45。在关键字序列（35,10，15,20，25)中采用最低位优先排序（LSD)基数排序，第一趟之后所得结果为（）。（2 分）A.10，20,15，25，35 B。10,20，35，15，25C.20,10，35，25，15 D。20，10,35，15，25.标准答案:B46.下列逻辑结构中，（）为线性结构。（2 分）A.栈 B.队列 C。串 D.二叉树。标准答案：A，B,C47.深度为 3 的
13、二叉树可能的结点个数是（).(2 分)A。1 B。2 C.3 D。4。标准答案：A,B48.下列各项键值（)序列是大顶堆的。（2 分)A。23，68，94，16，5 B.94，68，23，16,5C.94，23，68,16,5 D。94，16,68，23，5。标准答案：B,C49。下列（)是限制了插入和删除操作的特殊线性表。(2分)A。栈 B.队列 C。串 D.数组.标准答案:A,B50.对一棵二叉排序树，用（）方法进行遍历，不一定得到各结点键值的有序序列。(2分）A。先根遍历 B.中根遍历 C.后根遍历 D.层次遍历。标准答案：A,C，D51。数据的最小单位是（）。（2 分）A.数据元素 B
14、.记录 C。数据对象 D。数据项.标准答案：D52.算法是对某一类问题求解步骤的有限序列。其中,（）是算法具有的 5 个特性之一.（2 分）A.有穷性 B。正确性 C。可读性 D.健壮性.标准答案：A53。（）是数据的逻辑结构。(2分）A。顺序表 B.链表 C。线性表 D。十字链表。标准答案：C54。()是限制了插入和删除操作在一端进行的线性表。（2 分）A.栈 B.队列 C.串 D。数组.标准答案：A55.（）是限制了插入和删除操作分别在两端进行的线性表.（2 分)A。栈 B.队列 C。串 D。数组.标准答案：B56。用链表表示线性表的优点是(）。（2 分）A.便于插入和删除B.便于随机存取
15、C。花费的存储空间较顺序存储少3第3页共4页D.数据元素的物理顺序与逻辑顺序相同。标准答案：A57.若已知一个栈的入栈序列是 1、2、3、4，其出栈序列不可能为（）。（2分)A.1、4、3、2 B.2、3、4、1 C.4、3、2、1 D.3、4、1、2。标准答案：D58.串下列关于串的叙述中，正确的是(）.（2分）A.2个串的长度相等,则 2个串相等B。空串至少包一个空格C.替换操作可以实现字符的删除D.一个串的长度至少是 1。标准答案：C59。深度为 h 的二叉树，第 h层至少有（）个结点。（2分）A.0 B.1 C。8 D.16.标准答案：B60.假设 n0,在程序段y=0;while（(
16、y+1)（y+1）A.n B。C。n2。标准答案：C61。下面叙述错误的是（）。（2 分)A。在集合1,2，3,4，5中元素 1是 2的直接前驱B。二叉排序树的中序遍历序列一定是有序的C.有 3 个结点的不同形态二叉树的数目为 5D.哈夫曼树中所有结点的孩子数目只可能为 2或者为 0。标准答案：A62。以下数据结构中，(）是线性结构.（2分）A。广义表 B.二叉树 C.稀疏矩阵 D.串.标准答案：D63。在一个长度为 n 的顺序表中删除一个元素的算法的时间复杂度为（）。（2分）A。O（1)B。O(log n）C。O(n)D.O（n2)。标准答案：C64.如果一个 huffman 树含有 n 个
17、叶子，则该树必有（）的结点.（2 分）A.n+1 B.2n+1 C。2n D。2n-1。标准答案：D65.在关键字序列(10,15，20,25，30)中,采用折半法查找 25，关键字之间比较需要（)次。（2 分）A.1 B。2 C。3 D.4.标准答案:B66.16 某二叉树的前序遍历序列和和中序遍历序列均为 abcd，该二叉树的后序遍历序列是（）.（2 分）A.abcd B.dcba C。acbd D.dbca。标准答案：B67。m 个顶点的有向完全图有（）个弧.（2 分)A.m(m1)/2 B。m+1 C.m D.m（m-1).标准答案:D68。下列各项键值（）序列不是堆的。(2分）A。9
18、4，68,23，16，5 B。94，23，68，5,16C。94，23，68，16,5 D.94,16,68，23，5.标准答案：D69.设单链表中指针 p 指向结点 A,q 指向新元素结点，若要 A之后插入一个新元素，则所需修改指针的操作为（）。（2 分）A。p-next=q,qnext=pnextB。qnext=p-next，p-next=qC。p-next=qnext，qnext=pD。p-next=p，q-next=p-next。标准答案：B70。在关键字序列（149，138,165,197，176，113，127)中采用最低位优先排序（LSD)基数排序，第一趟之后所得结果为(）。（2
19、分）A.149，138，165,197，176，113，127B.128，149，165，197，113,176,127C.128，149，165，197，113,127，176D。113，127，138，149，165，176,197.标准答案:B71。下列术语表示的数据中，()是同义语。（2 分）A.结点 B。数据元素 C.顶点 D.数据项。标准答案：A,B,C72。对于采用链式结构的队列,（）运算的实现算法的时间复杂度为 O(1)。（2 分)A。入队 B。出队 C。求队长 D。队清空。标准答案：A，B73.在 n 个数据元素中进行查找，（）方法的最坏时间复杂度为 O(n）。（2分）A。顺序查找 B。折半查找C。二叉排序树查找 D.斐波那契查找.标准答案：A，C74.下列是二叉树 4 种常见的遍历方法。其中，（）属于深度优先遍历.（2 分）A。前序遍历 B.中序遍历 C。后序遍历 D.层序遍历。标准答案：A，B,C75.下列（）哈希函数构造方法所得的哈希函数，使得查找时间复杂度通常不能到达 O（1)。(2分)A。直接定地法 B.数字分析法 C.平方取中法 D.折叠法.标准答案:B,C,D4第4页共4页