第一章 绪论1. 从逻辑上可以把数据结构分为（ C ）两大类。A动态结构、静态结构 B顺序结构、链式结构C线性结构、非线性结构 D初等结构、构造型结构2. 在下面的程序段中，对 x 的赋值语句的频度为（ C ） 。For（k=1；k next=s；s -next=p-next；Bs-next=p-next ；p- next=s；Cp- next=s；p-next=s-next；Dp- next=s-next；p- next=s；9在双向链表存储结构中，删除 p 所指的结点时须修改指针（ A ） 。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 之后插入 s 的操作是（ D ） 。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 个元素的前趋元素，则采用（ B ）存储方式最节省运算时间。A单链表 B顺序表 C双向链表 D单循环链表12. 若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。A单链表 B仅有头指针的单循环链表 C双向链表 D仅有尾指针的单循环链表第三章 栈和队列1向一个栈顶指针为 top 的链栈中插入一个 p 所指结点时，其操作步骤为（ C ）。Atop-next=p； Bp-next=top-next；top -next=p；Cp- next=top；top=p ； Dp-next=top ；top=top-next；2对于栈操作数据的原则是（ B ）。A先进先出 B后进先出C后进后出 D不分顺序3若已知一个栈的入栈序列是 1，2，3，n，其输出序列为 p1，p 2，p 3，p n，若 pn 是 n，则 Pi 为（ D ） 。Ai Bni C nil D不确定4表达式 a *（bc ） d 的后缀表达式是（ B ）。Aabcd* B abc*dCabc*d D *abcd5采用顺序存储的两个栈的共享空间 S1.m，用 topi代表第 i 个栈（i=1 ，2）的栈顶，栈 1 的底在 S1，栈 2 的底在 Sm，则栈满的条件是（ B ）。Atop2top1=0 Btop11= top2Ctop1top2 =m Dtop1= top26一个栈的入栈序列是 a，b，c ，d，e，则栈的不可能的输出序列是（ C ）。Aedcba Bdecba Cdceab Dabcde7在一个链队列中，若 f、r 分别为队首、队尾指针，则插入 p 所指结点的操作为（ B ）。Af-next=p；f=p Br-next=p ；r=pCp- next=r；r=p Dp-next=f ；f=p8用不带头结点的单链表存储队列时，在进行删除运算时（ D ）。A仅修改头指针 B仅修改尾指针C头、尾指针都要修改 D头、尾指针可能都要修改9. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（ C ）的数据结构。A队列 B静态链表 C栈 D顺序表10. 栈和队都是（ C ） 。A顺序存储的线性结构 B链式存储的非线性结构C限制存取点的线性结构 D限制存取点的非线性结构第四章 字符串及线性结构的扩展1. 下面关于串的叙述，错误的是（ C ） 。A串是字符的有限序列B串既可以采用顺序存储，也可以采用链式存储C空串是由空格构成的串D模式匹配是串的一种重要运算2. 串的长度是指（ B ） 。A串中所含不同字母的个数 B串中所含字符的个数C串中所含不同字符的个数 D串中所含非空格字符的个数3.4. 二维数组 M 的成员是 6 个字符（每个字符占一个存储单元，即一个字节）组成的串，行下标 i 的范围从 0 到 8，列下标 j 的范围从 1 到 10，则存放 M 至少需要（1） （ D ）个字节；M 的第 8 列和第 5 行共占（2） （ A ）个字节；若 M 按行优先方式存储，元素 M85的起始地址与当 M 按列优先方式存储时的（3） （ C ）元素的起始地址一致。（1）A. 90 B. 180 C. 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） （ C ） ；若该数组按行存放，元素 A85的起始地址为（2） （ D ） ；若该数组按列存放，元素 A85的起始地址为（3） （ B ） 。（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. SA+117 D. SA+2256. 稀疏矩阵采用压缩存储，一般有（ C ）两种方法。A二维数组和三维数组 B三元组和散列C三元组表和十字链表 D散列和十字链表第五章 树结构1. 下列说法正确的是（ C ） 。A二叉树中任何一个结点的度都为 2 B二叉树的度为 2C一棵 二叉树的度可小于 2 D任何一棵二叉树中至少有一个结点的度为 22. 以二叉链表作为二叉树的存储结构，在具有 n 个结点的二叉链表中（n0） ，空链域的个数为（ C ） 。A2n1 Bn1 Cnl D2nl3. 线索化二叉树中，某结点*p 没有孩子的充要条件是（ B ） 。A. p-lchild=NULL B. p-ltag=1 且 p-rtag=1C. p-ltag=0 D. p-lchild=NULL 且 p-ltag=14. 如果结点 A 有 3 个兄弟，而且 B 是 A 的双亲，则 B 的度是（ B ） 。A3 B4 C5 D15. 某二叉树 T 有 n 个结点，设按某种顺序对 T 中的每个结点进行编号，编号值为1，2，n，且有如下性质：T 中任意结点 v，其编号等于左子树上的最小编号减1，而 v 的右子树的结点中，其最小编号等于 v 左子树上结点的最大编号加 1，这是按（ B ）编号的。A. 中序遍历序列 B. 先序遍历序列 C. 后序遍历序列 D. 层次顺序6. 设 F 是一个森林，B 是由 F 转换得到的二叉树， F 中有 n 个非终端结点，B 中右指针域为空的结点有（ C ）个。An1 Bn C nl Dn27. 一棵完全二叉树上有 1001 个结点，其中叶子结点的个数是（ C ） 。A500 B501 C490 D4958. 设森林 F 中有 3 棵树，第 1、第 2 和第 3 棵树的结点个数分别为 N1，N 2 和 N3。与森林 F 对应的二叉树根结点的右子树上的结点个数是（ D ） 。AN 1 BN 1N 2 CN 2 DN 2N 39. 任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（ A ） 。A. 不发生改变 B. 发生改变 C. 不能确定 D. 以上都不对10. 若一棵二叉树的后序遍历序列为 dabec，中序遍历序列为 debac，则先序遍历序列为（ D ） 。A. cbed B. decab C. deabc D. cedba11. 若一棵二叉树的先序遍历序列为 abdgcefh，中序遍历的序列为 dgbaechf，则后序遍历的结果为（ D ） 。A. gcefha B. gdbecfha C. bdgaechf D. gdbehfca12. 一棵非空二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ B ） 。A. 所有的结点均无左孩子 B. 所有的结点均无右孩子C. 只有一个叶子结点 D. 是一棵满二叉树13. 设高度为 h 的二叉树上只有度为 0 和度为 2 的结点，则此类二叉树中所包含的结点数至少为（ B ） 。A. 2h B. 2h1 C. 2h1 D. h114. 一个具有 567 个结点的二叉树的高 h 为（ D ） 。A. 9 B. 10 C. 9566 之间 D. 10567 之间第六章 图结构1. n 条边的无向图的邻接表的存储中，边结点的个数有（ A ） 。A. n B. 2n C. n/2 D. nn2. n 条边的无向图的邻接多重表的存储中，边结点的个数有（ A ） 。A. n B. 2n C. n/2 D. nn3. 下列哪一种图的邻接矩阵是对称矩阵？（ B ）A. 有向图 B. 无向图 C. AOV 网 D. AOE 网4. 最短路径的生成算法可用（ C ） 。A. 普利姆算法 B. 克鲁斯卡尔算法 C. 迪杰斯特拉算法 D. 哈夫曼算法5. 一个无向图的邻接表如下图所示。序号 v e r t e x f i r s t e d g e13023011v 0v 1v 2v 30123（1）从顶点 v0 出发进行深度优先搜索，经历的结点顺序为（ B ） 。A. v0，v 3，v 2，v 1 B. v0，v 1，v 2，v 3C. v0， v2，v 1，v 3 D. v0，v 1，v 3，v 2（2）从顶点 v0 出发进行广度优先搜索，经历的结点顺序为（