2015级数据结构习题.doc

2015级数据结构习题第1章 绪论一、单项选择题：（从给定的选项中选择出一个最恰当的答案）1算法分析的目的是 _ 。 A找出数据结构的合理性 B研究算法中的输入和输出的关系 C分析算法的效率以求改进 D分析算法的易懂性和文档性2线性表的顺序存储结构是一种 _的存储结构。 A随机存取 B顺序存取 C索引存取 D散列存取3. 顺序存储设计时，存储单元的地址_。 A一定连续 B一定不连续 C不一定连续 D部分连续，部分不连续4. 下列数据中_是非线性数据结构。 A栈 B. 队列 C.完全二叉树 D. 串5一个算法应该是_。 A程序 B问题求解步骤的描述 C要满足五个基本特性 DA和C.6以下属于逻辑结构的是_。A顺序表 B 哈希表 C线性表 D 单链表7计算机执行下面的语句时，语句s的执行频度为 _ 。 FOR(i=l；i=i;j-) s; A O（n） BO(nlogn) C O(n3) DO(n2)8算法分析的两个主要方面是 _ 。 A空间复杂性和时间复杂性 B正确性和简明性 C可读性和文档性 D数据复杂性和程序复杂性9下面说法错误的是_. A算法原地工作的含义是指不需要增加额外的辅助空间 B. 在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 C. 所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 D.同一个算法，实现语言的级别越高，执行效率就越低10一个顺序表的第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是_。 A110 B108 C100 D12011从存储结构上可以把数据结构分为_两大类。 A动态结构、静态结构 B顺序结构、链式结构 C线性结构、非线性结构 D初等结构、构造型结构12下列叙述中正确的是_ 。A一种逻辑数据结构只能有一种存储结构。 B数据的逻辑结构属于线性结构，存储结构属于非线性结构。 C一种逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率。D一种逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率。13算法的计算量的大小称为计算的_。 A效率 B. 复杂性 C. 现实性 D. 难度14下述_是顺序存储结构的优点？ A存储密度大 B插入运算方便 C删除运算方便 D可方便地用于各种逻辑结构的存储表示15以下叙述中错误的是_。 A算法正确的程序最终一定会结束 B算法正确的程序可以有零个输出 C算法正确的程序可以有零个输入 D算法正确的程序对于相同的输入一定有相同的结果16数据结构的定义为(D，S)，其中D是_的*。 A算法 B数据元素 C数据操作 D逻辑结构17执行完下列语句段后，i值为_。 int f(int x) return (x0) ? x* f(x-1):2); int i ; i =f(f(1); A2 B 4 C 8 D 无限递归18一个递归算法必须包括_。 A. 递归部分 B. 终止条件和递归部分 C. 迭代部分 D.终止条件和迭代部分二、判断对错题：（正确的选A，错误的选B）1. 数据的逻辑结构是指数据的各数据项之间的逻辑关系。（ ）2. 顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。（ ）3. 记录是数据处理的最小单位。（ ）4. 程序一定是算法。（ ）5. 在顺序存储结构中，有时也存储数据结构中元素之间的关系。（ ）6. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构。（ ）7. 递归的算法简单、易懂、容易编写，而且执行效率也高。（ ）8. 每种数据结构都应具备三种基本运算：插入、删除和搜索。（ ）三、 应用题1. 给出圆环类的声明（内径为R1, 外径为R2）（包括求圆环面积、圆环内周长和外周长）。2. 给出等腰三角形类的声明（腰长为a, 底长为b）（包括求面积与周长）。第2章 线性表一、单项选择题：（从给定的选项中选择出一个最恰当的答案）1若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用_存储方式最节省时间。 A顺序表 B双链表 C带头结点的双循环链表 D单循环链表2以下数据结构中，_ 是线性结构。 A哈希表 B. 二叉树 C. 有向图 D. 串3设单链表中结点的结构为struct node ElemType data；struct node * Link；已知指针p所指结点不是尾结点，若在*p之后插入结点*s，则应执行下列_操作。 A s-link = p； p-link = s； B s-link = p-link； p-link = s； C s-link = p-link； p = s； D p-link = s； s-link = p；4. 在作进栈运算时,应先判别栈是否_。 A. 空 B. 满 C. 上溢 D. 下溢5若栈顶指针指向栈顶元素，当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为_。 A. n-1 B. n C. n+1 D. n/26. 若栈采用顺序存储方式存储，现两栈共享空间V1.m，topi代表第i个栈( i =1,2)栈顶，栈1的底在v1，栈2的底在Vm，若栈顶指针指向栈顶元素，则栈满的条件是_。 A. |top2-top1|=0 B. top1+1=top2 C. top1+top2=m D. top1=top27. 递归过程或函数调用时，处理参数及返回地址，要用一种称为_的数据结构。 A队列 B多维数组 C栈 D. 线性表8. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为_. A. 1和 5 B. 2和4 C. 4和2 D. 5和19.若进队列的序列为1,2,3,4 则_是一个出队列序列。 A. 3,2,1,4 B. 3,2,4,1 C. 4,3,2,1 D. 1,2,3,410在一个链队中，假设f和r分别为队首和队尾指针，则删除一个结点的运算时 _ 。 Ar=f-next; Br=r-next; Cf=f-next; Df=r-next;11线性表（ a1,a2,an）以链接方式存储时，访问第i位置元素的时间复杂性为_。 AO（i） BO（1） CO（n） DO（i-1）12删除一单向链表中P指针所指向结点的后继结点，正确的操作是_。 Ap-next=p-next-next; B p=p-next; C p-next=p； D p-next-next=p-next；13为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的_设在内存空间的两端。 A 长度 B 深度 C 栈顶 D 栈底14栈在_中应用。 A 递归调用 B 子程序调用 C 表达式求值 D A，31栈和队列都是_。 A顺序存储的线性结构 B链式存储的线性结构 C限制存取点的线性结构 D限制存取点的非线性结构15.在作退栈运算时应先判别栈是否_。 A. 空 B. 满 C. 上溢 D. 下溢16. 若一个栈的输入序列为1,2,3,n，输出序列的第一个元素是i，则第j个输出元素是_。 A. i-j-1 B. i-j C. j-i+1 D. 不确定的17在一个链队中，假设f和r分别为队首和队尾指针，则插入s所指结点的运算时 _ 。 Af-next=s; f=s; Br-next=s;r=s; Cs-next=r; r=s; Ds-next=f; f=s;18判定一个循环队列QU(最多元素为m0)为空的条件是 。AQU.front= （QU.rear+1）%m0 BQU.front！= （QU.rear+1）%m0 CQU.front= QU.rear DQU.front！= QU.rear19在单项循环链表head的末尾（rear指针指向）插入s指针指向的结点，正确操作是_。 Arear-next=s;s-next=head; Bs-next=rear; rear-next=head; C rear=s; s-next=head; Drear-next=s; s=head;20已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t到s。若字符串S=SCIENCESTUDY，则调用函数Scopy(P,Sub(S,1,7)后得到_ 。 AP=SCIENCE BP=STUDY CS=SCIENCE DS=STUDY21. 设计一个判别表达式中左，右括号是否配对出现的算法，采用_数据结构最佳。 A线性表的顺序存储结构 B. 队列 C. 线性表的链式存储结构 D. 栈22. 用链接方式存储的队列，在进行删除运算时_。 A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针都不修改23以下算法的功能是_(栈和队列的元素类型均为int)。 void algo（Stack S, int e） Stack T； int d； InitStack（T）； while (!StackEmpty(S) pop(S, d); if (d!=e ) push(T, d); while (!StackEmpty(T) pop(T, d); push(S, d); A删除栈S中的数据e B. 判断栈S中是否存在数据e C将栈S中的数据逆置 D.将栈S中的数据放入栈T中24. 以下算法的功能（栈中的数据元素类型为int）是_。 void status algo( Stack S) int i, n, a255; n=0; while (!StackEmpty(S) n+ ; Pop(S, an); for ( i=1; inext=r；q-next=r-next；r-next=q； Bp-next=r；r-next=q；q-next=r-next；Cr-next=q；q-next=r-next；p-next=r； Dr-next=q；p-next=r；q-next=r-next；28串的操作函数str定义为：int str(char*s) char *p=s；while (*p！=0)p+；return p-s；则str(abcde)的返回值是_。 A3 B4 C5 D629与线性表相比，串的插入和删除操作的特点是_。 A通常以串整体作为操作对象 B需要更多的辅助空间 C算法的时间复杂度较高 D涉及移动的元素更多30对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K%9作为散列函数，则散列地址为1的元素有_个。A1 B2 C3 D431设主串长为n，模式串长为m(mn)，则在匹配失败情况下，朴素匹配算法进行的无效位移次数为_。 Am Bn-m Cn-m+1 Dn32已知顺序表的存储结构为：typedef structElemtype v ;int length;L;以下算法的功能是_。void SortA(sqlist &L) int i=0, zerosum =0;if (L.length=0) return(0);else for( i=1; i=L.length; i+)if (L.vi0) L.vi- zerosum= L.vi;else zerosum+; A计算线性表L中非零元素数目 B将线性表L中零元素集中到表尾 C删除线性表L中的零元素 D计算线性表L中零元素数目33在下列对顺序表进行的操作中，算法时间复杂度为O(1)的是_。 A访问第i个元素的前驱( ) B在第i个元素之后插入一个新元素( ) C删除第i个元素( ) D对顺序表中元素进行排序34带头结点的单链表first为空的判定条件是_。 Afirst=NULL Bfirst-1ink=NULL Cfirst-link=first Dfirst!NULL35一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是_。 A2 3 4 1 5 B5 4 1 3 2 C2 3 1 4 5 D1 5 4 3 236设循环队列的结构是：structint dataMaxsize;int front,rear;Q;试问判断队列满的条件应是下列语句_。 AQ.front=Q.rear; BQ.front-Q.rear=Maxsize; CQ.front+Q.rear=Maxsize; DQ.front=(Q.rear+1)%Maxsize;二、判断对错题：（正确的选A，错误的选B）1. 取线性表的第i个元素的时间同i的大小有关。（ ）2. 两个栈共用静态存储空间，对头使用也存在空间溢出问题。（ ）3. 二叉树是一般树的特殊情形。（ ）4. 两个串相等的充分必要条件是分配的存储空间一样。（ ）5. 已知指针P指向键表L的某结点，执行语句P=P-next不会删除该链表中的结点。（ ）6. 在链队列中，即使不设置尾指针也能进行入队操作。（ ）7. 循环链表不是线性表. 。（ ）8. 顺序存储结构通过数据元素存储的位置表示元素之间的关系。（ ）9. 队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。（ ）10. 循环队列的引入，目的是为了克服假溢出。（ ）11. 链表中的头结点仅起到标识的作用。（ ）12. 对顺序表上的插入、删除算法的时间复杂性分析来说，通常以结点移动量为标准分析。（ ）13. 为了很方便的插入和删除数据，可以使用双向链表存放数据。（ ）14. 栈是实现过程和函数等子程序所必需的结构。（ ）15. 在执行简单的串匹配算法时，最坏的情况为每次匹配比较不等的字符出现的位置均为模式串的最末字符。（ ）16. 在单链表中，指针p指向元素为x的结点，实现删除x的后继的语句是p-next=p-next-next。（ ）17. 通常将链串的结点大小设置为大于1是为了提高存储密度。（ ）18. 线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。（ ）19. 单链表从任何一个结点出发，都能访问到所有结点。（ ）20. 在数据结构中，空串和空格串的概念是一样的。（ ）21. 如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串。（ ）22. 循环队列通常用指针来实现队列的头尾相接。（ ）23. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动将后续单元向前移动。（ ）三、应用题1借助堆栈将(A+B)*(C-D)*E+F)转换成后缀表达式，写出转换过程。2借助堆栈计算后缀表达式ABC*/DE*+AC*，写出计算过程。第3章 树一、单项选择题：（从给定的选项中选择出一个最恰当的答案）1在按层次遍历二叉树的算法中，需要借助的辅助数据结构是_ A队列 B栈 C线性表 D有序表2在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系_. A不一定相同 B都相同 C都不相同 D互为逆序3. 在下述结论中，正确的是_. 只有一个结点的二叉树的度为0; 二叉树的度为2；二叉树的左右子树可任意交换; 深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A B C D4. 树是结点的有限*，它_根结点，记为T。其余结点分成为m（m=0）个互不相交的*T1，T2， ，m，每个*又都是树。 A. 有0个或1个 B. 有0个或多个 C. 有且只有一个 D. 有1个或1个以上5若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是_. A9 B11 C15 D不确定6对于有n 个结点的二叉树, 其高度为_. Anlog2n Blog2n Clog2n+1 D不确定7. 利用二叉链表存储树，则根结点的右指针是_。 A指向最左孩子 B指向最右孩子 C空 D非空8已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为_。 ACBEFDA B FEDCBA C CBEDFA D不定9下面关于串的的叙述中，_是不正确的？ A串是字符的有限序列 B空串是由空格构成的串 C模式匹配是串的一种重要运算 D串既可以采用顺序存储，也可以采用链式存储10有关二叉树下列说法正确的是_。 A二叉树的度为2 B一棵二叉树的度可以小于2 C二叉树中至少有一个结点的度为2 D二叉树中任何一个结点的度都为211在一棵高度为k的满二叉树中，结点总数为_。 A2k-1 B2k C2k-1 Dlog2k+112树的后根遍历序列等同于该树对应的二叉树的_。 A 先序序列 B中序序列 C后序序列 D层次序列13对于前序遍历和中序遍历结果相同的二叉树为_。 A根结点无左孩子的二叉树 B根结点无右孩子的二叉树 C所有结点只有左子树的二叉树 D所有结点只有右子树的二叉树14下面的说法中正确的是_。 （1）任何一棵二叉树的叶子结点在三种遍历中的相对次序不变； （2）按二叉树定义，具有三个结点的二叉树共有6种。 A(1)(2) B(1) C(2) D(1)、(2)都错15在完全二叉树中，若一个结点是叶结点，则它没_。 A左子结点 B右子结点 C左子结点和右子结点 D左子结点，右子结点和兄弟结点16假设用于通信的电文由8个字母组成，其频率分别为0.07、0.19、0.02、0.06、 0.32、0.03、0.21、0.10, 为这8个字母设计哈夫曼编码，其中编码长度最大的字母的编码是_位。 A4 B5 C 6 D717采用邻接表存储的图的深度优先遍历算法类似于树的_。 A中根遍历 B先根遍历 C后根遍历 D按层次遍历18在n(n0)个元素的顺序栈中删除1个元素的时间复杂度为_。 AO(n) BO(nlog2n) CO(1) DO( )19若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用_遍历方法最合适。 A前序 B中序 C后序 D按层次20由3 个结点可以构造出_种不同的二叉树？ A2 B3 C4 D521设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为_。 A求子串 B联接 C匹配 D求串长22若串P=”structure”,其子串的数目是_。 A46 B45 C41 D4023设森林F对应的二叉树为B，它有m个结点，B的根为P, P的右子树结点个数为n,森林F中第一棵树的结点个数是_。 Am-n Bm-n-1 Cn+1 D条件不足，无法确定24二叉树的第I层上最多含有结点数为_。 A2I B 2I-1-1 C 2I-1 D2I -125在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为_个 A4 B5 C6 D726以下算法的功能是_。int BTreeDepth(Btree *BT) /*BT为二叉树某结点的指针int leftdep, rightdep;if(BT=NULL) return(0);leftdep=BTreeDepth(BT-left);rightdep=BTreeDepth(BT-right);if( leftdeprightdep)return(leftdep+1);else return(rightdep+1); A求二叉树的深度 B求二叉树结点数目 C先序遍历二叉树的结点 D求二叉树叶子结点的数目二、判断对错题：（正确的选A，错误的选B）1. 二叉树是一般树的特殊情形。（ ）2. 树最适合用来表示元素之间具有分支层次关系的数据。（ ）3. 哈夫曼树度为1的结点数等于度为2和0的结点数之差。（ ）4. 完全二叉树一定存在度为1的结点。（ ）5. 对一棵二叉树进行层次遍历时，应借助于一个栈。（ ）6. 二叉树只能用二叉链表表示。（ ）7. 树中的结点和图中的顶点就是指数据结构中的数据元素。（ ）8. 度为二的树就是二叉树。（ ）9. 二叉树的遍历结果不是唯一的。（ ）10. 将一棵树转换为二叉树后，根结点没有左子树。（ ）11. 对于一棵二叉树，如果度为2的结点数为n个，则叶子结点数为n1个。（ ）12. 对一棵有n个结点，高度为h的二叉树，进行任一种次序遍历的时间复杂度为O(h)。（ ）13. 在树中，如果从结点K出发，存在两条分别到达K，K”的长度相等的路径，则结点K和k”互为兄弟。（ ）三、应用题1. 证明存在这样的二叉树：其叶子节点在先根次序、中根次序、后根次序下的都按相同的相对位置出现（即每个叶子节点在先根次序、中根次序、后根次序排序结果中的位置相同）。3. 某二叉树的结点数据采用顺序存储表示如下：012345678910111213CABDEFG(1) 试画出此二叉树的图形表示。 (2分)(2) 写出结点D的双亲结点及左、右子女。 (2分)(3) 将此二叉树看作森林的二叉树表示，试将它还原为森林。(2分)3. 根据下面给定的几个数（6，11，6， 12，8，18，12，7，4）构造一颗赫夫曼树，并求出其带权路径长度。（给出具体过程）4. 假如一颗二叉树有5个节点，请画出满足下列条件的所有二叉树：（1） 先根序列和中根序列相同；（2） 中根序列和后根序列相同；5. 分别画出有A、B、C、D三个节点所组成的所有树和所有二叉树。6. 若一棵度为4的树中有n(1)个度为1的节点个数，n(2)个度为2的节点个数，n(3)个度为3的节点个数，n(4)个度为4的节点个数，问该树有多少个叶节点？第4章 图一、单项选择题：（从给定的选项中选择出一个最恰当的答案）1具有4个顶点的无向完全图有 _ 条边。 A20 B 16 C 12 D 62在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 _ 倍。 A4 B2 C 1 D1/23图中有关路径的定义是_。 A由顶点和相邻顶点序偶构成的边所形成的序列 B由不同顶点所形成的序列 C由不同边所形成的序列 D上述定义都不是4设无向图的顶点个数为n，则该图最多有_条边。 An-1 Bn(n-1)/2 C n(n+1)/2 Dn25要连通具有n个顶点的有向图，至少需要_条边。 An-l Bn Cn+l D2n6从邻接阵矩 可以看出，该图共有_个顶点。 A9 B3 C6 D17设图如右所示，在下面的5个序列中，符合深度优先遍历的序列有_。 a e b d f c a c f d e b a e d f c b a e f d c b a e f d b c A5个 B4个 C3个 D2个8在图采用邻接表存储时（n是图的顶点数，e是图的边数），求最小生成树的 Prim 算法的时间复杂度为_。 A O(n) B O(n+e) CO(n2) D O(n3)9n个结点的完全有向图含有边的数目_。 An*n n（n） Cn2 Dn*（nl）10无向图G=(V,E),其中：V=a,b,c,d,e,f,E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)，对该图进行深度优先遍历，得到的顶点序列正确的是_。 Aa,b,e,c,d,f Ba,c,f,e,b,d Ca,e,b,c,f,d Da,e,d,f,c,b11若以4, 5, 6, 3, 8作为叶子结点的权值构造哈夫曼树，则带权路径长度是 。 A 28 B 55 C 59 D 6812设m, n为一棵二叉树上的两个结点，在中序遍历时， n在m前的条件是 。 An在m右方 Bn是m 祖先 Cn在m左方 Dn是m子孙13 下列说法不正确的是_。 A图的遍历是从给定的源点出发每一个顶点仅被访问一次 B图的深度遍历不适用于有向图 C遍历的基本算法有两种：深度遍历和广度遍历 D图的深度遍历是一个递归过程14当各边上的权值_时，BFS算法可用来解决单源最短路径问题。 A均相等 B均互不相等 C不一定相等 D. 均相等或均不等15用Prim算法求下列连通的带权图的最小代价生成树，在算法执行的某刻，已选取的顶点*U1，2，5，边的*TE（1，2），（2，5），要选取下一条权值最小的边，应当从_组中选取。 A（1，4），（3，4），（3，5），（2，5） B（5，4），（5，3），（5，6） C（1，2），（2，3），（3，5） D（3，4），（3，5），（4，5），（1，4）16下面算法的功能是_。int count(adjmatrix GA，int i，int n)int d=0;for (int j=0; jnext;L是一带头结点单链表，结点有数据域 data和指针域 nextif (pre!=null)while (pre-next!=null)p=pre-next; if(p-data=pre-data) pre=p ELSE return(false)return(true); A判断L中相邻的两个结点是否升序排列 B判断L中相邻的两个结点是否降序排列 C判断L中的结点是否升序排列 D判断L中的结点是否降序排列5若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为_。 A (n-1)/2 B n/2 C (n+1)/2 D n6下列排序方法中，_不是稳定的排序方法？ A直接选择排序 B二分法插入排序 C二路归并排序 D快速排序7. 既希望较快的查找又便于线性表动态变化的查找方法是 _ 。 A顺序查找 B. 折半查找 C. 索引顺序查找 D. 哈希法查找8.以下算法的功能（栈中的数据元素类型为int）是_。void algo（Queue &Q）Stack S； int d；InitStack（S）；while (!QueueEmpty(Q) DeQueue(Q,d); Push(S,d);；while (!StackEmpty(S) pop(S,d); EnQueue(Q,d); A将栈S中的元素逆置 B将队列Q中的元素逆置 C输出栈S中的元素 D输出队列Q中的元素9当采用分快查找时，数据的组织方式为_。 A数据分成若干块，每块内数据有序 B数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块 C 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块 D 数据