数据结构期末考试模拟题Word文档格式.docx

1、hs=s; D. s-next=hs; hs=hs- 11.在一个链队列中，假定front和rear分别为队首指针和队尾指针，则进行插入*s结点的操作时应执行 。 A. front- front=s; B. rear- rear=s; C. front=front- D. front=rear- 12.线性表是 。 A. 一个有限序列，可以为空 B. 一个有限序列，不能为空 C. 一个无限序列，可以为空 D. 一个无限序列，不能为空 13.对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的， 删除一个元素时大约要移动表中的 个元素。 A. n+1 B. n-1 C. （n

2、-1）/2 D. n 14.线性表采用链式存储时，其地址 。 A. 必须是连续的 B. 部分地址必须是连续的 C. 一定是不连续的 D. 连续与否均可以 14.根据线性表的链式存储结构，每个结点所含指针的个数，链表分为单链表和 。 A. 循环链表 B. 多重链表 C. 普通链表 D. 无头结点链表15. 下列函数中渐进时间复杂度最小的是 。A. T1（n）=nlog2n5000n B. T3（n）=nlog2n6000nC. T2（n）=n28000n D. T4（n）=2log2n7000n 16.在数据结构中，与所使用的计算机无关的数据叫 结构。 A. 存储 B. 物理 C. 逻辑 D.

3、物理和存储 17.在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上 。 A. 一定相邻 B. 不一定相邻 C. 有时相邻 18.假定在一棵二叉树中，双分支结点数为15个，单分支结点数为32个，则叶子结点 数为 。 A. 15 B. 16 C. 17 D. 47 19.假定一棵二叉树的结点数为18个，则它的最小高度 。 A. 4 B. 5 C. 6 D. 18 20.在一棵二叉树中第五层上的结点数最多为 。 A. 8 B. 15 C. 16 D. 32 21.在一棵具有五层的满二叉树中，结点总数为 。 A. 31 B. 32 C. 33 D. 16 22.由权值分别为3,8,6,2,5的叶

4、子结点生成一棵哈夫曼树，它的带权路径长度为_。 A 24 B 48 C 72 D 53 23. 已知8个数据元素为（34、76、45、18、26、54、92、65），按照依次插入结点的方法生成一棵二叉排序树后，最后两层上的结点总数为 。 A. 1 B. 2 C. 3 D. 4 24.在树中除根结点外，其余结点分成m （m0）个 的集合T1,T2,T3.Tm,每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点（1im）。 A. 互不相交 B. 可以相交 C. 叶结点可以相交 D. 树枝结点可以相交 25.下面答案 是查找二叉树（又称二叉排序树）。 A. 二叉树中的每个结点的两棵子树

5、的高度差的绝对值不大于 B. 二叉树中的每个结点的两棵子树的高度差等于 C. 二叉树中的每个结点的两棵子树是有序的 D. 二叉树中的每个结点的关键字大于其左子树（如果存在）所有结点的关键字值， 且小于其右子树（如果存在）所有结点的关键字值。 26. 将含100个结点的完全二叉树从根这一层开始，每层从左至右依次对结点编号，根结点的编号为1。编号为49的结点X的双亲的编号为 。 A. 23 B. 24 C. 25 D. 2无法确定 27.在完全二叉树中，当i为奇数且不等于时，结点i的左兄弟是结点 ，否则没有左兄弟。 A. 2i-1 B. i+1 C. 2i+1 D. i-1 28.某二叉树T有n个

6、结点，设按某种遍历顺序对T中的每个结点进行编号，编号值为1,2,n且有如下性质：T中任一结点V，其编号等于左子树上的最小编号减1，而V的右子树 的结点中，其最小编号等于V左子树上结点的最大编号加1。这时按 编号。 A. 中序遍历序列 B. 前序遍历序列 C. 后序遍历序列 D. 层次遍历序列 29.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍。 A. 1/2 B. 1 C. 2 D. 4 30.对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小 为 。 A. n B. n+1 C. n-1 D. n+e 31.具有n个顶点的无向完全图，边的总数为 条。

7、A. n-1 B. n C. n+1 D. n*（n-1）/2 32.设图G有n个顶点和e条边，当G是非孤立顶点的连通图时有2e=n,故可推得深度优先搜索的时间复杂度为 。 A. O（e） B. O（n） C. O（ne） D. O（n+e）33. 由分别带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为 。 A. 23 B. 37 C. 44 D. 46 34.在无向图G的邻接矩阵A中，若Ai,j等于1，则Aj,i等于 。 A. i+j B. i-j C. 1 D. 0 35.图的深度优先或广度优先遍历的空间复杂性均为 。（访问标志位数组空间） A. O（n） B. O

