最新《数据结构与算法》(张晓莉)习题.doc

《最新《数据结构与算法》(张晓莉)习题.doc》由会员分享，可在线阅读，更多相关《最新《数据结构与算法》(张晓莉)习题.doc（46页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date数据结构与算法(张晓莉)习题1第一章 绪论1. 从逻辑上可以把数据结构分为（ ）两大类。A动态结构、静态结构 B顺序结构、链式结构C线性结构、非线性结构 D初等结构、构造型结构2. 在下面的程序段中，对x的赋值语句的频度为（ ）。For（k=1；k=n；k+） For（j=1；jnext=s；s-next=p-next；Bs-next=p-next；p-next=s；

2、Cp-next=s；p-next=s-next；Dp-next=s-next；p-next=s；9在双向链表存储结构中，删除p所指的结点时须修改指针（ ）。A（p- prior)- next = p-next ; （p-next）-prior =p- prior ;Bp- prior=（p- prior）- prior ; （p- prior）- next =p ;C（p-next）-prior =p ; p-rlink=（p- next）- next ;Dp-next =（p- prior）- prior ; p- prior =（p- next）- next10. 完成在双向循环链表结点p

3、之后插入s的操作是（ ）。Ap-next =s; s- prior =p; p- next- prior =s; s- next =p- next;Bp-next- prior =s; p- next =s; s- prior =p; s- next =p- next;Cs- prior =p; s- next = p-next; p- next =s; p- next- prior =s;Ds- prior =p; s- next = p-next; p- next- prior =s;p- next =s; 11. 若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（

4、）存储方式最节省运算时间。A单链表 B顺序表 C双向链表 D单循环链表12. 若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。A单链表 B仅有头指针的单循环链表 C双向链表 D仅有尾指针的单循环链表第三章 栈和队列1向一个栈顶指针为top的链栈中插入一个p所指结点时，其操作步骤为（ ）。Atop-next=p； Bp-next=top-next；top-next=p；Cp-next=top；top=p； Dp-next=top；top=top-next；2对于栈操作数据的原则是（ ）。A先进先出 B后进先出C后进后出 D不分顺序3若

5、已知一个栈的入栈序列是1，2，3，n，其输出序列为p1，p2，p3，pn，若pn 是n，则Pi为（ ）。Ai Bni Cnil D不确定4表达式a *（bc）d的后缀表达式是（ ）。Aabcd* Babc*dCabc*d D*abcd5采用顺序存储的两个栈的共享空间S1.m，用topi代表第i个栈（i=1，2）的栈顶，栈1的底在S1，栈2的底在Sm，则栈满的条件是（ ）。Atop2top1=0 Btop11= top2Ctop1top2 =m Dtop1= top26一个栈的入栈序列是a，b，c，d，e，则栈的不可能的输出序列是（ ）。Aedcba Bdecba Cdceab Dabcde7在

6、一个链队列中，若f、r分别为队首、队尾指针，则插入p所指结点的操作为（ ）。Af-next=p；f=p Br-next=p；r=pCp-next=r；r=p Dp-next=f；f=p8用不带头结点的单链表存储队列时，在进行删除运算时（ ）。A仅修改头指针 B仅修改尾指针C头、尾指针都要修改 D头、尾指针可能都要修改9. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（ ）的数据结构。A队列 B静态链表 C栈 D顺序表10. 栈和队都是（ ）。A顺序存储的线性结构 B链式存储的非线性结构C限制存取点的线性结构 D限制存取点的非线性结构第四章 字符串及线性结构的扩展1. 下面关于串的叙述

7、，错误的是（ ）。A串是字符的有限序列B串既可以采用顺序存储，也可以采用链式存储C空串是由空格构成的串D模式匹配是串的一种重要运算2. 串的长度是指（ ）。A串中所含不同字母的个数 B串中所含字符的个数C串中所含不同字符的个数 D串中所含非空格字符的个数3.4. 二维数组M的成员是6个字符（每个字符占一个存储单元，即一个字节）组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要（1）（ ）个字节；M的第8列和第5行共占（2）（ ）个字节；若M按行优先方式存储，元素M85的起始地址与当M按列优先方式存储时的（3）（ ）元素的起始地址一致。（1）A. 90 B. 180 C

8、. 240 D. 540（2）A. 108 B. 114 C. 54 D. 60（3）A. M85 B. M310 C. M58 D. M095. 数组A中，每个元素的存储占3个单元，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元个数是（1）（ ）；若该数组按行存放，元素A85的起始地址为（2）（ ）；若该数组按列存放，元素A85的起始地址为（3）（ ）。（1）A. 80 B. 100 C.240 D. 270（2）A. SA+141 B. SA+144 C. SA+222 D. SA+225（3）A. SA+141 B. SA+180 C.

