《数据结构》期末复习题-答案

《《数据结构》期末复习题-答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1.以下与数据的存储结构无关的术语是（c）C、哈希表2.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（B）B、1083.假设带头结点的单向循环链表的头指针为head,则该链表为空的判定条件是（C）C、head–>next==head4.若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是（D）D、2，3，5，1，6，45.下列关键字序列中，构成小根堆的是（A）A、{12，21，49，33，81，56，69，41}6.下列数据结构中，不属于二叉树的是（A）A、B树7.用顺序存储的方法来存储一棵二叉树，存放在一

2、维数组A[1..N]中，若结点A[i]有右孩子，则其右孩子是（C）。C、A[2i+1]8.设树T的高度为4，其中度为1、2、3、4的结点个数分别为4、2、1、1，则T中叶子数为（D）D、89.有数据{53，30，37，12，45，24，96}，从空二叉树开始逐个插入数据来形成二叉排序树，若希望高度最小，则应选择下面哪个序列输入（B）B、37，24，12，30，53，45，9610.对下面有向图给出了四种可能的拓扑序列，其中错误的是（C）C、5，1，6，3，4，211.m阶B-树中所有非终端（除根之外）结点中的关键字个数必须大于或等于(B)B、[m/2]-112.散列文件也称

3、为(C)B、索引文件13.数据结构是（D）D、相互之间存在一种或多种特定关系的数据元素的集合14.从逻辑关系来看，数据元素的直接前驱为0个或1个的数据结构只能是（C）C、线性结构和树型结构15.设p为指向双向循环链表中某个结点的指针，p所指向的结点的两个链域分别用p→llink和p→17rlink表示，则同样表示p指针所指向结点的表达式是（D）D、p→llink→rlink1.若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈(i=1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（B）B、top[1]+1=top[2]2.若

4、一棵二叉树有11个叶子结点，则该二叉树中度为2的结点个数是（A）A、103.树的先根序列等同于与该树对应的二叉树的（A）A、先序序列4.下面关于哈希(Hash，杂凑)查找的说法正确的是(C)C、不存在特别好与坏的哈希函数，要视情况而定5.下列序列中，（D）是执行第一趟快速排序后所得的序列。D、[68，11，69，23，18][93，73]6.下列关键字序列中，构成小根堆的是(D)D、(15，28，46，37，84，58，62，41)7.ISAM文件和VASM文件属于(C)C、索引顺序文件8.下面程序段的时间复杂度为（C）for(i=0;i

5、;j++)A[i][j]=i*j;C、O(m*n)9.已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为（A）A、q->next=s->next；s->next=p；10.为便于判别有向图中是否存在回路，可借助于（D）D、拓扑排序算法11.若以S和X分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列是（D）D、SSSXXSXX12.17设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1,则栈的容量至少

6、应该是(B)B、31.假设以数组A[m]存放循环队列的元素。已知队列的长度为length，指针rear指向队尾元素的下一个存储位置，则队头元素所在的存储位置为（B）。B、(rear-length+m)%m2.在一个链队列中，front和rear分别为头指针和尾指针，则插入一个结点s的操作为（D）。D、rear->next=s;rear=s;3.对于哈希函数H(key)=key%13,被称为同义词的关键字是（D）D、25和514.采用二叉链表存储的n个结点的二叉树，共有空指针（A）个。A、n+15.连通网的最小生成树是其所有生成树中（D）D、边的权值之和最小的生成树6.对记录

7、序列(314，298，508，123，486，145)依次按个位和十位进行两趟基数排序之后所得结果为（B）B、508，314，123，145，486，2987.任何一个无向连通图的最小生成树(C)。C、一棵或多棵8.无向图的邻接矩阵是一个(C)C、对称矩阵9.设无向图G-=(V,E)和G’=(V’,E’),如G’为G的生成树，则下列说法中不正确的是(B)。B、G’为G连通分量10.以v1为起始结点对下图进行深度优先遍历，正确的遍历序列是（D）D、v1，v2，v5，v6，v7，v3，v411.下面几个符号串编码集合中