8、（e） C. O（n-e） D. O（n+e） 36.二分法查找 存储结构。 A. 只适用于顺序 B. 只适用于链式 C. 既适用于顺序也适用于链式 D. 既不适合于顺序也不适合于链式37.已知一个有序表为（12、18、24、35、47、50、62、83、90、115、134），当二分查找值为90的元素时， 次比较后查找成功；当二分查找值为47的元素时， D 次比较后查找成功。 38.散列函数有一个共同性质，即函数值应当以 取其值域的每个值。 A. 最大概率 B. 最小概率 C. 平均概率 D. 同等概率39用线性探测法查找闭散列上，可能要探测多个散列地址，这些位置上的键值 。A.一定都是同义

9、词 B. 一定都不是同义词 C.相同 D. 不一定都是同义词 40.设散列地址空间为0m1,k为关键字，用p去除k，将所得的余数作为k的散列地址，即H（k）k % p。为了减少发生冲突的频率，一般取p为 。 A. 小于m的最大奇数 B. 小于m的最大偶数 C. m D. 小于m的最大素数41.现在A、B、C、D四个元素相继进行入栈操作，下面不可能得到的入栈序列为： A. ABCD B. BDAC C. CBDA D. DCBA二、判断题 1数据元素是数据的最小单位（ ）。 2数据项是数据的基本单位（ ）。 3顺序存储的线性表可以随机存取（ ）。 4线性表中的元素可以是各种各样的，但同一线性表中

10、的数据元素具有相同的特性， 因此，是属于同一数据对象（ ）。 5在单链表中，任何两个元素的存储位置之间都有固定的联系，因为可以从头结点查找任何一个元素（ ）。 6在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构（ ）。 7链表的每个结点中，都恰好包含一个指针（ ）。 8.中序遍历二叉排序树的结点不能得到排好序的结点序列。（ ）9.完全二叉树一定是满二叉树。10.满二叉树一定是完全二叉树。11由二叉树的前序和中序遍历序列可以推导出此二叉树的后序遍历序列。 12.由树转换成二叉树，其根结点的右子树总是空的（ ）。 13.后序遍历树和中序遍历与该树对应的二叉树，

11、其结果不同（ ）。 14.若有一个结点是某二叉树子树的中序遍历序列中的最后一个结点，则它必是该子 树的前序遍历序列中的最后一个结点（ ）。 15.若一个树叶是某子树的中序遍历序列中的最后一个结点，则它必是该子树的前序 遍历序列中的最后一个结点（ ）。 16.已知二叉树的前序遍历和后序遍历序列并不能唯一地确定这棵树，因为不知道树 的根结点是哪一个（ ）。 17.在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应作特殊处理（ ）。 18.有回路的图不能进行拓扑排序（ ）。 19.连通分量是无向图中的极小连通子图（ ）。 /极大/ 20.散列法存储的基本思想是由关键码的值决定数

12、据的存储地址（ ）。 21.散列表的查找效率取决于散列表造表时选取的散列函数和处理冲突的方法（ ）。 22.中序遍历二叉排序树的结点就可以得到排好序的结点序列（ ）。 23.在二叉排序树上插入新的结点时，不必移动其它结点，仅需改动某个结点的指针， 由空变为非空即可（ ）。24.线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。25. 算法就是程序。第1章作业题设 n 为正整数。试确定下列各程序段中前置以记号的语句的频度和时间复杂度：（1） i = 1; k = 0;While （i=n - 1） k + = 10 * I ; i +; （2） i = 1;do （i while

13、（I = n - 1）;（3） i = 1; k + = 10 * i ;（4） k = 0;for （ i = 1;i=n ;i+） for （ j = i;jj+） k + +;（5） for （ i = 1;j+） for （ k = 1;knext） Q =L; L =L- P =L ;while （ P-next） P =P-next ;P-next =Q; Q-next = NULL; / A（2） void BB（LNode *s, LNode *q ） p =s ;while （p-next!=q） p =p-p-next =s; /BBvoid AA（LNode *pa, L

14、Node *pb） / pa 和 pb 分别指向单循环链表中的两个结点BB（pa, pb）;BB（pb, pa）; /AA2.2 已知L是无表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。a 在P结点后插入S结点的语句序列-。b 在P结点前插入S结点的语句序列-。c 在表首插入S结点的语句序列-。d 在表尾插入S结点的语句序列-。（1） P-next=S;（2） P-next=P-next-（3） P-next=S-（4） S-（5） S-next=L；（6） S-next=NULL；（7） Q=P；（8） while （P-=Q） P=P