9、 SA+117 D. SA+2256. 稀疏矩阵采用压缩存储，一般有（ ）两种方法。A二维数组和三维数组 B三元组和散列C三元组表和十字链表 D散列和十字链表第五章 树结构1. 下列说法正确的是（ ）。A二叉树中任何一个结点的度都为2 B二叉树的度为2C一棵二叉树的度可小于2 D任何一棵二叉树中至少有一个结点的度为22. 以二叉链表作为二叉树的存储结构，在具有n个结点的二叉链表中（n0），空链域的个数为（ ）。A2n1 Bn1 Cnl D2nl3. 线索化二叉树中，某结点*p没有孩子的充要条件是（ ）。A. p-lchild=NULL B. p-ltag=1且p-rtag=1C. p-ltag

10、=0 D. p-lchild=NULL且p-ltag=14. 如果结点A有3个兄弟，而且B是A的双亲，则B的度是（ ）。A3 B4 C5 D15. 某二叉树T有n个结点，设按某种顺序对T中的每个结点进行编号，编号值为1，2，n，且有如下性质：T中任意结点v，其编号等于左子树上的最小编号减1，而v的右子树的结点中，其最小编号等于v左子树上结点的最大编号加1，这是按（ ）编号的。A. 中序遍历序列 B. 先序遍历序列 C. 后序遍历序列 D. 层次顺序6. 设F是一个森林，B是由F转换得到的二叉树，F中有n个非终端结点，B中右指针域为空的结点有（ ）个。An1 Bn Cnl Dn27. 一棵完全二

11、叉树上有1001个结点，其中叶子结点的个数是（ ）。A500 B501 C490 D4958. 设森林F中有3棵树，第1、第2和第3棵树的结点个数分别为N1，N2和N3。与森林F对应的二叉树根结点的右子树上的结点个数是（ ）。AN1 BN1N2 CN2 DN2N39. 任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（ ）。A. 不发生改变 B. 发生改变 C. 不能确定 D. 以上都不对10. 若一棵二叉树的后序遍历序列为dabec，中序遍历序列为debac，则先序遍历序列为（ ）。A. cbed B. decab C. deabc D. cedba11. 若一棵二叉树的先序遍历

12、序列为abdgcefh，中序遍历的序列为dgbaechf，则后序遍历的结果为（ ）。A. gcefha B. gdbecfha C. bdgaechf D. gdbehfca12. 一棵非空二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ ）。A. 所有的结点均无左孩子 B. 所有的结点均无右孩子C. 只有一个叶子结点 D. 是一棵满二叉树13. 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（ ）。A. 2h B. 2h1 C. 2h1 D. h114. 一个具有567个结点的二叉树的高h为（ ）。A. 9 B. 10 C. 9566之间 D

13、. 10567之间第六章 图结构1. n条边的无向图的邻接表的存储中，边结点的个数有（ ）。A. n B. 2n C. n/2 D. nn2. n条边的无向图的邻接多重表的存储中，边结点的个数有（ ）。A. n B. 2n C. n/2 D. nn3. 下列哪一种图的邻接矩阵是对称矩阵？（ ）A. 有向图 B. 无向图 C. AOV网 D. AOE网4. 最短路径的生成算法可用（ ）。A. 普利姆算法 B. 克鲁斯卡尔算法 C. 迪杰斯特拉算法 D. 哈夫曼算法5. 一个无向图的邻接表如下图所示。（1）从顶点v0出发进行深度优先搜索，经历的结点顺序为（ ）。A. v0，v3，v2，v1 B.

14、v0，v1，v2，v3C. v0，v2，v1，v3 D. v0，v1，v3，v2（2）从顶点v0出发进行广度优先搜索，经历的结点顺序为（ ）。A. v0，v3，v2，v1 B. v0，v1，v2，v3C. v0，v2，v1，v3 D. v0，v1，v3，v26. 设有向图n个顶点和e条边，进行拓扑排序时，总的计算时间为（ ）。A. O(nlog2e) B. O(en) C. O(elog2n) D. O(ne)7. 含有n个顶点e条边的无向连通图，利用Kruskal算法生成最小生成树，其时间复杂度为（ ）。A. O(elog2e) B. O(en) C. O(elog2n) D. O(nlog

15、2n)8. 关键路径是事件结点网络中（ ）。A. 从源点到汇点的最长路径 B. 从源点到汇点的最短路径C. 最长的回路 D. 最短的回路9. 下面关于求关键路径的说法，不正确的是（ ）。A. 求关键路径是以拓扑排序为基础的B. 一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同C. 一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差D. 关键活动一定位于关键路径上10. 有10个结点的无向图至少有（ ）条边才能确保其是连通图。A. 8 B. 9 C. 10 D. 11第七章 查找1. 静态查找表与动态查找表的根本区别在于（ ）。A. 它们的逻辑结构不一

