专升本《数据结构》-试卷-答案

PAGE5PAGE5第1页共5页.标准答案：C(75题150分)

专升本《数据结构》

10.m个结点的二叉树,其对应的二叉链表共有（）个非空链域。（2分)A.m B.m+1 C。2m D。m-1。标准答案:B1。数据的基本单位是（）。（2分）A.数据元素 B.记录 C。数据对象 D。数据项.标准答案：A2。(）是数据的不可分割的最小单位。（2分）A。数据对象 。数据元素 C.数据类型 D.数据项。标准答案：D3。算法的空间复杂度是对算法（）的度量.（2分）A.时间效率 。空间效率 C.可读性 D。健壮性.标准答案：B4。(）是限制了数据元素的内部结构仅为一个字符的线性表。（2分）A.栈 。队列 C。串 D.数组.标准答案：B5。串的长度是指串中所含（）的个数。（2分）不同字符 。不同字母 C。相同字符 D。所有字符。标准答案：D采用带头结点双向链表存储的线性表，在删除一个元素时，需要修改指针（2分）。2 C。3 D。4.标准答案：B线性表的顺序存储结构是一种()（2分）A。顺序存取 。随机存取 C。索引存取 D.Hash存取。标准答案:Ba［1..m]采用顺序存储,a[1］a［m]102411502字节,m是（）(2分）A。64 B.32 C。16 D。8。标准答案：A9。深度为h的二叉树，第h层最多有（）个结点。(2分）A.h 。2h—1C。2h-1 D.2h

11。下面叙述错误的是（).（2分）A.顺序表是借助物理单元相邻表示数据元素之间的逻辑关系B.对于空队列进行出队操作过程中发生下溢现象C.有向图的邻接矩阵一定是对称的D。具有相同的叶子个数和具有相同的叶子权值的赫夫曼树不是唯一的。标准答案:C12。以下与数据的存储结构无关的术语是（）.（2分）A。循环队列 。双向链表 C。哈希表 D。数组.标准答案：D13.在一个长度为n的链式栈中出栈实现算法的时间复杂度为()。(2分A。O(1) B。O(logn）C。O(n） D.O(n2)。标准答案：A14。在具有k个度数为2的二叉树中,必有()个叶子结点.（2分）A。k 。k—1 C。2k D。k+1。标准答案：D15。在关键字序列(10,20，30,40,50）中，采用折半法查找20，关键字之间比较需要（)次。（2分）A。1 。2 C.3 D.4.标准答案：C16.16abcd序列是（）（2分）A.abcd 。dcba C。acbd 。dbca.标准答案:B17。n个顶点的无向连通图的生成树，至少有（)个边。（2分）A.n(n—1) B。n（n-1）/2 C.2n D.n—1.标准答案：D18.可以采用（）这种数据结构，实现二叉树的层次遍历运算.(2分A.队列 。树 C。栈 D.集合.标准答案：A19。假设以数组A［0.。n—1］存放循环队列的元素，其头指针front指向队头元素、尾指针rear指向队尾元素一个，则在少用一个元素空间的前提下，队列空的判定条件为(）。（2分）A。rear==front B.（front+1)％n==rearC.rear+1==front D。(rear+1）％n=。标准答案:A20。序列（21，19，37，5,2)经冒泡排序法由小到大排序，第一趟后所得结果为(）.（2分）A.(19,21,37，5，2) B。（19，21，5，2，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 。{94，23，68，5,16C.{94，23，16，68,5 D.{94，16，68，23，5.标准答案：C,D24。在下列排序方法中,（）的空间复杂度为O(n）.其中，n为参加排序的元素个数。（2分）A。选择排序 B.快速排序 C。归并排序 D。冒泡排序.标准答案：B，C十字链表适合于（）选作存储结构。(2分A.队列 B.稀疏矩阵C。边或弧数较少的图 D.二叉树。标准答案：B，C基于数据的逻辑关系，数据的逻辑结构划分为()（2分）A。6类 。5类 C.4类 D.3类.标准答案:C27。（）不是算法具有的5个特性之一。（2分）

A.有穷性 B.确定性 C.可行性 D。正确性。标准答案：D28.算法的时间复杂度是对算法（）的度量。（2分）A。时间效率 B.空间效率 C。可读性 D。健壮性.标准答案：A29。线性表若采用链式存储结构时，要求结点的存储单元地址（）。（2分）A.必须是连续的 B。部分地址必须是连续C.必须是不连续的 D。连续或不连续都可以。标准答案：D30.二维数组通常采用顺序存储,其优点是(）。（2分A.便于增加存储空间 B.防止下标溢出C。避免数据元素的移动 D.便于依据下标进行随机存取。标准答案：D31ni要移动（）个元素.(2分）A.i+1 B.i C.n-i D.n—i+1.标准答案：C若已知一个栈的入栈序列是1、2、3、4，其出栈序列不可能为 。(2分)A。1、4、3、2 。3、4、1、2 C。4、3、2、1 D。2、3、4、1。标准答案：Ba［1.。256]采用顺序存储，a102a［21]的地址是（）。（2分)A.10 。30 C.50 D.70.标准答案：C深度为h的完全二叉树至少有(）个叶子结点。(2分A.（h-1)+1 。2（h-2)+1C.2h—1 D。2h-2。标准答案：D35。若二叉树对应的二叉链表共有m个非空链域,则该二叉树有（）个结点的二叉树。（2分）A。m B.m-1 C.m+1 D.2m.标准答案：B36.下面叙述错误的是（）。（2分)A。单链表是借助指针表示数据元素之间的逻辑关系B。在顺序栈的入栈操作过程中可能发生上溢现象C.具有相同的叶子个数和具有相同的叶子权值的赫夫曼树是唯一的D。无向图的邻接矩阵一定是对称的。标准答案:C37。以下（）术语与数据的存储结构无关（2分）A.栈 。哈希表 C.线索树 D.双向链表.标准答案：A38。在一个长度为n的链式队列中入队实现算法的时间复杂度为（）。（2分）A。O(1) B。O（logn）C.O（n） .标准答案:A39.队列的出队操作是指（）操作。(2分）A.队尾删除 。队头删除 C.队尾插入 D。队头插入.标准答案：B40。在关键字序列(10，15,20,25，30）中采用折半法查找25，依次与（）关键字进行了比较。（2分）A.30,25 B.20，25 C.20,30，25 D。25。标准答案：B4116abcdbcad的后序遍历序列是（)（2分）A.cbda B.dcba C.abcd D。dcba。标准答案:A42。所占用的存储空间大小仅与图的顶点个数相关的存储结构是(）.(2分A.邻接表 B.逆邻接表C。十字链表 D。邻接矩阵.标准答案：D43.可以采用（）这种数据结构,实现图的深度优先遍历运算.(2分A。队列 。树 C。栈 D。集合.标准答案：C44。线性表采用带头结点单链表实现，head为头指针,则判断表空的条件为（）。（2分）A。head==NULL 。head!=NULLC.head->next==NULL D.head—>next！=NULL。标准答案：C

45.在关键字序列（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.栈 。队列 C.串 D.二叉树。标准答案:A,B,C47。深度为3的二叉树可能的结点个数是()。（2分）A。1 。2 C.3 D。4。标准答案：A,B48.下列各项键值（）序列是大顶堆的。（2分)A.｛23，68，94，16，5 。C.{94,23，68，16,5 D.｛94，16，68，23,5.标准答案：B,C49。下列（）是限制了插入和删除操作的特殊线性表。（2分）A。栈 B.队列 C.串 D.数组.标准答案:A,B对一棵二叉排序树，用（）（2分）A.先根遍历 。中根遍历 C.后根遍历 D。层次遍历。标准答案:A,C，D数据的最小单位是（）（2分）A.数据元素 B.记录 C.数据对象 D.数据项.标准答案：D52。算法是对某一类问题求解步骤的有限序列。其中,（)是算法具有的5个特性之一。(2分)A。有穷性 B.正确性 C.可读性 D。健壮性。标准答案：A53.（)是数据的逻辑结构。（2分)A.顺序表 B.链表 C。线性表 D.十字链表。标准答案:C54。（）是限制了插入和删除操作在一端进行的线性表.（2分）A。栈 。队列 C.串 D.数组。标准答案：A（）（2分）栈 。队列 C.串 D。数组.标准答案：B用链表表示线性表的优点是（）(2分A.便于插入和删除便于随机存取C。花费的存储空间较顺序存储少D。数据元素的物理顺序与逻辑顺序相同。标准答案:A1、2、3、4,其出栈序列不可能为（)（2分）A.1、4、3、2 。2、3、4、1 C.4、3、2、1 D。3、4、1、2.标准答案：D串下列关于串的叙述中，正确的是（).(2分A。22个串相等。空串至少包一个空格CD.1.标准答案:C59。深度为h的二叉树,第h层至少有（）个结点.（2分）A。0 B.1 C。8 D.16。标准答案：B60。假设n≥0，在程序段｛y=0；while(（y+1)＊（y+1)A。n B。［］C.n2.标准答案：C61。下面叙述错误的是（）.（2分)A。在集合{1，2，3，4，512。二叉排序树的中序遍历序列一定是有序的C。有3个结点的不同形态二叉树的数目为5D.哈夫曼树中所有结点的孩子数目只可能为2或者为0.标准答案：A62。以下数据结构中,（）是线性结构。（2分）广义表 。二叉树 C.稀疏矩阵 D.串

。标准答案：D63。在一个长度为n的顺序表中删除一个元素的算法的时间复杂度为（)。（2分A.O（1) B.O（logn)C.O(n） D.O（n2).标准答案：C如果一个huffman树含有n个叶子，则该树必有(）的结点。(2分A。n+1 B.2n+1 C.2n D.2n-1.标准答案：D在关键字序列（10,15,20,25,30）25，关键字之间比较需要（）次。（2分）。2 C。3 D.4.标准答案：B66。16某二叉树的前序遍历序列和和中序遍历序列均为abcd，该二叉树的后序遍历序列是(）。（2分）A。abcd B.dcba C.acbd D.dbca。标准答案：Bm个顶点的有向完全图有（)（2分）A。m(m-1）/2 B。m+1 C。m D.m（m-1)。标准答案：D下列各项键值（)（2分)A。{94，68，23，16，5 。｛94，23，68，5，16C.｛94，23，68，16，5 D.{94，16，68，23，5.标准答案：DpA，q指向新元素结点,A素，则所需修改指针的操作为（).（2分)A.p—>next=q,q—>next=p->next。q—〉next=p->next,p—>next=qC。p-〉next=q->next，q—〉D.p-〉next=p,q-〉next=p->next。标准答案：B70。在关键字序列（149，138，165，197，176，113,127）中采用最低位优先排序（LSD）基数排序，第一趟之后所得结果为（）。（2分）A。149,138,165，197,176，113,127。128,149，165，197,113,176，127C.128，149,165，197,113，127,176D.113，127，138，149，165，176，197。标准答案：B71。下列术语表示的数据中，（）是同义语。（2分）A.结点 。数据元素 C.顶点 D。数据项.标准答案：A，B,C72.对于采用链式结构的队列，（）运算的实现算法的时间复杂度为O(1)。(2分A。