专升本《数据结构》模拟题试卷

专升本《数据结构》模拟题试卷一.（共75题,共150分）数据的基本单位是（）。（2分）数据元素记录数据对象数据项★检查答案标准答案：A（）是数据的不可分割的最小单位。（2分）数据对象数据元素数据类型数据项★检查答案标准答案：D算法的空间复杂度是对算法（）的度量。（2分）时间效率空间效率可读性健壮性★检查答案标准答案：B（）是限制了数据元素的内部结构仅为一个字符的线性表。（2分）栈队列串数组★检查答案标准答案：B串的长度是指串中所含（）的个数。（2分）不同字符不同字母相同字符所有字符★检查答案标准答案：D采用带头结点双向链表存储的线性表，在删除一个元素时，需要修改指针（）次。（2分）1234★检查答案标准答案：B线性表的顺序存储结构是一种（）的存储结构。（2分）顺序存取随机存取索引存取Hash存取★检查答案标准答案：B8.数组a[l..m]采用顺序存储，a⑴和a[m]地址分别为1024和1150,每个元素占2字节，则m是（）。（2分）TOC\o"1-5"\h\z6432168★检查答案标准答案：A深度为h的二叉树，第h层最多有（）个结点。（2分）h2h-12h-12h★检查答案标准答案：Cm个结点的二叉树，其对应的二叉链表共有（）个非空链域。（2分）mm+12mm-1★检查答案标准答案：B下面叙述错误的是（）。（2分）顺序表是借助物理单元相邻表示数据元素之间的逻辑关系对于空队列进行出队操作过程中发生下溢现象有向图的邻接矩阵一定是对称的具有相同的叶子个数和具有相同的叶子权值的赫夫曼树不是唯一的★检查答案标准答案：C以下与数据的存储结构无关的术语是（）。（2分）循环队列双向链表哈希表数组★检查答案标准答案：D在一个长度为n的链式栈中出栈实现算法的时间复杂度为（）。（2分）TOC\o"1-5"\h\zO（1）O（logn）\o"CurrentDocument"O（n）O（n2）★检查答案标准答案：A在具有k个度数为2的二叉树中，必有（）个叶子结点。（2分）kk-12kk+1★检查答案标准答案：D15.在关键字序列（10,20,30,40,50）中，采用折半法查找20，关键字之间比较需要（）次。（2分）1234★检查答案标准答案：C16某二叉树的后序遍历序列和和中序遍历序列均为abed，该二叉树的前序遍历序列是（）。 （2分）abeddebaaebddbea★检查答案标准答案：Bn个顶点的无向连通图的生成树，至少有（）个边。（2分）n（n-1）n（n-1）/2TOC\o"1-5"\h\z2nn-1★检查答案标准答案：D可以采用（）这种数据结构，实现二叉树的层次遍历运算。（2分）队列树栈集合★检查答案标准答案：A假设以数组A[O..n-1]存放循环队列的元素，其头指针front指向队头元素、尾指针rear指向队尾元素一个，则在少用一个元素空间的前提下，队列空的判定条件为（）。（2分）rear==front（front+1）％n==rearrear+1==front（rear+1）％n==front★检查答案标准答案：A序列（21，19，37，5，2）经冒泡排序法由小到大排序，第一趟后所得结果为（）。 （2分）（19，21，37，5，2）（19，21，5，2，37）（19，21，5，37，2）（19，21，2，5，37）★检查答案标准答案：B二叉链表适合作为（）的存储结构。 （2分）队列二叉树树森林★检查答案标准答案：B,C,D22.设哈希(Hash)函数为H(k)=k%17,其中k为关键字，关键字()是同义词。(2分)44,5,1528,45,626,57,125201,31,48★检查答案标准答案：B,C,D下列各项键值()序列不是堆的。(2分)A.{94，68，23，16，5B.{94，23，68，5，16C.{94，23，16，68，5D.{94，16，68，23，5★检查答案标准答案：C,D在下列排序方法中，()的空间复杂度为O(n)。其中，n为参加排序的元素个数。(2分)选择排序快速排序归并排序冒泡排序★检查答案标准答案：B,C十字链表适合于()选作存储结构。(2分)队列稀疏矩阵边或弧数较少的图二叉树★检查答案标准答案：B,C基于数据的逻辑关系，数据的逻辑结构划分为()基本结构。(2分)TOC\o"1-5"\h\z6类5类4类3类★检查答案标准答案：C()不是算法具有的5个特性之一。 (2分)A.有穷性

确定性可行性正确性★检查答案标准答案：D算法的时间复杂度是对算法（）的度量。（2分）时间效率空间效率可读性健壮性★检查答案标准答案：A线性表若采用链式存储结构时，要求结点的存储单元地址（）。（2分）必须是连续的部分地址必须是连续的必须是不连续的连续或不连续都可以★检查答案标准答案：D二维数组通常采用顺序存储，其优点是（）。（2分）便于增加存储空间防止下标溢出避免数据元素的移动便于依据下标进行随机存取★检查答案标准答案：D需要移动（）2分）采用顺序存储的线性表，若表长为n在第i号元素之后插入一个元素时,个元素。（2需要移动（）2分）TOC\o"1-5"\h\zi+1in-in-i+1★检查答案标准答案：C若已知一个栈的入栈序列是1、2、3、4，其出栈序列不可能为 1、4、3、23、4、1、24、3、2、12、3、4、1★检查答案标准答案：B33.数组a[1..256]采用顺序存储，a的首地址为10,每个元素占2字节，则a[21啲地址是（）。（2分）10TOC\o"1-5"\h\z305070★检查答案标准答案：C深度为h的完全二叉树至少有（）个叶子结点。（2分）2（h-1）+12（h-2）+1TOC\o"1-5"\h\z2h-12h-2★检查答案标准答案：D若二叉树对应的二叉链表共有m个非空链域，则该二叉树有（）个结点的二叉树。（2分）mm-1m+12m★检查答案标准答案：B下面叙述错误的是（）。 （2分）单链表是借助指针表示数据元素之间的逻辑关系在顺序栈的入栈操作过程中可能发生上溢现象具有相同的叶子个数和具有相同的叶子权值的赫夫曼树是唯一的无向图的邻接矩阵一定是对称的★检查答案标准答案：C以下（）术语与数据的存储结构无关（2分）栈哈希表线索树双向链表在一个长度为n的链式队列中入队实现算法的时间复杂度为()。(2分)O(1)O(logn)O(n)O(n2)★检查答案标准答案：A队列的出队操作是指()操作。(2分)队尾删除队头删除队尾插入队头插入★检查答案标准答案：B40.在关键字序列(10,15,20,25,30)中采用折半法查找25，依次与()关键字进行了比较。(2分)TOC\o"1-5"\h\z30,2520,2520，30，25\o"CurrentDocument"25★检查答案标准答案：B16某二叉树的前序遍历序列和和中序遍历序列分别为abed和bead，该二叉树的后序遍历序列是()。(2分)ebdadebaabeddeba★检查答案标准答案：A所占用的存储空间大小仅与图的顶点个数相关的存储结构是()。 (2分)邻接表逆邻接表十字链表邻接矩阵★检查答案标准答案：D可以采用()这种数据结构，实现图的深度优先遍历运算。(2分)队列树栈集合★检查答案标准答案：C线性表采用带头结点单链表实现，head为头指针，则判断表空的条件为（）。（2分）head==NULLhead!=NULLhead->next==NULLhead->next!=NULL★检查答案标准答案：C45.在关键字序列（35,10,15,20，25）中采用最低位优先排序（LSD）基数排序，第一趟之后所得结果为()。25，(2分)35A.10，20，15，B.10，20，35，15，25C.20，10，35，25，15D.20，10，35，15，25★检查答案标准答案：BTOC\o"1-5"\h\z下列逻辑结构中，（）为线性结构。 （2分）栈队列串二叉树★检查答案标准答案：A,B,C深度为3的二叉树可能的结点个数是（）。 （2分）1234★检查答案标准答案：A,B下列各项键值（）序列是大顶堆的。（2分）{23，68，94，16，5{94，68，23，16，5{94，23，68，16，5D.{94，16，68，23，5★检查答案标准答案：B,C下列（）是限制了插入和删除操作的特殊线性表。（2分）栈队列串数组★检查答案标准答案：A,B对一棵二叉排序树，用（）方法进行遍历，不一定得到各结点键值的有序序列。（2分）先根遍历中根遍历后根遍历层次遍历★检查答案标准答案：A,C,D数据的最小单位是（）。（2分）数据元素记录数据对象数据项★检查答案标准答案：D算法是对某一类问题求解步骤的有限序列。其中，（）是算法具有的5个特性之一。（2分）有穷性正确性可读性健壮性★检查答案标准答案：A（）是数据的逻辑结构。（2分）顺序表链表线性表十字链表（）是限制了插入和删除操作在一端进行的线性表。（2分）TOC\o"1-5"\h\z栈队列串数组★检查答案标准答案：A（）是限制了插入和删除操作分别在两端进行的线性表。（2分）栈队列串数组★检查答案标准答案：B用链表表示线性表的优点是（）。（2分）便于插入和删除便于随机存取花费的存储空间较顺序存储少数据元素的物理顺序与逻辑顺序相同★检查答案标准答案：A2分）若已知一个栈的入栈序列是1、2、3、42分）1、4、3、22、3、4、14、3、2、13、4、1、2★检查答案标准答案：D串下列关于串的叙述中，正确的是（）。（2分）2个串的长度相等，则2个串相等空串至少包一个空格替换操作可以实现字符的删除—个串的长度至少是1★检查答案标准答案：C深度为h的二叉树，第h层至少有（）个结点。（2分）01816★检查答案标准答案：B60.假设n三0,在程序段｛y=O;while（（y+l）*（y+l）v=n）@y++;中，标记@的语句实际执行的次数是（）。其中，[x]表示对x取整运算。（2分）n[]n2★检查答案标准答案：C6l. 下面叙述错误的是（）。（2分）在集合｛1，2，3，4，5中元素1是2的直接前驱二叉排序树的中序遍历序列一定是有序的有3个结点的不同形态二叉树的数目为5哈夫曼树中所有结点的孩子数目只可能为2或者为0★检查答案标准答案：A以下数据结构中，（）是线性结构。（2分）广义表二叉树稀疏矩阵TOC\o"1-5"\h\z串★检查答案标准答案：D在一个长度为n的顺序表中删除一个元素的算法的时间复杂度为（）。（2分）O（1）O（logn）\o"CurrentDocument"O（n）O（n2）★检查答案标准答案：C如果一个huffman树含有n个叶子，则该树必有（）的结点。（2分）n+12n+12n2n-165.在关键字序列（10,15,20,25,30）中，采用折半法查找25，关键字之间比较需要（）次。（2分）1234★检查答案标准答案：B16某二叉树的前序遍历序列和和中序遍历序列均为abed，该二叉树的后序遍历序列是（）。（2分）abeddebaaebddbea★检查答案标准答案：Bm个顶点的有向完全图有（）个弧。（2分）m（m-1）/2m+1mm（m-1）★检查答案标准答案：D下列各项键值（）序列不是堆的。（2分）A.{94，68，23，16，5{94，23，68，5，16{94，23，68，16，5D.{94，16，68，23，5★检查答案标准答案：D设单链表中指针p指向结点A，q指向新元素结点，若要A之后插入一个新元素，则所需修改指针的操作为（）。（2分）p->next=q，q->next=p->nextq->next=p->next，p->next=qp->next=q->next，q->next=pp->next=p，q->next=p->next70.在关键字序列（149，138，165，197，176，113，127）中采用最低位优先排序（LSD）基数排序，第一趟之后所得结果为（）。（2分）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★检查答案标准答案：B下列术语表示的数据中，（）是同义语。（2分）结点数据元素顶点数据项★检查答案标准