15、-（9） while （P-=NULL） P=P-（10） P=Q;（11） P=L;（12） L=S;（13） L=P；2.3 已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。e 删除P结点的直接后继结点的语句序列-。f 删除P结点的直接前驱结点的语句序列-。g 删除P结点的语句序列-。h 删除首元结点的语句序列-。i 删除尾元结点结点的语句序列-。（1） P=P-next=P;next=P -（4） P=P -（5） while （P!（6） while （Q-=NULL）P=Q;Q=Q-（7） while （P-next !

16、（10） Q=P;（11） Q=P-（12） P=L;（13） L=L-（14） free（Q）;【编程练习题】2.4 设顺序表 a 中的数据元素递增有序。试写一算法，将 x 插入到顺序表的适当位置上，以保持该表的有序性。2.5 试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表（a1,a2,an） 逆置为（an, an-1, a1）。2.6 试写一算法，对单链表实现就地逆置。 2.7编写算法删除顺序表中多余的数据元素，即使操作之后的顺序表中所有元素的值都不相第3章本章练习题中可以利用的栈和队列的类型定义如下：/ stack 类型void InitStack（ stack& s ）

17、; / 初始化 s 为空栈void Push（ stack&s , char x）; / 将元素 x 插入 s 的栈顶void Pop（ stack& / 删除 s 中的栈顶元素bool StackEmpty（ stack& s）; / 若栈 s 为空则返回 TRUE,否则返回 FALSEchar GetTop（ stack&/ 返回 s 中的栈顶元素void ClearStack（ stack& / 将栈 s 清空int StackLength（ stack& / 返回栈 s 中元素个数void DestroyStack（ stack&/ 销毁栈 s 结构/ queue 类型void Ini

18、tQueue（ queue& q ）;/ 初始化 q 为空栈void EnQueue（ queue& q , char x ）;/ 将元素 x 插入 q 的队尾void Dequeue（ queue& q）; / 删除 q 中队头元素char GetHead（ queue&/ 返回 q 中队头元素bool QueueEmpty（ queue& / 若队列 q 为空则返回 TRUE,否则返回 FALSEvoid ClearQueue（ queue& / 将队列 q 清空int QueueLength（ queue& / 返回队列 q 中元素个数void DestroyQueue（ queue&

19、/ 销毁队列 q 结构3.1（1） 设S1.max为顺序存储的栈，变量top指示栈顶的位置，栈为空的条件是_,栈为满的条件是_。（2） 一个栈的入栈序列是a, b, c, d, e,，则栈的不可能序列是： （A） edcba （B） decba （C） dceab （D） abcde（3） 设循环队列中数组下标的范围是1-n，其头尾指针分别为f和r，则其元素的个数为（ ） （a） r-f （b） r-f+1 （c） （r-f）mod n +1 （d） （r-f+n）mod n （4） 若一个最大长度为 M 的循环队列的队首和队尾指针用front 和rear 表示，则判别队为满的条件是:（A）（

20、rear-1）%M = front （B） （ rear+1）%M = front（C） rear= （front-1）%M （D） rear= （front+1）%M标识的循环队列，若队列不满3.2写出下列程序段的输出结果（栈的元素类型 SElemType 为 char）。void main（ ）Stack S;char x, y;InitStack（S）;x=c; y=kPush（S, x）; Push（S, a）; Push（S, y）;Pop（S, x）;t Push（S, x）;swhile （!StackEmpty（S） Pop（S, y）; printf（y）; ;printf（

21、x）;3.3 简述以下算法的功能（栈的元素类型 SElemType 为 int ）。（1） status algo1（Stack S） int i, n, A 255;n=0;while （!StackEmpty（S） ） n+; Pop（S, An）;for （ i=1; i= n ; i+） Push（S, Ai）;（2） status algo2（Stack S, int e） Stack T; int d;InitStack（T）;StackEmpty（S） Pop（S, d）;if （d!=e ） Push（T, d）; StackEmpty（T） Pop（T, d）;Push（S,

22、 d）;3.4简述以下算法的功能（栈和队列的元素类型均为 int）。void algo3（Queue &Q） InitStack （S）;QueueEmpty（Q） DeQueue（Q, d）; Push（S, d）;StackEmpty（S） Pop（S, d）; EnQueue（Q, d）; 3.5. 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。第6章6. 1. 高度为h的完全二叉树至少有多少个结点?至多有多少个结点?6.2 如果一棵树有n1个度为1的结点, 有n2个度为2的结点, , nm个度为m的结点, 试问有多少个度为0的结点? 试推导之。6.3由如图6.2所示的二叉树，回答以下问题： 其中序遍历序列为_； 其前序遍历序列为_； 其后序遍历序列为_；6.4将如图6.3所示的一个普通树转换成一棵二叉树，并写出它先序、中序、后序三种遍历的遍历序列。