16、样 B. 施加在其上的操作不一样C. 所包含的数据元素类型不一样 D. 存储实现不一样2. 在表长为n的顺序表上实施顺序查找，在查找不成功时与关键字比较的次数为（ ）。A. n B. 1 C. n+1 D. n-13. 顺序查找适用于存储结构为（ ）的线性表。A. 散列存储 B. 压缩存储C. 顺序存储或链式存储 D. 索引存储4. 用顺序查找法对具有n个结点的线性表查找一个结点的时间复杂度为（ ）。AO(log2n2) B. O(nlog2n) C. O(n) D. O(log2n)5. 适用于折半查找的表的存储方式及元素排列要求为（ ）。A. 链接方式存储，元素无序B. 链接方式存储，元素

17、有序C. 顺序方式存储，元素无序D. 顺序方式存储，元素有序6. 有一个长度为12的有序表，按折半查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为（ ）。A. 35/12 B. 37/12 C. 39/12 D. 43/127. 在有序表1，3，9，12，32，41，62，75，77，82，95，100上进行折半查找关键字为82的数据元素需要比较（ ）次。A. 1 B. 2 C. 4 D. 58. 设散列表长为14，散列函数为H（key）= key % 11。当前表中已有4个结点：addr (15)=4，addr (38)=5，addr (61)=6，addr (84

18、)=7。如用二次探测再散列处理冲突，则关键字为49的结点的地址是（ ）。A. 8 B. 3 C. 5 D. 99. 散列函数有一个共同的性质，即函数值应当以（ ）取其值域的每个值。A. 最大概率 B. 最小概率 C. 平均概率 D. 同等概率10. 假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行（ ）次探测。A. k1次 B. k次 C. k1次 D. k（k1）/2次11. 在散列函数H（k）= k % m中，一般来讲，m应取（ ）。A. 奇数 B. 偶数 C. 素数 D. 充分大的数12. 在采用线性探测法处理冲突所构成的散列表上进行查找，可能要探测多个位

19、置，在查找成功的情况下，所探测到的这些位置上的键值（ ）。A. 一定是同义词 B. 一定不是同义词C. 都相同 D. 不一定都是同义词第八章 排序1. 在待排序的元素序列基本有序的前提下，效率最高的排序方法是（ ）。A. 插入排序 B. 选择排序 C. 快速排序 D. 归并排序2. 设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用（ ）排序法。A. 冒泡排序 B. 快速排序 C. 堆排序 D. 基数排序3. 具有12个记录的序列，采用冒泡排序最少的比较次数是（ ）。A. 1 B. 144 C. 11 D. 664. 下列四种排序方法中，要求内存容量最大的是（ ）

20、。A. 插入排序 B. 选择排序 C. 快速排序 D. 归并排序5. 初始序列已经按键值有序时，用直接插入算法进行排序，需要比较的次数为（ ）。An2 B. nlog2n C. log2n D. n16. 下列四种排序方法，在排序过程中，关键码比较的次数与记录的初始排列顺序无关的是（ ）。A. 直接插入排序和快速排序 B. 快速排序和归并排序C. 直接选择排序和归并排序 D. 直接插入排序和归并排序7. 一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为（ ）。A. 79，46，56，38，40，84 B. 84，79，56，38，40，46C. 84，

21、79，56，46，40，38 D. 84，56，79，40，46，388. 一组记录的排序码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ ）。A. 38，40，46，56，79，84 B. 40，38，46，79，56，84C. 40，38，46，56，79，84 D. 40，38，46，84，56，799. 用某种排序方法对线性表（ 25，84，21，47，15，27，68，35，20）进行排序时，元素序列的变化情况如下：（1）25，84，21，47，15，27，68，35，20（2）20，15，21，25，47，27，68，35，84（3）15，20，21，25，35，27，47，68，84（4）15，20，21，25，27，35，47，68，84则所采用的排序方法是（ ）。A. 选择排序 B. 希尔排序 C. 归并排序 D. 快速排序10. 快速排序方法在（ ）情况下最不利于发挥其长处。A. 要排序的数据量太大 B. 要排序的数据中含有多个相同值C. 要排序的数据已基本有序 D. 要排序的数据个数为奇数-